限流算法

背景

在分布式系统中，随着业务量的增长，如何保护核心资源、防止系统过载、保证系统的稳定性成为了一个重要的问题。限流算法作为一种有效的流量控制手段，被广泛应用于各类系统中。

基于计数的限流算法

这种算法的基本思想是通过维护一个计数器，在特定的时间窗口内累计接收到的请求次数，当请求次数达到预设的阈值时，后续的请求会被限流或直接拒绝。

  1. 在一个固定的时间窗口（如1分钟）内，系统初始化一个计数器count为0。
  2. 每当一个新的请求到达时，计数器增加1。
  3. 当计数器的值超过了预先设定的限流阈值时，后续的请求会被限制。
  4. 时间窗口结束后（即过了1分钟），不管当前计数器的数值如何，都会重置为0，下一个时间窗口开始重新计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public interface RateLimiter {
    boolean acquire();
}
public class CounterBasedRateLimiter implements RateLimiter {
    /**
     * 窗口时长，毫秒级
     */
    private final long windowSize;
    /**
     * 限流大小
     */
    private final int limit;
    /**
     * 窗口开始时间，毫秒级
     */
    private long windowStartTime;
    /**
     * 计数器
     */
    private final AtomicInteger counter;

    public CounterBasedRateLimiter(long windowSize, int limit) {
        this.windowSize = windowSize;
        this.limit = limit;
        this.counter = new AtomicInteger();
        reset();
    }

    private synchronized void reset() {
        if (checkIfWindowValid()) {
            return;
        }
        windowStartTime = System.currentTimeMillis();
        counter.set(0);
    }

    private boolean checkIfWindowValid() {
        return System.currentTimeMillis() - windowStartTime <= windowSize;
    }

    @Override
    public boolean acquire() {
        // 检查窗口是否有效，若已无效则重置
        if (!checkIfWindowValid()) {
            reset();
        }
        return counter.incrementAndGet() <= limit;
    }
}

优点

  • 实现简单：它是最简单的限流算法之一，只需要维护一个计数器变量，每来一个请求就进行计数操作，无需复杂的逻辑设计
  • 直观易懂：设置明确的阈值，比如规定每秒允许100个请求，易于理解和配置
  • 实时性好：当请求到达时能够迅速做出是否允许的决策，不需要等待额外的信号或者状态变化
  • 资源消耗少：对于单机应用而言，仅需基本的内存空间来保存计数器即可，无需额外的队列或其他复杂数据结构

缺点

  • 突刺现象（毛刺效应）：在时间窗口切换时，若前一个窗口内的请求未满额，而后一个窗口一开始即有大量的请求涌入，则可能导致服务器瞬间压力过大。例如，如果1秒内允许100个请求，但在某秒的最后时刻突然来了100个请求，然后下一秒又是100个请求，即使总的请求并未超出每秒100次的限制，但连续两个窗口之间并没有均匀分配请求，从而造成服务压力波动。
  • 无法平滑限流：固定窗口计数器无法平滑控制请求流量，即无法很好地处理突发流量和平均流量之间的平衡。
  • 对周期较长的时间窗口效果不佳：长时间窗口内的限流可能会因为请求分布不均而导致服务器负载忽高忽低。

基于滑动窗口的限流算法

