限流算法

Web, 后端技术, 算法

引言

最近在对接飞书开放平台的API接口时，飞书出于稳定性考虑，API接口都加入了限流控制，一般为 100次/分钟，5次/秒。其实不只是作为服务端的飞书需要进行限流控制，作为调用方，最好也要按照这个限制的速度进行接口调用，以免产生不必要的报错或降级处理，影响用户体验。在Golang中原生库 golang.org/x/time/rate 已经提供了基于令牌桶的限流算法实现，直接拿来使用即可。但出于对限流算法原理的好奇，还是研究比较了下两个出名的限流算法——漏桶算法 VS 令牌桶算法。

漏桶算法

漏桶算法（Leaky Bucket Algorithm）是常见的限流算法之一，该算法形象地将流控模型抽象为几样事物：将缓存队列抽象为一个固定大小的会“漏水”的桶，将流量抽象为“水滴”，将流量的发送方抽象为“出水口”，将流量的到达速率抽象为“滴入速率”，将流量的恒定放行速率抽象为“滴出速率”。围绕上述事物，流控的具体过程可以抽象为：出水口的水滴以较快的速率滴入漏桶，漏桶则以恒定速率滴出漏桶，一旦桶中水的体积超过了桶容量，就会将溢出部分的水进行一定的处理。在任何情况下，限制网络的吞吐率不高于一个固定值。漏桶算法的设计思想如下图所示。

从计算机视角对漏桶算法的描述为：到达的流量（数据包或请求）首先进入缓存队列，再由缓存队列以恒定的出队速率放行流量，累积缓存的流量大小不超过队列容量，一旦队满，则对超出部分的流量进行降级处理。假设漏桶总容量为 B，当前容量为 b，流量的平均到达速率为 R，恒定放行速率为 T，则当 1个单位的流量到达时的算法执行流程为：

  • Step1  若 b + 1 > B，转 Step3; 若 b + 1 ≤ B，流量入队，等至放行后转 Step2;
  • Step2  流量出队并放行，缓存队列容量减 1，转 Step4;
  • Step3  按业务场景选择降级策略:丢弃流量、缓存至等待队列待令牌桶积累足够时处理、对流量做特殊标记当网络过载时丢弃。转 Step4;
  • Step4  处理后续到达的流量，转 Step1。

        从漏桶算法的流程可以总结出：理想情况下，当 R ≤ T 时，漏桶的当前容量保持为 b = 0 ，即不产生流量堆积，全过程的放行速率固定为 T；当 R > T 时，在相当长的时间段内，漏桶的当前容量由 0 ≤ b ≤ B 变化至 b > B ，即从未满变化至溢出，全过程的放行速率固定为 T 。因此无论网络流量的到达速率如何，漏桶算法都一味地将放行速率平滑化为 T ，显然在应对低频率、高并发的突发流量时容易造成流量堆积，无法充分且高效地利用网络资源，究其原因是漏桶算法缺少一定的动态控制策略。

        令牌桶算法

        令牌桶算法（Token Bucket Algorithm）是另一经典的限流算法，该算法除能限制流量恒定的放行速率外，还可支持短暂的突发流量，能一定程度上适应不同到达速率的场景。令牌桶算法的基本思想与漏桶算法类似，不同之处在于引入了一个以恒定速率生成令牌的桶，另外将漏桶改造为了一个不以恒定速率放行流量的普通队列，通过令牌桶中是否存在令牌来指示何时可以放行流量。令牌桶的设计思想如下图所示。

        假设令牌以固定速率 P 产生并缓存至令牌桶中，即每隔 1 / P 秒产生一个令牌存入桶中，流量平均到达速率为 R，平均放行速率为 T，令牌桶容量为 B，即桶中 最多存放 B 个令牌，令牌桶当前存有 b 个令牌，缓存队列容量为 M 个单位，当前缓存有 m 个单位的流量。下面分别从令牌产生和流量到达两个角度解析算法执行流程:

        • 当令牌产生时
          • Step1  若 b + 1 ≤ B，令牌入桶，转 Step2；若 b + 1 > B，丢弃令牌，转 Step2；
          • Step2  等待下一时间间隔到来，产生令牌，转 Step1。
        • 当1个单位的流量到达时
          • Step1  若 m + 1 > M，转 Step3；若 m + 1 ≤ M，流量入队，等到令牌后转 Step2；
          • Step2  删除桶中 1 个令牌，流量出队并放行，缓存队列容量减 1，转 Step4；
          • Step3  按业务场景选择降级策略：丢弃流量、缓存至等待队列待令牌桶积累足够时处理、对流量做特殊标记当网络过载时丢弃。转 Step4；
          • Step4  处理后续到达的流量，转 Step1。

              从令牌桶的算法流程容易分析得到：当令牌桶中令牌数足够多时， T 由 R 决定，进而让突发流量得到放行，充分利用网络传输带宽；当令牌数无法支撑流量消耗时，T 由 P 决定，又达到了限制流量的目的。

              使用示例

              鉴于令牌桶算法优势更明显，这里介绍一下使用Golang的golang.org/x/time/rate库进行限流控制的具体代码。首先需要创建一个limiter对象并设置令牌放入速率：

              import golang.org/x/time/rate
limiter := rate.NewLimiter(10, 1) // 第一个参数10表示每秒产生10个令牌，第二个参数1表示令牌桶的容量

              然后就是基于自己的业务场景消费令牌：

              // Wait方法会阻塞直到获取到令牌
if err := limiter.Wait(ctx); err ! = nil { 
   // context取消或超过期限 
}
// 消费一个令牌，执行你的业务逻辑

              当然这个库还有很多其他使用方式，网上资料很多，这里就不详细介绍了。