文章目录加载中

限流算法-令牌桶算法

# 漏桶算法的不足

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

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

# 变量描述

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
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog