分布式限流的主流方案

Love The Way You Lie 2022-10-07 12:51 198阅读 0赞

# 前言 #

详看文章，O(∩\_∩)O哈哈~

--------------------

# 常见的分布式限流方案 #

细数一下分布式限流都有哪些常见方案。话说条条大道通罗马，实现分布式限流的方案之多，两只手加起来都数不过来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70]  
说起Guava大家一定不陌生，它是Google出品的一款工具包（com.google.guava），我们经常用它做一些集合操作比如  
Lists.newArrayList()，它最早源于2007年的"Google Collections Library"项目。Guava不甘于将自己平凡的一生都耗费在Collections上面，于是乎它开始了转型，慢慢扩展了自己在Java领域的影响力，从反射工具、函数式编程、安全验证、数学运算等等方面，都提供了响应的工具包。  
在限流这个领域中，Guava也贡献了一份绵薄之力，在其多线程模块下提供了以RateLimiter为首的几个限流支持类。我们前面提到了，Guava是一个客户端组件，也就是说它的作用范围仅限于“当前”这台服务器，不能对集群以内的其他服务器施加流量控制。  
![在这里插入图片描述][20210618090217339.png]

打个比方，目前我有2台服务器\[Server 1，Server 2\]，这两台服务器都部署了一个登陆服务，假如我希望对这两台机器的流量进行控制，比如将两台机器的访问量总和控制在每秒20以内，如果用Guava来做，只能独立控制每台机器的访问量<=10。  
尽管Guava不是面对分布式系统的解决方案，但是其作为一个简单轻量级的客户端限流组件，非常适合来讲解限流算法。

# 网关层限流 #

剑阁峥嵘而崔嵬，一夫当关，万夫莫开  
–《蜀道难》李白

在整个分布式系统中，如果有这么一个“一夫当关，万夫莫开”的角色，非网关层莫属。服务网关，作为整个分布式链路中的第一道关卡，承接了所有用户来访请求.  
网关层限流的架构考量

漏斗是个好东西，不仅可以用来打香油，还可以应用在很多系统设计的领域，我们将系统流量的分布层次抽象成一个简单的漏斗模型来看  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 1]  
上面是一个最普通的流量模型，从上到下的路径依次是：  
用户流量从网关层转发到后台服务,后台服务承接流量，调用缓存获取数据,缓存中无数据，则访问数据库.

为什么说它是一个漏斗模型

因为流量自上而下是逐层递减的，在网关层聚集了最多最密集的用户访问请求，其次是后台服务。然后经过后台服务的验证逻辑之后，刷掉了一部分错误请求，剩下的请求落在缓存上，如果缓存中没有数据才会请求漏斗最下方的数据库，因此数据库层面请求数量最小（相比较其他组件来说数据库往往是并发量能力最差的一环，阿里系的MySQL即便经过了大量改造，单机并发量也无法和Redis、Kafka之类的组件相比）  
如果在上面这个漏斗模型中做流量限制，大家觉得在哪个环节最合适？五四三二一，揭晓答案–网关层，它首当其冲对不对？因为它是整个访问链路的源头，是所有流量途径的第一站。目前主流的网关层有以软件为代表的Nginx，还有Spring Cloud中的Gateway和Zuul这类网关层组件，也有以硬件+软件为代表的F5（F5价钱贵到你怀疑人生）

Nginx里的几种核心限流模式：  
基于IP地址和基于服务器的访问请求限流  
并发量（连接数）限流  
下行带宽速率限制

# 中间件限流 #

对于分布式环境来说，无非是需要一个类似中心节点的地方存储限流数据。打个比方，如果我希望控制接口的访问速率为每秒100个请求，那么我就需要将当前1s内已经接收到的请求的数量保存在某个地方，并且可以让集群环境中所有节点都能访问。那我们可以用什么技术来存储这个临时数据呢？这个场景天然适合我们的中间件大显神威！而且还得需要支持超高并发的中间件，谁能堪此重任？  
一并中间件这下起劲儿了，纷纷表示“选我选我选我”。数据库行不行？不行，并发量不够。Message Queue行不行？好像MQ的运作模式不太适合这个场景，而且并发量也就差强人意。Kafka行不行，嗯，并发量杠杠的，是个Option。那Redis呢？OMG，憋说话就你了！理由这就给足你！  
![在这里插入图片描述][20210618090323138.png]  
Redis简直就是为服务端限流量身打造的利器。利用Redis过期时间特性，我们可以轻松设置限流的时间跨度（比如每秒10个请求，或者每10秒10个请求）。

同时Redis还有一个特殊技能–脚本编程，我们可以将限流逻辑编写成一段脚本植入到Redis中，这样就将限流的重任从服务层完全剥离出来，同时Redis强大的并发量特性以及高可用集群架构也可以很好的支持庞大集群的限流访问。

