4. 常见限流算法（中）：滑动窗口日志算法原理、实现、优缺点

滑动窗口日志算法（Sliding Window Log Algorithm）是固定窗口算法的直接改进版本。它通过记录每个请求的时间戳日志，并维护一个动态滑动的“窗口”来统计请求数量，从而彻底解决了固定窗口算法在窗口边界处的流量突刺问题。

4.1 算法核心原理

滑动窗口日志算法的核心思想是：将时间视为连续流动的河流，而非离散的区块。系统为每个请求记录其到达的时间戳，并存储在一个有序集合（日志）中。当新请求到达时，算法会移除所有超出当前窗口范围（例如过去1秒）的旧时间戳，然后统计当前窗口内的有效请求数。

关键定义： 滑动窗口日志算法使用一个精确到毫秒的时间戳日志，窗口的起始点是动态的，始终以“当前时间 - 窗口大小”为左边界，以“当前时间”为右边界。

下图展示了滑动窗口日志算法的工作流程：

滑动窗口日志算法原理图 T₀ T₁ T₂ T₃ 滑动窗口（窗口大小 = T₂ - T₀） ✕ ✓ ✓ ✓ ✓ ✕ 算法执行步骤 1. 新请求到达，记录当前时间戳 T_new。 2. 从日志中移除所有时间戳 < T_new - 窗口大小的旧记录。 3. 统计日志中剩余时间戳数量 count。 4. 若 count < 阈值，则允许请求并记录；否则拒绝请求。 动态滑动

4.2 算法实现

以下是一个基于 Redis 有序集合（Sorted Set）的滑动窗口日志算法实现示例。Redis 的 ZSET 天然支持按分数（时间戳）排序和范围删除，是实现该算法的理想选择。

import time
import redis

class SlidingWindowLogRateLimiter:
    """
    基于 Redis Sorted Set 的滑动窗口日志限流器
    """
    def __init__(self, redis_client, key_prefix, window_size=1.0, max_requests=10):
        self.redis = redis_client
        self.key_prefix = key_prefix
        self.window_size = window_size  # 窗口大小，单位：秒
        self.max_requests = max_requests  # 窗口内最大请求数

    def _get_window_key(self, user_id):
        return f"{self.key_prefix}:{user_id}"

    def allow_request(self, user_id):
        now = time.time()
        window_start = now - self.window_size
        key = self._get_window_key(user_id)

        # 使用 Redis 管道保证原子性
        pipe = self.redis.pipeline()

        # 1. 移除窗口外的旧时间戳
        pipe.zremrangebyscore(key, 0, window_start)

        # 2. 统计当前窗口内的请求数
        pipe.zcard(key)

        # 3. 添加当前请求的时间戳
        pipe.zadd(key, {str(now): now})

        # 4. 设置过期时间，避免内存泄漏
        pipe.expire(key, int(self.window_size * 2))

        # 执行管道
        _, count, _, _ = pipe.execute()

        # 判断是否超过阈值
        if count < self.max_requests:
            return True
        else:
            # 如果拒绝，需要回滚刚才添加的时间戳
            self.redis.zrem(key, str(now))
            return False

# 使用示例
redis_client = redis.Redis(host='localhost', port=6379, db=0)
limiter = SlidingWindowLogRateLimiter(redis_client, "api:sliding", window_size=1.0, max_requests=5)

if limiter.allow_request("user_123"):
    print("请求通过")
else:
    print("请求被限流")
实现要点：
  • 原子性：务必使用 Redis 管道或 Lua 脚本保证“移除旧记录-统计-添加新记录”的原子操作，避免竞态条件。
  • 过期时间：为每个 key 设置 TTL（通常为窗口大小的 2 倍），防止长时间不活跃的用户残留大量无用数据。
  • 时间戳精度：使用毫秒级时间戳（time.time() * 1000）可以避免同一毫秒内多个请求的时间戳冲突。

4.3 优缺点分析

维度 说明
✅ 优点
  • 精确限流：窗口边界平滑连续，彻底消除固定窗口的“突刺”问题，限流精度达到毫秒级。
  • 细粒度控制：可以精确统计任意时间区间内的请求分布，适合对流量有严格要求的场景。
  • 易于理解：算法逻辑直观，与“滑动窗口”的物理概念一致，便于团队沟通和维护。
❌ 缺点
  • 内存开销大：需要为每个请求存储时间戳，在高并发场景下（如每秒数万请求），内存消耗会快速增长。
  • 清理开销：每次请求都需要执行一次范围删除操作，当窗口内积累大量旧记录时，清理操作可能成为性能瓶颈。
  • 分布式一致性：在分布式环境下，依赖 Redis 单点或集群的原子操作，网络延迟和时钟偏差可能影响精度。

4.4 与固定窗口算法的对比

为了更直观地理解滑动窗口日志算法的优势，下表将其与固定窗口算法进行对比：

对比维度 固定窗口算法 滑动窗口日志算法
窗口边界 固定时间点（如整秒、整分钟） 动态连续，以当前时间为右边界
边界突刺 存在，窗口切换时可突发 2 倍流量 不存在，流量平滑
内存占用 低，仅存储一个计数器 高，存储每个请求的时间戳
限流精度 窗口级别（秒/分钟） 毫秒级，精确到每个请求
实现复杂度 简单 中等，需处理日志清理和原子性
适用场景 对精度要求不高的简单限流 对流量平滑度要求高的核心 API

4.5 适用场景与避坑指南

避坑指南：
  • 不要用于超高频场景：如果单机 QPS 超过 10 万，滑动窗口日志的内存和清理开销会变得不可接受，此时应考虑滑动窗口计数器算法（下一节介绍）或令牌桶算法。
  • 注意 Redis 内存上限：每个时间戳约占用 40-50 字节（ZSET 结构开销），假设窗口大小为 1 秒、阈值为 1000，则每个活跃用户占用约 50KB。务必监控 Redis 内存使用量。
  • 时钟同步问题：在分布式部署中，不同节点的系统时钟偏差会导致窗口边界不一致。建议所有节点使用统一的 NTP 服务，或使用 Redis 单点的时间作为权威时间源。

推荐使用场景：

  • 对流量突发敏感的 API，如支付接口、下单接口。
  • 需要精确审计和计费的场景，如按 API 调用次数收费的 SaaS 服务。
  • 用户级别的细粒度限流，且用户数量在可接受范围内（如数千到数万活跃用户）。
← 上一章 📖 返回目录 下一章 →