面试题：Redis多维度限流规则实现的基础思路

Question

请阐述在Redis中实现多维度限流规则的基本思路，比如基于哪些数据结构和操作来记录请求信息并实现限流逻辑。

Answer 1

基于滑动窗口算法实现多维度限流

1. 数据结构
   • 有序集合（Sorted Set）：用于记录请求的时间戳。例如，以时间戳为分数，请求标识（如用户ID、请求IP等）为成员。这样可以根据时间戳对请求进行排序，方便计算滑动窗口内的请求数量。
   • 哈希表（Hash）：用来记录每个维度（如用户ID、IP等）的请求计数。哈希表的键可以是维度标识，值为该维度在当前窗口内的请求数量。
2. 操作步骤
   • 请求到达时：
     • 首先，向有序集合中添加当前请求的时间戳和请求标识。例如，使用ZADD命令，ZADD key [NX|XX] [CH] [INCR] score member [score member ...]，其中key是有序集合的键，score为当前时间戳，member为请求标识。
     • 然后，从哈希表中获取对应维度的当前请求计数。如果哈希表中不存在该维度的记录，则初始化为1；否则，将计数加1。使用HGET和HSET命令，HGET key field获取计数，HSET key field value更新计数。
   • 限流判断：
     • 根据滑动窗口的大小，计算窗口的起始时间戳。例如，窗口大小为60秒，当前时间戳为now，则起始时间戳为now - 60。
     • 使用ZCOUNT命令统计有序集合中在窗口时间范围内的请求数量，ZCOUNT key min max，其中min为起始时间戳，max为当前时间戳。如果统计的请求数量超过了设定的限流阈值，则进行限流处理（如返回错误信息、拒绝请求等）。
     • 同时，检查哈希表中记录的请求计数是否与有序集合中统计的数量一致（由于删除过期请求等操作可能导致不一致），如果不一致则进行调整。
   • 清理过期请求：
     • 定期（如每隔一定时间间隔）删除有序集合中过期的请求记录。可以使用ZREMRANGEBYSCORE命令，ZREMRANGEBYSCORE key min max，其中min为负无穷，max为当前时间减去窗口大小，从而删除窗口外的过期请求。同时，相应地更新哈希表中的计数。

基于令牌桶算法实现多维度限流

1. 数据结构
   • 哈希表（Hash）：用于记录每个维度（如用户ID、IP等）的令牌桶状态。哈希表的键为维度标识，值可以是一个包含令牌桶容量、当前令牌数量、上次更新时间等信息的结构体。例如，值可以是一个JSON字符串，如{"capacity":100, "tokens":100, "last_update":1600000000}。
2. 操作步骤
   • 请求到达时：
     • 从哈希表中获取对应维度的令牌桶状态。使用HGET命令获取。
     • 根据上次更新时间，计算从上次更新到现在应该生成的令牌数量，按照令牌桶的生成速率进行计算。例如，令牌生成速率为每秒10个，上次更新时间为t1，当前时间为t2，则生成的令牌数量为(t2 - t1) * 10。将生成的令牌数量累加到当前令牌数量中，但不能超过令牌桶的容量。
     • 如果当前令牌数量大于等于1，则表示有足够的令牌处理请求，将当前令牌数量减1，处理请求；否则，进行限流处理（如返回错误信息、拒绝请求等）。
     • 更新哈希表中的令牌桶状态，包括当前令牌数量和上次更新时间，使用HSET命令。

基于漏斗算法实现多维度限流

1. 数据结构
   • 哈希表（Hash）：类似令牌桶算法，用于记录每个维度（如用户ID、IP等）的漏斗状态。哈希表的键为维度标识，值是一个包含漏斗容量、剩余空间、漏水速率等信息的结构体。例如，值可以是{"capacity":100, "left_space":100, "leaking_rate":10}。
2. 操作步骤
   • 请求到达时：
     • 从哈希表中获取对应维度的漏斗状态。使用HGET命令。
     • 根据上次更新时间和漏水速率，计算从上次更新到现在漏斗漏出的空间大小。例如，漏水速率为每秒10个单位空间，上次更新时间为t1，当前时间为t2，则漏出的空间为(t2 - t1) * 10。将漏出的空间加到剩余空间中，但不能超过漏斗的容量。
     • 如果剩余空间大于等于请求所需的空间（通常一个请求占用一个单位空间），则表示可以处理请求，将剩余空间减去请求所需空间；否则，进行限流处理（如返回错误信息、拒绝请求等）。
     • 更新哈希表中的漏斗状态，包括剩余空间和上次更新时间，使用HSET命令。