面试题：Redis多维度限流中如何基于滑动窗口算法实现限流

Question

在Redis多维度限流场景下，假设要对某个API的访问频率进行限制，请描述如何利用Redis实现滑动窗口限流算法，包括数据结构的选择、主要实现步骤以及该算法相较于固定窗口算法的优势。

Answer 1

数据结构选择

1. 有序集合（Sorted Set）：用于记录每个请求的时间戳。有序集合的score字段可以存储时间戳，member字段可以存储请求的唯一标识（如请求ID）。这样可以方便地根据时间范围进行查询和统计。
2. 字符串（String）：用于记录当前窗口内的请求计数。可以使用一个键值对，键为API的标识，值为当前窗口内的请求数量。

主要实现步骤

1. 初始化：
   • 设定窗口大小 windowSize（例如，60秒）和最大请求数 maxRequests。
   • 创建一个有序集合键，例如 api:request:timestamps，用于存储请求时间戳。
   • 创建一个字符串键，例如 api:request:count，初始值设为0，用于记录当前窗口内的请求数量。
2. 请求到达时：
   • 获取当前时间戳 currentTimestamp。
   • 将 currentTimestamp 作为score，请求唯一标识作为member添加到有序集合 api:request:timestamps 中。
   • 使用 ZREMRANGEBYSCORE 命令删除有序集合中时间戳小于 currentTimestamp - windowSize 的元素，这些元素已经超出了当前滑动窗口。
   • 使用 ZCARD 命令获取当前有序集合的元素数量，即当前窗口内的请求数量 currentCount。
   • 判断 currentCount 是否大于 maxRequests。如果 currentCount <= maxRequests，则允许请求通过，并将 api:request:count 的值更新为 currentCount；否则，拒绝请求。

滑动窗口算法相较于固定窗口算法的优势

1. 平滑限流：
   • 固定窗口算法：存在临界问题。例如，窗口大小为1分钟，允许100次请求。如果在第59秒突然有100次请求，然后在第60秒到第61秒又有100次请求，实际上在这2秒内有200次请求，超过了预期的限流。
   • 滑动窗口算法：通过不断滑动窗口，将时间窗口细化，能够更平滑地处理请求，避免临界问题。例如，将1分钟的窗口划分为多个小窗口（如10秒一个小窗口），即使在窗口切换时也能准确统计请求数量，不会出现请求突增导致的限流失效。
2. 更精确的限流控制：
   • 固定窗口算法：只能以固定的窗口粒度进行限流，无法精确到更小的时间单位。
   • 滑动窗口算法：可以根据实际需求设置非常小的时间窗口粒度，从而实现更精确的限流控制，更符合复杂业务场景的需求。