＜＜redis 设计与实现＞＞

第一部分：数据结构与对象

1.1 动态字符串(String)

Reids 中默认字符串是一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型。
SDS 源码中主要属性：

• free 记录buf中未使用空间。
• len 记录buf中长度 。
• buf 字节数组，用于保存字符串。

SDS定义：遵循C字符串以空字符结尾的惯例，空字符额外分配1字节空间，并不会算到len里面。这样做的目的是为了更好的复用C里面的字符串函数。

SDS杜绝缓存区溢出：在C中两个字符串的拼接数需要提前预留出来空间的，如果没有可能会造成溢出。而SDS在拼接API中会有类似java中的扩容机制，会在掉用API是自主的去帮你判断空间是否足够。

相比C中对字符串修改时内存分配SDS做了几种优化处理：

1. 空间预分配，主要用于字符串修改增长时，程序不仅会为SDS分配必须空间，还会分配额外的预留空间主要通过free属性。
2. 惰性空间释放，用于字符串修改时缩短，程序并不会立即进行内存重新分配来缩短多出来的字节，而是通过free属性将这些字节数记录下来等待将来使用。注意：这里并不需要担心空间浪费，SDS会有相对应的API进行释放。

**总结：**虽然redis使用C语言写的但大多数情况下redis的字符串是使用SDS（Simple Dynamic String，简单动态字符串）最为字符串表示。比起C字符串，SDS具有更多的优点。

1.2 链表(List)

每个链表节点使用一个listNode。List源码中主要属性：

• *prev 前置节点
• *next 后置节点
• *value 节点值

redis 的链表实现 list

list 结构为链表提供了表头指针 head 、表尾指针 tail ，以及链表长度计数器 len ，而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数：

• dup 函数用于复制链表节点所保存的值；
• free 函数用于释放链表节点所保存的值；
• match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

**总结：**链表被广泛用于实现 Redis 的各种功能，比如列表键，发布与订阅，慢查询，监视器，等等。

1.3 字典(Dict)

Redis 的字典使用哈希表(Hash)作为底层实现，一个哈希表中保存了多个哈希节点，每个哈希节点就保存了字典中的一个键值对。

下图是一个完整的字典结构：

1. table：一个hash表，对应一个dictEntry
2. dictEntry：有多个节点，属于一种数组，每当有值进来时会进行key的hash运算，再分配到对应的位置上，当hash冲突时会进行链地址法来解决hash冲突（类似于java中的jdk1.8以前的hashMap存储结构）。具体的hash算法Redis中使用的是MurmurHash2算法。在dict中有一个关键属性 dictht ht[2] 哈希表 默认使用的是ht[0]。ht[1]是在rehash(从新散列)的时候使用。
3. rehash Redis 中字典从ht[0] 复制到 ht[1]采用的是渐进式rehash，并不会一次性，集中的将所有数据复制到ht[1]中，防止数据量庞大时，一次性复制会对服务器造成影响甚至停止服务。渐进性rehash时如果需要查询，那么Redis首先会在ht[0]上查找，没找到再去ht[1]上找。新增的时候所有新增的数据都是新增在ht[1]上。

总结：

• 字典被广泛用于实现 Redis 的各种功能，其中包括数据库和哈希键。
• Redis 中的字典使用哈希表作为底层实现，每个字典带有两个哈希表ht[0],ht[1]，一个用于平时使用ht[0]，另一个仅在进行rehash 时使用ht[1]。
• 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。
• 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面，并且这个 rehash过程并不是一次性地完成的，而是渐进式地完成的。

1.4 跳跃表(skiplist)

跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维护多个指向其他节点的指针，从而达到快速访问节点的目的。

优点：跳跃表 平均时间复杂度O(\log N)，最坏O(N)。 还可以通过顺序性操作来批量处理节点。大部分情况下性能媲美平衡树。

Redis 使用跳跃表作为有序集合键的底层实现之一。条件是，当有序集合(zset)包含的元素比较多，或者有序集合中元素的成员(member)是比较长的字符串是，Redis就会使用跳跃表来做有序集合(zset)键的底层实现。