☆ 限流组件

除了上面介绍的几种方式以外，目前也有一些开源组件提供了类似的功能，比如Sentinel就是一个不错的选择。Sentinel是阿里出品的开源组件，并且包含在了Spring Cloud Alibaba组件库中。

☆从架构维度考虑限流设计

在真实的大型项目里，不会只使用一种限流手段，往往是几种方式互相搭配使用，让限流策略有一种层次感，达到资源的最大使用率。在这个过程中，限流策略的设计也可以参考前面提到的漏斗模型，上宽下紧，漏斗不同部位的限流方案设计要尽量关注当前组件的高可用。以我参与的实际项目为例，比如说我们研发了一个商品详情页的接口，通过手机淘宝导流，app端的访问请求首先会经过阿里的mtop网关，在网关层我们的限流会做的比较宽松，等到请求通过网关抵达后台的商品详情页服务之后，再利用一系列的中间件+限流组件，对服务进行更加细致的限流控制（这里面还会包含熔断降级等一系列复杂的异常处理.

# 限流方案常用算法讲解 #

限流方案常用算法讲解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 2]  
天下武学出同源

正所谓天下武学殊途同归，不管是Nginx限流还是Redis限流，也不管招式耍的再花哨，到了最后都是应用几种特定的限流算法。

常见的限流算法一只手都可以数的过来，令牌桶算法、漏桶算法、滑动窗口和计数器算法来讲一下。

令牌桶算法

Token Bucket令牌桶算法是目前应用最为广泛的限流算法，顾名思义，它有以下两个关键角色：

☆令牌  
获取到令牌的Request才会被处理，其他Requests要么排队要么被直接丢弃。

☆桶  
用来装令牌的地方，所有Request都从这个桶里面获取令牌

了解了这两个角色之后，让我们来看一下令牌桶算法的图示：  
![在这里插入图片描述][20210618090554343.png]  
下面我们分别从令牌生成和令牌获取两个流程来解读令牌桶算法：

☆ 令牌生成

这个流程涉及到令牌生成器和令牌桶，前面我们提到过令牌桶是一个装令牌的地方，既然是个桶那么必然有一个容量，也就是说令牌桶所能容纳的令牌数量是一个固定的数值。

对于令牌生成器来说，它会根据一个预定的速率向桶中添加令牌，比如我们可以配置让它以每秒100个请求的速率发放令牌，或者每分钟50个。注意这里的发放速度是匀速，也就是说这50个令牌并非是在每个时间窗口刚开始的时候一次性发放，而是会在这个时间窗口内匀速发放。

在令牌发放器就是一个水龙头，假如在下面接水的桶子满了，那么自然这个水（令牌）就流到了外面。在令牌发放过程中也一样，令牌桶的容量是有限的，如果当前已经放满了额定容量的令牌，那么新来的令牌就会被丢弃掉。

☆ 令牌获取

每个访问请求到来后，必须获取到一个令牌才能执行后面的逻辑。假如令牌的数量少，而访问请求较多的情况下，一部分请求自然无法获取到令牌，那么这个时候我们可以设置一个“缓冲队列”来暂存这些多余的令牌。

缓冲队列其实是一个可选的选项，并不是所有应用了令牌桶算法的程序都会实现队列。当有缓存队列存在的情况下，那些暂时没有获取到令牌的请求将被放到这个队列中排队，直到新的令牌产生后，再从队列头部拿出一个请求来匹配令牌。

当队列已满的情况下，这部分访问请求将被丢弃。在实际应用中我们还可以给这个队列加一系列的特效，比如设置队列中请求的存活时间，或者将队列改造为PriorityQueue，根据某种优先级排序，而不是先进先出。算法是死的，人是活的，先进的生产力来自于不断的创造，在技术领域尤其如此。

漏桶算法

Leaky Bucket。瞧见没，又是个桶，限流算法是跟桶杠上了，那么漏桶和令牌桶有什么不同呢？我们来看图说话：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 3]  
漏桶算法的前半段和令牌桶类似，但是操作的对象不同，令牌桶是将令牌放入桶里，而漏桶是将访问请求的数据包放到桶里。同样的是，如果桶满了，那么后面新来的数据包将被丢弃。

漏桶算法的后半程是有鲜明特色的，它永远只会以一个恒定的速率将数据包从桶内流出。打个比方，如果我设置了漏桶可以存放100个数据包，然后流出速度是1s一个，那么不管数据包以什么速率流入桶里，也不管桶里有多少数据包，漏桶能保证这些数据包永远以1s一个的恒定速度被处理。

# 漏桶 vs 令牌桶的区别 #

