
1. 固定窗口(Fixed Window)
原理:
- 固定窗口算法将时间划分为固定的时间段(窗口),比如 1 秒、1 分钟等。在每个时间段内,允许最多一定数量的请求。如果请求超出配额,则拒绝。
优点:
缺点:
- 在窗口边界处可能出现流量突增的情况(称为“边界效应”),比如两个窗口交界处可能短时间内允许通过的请求数量翻倍。
Lua脚本:
local current = redis.call('GET', KEYS[1])
if current and tonumber(current) >= tonumber(ARGV[1]) then
return 0
else
current = redis.call('INCR', KEYS[1])
if tonumber(current) == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[2])
end
return 1
end
Java模拟限流:
package com.strap.common.redis.demo;
import lombok.SneakyThrows;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPoolConfig;
public class FixedWindowExample {
private static final String LIMIT_SCRIPT =
"-- KEYS[1]: 限流的键(通常为用户ID或者API)\n" +
"-- ARGV[1]: 最大允许请求数\n" +
"-- ARGV[2]: 窗口时间(以秒为单位)\n" +
"\n" +
"local current = redis.call('GET', KEYS[1])\n" +
"\n" +
"if current and tonumber(current) >= tonumber(ARGV[1]) then\n" +
" return 0 -- 返回0表示超出限流\n" +
"else\n" +
" current = redis.call('INCR', KEYS[1])\n" +
" if tonumber(current) == 1 then\n" +
" redis.call('EXPIRE', KEYS[1], ARGV[2]) -- 设置窗口时间\n" +
" end\n" +
" return 1 -- 返回1表示未超限\n" +
"end";
@SneakyThrows
public static void main(String[] args) {
JedisPoolConfig config = new JedisPoolConfig();
config.setBlockWhenExhausted(true);
try (Jedis jedis = new Jedis("127.0.0.1", 6379)) {
for (int i = 0; i < 100; i++) {
Thread.sleep(100);
Object o = jedis.eval(LIMIT_SCRIPT, 1, "FixedWindowExample", "10", "5");
if (Long.valueOf(1).equals(o)) {
System.out.println(i + "=============================放行");
} else {
System.out.println(i + "拦截=============================");
}
}
}
}
}
2. 滑动窗口(Sliding Window)
原理:
- 滑动窗口改进了固定窗口的“边界效应”问题,它通过更细粒度的时间单位来平滑地控制请求。滑动窗口可以在较短的时间窗口内动态调整请求计数,防止瞬时流量激增。
优点:
缺点:
Lua脚本:
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[3] - ARGV[1] * 1000)
local count = redis.call('ZCARD', KEYS[1])
if tonumber(count) >= tonumber(ARGV[2]) then
return 0
else
redis.call('ZADD', KEYS[1], ARGV[3], ARGV[3])
redis.call('EXPIRE', KEYS[1], ARGV[1])
return 1
end
Java模拟限流:
package com.strap.common.redis.demo;
import lombok.SneakyThrows;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPoolConfig;
public class SlidingWindowExample {
private static final String LIMIT_SCRIPT =
"-- KEYS[1]: 限流的键(通常为用户ID或者API)\n" +
"-- ARGV[1]: 时间窗口(秒)\n" +
"-- ARGV[2]: 最大允许请求数\n" +
"-- ARGV[3]: 当前时间戳(毫秒)\n" +
"\n" +
"-- 移除窗口外的请求\n" +
"redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[3] - ARGV[1] * 1000)\n" +
"\n" +
"local count = redis.call('ZCARD', KEYS[1])\n" +
"\n" +
"if tonumber(count) >= tonumber(ARGV[2]) then\n" +
" return 0 -- 请求被限制\n" +
"else\n" +
" redis.call('ZADD', KEYS[1], ARGV[3], ARGV[3]) -- 添加当前请求的时间戳\n" +
" redis.call('EXPIRE', KEYS[1], ARGV[1]) -- 设置过期时间\n" +
" return 1 -- 请求允许\n" +
"end";
@SneakyThrows
public static void main(String[] args) {
JedisPoolConfig config = new JedisPoolConfig();
config.setBlockWhenExhausted(true);
try (Jedis jedis = new Jedis("127.0.0.1", 6379)) {
for (int i = 0; i < 100; i++) {
Thread.sleep(100);
long now = System.currentTimeMillis();
Object o = jedis.eval(LIMIT_SCRIPT, 1, "SlidingWindowExample", "5", "10", now + "");
if (Long.valueOf(1).equals(o)){
System.out.println(i + "=============================放行");
}else {
System.out.println(i + "拦截=============================");
}
}
}
}
}
3. 令牌桶(Token Bucket)
原理:
- 令牌桶算法以恒定速率向桶中添加令牌。每次请求需要消耗一定数量的令牌,如果桶内有足够的令牌,允许请求通过;否则拒绝请求。令牌可以积累,从而允许短时间内的流量突发。
优点:
- 允许短时间的流量突发,适用于需要应对高峰流量的场景。
缺点:
- 如果高峰流量持续时间较长,可能导致后续请求被大量拒绝。
Lua脚本:
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requestedTokens = tonumber(ARGV[4])
local expire = math.ceil(capacity / rate)
local currentTokens = tonumber(redis.call('HGET', key, 'currentTokens') or capacity)
local lastUpdate = tonumber(redis.call('HGET', key, 'last_update') or 0)
if lastUpdate == 0 then
redis.call('HSET', key, 'last_update', now)
redis.call('HSET', key, 'currentTokens', currentTokens)
redis.call('EXPIRE', key, expire)
else
local tokensToAdd = math.floor((now - lastUpdate) / 1000 * rate)
currentTokens = math.min(capacity, currentTokens + tokensToAdd)
end
local isAllow = 0
if currentTokens >= requestedTokens then
isAllow = 1
redis.call('HSET', key, 'last_update', now)
redis.call('HSET', key, 'currentTokens', currentTokens - requestedTokens)
redis.call('EXPIRE', key, expire)
end
return {isAllow, currentTokens}
Java模拟限流:
package com.strap.common.redis.demo;
import lombok.SneakyThrows;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPoolConfig;
import java.util.List;
public class TokenBucketExample {
private static final String LIMIT_SCRIPT = "-- 当前的键\n" +
"local key = KEYS[1]\n" +
"-- 令牌桶的容量\n" +
"local capacity = tonumber(ARGV[1])\n" +
"-- 令牌的生成速率(个/秒)\n" +
"local rate = tonumber(ARGV[2])\n" +
"-- 当前时间戳(毫秒)\n" +
"local now = tonumber(ARGV[3])\n" +
"-- 请求的令牌数量\n" +
"local requestedTokens = tonumber(ARGV[4])\n" +
"-- 键的最大生命周期\n" +
"local expire = math.ceil(capacity / rate)\n" +
"\n" +
"-- 获取当前桶内的令牌数量,默认为capacity\n" +
"local currentTokens = tonumber(redis.call('HGET', key, 'currentTokens') or capacity)\n" +
"-- 获取上次令牌更新的时间\n" +
"local lastUpdate = tonumber(redis.call('HGET', key, 'last_update') or 0)\n" +
"\n" +
"-- 首次进来初始化令牌数量\n" +
"if lastUpdate == 0 then\n" +
" redis.call('HSET', key, 'last_update', now)\n" +
" redis.call('HSET', key, 'currentTokens', currentTokens)\n" +
" redis.call('EXPIRE', key, expire)\n" +
"else\n" +
" -- 计算在当前时间段内生成的令牌数量\n" +
" local tokensToAdd = math.floor((now - lastUpdate) / 1000 * rate)\n" +
" currentTokens = math.min(capacity, currentTokens + tokensToAdd)\n" +
"end\n" +
"\n" +
"-- 计算当前是否能提供请求的令牌数量\n" +
"local isAllow = 0\n" +
"if currentTokens >= requestedTokens then\n" +
" isAllow = 1\n" +
" redis.call('HSET', key, 'last_update', now)\n" +
" redis.call('HSET', key, 'currentTokens', currentTokens - requestedTokens)\n" +
" redis.call('EXPIRE', key, expire)\n" +
"end\n" +
"\n" +
"return {isAllow, currentTokens}";
@SneakyThrows
public static void main(String[] args) {
JedisPoolConfig config = new JedisPoolConfig();
config.setBlockWhenExhausted(true);
try (Jedis jedis = new Jedis("127.0.0.1", 6379)) {
int rate = 1;
int capacity = 10;
int everyTime = 1;
for (int i = 0; i < 100; i++) {
Thread.sleep(100);
long now = System.currentTimeMillis();
Object o = jedis.eval(LIMIT_SCRIPT, 1, "TokenBucketExample", String.valueOf(capacity), String.valueOf(rate), String.valueOf(now), String.valueOf(everyTime));
List<Object> resutl = (List)o;
if (Long.valueOf(1).equals(resutl.get(0))){
System.out.println(i + "请求前桶内剩余令牌数:" + resutl.get(1) + "==============================放行");
}else {
System.out.println(i + "请求前桶内剩余令牌数:" + resutl.get(1) + "=拦截=============================");
}
}
}
}
}
4.漏桶(Leaky Bucket)
原理:
- 漏桶算法将请求流量放入一个“漏桶”中,桶以固定速率漏水(处理请求)。如果流量超过桶的容量,多余的请求将被拒绝。漏桶严格控制输出速率,因此不会出现流量突发。
优点:
缺点:
Lua脚本:
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requestedTokens = tonumber(ARGV[4])
local expire = math.ceil(capacity / rate)
local currentTokens = tonumber(redis.call('HGET', key, 'tokens') or 0)
local lastUpdate = tonumber(redis.call('HGET', key, 'last_update') or now)
local leaks = math.floor((now - lastUpdate) / 1000 * rate)
currentTokens = math.max(currentTokens - leaks + requestedTokens, 0)
local isAllow = 0
if currentTokens <= capacity then
isAllow = 1
redis.call('HSET', key, 'tokens', currentTokens)
redis.call('HSET', key, 'last_update', now)
redis.call('EXPIRE', key, expire);
end
return {isAllow, currentTokens}
Java模拟限流:
package com.strap.common.redis.demo;
import lombok.SneakyThrows;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPoolConfig;
import java.util.List;
public class LeakyBucketExample {
private static final String LIMIT_SCRIPT =
"-- 当前的键\n" +
"local key = KEYS[1]\n" +
"-- 漏桶的容量\n" +
"local capacity = tonumber(ARGV[1])\n" +
"-- 漏水速率(个/秒)\n" +
"local rate = tonumber(ARGV[2])\n" +
"-- 当前时间戳\n" +
"local now = tonumber(ARGV[3])\n" +
"-- 请求计数(进来的tokens数量)\n" +
"local requestedTokens = tonumber(ARGV[4])\n" +
"-- 键的最大生命周期\n" +
"local expire = math.ceil(capacity / rate)\n" +
"\n" +
"-- 获取当前漏桶内的令牌数量,默认为0\n" +
"local currentTokens = tonumber(redis.call('HGET', key, 'tokens') or 0)\n" +
"-- 获取上次漏桶令牌数量的更新时间\n" +
"local lastUpdate = tonumber(redis.call('HGET', key, 'last_update') or now)\n" +
"-- 漏桶在当前时间范围内已流出的令牌数\n" +
"local leaks = math.floor((now - lastUpdate) / 1000 * rate)\n" +
"-- 重新计算当前漏桶内的令牌数量 math.min(capacity, currentTokens + deltaTokens)\n" +
"currentTokens = math.max(currentTokens - leaks + requestedTokens, 0)\n" +
"-- 是否允许通过,默认不允许\n" +
"local isAllow = 0\n" +
"if currentTokens <= capacity then\n" +
" -- 当前令牌数量还能放进去\n" +
" isAllow = 1\n" +
" redis.call('HSET', key, 'tokens', currentTokens)\n" +
" redis.call('HSET', key, 'last_update', now)\n" +
" redis.call('EXPIRE', key, expire);\n" +
"end\n" +
"return {isAllow, currentTokens}";
@SneakyThrows
public static void main(String[] args) {
JedisPoolConfig config = new JedisPoolConfig();
config.setBlockWhenExhausted(true);
try (Jedis jedis = new Jedis("127.0.0.1", 6379)) {
int rate = 1;
int capacity = 10;
int everyTime = 1;
for (int i = 0; i < 100; i++) {
Thread.sleep(100);
long now = System.currentTimeMillis();
Object o = jedis.eval(LIMIT_SCRIPT, 1, "LeakyBucketExample", String.valueOf(capacity), String.valueOf(rate), String.valueOf(now), String.valueOf(everyTime));
List<Object> resutl = (List)o;
if (Long.valueOf(1).equals(resutl.get(0))){
System.out.println(i + "当前桶内令牌数:" + resutl.get(1) + "==============================放行");
}else {
System.out.println(i + "当前桶内令牌数:" + resutl.get(1) + "=拦截=============================");
}
}
}
}
}
算法对比
算法 | 工作机制 | 优点 | 缺点 | 使用场景 |
---|
固定窗口 | 固定时间窗口内计数 | 实现简单,快速判断 | 窗口边界可能导致流量突发(边界效应) | 简单的 API 限流,低要求的场景 |
滑动窗口 | 滑动时间窗口内计数 | 更精确地控制流量,减少流量突发 | 实现较复杂,较高的性能开销 | 动态限流场景,减少流量突增,如 API 网关 |
令牌桶 | 令牌以固定速率生成,请求消耗令牌 | 支持流量突发,且易于实现和理解 | 如果高峰流量持续时间过长,会导致后续请求被拒绝 | 适合支持突发流量的场景,如限速下载、API 限流 |
漏桶 | 固定速率处理请求,严格控制输出流量 | 严格控制流量,平滑输出 | 不允许流量突发 | 严格控制请求速率,如网络流量控制,负载均衡等 |
总结
- 固定窗口简单易用,适合对流量要求不高的场景。
- 滑动窗口平滑控制流量,适合对流量突发有一定需求但又希望平稳控制的场景。
- 令牌桶允许突发流量,适合需要高效处理短时流量高峰的应用。
- 漏桶严格控制请求速率,适合对平稳处理请求要求很高的场景。