Redis中ZSet数据结构与滑动窗口应用实现

目录

• Redis ZSET 数据存储机制
• SkipList + Hashtable
• ZipList
• 数据一致性
• 跳跃表（Skip List）详解
• 基本概念
• 数据结构实现
• 关键特性
• 为什么选择跳跃表？
• ZSET中与哈希表的协作
• Redis ZSET 实现滑动时间窗口限流
• 关键步骤
• 代码实现（Spring Boot）
• 使用示例

Redis 的 ZSET（有序集合） 是一种结合了 哈希表 phkHLxBFTz和 跳跃表（Skip List） 的混合数据结构，既能实现 O(1) 复杂度的成员存在性判断，又能以 O(logN) 复杂度维护有序性。

Redis ZSET 数据存储机制

ZSET 有两种实现机制：

SkipList + HashTable

数据实际上是同时存在于两个数据结构中的

跳表（SkipList）

• 按 score 排序存储 member
• 支持范围查询（ZRANGE 等命令）
• 维护成员的有序性

哈希表（HashTable）

• 存储 member -> score 的映射
• 用于快速判断成员是否存在（O(1) 复杂度）
• 直接获取成员的分数（ZSCORE 命令）

ZipList

ZipList：对于小型有序集合（元素少且 member 小），Redis 会使用 ziplist 编码来节省内存，只有当元素数量或大小超过阈值时才会转换为真正的跳跃表+哈希表实现。

• 按 (元素, score) 对顺序存储

数据一致性

Redis 通过保证所有写操作（ZADD/ZREM等）都同时更新这两个数据结构来维护一致性。当添加一个新成员时：

1. 会先将其添加到哈希表中
2. 然后插入到跳跃表的正确位置

跳跃表（Skip Lipythonst）详解

基本概念

跳跃表是一种概率平衡的数据结构，它通过维护多级索引来提高有序链表的查找效率。它结合了链表和类似二分查找的特性。

数据结构实现

Redis 中跳跃表的核心定义（简化版）：

typedef struct zskiplistNode {
    robj *member;          // 成员对象（如字符串）
    double score;          // 分数（用于排序）
    struct zskiplistNode *backward; // 后退指针（双向链表）
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span;  // 跨度（用于计算排名）
    } level[];             // 柔性数组，表示节点的层级
} zskiplistNode;
 
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;  // 节点数量
    int level;            // 当前最大层数
} zskiplist;

关键特性

层级随机生成：

• 新节点的层数由随机算法决定（幂次定律）
• Redis 中最大层数为 32

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

查找操作：

• 从最高层开始查找
• 如果当前节点的值小于目标值，则继续前进
• 否则下降一层继续查找
• 时间复杂度：O(logN)

插入操作：

• 先查找插入位置
• 随机生成新节点的层数
• 更新各层指针
• 时间复杂度：O(logN)

删除操作：

• 类似插入的逆过程
• 时间复杂度：O(logN)

为什么选择跳跃表？

Redis 选择跳跃表而非平衡树（如红黑树）的主要原因：

• 实现简单：不需要复杂的旋转操作
• 范围查询高效：底层链表天然有序，便于范围操作
• 并发友好：更容易实现无锁并发
• 平均性能好：虽然最坏情况不如平衡树，但实际表现优异

ZSET中与哈希表的协作

当执行 ZADD 命令时：

• 先在哈希表中查找/更新 member-score 映射
• 然后在跳跃表中插入/更新节点
• 保证两个操作的原子性

这种双数据结构设计使得 ZSET 能够：

• 快速判断成员是否存在（哈希表）
• 高效执行范围查询（跳跃表）
• 支持丰富的有序集合操作

Redis ZSET 实现滑动时间窗口限流

Redis ZSET除了实现排行榜之类的排序功能，还能根据拥有排序的特性，简单的实现滑动时间窗口限流功能。

关键步骤

• 清理旧数据：ZREMRANGEBYSCORE key -inf (currentTime - Windowsize)
• 统计当前请求数：ZCARD key
• 检查是否超限：比较当前计数与阈值
• 记录新请求：ZADD key currentTime uniqueId
• 设置过期时间：EXPIRE key windowSize + buffer

代码实现（Spring Boot）

import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.stereotype.Component;
 
import Java.util.Collections;
import java.util.UUID;
 
@Component
public class SlidingWindowLimiter {
    
    private final RedisTemplate<String, String> redisTemplate;
    
    // Lua脚本（原子操作）
    private static final String LUA_SCRIPT = 
        "local key = KEYS[1]\n" +
        "local now = tonumber(ARGV[1])\n" +
        "local window = tonumber(ARGV[2])\n" +
        "local maxRequests = tonumber(ARGV[3])\n" +
        "local requestId = ARGV[4]\n" +
       android "\n" +
        "-- 1. 移除窗口外的旧数据\n" +
        "redis.call('ZREMRANGEBYSCORE', key, 0, now - window)\n" +
        "\n" +
        "-- 2. 获取当前请求数\n" +
        "local count = redis.call('ZCARD', key)\n" +
        "\n" +
        "-- 3. 检查是否超限\n" +
        "if count >= maxRequests then\n" +
        "    return 0\n" +
        "end\n" +
        "\n" +
        "-- 4. 记录本次请求\n" +
        "redis.call('ZADD', key, now, requestId)\n" +
        "\n" +
        "-- 5. 刷新过期时间\n" +
        "redis.call('EXPIRE', key, window/1000 + 10)\n" +
        "return 1";
 
    public SlidingWindowLimiter(RedisTemplate<String, String> redisTemplate) {
        this.redisTemplate = redisTemplate;
    }
 
    /**
     * 检查请求是否允许通过
     * @param key 限流键（如 user_123:api_pay）
     * @param windowMillis 窗口大小（毫秒）
     * @param maxRequests 窗口内允许的最大请求数
     * @return true=允许, false=限流
     */
    public boolean allowRequest(String key, long windowMillis, int maxRequests) {
        // 构造Redis Key
        String redisKey = "rate_limit:" + key;
        
        // 准备脚本参数
        long currentTime = System.currentTimeMillis();
        String requestId = UUID.randomUUID().toString();http://www.devze.com
        
        // 执行Lua脚本
        DefaultRedisScript<Long> script = new DefaultRedisScript<>(LUA_SCRIPT, Long.class);
        Long result = redisTemplate.execute(
            script,
            Collections.singletonList(redisKey),
            currentTime, windowMillis, maxRequests, requestId
        );
        
        return result != null && result == 1;
    }
}

使用示例

@RestController
public class PaymentController {
    
    @Autowired
    private SlidingWindowLandroidimiter limiter;
    
    @PostMapping("/pay")
    public ResponseEntity<?> createPayment(@RequestBody PaymentRequest request) {
        // 构造限流键: 用户ID + 接口名
        String key = "user_" + request.getUserId() + ":payment";
        
        // 检查限流: 每用户每分钟最多10次支付
        if (!limiter.allowRequest(key, 60000, 10)) {
            return ResponseEntity.status(429).body("请求过于频繁");
        }
        
        // 执行业务逻辑
        paymentService.process(request);
        return ResponseEntity.ok("支付成功");
    }
}

到此这篇关于Redis中ZSet数据结构与滑动窗口应用的文章就介绍到这了,更多相关Redis ZSet滑动窗口内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！