《Redis设计与实现》数据结构与对象小记

h3l · 2020-03-09 13:50:10

---

本文是《Redis设计与实现》的数据结构与对象部分的流水账记录。建议先阅读该书。

数据结构

简单动态字符串(SDS, simple dynamic string)

用处：

• key
• value
• aof 缓冲区

特点：

• 可修改
• 可以直接返回长度
• 更安全
• 性能更高（空间预分配，惰性空间释放）

结构：

• int free，可用空间
• int len，字符串长度
• char buf[]，保存字符串

链表

用处：

• 列表
• 发布与订阅
• 慢查询
• 监视器

结构：

• ListNode
  • listNode * pre，前置节点
  • listNode * next，后置节点
  • void * value，值
• list
  • listNode * head，列表头
  • listNode * tail，列表尾
  • unsigned long len,列表长度

字典

依赖算法：使用 MurmurHash2 算法计算哈希值，速度快，分布随机

用处：

• 整个 redis 底层就使用字典
• hash

结构：

• dictht
  • dictEntry **table，哈希表数组
  • unsigned long size，哈希表大小，table 数组大小
  • unsigned long sizemask，哈希表大小掩码，用于计算索引，等于 size - 1
  • unsigned long used，已有节点数
• dictEntry
  • void *key, 键
  • union，值
  • dictEntry *next，指向下一个哈希表节点（解决冲突问题）
• dict
  • type，提供为特定类型的键值对的函数
  • private，传递给type中函数的特定参数
  • dictht ht[2],一般只用 ht[0], rehash 的使用会用 ht[1]
  • rehashidx, rehash 进度，没有 rehash 时为 -1

行为：

• 冲突，链表法解决冲突
• rehash
  • 渐进式 rehash
  • 负载计算：load_factor = ht[0].used / ht[0].size
  • rehash 时机：
    • 未执行 BGSAVE 或 BGREWRITEAOF并且负载大于等于1
    • 执行 BGSAVE 或 BGREWRITEAOF并且负载大于等于5
    • 负载小于 0.1 会收缩

跳跃表

特点：

• 实现简单
• 批量处理节点
• 平均时间复杂度 O(logN)，最坏 O(N)

用处：

• 有序集合
• 集群内部

结构：

• zskiplist
  • header 指向跳跃表表头
  • tail 指向跳跃表表尾
  • level 当前跳跃表层数
  • length 跳跃表长度，即其中元素个数
• zskiplistNode
  • 层（是一个数组，有多个层），是随机生成的
    • 包括前进指针和跨度（跨度用于计算排位（rank））
  • 后退指针
  • 分值
  • 成员对象

整数集合

用处：

• 整数类型的集合

结构：

• encoding 编码方式（决定 contents 中元素的类型）
• length 集合的元素
• contents 数组，保存集合的元素，有序排列

行为：

• 升级
  • 当向集合中添加新元素时，新元素类型比已有的类型都要长，会将已有元素的类型都变成新元素的类型
• 不支持降级

压缩列表

特点：

• 节约内存
• 连续内存

用处：

• 列表（少量列表项，并且列表项为短字符串或小整数）
• hash（少量键值对，键和值要么是短字符串要么是小整数）

结构：

• zl
  • zlbytes，4 字节，压缩列表占用的字节数
  • zltail，4 字节，表尾节点距起始点字节数
  • zllen，2 字节，节点数量
  • entryX，不定，节点列表
  • zlend，1字节，OxFF 标记结尾
• 节点
  • previous_entry_length，1或5字节，前置节点长度（5字节的时候使用 0xFE 作为开头），从后往前遍历
  • encoding
  • content

行为：

• 连锁更新

对象

包含

• 字符串对象
• 列表对象
• 哈希对象
• 集合对象
• 有序集合对象

对于 redis 保存的键值对来说，键总是一个字符串对象，而值则可能是上述任一。

特点：

• 根据场景选择底层实现
• 基于计数的内存回收

结构：

• type，类型
• encoding，编码
• ptr，指向底层数据结构的指针
• refcount，引用计数（OBJECT REFCOUNT key返回一个键被引用的次数）
• lru，记录最后被访问的时间（OBJECT IDLETIME key返回一个键多久没被访问）

字符串对象

编码：

• int
• raw（申请两次内存）
• embstr（申请一次内存，但是连续，不可修改）

列表对象

编码（底层实现方式）：

• ziplist
  • 在每个元素小于 64 字节，且列表长度小于 512 时使用压缩列表（可通过 list-max-ziplist-value 和 list-max-ziplist-entries配置）
• linkedlist

哈希对象

编码（底层实现方式）：

• ziplist
  • 每个键值对都小于 64 字节，且哈希键值数量小于 512 时使用压缩列表（可通过 hash-max-ziplist-value 和 hash-max-ziplist-entries配置）
• hashtable

集合对象

编码（底层实现方式）：

• intset
  • 对象都是整数，且元素数量小于 512（元素数量可通过set-max-intet-entries修改）
• hashtable

有序集合

编码（底层实现方式）：

• ziplist（分值小在表头，大的在表尾）
  • 每个成员长度小于 64 字节，元素小于 128 个（可通过 zset-max-ziplist-value 和 zset-max-ziplist-entries配置）
• skiplist（同时使用了一个hashtable，用于查询快速分值，并且底层的元素都是通过指针）

tips：

操作

OBJECT ENCODING key返回一个键的值编码。

TYPE返回一个键的值对象类型。

OBJECT REFCOUNT key返回一个键被引用的次数。

参考资料：

• 《Redis设计与实现》