Redis设计与实现-数据结构

1 简单动态字符串(SDS)

Redis中有两种字符串表示：

①、C字符串：C字符串只会作为字符串字面量（string literal），用在一些无须对字符串值进行修改的地方，如打印日志。
②、简单动态字符串：简单动态字符串（simple dynamic string, SDS）是redis构建一种字符串的抽象类型，是redis的默认字符串表示。如字符串键值对、缓冲区等都有SDS实现。

1.1 SDS的定义

sds.h/sdshdr结构表示一个SDS的值，如：

struct sdshdr {
    // 记录bug数组汇总已使用字节的数量.
    // 等于SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数组中未使用字节的数量.
    unsigned int free;
    // 字节数组，用于保存字符串.
    char buf[];
};

注：SDS遵循C字符串以空字符（'\0'）结尾，但这个字节的空间不计算在SDS的len属性中。

1.2、SDS字符串相对于C字符串的优点

常数复杂度获取字符串长度
- C字符串，没有记录自身的长度信息，获取C字符串长度时需进行遍历，其复杂度为O(N)。
- SDS字符串，有len属性，获取长度的复杂度为O(1)。
杜绝缓冲区溢出: SDS相对于C字符串，根据其空间分配策略，杜绝了发生缓冲区溢出的可能性。
减少修改字符串时带来的内存重新分配次数: SDS通过未使用空间free记录，实现空间预分配和惰性空间释放两种优化策略。
二进制安全
兼容部分C字符串函数

1.2.1 空间预分配

空间预分配用于优化SDS的字符串增长操作，当SDS的API对SDS进行修改，并且需要对SDS进行空间扩展时，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用空间。

分配策略：

若对SDS修改过后，len属性的值小于1MB，则分配与len属性同样大小的未使用空间，即此时len和free属性大小一致。
若对SDS修改过后，len属性的值大于1MB，则分配1MB的未使用空间。

1.2.2 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作，当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重新分配来回收缩短后多出来的字节，而是使用free属性将这些字节数量记录起来，并等待将来使用。

2 链表

链表作为一种常用的数据结构，在Redis中应用广泛，如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。此外，还有打不与订阅、慢查询、监视器等功能也用到了链表。

注：Redis的链表为双向链表。

2.1 链表和链表节点的实现

链表节点，使用一个adlist.h/listNode结构来表示：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

多个listNode可以通过prev和next指针组成双向链表，如下图所示：

链表，使用adlist.h/list结构表示：

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结构和三个listNode结构组成的链表。

3 字典

字典，又称为符号表（symbol table）、关联数组（assiciative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。字典中每个键都是独一无二的。

字典的应用：字典在Redis的应用广泛，如Redis的数据库就是使用字典来作为底层实现的。此外字典还是哈希键的底层实现之一。

3.1 字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表结点，而每个哈希表结点就保存了一个字段中的键值对。

3.1.1 哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义：

typedef struct dictht {
    // 哈希表数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个结构保存着一个键值对。
    dictEntry **table;
    // 哈希表大小.
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值.
    // 总是等于size-1.
    unsigned long sizemask;
    // 该哈希表已有结点的数量.
    unsigned long used;
} dictht;

示例：下图为一个大小为4的空哈希表。（没有任何键值对）

3.1.2 哈希表结点

哈希表结点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个哈希表结点,形成链表,用以解决哈希冲突的问题.
    struct dictEntry *next;
} dictEntry;

示例：下图是通过next指针,将两个指引着相同的键k1和k0连接的数据结构.

3.1.3 字典

Redis中的字典由dict.h/dict结构表示：

