这是一种用于限流（Rate Limiting）的算法，特别是在需要精确控制单位时间内请求次数的场景下。它能够严格保证在任何一段时间窗口内，请求都不会超过阈值。
-
核心思想
滑动日志算法的核心是记录每个请求的时间戳。当一个新的请求到来时，它会检查从当前时间点倒推一个时间窗口（例如1秒）内的所有请求数量（即“日志”）。如果这个数量已经达到了限制，就拒绝这个新请求；如果没有达到，就允许并通过，同时将这个新请求的时间戳也记录到日志中。 -
工作原理
我们通过一个例子来理解。假设我们的限流规则是：每秒最多允许2个请求。
初始化：我们维护一个列表（或队列）来存储请求的时间戳。初始时列表是空的。
logs = []
请求到来：
假设在 t=100ms 时，请求A到来。
计算时间窗口起点：current_time – window_size = 100ms – 1000ms = -900ms（这是一个很早的时间，意味着我们要看从过去到现在所有的记录）。
检查列表中在 [-900ms, 100ms] 这个时间窗口内的记录数量。目前只有它自己，数量为1 < 2。
允许通过。并将时间戳 100ms 加入到日志中。
logs = [100]
假设在 t=400ms 时，请求B到来。
时间窗口起点：400ms – 1000ms = -600ms。
检查 [-600ms, 400ms] 窗口内的记录：[100] 和 [400] 都在这个窗口内。数量为2。
允许通过（因为等于2，通常“不超过”包含等于，即允许第2个请求）。并将 400ms 加入日志。
logs = [100, 400]
假设在 t=500ms 时，请求C到来。
时间窗口起点：500ms – 1000ms = -500ms。
检查 [-500ms, 500ms] 窗口内的记录：[100] 不在这个窗口内（因为100 < 500-1000=-500? 不，100 > -500，所以在）。[100, 400, 500] 都在窗口内。
数量为3 > 2。
拒绝请求。日志保持不变。
logs = [100, 400]
假设在 t=1100ms 时，请求D到来。
时间窗口起点：1100ms – 1000ms = 100ms。
检查 [100ms, 1100ms] 窗口内的记录：[100] 刚好在起点上，算作在窗口内。[400] 和 [1100] 也在。
数量为3？别急，我们需要先清理过期日志。
一个关键操作：清理过期日志
在实际实现中，我们不会每次都从整个历史记录开始检查。为了提升效率，我们会在每次请求到来时，先清理掉那些早于当前时间窗口起点的日志。
对于请求D (t=1100ms)：
时间窗口起点是 100ms。
我们清理日志中所有 小于 100ms 的记录。100ms 这条记录等于起点，通常会被保留（因为它仍然在[100, 1100]这个区间内）。
清理后：logs = [100, 400]（因为 100 >= 100， 400 >= 100）。
现在检查窗口 [100ms, 1100ms] 内的记录数量：2。
2 <= 2，所以允许通过。并将 1100 加入日志。
logs = [100, 400, 1100]
- 算法流程总结
维护一个有序集合（如列表、队列或环形缓冲区）存储请求的时间戳。
当新请求到达时：
a. 获取当前时间 now。
b. 计算时间窗口的起始时间 window_start = now – window_size（例如 now – 1000 毫秒）。
c. 清理过期数据：从集合中删除所有时间戳 小于 window_start 的记录。
d. 检查计数：统计集合中剩余记录的数量 count。
e. 决策：
- 如果 count < limit：允许请求，并将 now 添加到集合中。
- 如果 count >= limit：拒绝请求。
- 优缺点
优点：
非常精确：它能保证在任何一段连续的时间窗口内，请求数都不会超过限制，边界情况处理得很好（例如上面例子中t=1100ms的请求和t=100ms的请求正好相隔1秒）。
平滑应对流量突发：由于它检查的是真实的滑动窗口，而不是固定的时间桶，所以对突发流量的处理比固定窗口算法更合理。
缺点：
消耗大量内存：如果限流阈值很大（例如每秒100万次请求），就需要存储100万个时间戳，这对内存是巨大的挑战。
计算开销大：每次请求都需要进行删除过期记录和计数的操作。如果日志很大，这个操作可能比较耗时。
- 实现优化
为了解决内存和性能问题，通常不会真的存储所有时间戳。常见的优化方案是使用Redis的Sorted Set（有序集合）来实现分布式限流。
Key：可以是用户的ID或API的名称。
Score：使用请求的时间戳（如Unix毫秒时间戳）。
Value：可以也存储时间戳，或者生成一个唯一值。
操作：
使用 ZREMRANGEBYSCORE 命令删除所有小于 (当前时间 – 时间窗口) 的成员。
使用 ZCARD 命令获取当前集合中的成员数量。
如果数量小于限制，则使用 ZADD 添加当前时间戳。
Redis Lua 脚本伪代码示例：
lua
local key = KEYS[1] — 限流的Key
local now = tonumber(ARGV[1]) — 当前时间戳
local window = tonumber(ARGV[2]) — 窗口大小，单位毫秒
local limit = tonumber(ARGV[3]) — 阈值
— 1. 清除过期日志
local window_start = now – window
redis.call(‘ZREMRANGEBYSCORE’, key, 0, window_start)
— 2. 获取当前日志数量
local count = redis.call(‘ZCARD’, key)
— 3. 判断是否超过限制
if count < limit then
— 4. 如果没超过，添加当前日志
redis.call(‘ZADD’, key, now, now) — 注意：这里Score和Value都用同一个时间戳，确保唯一性
— 5. 设置Key的过期时间，避免冷数据长期占用内存
redis.call(‘EXPIRE’, key, window/1000) — 过期时间设置为窗口大小（秒）
return true — 允许
end
return false — 拒绝
- 与其他限流算法对比
算法 原理 优点 缺点
固定窗口 将时间切分为多个窗口，每个窗口内计数。 实现简单，内存效率高。 窗口边界处可能出现双倍流量，不够平滑。
滑动窗口 是固定窗口的优化，将一个大窗口切分为多个小格子。 比固定窗口更平滑，一定程度上解决了边界问题。 精度和内存开销取决于格子数量，是权衡之策。
漏桶 以恒定速率处理请求，像一个漏水的桶。 输出流量非常平滑，整流效果最好。 无法应对突发流量（即使系统有空闲，请求也必须排队）。
令牌桶 以恒定速率生成令牌，请求需要拿到令牌才能通过。 允许一定程度的突发流量，是业界最常用的算法。 实现比固定窗口和漏桶稍复杂。
滑动日志 记录每个请求的时间点，检查滑动窗口内的总数。 最为精确，能严格保证限流效果。 内存和计算开销最大。
总结
滑动日志算法是一种精确但资源消耗较大的限流算法。它适用于需要极其精确控制流量、且流量规模不是特别巨大的场景（例如限制单个用户的重要操作频率）。在面对海量高并发请求时，通常会更倾向于使用令牌桶或滑动窗口算法作为折衷方案。