0x00 微服务中的限流
本篇博客来介绍下微服务中的服务限流（Ratelimit），它是保证服务稳定的基础组件之一。其他类似的概念还有服务熔断。微服务中的限流主要指业务代码的逻辑限流。 通常，限流策略相较于熔断，使用的更为广泛一些，因为限流的同时可以对其他（被限制）服务请求进行排队处理，而不是像熔断策略直接拒绝掉这些被限制的请求。当然了，简单的处理方式就是被限制的流量，可以根据具体的业务逻辑去处理，直接返回错误或者返回默认值等等。
0x01 应用场景
服务器的资源是有限的，同一时间能处理的请求也有限，当请求数量超过服务器能处理的瓶颈时，就会导致所有请求都无法在规定时间内完成。因此需要一种频率限制的算法，来保障单台服务器正在处理的请求数量不超过瓶颈，保证瓶颈以内的请求能顺利处理。
- 秒杀
- 恶意刷单
- 服务路径上关键服务挂掉导致的雪崩问题（限流并不一定能保证服务恢复）
比如，一个服务 A 的接口可能被 BCDE 多个服务进行调用，在 B 服务发生突发流量时，直接把 A 服务给调用挂了，导致 A 服务对 CDE 也无法提供服务。解决方案有两种：
- 每个 Caller 采用线程池进行资源隔离
- 使用限流手段对每个 Caller 进行限流
单机限流 VS 分布式限流
通常微服务中的限流分为两个场景：
- 单机（服务）限流，大部分的算法实现都基于此
- 分布式限流，通常用于多机并发，需要借助于满足AP或者CP的第三方系统来实现限流机制（通常采用Redis+Lua的原子特性）
0x02 算法实现
本小节，介绍常用的限流算法。无论是何种算法，都可以抽象成下面这张图，当请求发生时，请求方必须拿到请求的令牌，才可以访问到相应的应用。基于令牌的算法实现方式，常见的有这几种限流算法：
1、计数器算法（Counter）
此算法一般会限制一秒钟的能够通过的请求数（counter），比如限流 qps 为 100，那么从第一个请求进来开始计时，在接下去的 1s 内，每来一个请求，就把计数加 1，如果累加的数字达到了 100，那么后续的请求就会被全部拒绝。等到 1s 结束后，把计数恢复成 0，重新开始计数。这个计数器必须是原子的，在 golang 中可以使用 atomic 包来实现。
在笔者之前开发 DDoS 防护的限速策略时，也是采用的计数器配合hashtable 的方式进行限速，但是这种限速是无差别限速，效果非常不好。此外，该算法还存在 “毛刺现象”：如果我在单位时间 1s 内的前 10ms，已经通过了 100 个请求，那后面的 990ms，只能拒绝这些请求。
2、漏桶算法（Leaky bucket）
为了消除 “毛刺现象”，可以采用漏桶算法实现限流。算法内部有一个容器（或队列），类似漏斗，当请求进来时，相当于水倒入漏斗，然后从下端小口慢慢匀速的流出。不管上面流量多大，下面流出的速度始终保持不变。不管服务调用方多么不稳定，通过漏桶算法进行限流，每 10ms 处理一次请求。因为处理的速度是固定的，请求进来的速度是未知的，可能突然进来很多请求，没来得及处理的请求就先放在桶里，既然是个桶，肯定是有容量上限，如果桶满了，那么新进来的请求就丢弃。
- 漏桶算法的缺点：无法应对短时间的突发流量
- 漏桶算法的典型实现：Uber-Go rate limiter
3、令牌桶算法（Token bucket）
令牌桶算法是对漏桶算法的一种改进，漏桶算法能够限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。如下图，可以通过控制令牌的生产速度来完成对突发 case 的优化。
算法中，令牌桶用来存放固定数量的令牌。算法中存在一种机制，以一定的速率往桶中放令牌。每次请求调用需要先获取令牌，只有拿到令牌，才有机会继续执行，否则选择选择等待可用的令牌、或者直接拒绝。
放令牌这个动作是持续不断的进行，如果桶中令牌数达到上限，就丢弃令牌。所以存在这种情况，令牌桶中一直有大量的可用令牌，这时进来的请求就可以直接拿到令牌执行，比如设置 qps 为 100，那么限流器初始化完成 1s 后，桶中就已经有 100 个令牌了，这时服务还没完全启动好，等启动完成对外提供服务时，该限流器可以抵挡瞬时的 100 个请求。所以，只有桶中没有令牌时，请求才会进行等待，最后相当于以一定的速率执行。
令牌桶算法的典型实现：
0x03 惰性求值的意义
限流的核心是获取令牌，比如在golang中，可以用buffered channel加定时器方式实现：
- 每过一段时间向tokenBucket中添加token，如果bucket已经满了，那么直接放弃
- 直接从
buffered channel取出即可
//获取令牌
func TakeAvailable(block bool) bool{
var takenResult bool
if block {
select {
case <-tokenBucket:
takenResult = true
}
} else {
select {
case <-tokenBucket:
takenResult = true
default:
takenResult = false
}
}
return takenResult
}
//生产令牌
func TokenProducer() {
var fillInterval = time.Millisecond * 10
var capacity = 100
var tokenBucket = make(chan struct{}, capacity) //令牌存放
fillToken := func() {
ticker := time.NewTicker(fillInterval)
for {
select {
case <-ticker.C:
select {
case tokenBucket <- struct{}{}:
default:
}
fmt.Println("current token cnt:", len(tokenBucket), time.Now())
}
}
}
go fillToken()
time.Sleep(time.Hour)
}
但是其实有更为优雅的做法，就是使用惰性计算代替上述逻辑，先确定几个值：
- 放令牌的时间间隔为 $\Delta_{t}$ ，即令牌的生产周期，假设为
1s - 每次向令牌桶放入 $x$ 个令牌，假设为
100，且令牌平均铺满整个1s - 令牌桶的容量是 $cap$
那么，可知1个令牌的生产时间为 $\frac{\Delta_{t}}{x}$ ，即10ms，每隔10ms放入1个令牌；反之，放N个令牌需要的时间就是 10ms*N
func main(){
fmt.Println(time.Second/100) //1个令牌生产单位时间为10ms，即每隔10ms生产1个令牌
fmt.Println(10*time.Millisecond*100) //放100个令牌，需要1s
}
考虑下令牌桶的应用场景，令牌桶每隔一段固定的时间向桶中放令牌，我们记下上一次放令牌的时间为 t1，和当时的令牌数k1，那么现在在t2时刻调用TakeAvailable来取n个令牌。在t2时刻，令牌桶中理论上应该有多少令牌呢？即令牌单位生产时间乘以时间差，与k1求和后再与 $cap$ 取最小值，如下面的公式：
最终结果：cur = current > cap ? cap : current。这样仅需要使用两个时间点的时间差，再结合其它的参数，理论上在取令牌之前就完全可以知道桶里有多少令牌了。在得到正确的令牌数之后，再进行实际的TakeAvailable操作就好，这个Take操作只需要对令牌数进行简单的减法即可，记得加锁以保证并发安全。
后续，在分布式限流的实现中会大量看到使用惰性求值来实现限流算法的开源实现。
0x04 限流的配置
限流逻辑可以在客户端做，也可以在服务端来做（服务端实现更为常见）。服务端的限流也叫做流量整形（Traffic Shaping）。
限流值配置
在实际项目中，一般采用压测的方式，得到服务端接口的 qps，然后将此值作为配置限流的参考值。但是此值不灵活，有无更优雅的限流算法呢？
0x04 自适应限流（adaptive limiting）
首次接触这个概念是在 Kratos 项目中（Kratos 中的 gRPC 服务端框架中默认就开启了BBR 限流算法的拦截器）。Kratos 文档中对该算法的描述如下：
kratos 借鉴了 Sentinel 项目的自适应限流系统，通过综合分析服务的 cpu 使用率、请求成功的 qps 和请求成功的 rt 来做自适应限流保护
Sentinel 系统自适应限流从整体维度对应用入口流量进行控制，结合应用的 Load、CPU 使用率、总体平均 RT、入口 QPS 和并发线程数等几个维度的监控指标，通过自适应的流控策略，让系统的入口流量和系统的负载达到一个平衡，让系统尽可能跑在最大吞吐量的同时保证系统整体的稳定性。
本小节来源于Sentinel - 系统自适应保护
自适应限流的背景
在开始之前，先了解一下系统保护的目的：
- 保证系统不被拖垮
- 在系统稳定的前提下，保持系统的吞吐量
长期以来，系统保护的思路是根据硬指标，即系统的负载来做系统过载保护。当系统负载高于某个阈值，就禁止或者减少流量的进入；当 load 开始好转，则恢复流量的进入。这个思路带来了不可避免的两个问题：
- load 是一个结果，如果根据 load 的情况来调节流量的通过率，那么就始终有延迟性。也就意味着通过率的任何调整，都会过一段时间才能看到效果。当前通过率是使 load 恶化的一个动作，那么也至少要过
1秒之后才能观测到；同理，如果当前通过率调整是让 load 好转的一个动作，也需要1秒之后才能继续调整，这样就浪费了系统的处理能力。所以我们看到的曲线，总是会有抖动。 - 恢复慢。想象如此场景（真实），出现了这样一个问题，下游应用不可靠，导致应用 RT 很高，从而 load 到了一个很高的点。过了一段时间之后下游应用恢复了，应用 RT 也相应减少。这个时候，其实应该大幅度增大流量的通过率；但是由于这个时候 load 仍然很高，通过率的恢复仍然不高。
而 TCP BBR算法 的思想给了我们一个很大的启发。我们应该根据系统能够处理的请求，和允许进来的请求，来做平衡，而不是根据一个间接的指标（系统 load）来做限流。最终我们追求的目标是在系统不被拖垮的情况下，提高系统的吞吐率，而不是 load 一定要到低于某个阈值。如果我们还是按照固有的思维，超过特定的 load 就禁止流量进入，系统 load 恢复就放开流量，这样做的结果是无论我们怎么调参数/比例，都是按照果来调节因，都无法取得良好的效果。
Sentinel 在系统自适应保护的做法是，用 load1 作为启动自适应保护的因子，而允许通过的流量由处理请求的能力，即请求的响应时间以及当前系统正在处理的请求速率来决定。
系统规则
系统保护规则是从应用级别的入口流量进行控制，从单台机器的 load、CPU 使用率、平均 RT、入口 QPS 和并发线程数等几个维度监控应用指标，让系统尽可能跑在最大吞吐量的同时保证系统整体的稳定性。
系统保护规则是应用整体维度的，而不是资源维度的，并且仅对入口流量生效。入口流量指的是进入应用的流量，比如 Web 服务或 gRPC 服务端接收的请求，都属于入口流量。
系统规则支持以下的模式：
- Load 自适应（仅对 Linux/Unix-like 机器生效）：系统的负载 load1 作为启发指标，进行自适应系统保护。当系统 load1 超过设定的启发值，且系统当前的并发线程数超过估算的系统容量时才会触发系统保护（BBR 阶段）。系统容量由系统的
maxQps * minRt估算得出。设定参考值一般是CPU cores * 2.5 - CPU usage：当系统 CPU 使用率超过阈值即触发系统保护（取值范围
0.0-1.0），比较灵敏 - 平均 RT：当单台机器上所有入口流量的平均 RT 达到阈值即触发系统保护，单位是毫秒
- 并发线程数：当单台机器上所有入口流量的并发线程数达到阈值即触发系统保护
- 入口 QPS：当单台机器上所有入口流量的 QPS 达到阈值即触发系统保护
原理
我们把系统处理请求的过程想象为一个水管，到来的请求是往这个水管灌水，当系统处理顺畅的时候，请求不需要排队，直接从水管中穿过，这个请求的RT是最短的；反之，当请求堆积的时候，那么处理请求的时间则会变为：排队时间 + 最短处理时间
1、推论一: 如果我们能够保证水管里的水量，能够让水顺畅的流动，则不会增加排队的请求；也就是说，这个时候的系统负载不会进一步恶化
用 T 来表示(水管内部的水量)，用RT来表示请求的处理时间，用P来表示进来的请求数，那么一个请求从进入水管道到从水管出来，这个水管会存在 P * RT 个请求。换一句话来说，当 T ≈ QPS * Avg(RT) 的时候，我们可以认为系统的处理能力和允许进入的请求个数达到了平衡，系统的负载不会进一步恶化。
接下来的问题是，水管的水位是可以达到了一个平衡点，但是这个平衡点只能保证水管的水位不再继续增高，但是还面临一个问题，就是在达到平衡点之前，这个水管里已经堆积了多少水。如果之前水管的水已经在一个量级了，那么这个时候系统允许通过的水量可能只能缓慢通过，RT会大，之前堆积在水管里的水会滞留；反之，如果之前的水管水位偏低，那么又会浪费了系统的处理能力。
2、推论二: 当保持入口的流量是水管出来的流量的最大的值的时候，可以最大利用水管的处理能力
然而，和 TCP BBR 的不一样的地方在于，还需要用一个系统负载的值（load1）来激发这套机制启动
注意：这种系统自适应算法对于低 load 的请求，它的效果是一个兜底的角色。对于不是应用本身造成的 load 高的情况（如其它进程导致的不稳定的情况），效果不明显。
0x05 限流算法对比
0x06 总结
本文介绍了微服务中重要的限流概念，限流机制在微服务架构中用来保护核心服务不被瞬时高并发请求拖垮，起到了关键性的作用。
