Redis数据类型内部实现机制详解

高级

需要数据结构和缓存系统基础知识

1. 术语定义

Redis(Remote Dictionary Server,远程字典服务器Redis的全称,表明它是一个基于网络的键值对存储系统)是一个开源的、基于内存的数据结构存储系统,可用作数据库、缓存和消息中间件。Redis支持多种数据类型,每种数据类型都有其独特的内部实现机制,这些实现机制直接影响着Redis的性能特性和适用场景。

核心数据类型

  • String(字符串):最基本的数据类型
  • List(列表):有序的字符串集合
  • Hash(哈希):字段-值对的集合
  • Set(集合):无序的唯一字符串集合
  • Sorted Set(有序集合):带分数的有序唯一字符串集合

扩展数据类型

  • Bitmap(位图):处理位操作的特殊字符串
  • HyperLogLog:用于估计集合基数的概率数据结构
  • Geo(地理位置):存储地理坐标和计算地理距离
  • Stream(流):用于消息队列的新数据类型

2. 实现细节与优化

Redis对象系统

Redis内部使用一个名为redisObject(Redis对象)Redis中所有值都使用redisObject表示,包含类型、编码方式、引用计数等信息的结构体来表示所有的键值对,这种设计允许Redis根据数据特征灵活选择内部编码方式。

typedef struct redisObject {
    unsigned type:4;      // 类型:字符串、列表、哈希等
    unsigned encoding:4;  // 编码方式:取决于type和数据特征
    unsigned lru:24;      // LRU信息或LFU数据
    int refcount;         // 引用计数
    void *ptr;            // 指向实际数据结构的指针
} robj;

String(字符串)实现

Redis的字符串是使用简单动态字符串(SDS, Simple Dynamic String)Redis自己实现的字符串结构,比C字符串更安全高效实现的,而不是C语言的原生字符串。SDS具有以下特性:

  • 二进制安全:可以存储任何二进制数据,不仅限于文本
  • 预分配空间:减少频繁内存分配
  • 惰性空间释放:避免频繁释放内存
  • O(1)时间复杂度获取字符串长度
struct sdshdr {
    int len;       // 已使用的字节数
    int free;      // 剩余可用字节数
    char buf[];    // 字符数组,柔性数组成员
};

Redis 3.2版本后,SDS结构进行了优化,根据字符串长度使用不同的结构体(sdshdr5/8/16/32/64),以节省内存。

List(列表)实现

Redis的列表数据类型在不同版本有不同实现:

  • Redis 3.2之前:使用压缩列表(ziplist)一种紧凑的、内存高效的双向链表实现双向链表(linkedlist)传统的双向链表实现,每个节点都是单独的内存分配两种结构
  • Redis 3.2之后:引入了QuickList结合了ziplist和linkedlist的优点,是ziplist的双向链表结构,将多个ziplist连接起来,平衡了内存使用和访问效率

QuickList是ziplist和linkedlist的混合体,每个quicklist节点包含一个ziplist,适合存储中等长度的列表。

typedef struct quicklist {
    quicklistNode *head;  // 头节点
    quicklistNode *tail;  // 尾节点
    unsigned long count;  // 所有ziplist中的总元素数
    unsigned int len;     // quicklist节点数量
    int fill : 16;        // ziplist大小限制
    unsigned int compress : 16; // 压缩深度设置
} quicklist;

Hash(哈希)实现

Redis哈希表的内部实现根据数据量和元素大小使用两种不同的编码:

  • 当哈希表元素较少且元素值较小时,使用压缩列表(ziplist)按照key1, value1, key2, value2...的顺序存储
  • 当元素增多或元素值变大,会转换为字典(dict)基于哈希表实现的字典结构,支持O(1)复杂度的查找结构
typedef struct dict {
    dictType *type;       // 字典类型函数
    void *privdata;       // 私有数据
    dictht ht[2];         // 哈希表数组,用于rehash
    long rehashidx;       // rehash索引,-1表示未进行rehash
    unsigned long iterators; // 当前正在使用的迭代器数量
} dict;

Redis使用渐进式rehash将rehash操作分散到多次请求中,避免一次性rehash带来的性能问题技术,在字典扩容或缩容时,将rehash操作分散到多次请求中进行,减少单次操作的时间复杂度。

Set(集合)实现

