Redis数据结构学习笔记

图文主要参考小林Coding的图解redis数据结构

redis为什么快

除了它是内存数据库，使得所有的操作都在内存上进?之外，还有?个重要因素，它实现的数据结构，使
得我们对数据进?增删查改操作时，Redis 能?效的处理。

数据库全景图

:::tips
redisDb 结构，表示 Redis 数据库的结构，结构体?存放了指向了 dict 结构的指针；
dict 结构，结构体?存放了 2 个哈希表，正常情况下都是?「哈希表1」，「哈希表2」只有在rehash 的时候才?，具体什么是 rehash，我在本?的哈希表数据结构会讲；
ditctht 结构，表示哈希表的结构，结构?存放了哈希表数组，数组中的每个元素都是指向?个哈希表节点结构（dictEntry）的指针；
dictEntry 结构，表示哈希表节点的结构，结构?存放了 void * key 和 void * value 指针， *key 指向的是 String 对象，? *value 则可以指向 String 对象，也可以指向集合类型的对象，?如 List 对象、Hash 对象、Set 对象和 Zset 对象
:::

Redis 数据结构

并不是指 String（字符串）对象、List（列表）对象、Hash（哈希）对象、Set（集合）对象和 Zset（有序集合）对象，因为这些是 Redis 键值对中值的数据类型，也就是数据的保存形式，这些对象的底层实现的?式就?到了数据结构。

SDS

简单动态字符串（simple dynamic string，SDS）

C语言字符缺陷

1）结尾位置用“\0”

char * 指针只是指向字符数组的起始位置，?字符数组的结尾位置就?“\0”表示，意思是指字符串的结束
获取字符串?度的函数strlen ，就是通过字符数组中的每?个字符，并进?计数，等遇到字符为 “\0” 后，就会停?遍历

2）字符串里面不能含有“\0”字符

这个限制使得 C 语?的字符串只能保存?本数据，不能保存像图?、?频、视频?化这样的?进制数据

3）strcat会缓冲区溢出

总结

:::tips
1）获取字符串?度的时间复杂度为 O（N）；
2）字符串的结尾是以 “\0” 字符标识，字符串??不能包含有 “\0” 字符，因此不能保存?进制数据；
3）字符串操作函数不?效且不安全，?如有缓冲区溢出的?险，有可能会造成程序运?终?；
:::

SDS的改进

:::tips
1）len，记录了字符串?度。这样获取字符串?度的时候，只需要返回这个成员变量值就?，时间复杂度
只需要 O（1）
2）alloc，分配给字符数组的空间?度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的
空间??，可以?来判断空间是否满?修改需求，如果不满?的话，就会?动将 SDS 的空间扩展?
执?修改所需的??，然后才执?实际的修改操作，所以使? SDS 既不需要?动修改 SDS 的空间?
?，也不会出现前?所说的缓冲区溢出的问题。
3）flags，?来表示不同类型的 SDS。?共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、
sdshdr32 和 sdshdr64，后?在说明区别之处。
4）buf[]，字符数组，?来保存实际数据。不仅可以保存字符串，也可以保存?进制数据。
:::

总结

1. O（1）复杂度获取字符串?度：Redis 的 SDS 结构因为加?了 len 成员变量，获取字符串?度的时候，直接返回这个成员变量的值就?
2. ?进制安全：有个专?的 len 成员变量来记录?度，所以可存储包含 “\0” 的数据
3. 不会发?缓冲区溢出：引?了 alloc 和 len 成员变量，当判断出缓冲区??不够?时，Redis 会?动将扩? SDS 的空间??，下次在操作 SDS 时，如果 SDS 空间够的话，API 就会直接使?「未使?空间」，??须执?内存分配，有效的减少内存分配次数
4. 节省内存空间：有个 flags 成员变量，表示的是 SDS 类型。Redis ?共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同??的字符串，从?有效节省内存空间。Redis 在编程上还使?了专?的编译优化来节省内存空间，即在 struct 声明了 attribute ((packed)) ，它的作?是：告诉编译器取消结构体在编译过程中的优化对?，按照实际占?字节数进?对?

链表

Redis 的 List 对象的底层实现之?就是链表

:::tips
链表优点：

1. listNode 链表节点的结构?带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂

   度只需O(1)，?且这两个指针都可以指向 NULL，所以链表是?环链表；
   

2. list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；

3. list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；

4. listNode 链表节使? void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

链表缺陷：

1. 链表每个节点之间的内存都是不连续的，意味着?法很好利? CPU 缓存。能很好利? CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利? CPU 缓存来加速访问。
2. 保存?个链表节点的值都需要?个链表节点结构头的分配，内存开销较?
   :::

