Lanchester Blog

Leave a leaf

0%

Redis 数据结构与对象系统

Posted on Edited on In

对于 Redis 来说，它的高性能是取决于多个方面的。而高效的数据结构以及合理的数据编码使得 Redis 在保持高效读写的同时，更好的利用内存。

高效的数据结构

Redis 中有多种数据类型，每种数据类型的底层都由一种或多种数据结构来支持。正是因为有了这些数据结构，Redis 在存储与读取上的速度才不受阻碍。

简单动态字符串

SDS （Simple Dynamic String，简单动态字符串）是 Redis 底层所使用的字符串表示，用来处理字符串。除了用来保存数据库中的字符串值之外，SDS还被用作缓冲区（Buffer）：AOF 模块中的 AOF 缓冲区，以及客户端状态中的输入缓冲区，都是由 SDS 实现的。

字符串长度处理

下图是字符串在 C 语言中的存储方式，想要获取「Redis」的长度，需要从头开始遍历，直到遇到 ‘\0’ 为止。

而「Redis」对该读取方式进行了优化：用一个 len 字段记录当前字符串的长度。想要获取长度只需要获取 len 字段即可。前者遍历的时间复杂度为 O(n)，Redis 中 O(1) 就能拿到，速度明显提升。

内存重新分配

C 语言中涉及到修改字符串的时候会重新分配内存。修改地越频繁，内存分配也就越频繁。而内存分配是会消耗性能的，那么性能下降在所难免。而 Redis 中会涉及到字符串频繁的修改操作，这种内存分配方式显然就不适合了。于是 SDS 实现了两种优化策略：

空间预分配

对 SDS 修改及空间扩充时，除了分配所必须的空间外，还会额外分配未使用的空间。

具体分配规则是这样的：SDS 修改后，len 长度小于 1MB，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于等于 1M，那么将额外分配 1M 的未使用空间，直到数据长度达到 512M。

通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。

二进制安全

你已经知道了 Redis 可以存储各种数据类型，那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如 ‘\0’ 等。前面我们提到过，C 中字符串遇到 ‘\0’ 会结束，那 ‘\0’ 之后的数据就读取不上了。但在 SDS 中，是根据 len 长度来判断字符串结束的。因此二进制安全的问题就解决了。

双端链表

列表 List 更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出，一个先进后出。双端链表很好的支持了这些特性。包括链表键在内，发布与订阅、慢查询、监视器等功能也用到了链表，Redis 服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

前后节点

链表里每个节点都带有两个指针，prev 指向前节点，next 指向后节点。这样在时间复杂度为 O(1) 内就能获取到前后节点。

头尾节点

头节点里有 head 和 tail 两个参数，分别指向头节点和尾节点。这样的设计能够对双端节点的处理时间复杂度降至 O(1) ，对于队列和栈来说再适合不过。同时链表迭代时从两端都可以进行。

链表长度

头节点里同时还有一个参数 len，和上边提到的 SDS 里类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到 len 值就可以了，这个时间复杂度是 O(1)。

字典

Redis 作为 K-V 型数据库，所有的键值都是用字典来存储的。字典的特性能够在 O(1) 时间复杂度内取出和插入关联的值。

数据结构实现

下图是一个空的哈希表实现

下图是带两个节点的哈希表实现

下面是普通状态下（没有进行重哈希的）的字典的实现

rehash过程

基本原理

扩展和收缩哈希表的工作可以通过执行 rehash（重新散列）操作来完成，Redis 对字典的哈希表执行 rehash 的步骤如下：

  1. 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即是 ht[0].used 属性的值）：
    • 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2 的 n 次方幂
    • 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2 的 n 次方幂
  2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面（rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上）。
  3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

渐进式优化

如果将全部键值对一次地、集中式地 rehash 完成，可能会导致服务器暂停一段时间服务。因此为了避免 rehash 对服务器造成一定的影响，采取的是渐进式地、分多次地完成该操作。

以下是哈希表渐进式 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 而带来的庞大计算量。

跳跃表

