基于Redis的三种限流算法解析与应用

常见限流算法

固定窗口算法

在固定的时间窗口下进行计数，达到阈值就拒绝请求。固定窗口如果在窗口开始就打满阈值，窗口后半部分进入的请求都会拒绝。

滑动窗口算法

在固定窗口的基础上，窗口会随着时间向前推移，可以在时间内平滑控制流量，解决固定窗口出现的突发流量问题。

漏斗算法

请求来了先进入漏斗，漏斗以恒定的速率放行请求。

令牌桶算法

在令牌桶中，以恒定的速率放入令牌，令牌桶也有一定的容量，如果满了令牌就无法放进去了。拿到令牌的请求通过，并消耗令牌，如果令牌桶中令牌为空，则会丢弃该请求。

Redis实现滑动窗口算法

Redis常用的限流算法，如果是秒级的，可以简单看做滑动窗口，如果不是秒级，则是固定窗口

local maxCount = KEYS[1]
local expireTime = KEYS[2]
local rkey = KEYS[3]
local count = redis.call('get', rkey)

if count then
if tonumber(count) < tonumber(maxCount) then
    redis.call('incr', rkey)
    return 1
else
    return 0
  end
else
  redis.call('set', rkey, '1')
  redis.call('expire', rkey, tonumber(expireTime))
return 1
end

复制

那如何利用Redis，实现一个简单的滑动窗口限流的功能？

❝

因为滑动窗口和时间有关，所以很容易能想到要基于时间进行统计。那么我们只需要在每一次有请求进来的时候，记录下请求的时间戳和请求的数据，然后在统计窗口内请求的数量时，只需要统计窗口内的被记录的数据量有多少条就行了。

在Redis中，我们可以基于ZSET来实现这个功能。假如我们限定认证接口一分钟只能调用50次。

那么，我们就可以把这个需要做限流的资源名作为key在redis中进行存储，然后value我们采用ZSET这种数据结构，把他的score设置为当前请求的时间戳，member的话建议用请求的详情的hash进行存储（或者UUID、MD5什么的），避免在并发时，时间戳一致出现scode和memberv一样导致被zadd幂等的问题。所以，我们实现滑动窗口限流的主要思想是：只保留在特定时间窗口内的请求记录，而丢弃窗口之外的记录。

主要步骤如下：

• 定义滑动窗口的时间范围，例如，窗口大小为60秒。
• 每次收到一个请求时，我们就定义出一个zset然后存储到redis中。
• 然后再通过ZREMRANGEBYSCORE命令来删除分值小于窗口起始时间戳（当前时间戳-60s）的数据。
• 最后，再使用ZCARD命令来获取有序集合中的成员数量，即在窗口内的请求量。

public boolean allowRequest(String key) {
        当前时间戳
        long currentTime = System.currentTimeMillis();
        窗口开始时间是当前时间减60s
        long windowStart = currentTime - 60 * 1000;
        删除窗口开始时间之前的所有数据
        jedis.zremrangeByScore(key, "-inf", String.valueOf(windowStart));
        计算总请求数
        long currentRequests = jedis.zcard(key);
     //窗口足够则把当前请求加入
        if (currentRequests < limit) {
            jedis.zadd(key, currentTime, String.valueOf(currentTime));
            returntrue;
        }
        returnfalse;
}

复制

public boolean allowRequest(String key) {
         当前时间戳
        long currentTime = System.currentTimeMillis();
         窗口开始时间是当前时间减60秒
        long windowStart = currentTime - 60 * 1000;
         删除窗口开始时间之前的所有数据
        redisTemplate.opsForZSet().removeRangeByScore(key, Double.NEGATIVE_INFINITY, windowStart);
         计算总请求数
        Long currentRequests = redisTemplate.opsForZSet().zCard(key);    
         窗口足够则把当前请求加入
        if (currentRequests < limit) {
            redisTemplate.opsForZSet().add(key, String.valueOf(currentTime), currentTime);
            returntrue;
        }
        returnfalse;
}

复制

在高并发情况下，以上代码可能会存在原子性的问题，需要考虑加事务或者lua脚本

