Redis设计与实现-数据结构

Posted on   |   In   |     |   visitors

虽然说之前也使用过Redis这个久负盛名的NoSQL数据库，但是也仅仅停留在用得阶段，并没有对其的设计原理和实现进行深究，对Redis的印象也只是停留在它是一个基于内存的k-v键值存储数据库，经常被用来做系统的缓存方案。但是知道这些对我来说并不够，便找了本书结合网上的源码一起看，本文是基于《Redis设计与实现》书籍第一部分的mini版阅读笔记，方便以后回顾。

概述

Redis数据库里面的键值对都是由对象组成的，其中：

  • 数据库键总是一个字符串对象。
  • 数据库键的值value则可以是：字符串对象、列表对象、哈希对象、集合对象、有序集合对象这五种对象中的任意一种。

第一部分主要是介绍实现五种对象的最底层数据结构，以及每种对象分别对应有哪些数据结构实现方式。

数据结构

难怪数据结构在计算机的基础学科中占据那么重要的地位，无论是数据库领域的存储还是要寻找合适的算法实现，都是跟数据结构密不可分。Redis中最底层设计的数据结构主要有：简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。下面逐一说明：

简单动态字符串（sds）

简称SDS（simple dynamic string），sds没有采用C语言中的字符串，而是自己定义了sds，在sds.h中定义的数据结构为：

1
2
3
4
5
6
7
8
9
10
struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

c字符串与SDS字符串之间的区别如下：

c字符串 SDS
获取字符串长度的复杂度为O(N)。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。 API是安全的，不会造成缓冲区溢出。
修改字符串长度N次必然需要执行N次内存重分配。 修改字符串长度N次最多需要执行N次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 string.h 库中的函数。 可以使用一部分 string.h 库中的函数。

链表（list）

链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器等等。链表由链表节点组成，在adlist.h/listNode中定义了节点的数据结构，如下：

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

一个链表会有许多的节点，所以只定义节点数据结构当然不行，Redis在adlist.h/list 中定义了持有链表的数据结构，这样操作链表会更加方便，代码如下：

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

小结如下：

  • 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
  • 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

字典（dict）

字典是一种用于保存键值对的抽象数据结构，在Redis中的应用相当广泛，比如Redis的数据库就是使用字典作为底层实现的，对数据库的增删改查也是构建在对字典的操作之上的。
Redis的字典主要有哈希表实现而成，而哈希表中又有若干个哈希表节点，在dict.h/dictht 中定义了哈希表的结构：

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

table属性是个数组，数组每个元素都是一个指向dictEntry节点的指针，每个dictEntry保存的是一个键值对。而在dict.h/dictEntry中定义了哈希表中节点的数据结构：

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

当然有这些数据结构还不够，还需要对哈希表和哈希表节点进行管理，于是有字典结构，在dict.h/dict中定义了字典结构，这就如同adlist.h/list中定义了链表结构一样，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表,字典只使用ht[0],ht[1]则是在rehash的时候使用
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

如图所示为一个普通状态下的字典：

字典小结：

  • Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
  • 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
  • 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。

跳表（zskiplist）

记得之前在看levelDB源码的时候，想起levelDB在内存中的memtable的核心结构就是用到了跳表，现在再看Redis的时候发现Redis的底层数据结构也用到了跳表，这里不回顾跳表算法了，只谈Redis中跳表的实现方式。
Redis中跳表的实现是由redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义， 其中 zskiplistNode 结构用于表示跳跃表节点， 而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针， 等等。
redis.h/zskiplistNode中定义的节点数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层，每个跳表节点都会有若干层
    struct zskiplistLevel {
        // 指向表尾方向的前进指针
        struct zskiplistNode *forward;
        // 跨度，两个节点之间的距离
        unsigned int span;
    } level[];
} zskiplistNode;

redis.h/zskiplist中定义的跳表结构如下：

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

跳表小结：

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

整数集合（instet）

当一个集合只包含整数值元素，并且这个集合元素数量不多时，redis就会使用整数集合作为集合建的底层实现。
在 intset.h/intset 中定义了一个整数集合的数据结构：

