服务高可用之限流

在不同场景下限流的定义也各不相同，可以是每秒请求数、每秒事务处理数、网络流量。通常我们所说的限流指的是限制到达系统并发请求数，使得系统能够正常的处理部分用户的请求，来保证系统的稳定性。

限流的英文是Rate limit（速率限制），维基百科中的定义比较简单。我们编写的程序可以被外部调用，Web 应用通过浏览器或者其他方式的 HTTP 方式访问，接口的访问频率可能会非常快，如果我们没有对接口访问频次做限制可能会导致服务器无法承受过高的压力挂掉，这时候也可能会产生数据丢失。而限流算法就可以帮助我们去控制每个接口或程序的函数被调用频率，它有点儿像保险丝，防止系统因为超过访问频率或并发量而引起瘫痪。

我们可能在调用某些第三方的接口的时候会看到类似这样的响应头：

X-RateLimit-Limit: 60 //每秒60次请求
X-RateLimit-Remaining: 23 //当前还剩下多少次
X-RateLimit-Reset: 1540650789 //限制重置时间

限流的行为指的就是在接口的请求数达到限流的条件时要触发的操作，一般可进行以下行为：

• 拒绝服务：把多出来的请求拒绝掉（定向到错误页或告知资源没有了）
• 服务降级：关闭或是把后端服务做降级处理。这样可以让服务有足够的资源来处理更多的请求（返回兜底数据或默认数据）
• 特权请求：资源不够了，我只能把有限的资源分给重要的用户
• 延时处理：一般会有一个队列来缓冲大量的请求，这个队列如果满了，那么就只能拒绝用户了，如果这个队列中的任务超时了，也要返回系统繁忙的错误了
• 弹性伸缩：用自动化运维的方式对相应的服务做自动化的伸缩

常见限流算法

限流的实现方案有很多种：

• 合法性验证限流：比如验证码、IP 黑名单等，这些手段可以有效的防止恶意攻击和爬虫采集
• 容器限流：比如 Tomcat、Nginx 等限流手段，其中 Tomcat 可以设置最大线程数（maxThreads），当并发超过最大线程数会排队等待执行； Nginx 提供了两种限流手段：一是控制速率，二是控制并发连接数
• 服务端限流：比如我们在服务器端通过限流算法实现限流

计数限流

最简单的限流算法就是计数限流了，例如系统能同时处理100个请求，保存一个计数器，处理了一个请求，计数器加1，一个请求处理完毕之后计数器减1。每次请求来的时候看看计数器的值，如果超过阈值要么拒绝。

应用场景：一些API接口的账号总调用次数

• 优点：简单粗暴
• 缺点：假设我们允许的阈值是1万，此时计数器的值为0， 当1万个请求在前1秒内一股脑儿的都涌进来，这突发的流量可是顶不住的。缓缓的增加处理和一下子涌入对于程序来说是不一样的。

固定窗口限流

它相比于计数限流主要是多了个时间窗口的概念。计数器每过一个时间窗口就重置。

规则如下：

• 请求次数小于阈值，允许访问并且计数器 +1
• 请求次数大于阈值，拒绝访问
• 这个时间窗口过了之后，计数器清零

看起来好像很完美，实际上还是有缺陷的。

假设有个用户在第 59 秒的最后几毫秒瞬间发送 200 个请求，当 59 秒结束后 Counter 清零了，他在下一秒的时候又发送 200 个请求。那么在 1 秒钟内这个用户发送了 2 倍的请求，如下图：

QPS 限流算法

QPS 限流算法通过限制单位时间内允许通过的请求数来限流。

优点：

• 计算简单，是否限流只跟请求数相关，放过的请求数是可预知的（令牌桶算法放过的请求数还依赖于流量是否均匀），比较符合用户直觉和预期。
• 可以通过拉长限流周期来应对突发流量。如 1 秒限流 10 个，想要放过瞬间 20 个请求，可以把限流配置改成 3 秒限流 30 个。拉长限流周期会有一定风险，用户可以自主决定承担多少风险。

缺点：

• 没有很好的处理单位时间的边界。比如在前一秒的最后一毫秒和下一秒的第一毫秒都触发了最大的请求数，就看到在两毫秒内发生了两倍的 QPS。
• 放过的请求不均匀。突发流量时，请求总在限流周期的前一部分放过。如 10 秒限 100 个，高流量时放过的请求总是在限流周期的第一秒。

为了解决这个问题引入了滑动窗口限流。

滑动窗口限流

