漏桶算法

【算法介绍】
漏桶算法是一种强制进行常量限流而不管流量突发的情况的算法。
漏桶.svg

【工作原理】

  1. 请求进入漏桶，漏桶以固定的速率出水，即处理请求；
  2. 请求的速率低于处理请求的速率，则请求都正常处理；
  3. 请求的速率高于处理请求的速率，部分请求拒绝处理。

【技术本质】
总量控制，桶的大小是设计关键。

【优缺点】

  1. 桶的大小动态调整比较困难；
  2. 无法精确控制处理请求速度。

【应用场景】
瞬时高流量：0点签到、限时秒杀。
漏桶的保护是尽量缓存请求，缓存不下才选择丢弃。

令牌桶

【算法介绍】
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。
令牌桶.svg

【核心参数】

  1. 产生令牌的速率：CIR / EIR（Committed Information Rate / Excess Information Rate）
  2. 消耗令牌的速率：CBS / EBS（Committed Burst Size / Excess Burst Size）

【工作流程】

  1. 产生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达CBS/EBS，则丢弃多余令牌。
  2. 消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。
  3. 验证通过：输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃。

【技术本质】
速率控制，令牌产生的速度是关键。

【优缺点】

  1. 可以动态调整处理速度。

【应用场景】
对自身服务接口限流，防止过载；控制访问第三方服务的速度，防止压垮下游服务。
令牌桶的保护主要是丢弃请求。

参考

[1] https://xie.infoq.cn/article/4a0acdd12a0f6dd4a53e0472c
[2] https://cxybb.com/article/qq_39399966/99697362