限流算法¶

固定窗口（Fixed-window）¶

固定窗口算法将时间分割成固定长度的窗口，在每个窗口中计算请求次数。如果请求次数超过了设定的阈值，后续请求将被拒绝。该算法易于实现，并且针对DDOS攻击有效，但可能会限制合法用户。

• 适用场景：限制合法用户，如购买流量包或API调用次数包
• 问题：在窗口切换的瞬间可能会有两倍于限制的请求被允许，即“窗口切换”问题。
• Redis实现：
• 每个时间窗作为一个key-value计数器，使用当前时间作为key的一部分，并设置过期时间
• 每次请求时用INCR加一，并检查是否超过限制

local key = KEYS[1]
local requests = tonumber(redis.call('GET', key) or '-1')
local max_requests = tonumber(ARGV[1])
local expiry = tonumber(ARGV[2])

if (requests == -1) or (requests < max_requests) then
  redis.call('INCR', key)
  redis.call('EXPIRE', key, expiry)
  return false
else
  return true
end

滑动窗口（Sliding-window）¶

滑动窗口算法将一个大的时间窗口分成多个小窗口，每次大窗口向后滑动一个小窗口，并保证大的窗口内流量不会超出最大值，这种实现比固定窗口的流量曲线更加平滑。它是固定窗口的一种改进，但从根本上并没有真正解决固定窗口算法的临界突发流量问题。

• 适用场景：限制合法用户，如购买流量包或API调用次数包，适用于需要更精细控制请求分布的场景
• 问题：依然存在单倍峰值问题，导致请求被拒绝。且实现相对复杂，需要更多的存储来追踪滑动窗口。
• Redis实现：
• 使用一个sorted set作为时间窗，每次请求时将当前时间作为元素放入set中
• 移除窗口外的元素，再查看set的大小是否超过限制

local current_time = redis.call('TIME')
local trim_time = tonumber(current_time[1]) - tonumber(ARGV[2])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, trim_time)
local request_count = redis.call('ZCARD',KEYS[1])

if request_count < tonumber(ARGV[3]) then
    redis.call('ZADD', KEYS[1], current_time[1])
    redis.call('EXPIRE', KEYS[1], ARGV[2])
    return true
end
return false

漏桶（Leaky Bucket）¶

想象有一个木桶，桶的容量是固定的。当有请求到来时先放到木桶中，处理请求的worker以固定的速度从木桶中取出请求进行相应。如果木桶已经满了，直接返回请求频率超限的错误码或者页面。

• 适用场景：以严格速率保护系统资源
• 问题：在高流量下，令牌桶可能很快被耗尽，导致请求被拒绝，也导致获得令牌的请求产生高延迟。
• Redis实现：
• TBD

令牌桶（Token Bucket）¶

想象有一个木桶，桶的容量是固定的。以恒定的速度往木桶里加入令牌，木桶满了则不再加入令牌。服务收到请求时尝试从木桶中取出一个令牌，如果能够得到令牌则继续执行后续的业务逻辑。如果没有得到令牌，直接返回访问频率超限的错误码或页面等，不继续执行后续的业务逻辑。令牌桶兼备窗口和漏桶的功能，即既可以恒定速率限流的同时又可以应对一定的突发流量。

• 适用场景：应对突发流量峰值同时保护系统资源
• 问题：在高流量下，令牌桶可能很快被耗尽，导致请求被拒绝。
• Redis实现：
• TBD

参考信息¶

• https://developer.redis.com/develop/java/spring/rate-limiting/fixed-window/reactive-lua/
• https://developer.redis.com/develop/dotnet/aspnetcore/rate-limiting/sliding-window/
• https://www.cnblogs.com/ciel717/p/16180017.html