高并发系统的限流算法_高并发服务限流算法

分布式环境下应对高并发保证服务稳定几招，按照个人理解，优先级从高到低分别为缓存、限流、降级、熔断，每招都有它的作用，本文重点就讲讲限流这部分。
坦白讲，其实上面的说法也不准确，因为服务降级、熔断本身也是限流的一种，因为它们本质上也是阻断了流量进来，但是本文希望大家可以把限流当做一个单纯的名词来理解，看一下对请求做流控的几种算法及具体实现方式。
其实很好理解的一个问题，为什么要限流，自然就流量过大了呗，一个对外服务有很多场景都会流量增大：
注意这个"大"，1000QPS大吗？5000QPS大吗？10000QPS大么？没有答案，因为没有标准，因此，"大"一定是和正常流量相比的大。流量一大，服务器扛不住，扛不住就挂了，挂了没法提供对外服务导致业务直接熔断。怎么办，最直接的办法就是从源头把流量限制下来，例如服务器只有支撑1000QPS的处理能力，那就每秒放1000个请求，自然保证了服务器的稳定，这就是限流。
下面看一下常见的两种限流算法。
漏桶算法的原理比较简单，水（请求）先进入到漏桶里，人为设置一个最大出水速率，漏桶以<=出水速率的速度出水，当水流入速度过大会直接溢出（拒绝服务）：

因此，这个算法的核心为：
因此这是一种强行限制请求速率的方式，但是缺点非常明显，主要有两点：
所以，通常来说利用漏桶算法来限流，实际场景下用得不多。
令牌桶算法
令牌桶算法是网络流量整形（Traffic Shaping）和限流（Rate Limiting）中最常使用的一种算法，它可用于控制发送到网络上数据的数量并允许突发数据的发送。
从某种意义上来说，令牌桶算法是对漏桶算法的一种改进，主要在于令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用，来看下令牌桶算法的实现原理：

