限流算法笔记

我们为什么需要限流？

防止恶意攻击、保障系统稳定、应对秒杀等高并发场景

有哪些常见的限流算法？

固定窗口，滑动窗口，漏桶，令牌桶

固定窗口，缺点：比如

限流阀值为5个请求，单位时间窗口是1s，如果我们在单位时间内的前0.8-1s和1-1.2s，分别并发5个请求。虽然都没有超过阀值，但是如果算0.8-1.2s内的，则并发数高达10，已经超过单位时间1s不超过5阀值的定义了。

当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

-- 滑动窗口限流脚本（Redis 7 兼容：所有新变量均使用 local，避免写全局表导致 readonly 错误）
local key = KEYS[1]
local window = tonumber(ARGV[1]) -- 秒
local limit = tonumber(ARGV[2])
local now = tonumber(ARGV[3]) -- 毫秒

if not window or not limit or not now then
  return redis.error_reply("Invalid input parameters")
end

-- 计算窗口起点（毫秒）
local after = now - window * 1000
-- 清理窗口外数据
redis.call('ZREMRANGEBYSCORE', key, 0, after)
-- 当前窗口内请求数量
local current = redis.call('ZCARD', key)
if current < limit then
  -- 使用一个局部自增序列来避免随机数（随机会导致不可重复性，影响复制与集群）
  local seqKey = key .. ':seq'
  local seq = redis.call('INCR', seqKey)
  -- 保证序列键生命周期不超过窗口
  if seq == 1 then
    redis.call('PEXPIRE', seqKey, window * 1000)
  end
  local member = now .. '-' .. seq
  redis.call('ZADD', key, now, member)
  redis.call('PEXPIRE', key, window * 1000) -- 用毫秒精度保持一致
  return current + 1
else
  return 0
end

Q：为什么滑动窗口算法用ZSet，TreeMap等结构？

A：排序基准是时间戳：

在 Lua 脚本中，ZSet 的 score 就是请求发生时的毫秒时间戳。
TreeMap 的 key 也是请求发生时的时间戳。
这个特性是实现“滑动”的基础，因为它让我们可以轻易地识别出哪些请求是“旧的”。

能够高效地清除掉过期的、不再窗口内的数据。

TreeMap 是单机内存的实现方式，适用于单体应用；而 ZSet 是分布式的实现方式，适用于微服务或集群环境。

漏桶：

在网络通信中常用于流量整形，可以很好地解决平滑度问题
缺点需要对请求进行缓存，会增加服务器的内存消耗。对于流量波动比较大的场景，需要较为灵活的参数配置才能达到较好的效果。
无法应对突发流量

令牌桶：

Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。

稳定性高：令牌桶算法可以控制请求的处理速度，可以使系统的负载变得稳定。精度高：令牌桶算法可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流。弹性好：令牌桶算法可以处理突发流量，可以在短时间内提供更多的处理能力，以处理突发流量。

但是较为复杂。

参考： https://www.nowcoder.com/discuss/552987164095557632

【动画学Redis分布式限流算法，面试必考，令牌桶、漏桶、计数器、滑动窗口你学会了吗？】 https://www.bilibili.com/video/BV1BH4y1g7ad/?share_source=copy_web&vd_source=4d36ad70083da21a644325f824406c76