压缩列表

压缩列表的最?特点，就是它被设计成?种内存紧凑型的数据结构，占??块连续的内存空间，不仅可以利? CPU 缓存，?且会针对不同?度的数据，进?相应编码，这种?法可以有效地节省内存开销。
:::tips
压缩列表的缺陷也是有的：

1. 不能保存过多的元素，否则查询效率就会降低；
2. 新增或修改某个元素时，压缩列表占?的内存空间需要重新分配，甚?可能引发连锁更新的问题。

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不?的情况才会使?压缩列表作为底层数据结构。
:::

:::tips

1. zlbytes，记录整个压缩列表占?对内存字节数；
2. zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
3. zllen，记录压缩列表包含的节点数量；
4. zlend，标记压缩列表的结束点，固定值 0xFF（?进制255）。

压缩列表entry节点包含三部分内容：

5. prevlen，记录了「前?个节点」的?度；
6. encoding，记录了当前节点实际数据的类型以及?度；
7. data，记录了当前节点的实际数据；

:::

连锁更新

:::tips
压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占?的内存空间就需要重新分配。?当新插?的元素较?时，可能会导致后续元素的 prevlen 占?空间都发?变化，从?引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降

:::

压缩列表的缺陷

:::tips
连锁更新?旦发?，就会导致压缩列表占?的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能,，压缩列表只会?于保存的节点数量不多的场景.
:::

quicklist

quicklist 是「双向链表 + 压缩列表」组合，因为?个 quicklist 就是?个链表，?链表中的每个元素?是?个压缩列表
:::tips
压缩列表会有「连锁更新」的?险，?旦发?，会造成性能下降。
quicklist 解决办法，通过控制每个链表节点中的压缩列表的??或者元素个数，来规避连锁更新的问题。
因为压缩列表元素越少或越?，连锁更新带来的影响就越?，从?提供了更好的访问性能。
:::

结构设计

:::tips

1. 在向 quicklist 添加?个元素的时候，不会像普通的链表那样，直接新建?个链表节点。?是会检查插?位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构?的压缩列表，如果不能容纳，才会新建?个新的 quicklistNode 结构。
2. quicklist 会控制 quicklistNode 结构?的压缩列表的??或者元素个数，来规避潜在的连锁更新的?险，但是这并没有完全解决连锁更新的问题。
   :::

listpack

结构设计

:::tips
listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标
识。图中的 listpack entry 就是 listpack 的节点了。
主要包含三个??内容：

1. encoding，定义该元素的编码类型，会对不同?度的整数和字符串进?编码；
2. data，实际存放的数据；
3. len，encoding+data的总?度；
   :::
   listpack 没有压缩列表中记录前?个节点?度的字段了，listpack 只记录当前节点的?度，当我们向 listpack 加??个新元素的时候，不会影响其他节点的?度字段的变化，从?避免了压缩列表的连锁更新问题。

哈希表

:::tips
哈希表中的每?个 key 都是独???的，程序可以根据 key 查找到与之关联的 value，或者通过 key 来更
新 value，?或者根据 key 来删除整个 key-value等等。
在讲压缩列表的时候，提到过 Redis 的 Hash 对象的底层实现之?是压缩列表（最新 Redis 代码已将压缩
列表替换成 listpack）。Hash 对象的另外?个底层实现就是哈希表。
哈希表优点在于，它能以 O(1) 的复杂度快速查询数据，Redis 采?了「链式哈希」来解决哈希冲突
:::

rehash过程

:::tips
在正常服务请求阶段，插?的数据，都会写?到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。
随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

1. 给「哈希表 2」 分配空间，?般会?「哈希表 1」 ? 2 倍；
2. 将「哈希表 1 」的数据迁移到「哈希表 2」 中；
3. 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建?个空?的哈希表，为下次 rehash 做准备。
   :::

渐进式rehash

为了避免 rehash 在数据迁移过程中，因拷?数据的耗时，影响 Redis 性能的情况，所以 Redis 采?了渐
进式 rehash，也就是将数据的迁移的?作不再是?次性迁移完成，?是分多次迁移。

rehash 触发条件

rehash 的触发条件跟负载因?（load factor）有关系

整数集合

整数集合是 Set 对象的底层实现之?，Set 对象只包含整数值元素

:::tips
可以看到，保存元素的容器是?个 contents 数组，虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体?的encoding 属性的值。?如：

1. 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是?个 int16_t 类型的数组，数组中每?个元素的类型都是 int16_t；
2. 如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是?个 int32_t 类型的数组，数组中每?个元素的类型都是 int32_t；
3. 如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是?个 int64_t 类型的数组，数组中每?个元素的类型都是 int64_t；不同类型的 contents 数组，意味着数组的??也会不同。
   :::