滑动窗口是针对计数器存在的临界点缺陷，所谓 滑动窗口（Sliding window） 是一种流量控制技术，这个词出现在 TCP 协议中。滑动窗口把固定时间片进行划分，并且随着时间的流逝，进行移动，固定数量的可以移动的格子，进行计数并判断阀值。

上图中我们用红色的虚线代表一个时间窗口（一分钟），每个时间窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟时间窗口向右移动一格，可以看红色箭头的方向。我们为每个格子都设置一个独立的计数器 Counter，假如一个请求在 0:45 访问了那么我们将第五个格子的计数器 +1（也是就是 0:40~0:50），在判断限流的时候需要把所有格子的计数加起来和设定的频次进行比较即可。

滑动窗口如何解决我们上面遇到的问题呢？

当用户在0:59 秒钟发送了 200个请求就会被第六个格子的计数器记录 +200，当下一秒的时候时间窗口向右移动了一个，此时计数器已经记录了该用户发送的 200 个请求，所以再发送的话就会触发限流，则拒绝新的请求。

其实计数器就是滑动窗口啊，只不过只有一个格子而已，所以想让限流做的更精确只需要划分更多的格子就可以了，为了更精确我们也不知道到底该设置多少个格子，格子的数量影响着滑动窗口算法的精度，依然有时间片的概念，无法根本解决临界点问题。

漏桶算法

漏桶算法是水先进入到漏桶里，漏桶再以一定的速率出水，当流入水的数量大于流出水时，多余的水直接溢出。把水换成请求来看，漏桶相当于服务器队列，但请求量大于限流阈值时，多出来的请求就会被拒绝服务。漏桶算法使用队列实现，可以以固定的速率控制流量的访问速度，可以做到流量的“平整化”处理。

漏桶算法实现步骤：

• 将每个请求放入固定大小的队列进行存储
• 队列以固定速率向外流出请求，如果队列为空则停止流出
• 如队列满了则多余的请求会被直接拒绝

漏桶是一个比较好的限流整型工具， 但是漏桶算法也有一定的缺陷，因为水从桶的底部以固定的速率匀速流出，当有在服务器可承受范围内的瞬时突发请求进来，这些请求会被先放入桶内，然后再匀速的进行处理，这样就会造成部分请求的延迟。所以他无法应对在限流阈值范围内的突发请求。不过如果较起真来，我觉得这个缺点是不成立的。毕竟漏桶本就是用来平滑流量的，如果支持突发，那么输出流量反而不平滑了。如果要找一种能够支持突发流量的限流算法，那么令牌桶算法可以满足需求。

令牌桶算法

令牌桶和漏桶颇有几分相似，只不过令牌通里存放的是令牌。它的运行过程是这样的，一个令牌工厂按照设定值定期向令牌桶发放令牌。当令牌桶满了后，多出的令牌会被丢弃掉。每当一个请求到来时，该请求对应的线程会从令牌桶中取令牌。初期由于令牌桶中存放了很多个令牌，因此允许多个请求同时取令牌。当桶中没有令牌后，无法获取到令牌的请求可以丢弃，或者重试。下面我们来看一下的令牌桶示意图：

令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然后请求只有拿到了令牌才能通过，之后再被服务器处理。当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃。

• 定速的往桶内放入令牌
• 令牌数量超过桶的限制，丢弃
• 请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝

令牌桶算法和漏桶算法的方向刚好是相反的，我们有一个固定的桶，桶里存放着令牌（token）。一开始桶是空的，系统按固定的时间（rate）往桶里添加令牌，直到桶里的令牌数满，多余的请求会被丢弃。当请求来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。

• 令牌桶算法，放在服务端，用来保护服务端（自己），主要用来对调用者频率进行限流，为的是不让自己被压垮。所以如果自己本身有处理能力的时候，如果流量突发（实际消费能力强于配置的流量限制=桶大小），那么实际处理速率可以超过配置的限制（桶大小）。
• 而漏桶算法，放在调用方，这是用来保护他人，也就是保护他所调用的系统。主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。

限流组件

一般而言我们不需要自己实现限流算法来达到限流的目的，不管是接入层限流还是细粒度的接口限流其实都有现成的轮子使用，其实现也是用了上述我们所说的限流算法。

• Google Guava提供的限流工具类 RateLimiter，是基于令牌桶实现的，并且扩展了算法，支持预热。
• 阿里开源的限流框架 Sentinel中的匀速排队限流策略，就采用了漏桶算法。
• Nginx 中的限流模块 limit_req_zone，采用了漏桶算法，
• OpenResty 中的 limit.req库。
• Netflix开源的 Hystrix
• Resilience4j

Sentinel、Hystrix、resilience4j对比：