public boolean allowRequest(String key) {
     当前时间戳
    long currentTime = System.currentTimeMillis();

     使用Lua脚本来确保原子性操作
    String luaScript = "local window_start = ARGV[1] - 60000\n" +
                       "redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', window_start)\n" +
                       "local current_requests = redis.call('ZCARD', KEYS[1])\n" +
                       "if current_requests < tonumber(ARGV[2]) then\n" +
                       "    redis.call('ZADD', KEYS[1], ARGV[1], ARGV[1])\n" +
                       "    return 1\n" +
                       "else\n" +
                       "    return 0\n" +
                       "end";
    Object result = jedis.eval(luaScript, 1, key, String.valueOf(currentTime), String.valueOf(limit));       
    return (Long) result == 1;
}

复制

public boolean allowRequest(String key) {
   // 当前时间戳
    long currentTime = System.currentTimeMillis();

     使用Lua脚本来确保原子性操作
    String luaScript = "local window_start = ARGV[1] - 60000\n" +
            "redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', window_start)\n" +
            "local current_requests = redis.call('ZCARD', KEYS[1])\n" +
            "if current_requests < tonumber(ARGV[2]) then\n" +
            "    redis.call('ZADD', KEYS[1], ARGV[1], ARGV[1])\n" +
            "    return 1\n" +
            "else\n" +
            "    return 0\n" +
            "end";
//        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
//        //读取 lua 脚本
//        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limit.lua")));
//        redisScript.setResultType(Long.class);

    Long result = redisTemplate.execute(new DefaultRedisScript<>(luaScript, Long.class),
            Collections.singletonList(key),
            String.valueOf(currentTime), String.valueOf(limit));      
    return result == 1;
}

复制

❝

ZREMRANGEBYSCORE key min max
命令用于移除有序集中，指定分数（score）区间内的所有成员，-inf
代表负无穷，+inf
代表正无穷

扩展

实际开发过程，可以结合AOP实现 ，为此我们必须自定义注解，然后根据注解参数，来个性化的控制限流

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface RateLimitAspect {
    **
     * 时间窗口, 单位秒
     * @return
     */
    int time() default 60;

    **
     * 允许请求数
     * @return
     */
    int count() default 100;
}


@Aspect
@Component
public class ApiRateLimitAspect {

    @Before("@annotation(RateLimitAspect)")
    public void beforeMethod(JoinPoint joinPoint, RateLimitAspect rateLimitAspect) {
        / 获取注解参数
        String value = rateLimitAspect.value();
        System.out.println("Annotation value: " + value);

        // 其他业务逻辑...
    }
}

复制

令牌桶法

• 初始化令牌桶大小和放令牌的速率。
• 使用Redis的Lua脚本实现原子操作，保证线程安全。
• 判断是否有足够令牌满足请求。

local key = KEYS[1] -- 令牌桶的最大容量
local capacity = tonumber(ARGV[1]) -- 每次请求消耗的令牌数，通常为 1
local tokens = tonumber(ARGV[2]) -- 当前的时间戳，用作计算时间差的基础
local now = tonumber(ARGV[3])
local refillTime = tonumber(ARGV[4]) -- 每次令牌桶完全填充之间的时间间隔（以秒为单位）

local currentTokens = tonumber(redis.call("get", key)) or capacity
local lastRefillTime = tonumber(redis.call("get", key .. ":time")) or now

local timeElapsed = now - lastRefillTime
local refillTokens = math.floor(timeElapsed / refillTime)

currentTokens = math.min(capacity, currentTokens + refillTokens)
if currentTokens > 0 then
    redis.call("set", key, currentTokens - 1)
    redis.call("set", key .. ":time", now)
    return 1
else
    return 0
end

复制

最后

每种方法都有其适用场景和优缺点。固定窗口限流简单易实现，但可能存在边界问题；滑动窗口限流更精确，但实现复杂度和性能要求更高；令牌桶算法能够精确控制流量，支持突发流量，但实现最为复杂。选择合适的限流方案，可以有效地保护系统不受流量冲击，提高系统的可用性和用户体验。

在实际应用中，需要根据业务特点和流量分布选择合适的限流策略。例如，对于需要严格速率控制的API服务，令牌桶算法可能是更好的选择；而对于相对简单的应用，固定窗口限流可能已经足够。此外，限流策略的调整也是一个动态的过程，需要根据系统的运行情况和业务需求进行调整。