升级操作

:::tips
当我们将?个新元素加?到整数集合??，如果新元素的类型（int32_t）?整数集合现有所有元素的类型（int16_t）都要?时，整数集合需要先进?升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间??，然后才能将新元素加?到整数集合?，当然升级的过程中，也要维持整数集合的有序性。
:::
1）假设有3个类型int16_t的元素

2）现在要加入一个新元素65535，需要使用int32_t来保存
contents数组腰扩容，4*32-3-16=80

:::tips

1. 如果要让?个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简单做法就是直接使? int64_t 类型的数组。不过这样的话，当如果元素都是 int16_t 类型的，就会造成内存浪费的情况
2. 整数集合升级就能避免这种情况，如果?直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就?直是? int16_t 类型的数组，只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进?升级操作
3. 因此，整数集合升级的好处是节省内存资源
4. 不?持降级操作，?旦对数组进?了升级，就会?直保持升级后的状态。?如前?的升级操作的例?，如果删除了 65535 元素，整数集合的数组还是 int32_t 类型的，并不会因此降级为 int16_t 类型
   :::

跳表

:::tips
Redis 只有在 Zset 对象的底层实现?到了跳表，跳表的优势是能?持平O(logN) 复杂度的节点查找

1. Zset 对象在使?压缩列表作为底层数据结构的时候，zset对象结构的指针会指向压缩列表
2. Zset对象在使?跳表作为底层数据结构的时候，zset对象结构的指针会指向zset结构（哈希表+跳表）
   :::
   
   :::tips
   Zset 对象在使?跳表作为底层实现的时候，并不是指向跳表数据结构，?是指向了zset结构，它包含两个数据结构?个是跳表，?个是哈希表。这样的好处是既能进??效的范围查询，也能进??效单点查询。
   :::

结构设计

跳表是在链表基础上改进过来的，实现了?种「多层」的有序链表

:::tips
图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

1. L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
2. L1 层级共有 3 个节点，分别是节点 2、3、5；
3. L2 层级只有 1 个节点，也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，?使?了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点4。
可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很?时，跳表的查找复杂度就是 O(logN)。
:::

节点数据结构

:::tips
跨度实际上是为了计算这个节点在跳表中的排位
:::

跳表结构体

:::tips

1. 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
2. 跳表的?度，便于在O(1)时间复杂度获取跳表节点的数量；
3. 跳表的最?层数，便于在O(1)时间复杂度获取跳表中层?最?的那个节点的层数量；
   :::

跳表查询过程

:::tips
查找?个跳表节点的过程时，跳表会从头节点的最?层开始，逐?遍历每?层。在遍历某?层的跳表节点时，会?跳表节点中的 SDS 类型的元素和元素的权重来进?判断，共有两个判断条件：

1. 如果当前节点的权重「?于」要查找的权重时，跳表就会访问该层上的下?个节点。
2. 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「?于」要查找的数据时，跳表就会访问该层上的下?个节点。

如果上?两个条件都不满?，或者下?个节点为空时，跳表就会使??前遍历到的节点的 level 数组?的下?层指针，然后沿着下?层指针继续查找，这就相当于跳到了下?层接着查找。
:::

:::tips
如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

1. 先从头节点的最?层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重?要查找节点的?，所以要访问该层上的下?个节点；
2. 但是该层上的下?个节点是空节点，于是就会跳到「元素：abc，权重：3」节点的下?层去找，也就是 leve[1];
3. 「元素：abc，权重：3」节点的 leve[1] 的下?个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点?较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「?于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下?层去找，也就是 leve[0]；
4. 「元素：abc，权重：3」节点的 leve[0] 的下?个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。
   :::

跳表节点层数设置

:::tips
跳表的相邻两层的节点数量最理想的?例是 2:1，查找复杂度可以降低到 O(logN)。
:::
怎么维持？
:::tips
Redis 则采??种巧妙的?法是，跳表在创建节点的时候，随机?成每个节点的层数，并没有严格维持相
邻两层的节点数量?例为 2 : 1 的情况。
具体的做法是，跳表在创建节点时候，会?成范围为[0-1]的?个随机数，如果这个随机数?于 0.25（相当
于概率 25%），那么层数就增加 1 层，然后继续?成下?个随机数，直到随机数的结果?于 0.25 结束，
最终确定该节点的层数。
这样的做法，相当于每增加?层的概率不超过 25%，层数越?，概率越低，层?最?限制是 64。
:::