基于滑动窗口的限流算法是一种较为先进且灵活的流量控制技术，用于限制在一定时间窗口内某个资源的访问次数或流量。相较于简单的固定窗口计数器限流，滑动窗口算法能更好地处理请求的均匀分布和平滑限流，减少因为窗口切换带来的不连续性和峰值问题。

  1. 窗口划分：将时间线划分为一系列固定大小的连续小窗口，例如，将一分钟划分为60个一秒的窗口。
  2. 窗口滑动：随着时间的推进，窗口就像一个滑动门一样，不断地向右滑动，每过一秒，新的窗口就会取代旧窗口。
  3. 请求计数：每当一个请求到来时，系统会在对应的时间窗口内进行计数。也就是说，每个窗口都有一个独立的计数器，记录在此窗口内发生的请求次数。
  4. 限流判断：判断当前时间点对应的完整滑动窗口内（从现在开始回溯至窗口大小之前的所有时间）的请求总数是否超过了预设的阈值。如果超过阈值，则拒绝新增的请求；否则，接受请求并将该窗口内的计数器加一。
  5. 窗口更新：每当滑动窗口向前移动时，旧窗口内的计数器不再增加，并且可能被清除或复位，以便继续统计新窗口的请求。
  6. 平滑处理突发流量：相比固定窗口，滑动窗口的优势在于它能够更平滑地处理流量的变化，因为它总是考虑的是最近一段时间内的请求总量，而不是在固定的间隔点重置计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class SlidingWindowRateLimiter implements RateLimiter {
    /**
     * 窗口时长，秒级
     */
    private final long windowSize;
    /**
     * 限流大小
     */
    private final int limit;
    /**
     * 滑动窗口
     */
    private final ConcurrentHashMap<Long, AtomicInteger> window;
    /**
     * 当前滑动窗口的起始区间
     */
    private long windowStart;
    /**
     * 当前总数
     */
    private final AtomicInteger total;

    public SlidingWindowRateLimiter(long windowSize, int limit) {
        this.windowSize = windowSize;
        this.limit = limit;
        this.window = new ConcurrentHashMap<>();
        this.total = new AtomicInteger();
        this.windowStart = System.currentTimeMillis() / 1000;
    }

    private synchronized void refresh(long cur) {
        // 再次检查
        if (window.containsKey(cur)) {
            return;
        }

        // 清理过期区间数据
        long newWindowStart = cur - windowSize + 1;
        for (long i = windowStart; i < newWindowStart; i++) {
            AtomicInteger removed = window.remove(i);
            if (removed != null) {
                total.addAndGet(-removed.intValue());
            }
        }
        windowStart = newWindowStart;

        // 最后加上新的时间区间
        window.putIfAbsent(cur, new AtomicInteger(0));
    }

    @Override
    public boolean acquire() {
        long cur = System.currentTimeMillis() / 1000;
        // 检查当前时间区间是否已初始化，若未初始化，则进行初始化
        if (!window.containsKey(cur)) {
            refresh(cur);
        }

        // 尝试从滑动窗口获取元素
        while (!Thread.interrupted()) {
            int curTotal = total.get();
            if (curTotal + 1 > limit) {
                return false;
            }
            if (total.compareAndSet(curTotal, curTotal + 1)) {
                window.get(cur).incrementAndGet();
                return true;
            }
        }
        return false;
    }
}

优点

  • 平滑限流：滑动窗口算法能够在一定程度上平滑地控制流量，因为它不是基于固定时间间隔进行重置计数，而是随着时间的推移逐步更新窗口内的请求计数，这样可以有效避免固定窗口算法在窗口切换时出现的“突刺现象”，即短时间内流量集中涌入。
  • 灵活性：可以灵活地控制时间窗口的粒度，例如将其划分为多个小窗口，这样可以根据实际业务需求调整限流策略的灵敏度和精度。
  • 即时性：滑动窗口能够即时反应系统的实时负载状况，每当一个窗口过去，新的窗口立刻生效，所以限流策略能够更快地响应系统负载的变化。
  • 适应突发流量：对于短期的突发流量，滑动窗口限流算法相比于固定窗口更能合理地分配流量，因为它考虑到的是过去一段时间内整体的请求量，而非单一窗口内的绝对数量。

缺点

  • 复杂性提高：相较于固定窗口计数器，滑动窗口算法在实现上更为复杂，需要维护多个窗口及其计数器的状态，增加了系统的复杂性和实现成本。
  • 空间占用：随着窗口粒度的细化，需要存储的数据结构（如队列或哈希表）所占用的内存空间也会相应增大。特别是在高并发和长时间跨度的情况下，可能需要更大的内存来支持多窗口的计数。
  • 处理突发流量局限性：虽然相比固定窗口有所改善，但如果突发流量非常猛烈且持续时间超过一个窗口的长度，滑动窗口限流仍可能无法完全消除流量尖峰对系统的影响。

