Redis 数据结构的底层实现—字符串、哈希表、列表、集合

Redis 的键（key）查找机制基于哈希表实现。常用的数据结构有字符串、哈希表、列表、集合及有序集合。

表 Redis 常用的5种数据结构

1 字符串 String

底层结构: SDS（Simple Dynamic String,简单动态字符串）。

struct sdshdr {
   int len; // 已使用的字节长度
   int alloc; // 总分配的字节长度
   char buf[]; // 实际存储字符的字节数组
}

SDS具有以下优势：

1.减少内存重分配次数。

空间预分配，当SDS需要扩容时，会额外预分配alloc的冗余空间。

惰性空间释放，缩短字符串时，不会立即释放多余空间。

2.二进制安全。

C字符串以\0作为结尾标识符，无法存储包含\0的二进制数据。而SDS根据len及buf[]来读取数据。

3.兼容部分C字符串函数。

SDS的buf数组仍以\0结尾。

2 哈希表 Hash

有两种结构：ziplist（压缩列表）与hashtable（哈希表）。

ziplist -> hashtable（redis不支持逆转）转换触发条件：

1. hash-max-ziplist-entires(默认512)，字段数量。
2. hash-max-ziplist-value(默认64字节)，所有字段和值的最大长度。

表 哈希表的底层结构ziplist与hashtable的对比

2.1 哈希表的渐进式Rehash

Rehash 是指对哈希表的大小进行扩展或收缩。为避免Rehash对服务器性能造成影响，服务器会分多次、渐进式地将ht[0](原哈希表)里所有的键值迁移到ht[1]中。步骤如下：

1. 初始化新哈希表ht[1]，设置rehashidx=0。
2. 逐步迁移数据。从ht[0].table[rehashidx]迁移整个桶（链条上所有的节点）到ht[1],rehashidx++,指向下一个待迁移的桶。
3. 操作兼容。在rehash期间，插入直接写入ht[1];删除/查找/更新操作，先在ht[0]中查找，若未找到，则继续在ht[1]中查找；若某个桶正在迁移，对该桶的访问会短暂阻塞，直到迁移完成。
4. 完成迁移，rehashix=-1,ht[0]情况，将ht[1] 设置为ht[0]。

3 列表 List

底层结构：quicklist。快速列表时一个由多个ziplist节点双向连接的链表。每个ziplist节点称为quicklistNode。

头部/尾部插入O(1):若头/尾节点的ziplist未满，直接插入到ziplist中，若已满，创建新的quicklistNode，插入元素后链接到链表头部/尾部。

中间插入O(n):需要遍历定位到具体位置。可能触发ziplist分裂和内存重分配。

list-max-ziplist-size参照控制ziplist的元素数量。

3.1 内存大小优化—压缩

对离头尾节点一定深度（list-compress-depth）的ziplist进行压缩，来减少内存占用。

将ziplist的原始数据通过LZF算法压缩，压缩后的数据替换原ziplist，更新quicklistNode.encoding为LZF。

读操作：如果encoding为LZF，则触发解压，生成临时ziplist，标记recompress=1（后续需要重新压缩）。

写操作：若recompress=1，再次调用LZF压缩。

4 集合 Set

有两种结构：intset 与hashtable。

intset -> hashtable 触发条件：

1. 插入的元素不是整数。
2. 元素数量超过set-max-intset-entires(默认512)。

intset是一个有序的整数数组，查找的时间复杂度为O(logn)。

hashtable 中每个entry的key字段存储Set的成员，value字段固定为null。

5 有序集合 Sorted Set

有两种结构：ziplist 与 skip list + hashtable。

ziplist -> skip list + hashtable 触发条件：

1. 元素数量大于zset-max-ziplist-entires(默认128)。
2. 元素字节长度大于zset-max-ziplist-value(默认64字节)。

ziplist: 以连续内存块存储成员和分数，第一个节点保存成员，第二个节点保存成员的分值。从小到大进行排序。复杂度O(n)。

skip list + hashtable : 哈希表存储的是元素key为元素，value为分值，作用是通过成员直接查找分数。复杂度O(log n)。