深入Redis系列（二）Redis底层数据结构：动态字符串、链表、字典、跳跃表和压缩列表

本文内容参考《redis设计与实现》一书总结归纳而得，归于合集： redis知识汇总

01 简单动态字符串

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（simple dynamic
string，SDS）的抽象类型，并将 SDS用作Redis 的默认字符串表示。

在Redis里面，C字符串只会作为字符串字面量（string literal）用在一些无须对字符串值进行修改的地方，比如打印日志：

redisLog(REDIS_WARNING,"Redis is now ready to exit,bye bye...");

当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis
就会使用SDS来表示字符串值，比如在Redis的数据库里面，包含字符串值的键值对在底层都是由SDS实现的。

如果客户端执行命令：

SET msg "hello world"

Redis将在数据库中创建一个新的键值对，其中：

键是一个字符串对象，对象的底层实现是一个保存着字符串msg的SDS。

值也是一个字符串对象，底层实现是一个保存着字符串hello world的SDS。

又如：

RPUSH fruits "apple" "banana" "cherry"

Redis将在数据库中创建一个新的键值对，其中：

键是一个字符串对象，对象的底层实现是一个保存着字符串fruits的SDS。

值是一个列表对象，列表对象包含三个SDS。

SDS的定义

SDS定义在头文件sds.h中，是一个结构体：

struct sdshdr {    int len; // 记录buf数组中已经使用的有效字节数（不包含空字符），等于SDS所保存的字符串长度        int free; // 记录buf数组中未使用字节的数量        char buf[]; // 字节数组，保存字符串（有空字符），长度为buf=len+free+1}

free属性的值为0，表示这个SDS没有分配任何未使用空间。 len属性的值为5，表示这个SDS保存了一个五字节长的字符串。

buf属性是一个char类型的数组，数组的前五个字节分别保存了Redis五个字符，而最后一个字节则保存了空字符’\0’。

SDS与C字符串的区别

区别1：常数复杂度获取字符串长度

和C字符串不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1)。

区别2：杜绝缓冲区溢出

C字符串不检查缓冲区，因此可能会出现缓冲区溢出，例如使用strcat函数时：

char *strcat(char *dest, const char *src);

如果dest的空间不足，不能容纳下dest+src个字节的长度，则会溢出。

区别3：减少修改字符串时带来的内存重分配次数

SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。

通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

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

其中，额外分配的未使用空间数量由以下公式决定：

如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS
len属性的值将和free属性的值相同。举个例子，如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存空字符）。

如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度为30MB+1MB+1byte

示例：

执行sdscat之前的SDS：

执行：

sdscat(s, " Cluster");

执行之后的SDS：buf的长度为free+len+1=27

惰性空间释放

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

举个例子，sdstrim函数接受一个SDS和一个C字符串作为参数，移除SDS中所有在C字符串中出现过的字符。

示例：

执行之前：

执行：

sdstrim(s, "XY");

执行之后：

02 链表

链表和链表节点的实现

链表节点在头文件adlist.h中定义，是一个结构体：

typedef struct listNode {    // 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 节点值    void *value;}listNode; // 本质是一个双向链表

链表在头文件adlist.h中定义，也是一个结构体：

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;

03 字典

字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。

在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。

字典经常作为一种数据结构内置在很多高级编程语言里面，但Redis所使用的C语言并没有内置这种数据结构，因此Redis构建了自己的字典实现。

字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

哈希表补充：

哈希表：也叫做散列表。是根据关键字（键）和值直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值
value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做哈希表（散列表）。哈希表的关键思想是使用哈希函数，将键
key 和值 value 映射到对应表的某个区块中。

哈希函数的作用： 将关键字（键，key）映射为值（哈希地址，value，数组下标）。

哈希冲突

哈希冲突：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) =
Hash(key2)，这种现象称为哈希冲突。

解决：

开放地址法：指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。

H(i) = (Hash(key) + F(i)) \% m, i = 1, 2, 3, ..., n (n ≤ m - 1)F(i)：冲突解决方法Hash(key)：哈希值m：哈希表长

线性探测法/ 二次探测法/ 伪随机序列

链地址法：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。

字典的实现

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

在dict.h中定义：