根据它们各自的特点不难看出来，这两种算法都有一个“恒定”的速率和“不定”的速率。  
令牌桶是以恒定速率创建令牌，但是访问请求获取令牌的速率“不定”，反正有多少令牌发多少，令牌没了就干等。  
而漏桶是以“恒定”的速率处理请求，但是这些请求流入桶的速率是“不定”的。

从这两个特点来说，漏桶的天然特性决定了它不会发生突发流量，就算每秒1000个请求到来，那么它对后台服务输出的访问速率永远恒定。  
而令牌桶则不同，其特性可以“预存”一定量的令牌，因此在应对突发流量的时候可以在短时间消耗所有令牌，其突发流量处理效率会比漏桶高，但是导向后台系统的压力也会相应增多。

☆滑动窗口

Rolling Window，穿上你的滑板鞋，跟我一起摇摆。

![在这里插入图片描述][20210618090647723.png]  
上图中黑色的大框就是时间窗口，我们设定窗口时间为5秒，它会随着时间推移向后滑动。我们将窗口内的时间划分为五个小格子，每个格子代表1秒钟，同时这个格子还包含一个计数器，用来计算在当前时间内访问的请求数量。那么这个时间窗口内的总访问量就是所有格子计数器累加后的数值。

比如说，我们在每一秒内有5个用户访问，第5秒内有10个用户访问，那么在0到5秒这个时间窗口内访问量就是15。如果我们的接口设置了时间窗口内访问上限是20，那么当时间到第六秒的时候，这个时间窗口内的计数总和就变成了10，因为1秒的格子已经退出了时间窗口，因此在第六秒内可以接收的访问量就是20-10=10个。

滑动窗口其实也是一种计算器算法，它有一个显著特点，当时间窗口的跨度越长时，限流效果就越平滑。打个比方，如果当前时间窗口只有两秒，而访问请求全部集中在第一秒的时候，当时间向后滑动一秒后，当前窗口的计数量将发生较大的变化，拉长时间窗口可以降低这种情况的发生概率

# Guava RateLimiter预热模型 #

☆ 什么是流量预热

我们都知道在做运动之前先得来几组拉伸之类的动作，给身体做个热身，让我们的身体平滑过渡到后面的剧烈运动中。流量预热也是一样的道理，对限流组件来说，流量预热就类似于一种热身运动，它可以动态调整令牌发放速度，让流量变化更加平滑。

我们来举一个例子：某个接口设定了100个Request每秒的限流标准，同时使用令牌桶算法做限流。假如当前时间窗口内都没有Request过来，那么令牌桶中会装满100个令牌。如果在下一秒突然涌入100个请求，这些请求会迅速消耗令牌，对服务的瞬时冲击会比较大。因此我们需要一种类似“热身运动”的缓冲机制，根据桶内的令牌数量动态控制令牌的发放速率，让忙时流量和闲时流量可以互相平滑过渡。

☆流量预热的做法

我们以Guava中的RateLimiter为例，看看流量预热在RateLimiter中是如何运作的，我们用下面的状态转换图来展示整个过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 4]  
横坐标是令牌桶的当前容量，纵坐标是令牌发放速率，我们先从横坐标来分析

☆横坐标

下面两种场景会导致横坐标的变化：

闲时流量 流量较小或者压根没流量的时候，横坐标会逐渐向右移动，表示令牌桶中令牌数量增多，忙时流量 当访问流量增大的时候，横坐标向左移动，令牌桶中令牌数量变少，横轴有两个重要的坐标，一个是最右侧的“令牌桶最大容量”，这个不难理解。还有一个是Half容量，它是一个关键节点，会影响令牌发放速率。

☆纵坐标

纵坐标表示令牌的发放速率，这里有3个标线，分别是稳定时间间隔，2倍间隔，3倍间隔。

这里间隔的意思就是隔多长时间发放一个令牌，而所谓稳定间隔就是一个基准时间间隔。假如我们设置了每秒10个令牌的限流规则，那么稳定间隔也就是1s/10=0.1秒，也就是说每隔0.1秒发一个令牌。相应的，3倍间隔的数值是用稳定间隔乘以系数3，比如上面这个例子中3倍间隔就是0.3秒。

☆运作模式

了解了横坐标和纵坐标的含义之后，让我们来试着理解预热模型的用例。继续沿用上面10r/s的限流设置，稳定间隔=0.1s，3x间隔是0.3s。

