生产环境常见的限流算法

在高并发场景下，为了保护系统的稳定性和可用性，需要对请求进行限流。本文介绍几种生产环境中常见的限流算法，并结合Java代码实现。

令牌桶算法

令牌桶算法是一种基于固定时间间隔补充令牌的算法，其核心思想是通过令牌桶来控制请求的访问速率。

具体实现方法：

1. 定义一个令牌桶，包含以下属性：
   • rate：每秒产生多少个令牌。
   • burst：桶的大小（最多容纳多少个令牌）。
   • tokens：当前桶中剩余的令牌数量。
2. 每次请求到来时，从令牌桶中获取令牌。
   • 如果令牌数量大于0，则可以处理请求，将令牌数量减1。
   • 如果令牌数量等于0，则无法处理请求。
3. 定时往令牌桶中添加令牌，直到桶满为止。

Java代码实现：

public class TokenBucket {

    private final int rate; // 令牌产生速率，单位 token/s
    private final int burst; // 令牌桶大小，单位 token
    private volatile int tokens = 0; // 当前令牌数量
    private volatile long lastRefillTime = System.currentTimeMillis(); // 上次添加令牌的时间，单位 ms

    public TokenBucket(int rate, int burst) {
        this.rate = rate;
        this.burst = burst;
    }

    public synchronized boolean tryAcquire() {
        refillTokens(); // 先补充令牌
        if (tokens > 0) {
            tokens--;
            return true; // 获取令牌成功
        } else {
            return false; // 获取令牌失败
        }
    }

    private void refillTokens() {
        long now = System.currentTimeMillis();
        if (now > lastRefillTime) { // 计算上次添加令牌到现在的时间间隔
            long interval = (now - lastRefillTime) / 1000; // 转换为秒
            int newTokens = (int) Math.min(burst, tokens + interval * rate); // 计算新添加的令牌数
            tokens = newTokens;
            lastRefillTime = now;
        }
    }
}

漏桶算法

漏桶算法是一种固定容量的水桶，其出水口的流速是固定的。请求按照固定速率被处理，多余的请求会被丢弃。

具体实现方法：

1. 定义一个容量固定的桶（漏桶），包含以下属性：
   • capacity：桶的大小（最多能存储多少个请求）。
   • rate：请求处理速率，每秒处理多少个请求。
   • queue：存储请求的队列。
2. 请求到来时，先将其加入队列。
3. 定时从队列中取出请求进行处理，每秒最多处理 rate 个请求。

Java代码实现：

public class LeakyBucket {

    private final int capacity; // 漏桶容量，单位 requests
    private final int rate; // 处理速率，单位 requests/s
    private final Queue<Long> queue = new LinkedList<>(); // 存储请求的队列

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        startLeaking();
    }

    public synchronized boolean tryAcquire() {
        if (queue.size() < capacity) { // 判断桶是否已满
            queue.offer(System.currentTimeMillis());
            return true; // 加入队列成功
        } else {
            return false; // 加入队列失败
        }
    }

    private void startLeaking() {
        newThread(() -> {
            while (true) {
                synchronized (LeakyBucket.this) {
                    if (!queue.isEmpty()) {
                        long requestTime = queue.poll();
                        long now = System.currentTimeMillis();
                        long interval = now - requestTime;
                        if (interval < 1000) { // 检查请求是否过早
                            try {
                                Thread.sleep(1000 - interval);
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                    }
                }
                try {
                    Thread.sleep(1000 / rate); // 控制处理速率
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
    }
}

令牌桶算法 vs 漏桶算法

• 令牌桶算法是基于令牌生产速率进行限流，对于瞬时突发流量能够有一定的容许度；漏桶算法是基于固定的流出速率进行限流，对于瞬时突发流量无法承受。
• 令牌桶算法中，若令牌桶充满后再也不会产生令牌，因此允许突发流量。而在漏桶算法中，无法处理大量超过流出速率的流量而导致丢失请求。
• 令牌桶算法可以较为精确地控制请求的速率，但相应的代码实现也更加复杂。漏桶算法实现简单，但是无法处理突发流量，因此需要根据具体场景选择合适的算法。

操作步骤

1. 安装JDK和Maven。
2. 创建一个新的Java项目，并添加依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.0-jre</version>
</dependency>

1. 在项目中创建TokenBucket和LeakyBucket类，并实现对应的限流算法。
2. 在主函数中进行测试，例如：

public static void main(String[] args) {
    TokenBucket tokenBucket = new TokenBucket(10, 20);
    for (int i = 0; i < 100; i++) {
        if (tokenBucket.tryAcquire()) {
            System.out.println("处理请求 " + i);
        } else {
            System.out.println("丢弃请求 " + i);
        }
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

输出示例：

处理请求 0
处理请求 1
处理请求 2
处理请求 3
处理请求 4
处理请求 5
处理请求 6
处理请求 7
处理请求 8
处理请求 9
丢弃请求 10
...

结束语

以上介绍了令牌桶算法和漏桶算法两种常见的限流算法，并提供了Java代码实现。在实践过程中，需要根据具体场景进行选择和优化，以实现最佳的限流效果。