typedef struct dict {
    // 类型特定函数.Redis会为用途不同的字典设置不同的类型特定函数。
    dictType *type;
    // 私有数据.保存了需要传给那些类型特定函数的可选参数。
    void *privdata;
    // 哈希表.包含了两个项的数组，每个项都是dictht哈希表，通常，字典只使用ht[0]哈希表，ht[1]哈希表只会在ht[0]进行rehash时使用。
    dictht ht[2];
    // rehash索引.记录rehash的进度，若当前没有进行rehash，那么它的值为-1.
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

其中type和privdata属性是针对不同类型的键值对,为创建多态字典而设置。

type特定函数结构：

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;

示例：下图为普通状态的下的字典示例。

3.2 哈希算法

要将一个新的键值对添加到字典中时，程序需先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表结点放到哈希表数组的指定索引上面。

Redis计算哈希值方式？

使用字典设置的哈希函数，计算键key的哈希值：

1	hash = dict->type->hashFunction(key);

Redis计算索引值的方式？

根据哈希表的sizemask属性和哈希值计算出索引值，其中根据情况不同，ht[x]可以使ht[0]或ht[1]。

1	index = hash & dict->ht[x].sizemask;

注：当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

3.3 解决键冲突

当有两个或者以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。

Redis怎样解决键冲突？

Redis的哈希表使用链地址法来解决键冲突。

每个哈希表结点都有一个next指针，多个哈希表结点可以用next指针构成一个单向链表，被分配到同一个索引上的多个结点可以用这个单向链表连接起来，解决键冲突的问题。

注：由于dictEntry结点组成的链表没有指向链表表尾的指针，所以程序总是将新节点添加到链表的表头位置（复杂度为O(1)）

示例：k2与k1发生了键冲突，k2后添加，如下图所示。

3.4 rehash

随着操作的不断执行，哈希表保存的键值对会逐渐增减，为了让哈希表的负载因子维持在一个合理的范围内，需对哈希表的大小进行相应的扩展或收缩。这个过程就是rehash。

Redis是怎样对字典的哈希表执行rehash的（rehash的步骤）？

①、为字典的h[1]哈希表分配空间。
- 扩展操作：ht[1]的大小为第一个大于等于ht[0].used*2的2^n(2的n次方幂)；
- 收缩操作：ht[1]的大小为第一个大于等于ht[0].used的2^n。
②、将保存在ht[0]中的所有键值对rehash到ht[1]上面，rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
③、当ht[0]包含的所有键值对都前移到了ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

示例：假设ht[0].used当前的值为4，要对进行扩展操作，则ht[1]的大小为4*2=8，刚好为2^3，所以ht[1]哈希表的大小设置为8.

哈希表的扩展与收缩都与负载因子有关，那么什么是负载因子呢？怎样计算负载因子？

Redis的负载因子为哈希表以保存结点的数量与哈希表的大小的比值，计算方法如下：

1	load_factor = ht[0].used / ht[0].size

示例：对于一个大小为512，包含256个键值对的哈希表说，这个哈希表的负载因子为：

load_factor = 256 / 512 = 0.5

什么情况下程序会自动对哈希表执行扩展操作？

①、服务器没有在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1.
②、服务器正在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5.

注：在执行BGSAVE或者BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而避免在子进程存在期间进行哈希表扩展操作，避免不必要的内存写入，最大限度地节约内存。

什么情况下程序会对哈希表执行收缩操作？

当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

3.5 渐进式rehash

扩展或收缩哈希表需要将ht[0]里面的键值对rehash到ht[1]里面，但是这个rehash动作并不是一次性、集中式完成的，而是分多次、渐进式地完成的。

为什么要渐进式完成rehash？

为了避免大量键值对rehash对服务器性能造成影响。采用分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

哈希表是怎样渐进式rehash的（rehash的详细步骤）？

①、为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表、
②、在字典中维持一个rehashidx，并将它的值设置为0，表示rehash工作正式开始。
③、在rehash进行期间，每次对字段执行添加、删除、查找、更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后，程序将rehashidx属性的值增加一。
④、随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]上，这是程序将rehashidx属性设为-1，表示rehash操作已完成。

渐进式rehash执行期间会涉及到ht[0]和ht[1]两个哈希表，是怎样操作的呢？

