从理论到实践：对四种限流算法的思考与总结

312

发布时间：2024-09-07 10:56:01

在分布式系统中，限流是一个重要的机制，它用来保护系统免受突发流量的冲击，防止系统过载导致的服务不可用。限流算法主要有以下四种：固定窗口限流、滑动窗口限流、漏桶算法以及令牌桶算法。

固定窗口限流

定义: 在固定的时间窗口内，只允许特定数量的请求通过，超过该数量的请求将被拒绝。

优点: 实现简单，易于理解和实现。

缺点: 容易造成流量突刺现象。例如，如果一分钟内允许10次请求，那么在开始的第一秒内所有请求都到达，下一分钟开始时又会有一波新的请求到达，这会导致服务端的压力瞬间增大。

JAVA示例代码：

import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowRateLimiter {
    private final int limit;
    private final AtomicInteger counter = new AtomicInteger(0);
    private long lastResetTime = System.currentTimeMillis();

    public FixedWindowRateLimiter(int limit) {
        this.limit = limit;
    }

    public boolean allow() {
        long now = System.currentTimeMillis();
        if (now - lastResetTime >= 1000) { // 以秒为单位重置
            counter.set(0);
            lastResetTime = now;
        }
        return counter.incrementAndGet() <= limit;
    }
}

滑动窗口限流

定义: 将固定窗口进行细分，分成多个更小的时间段，每个时间段内的请求数量都有一个上限，从而平滑了请求的分布。

优点: 解决了固定窗口限流的流量突刺问题。

缺点: 实现较为复杂，需要精确地控制时间窗口的大小以及如何移动这些窗口。

JAVA示例代码：

import java.util.concurrent.ConcurrentLinkedQueue;

public class SlidingWindowRateLimiter {
    private final ConcurrentLinkedQueue<Long> queue = new ConcurrentLinkedQueue<>();
    private final int limitPerSecond;
    private final long windowMs = 1000; // 一秒

    public SlidingWindowRateLimiter(int limitPerSecond) {
        this.limitPerSecond = limitPerSecond;
    }

    public boolean allow() {
        long now = System.currentTimeMillis();
        queue.removeIf(time -> time < now - windowMs);
        if (queue.size() >= limitPerSecond) {
            return false;
        }
        queue.add(now);
        return true;
    }
}

漏桶算法

定义: 想象一个有固定容量的桶，请求到达时放入桶中，然后按照固定的速率流出桶。如果桶满了，后续的请求会被丢弃。

优点: 能够平滑流量，保证系统的稳定运行。

缺点: 固定的流出速率意味着无法充分利用系统的瞬时处理能力，可能导致一些请求被无谓地丢弃。

JAVA示例代码：

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class LeakyBucket {
    private final ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
    private final int capacity;
    private final int rate;
    private int current;

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.current = 0;
        executor.scheduleAtFixedRate(() -> decrement(), 0, 1000 / rate, TimeUnit.MILLISECONDS);
    }

    public synchronized boolean allow() {
        if (current < capacity) {
            current++;
            return true;
        }
        return false;
    }

    private synchronized void decrement() {
        if (current > 0) current--;
    }
}

令牌桶算法

定义: 类似于漏桶算法，但令牌桶允许以一定的速率向桶中填充令牌，且桶有一定的容量。请求需要获取令牌后才能被处理，如果桶中有足够的令牌，则可以立即处理请求；如果没有，则等待或者被拒绝。

优点: 不仅能够平滑流量，还能在短时间内处理突发流量，提高了系统的吞吐量。

缺点: 需要合理配置令牌的生成速率和桶的大小，否则可能会导致资源浪费或服务响应延迟。

JAVA示例代码：

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class TokenBucket {
    private final ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);
    private final int capacity;
    private final int rate;
    private int tokens = 0;

    public TokenBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        executor.scheduleAtFixedRate(this::addToken, 0, 1000 / rate, TimeUnit.MILLISECONDS);
    }

    public synchronized boolean allow() {
        if (tokens > 0) {
            tokens--;
            return true;
        }
        return false;
    }

    private synchronized void addToken() {
        if (tokens < capacity) tokens++;
    }
}

注：以上代码只是示意性的，并未处理所有可能的异常情况，实际生产环境中使用时需根据具体情况进行调整和完善。

本文被 Java编程专题收录

13712947744