Wei's Blog

Redis设计与实现（一）

 
  • 2020年 04月09日

第二章 动态字符串

主要介绍了redis的SDS(Simple Dynamic String)的数据结构，比C上的String是有一个升级的，重点有几点：

  1. SDS的数据结构里除了一个char数组，还有两个int字段，分别保存数组总长度 以及 剩余可用长度。
  2. SDS的扩容机制：数组长度小于 1M 时，每次扩容会额外扩容一倍，扩容后的剩余可用长度是总长度的一半；数组长度大于 1M 时，每次扩容额外扩容 1M。
  3. SDS支持存储\0作为字符串内容（而不是结尾分隔符），因为额外记录了数组中的有效字符数的长度。

第三章 链表

比较普通的一个双向链表，没有什么特别突出的点。

第四章 字典

其实就是Map类的数据结构，重点有以下几点：

  1. 字典里有两个hash指针，一般用 ht[0]，在做扩容（也就是rehash）的时候，可能会用到ht[1]，扩容完成之后，会释放原ht[0]，将ht[1]赋值给ht[0]
  2. 渐进式扩容：为了避免一次扩容过程中copy大量的数据，导致Redis无法提供服务，因此redis会采用逐步扩容的方式对字典进行扩容。具体过程如下：
  3. 扩ht[1]，并且设置扩容标志rehashidx为0
  4. 在对字典进行操作的时候（查询、增加、删除），顺带将ht[0]的部分对象rehash到ht[1]中，并将rehashidx加1
  5. 扩容结束之后，将rehashidx设置为-1，表示扩容完成。
  6. 额外注意：在扩容期间，对字典的所有查询和删除操作，会同时在ht[0]和ht[1]上生效，所有的写入操作只在ht[1]上生效

第五章 跳跃表

普通的跳跃表，也没有介绍算法和数据结构

第六章 整数集合

比较有意思的一个数据结构，使用场景固定：只包含整数的集合并且数量不多，集合内元素是有序的。有意思的地方在于，该数据结构底层用了一个int_8类型来存放所有整数，包括int_8、int_16、int_32和int_64。

整数集合里包含三个属性，一个是集合数组，一个int_8类型的数组；一个是数组中元素的个数，这里要特别注意，是元素个数；还有一个是数组中数据的编码格式，该字段决定了数组中存放的数据格式。

整数集合的插入过程大致如下：

  1. 判断插入元素的类型是否与当前编码格式匹配
  2. 如果小于当前编码（指的是数据长度小于，而不是数值小于），则直接插入（其实是顺序比较插入，因为要保证有序）
  3. 如果大于当前编码，则触发集合升级动作，升级完成后，进行插入。

集合升级过程如下：

  1. 首先根据最大的数据长度，确定新的整数类型
  2. 根据新的整数类型来确定升级后的数组大小
  3. 将集合中的所有元素（包括插入的元素），按照从右往左的顺序，依次排列到新的数组里

需要注意的是集合升级之后，是没有降级动作的。也就是一旦集合升级到int_64的数据结构了，就永远不可能降回int_16了。

整数集合的好处有两点：一是自适应，能够存放多种整数结构。二是节约空间，使用恰当的格式存放整数。

第七章 压缩列表

一个在内存中连续存放的数据结构，用于小规模（整数较小 或 字符串较小）的hash类型或list类型。压缩列表的存储划分有三块:

  1. 第一块是前一个元素的长度previous_entry_length
  2. 第二块是当前数据的编码和数据长度encoding
  3. 第三块是实际的数据内容content

这里比较有意思的是第一块previous_entry_length。

  1. 首先，通过这个属性，可以实现列表从右向左的遍历，也就是压缩列表支持双向遍历。
  2. 其次，在前一个元素的长度（总长度）小于254字节时，previous_entry_length长度为一个字节；在前一个元素长度大于或等于254字节时，previous_entry_length长度为5个字节。

基于第二点，会有一个很有意思的现象，叫做 连锁更新。 设想一个场景，有一个包含10个元素的压缩列表，其中的元素长度都在 250~253 之间。在修改这个压缩列表的第一个元素，并且将其增加到 255 个字节时，会引发第二个元素的长度更新（也就是previous_entry_length需要从1个字节增加到5个字节）。于是第二个元素的长度也达到了254个字节以上，又会引发第三个元素的更新，以此类推。这个现象，就叫做 连锁更新。很容易分析，在最坏情况下，往压缩列表中插入或更新数据的最坏时间复杂度是 $O(N^2)$，不过一般情况下，时间复杂度为 $O(N)$。

第八章 对象

