漏桶算法

算法介绍

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

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

变量描述

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:桶的总容量