生产环境常见的限流算法
在高并发场景下，为了保护系统的稳定性和可用性，需要对请求进行限流。本文介绍几种生产环境中常见的限流算法，并结合Java代码实现。
令牌桶算法
令牌桶算法是一种基于固定时间间隔补充令牌的算法，其核心思想是通过令牌桶来控制请求的访问速率。
具体实现方法：
- 定义一个令牌桶，包含以下属性：
- rate：每秒产生多少个令牌。
- burst：桶的大小（最多容纳多少个令牌）。
- tokens：当前桶中剩余的令牌数量。
- 每次请求到来时，从令牌桶中获取令牌。
- 如果令牌数量大于0，则可以处理请求，将令牌数量减1。
- 如果令牌数量等于0，则无法处理请求。
- 定时往令牌桶中添加令牌，直到桶满为止。
Java代码实现：
代码语言：javascript复制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;
}
}
}漏桶算法
漏桶算法是一种固定容量的水桶，其出水口的流速是固定的。请求按照固定速率被处理，多余的请求会被丢弃。
具体实现方法：
- 定义一个容量固定的桶（漏桶），包含以下属性：
- capacity：桶的大小（最多能存储多少个请求）。
- rate：请求处理速率，每秒处理多少个请求。
- queue：存储请求的队列。
- 请求到来时，先将其加入队列。
- 定时从队列中取出请求进行处理，每秒最多处理 rate 个请求。
Java代码实现：
代码语言：javascript复制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 漏桶算法
- 令牌桶算法是基于令牌生产速率进行限流，对于瞬时突发流量能够有一定的容许度；漏桶算法是基于固定的流出速率进行限流，对于瞬时突发流量无法承受。
- 令牌桶算法中，若令牌桶充满后再也不会产生令牌，因此允许突发流量。而在漏桶算法中，无法处理大量超过流出速率的流量而导致丢失请求。
- 令牌桶算法可以较为精确地控制请求的速率，但相应的代码实现也更加复杂。漏桶算法实现简单，但是无法处理突发流量，因此需要根据具体场景选择合适的算法。
操作步骤
- 安装JDK和Maven。
- 创建一个新的Java项目，并添加依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.0-jre</version>
</dependency>- 在项目中创建TokenBucket和LeakyBucket类，并实现对应的限流算法。
- 在主函数中进行测试，例如：
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();
}
}
}输出示例：
代码语言：javascript复制处理请求 0
处理请求 1
处理请求 2
处理请求 3
处理请求 4
处理请求 5
处理请求 6
处理请求 7
处理请求 8
处理请求 9
丢弃请求 10
...结束语
以上介绍了令牌桶算法和漏桶算法两种常见的限流算法，并提供了Java代码实现。在实践过程中，需要根据具体场景进行选择和优化，以实现最佳的限流效果。