整个的过程是这样的：
那么，我们再看一下，为什么令牌桶算法可以防止一定程度的突发流量呢？可以这么理解，假设我们想要的速率是1000QPS，那么往桶中放令牌的速度就是1000个/s，假设第1秒只有800个请求，那意味着第2秒可以容许1200个请求，这就是一定程度突发流量的意思，反之我们看漏桶算法，第一秒只有800个请求，那么全部放过，第二秒这1200个请求将会被打回200个。
注意上面多次提到一定程度这四个字，这也是我认为令牌桶算法最需要注意的一个点。假设还是1000QPS的速率，那么5秒钟放1000个令牌，第1秒钟800个请求过来，第2~4秒没有请求，那么按照令牌桶算法，第5秒钟可以接受4200个请求，但是实际上这已经远远超出了系统的承载能力，因此使用令牌桶算法特别注意设置桶中令牌的上限即可。
总而言之，作为对漏桶算法的改进，令牌桶算法在限流场景下被使用更加广泛。
上面说了令牌桶算法在限流场景下被使用更加广泛，接下来我们看一下代码示例，模拟一下每秒最多过五个请求：
利用RateLimiter.create这个构造方法可以指定每秒向桶中放几个令牌，比方说上面的代码create(5)，那么每秒放置5个令牌，即200ms会向令牌桶中放置一个令牌。这边代码写了一条线程模拟实际场景，拿到令牌那么就能执行下面逻辑，看一下代码执行结果：
看到，非常标准，在每次消耗一个令牌的情况下，RateLimiter可以保证每一秒内最多只有5个线程获取到令牌，使用这种方式可以很好的做单机对请求的QPS数控制。
至于为什么2019-08-25 20:58:53这个时间点只有1条线程获取到了令牌而不是有5条线程获取到令牌，因为RateLimiter是按照秒计数的，可能第一个线程是2019-08-25 20:58:53.999秒来的，算在2019-08-25 20:58:53这一秒内；下一个线程2019-08-25 20:58:54.001秒来，自然就算到2019-08-25 20:58:54这一秒去了。
上面的写法是RateLimiter最常用的写法，注意：
处理请求，每次来一个请求就acquire一把是RateLimiter最常见的用法，但是我们看acquire还有个acquire(int permits)的重载方法，即允许每次获取多个令牌数。这也是有可能的，请求数是一个大维度每次扣减1，有可能服务器按照字节数来进行限流，例如每秒最多处理10000字节的数据，那每次扣减的就不止1了。
接着我们再看一段代码示例：
代码运行结果为：
看到这就是标题所说的预消费能力，也是RateLimiter中允许一定程度突发流量的实现方式。第二次需要获取5个令牌，指定的是每秒放1个令牌到桶中，我们发现实际上并没有等5秒钟等桶中积累了5个令牌才能让第二次acquire成功，而是直接等了1秒钟就成功了。我们可以捋一捋这个逻辑：
也就是说，前面的请求如果流量大于每秒放置令牌的数量，那么允许处理，但是带来的结果就是后面的请求延后处理，从而在整体上达到一个平衡整体处理速率的效果。
突发流量的处理，在令牌桶算法中有两种方式，一种是有足够的令牌才能消费，一种是先消费后还令牌。后者就像我们0首付买车似的，30万的车很少有等攒到30万才全款买的，先签了相关合同把车子给你，然后贷款慢慢还，这样就爽了。RateLimiter也是同样的道理，先让请求得到处理，再慢慢还上预支的令牌，客户端同样也爽了，否则我假设预支60个令牌，1分钟之后才能处理我的请求，不合理也不人性化。
RateLimiter的限制
特别注意RateLimiter是单机的，也就是说它无法跨JVM使用，设置的1000QPS，那也在单机中保证平均1000QPS的流量。
假设集群中部署了10台服务器，想要保证集群1000QPS的接口调用量，那么RateLimiter就不适用了，集群流控最常见的方法是使用强大的Redis：
总得来说，集群限流的实现也比较简单。
本文主要写了常见的两种限流算法漏桶算法与令牌桶算法，并且演示了Guava中RateLimiter的实现，相信看到这里的朋友一定都懂了，恭喜你们！
令牌桶算法是最常用的限流算法，它最大的特点就是容许一定程度的突发流量。
漏桶算法同样也有自己的应用之处，例如Nginx的限流模块就是基于漏桶算法的，它最大的特点就是强行限制流量按照指定的比例下发，适合那种对流量有绝对要求的场景，就是流量可以容许在我指定的值之下，可以被多次打回，但是无论如何决不能超过指定的。
虽然令牌桶算法相对更好，但是还是我经常说的，使用哪种完全就看大家各自的场景，适合的才是最好的。

开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。

缓存：缓存的目的是提升系统访问速度和增大系统处理容量。
降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。
限流：限流的目的是通过对并发请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以进行拒绝服务、排队或等待、降级等处理。
限流是限制系统的输入和输出流量，以达到保护系统的目的，而限流的实现主要是依靠限流算法，限流算法主要有4种：

固定时间窗口算法（计数器）
滑动时间窗口算法
令牌桶算法
漏桶算法

1. 固定时间窗口算法

又称计数器算法。固定时间窗口算法就是统计记录单位时间内进入系统或者某一接口的请求次数，在限定的次数内的请求则正常接收处理，超过次数的请求则拒绝掉或者改为异步处理等限流措施。

时间窗口长度如果为1分钟，如图。

计数器算法

此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性即可轻松实现。

单机伪代码如下。