小结：redis 在内部只有2个地方使用的跳跃表，一个是**有序集合(zset)**键，另一个在集群节点中用作内部数据结构。

Redis中的跳表由zskiplistNode(节点) 和 zskiplist(保存节点相关信息) 两张结构定义。具体结构图如上图5-1：
zskiplist 参数说明：

1. header 存储头节点地址。
2. tail 存储尾节点地址。
3. level 记录目前层数最大的那个节点层数。(头结点的层数不计算在内)
4. length 记录跳跃表的长度。(头结点的层数不计算在内)

zskiplistNode 参数说明：

1. L1~L32 存储的其他节点指针地址。
2. BW 节点的后退指针。
3. 1.0… 节点的分值，影响节点的顺序。
4. o1… 节点成员对象。

总结：

• 跳跃表是有序集合(zset)的底层实现之一，除此之外它在 Redis 中没有其他应用。
• Redis 的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
• 每个跳跃表节点的层高都是1至32之间的随机数。
• 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
• 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

1.5 整数集合(intset)

整数集合(intset)是集合键的底层实现之一：当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合最为集合键的底层实现。

• 升级

redis 中的intset 整数是有int16_t，int32_t，int64_t。3种整数类型。当我们最开始存储时类型为int16_t，再次新增的int32_t类型的数据时，intset 会对底层数据类型进行升级。将int16_t 升级为 int32_t。 升级的重点在于重新分配字节空间，原先16字节一个空间变为32字节一个空间，然后在将对应的值移动到对应的新字节空间中。最后再将新值插入。如下图：

升级的优点：

1. 提升灵活性。应为在C语言中一般int16_t只存16的元素，要是有32的元素也只会使用int32_t来存储，在intset中可以通过自动升级来适应新元素，16，32，64都可以存在集合里，不必担心类型错误。
2. 节约内存。intset 只有在需要的时候才会进行升级。这很好的为我们节约了不必要的内存消耗。

• 降级

整数集合(intset)不支持降级操作，一旦升级，就算导致升级的元素被删除，也会一直保持当前类型状态。
总结：

• 整数集合是集合键的底层实现之一。
• 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
• 整数集合只支持升级操作，不支持降级操作。

1.6 压缩列表(ziplist)

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键或者哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键或者哈希键的底层实现。

压缩列表是Redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。具体结构图如下：

1. zlbytes：记录整个压缩列表占用的内存字节数：在对压缩列表内存进行重新分配，或者计算zlend的位置时使用。
2. zltail：记录压缩列表的表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量可以直接定位到表尾节点的地址。
3. zllen：记录压缩列表的节点数量。
4. entryX：压缩列表的各个节点。
5. zlend：用于标记压缩列表的末端。

压缩列表节点的构成：

1. previous_entry_length：记录了压缩列表中的前一个节点的长度。作用：程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。注意：该参数会导致连锁更新问题。具体原因是previous_entry_length 的长度属性可以为1字节，或5字节。
2. encoding：记录了节点content属性所保存的数据类型和长度。
3. content：保存节点的值。

连锁更新

根据上面的介绍，我们知道previous_entry_length 是保存上一个节点的长度，当节点长度小于254字节，其长度属性类1字节。超过254字节那么previous_entry_length的长度属性要使用5个字节来保存这个长度值。现在如果我们新增一个字节长度大于254的新节点到表头节点，那么下一个节点的previous_entry_length就需要进行更新值身的长度，对压缩列表执行空间重新分配。
当e1进行重新分配空间后，e1的长度字节发生了变化，导致e2的previous_entry_length无法保存其长度，这是e2又会进行重新分配空间，一直进行扩展到eN。这就是连锁更新。
连锁更新的复杂度很高，但它真正造成性能问题的几率很低的。在实际操作中这种连锁更新的触发并不多见。其次就算出现，但只要被更新的节点数量不多，就不会对性能造成影响。

总结：

• 压缩列表是一种为节约内存而开发的顺序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
• 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。