Redis 底层学习-数据结构

1.简单动态字符串-SDS

数据结构

image-20200819162905094

  • len: 记录 sds 字符串的长度
  • free：buf 数组中未使用的数量
  • buf[]:保存字符串的字节数组

需要注意的是，buf 数组中最后一个字节存储的是\0，并且这个字节并不计算到 len 的长度中。这么做的原因是为了保持和 c 语言中的字符串保持一致，可以直接使用 c 语言字符串的一些库函数。

SDS 和 c 语言字符串的区别

常数复杂度获取字符串长度

SDS 包含了 len 属性，可以在 O(1)的复杂度中获取到字符串长度，而 c 语言需要便利整个字符串，直到字符串结尾计数结束，复杂度为 O(n)

杜绝缓冲区溢出

在 c 语言字符串中，在执行 strcat 函数，假定当前字符串分配了足够的内存。如果当前字符串的分配长度不够修改的长度，那么会顺延到下一个空间，会造成当前字符串修改错误，下一个空间的变量也会被莫名修改。

在 sds 字符串中，修改的时候会判断 len 的长度是否满足需要，否则进行扩容

减少内存重分配的次数

c 语言字符串在执行 append、trim 函数的时候，需要通过内存重分配来扩展空间或者释放多余的空间。因为内存分配涉及到复杂的算法，是一个比较耗时的工作。

SDS 对于字符串做了优化，通过空间预分配和惰性空间释放来减少内存重分配的次数。

  • 空间预分配
    • 对 sds 修改之后，sds 的长度小于 1MB，那么程序分配和 len 长度一样的未使用空间
    • 对 sds 修改之后，sds 的长度大于 1MB，那么程序分配 1M 的未使用空间
  • 惰性空间释放：在对 sds 进行缩短操作的时候，并不会立马释放多出来的空间。而是通过 free 属性记录下来，以等待将来使用。sds 也提供了相应的 api，释放多余的空间

2.链表

数据结构

image-20200819201531691

image-20200819201554133

链表特性

  • 双端：链表节点含有 prev 和 next 指针，获取上一个节点和下一个节点的时间复杂度都是 O(1)
  • 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 null，对链表的访问以 null 结尾
  • 带表头指针和表尾指针：获取链表的头节点和尾节点的时间复杂度都是 O(1)
  • 带链表长度计数器：通过 len 属性获取链表的长度的时间复杂度尾 O(1)
  • 多态：链表节点使用 void*指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型指定函数，所以链表可以用来保存各种不同类型的值。

3.字典

数据结构

image-20200819202633205

一个字典-dict 中含有 2 个哈希表-dictht，每一个哈希表里面含有 1 个哈希表节点数组，每一个哈希表节点保存着对应的 key 和 value，以及指向下一个哈希表节点的指针(hash 冲突)。

解决哈希冲突的方式就是拉链法，这里和 java 中的方式是大同小异的，就不赘述了。

rehash

字典中含有 2 个哈希表，为存储元素位置，ht[1]为扩展之后的元素迁移位置。当 rehash 完成之后，删掉 ht[0]，ht[1]变成 ht[0],重写创建一个 ht[1]。

rehash 之后的哈希表数组的长度：

  • 如果进行的是扩展操作，那么扩展之后的哈希表的长度为第一个大于等于 ht[0].uesed*2 的值，并且这个值是 2 的 N 次方
  • 如果进行的收缩操作，那么收缩之后的哈希表的长度为第一个大于等于 ht[0].uesed 的值，并且这个值是 2 的 N 次方

例子：如果当前已使用为 15，15*2=30，那么第一个大于等于它的 2 的 n 次幂就是 32，所以扩容之后的长度就是 32

rehash 的场景：

  • 服务器目前没有进行 bgsave 或者 bgrewriteaof 命令，并且哈希表的负载因子大于 1.
  • 服务器正在进行 bgsave 或者 bgrewriteaof 命令，并且哈希表的负载因子大于 5
  • 另一方面，当负载因子小于 0.1 的时候，程序自动进行收缩操作

