高可用之限流-01-入门介绍

限流系列

开源组件 rate-limit: 限流

高可用之限流-01-入门介绍

高可用之限流-02-如何设计限流框架

高可用之限流-03-Semaphore 信号量做限流

高可用之限流-04-fixed window 固定窗口

高可用之限流-05-slide window 滑动窗口

高可用之限流-06-slide window 滑动窗口 sentinel 源码

高可用之限流-07-token bucket 令牌桶算法

高可用之限流 08-leaky bucket漏桶算法

高可用之限流 09-guava RateLimiter 入门使用简介 & 源码分析

背景

在如今的互联网已经作为社会基础设施的大环境下，上面的这个场景其实离我们并不是那么远，同时也会显得没那么极端。

例如，层出不穷的营销玩法，一个接着一个的社会热点，以及互联网冰山之下的黑产、刷子的蓬勃发展，更加使得这个场景变的那么的需要去考虑、去顾忌。

因为随时都有可能会涌入超出你预期的流量，然后压垮你的系统。

那么限流的作用就很显而易见了：只要系统没宕机，系统只是因为资源不够，而无法应对大量的请求，为了保证有限的系统资源能够提供最大化的服务能力，因而对系统按照预设的规则进行流量（输出或输入）限制的一种方法，确保被接收的流量不会超过系统所能承载的上限。

限流

服务治理本身的概念比较大，包括鉴权、限流、降级、熔断、监控告警等等。

场景需求

比如限制微服务集群单台机器每秒请求次数，我们还需要针对不同调用方甚至不同接口进行更加细粒度限流： 比如限制 A 调用方对某个服务的某个的接口的每秒最大请求次数。

流

限流中的“流”字该如何解读呢？要限制的指标到底是什么？

不同的场景对“流”的定义也是不同的，可以是网络流量，带宽，每秒处理的事务数 (TPS)，每秒请求数 (hits per second)，并发请求数， 甚至还可能是业务上的某个指标，比如用户在某段时间内允许的最多请求短信验证码次数。

从保证系统稳定可用的角度考量，对于微服务系统来说，最好的一个限流指标是：并发请求数。

通过限制并发处理的请求数目，可以限制任何时刻都不会有过多的请求在消耗资源 ，比如：我们通过配置 web 容器中 servlet worker 线程数目为 200，则任何时刻最多都只有 200 个请求在处理，超过的请求都会被阻塞排队。

对比 TPS 和 hits per second 的两个指标，我们选择使用 hits per second 作为限流指标。

因为，对 TPS 的限流实际上是无法做的，TPS 表示每秒处理事务数，事务的开始是接收到接口请求，事务的结束是处理完成返回，所以有一定的时间跨度，如果事务开始限流计数器加一，事务结束限流计数器减一，则就等同于并发限流。

而如果把事务请求接收作为计数时间点，则就退化为按照 hits per second 来做限流，而如果把事务结束作为计数时间点，则计数器的数值并不能代表系统当下以及接下来的系统访问压力。

对 hits per second 的限流是否是一个有效的限流指标呢？答案是肯定的，这个值是可观察可统计的，所以方便配置限流规则，而且这个值在一定程度上反应系统当前和接下来的性能压力，对于这一指标的限流确实也可以达到限制对系统资源的使用。

有了流的定义之后，我们接下来看几种常用的限流算法：固定时间窗口，滑动时间窗口，令牌桶算法，漏桶算法以及他们的改进版本。

常见算法

固定时间窗口

• 算法思想

首先需要选定一个时间起点，之后每次接口请求到来都累加计数器，如果在当前时间窗口内，根据限流规则（比如每秒钟最大允许 100 次接口请求）， 累加访问次数超过限流值，则限流熔断拒绝接口请求。

当进入下一个时间窗口之后，计数器清零重新计数。

• 缺点

限流策略过于粗略，无法应对两个时间窗口临界时间内的突发流量。

我们举一个例子：假设我们限流规则为每秒钟不超过 100 次接口请求，第一个 1s 时间窗口内，100 次接口请求都集中在最后的 10ms 内， 在第二个 1s 的时间窗口内，100 次接口请求都集中在最开始的 10ms 内，虽然两个时间窗口内流量都符合限流要求 (<=100 个请求)， 但在两个时间窗口临界的 20ms 内会集中有 200 次接口请求，如果不做限流，集中在这 20ms 内的 200 次请求就有可能压垮系统。

