限流算法-漏桶和令牌桶

限流算法-漏桶和令牌桶

Tags
流量控制
令牌桶算法
漏桶算法
CreatedTime
Aug 15, 2022 06:37 AM
Slug
2020-10-11-lou-tong
UpdatedTime
Last updated August 15, 2022

漏桶算法

算法介绍

漏桶算法能够实现平滑流量,防止过大流量打到后端服务,导致崩溃。
对于不确定的流入速度,经过漏桶的处理,流出的速度是稳定。

变量描述

C:桶的总容量
r:水漏走的速度
a:上个请求
at:上个请求进来的时间
w:处理完上个请求后,桶里的总量
b:新请求
bt:新请求进来的时间

算法实现

let R = 10; // 每ms允许10个流量,QPS是10000 let C = 20000; // 桶容量上限是20000个请求 let at = Date.now(); let w = C; function loutong() { const bt = Date.now(); const wb = (bt - at) * R; // a请求和b请求之间,漏桶中溜走的水 w = max(w - wb, 0); // 当前桶中还没消耗的水 at = bt; if (w < C) { ++w; return true; // 放过请求 } else { return false; } }

令牌桶算法

漏桶算法的不足

当突发流量来袭的时候,由于漏桶算法的流速是固定的,所以超过日常流量的那部分流量,是不会被放过的。
相对来说,令牌桶算法就可以应对这种“突发流量”。

变量描述

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