四大限流算法教你如何应对流量激增

共计 4282 个字符，预计需要花费 11 分钟才能阅读完成。

在分布式系统中，高并发场景下，为了防止系统因突然的流量激增而导致的崩溃，同时保证服务的高可用性和稳定性，限流是最常用的手段。
实际开发可能都是直接用现成的轮子，现成的限流框架Sentinel、Zuul、Hystrix等，但是底层的算法还是有必要了解一下。这里主要介绍4种常见的限流算法：固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。

一、固定窗口算法

固定窗口限流算法，也叫计数器限流算法，是最简单的一种限流算法。

1.1 实现原理

原理：在一个固定长度的时间窗口内限制请求数量，来一个请求，次数加一，超过最大限制，就拒绝。

1.2 代码实现

public class FixWindowLimiter {

    /**
     * 每个窗口的最大请求数量
     */
    public static long threshold = 10;
    /**
     * 窗口大小，1000ms
     */
    public static long windowUnit = 1000;
    /**
     * 窗口内的当前请求数量
     */
    public static long count = 0;
    /**
     * 窗口的开始时间
     */
    public static long lastTime = 0;

    /**
     * 限流方法，返回true表示通过
     */
    public boolean limit() {
        // 获取系统当前时间
        long currentTime = System.currentTimeMillis();
        // 判断是否在当前时间窗口内，如果不在就开启一个新的时间窗口
        if (currentTime - lastTime > windowUnit) {
            // 计数器清零
            count = 0;
            // 开启新的时间窗口
            lastTime = currentTime;
        }
        // 判断是否超过最大请求量
        if (count < threshold) {
            count++;
            return true;
        }
        return false;
    }

}

1.3 优缺点

优点： 实现简单，容易理解
缺点：

1. 限流不够平滑。例如：限流每秒3个，在第一毫秒就处理了3个请求，达到限流阈值，窗口剩余时间的请求都将被拒绝。
2. 无法处理窗口边界问题。因为是在某个时间窗口进行流量控制，所以可能出现边界问题，即在时间窗口的边界可能会有大量的请求被允许，导致突发流量。

二、滑动窗口算法

滑动窗口算法是对固定窗口算法的改进。在滑动窗口算法中，窗口的起止时间是动态的，窗口大小是固定的。这种算法能够较好的处理窗口的边界问题，但需要记录每个请求的时间戳。

2.1 实现原理

来一个请求，就向后推一个时间窗口，计算这个窗口内的请求数量。如果数量超过限制就拒绝请求，否则接受请求，并记录请求时间戳，另外还需要一个任务清理过期的时间戳。

2.2 代码实现

public class SlidingWindowLimiter {

    /**
     * 每个窗口的最大请求数量
     */
    public static long threshold = 10;
    /**
     * 窗口大小，1000ms
     */
    public static long windowUnit = 1000;
    /**
     * 请求集合，用来存储窗口内的请求数量
     */
    public static List<Long> requestList = new ArrayList<>();

    /**
     * 限流方法，返回true表示通过
     */
    public boolean limit() {
        // 获取系统当前时间
        long currentTime = System.currentTimeMillis();
        // 统计当前窗口内，有效的请求数量
        int sizeOfValid = this.sizeOfValid(currentTime);
        // 判断是否超过最大请求数量
        if (sizeOfValid < threshold) {
            // 把当前请求添加到请求集合里
            requestList.add(currentTime);
            return true;
        }
        return false;
    }

    /**
     * 统计当前窗口内，有效的请求数量
     */
    private int sizeOfValid(long currentTime) {
        int sizeOfValid = 0;
        for (Long requestTime : requestList) {
            // 判断是否在当前时间窗口内
            if (currentTime - requestTime <= windowUnit) {
                sizeOfValid++;
            }
        }
        return sizeOfValid;
    }

    /**
     * 清理过期的请求（单独启动一个线程处理）
     */
    private void clean() {
        // 判断是否超出当前时间窗口内
        requestList.removeIf(requestTime -> System.currentTimeMillis() - requestTime > windowUnit);
    }

}

2.3 优缺点

优点：解决了固定窗口算法的窗口边界问题，避免了突发流量击垮服务器
缺点：

• 依然存在限流不够平滑的问题。例如：限流每秒3个，在第一毫秒发送了3个请求，达到 限流，剩余的窗口时间内的请求会被拒绝。

三、漏桶算法

漏桶算法是一种常用的流量整形(traffic shaping)和流量控制(traffic policing)的算法，它可以有效的控制数据的传输速率以及网络拥塞。

3.1 实现原理