滑动时间窗口

滑动时间窗口算法是对固定时间窗口算法的一种改进，流量经过滑动时间窗口算法整形之后，可以保证任意时间窗口内，都不会超过最大允许的限流值，从流量曲线上来看会更加平滑，可以部分解决上面提到的临界突发流量问题。

对比固定时间窗口限流算法，滑动时间窗口限流算法的时间窗口是持续滑动的，并且除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，对内存的占用会比较多。

• 算法模型

滑动时间窗口的算法模型如下：

滑动窗口记录的时间点 list = (t_1, t_2, …t_k)，时间窗口大小为 1 秒，起点是 list 中最小的时间点。

当 t_m 时刻新的请求到来时，我们通过以下步骤来更新滑动时间窗口并判断是否限流熔断：

STEP 1: 检查接口请求的时间 t_m 是否在当前的时间窗口 [t_start, t_start+1 秒) 内。如果是，则跳转到 STEP 3，否则跳转到 STEP 2.

STEP 2: 向后滑动时间窗口，将时间窗口的起点 t_start 更新为 list 中的第二小时间点，并将最小的时间点从 list 中删除。然后，跳转到 STEP 1。

STEP 3: 判断当前时间窗口内的接口请求数是否小于最大允许的接口请求限流值，即判断: list.size < max_hits_limit，如果小于，则说明没有超过限流值，允许接口请求，并将此接口请求的访问时间放入到时间窗口内，否则直接执行限流熔断。

• 缺陷

即便滑动时间窗口限流算法可以保证任意时间窗口内接口请求次数都不会超过最大限流值，但是仍然不能防止在细时间粒度上面访问过于集中的问题。

比如上面举的例子，第一个 1s 的时间窗口内 100 次请求都集中在最后 10ms 中。

也就是说，基于时间窗口的限流算法，不管是固定时间窗口还是滑动时间窗口，只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。

• 改进版本

多层次限流，我们可以对同一个接口设置多条限流规则，除了 1 秒不超过 100 次之外，我们还可以设置 100ms 不超过 20 次 (这里需要设置的比 10 次大一些)， 两条规则同时限制，流量会更加平滑。

除此之外，还有针对滑动时间窗口限流算法空间复杂度大的改进算法，限于篇幅，这里就不展开详说了。

令牌桶算法

令牌桶和漏桶算法的算法思想大体类似，可以把漏桶算法作为令牌桶限流算法的改进版本，所以我们以介绍令牌桶算法为主。

• 核心算法

我们先来看下最基础未经过改进的令牌桶算法：

1. 接口限制 t 秒内最大访问次数为 n，则每隔 t/n 秒会放一个 token 到桶中；

2. 桶中最多可以存放 b 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 会被丢弃；

3. 接口请求会先从令牌桶中取 token，拿到 token 则处理接口请求，拿不到 token 则执行限流。

令牌桶算法看似比较复杂，每间隔固定时间都要放 token 到桶中，但并不需要专门起一个线程来做这件事情。

每次在取 token 之前，根据上次放入 token 的时间戳和现在的时间戳，计算出这段时间需要放多少 token 进去，一次性放进去，所以在实现上面也并没有太大难度。

漏桶算法

漏桶算法稍微不同与令牌桶算法的一点是：对于取令牌的频率也有限制。

要按照 t/n 固定的速度来取令牌，所以可以看出漏桶算法对流量的整形效果更加好，流量更加平滑，任何突发流量都会被限流。

因为令牌桶大小为 b，所以是可以应对突发流量的。

• 其他改进算法

当然，对于令牌桶算法，还有很多其他改进算法，比如：

1. 预热桶

2. 一次性放入多个令牌

3. 支持一次性取多个令牌

• 使用场景

令牌桶和漏桶算法比较适合阻塞式限流。

比如一些后台 job 类的限流，超过了最大访问频率之后，请求并不会被拒绝，而是会被阻塞到有令牌后再继续执行。

