本来就是真实的用户，并且开通了appid，但是出现频繁调用接口的情况；这种情况需要给相关appid限流处理，常用的限流算法有令牌桶和漏桶算法。 在开发中我们可能会遇到接口访问频次过高，这时候就需要做流量限制，你可能是用的`Nginx`这种 Web Server 来控制也可能是用了一些流行的类库实现。在分布式系统中更是如此，限流是高并发系统的一大杀器，在设计限流算法之前我们先来了解一下它们是什么。 ## 是什么 限流的英文是`Rate limit`（速率限制），维基百科中的定义比较简单。我们编写的程序可以被外部调用，Web 应用通过浏览器或者其他方式的 HTTP 方式访问，接口的访问频率可能会非常快，如果我们没有对接口访问频次做限制可能会导致服务器无法承受过高的压力挂掉，这时候也可能会产生数据丢失。 而限流算法就可以帮助我们去控制每个接口或程序的函数被调用频率，它有点儿像保险丝，防止系统因为超过访问频率或并发量而引起瘫痪。我们可能在调用某些第三方的接口的时候会看到类似这样的响应头： > X-RateLimit-Limit: 60 //每秒60次请求 X-RateLimit-Remaining: 23 //当前还剩下多少次 X-RateLimit-Reset: 1540650789 //限制重置时间 ## 常见限流算法 ### 计数器 计数器是最简单的限流算法，思路是维护一个单位时间内的计数器`Counter`，如判断单位时间已经过去，则将计数器归零。 **我们假设有个需求对于某个接口`/query`每分钟最多允许访问200次。** 1. 可以在程序中设置一个变量`count`，当过来一个请求我就将这个数`+1`，同时记录请求时间。 2. 当下一个请求来的时候判断`count`的计数值是否超过设定的频次，以及当前请求的时间和第一次请求时间是否在 1 分钟内。 * 如果在 1 分钟内并且超过设定的频次则证明请求过多，后面的请求就拒绝掉。 * 如果该请求与第一个请求的间隔时间大于 1 分钟，且`count`值还在限流范围内，就重置`count`。 ``` public 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; } } } ``` 这种方法虽然简单，但也有个大问题就是没有很好的处理单位时间的边界。 假设有个用户在第 59 秒的最后几毫秒瞬间发送 200 个请求，当 59 秒结束后 Counter 清零了，他在下一秒的时候又发送 200 个请求。那么在 1 秒钟内这个用户发送了 2 倍的请求，如下图：  这种方式的缺点在于它没有更细粒度的划分临界点，如果我们可以把这个时间窗口划分成 6 份，每一份代表 10 秒，当然你可以将它划分的更细。那么如何解决这里的临界问题呢？来看看下面的滑动窗口吧。 ### 滑动窗口（sentinel） 所谓[滑动窗口（Sliding window）](https://en.wikipedia.org/wiki/Sliding_window_protocol)是一种流量控制技术，这个词出现在 TCP 协议中。我们来看看在限流中它是怎样表现的：  上图中我们用红色的虚线代表一个时间窗口（一分钟），每个时间窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟时间窗口向右移动一格，可以看红色箭头的方向。我们为每个格子都设置一个独立的计数器 Counter，假如一个请求在`0:45`访问了那么我们将第五个格子的计数器 +1（也是就是`0:40~0:50`），在判断限流的时候需要把所有格子的计数加起来和设定的频次进行比较即可。 那么滑动窗口如何解决我们上面遇到的问题呢？来看下面的图：  当用户在`0:59`秒钟发送了 200 个请求就会被第六个格子的计数器记录 +200，当下一秒的时候时间窗口向右移动了一个，此时计数器已经记录了该用户发送的 200 个请求，所以再发送的话就会触发限流，则拒绝新的请求。 通过上面的分析相信你了解什么是滑动窗口了，回想一下其实计数器就是滑动窗口啊，只不过只有一个格子而已，所以我们想让限流做的更精确只需要划分更多的格子就可以了，真是秒啊！为了更精确我们也不知道到底该设置多少个格子，所以又出了 2 种流行的平滑限流算法分别是漏桶算法和令牌桶算法，继续往下看。 ### 漏桶算法  漏桶算法（Leaky Bucket）是什么呢？大家都用过水龙头，打开龙头开关水就会流下滴到水桶里，而漏桶指的是水桶下面有个漏洞可以出水。如果水龙头开的特别大那么水流速就会过大，这样就可能导致水桶的水满了然后溢出。 而我们讨论的漏桶算法的思路也很简单，水龙头打开后流下的水（请求）以一定的速率流到漏桶里（限流容器），漏桶以一定的速度出水（接口响应速率），如果水流速度过大（请求过多）就可能会导致漏桶的水溢出（访问频率超过接口响应速率），这时候我们需要关掉水龙头（拒绝请求），下面是经典的漏桶算法图示：  这张图中有 2 个变量，一个是桶的大小（capacity），另一个是水桶漏洞的大小（rate），那么我们可以写下如下代码来实现： ``` public 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; } } ``` 漏桶算法有以下特点： * 漏桶具有固定容量，出水速率是固定常量（流出请求） * 如果桶是空的，则不需流出水滴 * 可以以任意速率流入水滴到漏桶（流入请求） * 如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝） * 流入：以任意速率往桶中放入水滴。 * 流出：以固定速率从桶中流出水滴。 用白话具体说明：假设漏斗总支持并发100个最大请求，如果超过100个请求，那么会提示系统繁忙，请稍后再试，数据输出那可以设置1个线程池，处理线程数5个，每秒处理20个请求。 缺点：因为当流出速度固定，大规模持续突发量，无法多余处理，浪费网络带宽 优点：无法击垮服务 ### 令牌桶算法（guava RateLimiter） 令牌桶算法（Token Bucket）是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。  令牌桶算法和漏桶算法的方向刚好是相反的，我们有一个固定的桶，桶里存放着令牌（token）。一开始桶是空的，系统按固定的时间（rate）往桶里添加令牌，直到桶里的令牌数满，多余的请求会被丢弃。当请求来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。 ``` public 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) { // 若不到1个令牌,则拒绝 return false; } else { // 还有令牌，领取令牌 tokens -= 1; return true; } } } ``` 若仔细研究算法，我们会发现我们默认从桶里移除令牌是不需要耗费时间的。如果给移除令牌设置一个延时时间，那么实际上又采用了漏桶算法的思路。Google的Guava库下的SmoothWarmingUp类就采用了这个思路。 我们再来考虑一下临界问题的场景。在0:59秒的时候，由于桶内积满了100个token，所以这100个请求可以瞬间通过。但是由于token是以较低的速率填充的，所以在1:00的时候，桶内的token数量不可能达到100个，那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问题。下图比较了计数器（左）和令牌桶算法（右）在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率，但是下一个突发速率必须要等桶内有足够的 token后才能发生  ## 总结 计数器 VS 滑动窗口： > 计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。 漏桶算法 VS 令牌桶算法： > 漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。 * 令牌桶算法，放在服务端，用来保护服务端（自己），主要用来对调用者频率进行限流，为的是不让自己被压垮。所以如果自己本身有处理能力的时候，如果流量突发（实际消费能力强于配置的流量限制=桶大小），那么实际处理速率可以超过配置的限制（桶大小）。 * 而漏桶算法，放在调用方，这是用来保护他人，也就是保护他所调用的系统。主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。 令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。 ### RateLimiter使用示例 Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法(Token Bucket)来完成限流，非常易于使用。RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率，它支持两种获取permits接口，一种是如果拿不到立刻返回false（`tryAcquire()`），一种会阻塞等待一段时间看能不能拿到（`tryAcquire(long timeout, TimeUnit unit)`）。 使用tryAcquire方法获取令牌的示例代码： ``` @Slf4j public class RateLimiterExample1 { /** * 每秒钟放入5个令牌，相当于每秒只允许执行5个请求 */ private static final RateLimiter RATE_LIMITER = RateLimiter.create(5); public static void main(String[] args) { // 模拟有100个请求 for (int i = 0; i < 100; i++) { // 尝试从令牌桶中获取令牌，若获取不到则等待300毫秒看能不能获取到 if (RATE_LIMITER.tryAcquire(300, TimeUnit.MILLISECONDS)) { // 获取成功，执行相应逻辑 handle(i); } } } private static void handle(int i) { log.info("{}", i); } } ``` 若想保证所有的请求都被执行，而不会被抛弃的话，可以选择使用acquire方法： ``` @Slf4j public class RateLimiterExample2 { /** * 每秒钟放入5个令牌，相当于每秒只允许执行5个请求 */ private static final RateLimiter RATE_LIMITER = RateLimiter.create(5); public static void main(String[] args) { for (int i = 0; i < 100; i++) { // 从令牌桶中获取一个令牌，若没有获取到会阻塞直到获取到为止，所以所有的请求都会被执行 RATE_LIMITER.acquire(); // 获取成功，执行相应逻辑 handle(i); } } private static void handle(int i) { log.info("{}", i); } ``` ### 集群限流 前面讨论的几种算法都属于单机限流的范畴，但是业务需求五花八门，简单的单机限流，根本无法满足他们。 比如为了限制某个资源被每个用户或者商户的访问次数，5s只能访问2次，或者一天只能调用1000次，这种需求，单机限流是无法实现的，这时就需要通过集群限流进行实现。 如何实现？为了控制访问次数，肯定需要一个计数器，而且这个计数器只能保存在第三方服务，比如redis。 大概思路：每次有相关操作的时候，就向redis服务器发送一个incr命令，比如需要限制某个用户访问/index接口的次数，只需要拼接用户id和接口名生成redis的key，每次该用户访问此接口时，只需要对这个key执行incr命令，在这个key带上过期时间，就可以实现指定时间的访问频率。 ## 参考资料 > https://blog.51cto.com/zero01/2307787 > https://blog.biezhi.me/2018/10/rate-limit-algorithm.html