漏桶算法

基于漏桶（Leaky Bucket）的限流算法是一种在网络传输和系统资源管理中广泛应用的流量整形和控制技术。该算法的核心理念是模拟一个带有小孔的桶，其中水代表流入系统的请求或数据包，桶则象征系统的处理能力。

  1. 桶容量：漏桶有一个固定容量，代表着系统能够暂时缓冲的最大请求量。不过，不同于令牌桶算法，漏桶的实际容量并不直接影响限流速率，只是决定了系统能够承受多大的突发流量。
  2. 漏水速率：漏桶上有固定速率的漏水口，这个速率代表了系统能够处理请求的恒定速度。无论桶内有多少水（请求），系统都按此速率向外处理请求。
  3. 流入请求：请求像水滴一样源源不断地进入漏桶，不论请求的速率有多快，漏桶都会接收所有的请求。
  4. 流量控制：如果请求的速率超过了漏水速率，那么漏桶内部的水量将会逐渐积累起来。当桶满时，新来的请求将被丢弃或拒绝，以此来限制流入系统的总体流量。
  5. 无突发处理能力：漏桶算法的一个显著特点是它不具备处理突发流量的能力。即使桶内没有水（请求空闲期），漏水速率也不会因此加快，这意味着系统的处理速率始终保持恒定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class LeakyBucketRateLimiter implements RateLimiter {
    /**
     * 流速，每秒漏rate个
     */
    private final int rate;
    /**
     * 桶大小
     */
    private final int bucketSize;
    /**
     * 漏桶
     */
    private final BlockingQueue<Object> bucket;

    public LeakyBucketRateLimiter(int bucketSize, int rate) {
        this.bucketSize = bucketSize;
        this.rate = rate;
        bucket = new ArrayBlockingQueue<>(bucketSize);
        new Thread(this::leaky).start();
    }

    public void leaky() {
        // 按照规定速度漏
        while (!Thread.interrupted()) {
            bucket.poll();
            sleep();
        }
    }

    @Override
    public boolean acquire() {
        // 尝试向桶插入元素，若有空间能插入返回true，否则返回false
        return bucket.offer(1);
    }

    public void sleep() {
        try {
            Thread.sleep(1000 / rate);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

优点

  • 流量整形：漏桶算法能够强制将流量塑造成稳定的涓流，确保系统处理请求的速率恒定，这对于保护系统免受突发流量冲击，保持稳定性能非常重要。
  • 公平性：所有进入漏桶的请求都会按照预定的速率被处理，无论请求何时到达，都能得到公平对待，不存在请求间的竞争关系。
  • 易于实现：漏桶算法的概念和实现相对简单，可以用一个队列加上定时任务来模拟漏桶的行为，便于快速实施和调试。
  • 防止系统过载：当系统无法处理过多的请求时，漏桶可以作为一个缓存区，暂时存储部分请求，但由于漏水速率恒定，一旦桶满，超出的部分会被丢弃或拒绝，从而保护系统不被过度压垮。

缺点

  • 无法处理突发流量：漏桶算法最大的缺点是无法应对合理的突发流量需求。无论系统当前负载如何，只要漏桶的漏水速率不变，即使是系统有能力处理更多的请求时，也无法加速处理突发的大量请求。
  • 资源利用率不高：在流量较低时，漏桶算法可能导致系统资源利用率不足。即使系统此时有足够的处理能力，也无法增加处理速率，这可能导致在某些时段内系统性能未能充分利用。
  • 缺乏弹性：对于那些希望系统能在负载较低时积攒一定的处理能力以应对未来可能的突发请求的场景，漏桶算法并不能提供这样的弹性伸缩特性。
  • 无法区分优先级：漏桶算法对所有请求一视同仁，不考虑请求的优先级，所有请求都按相同的速率流出，不利于实现基于优先级的流量控制。

令牌桶算法

基于令牌桶（Token Bucket）的限流算法是一种在网络传输、系统资源调度和API调用限速等领域广泛应用的流量控制策略。该算法通过模拟一个不断填充令牌的桶来决定哪些请求可以被执行。

  1. 令牌生成：系统按照一个恒定的速率生成令牌并存入令牌桶中。这个速率体现了系统允许的最大处理速率。
  2. 令牌桶容量：令牌桶具有一个固定的容量上限，当桶内令牌数量达到容量上限时，多余的令牌将被丢弃。
  3. 请求处理：当请求到达时，必须从令牌桶中获取一个或多个令牌（取决于请求所需的成本或权重）。只有当桶中有足够的令牌可供消费时，请求才会被允许执行。
  4. 突发处理：令牌桶的一个重要特性是可以积累令牌，因此在请求较少时，令牌会不断累积在桶内。这样一来，当后续有突发请求时，桶内已经累积的令牌可以快速满足这些请求，使得系统在一定程度上能够应对短期内的流量高峰。
  5. 流量控制：通过控制令牌生成速率和桶的容量，系统可以实现对请求处理速率的限制。如果令牌桶为空并且系统还在按照限速速率填充令牌，后续的请求将不得不等待令牌生成后再处理，从而实现了限流目的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class TokenBucketRateLimiter implements RateLimiter {
    /**
     * 每秒补充的令牌数
     */
    private final int rate;
    /**
     * 最大令牌数量
     */
    private final int bucketSize;
    /**
     * 令牌桶
     */
    private final AtomicInteger bucket;

    public TokenBucketRateLimiter(int rate, int bucketSize) {
        this.rate = rate;
        this.bucketSize = bucketSize;
        bucket = new AtomicInteger(0);
        new Thread(this::refill).start();
    }

    public void refill() {
        // 定时补充令牌
        while (!Thread.interrupted()) {
            if (bucket.get() < bucketSize) {
                bucket.incrementAndGet();
            }
            sleep();
        }
    }

    @Override
    public boolean acquire() {
        // 尝试获取令牌
        while (!Thread.interrupted()) {
            int cur = bucket.get();
            if (cur == 0) {
                return false;
            }
            if (bucket.compareAndSet(cur, cur - 1)) {
                return true;
            }
        }
        return false;
    }

    public void sleep() {
        try {
            Thread.sleep(1000 / rate);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

优点

  • 允许突发流量：令牌桶算法能够在规定了平均发送速率的同时，允许某种程度的突发请求。当令牌桶中有足够令牌积累时，短时间内大量请求可以被迅速处理，这有利于应对系统的峰值负载。
  • 平滑限流：虽然令牌桶本身并不直接平滑输出流量，但它能通过持续且均匀地向桶中添加令牌来维持一个稳定的平均处理速率。因为令牌可以预先积累，所以对于短期的超额流量有一定的容忍度。
  • 灵活配置：令牌桶算法可以根据需要调整令牌生成速率（即限流速率）和桶的容量（即最大突发容量），从而灵活地适应不同应用场景下的流量控制要求。
  • 响应及时性：只要令牌桶中有令牌，请求就能立即得到处理，减少了延迟，提升了用户体验。

缺点

  • 无法严格限制瞬时流量：尽管令牌桶算法能在一定程度上抑制突发流量，但如果桶的容量较大，短时间内仍可能允许超出平均速率的流量通过。
  • 实现复杂度：相比于简单的固定速率控制机制，令牌桶算法的实现相对复杂，需要设计和维护令牌的生产和消费过程。
  • 无法精确匹配特定时间窗口内的绝对限流：在一些需要严格保证每个时间窗口内请求总量不超过某一阈值的场景下，令牌桶可能无法做到完全精确控制。
  • 内存消耗：令牌桶需要存储令牌的数量信息，大规模分布式系统中可能会带来额外的内存开销。

限流工具

Guava RateLimiter

Redisson RateLimiter

系统设计
#系统设计 #限流算法
限流算法
http://hanqichuan.com/2024/12/19/系统设计/限流算法/
作者
韩启川
发布于
2024年12月19日
许可协议