我们先考虑闲时到忙时的流量转变，假定当前我们处于闲时流量阶段，没几个访问请求，这时令牌桶是满的。接着在下一秒突然涌入了10个请求，这些请求开始消耗令牌桶中的令牌。在初始阶段，令牌的放行速度比较慢，在第一个令牌被消耗以后，后面的请求要经过3x时间间隔也就是0.3s才会获取第二块令牌。随着令牌桶中令牌数量被逐渐消耗，当令牌存量下降到最大容量一半的时候（Half位置），令牌放行的速率也会提升，以稳定间隔0.1s发放令牌。

反过来也一样，在流量从忙时转变为闲时的过程中，令牌发放速率是由快到慢逐渐变化。起始阶段的令牌放行间隔是0.1s，随着令牌桶内令牌逐渐增多，当令牌的存量积累到最大容量的一半后，放行令牌的时间间隔进一步增大为0.3s。

RateLimiter正是通过这种方式来控制令牌发放的时间间隔，从而使流量的变化更加平滑。  
核心代码

理解了预热模型的运作流程之后，我们来看一下具体代码是如何实现的。  
实现流量预热的类是SmoothWarmingUp，它是SmoothRateLimiter的一个内部类，我们重点关注一个doSetRate方法，它是计算横纵坐标系关键节点的方法，先来看一下SmoothRateLimiter这个父类中定义的方法

// permitsPerSecond表示每秒可以发放的令牌数量
    @Override
    final void doSetRate(double permitsPerSecond, long nowMicros) { 
    resync(nowMicros);
    
    // 计算稳定间隔，使用1s除以令牌桶容量
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
    this.stableIntervalMicros = stableIntervalMicros;
    
    // 调用SmoothWarmingUp类中重载的doSetRate方法
    doSetRate(permitsPerSecond, stableIntervalMicros);
    }

父类在这里的作用主要是计算出了稳定时间间隔（使用1s / 每秒放行数量的公式来计算得出），然后预热时间、三倍间隔等是在子类的doSetRate方法中实现的。  
接下来我们看子类SmoothWarmingUp中的doSetRate做了什么

@Override
    void doSetRate(double permitsPerSecond, double stableIntervalMicros) { 
    	double oldMaxPermits = maxPermits;
    	
    	// maxPermits表示令牌桶内最大容量，它由我们设置的预热时间除以稳定间隔获得
    	// 打个比方，如果stableIntervalMicros=0.1s，而我们设置的预热时间是2s
    	// 那么这时候maxPermits就是2除以0.1=20
    	maxPermits = warmupPeriodMicros / stableIntervalMicros;
    	
    	// 这句不用解释了吧，halfPermits是最大容量的一半
    	halfPermits = maxPermits / 2.0;
    
    	// coldIntervalMicros就是我们前面写到的3倍间隔，通过稳定间隔*3计算得出
    	// 稳定间隔是0.1，3倍间隔是0.2，那么平均间隔是0.2
    	double coldIntervalMicros = stableIntervalMicros * 3.0;
    	
    	// slope的意思是斜率，也就是前面我们图中预热阶段中画出的斜线（速率从稳定间隔向3x间隔变化的斜线）
    	// 它的计算过程就是一个简单的求斜率公式
    	slope = (coldIntervalMicros - stableIntervalMicros) / halfPermits;
    	
    	// 计算目前令牌桶的令牌个数
    	if (oldMaxPermits == Double.POSITIVE_INFINITY) { 
    		// 如果令牌桶最大容量是无穷大，则设置当前可用令牌数为0
    		// 说实话这段逻辑没什么用
    	storedPermits = 0.0;
    	} else { 
    	storedPermits = (oldMaxPermits == 0.0)
    	? maxPermits // 初始化的状态是3x间隔
    	: storedPermits * maxPermits / oldMaxPermits;
    }
    }

通过上面的两个函数，RateLimiter限流器就对maxPermits和slope（预热期斜率）两个变量做了初始化配置。我把关键步骤都注释在了代码里，大家理解了之后，可以尝试去阅读这个类的其他方法，弄清maxPermits和slope是如何影响令牌发放速率的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70]: /images/20221005/29e9a2cb14f0455fb433d204bce06301.png
[20210618090217339.png]: /images/20221005/613c51200b914bf5840ddce2d87b389a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 1]: /images/20221005/33cfc49e7166470788706a7a64528578.png
[20210618090323138.png]: /images/20221005/5ac5e6ce065f4a0fa318bba191e83810.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 2]: /images/20221005/849103a8c33b47e9be10da082755bb22.png
[20210618090554343.png]: /images/20221005/32dda630cbf244c396f0c0d2a9a71a2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 3]: /images/20221005/60aabdced93b4af0b1b78843b3cf4c09.png
[20210618090647723.png]: /images/20221005/6a00dd7dbac74ecd9259bdfe566adf56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMzcwOTEz_size_16_color_FFFFFF_t_70 4]: /images/20221005/f9268b3c38e14adabda3615833b65e20.png