• 一个固定容量的漏桶，按照固定速率出水（处理请求）;
• 当流入谁（请求数量）的速度过大，会直接溢出（超过限制的请求会直接被丢弃/拒绝）；
• 桶里的水（请求）不够则无法出水（桶内没有请求则不处理）；

当请求流量正常或者较小的时候，请求能够得到正常的处理。当请求流量过大，漏桶限流算法可以通过丢弃部分请求来防止系统过载。

这种算法的一个重要特性是，输出速率始终保持一致，无论输入的流量怎么变化。也正是因为如此，它无法处理突发流量。此外，如果入口流量过大，漏桶可能溢出，导致数据丢失。

3.2 代码实现

public class LeakyBucketLimiter {

    /**
     * 桶的最大容量
     */
    public static long threshold = 10;
    /**
     * 桶内当前水量
     */
    public static long count = 0;
    /**
     * 漏水速率（每秒5次）
     */
    public static long leakRate = 5;
    /**
     * 上次漏水时间
     */
    public static long lastLeakTime = System.currentTimeMillis();

    /**
     * 限流方法，返回true表示通过
     */
    public boolean limit() {
        // 调用漏水方法
        this.leak();
        // 判断是否超过最大请求数量
        if (count < threshold) {
            count++;
            return true;
        }
        return false;
    }

    /**
     * 漏水方法，计算并更新这段时间内漏水量
     */
    private void leak() {
        // 获取系统当前时间
        long currentTime = System.currentTimeMillis();
        // 计算这段时间内，需要流出的水量
        long leakWater = (currentTime - lastLeakTime) * leakRate / 1000;
        count = Math.max(count - leakWater, 0);
        lastLeakTime = currentTime;
    }

}

3.3 优缺点

优点：

• 平滑流量。固定的速率处理请求，平滑和整形流量，避免流量突发和波动。
• 防止过载。多余的流量可以直接丢弃。
  缺点：
• 无法处理突发流量。漏桶的出口速率固定，无法处理突发流量
• 可能会丢失数据。如果入口流量过大，超过桶的容量，那么会丢弃部分请求。在一些不能接受丢失请求的场景不适用

四、令牌桶算法

令牌桶限流算法也是一种常用的流量整形和速率限制算法。

4.1 实现原理

1. 系统以固定的速率向桶中添加令牌
2. 当有请求到来时，会尝试从桶中移除一个令牌。只要桶中有足够的令牌，则请求都会被处理
3. 如果桶中没有令牌，那么请求会被拒绝
4. 桶中的令牌数不能超过桶的数量，如果新的令牌超过桶的容量，新的令牌会被丢弃

令牌桶算法的一个重要特性是，它可以应对突发流量。当桶中有足够的令牌，就可一次性处理多个请求。

4.2 代码实现

public class TokenBucketLimiter {

    /**
     * 桶的最大容量
     */
    public static long threshold = 10;
    /**
     * 桶内当前的令牌数量
     */
    public static long count = 0;
    /**
     * 令牌生成速率（每秒5次）
     */
    public static long tokenRate = 5;
    /**
     * 上次生成令牌的时间
     */
    public static long lastRefillTime = System.currentTimeMillis();

    /**
     * 限流方法，返回true表示通过
     */
    public boolean limit() {
        // 调用生成令牌方法
        this.refillTokens();
        // 判断桶内是否还有令牌
        if (count > 0) {
            count--;
            return true;
        }
        return false;
    }

    /**
     * 生成令牌方法，计算并更新这段时间内生成的令牌数量
     */
    private void refillTokens() {
        long currentTime = System.currentTimeMillis();
        // 计算这段时间内，需要生成的令牌数量
        long refillTokens = (currentTime - lastRefillTime) * tokenRate / 1000;
        count = Math.min(count + refillTokens, threshold);
        lastRefillTime = currentTime;
    }

}

4.3 优缺点

优点：

1. 可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
2. 限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）。
3. 灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率。

缺点：

1. 可能导致过载：如果令牌产生的速度过快，可能会导致大量的突发流量，这可能会使网络或服务过载。
2. 需要存储空间：令牌桶需要一定的存储空间来保存令牌，可能会导致内存资源的浪费。
3. 实现稍复杂：相比于计数器算法，令牌桶算法的实现稍微复杂一些。

五、总结

固定窗口算法实现简单，但是限流不够平滑，存在窗口边界问题，适用于需要简单实现限流的场景。

滑动窗口算法解决了窗口边界问题，但是还是存在限流不够平滑的问题，适用于需要控制平均请求速率的场景。

漏桶算法的优点是流量处理更平滑，但是无法应对突发流量，适用于需要平滑流量的场景。

令牌桶算法既能平滑流量，又能处理突发流量，适用于需要处理突发流量的场景。