针对删除、查找、更新操作，会在两个哈希表上进行，例如，查找一个键时，程序会在ht[0]上查找，若没有找到，会继续到ht[1]里面进行查找。
对于新增操作，新增加到字典的键值对一律被保存到ht[1]里面，而ht[0]则不再进行任何操作。

4 跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

Redis使用跳跃表作为有序集合键的底层实现之一，若一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。此外，跳跃表还在集群节点中用作内部数据结构。

4.1 跳跃表结点的实现

Redis跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义。

跳跃表示例如下：

zskiplistNode结构用于表示跳跃表的结点。

typedef struct zskiplistNode {
    // 成员对象.示例图中o1，o2，o3是结点所保存的成员对象。
    robj *obj;
    // 分值. 跳跃表中，结点按照各自所保存的分值从小到大排列。
    double score;
    // 后退指针.指向当前的结点的前一个结点，后退指针在程序从表尾想表头遍历时使用。示例图上用BW标识结点的后退指针。
    struct zskiplistNode *backward;
    // 层.每个层都有两个属性：前进指针和跨度。
    struct zskiplistLevel {
        // 前进指针.前进指针用于访问表尾方向的其他节点。示例图上的带有数字的剪头就表示前进指针。
        struct zskiplostNode *forward;
        // 跨度.跨度记录了前进指针所指向结点和当前结点的距离。示例图上箭头上的数字就表示跨度。
        unsigned int span;
    } level[];
} zskiplistNode;

4.1.1 层

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度。一般来说，层的数量越多，访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候，程序都根据幂次定律(power law，越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度。

示例：下图为三个高度分别为1层、3层、5层的节点。

4.1.2 前进指针

每个层都有一个指向表尾党项的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。

跳跃表是怎样遍历所有节点的呢？

示例图如下：

①、迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中第二个节点。
②、在第二个结点时，程序沿着第二层的前进指针移动到表中第三个节点。
③、在第三个节点时，程序沿着第二层的前进指针移动到表中的第四个结点。
④、当程序在此沿着第四个节点的前进指针移动时，它碰到了一个NULL，程序知道这时已经到达了跳跃表的表尾，结束遍历。

注：遍历操作只使用前进指针就能完成。

4.1.3 跨度

层的跨度（level[i].span属性）用于记录两个结点之间的距离，两个结点之间跨度越大，他们相距得就越远；指向null的所有前进指针的跨度都为0，因为他们没有指向任何节点。

跨度实际上是用来计算排位的：在查找某个结点的过程中，将访问过的所有层的跨度累计起来，得到的结果就是目标结点在跳跃表中的排位。

4.1.4 后退指针

节点的后退指针(backward属性)用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

4.1.5 分值和成员

节点的分值(score属性)是一个double类型的浮点数，跳跃表中的所有结点都按分值从小到大来排序。

节点的成员对象(obj属性)是一个指针，他指向一个字符串对象，而字符串对象则保存着一个SDS值。

注：同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但多个结点保存的分值却可以是相同的。分值相同的结点将按照成员对象在字典序中的大小来进行排序，成员对象较小的结点会排在前面（靠近表头的方向）。

4.2 跳跃表的实现

仅靠多个跳跃表节点就可以组成一个跳跃表，但通过一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或快速地获取跳跃表节点的数量等信息。

zskiplist结构如下：

typedef struct zskiplist {
    // header 指向跳跃表的表头节点。
    // tail 指向跳跃表的表位节点.
    struct zskiplistNode *header, *tail;
    // 记录跳跃表的长度，即跳跃表目前包含结点的数量（表头节点不计算在内）
    unsigned long length;
    // level 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
    int level;
} zskiplist;

注：level表头节点的层高并不计算在内。

五、整数集合

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

（注：整数集合是只包含整数值元素的集合。）

5.1 整数集合的实现

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

每个intset.h/intset结构表示一个整数集合：

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

整数集合的底层实现是什么？

整数集合的底层是通过数组（contents属性）实现的，整数集合的每个元素都是contents数组的一个数组项(item)，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

注：

①、数组元素在底层是有进行从小到大的排序的。

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

encoding属性的取值包括以下内容：

INTSET_ENC_INT16:表示int16_t类型的数组，数组里面每个项都是一个int16_t类型的整数值（2^15 ~2^(15)-1）。
INTSET_ENC_INT32:表示int32_t类型的数组，数组里面每个项都是一个int32_t类型的整数值(2^31 ~2^(31)-1)。
INTSET_ENC_INT64:表示int64_t类型的数组，数组里面每个项都是一个int64_t类型的整数值(2^63 ~2^(63)-1)。

5.2 升级

当添加新元素到整数集合中时，新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先升级，然后才能将新元素添加到整数集合里面。

Redis是怎样升级整数集合并添加新元素的呢（升级及添加新元素的步骤）？

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

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

注：每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中又有的元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)。

