限流算法-漏桶和令牌桶

漏桶算法

算法介绍

漏桶算法能够实现平滑流量，防止过大流量打到后端服务，导致崩溃。

对于不确定的流入速度，经过漏桶的处理，流出的速度是稳定。

变量描述

C：桶的总容量

r：水漏走的速度

a：上个请求

at：上个请求进来的时间

w：处理完上个请求后，桶里的总量

b：新请求

bt：新请求进来的时间

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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）数

算法实现

消耗令牌的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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