Qian0817
0%

Redis中的数据结构

发表于 更新于 分类于
本文字数： 5.9k 阅读时长 ≈ 17 分钟
介绍在Redis实现时采用的数据结构

简单字符串SDS

因为C语言使用的字符串无法满足Redis的需求，Redis构建了一种简单字符串来代替C字符串。在Redis的数据库中，所有包含字符串的地方都会使用到SDS来实现。

SDS定义

SDS的结构如下所示：

1
2
3
4
5
6
7
8
struct sdshdr {
    // 已占用空间的长度
    int len;
    // 剩余可用空间的长度
    int free;
    // 保存的字符串
    char buf[];
};

free属性记录了buf数组中未使用字节的数量，len属性记录了已经使用字节的数量，buf数组存储字符串。

为了重用C字符串函数库中的函数，buf字段遵循C语言中以空字符结尾的惯例，最后为空字符’/0’。

SDS优点

通过SDS这一数据结构，带来了例如可以用常数复杂度获取字符串长度，杜绝了缓冲区溢出，减少内存重新分配次数，二进制安全等等好处。

其中通过未使用空间，Redis实现了空间预分配以及惰性空间释放两种策略来减少内存分配次数。

空间预分配

当对一个SDS进行修改的时候，Redis不仅会分配修改所必须的空间，同时还会分配额外的未使用空间。空间的分配方法为：

  • SDS长度小于1MB时，程序分配和len属性同样大小的未使用空间。此时len属性的值与free属性相同。
  • SDS长度大于1MB时，程序会固定分配1MB的未使用空间。

通过空间预分配策略，减少了连续执行字符串增长所需的内存分配时间。在扩展SDS之前，会先检查未使用空间是否足够，如果足够的话，会直接使用未分配空间，而无需再次分配。

惰性空间释放

当一个SDS需要缩短时，会先使用free属性来将这些字节记录起来。通过惰性空间释放，SDS避免了缩短字符串时所需的内存重新分配操作，并为将来的增长操作提供了优化。

链表

链表作为一种常用的数据结构，在Redis中应用十分广泛。

链表结构

链表节点的实现如下所示：

1
2
3
4
5
6
7
8
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

从数据结构定义可以看出其结构是一个双端队列。list结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
    // 链表所包含的节点数量
    unsigned long len;
} list;

同时list结构为链表提供了表头节点head，表尾节点tail，链表长度len的信息。同时在list中放了三个函数dup用于复制链表节点，free用于释放链表节点，match用于对比所保存的的值与另一个输入值是否相等。

字典

字典用于保存K-V键值对，在Redis中的使用十分广泛。对数据库的增删改查以及哈希键的实现就使用到了字典。

字典结构

哈希表节点的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

每个dictEntry都保存着一个键值对。其中key属性保存着键值对中的键，v属性保存着键值对中的值。因为Redis中的字典使用了链地址法来解决哈希冲突，所以需要next属性来形成链表。

哈希表的结构如下：

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

table属性是一个数组，每个元素都是一个dictEntry。size属性记录了这个哈希表的大小，也就是table的长度。sizemask的值总数等于size-1，这个属性决定了一个键值对应该被放到哪个索引中去。used属性记录了已经有多少个键值对被插入。

字典的结构如下：

1
2
3
4
5
6
7
8
9
10
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引，当不再 rehash 过程时值为-1
    int rehashidx;
} dict;

其中type属性是指向dictType类型的指针,在其中保存了操作特定类型键值对的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

privdata属性保存了需要传给那些特定类型的可选参数。rehashidx记录了rehash目前的进度，如果没有进行rehash，那么值为-1。ht属性是包含两个项的数组，当没有进行rehash时，字典只使用ht[0]哈希表，ht[1]只会在rehash过程中使用。

哈希算法

Redis中使用MurmurHash算法来计算键的哈希值。这种算法的优势在于在提供很好的随机分布性的同时计算速度也十分的快。

渐进式rehash

当出现以下情况时，会进行rehash操作：

  • 服务器没有执行BGSAVE命令或者BGREWRITEAOF命令，负载因子大于1

  • 服务器执行BGSAVE命令或者BGREWRITEAOF命令，负载因子大于5

  • 负载因子小于0.1

为了避免rehash对Redis的性能造成影响，Redis实际上会分多次将ht[0]中的数据转移到ht[1]之中，具体的过程如下：

  1. 为ht[1]分配空间，设置rehashidx属性的值为0。

  2. 每当对字典进行操作的时候，程序在执行指定操作的同时，会将在rehashidx索引上的键值对rehash到ht[1]之中。当rehash工作完成时，rehashidx属性加一。

  3. 当ht[0]中所有键值对被rehash到ht[1]中时，将rehashidx设置为-1，结束rehash。

在rehash过程中，如果需要进行增删改查等操作的时候，会先在ht[0]中进行查找，如果没找到则进入ht[1]中进行查找。同时新添加的键值对会被记录到ht[1]之中。

跳跃表

跳跃表是一种有序的数据结构，能够做到快速的访问节点。在大部分情况下，跳表的速率与平衡树相差不大，但是实现更为简单，因此Redis中使用了跳表来代替平衡树。Redis使用跳表来作为有序集合键。

