场景设计：设计一个分布式限流器，采用令牌桶算法，漏桶算法、滑动窗口算法实现
目录
1. 令牌桶算法实现
设计思路
代码实现
2. 漏桶算法实现
设计思路
代码实现
3. 滑动窗口算法实现
设计思路
代码实现
测试代码示例
依赖引入
总结
以下将分别使用令牌桶算法、漏桶算法和滑动窗口算法来设计并实现一个分布式限流器的 Java 版本，同时借助 Redis 来实现分布式状态的存储与同步。
1. 令牌桶算法实现
设计思路
令牌桶算法中，系统以固定速率向令牌桶中添加令牌，每个请求需要从令牌桶中获取一个或多个令牌才能被处理。若令牌桶中没有足够的令牌，请求将被拒绝。
代码实现
java
import redis.clients.jedis.Jedis;
public class TokenBucketRateLimiter {
private static final String REDIS_KEY = "token_bucket_rate_limiter";
private final Jedis jedis;
private final int capacity;
private final double rate;
private static final String LUA_SCRIPT =
"local key = KEYS[1] " +
"local tokensNeeded = tonumber(ARGV[1]) " +
"local capacity = tonumber(ARGV[2]) " +
"local rate = tonumber(ARGV[3]) " +
"local now = tonumber(ARGV[4]) " +
"local lastUpdate = tonumber(redis.call('hget', key, 'last_update')) " +
"local tokens = tonumber(redis.call('hget', key, 'tokens')) " +
"local elapsedTime = now - lastUpdate " +
"local newTokens = math.min(capacity, tokens + elapsedTime * rate) " +
"if newTokens >= tokensNeeded then " +
" redis.call('hset', key, 'tokens', newTokens - tokensNeeded) " +
" redis.call('hset', key, 'last_update', now) " +
" return 1 " +
"else " +
" redis.call('hset', key, 'tokens', newTokens) " +
" redis.call('hset', key, 'last_update', now) " +
" return 0 " +
"end";
public TokenBucketRateLimiter(String host, int port, int capacity, double rate) {
this.jedis = new Jedis(host, port);
this.capacity = capacity;
this.rate = rate;
initialize();
}
private void initialize() {
jedis.hset(REDIS_KEY, "tokens", String.valueOf(capacity));
jedis.hset(REDIS_KEY, "last_update", String.valueOf(System.currentTimeMillis() / 1000));
}
public boolean allowRequest(int tokensNeeded) {
Object result = jedis.eval(LUA_SCRIPT, 1, REDIS_KEY, String.valueOf(tokensNeeded),
String.valueOf(capacity), String.valueOf(rate), String.valueOf(System.currentTimeMillis() / 1000));
return (Long) result == 1;
}
public void close() {
jedis.close();
}
}
2. 漏桶算法实现
设计思路
漏桶算法中，请求像水一样流入漏桶，漏桶以固定的速率处理请求。如果桶满了，多余的请求将被丢弃。
代码实现
java
import redis.clients.jedis.Jedis;
public class LeakyBucketRateLimiter {
private static final String REDIS_KEY = "leaky_bucket_rate_limiter";
private final Jedis jedis;
private final int capacity;
private final double rate;
private static final String LUA_SCRIPT =
"local key = KEYS[1] " +
"local now = tonumber(ARGV[1]) " +
"local capacity = tonumber(ARGV[2]) " +
"local rate = tonumber(ARGV[3]) " +
"local lastUpdate = tonumber(redis.call('hget', key, 'last_update')) " +
"local water = tonumber(redis.call('hget', key, 'water')) " +
"local elapsedTime = now - lastUpdate " +
"local leakedWater = math.min(water, elapsedTime * rate) " +
"local newWater = math.max(0, water - leakedWater) " +
"if newWater + 1 <= capacity then " +
" redis.call('hset', key, 'water', newWater + 1) " +
" redis.call('hset', key, 'last_update', now) " +
" return 1 " +
"else " +
" redis.call('hset', key, 'water', newWater) " +
" redis.call('hset', key, 'last_update', now) " +
" return 0 " +
"end";
public LeakyBucketRateLimiter(String host, int port, int capacity, double rate) {
this.jedis = new Jedis(host, port);
this.capacity = capacity;
this.rate = rate;
initialize();
}
private void initialize() {
jedis.hset(REDIS_KEY, "water", "0");
jedis.hset(REDIS_KEY, "last_update", String.valueOf(System.currentTimeMillis() / 1000));
}
public boolean allowRequest() {
Object result = jedis.eval(LUA_SCRIPT, 1, REDIS_KEY, String.valueOf(System.currentTimeMillis() / 1000),
String.valueOf(capacity), String.valueOf(rate));
return (Long) result == 1;
}
public void close() {
jedis.close();
}
}
3. 滑动窗口算法实现
设计思路
滑动窗口算法将时间划分为固定大小的窗口，统计每个窗口内的请求数量。如果请求数量超过了阈值，则拒绝新的请求。
代码实现
java
import redis.clients.jedis.Jedis;
public class SlidingWindowRateLimiter {
private static final String REDIS_KEY_PREFIX = "sliding_window_rate_limiter:";
private final Jedis jedis;
private final int windowSize;
private final int limit;
public SlidingWindowRateLimiter(String host, int port, int windowSize, int limit) {
this.jedis = new Jedis(host, port);
this.windowSize = windowSize;
this.limit = limit;
}
public boolean allowRequest() {
long currentTime = System.currentTimeMillis();
String key = REDIS_KEY_PREFIX + (currentTime / (windowSize * 1000));
// 移除窗口外的请求记录
jedis.zremrangeByScore(key, 0, currentTime - windowSize * 1000);
// 添加当前请求记录
jedis.zadd(key, currentTime, String.valueOf(currentTime));
// 设置过期时间
jedis.expire(key, windowSize);
// 统计窗口内的请求数量
long count = jedis.zcard(key);
return count <= limit;
}
public void close() {
jedis.close();
}
}
测试代码示例
java
public class RateLimiterTest {
public static void main(String[] args) {
// 令牌桶算法测试
TokenBucketRateLimiter tokenBucketRateLimiter = new TokenBucketRateLimiter("localhost", 6379, 100, 10);
for (int i = 0; i < 20; i++) {
if (tokenBucketRateLimiter.allowRequest(1)) {
System.out.println("Token Bucket: Request " + i + " is allowed.");
} else {
System.out.println("Token Bucket: Request " + i + " is denied.");
}
}
tokenBucketRateLimiter.close();
// 漏桶算法测试
LeakyBucketRateLimiter leakyBucketRateLimiter = new LeakyBucketRateLimiter("localhost", 6379, 100, 10);
for (int i = 0; i < 20; i++) {
if (leakyBucketRateLimiter.allowRequest()) {
System.out.println("Leaky Bucket: Request " + i + " is allowed.");
} else {
System.out.println("Leaky Bucket: Request " + i + " is denied.");
}
}
leakyBucketRateLimiter.close();
// 滑动窗口算法测试
SlidingWindowRateLimiter slidingWindowRateLimiter = new SlidingWindowRateLimiter("localhost", 6379, 10, 5);
for (int i = 0; i < 20; i++) {
if (slidingWindowRateLimiter.allowRequest()) {
System.out.println("Sliding Window: Request " + i + " is allowed.");
} else {
System.out.println("Sliding Window: Request " + i + " is denied.");
}
}
slidingWindowRateLimiter.close();
}
}
依赖引入
如果你使用 Maven 项目，需要在 pom.xml 中添加 Jedis 依赖：
xml
<dependency>
<groupId>redis.clients</groupId>
<artifactId>jedis</artifactId>
<version>3.7.0</version>
</dependency>
总结
通过上述代码，我们分别实现了基于令牌桶算法、漏桶算法和滑动窗口算法的分布式限流器。不同的算法适用于不同的场景，你可以根据实际需求选择合适的算法。同时，借助 Redis 实现了分布式状态的存储和同步，确保多个服务实例能够共享限流状态。