以上介绍的都是redis的基础数据结构，实际上在redis的存储中，基础的操作元素是一个对象，无论是key还是value，实际上都是对象。key是一个string对象，而value有5种类型，分别为

  • string
  • list
  • hash
  • set
  • zset

redis的数据结构如下所示

typedef struct redisObject {
  // 类型
  unsigned type:4
  // 编码
  unsigned encoding:4
  // 数据存储地址
  void *ptr
  // 最近一次被访问的时间
  unsigned lru:22
}

其中type就是五种数据类型，encoding是前面介绍的基础数据结构中的一种。具体每种类型底层的实现如下

string

能够存储字符串格式的数据，最常用的数据类型，也是唯一一个会在其他数据类型中嵌套使用的数据类型。

redis在存储string类型的数据时，会先判断数据类型以及数据长度，根据不同的情况采用不同的存储结构。

  • 如果是整数类型，并且数据长度可以使用long表示，那么会采用long进行存储。
  • 如果数据长度小于等于32个字节，那么会用embstr来保存。embstr实际上是一个redisObject加SDS的数据结构，它们在内存中是连续的，读取和写入都只需要一次内存访问。
  • 其余情况下，使用SDS进行存储。

list

有序列表格式的数据类型。

redis在存储list的时候，有两种数据结构，一个是压缩列表ziplist，一个是链表linkedlist。只有满足以下两种情况的时候，才使用压缩列表存储

  • 列表内所有元素的长度都小于64字节
  • 列表内元素个数小于512个

hash

包含多个键值对的数据类型。

有两种数据结构，一个是压缩列表ziplist，一个是字典hashtable。只有满足以下两种情况时，才使用压缩列表存储

  • 列表内所有元素的长度都小于64字节
  • 列表内键值对个数小于512个

压缩列表存储键值对是这么存的：将key对象推入压缩列表表尾，紧接着，将value对象推入压缩列表表尾，也就是key对象和value对象永远是成对相邻出现。在查询时，会遍历整个压缩列表，找到查询的key值以及紧跟其后的value值。其中key对象和value对象都是string类型的数据结构。

set

集合数据类型。

也有两种数据结构，一个是整数集合intset和字典hashtable。只有满足以下两种情况时，才使用整数集合存储

  • set内所有元素都是整数类型
  • set内元素个数小于512个

本质上，set和hash是非常类似的（包括JAVA里也是用HashMap实现的HashSet），在redis里，一个set其实就是所有value对象为null的hash对象。

zset

有序集合数据类型。zset和set的区别，主要在于zset会有一个分值score字段，能够基于分值做排序以及范围查找等功能。

也有两种数据结构，一个是压缩列表ziplist，一个是跳跃表skiplist加字典hashtable。只有满足以下两种情况时，才使用压缩列表存储

  • zset内所有元素的长度都小于64个字节
  • zset内元素个数小于128个

在使用ziplist实现zset存储时，先根据score值，找到该元素在压缩列表中的位置，然后将元素对象先插入到对应位置，紧接着，在元素后面插入score值对象。其中，score值较小的排在前面。

在使用skiplist和hashtable实现zset存储时，skiplist中根据score值作为索引实现一个跳跃表，跳跃表最底层有元素值（所有的），hashtable以元素值作为key，score作为value，同样也有所有元素值。

那么为什么要用两种数据结构来做zset的存储呢？主要是基于zset不同使用场景下的性能考虑的，以zset支持的以下两个API举例：根据score值范围查找zrange、获取单个元素score值zscore。

  • zrange如果使用skiplist实现，只需要 $O(logN)$ 的时间复杂度；而使用hashtable的话，需要 $O(NlogN)$ 的时间复杂度，并且需要 $O(N)$ 的额外空间复杂度。
  • zscore如果使用skiplist实现，需要遍历整个列表，需要 $O(logN)$ 的时间复杂度；而使用hashtable的话，仅需要 $O(1)$ 的时间复杂度。

总结

Redis设计与实现 一书的第一章 数据结构与对象 到此结束。主要介绍了Redis底层使用的基础数据结构和对象，之前在我的认知中，对Redis的数据结构了解其实只到了五种数据类型这一层，实际上对于这些数据类型的底层数据结构实现，相关的实现设计其实都没有太多的了解，包括Redis是基于C语言实现的之前也不知道。后面会进行本书的后续章节的学习与总结，时间应该不会太久吧，学习的目的不是为了进行redis开发，而是希望能对redis有更多的了解，并且在条件允许（或者说有兴趣）的情况下，能够造一个类似的轮子，至少需要知道如何造一个类似的轮子。

除了本文所介绍的内容之外，书中还有许多各数据类型所支持的API，以及该API对应的实现方式。这一部分本人认为不太重要，并且不是学习的重点，因此没有列举。

搜索