对于像微服务接口这种对响应时间比较敏感的限流场景，会比较适合选择基于时间窗口的否决式限流算法，其中滑动时间窗口限流算法空间复杂度较高，

内存占用会比较多，所以对比来看，尽管固定时间窗口算法处理临界突发流量的能力较差，但实现简单，而简单带来了好的性能和不容易出错，

所以固定时间窗口算法也不失是一个好的微服务接口限流算法。

guava 实现

http://ifeve.com/guava-ratelimiter/

可参考 guava 的实现。

一、怎么做「限流」

从前面聊到的内容中我们也知道，限流最好能“限”在一个系统处理能力的上限附近，所以：

1、通过「压力测试」等方式获得系统的能力上限在哪个水平是第一步。

2、其次，就是制定干预流量的策略。比如标准该怎么定、是否只注重结果还是也要注重过程的平滑性等。

3、最后，就是处理“被干预掉”的流量。能不能直接丢弃？不能的话该如何处理？

获得系统能力的上限

第一步不是我们这次内容的重点，说起来就是对系统做一轮压测。可以在一个独立的环境进行，也可以直接在生产环境的多个节点中选择一个节点作为样本来压测，当然需要做好与其他节点的隔离。

一般我们做压测为了获得2个结果，「速率」和「并发数」。

前者表示在一个时间单位内能够处理的请求数量，比如xxx次请求/秒。后者表示系统在同一时刻能处理的最大请求数量，比如xxx次的并发。从指标上需要获得「最大值」、「平均值」或者「中位数」。后续限流策略需要设定的具体标准数值就是从这些指标中来的。

题外话：从精益求精的角度来说，其他的诸如cpu、网络带宽以及内存的耗用也可以作为参照因素。

制定干预流量的策略

常用的策略就4种，我给它起了一个简单的定义——「两窗两桶」。

两窗就是：固定窗口、滑动窗口，两桶就是：漏桶、令牌桶。

固定窗口

固定窗口就是定义一个“固定”的统计周期，比如1分钟或者30秒、10秒这样。

然后在每个周期统计当前周期中被接收到的请求数量，经过计数器累加后如果达到设定的阈值就触发「流量干预」。

直到进入下一个周期后，计数器清零，流量接收恢复正常状态。

这个策略最简单，写起代码来也没几行。

全局变量 int totalCount = 0;  //有一个「固定周期」会触发的定时器将数值清零。

if(totalCount > 限流阈值) {

    return; //不继续处理请求。

}

totalCount++;

// do something...

固定窗口有一点需要注意的是，假如请求的进入非常集中，那么所设定的「限流阈值」等同于你需要承受的最大并发数。

所以，如果需要顾忌到并发问题，那么这里的「固定周期」设定的要尽可能的短。因为，这样的话「限流阈值」的数值就可以相应的减小。

甚至，限流阈值就可以直接用并发数来指定。比如，假设固定周期是3秒，那么这里的阈值就可以设定为「平均并发数*3」。

不过不管怎么设定，固定窗口永远存在的缺点是：由于流量的进入往往都不是一个恒定的值，所以一旦流量进入速度有所波动，要么计数器会被提前计满，导致这个周期内剩下时间段的请求被“限制”。

要么就是计数器计不满，也就是「限流阈值」设定的过大，导致资源无法充分利用。

「滑动窗口」可以改善这个问题。

滑动窗口

滑动窗口其实就是对固定窗口做了进一步的细分，将原先的粒度切的更细，比如1分钟的固定窗口切分为60个1秒的滑动窗口。

然后统计的时间范围随着时间的推移同步后移。

同时，我们还可以得出一个结论是：如果固定窗口的「固定周期」已经很小了，那么使用滑动窗口的意义也就没有了。

举个例子，

现在的固定窗口周期已经是1秒了，再切分到毫秒级别能反而得不偿失，会带来巨大的性能和资源损耗。

滑动窗口大致的代码逻辑是这样：

全局数组 链表[]  counterList = new 链表[切分的滑动窗口数量];
//有一个定时器，在每一次统计时间段起点需要变化的时候就将索引0位置的元素移除，并在末端追加一个新元素。
int sum = counterList.Sum();
if(sum > 限流阈值) {
    return; //不继续处理请求。
}

