高并发系统的限流算法与实现

开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。

• 缓存：缓存的目的是提升系统访问速度和增大系统处理容量。
• 降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。
• 限流：限流的目的是通过对并发请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以进行拒绝服务、排队或等待、降级等处理。

限流是限制系统的输入和输出流量，以达到保护系统的目的，而限流的实现主要是依靠限流算法，限流算法主要有4种：

1. 固定时间窗口算法（计数器）
2. 滑动时间窗口算法
3. 令牌桶算法
4. 漏桶算法

1. 固定时间窗口算法

又称计数器算法。固定时间窗口算法就是统计记录单位时间内进入系统或者某一接口的请求次数，在限定的次数内的请求则正常接收处理，超过次数的请求则拒绝掉或者改为异步处理等限流措施。

时间窗口长度如果为1分钟，如图。

此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性即可轻松实现。

单机伪代码如下。

class CounterDemo {
    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;
        }
    }
}

算法特点

1. 实现简单。
2. 时间窗口固定，每个窗口开始时计数为零，这样后面的请求不会受到之前的影响，做到了前后请求隔离。
3. 因为两个时间窗口之间没有任何联系，所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求。所以固定时间窗口算法无法限制窗口间突发流量。

2. 滑动时间窗口算法

滑动时间窗口算法其实是固定时间窗口算法的优化，主要是为了解决固定时间窗口算法无法限制窗口间突发流量的缺点。 上面的计数器的单位时间是1分钟，而在使用滑动时间窗口，可以把1分钟分成6格，每格时间长度是10s，每一格又各自管理一个计数器，单位时间用一个长度为60s的窗口描述。一个请求进入系统，对应的时间格子的计数器便会+1，而每过10s，这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限，便会执行限流措施。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

算法特点

1. 因为窗口顺延，所以可以抵御窗口间突发流量(对比固定时间窗口算法)。
2. 假如限流10万次/小时，如果某个调用者在前10分钟调用了10万次那么他必须再等待1小时才能发起下一次正常请求。所以没有做到前后请求隔离。

阿里开源的Sentinel，采用的是滑动窗口算法进行限流，可以阅读相关代码，加深对滑动时间窗口算法的理解。

3. 漏桶算法(leaky bucket)

漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。这个从桶底流出去的水就是系统正常处理的请求，从旁边流出去的水就是系统拒绝掉的请求。

单机伪代码如下。

class LeakyDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public int water; // 当前水量(当前累积请求数)

    public boolean grant() {
        long now = getNowTime();
        water = max(0, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        } else {
            // 水满，拒绝加水
            return false;
        }
    }
}

算法特点

1. 因为流出的速度是一定的，可以抵御突发流量，做到更加平滑的限流，而且不允许流量突发。

4. 令牌桶算法(Token Bucket)

令牌桶算法是比较常见的限流算法之一，Google开源项目Guava中的RateLimiter使用的就是令牌桶算法。流程如下：

1. 所有的请求在处理之前都需要拿到一个可用的令牌才会被处理。
2. 根据限流大小，设置按照一定的速率往桶里添加令牌。
3. 桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝。
4. 请求到达后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除。

单机伪代码如下，分布式环境可以使用Redisson。

class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public int tokens; // 当前令牌数量

    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若桶中没有令牌,则拒绝
            return false;
        } else {
            // 还有令牌，领取令牌
            tokens -= 1;
            return true;
        }
    }
}

算法特点

1. 可以抵御突发流量，因为桶内的令牌数不会超过给定的最大值
2. 可以做到更加平滑的限流，因为令牌是匀速放入的。
3. 令牌桶算法允许流量一定程度的突发。（相比漏桶算法）

在时间点刷新的临界点上，只要剩余token足够，令牌桶算法会允许对应数量的请求通过，而后刷新时间因为token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量。因此，令牌桶算法也被广泛使用。

更多内容，欢迎关注微信公众号：全菜工程师小辉~