常见限流算法

限流

工程上的限流是什么呢？

限制的是 「流」，在不同场景下「流」的定义不同，可以是每秒请求数、每秒事务处理数、网络流量等等。

通常我们说的限流指代的是 限制到达系统的并发请求数，使得系统能够正常的处理 部分 用户的请求，来保证系统的稳定性。

限流不可避免的会造成用户的请求变慢或者被拒的情况，从而会影响用户体验。因此限流是需要在用户体验和系统稳定性之间做平衡的，即我们常说的 trade off。

限流也称流控（流量控制）。

为什么需要限流

限流是为了保证系统的稳定性。

限流的本质是因为后端处理能力有限，需要截掉超过处理能力之外的请求，亦或是为了均衡客户端对服务端资源的公平调用，防止一些客户端饿死。

常见的限流算法

计数限流、滑动窗口限流、漏桶限流、令牌桶限流。

计数限流

计数限流是指限制某一个接口或者某一行为单位时间内的响应次数。设置一个计数器，对某一时间段内的请求进行计数，当请求超过设置的阈值之后则触发饱和策略（可以选择拒绝/阻塞请求）。

1
2
3
4
5
6
7

boolean tryAcquire() {
    if (counter < threshold) {
    counter ++;
        return true;
    }
    return false;
}

优点：简单粗暴，单机在 Java 中可用 Atomic 等原子类、分布式就 Redis incr。

缺点： 对突增流量处理不优化，有可能被绕过限流策略

假设系统每秒允许 100 个请求，假设第一个时间窗口是 0-1s，在第 0.55s 处一下次涌入 100 个请求，过了 1 秒的时间窗口后计数清零，此时在 1.05 s 的时候又一下次涌入100个请求。

虽然窗口内的计数没超过阈值，但是全局来看在 0.55s-1.05s 这 0.1 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。

滑动窗口限流

滑动窗口限流解决了上面的问题，可以保证在任意时间窗口内都不会超过阈值。

滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。

规则如下，假设时间窗口为 1 秒

• 记录每次请求的时间
• 统计每次请求的时间 至 往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
• 统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

1
2
3
4
5
6
7
8
9
10
11

boolean tryAcquire() {
    // 获取当前时间
    long now = currentTimeMuillis();
    // 根据当前时间获取窗口内的计数
    long counter = getCounterInTimeWindow(now);
    if (counter < threshold) { // 小于阈值
        addToTimeWindow(now);
        return true;
    }
    return false;
}

滑动窗口虽然解决了计数算法的临界值问题，但是对突增流量问题依旧不友好。

漏桶算法

漏桶（Leaky Bucket）算法是限流方面比较经典的算法，该算法最早应用于网络拥塞控制方面。

理解该算法可以联想一个具体的漏桶模型，不管进水量有多大，漏桶始终以恒定的速率往外排水，如果桶被装满则后来涌入的水会漫出去。

对应接口限流来说，用户的请求可以看做是这里的水，不管用户的请求量有多大多不均衡，能够被处理的请求速率是恒定的，而且能够被接受的请求数也是有上限的，超出上限的请求会被拒绝，典型的我们可以采用队列作为这里的漏桶实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

boolean tryAcquire() {
    // 获取当前时间
    long now currentTimeMillis();
    // （当前时间 - 上次注水时间）*流出速率 = 流出的水量
    long consumeWater = (now - lastInjectTime) * rate;
    // 之前桶内的水量 - 这段时间流出的水量
    long leftWater = max(0, leftWater - consumeWater);
    if (leftWater + 1 <= capacity) {
        lastInjectTime = now;
        leftWater ++;
        return true;
    } else {
        return false;
    }
}

由上面的解释我们应该能够感觉到漏桶算法非常适用于秒杀系统的限流，漏桶在这种应用场景下可以起到一定的削峰填谷的作用，并且漏桶的设计从根本上能够应对集中访问的问题，同时具备平滑策略，但是始终恒定的处理速率有时候并不一定是好事情，对于突发的请求洪峰，在保证服务安全的前提下，应该尽最大努力去响应，这个时候漏桶算法显得有些呆滞。

令牌桶算法

令牌桶（Token Bucket）算法可以看作是漏桶算法的逆过程。该算法要求系统以一定的速率发放访问令牌，用户的请求必须在持有合法令牌的前提下才能够被响应，我们可以按照权重设置一类请求被响应所需持有的令牌数，只有当桶中的令牌数目满足当前请求所需时才授予令牌，对于其他情况则拒绝该请求。

可以看出令牌桶在应对突发流量的时候，桶内假如有 100 个令牌，那么这 100 个令牌可以马上被取走，而不像漏桶那样匀速的消费。所以在应对突发流量的时候令牌桶表现的更佳。

虽然漏桶和令牌桶对比时间窗口对流量的限流效果更佳，流量更加得平滑，但是也有各自的缺点。

拿令牌桶来说，假设没预热，在刚上线时候桶里没令牌，这是就会存在误杀问题（系统明明没有负载）。

再比如说请求的访问其实是随机的，假设令牌桶每20ms放入一个令牌，桶内初始没令牌，这请求就刚好在第一个20ms内有两个请求，再过20ms里面没请求，其实从40ms来看只有2个请求，应该都放行的，而有一个请求就直接被拒了。这就有可能造成很多请求的误杀，但是如果看监控曲线的话，好像流量很平滑，峰值也控制的很好。

再拿漏桶来说，漏桶中请求是暂时存在桶内的。这其实不符合互联网业务低延迟的要求。

所以漏桶和令牌桶其实比较适合阻塞式限流场景，即没令牌我就等着，这就不会误杀了，而漏桶本就是等着。比较适合后台任务类的限流。而基于时间窗口的限流比较适合对时间敏感的场景，请求过不了您就快点儿告诉我，等的花儿都谢了。

限流的难点

__限流的难点在于配置__，如何让限流在不误伤的前提下尽量发挥硬件的最大性能是一个富有经验的问题，而压测是一个基础且行之有效的途径。

限流组件

• Google Guava - RateLimiter（基于令牌桶实现，并扩展了算法，支持预热功能）
• Alibaba - Sentinel （基于漏桶算法，匀速排队限流策略）