1
2
3
4
5
6
7
8
9
10
11
typedef struct intset {
    // 编码方式，根据不同的编码方式来确定contents中元素的类型
    uint32_t encoding;
    // 集合包含的元素数量，即使contents数组的长度
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

每当要在整数集合中添加一个整数，这个整数的类型的长度比现有的所有元素的类型长度都长时，整数集合就要进行升级（upgrade），然后才能将新元素添加到整数集合中。
整数集合小结：

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型， 改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存，因为只会在需要的时候进行升级。
  • 整数集合只支持升级操作， 不支持降级操作。

压缩列表（ziplist）

当一个列表键只包含少量列表项，而且每个列表项要么是小整数值要么就是长度比较短的字符串，那么Redis就会用压缩列表来做列表键的底层实现。
压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。
下图是压缩列表的构成部分：

zlbytes:记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用。
zltail:记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen:当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX:压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend:（十进制 255 ），用于标记压缩列表的末端。

其中，压缩列表节点的构成如下图：

previous_entry_length:以字节为单位， 记录了压缩列表中前一个节点的长度。
encoding:记录了节点的 content 属性所保存数据的类型以及长度.
content:负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

压缩列表小结：

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高。

对象

Redis 并没有直接使用上述数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统， 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。
Redis 使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时， 我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。Redis 中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性：

1
2
3
4
5
6
7
8
9
typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // ...
} robj;

字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。其中对于int编码的字符串对象的一些操作可以int编码转换为raw编码，比如APPEND命令，embstr也是如此。
说一下三种字符串编码方式的区别：如果一个字符串对象保存的是整数值，则直接用int编码；如果一个字符串对象保存的是字符串值，但是长度大于等于39，则用raw编码；否则长度小于39就用embstr编码。

列表对象

列表对象的编码可以是 ziplist（压缩列表） 或者 linkedlist（链表） 。
当列表对象可以同时满足以下两个条件时， 列表对象使用 ziplist 编码：

  1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
  2. 列表对象保存的元素数量小于 512 个；
    不能满足这两个条件的列表对象需要使用 linkedlist 编码。

    哈希对象

    哈希对象的编码可以是 ziplist 或者 hashtable 。
    ziplist 编码的哈希对象使用压缩列表作为底层实现， 每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。如下图所示：

    hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存，如下图所示：

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

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
  2. 哈希对象保存的键值对数量小于 512 个；
    不能满足这两个条件的哈希对象需要使用 hashtable 编码。

集合对象

集合对象的编码可以是 intset 或者 hashtable 。
intset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。
另一方面， hashtable 编码的集合对象使用字典作为底层实现， 字典的每个键都是一个字符串对象， 每个字符串对象包含了一个集合元素， 而字典的值则全部被设置为 NULL ，意思就是只保留key而不需要value。

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

  1. 集合对象保存的所有元素都是整数值；
  2. 集合对象保存的元素数量不超过 512 个；
    不能满足这两个条件的集合对象需要使用 hashtable 编码。

有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist 。
ziplist 编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。
压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。
skiplist 编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：

1
2
3
4
5
6
typedef struct zset {
    zskiplist *zsl;//保证有序性
    dict *dict;//保证获取某个对象以O（1）的时间复杂度
} zset;

使用跳表和dict字典两种数据结构的有序集合对象，兼具了跳表和字典两种数据结构的优点特性，由于会共享元素的成分和分值，所以也不会出现内存浪费。

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

  1. 有序集合保存的元素数量小于 128 个；
  2. 有序集合保存的所有元素成员的长度都小于 64 字节；
    不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

内存回收

C语言本身不具备内存回收，Redis 在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。redis通过redisObject中的refcount属性维护这一特性：

1
2
3
4
5
 typedef struct redisObject {
    // ...
    // 引用计数
    int refcount;
} robj;

当创建对象时，refcount等于1，当对象被另外一个新对象用时，加1，不再被新对象用时减1，引用值为0时，对象占用的内存会被释放。

对象共享

除了用于实现引用计数内存回收机制之外， 对象的引用计数属性还带有对象共享的作用。
在 Redis 中， 让多个键共享同一个值对象需要执行以下两个步骤：

  1. 将数据库键的值指针指向一个现有的值对象；
  2. 将被共享的值对象的引用计数增一。

共享对象机制对于节约内存非常有帮助，数据库中保存的相同值对象越多，对象共享机制就能节约越多的内存。
共享对象和目标对象完全相同的情况下，程序才会将共享对象用作键的值对象，而一个共享对象保存的值越复杂，验证共享对象和目标对象是否相同所需的复杂度就会越高，消耗的 CPU 时间也会越多，因此尽管共享更复杂的对象可以节约更多的内存，Redis 只对包含整数值的字符串对象进行共享。

最后

本文大部分内容来自于原书籍的节选，所以如果想知道更详细内容可以直接阅读书籍。

-EOF-