int 当前索引 = 当前时间的秒数 % 切分的滑动窗口数量;
counterList[当前索引]++;
// do something...

虽然说滑动窗口可以改善这个问题，但是本质上还是预先划定时间片的方式，属于一种“预测”，意味着几乎肯定无法做到100%的物尽其用。

但是，「桶」模式可以做的更好，因为「桶」模式中多了一个缓冲区（桶本身）。

漏桶

首先聊聊「漏桶」吧。

漏桶模式的核心是固定“出口”的速率，不管进来多少量，出去的速率一直是这么多。

如果涌入的量多到桶都装不下了，那么就进行「流量干预」。

整个实现过程我们来分解一下。

1. 控制流出的速率。这个其实可以使用前面提到的两个“窗口”的思路来实现。如果当前速率小于阈值则直接处理请求，否则不直接处理请求，进入缓冲区，并增加当前水位。

2. 缓冲的实现可以做一个短暂的休眠或者记录到一个容器中再做异步的重试。

3. 最后控制桶中的水位不超过最大水位。这个很简单，就是一个全局计数器，进行加加减减。

这样一来，你会发现本质就是：通过一个缓冲区将不平滑的流量“整形”成平滑的（高于均值的流量暂存下来补足到低于均值的时期），以此最大化计算处理资源的利用率。

实现代码的简化表示如下：

全局变量 int unitSpeed;  //出口当前的流出速率。每隔一个速率计算周期（比如1秒）会触发定时器将数值清零。

全局变量 int waterLevel; //当前缓冲区的水位线。

if(unitSpeed < 速率阈值) {

    unitSpeed++;
    //do something...
}else{
    if(waterLevel > 水位阈值){
        return; //不继续处理请求。
    }

    waterLevel++;
    while(unitSpeed >= 速率阈值){
        sleep(一小段时间)。
    }

    unitSpeed++;
    waterLevel--;
    //do something...
}

更优秀的「漏桶」策略已经可以在流量的总量充足的情况下发挥你所预期的100%处理能力，但这还不是极致。

你应该知道，一个程序所在的运行环境中，往往不单单只有这个程序本身，会存在一些系统进程甚至是其它的用户进程。

也就是说，程序本身的处理能力是会被干扰的，是会变化的。所以，你可以预估某一个阶段内的平均值、中位数，但无法预估具体某一个时刻的程序处理能力。

又因此，你必然会使用相对悲观的标准去作为阈值，防止程序超负荷。

那么从资源利用率来说，有没有更优秀的方案呢？有，这就是「令牌桶」。

令牌桶

令牌桶模式的核心是固定“进口”速率。

先拿到令牌，再处理请求，拿不到令牌就被「流量干预」。

因此，当大量的流量进入时，只要令牌的生成速度大于等于请求被处理的速度，那么此刻的程序处理能力就是极限。

也来分解一下它的实现过程。

1. 控制令牌生成的速率，并放入桶中。这个其实就是单独一个线程在不断的生成令牌。

2. 控制桶中待领取的令牌水位不超过最大水位。这个和「漏桶」一样，就是一个全局计数器，进行加加减减。

大致的代码简化表示如下（看上去像「固定窗口」的反向逻辑）：

全局变量 int tokenCount = 令牌数阈值; //可用令牌数。有一个独立的线程用固定的频率增加这个数值，但不大于「令牌数阈值」。

if(tokenCount == 0){
    return; //不继续处理请求。
}
tokenCount--;
//do something...

聪明的你可能也会想到，这样一来令牌桶的容量大小理论上就是程序需要支撑的最大并发数。

的确如此，假设同一时刻进入的流量将令牌取完，但是程序来不及处理，将会导致事故发生。

所以，没有真正完美的策略，只有合适的策略。因此，根据不同的场景能够识别什么是最合适的策略是更需要锻炼的能力。

最佳实践

四种策略该如何选择？

首先，固定窗口。一般来说，如非时间紧迫，不建议选择这个方案，太过生硬。但是，为了能快速止损眼前的问题可以作为临时应急的方案。