作为 Redis 中特有的数据结构-跳跃表，其在链表的基础上增加了多级索引来提升查找效率。Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现。除此之外，Redis 只在实现有序集合键和在集群节点中用作内部数据结构这两个地方用到了它。

基本结构

如下图，对初始链表做一层“索引”，每两个节点提取一个节点到上一层，然后用down指针连接到下一层。

现在我们查询16这个节点。从第一级索引开始，找到13，并且下一个为17，显然16在这两个节点之间，利用down指针下降一层，这次我们遍历2次即可。利用索引后，遍历了5+2=7次，而原始链表需要10次，这里加一层索引遍历次数减少了，效率提高了一点，但还不够，我们继续往上添加索引层。

查询结果是6次，效率又提高了！那么这种链表加多级索引就是跳表的结构了。

查询时间复杂度

① 假设链表有 N 个节点，按图所示依次往上级添加索引，第一级有 N/2 个节点，第二级有 N/4 个节点，那么第 k 级索引有N/(2^k)个节点。

② 假设索引有 H 级，最高级有 2 个节点。就有N/(2^h)=2 --> h=log2N-1（以 2 为底 N 的对数）。加上原始链表，那么高度就是 log2N 了。

③ 查询时，如果每层都遍历 m 次（最高级最多遍历2次，其他级最多遍历m次）那么复杂度就是O（mlgN）（在大O表示法里，logaN 级别的复杂度等于 lnN 复杂度,去掉 m 就是 O(logn) 级别了），我们求一下 m 的值。

在第k级时，我们遍历到了 y 和 z，查询值介于两者之间，通过down指针，到达第 k-1 级，而这一级 y 和 z 之间最多有 3 个节点，那么 m 就等于 3 了。综上跳表的查询时间复杂度就是O（logn）了。

结构空间复杂度

空间复杂度就是每层节点和，即n/2+n/4+...+4+2=n-2,空间复杂度就是 O(n) 了。

当然了这里也可以扩大索引间隔，减少一点索引空间，但是我们还是按照上面的求时间复杂度方法，得到的结果仍是 O(logn)。实际应用中，向来是比较乐意用空间换时间的，所以这种做法的意义并不大，因为时间复杂度还是没变！

并且软件开发中，链表存的可能是一个很大的对象，索引只需要记录关键字和一些指针，那么额外的空间和原数据相比完全可以忽略！

高效的动态插入和删除

插入动作的时间复杂度仍是 O(logn) = 单链表插入复杂度 O(1) + 查找插入点复杂度，加上查找时间 O(logn)。

删除要麻烦一点，因为删除的节点要是在索引中，还需要更新索引，更新索引就得找到前驱节点，当然双链表可以不用考虑了！

索引动态更新

更极端的可以退化成单链表，所以索引的动态更新是必要的！

AVL树是通过左右旋转保持平衡性，而跳表是通过随机函数生成一个值K，然后将节点添加到第一级到第K级索引中。

redis跳表存储结构

整数集合

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

整数集合基本结构

整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现重复元素。

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：

  • 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t 类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。
  • 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t 类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
  • 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t 类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）。

升级

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

升级整数集合并添加新元素共分为三步进行：

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

升级之后新元素的摆放位置：

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大， 所以这个新元素的值要么就大于所有现有元素， 要么就小于所有现有元素

  • 在新元素小于所有现有元素的情况下， 新元素会被放置在底层数组的最开头（索引 0 ）；
  • 在新元素大于所有现有元素的情况下， 新元素会被放置在底层数组的最末尾（索引 length-1 ）。

升级的好处：提升灵活性

因为 C 语言是静态类型语言， 为了避免类型错误， 我们通常不会将两种不同类型的值放在同一个数据结构里面。

比如说， 我们一般只使用 int16_t 类型的数组来保存 int16_t 类型的值， 只使用 int32_t 类型的数组来保存 int32_t 类型的值， 诸如此类。

但是， 因为整数集合可以通过自动升级底层数组来适应新元素， 所以我们可以随意地将 int16_t 、 int32_t 或者 int64_t 类型的整数添加到集合中， 而不必担心出现类型错误， 这种做法非常灵活。