渐进式 rehash

在字典数据特别大的时候，从 ht[0]到 ht[1]迁移的时间可能特别长，所以通过渐进式 rehash 操作，来保证不会因为一次操作阻塞服务。

步骤：

  1. 为 ht[1]分配空间，让字典拥有 ht[0]和 ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx，并将它设置为 0，标示 rehash 工作正式开始。
  3. 在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行了指定的操作以外，还会顺带将 ht[0]表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 的属性的值增一。
  4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被 rehash 到 ht[1]，这是程序将 rehashidx 属性的值设为-1，标示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值所需要的计算工作平摊到字典的每个添加、删除、查找和更新操作上，从而避免集中时 rehash 而带来的庞大计算量。

渐进式 rehash 执行期间的哈希表操作

在执行渐进式 rehash 的过程中，字典会同时使用 ht[0]和 ht[1]两个哈希表，所在渐进式 rehash 进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行。查找时，先在 ht[0]查找，如果没找到的话，会继续到 ht[1]中查找。

在渐进式 rehash 执行期间，新添加的字典的键值对会直接保存在 ht[1]中。

4.跳跃表

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

image-20200820104530082

zskiplist

  • header：指向跳跃表的表头节点
  • tail：指向跳跃表的表尾节点
  • Level:记录目前跳跃表内，层数最大的那个节点的层数
  • length：记录目前跳跃表的长度

zskiplistNode

image-20200820104821493

  • 层：这是一个数组对象，对象存储的是指向某个前进节点的指针和两者之间的跨约长度
  • 后退指针：指向当前节点的上一个节点，主要用来从表尾向表头遍历。
  • 分值：保存的分值，跳跃表中的节点按照分值从小到大排列
  • 成员对象-obj：存储的对象的值

特性

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

5.整数集合

整数集合时集合键-set 的底层实现之一，当一个集合只包含整数元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

整数集合是 Redis 用于保存整数值的集合抽象数据结构，它可以保存 int16_t,int32_t,int64_t 的整数值，并且不会出现重复元素。

数据结构

image-20200820110450037

encoding：可以为 intset _enc_8、intset _enc_16、intset _enc_32。这个决定了 contents 数组中保存元素的数据格式

contents：整数集合的每个元素都是 contents 数组的一个数组项，每个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

length：保存整数集合中包含元素的长度。也是 contents 数组的长度。

数据类型升级

当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级 ，然后才能将新元素添加到整数集合中

步骤：

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位置上。而且在放置过程中，需要继续维持底层数组的有序性质不变。–计算每个元素本来应该在的位置 ，从尾部开始移动元素位置
  3. 将新元素添加到底层数组里面。

数据类型升级的好处

  1. 提升灵活性：一个数组中存储的都是相同类型的元素，通过升级保证元素类型一致
  2. 节约内存：可以让集合能保存 3 个不同类型的值，又确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

降级

整数集合不支持降级操作，一但对数组进行了升级，编码就会一致保持升级后的状态。

6.压缩列表

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

数据结构

image-20200820142409328

zlbytes：记录整个压缩列表占用的内存字节数，在对压缩列表重分配，或者计算 zlend 的位置时使用

zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点的地址。

zllen：记录了压缩列表包含的节点数量，如果这个属性的值等于 unint16—max-65535 时，节点的真实数量需要遍历整个压缩列表才能计算得出。

entryx：列表节点。保存节点的内容

zlend：用于标记压缩列表的末端。

压缩列表节点

image-20200820143036588

previous_entry_length:记录的是前一个节点的长度，可以通过上一个节点的长度 ，从当前节点推导出前一个节点的位置。

encoding：记录了节点的 content 属性所保存的类型以及长度。–字节或者整数

content：保存节点的值

连锁更新

由于 previous_entry_length 可能是 1 个字节或者 5 个字节，在前一个节点的长度大于 254 字节的时候，会导致 previous_entry_length 从一个字节更新到 5 个字节，从而可能导致后续所有节点都更新的情况。出现的几率还是很低的。