Redis的集合类型有两种内部编码:

  • 当集合中的元素都是整数且元素数量较少时,使用整数集合(intset)专门用于存储整数值的有序数组结构
  • 当包含非整数元素或元素数量较多时,使用字典(dict)这里的dict只使用key部分,value统一设为NULL,此时value字段为NULL
typedef struct intset {
    uint32_t encoding;    // 编码方式:INTSET_ENC_INT16/32/64
    uint32_t length;      // 元素数量
    int8_t contents[];    // 实际存储数据的数组
} intset;

整数集合会根据存储的整数范围自动升级编码(如从16位升级到32位),但不会降级,这是一种内存与性能的权衡。

Sorted Set(有序集合)实现

Redis的有序集合是最复杂的数据类型之一,根据数据规模使用不同的实现:

  • 元素较少时:使用压缩列表(ziplist)按照member1, score1, member2, score2...的顺序存储
  • 元素较多时:使用跳跃表(skiplist)一种可以快速查找的数据结构,平均查找复杂度为O(logN)字典(dict)用于O(1)复杂度查找成员的组合
  • Redis 5.0后引入了listpackziplist的改进版本,解决了一些边缘情况下的问题替代ziplist
typedef struct zset {
    dict *dict;           // 字典,用于O(1)查找成员
    zskiplist *zsl;       // 跳跃表,用于有序访问
} zset;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点
    unsigned long length;                // 节点数量
    int level;                          // 当前最大层数
} zskiplist;

跳跃表是有序集合的核心,它通过在链表上增加多级索引来加速查找,平均查找复杂度为O(logN),接近平衡树,但实现更简单。

3. 应用场景

String应用场景

  • 缓存HTML片段或页面
  • 计数器(使用INCR/DECR命令)
  • 分布式锁(使用SETNX命令)
  • 会话缓存
# 使用String实现计数器
SET pageviews 0
INCR pageviews
GET pageviews  # 返回"1"

# 使用String实现分布式锁
SETNX lock:resource_name unique_value
# 业务逻辑...
DEL lock:resource_name

List应用场景

  • 消息队列(使用LPUSH/RPOP或RPUSH/LPOP)
  • 最新动态(如朋友圈、微博)
  • 任务队列
# 使用List实现简单消息队列
LPUSH tasks "task1"
LPUSH tasks "task2"
# 消费者获取任务
RPOP tasks  # 返回"task1"

Hash应用场景

  • 存储对象数据(用户信息、商品信息等)
  • 购物车
  • 配置信息存储
# 使用Hash存储用户信息
HMSET user:1000 username "张三" email "[email protected]" age 28
HGET user:1000 username  # 返回"张三"
HGETALL user:1000  # 获取所有字段和值

Set应用场景

  • 标签系统
  • 唯一性检查
  • 共同好友、共同关注
  • 随机抽奖
# 使用Set实现标签系统
SADD article:1:tags "Redis" "数据库" "NoSQL"
SMEMBERS article:1:tags  # 获取所有标签

# 查找共同关注
SINTER user:1:following user:2:following

Sorted Set应用场景

  • 排行榜
  • 优先级队列
  • 延迟队列
  • 带权重的搜索
# 使用Sorted Set实现排行榜
ZADD leaderboard 100 "player1"
ZADD leaderboard 85 "player2"
ZADD leaderboard 95 "player3"
# 获取前三名
ZREVRANGE leaderboard 0 2 WITHSCORES

扩展数据类型应用

  • Bitmap:用户活跃度统计、布隆过滤器
  • HyperLogLog:UV统计(网站访问量)
  • Geo:附近的人、商店等地理位置应用
  • Stream:消息队列、事件流处理
# 使用Bitmap记录用户每天登录情况
SETBIT user:1:login:2023 0 1  # 1月1日登录
SETBIT user:1:login:2023 1 0  # 1月2日未登录
BITCOUNT user:1:login:2023  # 统计登录天数

4. 比较分析

数据类型 内部编码 时间复杂度 优点 缺点
String int, embstr, raw O(1) 内存占用小,操作简单高效 功能相对简单
List ziplist, quicklist O(1)头尾操作,O(N)随机访问 有序,支持双向操作 随机访问效率低
Hash ziplist, dict O(1)单字段操作,O(N)全字段操作 存储结构化数据,节省空间 不支持嵌套
Set intset, dict O(1)添加/删除/判断,O(N)遍历 唯一性保证,集合运算 无序性,不支持权重
Sorted Set ziplist, skiplist+dict O(logN)添加/删除/更新,O(N)范围查询 有序性,支持范围查询 内存占用较高,操作复杂度较高