升级的好处：节约内存

当然， 要让一个数组可以同时保存 int16_t、int32_t、int64_t 三种类型的值， 最简单的做法就是直接使用 int64_t 类型的数组作为整数集合的底层实现。 不过这样一来， 即使添加到整数集合里面的都是 int16_t 类型或者 int32_t 类型的值， 数组都需要使用 int64_t 类型的空间去保存它们， 从而出现浪费内存的情况。

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值， 又可以确保升级操作只会在有需要的时候进行， 这可以尽量节省内存。

降级

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

压缩列表

如果在一个链表节点中存储一个小数据，比如一个字节。那么对应的就要保存头节点，前后指针等额外的数据。这样就浪费了空间，同时由于反复申请与释放也容易导致内存碎片化。这样内存的使用效率就太低了。于是，redis 采用了压缩列表的策略。

压缩列表数据结构

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

下图是压缩列表的构成

它是经过特殊编码，专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。并且压缩列表的内存是连续分配的，遍历的速度很快。

压缩列表节点数据结构

previous_entry_length

因为节点的 previous_entry_length 属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。因此可以从后向前遍历整个压缩列表。

encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度：

  • 一字节、两字节或者五字节长，值的最高位为 00、01 或者 10 的是字节数组编码：
    这种编码表示节点的 content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录
  • 一字节长，值的最高位以11开头的是整数编码：这种编码表示节点的 content 属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录

下图为压缩列表子节点示例

连锁更新

向一个节点长度都在 [250, 253] 字节的压缩列表添加一个 new 节点（长度大于等于 254字节，需要 5 字节的 previous_entry_length 来储存），因为 e1 储存了前一节点的长度，因此要将 e1 进行扩展，紧接着对 e2 进行扩展，不断推进下去。这里拓展的原因是因为 e1 为了储存前节点长度，previous_entry_length 字段扩展到 5 字节，节点长度超过了 254，造成下一节点的扩展。

当然根据该原理，新增和删除节点特定情况下都会造成连锁更新。

对象系统

Redis 并没有直接使用上述这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。

除此之外，Redis 的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；另外，Redis 还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同个对象来节约内存。

最后，Redis 的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了 maxmemory 功能的情况下，空转时长较大的那些键可能会优先被服务器删除。

对象的类型与编码

Redis 是非关系型数据库中键值对数据库的典型代表。因此，Redis 每当创建一个键值对时，都要创建一个键对象、一个值对象。

对象的类型

下图是 Redis 键值对支持的类型

对象 对象 type 属性的值 TYPE 命令的输出
字符串对象 REDIS_STRING “string”
列表对象 REDIS_LIST “list”
哈希对象 REDIS_HASH “hash”
集合对象 REDIS_SET “set”
有序集合对象 REDIS_ZSET “zset”

对象的编码

对象的 encoding 属性记录了对象使用的编码，也就是指明对象用的是什么底层实现。

下图是所有的编码常量

下图是对象类型和编码常量组成的对象

通过 encoding 属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了 Redis的灵活性和效率，因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

举个例子，在列表对象包含的元素比较少时，Redis 使用压缩列表作为列表对象的底层实现：

  • 因为压缩列表比双端链表更节约内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中
  • 随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失时，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面

字符串对象

int编码的字符串对象

字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示

embstr编码的字符串对象

该字符串对象可以表示：字符串值，或者因为长度太大而没办法用 long 类型表示的整数，或者用 long double 类型来表示的浮点值。但最终的字符串长度不得大于 32 字节。

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样，都使用 redisobject 结构和 sdshdr 结构来表示字符串对象，但 raw 编码会调用两次内存分配函数来分别创建 redisobject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含 redisobject 和 sdshdr。

  • embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。
  • 释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而释放 raw 编码的字符串对象需要调用两次内存释放函数。
  • 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起 raw 编码的字符串对象能够更好地利用缓存带来的优势。

raw编码的字符串对象

