常用的限流算法总结

本篇文章主要对常用的限流算法进行总结，会按照以下思路来进行整理，首先明确什么是限流，为什么需要限流，常用的限流算法有哪些，最后对我自己觉得限流有关的比较不错的文章进行总结。

什么是限流

限流指代的是限制到达系统的并发请求数，使得系统能够正常的处理部分用户的请求，来保证系统的稳定性。限流不可避免的会造成用户的请求变慢或者被拒的情况，从而会影响用户体验。因此限流是需要在用户体验和系统稳定性之间做平衡的，即我们常说的 trade off。限流也称流控（流量控制）

为什么限流

限流主要是为了保证系统的稳定性，根本原因是后端机器的处理能力有限，满足不了当前大流量的访问。当然还有其它的比如放置恶意攻击等。

常用的限流算法

比较常用的限流算法有下面四种

固定窗口限流
滑动窗口限流
漏桶算法
令牌桶算法

固定窗口限流

将时间按照设定的周期划分为多个窗口
在当前时间窗口内每来一次请求就将计数器加一
如果计数器超过了限制数量，则拒绝服务
当时间到达下一个窗口时，计数器的值重置

对应的伪代码如下

boolean tryAcquire(){
    long now = currentTimeMillis(); // 获取当前时间
    if(now - lastAcquireTime > TimeWindow){  // 是否过了时间窗口
        counter = 0; // 计算器置0
        lastAcquireTime = now;
    }
    if(counter < threshold){  // 小于阈值
        counter++;
        return true;
    }
    return false;
}

这种算法很好实现，但是会出现限流不准确的问题，例如：

假设限制每秒通过 5 个请求，时间窗口的大小为 1 秒，当前时间窗口周期内的后半秒正常通过了 5 个请求，下一个时间窗口周期内的前半秒正常通过了 5 个请求，在这两个窗口内都没有超过限制。但是在这两个窗口的中间那一秒实际上通过了 10 个请求，显然不满足每秒 5 个请求的限制。

滑动窗口限流

将设定的时间周期设为滑动窗口的大小，记录每次请求的时刻
当有新的请求到来时将窗口滑到该请求来临的时刻
判断窗口内的请求数是否超过了限制，超过限制则拒绝服务，否则请求通过
丢弃滑动窗口以外的请求

这种算法解决了固定窗口计数器出现的通过请求数是限制数两倍的缺陷，但是实现起来较为复杂，并且需要记录窗口周期内的请求，如果限流阈值设置过大，窗口周期内记录的请求就会很多，就会比较占用内存。

对应的伪代码如下

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

滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。

我们所想的限流场景，例如每秒限制100个请求。希望请求每10ms来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率。因此可能存在5ms内就打满了阈值的情况。

当然对于这种情况还是有变型处理的，例如设置多条限流规则。不仅限制每秒 100 个请求，再设置每 10ms 不超过 2 个。

漏桶算法

将进来的请求流量视为水滴先放入桶内
水从桶的底部以固定的速率匀速流出，相当于在匀速处理请求
当漏桶内的水满时(超过了限流阈值)则拒绝服务

算法伪代码如下

boolean tryAcquire(){
    long now = currentTimeMillis(); // 获取当前时间
    long consumeWater = (now - lastInjectTime) * rate // 当前时间减去上次注水时间 * 流出的速率 = 流出的水量
    long leftWater = max(0, leftWater - consumeWater); // 之前桶内的水量 - 这段时间流出的水量
    if(leftWater + 1 <= capacity){ // 水桶内的水量 + 此次注入的异地书 是否不大于桶的大小
        lastInjectTime = now; // 重置注水时间 
        leftWater++; // 水桶数量+1
        return true;
    }else{
        return false;
    }
}

可以看到这种算法的特点就是宽进严出，有点类似于消息队列，具有削峰填谷的特点。一般漏捅算法也是由队列来实现，处理补过来的请求就排队，队列满了就开始拒绝请求。

经过上面漏桶对流量的处理，使得流量能够平滑的流出，看起来是不错的，但是在面对突发流量时，服务的处理速度和平时一样，而在这种情况下，真实希望的是在系统平稳运行的同时，提升用户体验，即能够更快的处理请求。

令牌桶算法

定速的往桶内放入令牌
令牌数量超过桶的限制，丢弃
请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝

对应的伪代码如下

boolean tryAcquire(){
    long now = currentTimeMillis(); // 获取当前时间
    long generatedToken = (now - lastInjectTime) * rate // 当前时间减去上次取令牌时间 * 流出的速率 = 流出的水量
    long leftToken = min(capacity, leftWater + generatedToken); // 之前桶内的令牌数+ 这段时间放入的令牌数
    if(leftToken >= 1){ 
        lastInjectTime = now; // 重置获取令牌时间
        leftToken--; // 令牌数-1
        return true;
    }
    return false;
}

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

对于需要预热的场景需要进一步考虑，比如我们的某个接口业务，需要使用到数据库连接，由于连接需要预热才能进入到最佳状态，如果我们的系统长时间处于低负载或零负载状态（当然，应用刚启动也是一样的），连接池中的连接慢慢释放掉了，此时我们认为连接池是冷的。

假设我们的业务在稳定状态下，正常可以提供最大 1000 QPS 的访问，但是如果连接池是冷的，我们就不能让 1000 个请求同时进来，因为这会拖垮我们的系统，我们应该有个预热升温的过程。

总结

上面所述的算法其实只是这些算法最粗略的实现和最本质的思想，在工程上其实还是有很多变型的。

从上面看来好像漏桶和令牌桶比时间窗口算法好多了，那时间窗口算法有啥子用，并不是的，虽然漏桶和令牌桶对比时间窗口对流量的整形效果更佳，流量更加得平滑，但是也有各自的缺点（上面已经提到了一部分）。

拿令牌桶来说，假设你没预热，那是不是上线时候桶里没令牌？没令牌请求过来不就直接拒了么？这就误杀了，明明系统没啥负载现在。

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

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

所以漏桶和令牌桶其实比较适合阻塞式限流场景，即没令牌我就等着，这就不会误杀了，而漏桶本就是等着。比较适合后台任务类的限流。而基于时间窗口的限流比较适合对时间敏感的场景，请求过不了直接返回给前端。

枫秀学习日志

常用的限流算法总结

什么是限流

为什么限流

常用的限流算法

固定窗口限流

滑动窗口限流

漏桶算法

令牌桶算法

总结

相关内容