内存优化策略对比

graph TD A[Redis内存优化策略] --> B[共享对象] A --> C[编码优化] A --> D[压缩数据结构] A --> E[内存淘汰策略] B --> B1[整数对象池] C --> C1[int编码的String] C --> C2[ziplist编码的集合类型] C --> C3[intset编码的Set] D --> D1[ziplist] D --> D2[quicklist] D --> D3[listpack] E --> E1[LRU] E --> E2[LFU] E --> E3[Random] E --> E4[TTL]

数据类型选择决策树

graph TD Start[需要存储什么] --> A{是否需要结构化数据} A -->|否| B{是否需要有序} A -->|是| C[使用Hash] B -->|否| D{是否需要唯一性} B -->|是| E{是否需要权重分数} D -->|否| F[使用String] D -->|是| G[使用Set] E -->|否| H[使用List] E -->|是| I[使用Sorted Set]
graph TD Start[数据存储需求] --> A{是简单值还是复杂数据} A -->|简单值| B{是否需要原子递增/递减} A -->|复杂数据| C{是否需要字段-值对} B -->|是| B1[使用String + INCR/DECR] B -->|否| B2{是否是二进制数据} B2 -->|是| B3[使用String] B2 -->|否| B4{是否需要位操作} B4 -->|是| B5[使用Bitmap] B4 -->|否| B3 C -->|是| C1[使用Hash] C -->|否| D{是否需要有序集合} D -->|是| E{是否需要按分数排序} D -->|否| F{是否需要唯一性} E -->|是| E1[使用Sorted Set] E -->|否| E2[使用List] F -->|是| F1[使用Set] F -->|否| F2{是否需要队列操作} F2 -->|是| F3[使用List] F2 -->|否| F4{是否需要计算集合基数} F4 -->|是| F5[使用HyperLogLog] F4 -->|否| F6{是否存储地理位置} F6 -->|是| F7[使用Geo] F6 -->|否| F8{是否需要消息队列} F8 -->|是| F9[使用Stream] F8 -->|否| F10[根据具体需求选择]

5. 总结

核心要点

mindmap root((Redis数据类型)) String ::icon(fa fa-font) SDS实现 二进制安全 预分配空间 List ::icon(fa fa-list) QuickList结构 双向链表 适合队列 Hash ::icon(fa fa-hashtag) ziplist/dict 渐进式rehash 适合存储对象 Set ::icon(fa fa-th-large) intset/dict 唯一性保证 集合运算 Sorted Set ::icon(fa fa-sort) skiplist+dict 分数排序 范围查询

常见问题与解决方案

问题:Redis内存占用过高

解决方案:

  • 使用更紧凑的数据结构(如ziplist代替普通链表)
  • 设置合理的maxmemory和淘汰策略
  • 使用Redis 4.0+的内存优化功能
  • 对大key进行拆分

问题:Redis性能下降

解决方案:

  • 避免使用复杂度高的命令(如KEYS)
  • 合理设置数据过期时间
  • 使用Pipeline减少网络往返
  • 避免大量数据同时过期
  • 监控并优化慢查询

问题:数据类型选择困难

解决方案:

  • 明确业务需求和访问模式
  • 考虑数据量大小和增长趋势
  • 权衡内存占用和操作复杂度
  • 参考上述决策树进行选择

最佳实践

数据结构选择

  • 根据数据访问模式选择合适的数据类型
  • 利用Redis的特殊编码优化内存使用
  • 避免使用过于复杂的数据结构

键设计

  • 使用有意义的前缀,如"user:1000:profile"
  • 避免过长的键名
  • 使用冒号分隔多级键名

内存管理

  • 设置合理的maxmemory限制
  • 使用适当的淘汰策略(如volatile-lru)
  • 定期清理过期数据

性能优化

  • 使用Pipeline和Multi/Exec减少网络往返
  • 避免使用O(N)复杂度的命令处理大数据集
  • 合理使用Lua脚本减少网络交互

6. 参考资料

中文资源

英文资源