class CounterDemo {
 public long timeStamp = getNowTime();
 public int reqCount = 0;
 public final int limit = 100; // 时间窗口内最大请求数
 public final long interval = 1000; // 时间窗口ms
 public boolean grant() {
 long now = getNowTime();
 if (now < timeStamp + interval) {
 // 在时间窗口内
 reqCount++;
 // 判断当前时间窗口内是否超过最大请求控制数
 return reqCount <= limit;
 } else {
 timeStamp = now;
 // 超时后重置
 reqCount = 1;
 return true;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法特点

实现简单。
时间窗口固定，每个窗口开始时计数为零，这样后面的请求不会受到之前的影响，做到了前后请求隔离。
因为两个时间窗口之间没有任何联系，所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求。所以固定时间窗口算法无法限制窗口间突发流量。
2. 滑动时间窗口算法

滑动时间窗口算法其实是固定时间窗口算法的优化，主要是为了解决固定时间窗口算法无法限制窗口间突发流量的缺点。

上面的计数器的单位时间是1分钟，而在使用滑动时间窗口，可以把1分钟分成6格，每格时间长度是10s，每一格又各自管理一个计数器，单位时间用一个长度为60s的窗口描述。一个请求进入系统，对应的时间格子的计数器便会+1，而每过10s，这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限，便会执行限流措施。

滑动窗口算法

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

算法特点

因为窗口顺延，所以可以抵御窗口间突发流量(对比固定时间窗口算法)。
假如限流10万次/小时，如果某个调用者在前10分钟调用了10万次那么他必须再等待1小时才能发起下一次正常请求。所以没有做到前后请求隔离。
阿里开源的Sentinel，采用的是滑动窗口算法进行限流，可以阅读相关代码，加深对滑动时间窗口算法的理解。

3. 漏桶算法(leaky bucket)

漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。这个从桶底流出去的水就是系统正常处理的请求，从旁边流出去的水就是系统拒绝掉的请求。

漏桶算法

单机伪代码如下。

class LeakyDemo {
 public long timeStamp = getNowTime();
 public int capacity; // 桶的容量
 public int rate; // 水漏出的速度
 public int water; // 当前水量(当前累积请求数)
 public boolean grant() {
 long now = getNowTime();
 water = max(0, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
 timeStamp = now;
 if ((water + 1) < capacity) {
 // 尝试加水,并且水还未满
 water += 1;
 return true;
 } else {
 // 水满，拒绝加水
 return false;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法特点

因为流出的速度是一定的，可以抵御突发流量，做到更加平滑的限流，而且不允许流量突发。
4. 令牌桶算法(Token Bucket)

令牌桶算法是比较常见的限流算法之一，Google开源项目Guava中的RateLimiter使用的就是令牌桶算法。流程如下：

所有的请求在处理之前都需要拿到一个可用的令牌才会被处理。
根据限流大小，设置按照一定的速率往桶里添加令牌。
桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝。
请求到达后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除。

令牌桶算法

单机伪代码如下，分布式环境可以使用Redisson。

class TokenBucketDemo {
 public long timeStamp = getNowTime();
 public int capacity; // 桶的容量
 public int rate; // 令牌放入速度
 public int tokens; // 当前令牌数量
 public boolean grant() {
 long now = getNowTime();
 // 先添加令牌
 tokens = min(capacity, tokens + (now - timeStamp) * rate);
 timeStamp = now;
 if (tokens < 1) {
 // 若桶中没有令牌,则拒绝
 return false;
 } else {
 // 还有令牌，领取令牌
 tokens -= 1;
 return true;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法特点

可以抵御突发流量，因为桶内的令牌数不会超过给定的最大值
可以做到更加平滑的限流，因为令牌是匀速放入的。
令牌桶算法允许流量一定程度的突发。（相比漏桶算法）
在时间点刷新的临界点上，只要剩余token足够，令牌桶算法会允许对应数量的请求通过，而后刷新时间因为token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量。因此，令牌桶算法也被广泛使用。

参考资料：

1. https://www.toutiao.com/i6791468953957827086/?tt_from=mobile_qq&utm_campaign=client_share&timestamp=1615301042&app=news_article&utm_source=mobile_qq&utm_medium=toutiao_android&use_new_style=1&req_id=20210309224402010151188142240FC51A&share_token=7913ca89-04f1-4dd2-a2fd-85a58e2de4ab&group_id=6791468953957827086
2. https://www.toutiao.com/i6718713888445039116/?group_id=6718713888445039116