Redis有序集合(Sorted Set)实现原理

▶Redis核心
- ▶数据结构
- ▶内存管理
  - 内存分配策略
  - 淘汰算法
▶持久化
- ▶RDB机制
  - 快照生成原理
  - 文件格式解析
- ▶AOF机制
  - 命令追加策略
  - 重写过程分析
▶高可用
- ▶主从复制
  - SYNC原理
  - 增量复制
- ▶哨兵机制
  - 故障检测
  - 领导选举
▶高级特性
- ▶事务系统
  - ACID实现
  - WATCH原理
- ▶Lua脚本
  - 沙盒环境
  - 执行管道
▶实战问题
- ▶缓存问题
- ▶数据一致性
  - 读写一致性
  - 双写一致性
- ▶性能优化
  - 大key处理
  - 热点key优化

发布时间: 2025-03-22 10:37

↑

# Redis有序集合(Sorted Set)实现原理

## 引言

Redis有序集合是一个有序的字符串集合，每个成员都关联了一个分数，通过分数来为集合中的成员进行从小到大的排序。本文将深入探讨Redis有序集合的实现原理、内部编码方式以及实际应用场景。

## 底层实现

### 跳跃表（skiplist）

Redis有序集合的主要实现之一是跳跃表，它提供了一个有序的数据结构，并且支持快速的插入和查找：

```c
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode {
    sds ele;                    // 成员对象
    double score;               // 分值
    struct zskiplistNode *backward;  // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned long span;             // 跨度
    } level[];                  // 层
} zskiplistNode;
```

### 跳跃表的特点

1. **多层链表**
   - 每个节点包含多个层
   - 每层都有一个指向后续节点的指针
   - 层数随机生成，最高32层

2. **查找过程**
   ```c
   // 在跳跃表中查找分值为score的节点
   zskiplistNode *zslFind(zskiplist *zsl, double score) {
       zskiplistNode *x = zsl->header;
       // 从最高层开始查找
       for (int i = zsl->level-1; i >= 0; i--) {
           while (x->level[i].forward &&
                  x->level[i].forward->score < score)
               x = x->level[i].forward;
       }
       x = x->level[0].forward;
       return x;
   }
   ```

### 字典（Dict）

为了支持O(1)复杂度的成员查找，有序集合同时使用了字典结构：

```c
typedef struct zset {
    dict *dict;         // 字典，保存成员到分值的映射
    zskiplist *zsl;    // 跳跃表，保存所有成员
} zset;
```

## 内部编码

Redis有序集合有两种内部编码方式：

### 1. ziplist（压缩列表）

当有序集合的元素数量小于128个，且每个元素的值都小于64字节时，使用ziplist编码：

```redis
ZADD scores 89 "Alice" 67 "Bob"
```

### 2. skiplist（跳跃表）

当不满足ziplist的条件时，使用skiplist编码：

```redis
ZADD leaderboard 10000 "player1" 9999 "player2"
```

## 常用命令

### 基本操作

```redis
# 添加成员和分数
ZADD key score member [score member ...]

# 获取成员分数
ZSCORE key member

# 获取成员排名
ZRANK key member    # 从小到大排名
ZREVRANK key member # 从大到小排名

# 删除成员
ZREM key member [member ...]
```

### 范围操作

```redis
# 按分数范围获取成员
ZRANGEBYSCORE key min max [WITHSCORES]

# 按排名范围获取成员
ZRANGE key start stop [WITHSCORES]

# 获取指定分数范围的成员数量
ZCOUNT key min max
```

### 集合操作

```redis
# 交集
ZINTERSTORE destination numkeys key [key ...]

# 并集
ZUNIONSTORE destination numkeys key [key ...]
```

## 应用场景

### 1. 排行榜系统

```redis
# 记录玩家得分
ZADD leaderboard 1000 "player1" 2000 "player2" 3000 "player3"

# 获取前10名玩家
ZREVRANGE leaderboard 0 9 WITHSCORES

# 获取玩家排名
ZREVRANK leaderboard "player1"
```

### 2. 权重队列

```redis
# 添加带权重的任务
ZADD tasks 10 "task1" 20 "task2" 5 "task3"

# 获取最高优先级的任务
ZRANGE tasks -1 -1

# 处理完成后删除任务
ZREM tasks "task1"
```

### 3. 延迟队列

```redis
# 添加延迟任务，score为执行时间戳
ZADD delayed_queue 1735689600 "task1" 1735776000 "task2"

# 获取到期的任务
ZRANGEBYSCORE delayed_queue 0 $(date +%s)
```

### 4. 实时计数器

```redis
# 记录用户访问次数
ZINCRBY hourly_stats $(date +%s) 1 "user:1001"

# 获取一小时内的访问统计
ZRANGEBYSCORE hourly_stats $(expr $(date +%s) - 3600) $(date +%s)
```

## 性能优化

### 1. 内存优化

- 合理使用ziplist编码
- 及时清理过期数据
- 控制成员数量

```redis
# 获取有序集合的基数
ZCARD key

# 删除指定排名范围的成员
ZREMRANGEBYRANK key start stop
```

### 2. 查询优化

- 使用LIMIT限制返回结果
- 避免获取大范围数据
- 合理使用WITHSCORES选项

```redis
# 使用LIMIT优化分页查询
ZRANGEBYSCORE key -inf +inf WITHSCORES LIMIT 0 10
```

### 3. 批量操作

优先使用批量命令：

```redis
# 优先使用
ZADD myset 1 "a" 2 "b" 3 "c"

# 而不是多次
ZADD myset 1 "a"
ZADD myset 2 "b"
ZADD myset 3 "c"
```

## 注意事项

1. **内存管理**
   - 注意大数据量时的内存占用
   - 合理设置ziplist配置
   - 避免存储过大的成员

2. **分数设计**
   - 分数可以是整数或双精度浮点数
   - 相同分数的成员按字典序排序
   - 分数范围：-inf到+inf

3. **并发操作**
   - 单个命令是原子的
   - 多个命令需要使用事务
   - 注意ZINTERSTORE等操作的原子性

4. **性能考虑**
   - 添加和删除的时间复杂度为O(log(N))
   - 按分数查找的时间复杂度为O(log(N))
   - 集合运算的时间复杂度较高

## 总结

Redis有序集合通过跳跃表和字典的结合，实现了高效的有序数据结构。它在排行榜、延迟队列等场景中有广泛应用。通过合理使用各种命令和优化策略，可以充分发挥有序集合的性能优势。在使用时需要注意内存管理、分数设计和并发操作等问题，根据实际需求选择合适的使用方式。

元素码农