升级时新元素的摆放位置，要引发升级，那么要么新元素大于所有现有元素，要么小于现有所有元素，因此摆放位置应该在数组的两端。

为什么要进行升级，而不是直接采用int64_t类型？

①、提高灵活性。
②、节约内存。

5.3 降级

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

六、压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

压缩列表(ziplist)在Redis的应用场景有哪些？

①、当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

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

6.1 压缩列表的构成

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。

压缩列表的各个组成部分如下图：

下表中记录了各个组成部分的类型、长度以及用途。

示例：包含三个节点的压缩列表

其中：

zlbytes的属性值为0x50,表示压缩列表的总长为80.
zltail属性的值为0x3c，表示有一个指向压缩列表起始地址的指针p，在指针p加上偏移量60，就可以计算出表尾节点entry3的地址。
zllen属性值为0x3，表示压缩列表包含三个节点。
zlend属性值为特殊值，用于标记压缩列表的末端。

6.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值。

字节数组可以是以下三中长度的其中一种：
- 长度小于等于63（2^6-1）字节的字节数组。
- 长度小于等于16383（2^14-1）字节的字节数组。
- 长度小于等于4294967295（2^32-1）字节的字节数组。
整数值可以是以下六种长度的其中一种：
- 4位长，介于0~12之间的无符号整数；
- 1字节长的有符号整数；
- 3字节长的有符号整数；
- int16_t类型整数；
- int32_t类型整数；
- int64_t类型整数。

压缩列表结点的组成部分如下：

6.2.1 previous_entry_length

previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度，previous_entry_length属性的长度可以是1字节或者5字节。

若前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节，前一节点的长度就保存在这一个字节里面。
若前一节点的长度大于等于254字节，那么previoud_entry_length属性的长度为5字节，其中第一字节会被设置为0xFE，而后的四个字节则用于保存前一节点的长度。

根据previous_entry_length属性可以计算得到前一个节点的起始地址。通过这一原理，即可实现从表尾向表头遍历。

6.2.2 encoding

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

字节数组编码：一字节、两字节或者五字节，encoding最高位为00、01、10表示字节数组编码，除去最高两位后表示数组的长度。

整数编码：一字节，encoding最高位为11，除去最高两位后的其他位记录整数值的类型和长度。

6.2.3 content

节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由encoding属性决定。

示例1：以下示例展示了一个保存字节数组的节点示例。

其中：

encoding的最高两位为00，表示一个字节数组。
encoding的后六位001011记录了字节数组的长度为11.
content属性保存着节点的值“hello world”

示例2：以下示例展示了一个保存整数值的节点示例。

其中：

encoding表示节点保存的是int16_t类型的整数值。
content属性保存着节点的值10086.

6.3 连锁更新

什么情况下会发生连锁更新？

比如当前所有结点长度均小于254字节情况下，新添加一个长度大于254字节的节点到压缩列表的表头，此时需对压缩列表执行空间重分配操作，扩展后面的previous_entry_length属性空间。

定义：Redis将这种特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”。

连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为O(N^2)。

参考资料

redis设计与实现（第二版）黄健宏