🍵 限流算法

是什么？

• 限制到达系统的并发请求数量，保证系统能够正常响应部分用户请求
• 对于超过限制的流量，则通过 拒绝服务 的方式，保证系统的整体可用性

1. 计数器

1) 原理

• 在 一段时间间隔 内，对请求进行计数，与阈值相比，判断是否需要限流
• 一旦达到时间临界点，计数器清零

2) 特点

• 实现简单，适用于不太精确的场景
• 将 时间间隔 分为一个格，达到时间后，从下一个时间范围内从 0 开始重新计算
• 边界没有很好的处理，限流无法精确控制

---

2. 滑动窗口

1) 原理

• 在 一段时间间隔 内，划分为多个窗口，每次滑动后，统计窗口内的总请求数，与阈值对比，判断是否需要限流

2) 特点

• 将 固定时间间隔 分段，时间比计数器算法复杂，适用于稍微精准的场景
• 实现稍微复杂，还是无法彻底解决计数器算法存在的边界问题

---

3. 漏桶算法

1) 原理

• 利用一个 固定容量 的桶，按照 固定速率 流出水滴
• 对于能够流入桶中的水，意味着该请求可以被处理，但不确定什么时候会被处理
• 对于桶已满的情况，此时无法流入桶中，意味着该请求被拒绝，被限流

2) 特点

• 漏桶容量固定，出水流量固定
• 若桶为空，则无需流出水滴
• 若桶满，则无法流入水滴，意味着新请求被拒绝
• 可以以任意速率流入水滴到桶中，意味着不限制流入请求的速率
• 可以控制 消费频率
• 实现稍微复杂，单位时间内，无法多消费

---

4. 令牌桶

1) 原理

• 利用一个 固定容量 的桶，桶中可以放入 令牌
• 初始时，桶为空，按照 固定速率 向桶中添加令牌，直到桶中的令牌已满
  • 定时添加令牌
    • 采用专门的线程，定时补充令牌，除非桶已满
  • 计算应该添加的令牌数
    • 当桶为空时，通过公式 (当前时间 - 上次添加时间) * 桶中令牌的生成速率 添加理应添加的令牌数
• 当请求来时，首先需要拿取桶中的令牌，成功拿到的请求可以继续执行
• 若桶为空，说明无法拿到令牌，该请求被拒绝

2) 特点

• 令牌按照 固定速率 添加到令牌桶中
• 桶中最多存放的令牌数固定，超过的令牌无法添加
• 可解决漏桶算法无法灵活消费的问题，又能避免过度消费
• 实现稍微复杂