该字符串对象保存的是一个字符串值、整型或是浮点型数值，并且这个字符串值的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值

根据相应操作，这三种类型可相互转换

部分命令实现

列表对象

列表对象的编码可以是 ziplist 或者 linkedlist。

ziplist编码的numbers列表对象

linkedlist编码的numbers列表对象

当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码：

  • 列表对象保存的所有字符串元素的长度都小于64字节
  • 列表对象保存的元素数量小于512个；

不能满足这两个条件的列表对象需要使用 linkedlist 编码

部分命令实现

哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable。

zpilist编码的哈希对象

压缩列表的键值对按顺序从表尾插入

hashtable编码的哈希对象

当哈希对象可以同时满足以下两个条件时，哈希对象使用 ziplist 编码，否则使用 hashtable：

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  • 哈希对象保存的键值对数量小于512个

部分命令实现

集合对象

集合对象的编码可以是 intset 或者 hashtable。

intset编码的集合对象

hashtable编码的集合对象

当集合对象可以同时满足以下两个条件时，对象使用 intset 编码，否则使用 hashtable：

  • 集合对象保存的所有元素都是整数值
  • 集合对象保存的元素数量不超过512个

部分命令实现

有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist。

ziplist编码的有序集合对象

压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。

skiplist编码的有序集合对象

skiplist编码的有序集合对象使用的是 zset 结构作为底层实现，它同时包含一个字典和一个跳跃表。字典保存 key 和 value 的映射关系，跳跃表保存了按 value 从小到大排序的所有集合元素。这两种数据结构通过指针共享相同元素的成员和分值，节省了内存。

当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码，否则使用 skiplist 编码：

  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素成员的长度都小于64字节

部分命令实现

对象共享与内存回收

引用计数原理

redis 在对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，应用可以通过跟踪对象的引用计数信息，在适当的时机自动释放对象并进行内存回收。

每个对象的引用计数信息由 redisObject 结构的 refcount 属性记录

typedef struct redisObject {
    ...
    //引用计数
    int refcount;
    ...
} ...

对象共享原理

当准备创建多个相同整型值的字符串对象时，只创建一份数据，随后全部改为指针引用的形式来获取相关的内容。这些共享内容不仅仅能被字符串对象引用，也可以在那些数据结构中嵌套了字符串对象的对象（linkedlist 编码的列表对象、hashtable 编码的哈希对象、hashtable 编码的集合对象，以及 zset 编码的有序集合对象）中引用。

注意：能共享的对象只能是包含整数的字符串对象。

为什么不共享包含字符串的对象？

当服务器考虑将一个共享对象设置为键的值对象时，程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同，只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象用作键的值对象，而一个共享对象保存的值越复杂，验证共享对象和目标对象是否相同所需的复杂度就会越高，消耗的CPU时间也会越多：

  • 如果共享对象是保存整数值的字符串对象，那么验证操作的复杂度为 O(1)
  • 如果共享对象是保存字符串值的字符串对象，那么验证操作的复杂度为 O(N)
  • 如果共享对象是包含了多个值（或者对象的）对象，比如列表对象或者哈希对象，那么验证操作的复杂度将会是O(N^2)。

因此，尽管共享更复杂的对象可以节约更多的内存，但受到 CPU 时间的限制 Redis 只对包含整数值的字符串对象进行共享。

基于引用计数的内存回收原理

对象的引用计数信息会随着对象的使用状态而不断变化：

  • 在创建一个新对象时，引用计数的值会被初始化为 1
  • 当对象被一个新程序使用时，它的引用计数值会被增一
  • 当对象不再被一个程序使用时，它的引用计数值会被减一
  • 当对象的引用计数值变为 0 时，对象所占用的内存会被释放

基于对象空转时长的内存回收原理

typedef struct redisObject {
    ...
    //对象最后一次被命令程序访问的时间：
    unsigned lru:22;
    ...
}...

除了可以被 OBJECT IDLETIME 命令打印出来之外，键的空转时长还有另外一项作用：如果服务器打开了 maxmemory 选项，并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru，那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。