限流算法-令牌桶算法

# 漏桶算法的不足

当突发流量来袭的时候，由于漏桶算法的流速是固定的，所以超过日常流量的那部分流量，是不会被放过的。

相对来说，令牌桶算法就可以应对这种“突发流量”。

# 变量描述

C：桶的总容量

r：令牌放入的速度

上个请求：a

上个请求的时间：at

w：桶里剩余的令牌（token）数

# 算法实现

消耗令牌的逻辑：

let R = 10; // 每ms允许10个流量，QPS是10000
let C = 20000; // 桶容量上限是20000个请求

let at = Date.now();
let w = 0;

function lingPaiTong() {
  const bt = Date.now();
  const wb = (bt - at) * R; // a请求和b请求之间，令牌桶中新放入的令牌
  w = min(w + wb, C); // 当前桶中剩余的令牌数
  at = bt;

  if (w > 0) {
    w--;
    return true; // 请求拿到令牌，令牌桶中令牌减1
  } else {
    return false;
  }
}

# 应用场景举例

比如 token 放入速度：5 个/s

总容量是：20 个 token

那么能处理 2 种流量：

• 平滑流量：每秒 5 个请求，持续 4s
• 突发流量：前 4s 无请求，桶中积累了 20 个 token，突然来了 13 个请求，那么都能处理，并且还剩 7 个 token