文章目录加载中
限流算法-令牌桶算法
# 漏桶算法的不足
当突发流量来袭的时候,由于漏桶算法的流速是固定的,所以超过日常流量的那部分流量,是不会被放过的。
相对来说,令牌桶算法就可以应对这种“突发流量”。
# 变量描述
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