解剖常见的限流算法_固定窗口滑动窗口

 

1. 瞬时流量过高，服务被压垮？
2. 恶意用户高频光顾，导致服务器宕机？
3. 消息消费过快，导致数据库压力过大，性能下降甚至崩溃？

限流顾名思义，就是对请求或并发数进行限制；通过对一个时间窗口内的请求量进行限制来保障系统的正常运行。如果我们的服务资源有限、处理能力有限，就需要对调用我们服务的上游请求进行限制，以防止自身服务由于资源耗尽而停止服务。

常用的限流算法有固定窗口算法、滑动窗口算法、漏斗算法和令牌桶算法 

1.固定窗口算法

固定窗口算法（有的也称计数器算法）是一种最简单的限流算法，它将时间划分为固定大小的窗口，例如1秒或1分钟。在每个窗口内，限定最大请求数量，如果窗口内请求数超过限定值，则进行限流。

所以在理想状态下，固定窗口是可以做到有效的限流的 

如下图：

但是 , 这种算法有一个很明显的临界问题：如果我在 0 秒末 和 1 秒初都发送一百个请求，我们这个限流算法并不会拦截，这种效果是我们想要的吗？显然不是！

 

固定窗口算法简单易懂，实现起来比较容易
但是其窗口大小固定，不适应请求流量的突发性波动，可能导致资源利用率低

实现代码：

public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms
 
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
    public long getNowTime() {
        return System.currentTimeMillis();
    }
}

2.滑动窗口算法

滑动窗口算法是对固定窗口算法的改进，它引入了一个滑动窗口，将时间划分为固定大小的窗口，并随着时间的推移，通过移动窗口的方式进行限流。例如，每隔一段时间移动一个窗口，新的请求会被计入窗口内，而旧的请求将被剔除。

TIPS: 当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

假设在0 时刻，是这样的

 在01.s 之后，这个窗口变成这样子(j假设窗口的移动时间间隔为1秒10次)

然后再模拟一下我们在固定窗口的限流失效的情况

在系统时间的 0 秒末 和 1 秒初都发送一百个请求

成功的拦截这个短时间间隔的高并发请求，达到了我们预期的限流效果

滑动窗口算法虽然解决了固定窗口的临界问题，但是一旦到达限流后，请求都会直接暴力被拒绝。酱紫我们会损失一部分请求，这其实对于产品来说，并不太友好。

3.漏桶算法

请求以固定速率到达，该算法会维护一个固定容量的漏桶，每个请求需要占用桶中的一个空间。如果桶已满，则拒绝请求。

用大白话来说就是：请求就像水一样以任意速度注入漏桶，而桶会按照固定的速率将水漏掉；当注入速度持续大于漏出的速度时，漏桶会变满，此时新进入的请求将会被丢弃。

 

由介绍可以知道，漏桶模式中的消费处理总是能以恒定的速度进行，可以很好的保护自身系统不被突如其来的流量冲垮；但是这也是漏桶模式的缺点，假设 QPS 为 2，同时 2 个请求进来，2 个请求并不能同时进行处理响应，因为每 1s / 2= 500ms 只能处理一个请求。

 

4.令牌桶算法

令牌桶算法是对漏桶算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发。

在令牌桶算法中，存在一个令牌桶，算法中存在一种机制以恒定的速率向令牌桶中放入令牌。令牌桶也有一定的容量（这是应对并发的关键），如果满了令牌就无法放进去了。当请求来时，会首先到令牌桶中去拿令牌，如果拿到了令牌，则该请求会被处理，并消耗掉拿到的令牌；如果令牌桶为空，则该请求会被丢弃。

 

Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一个实现，日常开发中我们也不会手动实现了，这里直接使用 RateLimiter 进行测试。

虽然演示了 Google Guava 工具包中的 RateLimiter 的实现，但是我们需要思考一个问题，就是令牌的添加方式，如果按照指定间隔添加令牌，那么需要开一个线程去定时添加，如果有很多个接口很多个 RateLimiter 实例，线程数会随之增加，这显然不是一个好的办法。

显然 Google 也考虑到了这个问题，在 RateLimiter 中，是在每次令牌获取时才进行计算令牌是否足够的。它通过存储的下一个令牌生成的时间，和当前获取令牌的时间差，再结合阈值，去计算令牌是否足够，同时再记录下一个令牌的生成时间以便下一次调用。

Guava 源码：

void resync(long nowMicros) { // 当前微秒时间
    // 当前时间是否大于下一个令牌生成时间
    if (nowMicros > this.nextFreeTicketMicros) { 
      	// 可生成的令牌数 newPermits = （当前时间 - 下一个令牌生成时间）/ 令牌生成时间间隔。
      	// 如果 QPS 为2，这里的 coolDownIntervalMicros 就是 500000.0 微秒(500ms)
        double newPermits = (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
				// 更新令牌库存 storedPermits。
      	this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
				// 更新下一个令牌生成时间 nextFreeTicketMicros
      	this.nextFreeTicketMicros = nowMicros;
    }
}

总结

固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有“突刺现象”，在窗口切换时可能会产生两倍于阈值流量的请求。

而滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题。

漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。

令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。