其次，滑动窗口。这个方案适用于对异常结果「高容忍」的场景，毕竟相比“两窗”少了一个缓冲区。但是，胜在实现简单。

然后，漏桶。个人觉得这个方案最适合作为一个通用方案。虽说资源的利用率上不是极致，但是「宽进严出」的思路在保护系统的同时还留有一些余地，使得它的适用场景更广。

最后，令牌桶。当你需要尽可能的压榨程序的性能（此时桶的最大容量必然会大于等于程序的最大并发能力），并且所处的场景流量进入波动不是很大（不至于一瞬间取完令牌，压垮后端系统）。

分布式系统中带来的新挑战

每一个上游系统都可以理解为是其下游系统的客户端。

然后我们回想一下前面的内容，可能你发现了，前面聊的「限流」都没有提到到底是在客户端做限流还是服务端做，甚至看起来更倾向是建立在服务端的基础上做。

但是你知道，在一个分布式系统中，一个服务端本身就可能存在多个副本，并且还会提供给多个客户端调用，甚至其自身也会作为客户端角色。

那么，在如此交错复杂的一个环境中，该如何下手做限流呢？

我的思路是通过「一纵一横」来考量。

纵

都知道「限流」是一个保护措施，那么可以将它想象成一个盾牌。另外，一个请求在系统中的处理过程是链式的。那么，正如古时候军队打仗一样，盾牌兵除了有小部分在老大周围保护，剩下的全在最前线。因为盾的位置越前，能受益的范围越大。

分布式系统中最前面的是什么？接入层。

如果你的系统有接入层，比如用nginx做的反向代理。

那么可以通过它的ngx_http_limit_conn_module以及ngx_http_limit_req_module来做限流，是很成熟的一个解决方案。

如果没有接入层，那么只能在应用层以AOP的思路去做了。

但是，由于应用是分散的，出于成本考虑你需要针对性的去做限流。比如ToC的应用必然比ToB的应用更需要做，高频的缓存系统必然比低频的报表系统更需要做，Web应用由于存在Filter的机制做起来必然比Service应用更方便。

那么应用间的限流到底是做到客户端还是服务端呢？

个人的观点是，从效果上客户端模式肯定是优于服务端模式的，因为当处于被限流状态的时候，客户端模式连建立连接的动作都省了。另一个潜在的好处是，与集中式的服务端模式相比，可以把少数的服务端程序的压力分散掉。但是在客户端做成本也更高，因为它是去中心化的，假如需要多个节点之间的数据共通的话，是一个很麻烦的事情。

所以，最终个人建议你：如果考虑成本就服务端模式，考虑效果就客户端模式。当然也不是绝对，比如一个服务端的流量大部分都来源于某一个客户端，那么就可以直接在这个客户端做限流，这也不失为一个好方案。

数据库层面的话，一般连接字符串中本身就会包含「最大连接数」的概念，就可以起到限流的作用。如果想做更精细的控制就只能做到统一封装的数据库访问层框架中了。

聊完了「纵」，那么「横」是什么呢？

横

不管是多个客户端，还是同一个服务端的多个副本。每个节点的性能必然会存在差异，如何设立合适的阈值？

以及如何让策略的变更尽可能快的在集群中的多个节点生效？

说起来很简单，引入一个性能监控平台和配置中心。

但这些真真要做好不容易，后续我们再展开这块内容。

拓展阅读

Bloom Filter

Cache 之旅系列

ActiveMQ

参考资料

限流

https://mp.weixin.qq.com/s/k9tm-4lBwm69nxnYp9octA

https://github.com/wangzheng0822/ratelimiter4j

• guava

http://ifeve.com/guava-ratelimiter/

• 限流系列
• 背景
• 限流
  • 场景需求
  • 流
• 常见算法
  • 固定时间窗口
  • 滑动时间窗口
  • 令牌桶算法
  • 漏桶算法
  • guava 实现
• 一、怎么做「限流」
  • 获得系统能力的上限
  • 制定干预流量的策略
    • 固定窗口
    • 滑动窗口
    • 漏桶
    • 令牌桶
• 最佳实践
• 分布式系统中带来的新挑战
  • 纵
  • 横
• 拓展阅读
• 参考资料