跳表结构

跳表节点的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

其中obj成员是一个指针指向一个Redis对象。score属性代表该节点的分值，跳跃表中的节点都会按照该分值由大到小进行排列。在跳跃表中，成员对象obj是唯一的但是score可以相同。如果出现分值相同的节点，那么Redis会按照成员对象的字典序大小进行排序。后退指针backward用于从表尾向表头方向对成员进行访问。

层属性level是一个数组，其中每个元素可以包含前进指针和跨度。前进指针用于从表头向表尾进行访问。跨度用于记录两个节点之间的距离，在查找时跨度用来计算排位（Rank）。

跳跃表的结构如下：

1
2
3
4
5
6
7
8
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

其中header和tail分别表示跳跃表的表头和表尾节点。level记录了目前跳跃表内层次最大的那个节点的层数，其值大于1小于32。length属性记录了跳跃表的长度。

整数集合

整数集合用于实现集合键。当一个集合只包含有整数值且数量不多时，那么会使用整数集合作为集合的底层实现。其可以保存int_16t,int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

整数集合实现

整数集合的结构如下：

1
2
3
4
5
6
7
8
typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

encoding表示整数的编码方式。虽然将contents数组声明为int8_t类型，但是contents数组的真正类型取决于encoding类型。其中encoding类型可以为INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64。length表示所包含的元素个数。contents是用于保存元素的，其值会按照由小到大的顺序进行排列。

整数集合升级

每当一个新的元素添加到整数集合之中时，如果新元素的类型比现有类型要长时，那么需要进行升级，才能将新元素添加到整数集合中去。升级整数集合的步骤如下：

  1. 根据新元素的类型扩展数组的空间大小，分配对应的空间。
  2. 将原数组之中所有的元素的类型进行转换，将转换后的元素放到正确的位置上去。同时在放置的过程中，需要确保有序性质不变。
  3. 将新的元素添加到整数集合中去。

整数集合的升级是为了提升集合的灵活性以及节约内存的需要。

压缩列表

压缩列表用于实现列表键和哈希键。如果一个列表键中只包含少量的元素并且每个元素是小整数或者短字符串，会选择使用压缩列表来作为列表键的底层实现。

压缩列表实现

压缩列表由以下部分构成。

属性 类型 长度 用途
zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数
zltail uint32_t 4字节 记录表尾节点距离压缩列表的起始位置有多远
zllen uint16_t 2字节 压缩列表包含的节点个数
entryX 列表节点 压缩列表包含的各个节点
zlend uint8_t 1字节 用于标记压缩列表的末端

其中每个压缩列表节点可以保存一个字节数组或者整数值。每个压缩列表节点由以下部分构成。

属性 长度 作用
previous_entry_length 1字节或5字节 记录前一个节点的长度
encoding 1字节或2字节或5字节 记录content属性所保存的数据类型及长度
content 保存节点的值

对于previos_entry_length属性，如果前一个节点的长度小于254则占一个字节，否则占用五个字节，并且第一个字节会被设置为254，后四个节点则用于保存前一个节点的长度。通过previos_entry_length属性，程序可以通过指针运算计算出前一个节点的起始位置，实现从表尾到表头的遍历过程。

对于encoding属性，其记录了所保存数据的类型的以及长度。

如果编码最高位为00，01或者10，说明所保存的类型是字节数组。数组的长度由编码除去最高两位之后的记录。如果最高位为00，那么编码长度为1，储存的是小于等于63字节的字节数组。如果最高位为01，那么编码长度为2，储存的是小于等于16383字节的字节数组。如果最高位为10，那么编码长度为5，储存的是小于等于4294967295字节的字节数组。

如果最高位以11开头，那么说明保存的是整数值。保存的整数值类型与长度由除去最高两位的其他位记录。整数编码的方式如下：

编码 编码长度 保存的属性类型
11000000 1字节 int16_t类型整数
11010000 1字节 int32_t类型整数
11100000 1字节 int64_t类型整数
11110000 1字节 24位有符号整数
11111110 1字节 8位有符号整数
1111xxxx 1字节 xxxx就是保存的值，无需content

连锁更新

previos_entry_length属性记录了前一个节点的长度。在一些特殊的情况下，例如在一个压缩列表中存在连续多个长度介于250-253字节的节点e1-eN。因为这些节点的长度都小于254字节，记录这些长度的previos_entry_length只需要1字节。但是如果在e1之前新插入一个长度大于254字节的节点，会导致e1节点的previos_entry_length属性需要扩容到5个字节，但是以此类推会导致e1-eN的所有节点都会需要进行扩容。这种连续多次空间扩展操作被称为连锁更新。

当出现连锁更新的时候，最坏情况下需要对压缩列表进行N次重新分配空间操作，每次空间分配的最坏时间复杂度为O(N)，最终导致连锁更新的时间复杂度为O(N2)。虽然时间复杂度较高，但是因为在实际中这种情况不多见，即使出现如果被更新的节点不多，也不会对性能产生影响。