Data Structure Impl

数据结构实现

以7.0.10版为例。

层级

数据库

在Redis中，数据库以redisDB对象存在，定义如下：

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
    clusterSlotToKeyMapping *slots_to_keys; /* Array of slots to keys. Only used in cluster mode (db 0). */
} redisDb;

对象

Redis是key-value存储，key value和都被抽象成对象。

key只能是string，value可以是多重类型，比如string，set，Zset、list等。

定义如下

//version: 7.0.10
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;
  • type: 是哪种Redis对象。
  • encoding：表示对象是哪种底层编码，比如string的对象可以是embstr、也可以是raw。通过object encoding [key]来查看。
  • lru：lru相关，缓存淘汰机制。
  • refcount：引用计数，描述有多少个指针，指向该对象。
  • ptr：内容指针，指向实际的对象。

String

编码格式

INT

如果一个字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示， 那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int 。

EMBSTR

sdshdr的内存是和redisObject一块分配的，是连续的。所以叫做embed string。

因为内存分配需要

RAW

不难发现RAW和EMBSTR都有个sdshdr结构。

SDS

字符串应用很频繁，在C语言中的字符串以\0结尾，存在一些问题。

  1. 字符串里面不能含有 “\0” 字符，否则最先被程序读入的 “\0” 字符将被误认为是字符串结尾，这个限制使得 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据（这也是一个可以改进的地方）
  2. 使用strcat拼接时需要程序员自己考虑内存长度，不注意就会导致段错误。
  3. 获取长度时，需要遍历整个字符串，直到遇到\0这个字符。

Redis的SDS解决了这些问题。

原理

在7.0.10的版本下，Redis的SDS按照长度分为sdshdr8、sdshdr16、sdshdr32、sdshdr64等多个长度。以sdshdr32为例，结构如下。

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
  • len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
  • alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。
  • flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。
  • buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。

C语言中的问题，得到了解决：

  1. 二进制安全：可以含有\0，因为有一个长度变量记录长度。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “\0” 字符。
  2. 不会发生缓冲区溢出，因为sds暴露的api会检查缓冲区是否足够，不够则自动扩容。
  3. $O(1)$复杂度获取字符串长度，直接获取len变量即可。

其中，扩容的规则如下

  • 如果所需的 sds 长度小于 1 MB，那么最后的扩容是按照翻倍扩容来执行的，即 2 倍的newlen
  • 如果所需的 sds 长度超过 1 MB，那么最后的扩容长度应该是 newlen + 1MB。

其他优化

  1. 设计多种长度sds，尽量节约空间。

  2. Redis 在编程上还使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。这样，就可以节约空间。以时间换空间。

ZipList

压缩链表的元素和控制头的内存是连续的，主要是为了节省指针域，整个空间都是连续的。

压缩列表在表头有三个字段：

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

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。

另外，压缩列表节点（entry）的构成如下：

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

  • prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
  • encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
  • data，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

其中，prevlen会根据前一个节点的长度进行不同的空间大小分配：

  • 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
  • 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

不难发现，prevlen记录的是前一个节点的大小，因此当前一个元素改动时，可能发生连锁反应。

例如下图，插入一个新节点new

会发生连锁反应，导致多次内存的复制。

listpack

为了解决「连锁更新」的问题，引出来PackList，

ZipList发生该问题的本质是

  1. prevlen的字节数是可变动的。
  2. prevlen表示的不是节点本身的大小，会收到其他节点长度变更，导致连锁变更。

所以其实只要解决一点，就可以解决这个问题。为了节约空间，ListPack从第二点入手，记录本节点的属性。其结构如下

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

每个 listpack 节点结构如下：

ListPack节点的内存顺序如下

<encoding-type> <element-data> <element-tot-len>

这3个元素都是记录的本身的属性

  • encoding-type 编码类型
  • element-data 元素数据
  • element-tot-len 本元素除了本字段的长度

其他优化

其中，elemnt-tot-len有一些特别：它所占用的每个字节的第一个bit用于表示是否结束。0是结束，1是继续，剩下7bit用于存储大小。例如0000-0001 1000-0100，我们逆序遍历时，首先读取最后那个字节，读到1000-0100,发现第一个bit是1，需要继续读取一个字节，直到第一个bit为0。所以这里element-tot-len一共两个字节，大小为 000-0001 000-0100， 即这个元素132字节。

QuickList

quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是 quicklistNode。

typedef struct quicklist {
    //quicklist的链表头
    quicklistNode *head;      //quicklist的链表头
    //quicklist的链表尾
    quicklistNode *tail; 
    //所有压缩列表中的总元素个数
    unsigned long count;
    //quicklistNodes的个数
    unsigned long len;       
    ...
} quicklist;

接下来看看，quicklistNode 的结构定义：

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;     //前一个quicklistNode
    //下一个quicklistNode
    struct quicklistNode *next;     //后一个quicklistNode
    //quicklistNode指向的压缩列表
    unsigned char *zl;              
    //压缩列表的的字节大小
    unsigned int sz;                
    //压缩列表的元素个数
    unsigned int count : 16;        //ziplist中的元素个数 
    ....
} quicklistNode;

可以看到，quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。

我画了一张图，方便你理解 quicklist 数据结构。

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

Hash

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

渐进式rehash

渐进式 rehash 步骤如下：

  • 给「哈希表 2」 分配空间；
  • 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
  • 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

比如，查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。

rehash 触发条件

介绍了 rehash 那么多，还没说什么时情况下会触发 rehash 操作呢？

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

负载因子可以通过下面这个公式计算：

触发 rehash 操作的条件，主要有两个：

  • 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
  • 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。

rehash的问题

  • 对于键空间字典和过期字典，会有个 serverCron 时间事件自动跟进 rehash 的过程，就算之后马上没有流量访问了，也会推进 rehash，可以通过配置修改是否推进。
  • 普通的其它字典则不会推进。

整数集合

整数集合本质上是一块连续内存空间，它的结构定义如下：

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

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

  • 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
  • 如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
  • 如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

不同类型的 contents 数组，意味着数组的大小也会不同。

升级操作

Redis
Data Structure Impl
https://messenger1th.github.io/2024/07/24/Redis/Data Structure Impl/
作者
Epoch
发布于
2024年7月24日
许可协议