typedef struct dictht {  // 哈希表数组  dictEntry **table;  // 哈希表数组大小  unsigned long size;  // 哈希表大小掩码，用于计算索引值  // 总是等于size-1，作用：让索引始终落在0~size-1之间  unsigned long sizemask;  // 该哈希表已有节点的数量(已有的键值对数量)  unsigned long used;} dictht;

哈希节点dictEntry

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

typedef struct dictEntry {// 键    void *key;// 值，联合，可以用以下三种类型中的一种来表示值的类型    union(void *val;        uint64_tu64;        int64_ts64;    }V;// 指向下个哈希表节点，形成链表；作用：采用链地址法来解决哈希冲突    struct dictEntry *next;} dictEntry;

字典dict

typedef struct dict {    // 类型特定函数    dictType *type;    // 私有数据    void *privdata;    // 哈希表    dictht ht[2];    // rehash 索引    // 当rehash不在进行时，值为-1int rehashidx; /* rehashing not in progress if rehashidx ==-1 */} dict;

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

type 属性是一个指向 dictType 结构的指针，每个
dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。

privdata 属性则保存了需要传给那些类型特定函数的可选参数。

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;

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht
哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。

rehashidx记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。

哈希算法

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

计算方法：

hash = dict->type->hashFunction(key); // 计算key的哈希值index = hash & dict->ht[x].sizemark; // 使用sizemask和哈希值计算索引值，x可为0或1，计算出的index即为键值对在ht[x]数组的所在位置下标

示例

以size=4，sizemark=3的字典为例：

假设计算后的哈希值为hash(k0)=8，则索引为index = 8 & 3 = (1000) & (0011) = 0000 = 0。

键冲突

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

Redis的哈希表使用链地址法（separate
chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。

Rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load
factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：

如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n次方。

如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的 2^ n次 方。

将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash
做准备。

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

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

2.服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

其中哈希表的负载因子可以通过公式计算：

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

渐进式rehash

rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

这样做的原因在于，如果ht[0]里只保存着四个键值对，那么服务器可以在瞬间就将这些键值对全部rehash到ht[1]；但是，如果哈希表里保存的键值对数量不是四个，而是四百万、四千万甚至四亿个键值对，那么要一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

因此，为了避免 rehash
对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash
到ht[1]。

渐进rehash步骤

以下是哈希表渐进式rehash的详细步骤：

1.为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

2.在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示 rehash 工作正式开始。

3.在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

4.随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式
rehash 而带来的庞大计算量。

渐进rehash执行期间的哈希表操作

因为在进行渐进式rehash
的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。

另外，在渐进式 rehash
执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

04 跳跃表

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

跳跃表支持平均 O（logM）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

05 整数集合

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

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

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

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

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

length属性记录了整数集合包含的元素数量，也即是contents数组的长度。

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

如果 encoding属性的值为INTSET_ENC_INT16，那么
contents就是一个int16_t类型的数组，数组里的每个项都是一个int16_t类型的整数值（最小值为-32768，最大值为32767）。

如果 encoding 属性的值为INTSET_ENC_INT32，那么 contents 就是一个int32
t类型的数组，数组里的每个项都是一个int32_t类型的整数值（最小为-2147483648，最大值为2147483647）。

如果encoding属性的值为INTSET_ENC_INT64，那么contents就是一个int64
t类型的数组，数组里的每个项都是一个int64_t类型的整数值（最小值为-9223372036854775808，最大值为9223372036854775807）。

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

步骤分为三步：

1.根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

2.将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。

3.将新元素添加到底层数组中

升级的好处

提升灵 活性 & 节约内存

因为C语言是静态类型语言，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。

但是，因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将int16_t、int32_t
或者int64_t类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。

降级

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

06 压缩列表

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

例如，执行以下命令将创建一个压缩列表实现的列表键：

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer)6redis> OBJECT ENCODING lst"ziplist"

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

构成部分如下：

列表节点

列表节点entry的组成部分如下：

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

08 对象

Redis
并没有直接使用上面的数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。

通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。

对象的类型

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

Redis中的每个对象都由一个redis.h/redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性：

// redis.h/redisObjecttypedef struct redisObject {    // 类型，对应redis的五大数据类型    unsigned type:4;    // 编码，底层实现采用哪种数据结构    unsigned encoding:4;    // 记录对象最后一次被程序访问的时间    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */    // 引用计数    int refcount;    // 指向底层实现数据结构的指针    void *ptr;} robj;

type属性为下面常量中的一个：

/* Object types */#define REDIS_STRING 0 // 字符串对象#define REDIS_LIST 1 // 列表对象#define REDIS_SET 2 // 集合对象#define REDIS_ZSET 3 // 有序集合对象#define REDIS_HASH 4 // 哈希对象

对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种，因此：

当我们称呼一个数据库键为字符串键时，我们指的是“这个数据库键所对应的值为字符串对象”；

当我们称呼一个键为列表键时，我们指的是“这个数据库键所对应的值为列表对象”。

对数据库键使用TYPE命令时，返回该键对应值对象的类型。

# 键为字符串对象，值为字符串对象redis> SET msg "hello world"OKredis> TYPE msgstring

# 键为字符串对象，值为列表对象redis> RPUSH numbers 1 3 5
(integer)6redis> TYPE numberslist

# 键为字符串对象，值为哈希对象redis> HMSET profile name Tom age 25 career Programmer OKredis> TYPE profile hash

# 键为字符串对象，值为集合对象redis> SADD fruits apple banana cherry 
(integer)3 redis> TYPE fruits set