详解Redis底层的数据结构

前言

工作中的业务系统大面积应用了Redis，一个NoSQL内存数据库。Redis的高性能、易用性，让它成为目前互联网公司中一个必不可少的工具。这也引起了我的兴趣更进一步去了解它，但由于自己不是专业的DBA，所有很少去接触Redis的复制、Sentinel、Cluster等高级特性的实战，所以接下来的文章中，将更多地去介绍Redis的数据结构和一些原理，为以后Redis的进一步理解打下基础。

本文主要介绍Redis底层的6种数据结构，分别是：

简单动态字符串；
链表；
字典；
跳跃表；
整数集合；
压缩列表；

简单动态字符串

作用

简单动态字符串(simple dynamic string)，下称SDS。SDS是Redis最常用的数据结构，没有之一。当Redis需要的是一个可能被修改的字符串时，它就会使用SDS来表示，比如在Redis的数据库中，包含字符串值的键值对在底层都是由SDS实现的。看下面：

1 2	redis> SET msg "Hello Redis." OK

键值对的键是一个字符串对象，对象的底层实现是一个保存着“msg”的SDS；
键值对的值也是一个字符串对象，对象的底层是一个保存着“Hello Redis.”的SDS；

又比如：

1 2	redis> RPUSH name "Robert" "Archerda" (integer) 2

键值对的键是一个字符串对象，底层实现是一个保存着“name”的SDS；
键值对的值是一个列表对象，列表对象包含了2个字符串对象，这2个字符串对象的底层分别是2个SDS，保存着“Robert”，“Archerda”；

除了用来保存字符串值外，SDS有以下用处：

用作缓冲区（buffer）
- AOF模块中的AOF缓冲区；
- 客户端状态的输入缓冲区；

定义

在sds.h中，对SDS的定义如下：

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

请看下面的实例解析：

上图展示了一个SDS实例：

len属性的值为5，说明这个SDS保存了一个5个字节长的字符串；
free属性的值为0，说明这个SDS没有分配未使用的空间；
buff是一个char型的数组，数组的前5个字节分别保存了’R’,’e’,’d’,’i’,’s’这5个字符，而最后一个字节则保存着’\0’字符；

注意，SDS遵循C字符串以空字符结尾的规范，这样可以使得SDS直接使用C函数库里面的一些方法，比如printf("%s", sds->buf);。但是保存空字符的这个字节不计算在len属性里面。而且，为空字符额外分配1字节的操作和把空字符添加到末尾都是SDS函数自动完成的，对SDS的使用者完全透明。

我们可以使用DEBUG OBJECT <key-name>来查看某个key占用了多少空间。比如：

redis> get msg
"Redis"
redis> DEBUG OBJECT msg
Value at:0x7ff7e45050d0 refcount:1 encoding:embstr serializedlength:6 lru:636632 lru_seconds_idle:25

这里，我们只关注 serializedlength : 6，说明msg这个键对应的值占用了6个字节，注意这里是包括了最后一个空字符的长度。

SDS与C字符串的区别

SDS与C字符串都是以空字符’\0’结尾，但是C字符串不满足Redis对于安全性、效率以及功能方面的要求。

常数复杂度获取字符串长度
- SDS获取字符串长度，只需要读取len属性的值就可以了，复杂度为O(1);
- C字符串获取字符串长度，需要遍历整个字符串来计算长度，复杂度为O(n);
杜绝缓冲区溢出
- 当SDS的API需要修改SDS时，API会先检查SDS的空间是否满足修改的要求，如果不满足，API会自动扩展SDS的空间，然后再进行操作；所以SDS不需要手动去修改SDS的空间大小，也不存在类似C函数strcat所存在的缓冲区溢出的问题；
减少修改字符串所带来的内存重分配次数
- C字符串底层总是用N+1长度的字符数组来保存一个长度为N的字符串，每当需要修改这个字符串的时候，比如trim或者append，程序需要先通过内存重分配操作来扩展或释放内存空间，否则会出现缓冲区溢出或内存泄露；
- 内存重分配 涉及复杂的算法，可能会需要执行系统调用，所以这是一个比较耗时的操作；
- Redis作为内存数据库，经常被用于对速度要求苛刻、数据被频繁修改的场景，如果每次修改字符串都需要内存重分配，那么很大可能对性能造成影响；所以SDS用free属性来解除了字符串长度和底层数组长度之间的关联；
二进制安全
- C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则会被认为是字符串结尾，使得它只能保存文本数据，而不能保存图片、音频等二进制数据。而SDS的API会以处理二进制的方式来处理SDS存放在buf数组里面的数据，程序不会对其中的数组做任何限制、过滤。通过二进制安全的SDS，使得Redis不仅能够保存文本数据，还可以保存任意格式的二进制数据。

链表

作用

链表提供了高效地节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。链表在Redis中的应用也非常广泛，比如Redis中的列表键的底层实现之一就是链表。举个例子，下面的integers列表键包含了1024个整数。integers列表键的底层实现就是一个链表，链表中的每个节点保存了一个整数值。

redis> LLEN integers
(integer) 1024
redis> LRANGE integers 0 10
 1) "12"
 2) "11"
 3) "10"
 4) "9"
 5) "8"
 6) "7"
 7) "6"
 8) "5"
 9) "4"
10) "3"
11) "2"

除了链表键以外，Redis以下的功能也使用了链表：

发布与订阅；
慢查询；
监视器；
保存多个客户端的状态信息；
构建客户端的输出缓冲区（output buffer）；

定义

每个链表节点使用一个adList.h/listNode结构来表示；如下，多个listNode通过prev指针和next指针来组成一个双端队列。

/*
 * 双端链表节点
 */
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

虽然使用多个listNode结构就可以组成链表，但是Redis使用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结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match函数则是用于实现多态链表所需的类型特定函数：

dup函数用于复制链表节点所保存的值；
free函数用于释放链表节点所保存的值；
match函数用于对比链表节点所保存的值和另一个输入值是否相等；

下图是1个list结构和3个listNode结构组成的链表。

Redis的链表实现的特性总结如下：

特性	描述
双端	链表的节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
无环	表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
带链表长度计数器	程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度是O(1)
多态	链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match这3个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

字典

作用

字典，是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每个键都是独一无二的，程序可以在字典中根据键查找到与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对等。

字典在Redis中的应用非常广泛，比如Redis的数据库就是使用字典作为底层来实现的，对数据库的增删查改操作也是在对字典的操作之上的。比如，当我们执行命令：

1 2	redis> set msg "hello redis." OK

这个时候，Redis在数据库中创建了一个键为”msg”，值为”hello redis.”的键值对时，这个键值对就保存在数据库的字典里面。

除了用来表示数据库之外，字典还是哈希键的底层实现之一。举个例子，website是一个包含10086个键值对的哈希键，这个哈希键的键都是一些数据库的名字，而键的值就是数据库的主页网址：

redis> HLEN website
(integer) 10086
redis> HGETALL website
1) "Redis"
2) "redis.io"
3) "MongoDB"
4）"mongodb.org"
# ...

website键的底层实现就是一个字典，字典中包含了10086个键值对，例如：

键值对的键为”Redis”，值为”redis.io”;
键值对的键为”MongoDB”，值为”mongodb.org”；

定义

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

哈希表

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

/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

table属性是一个数组，数组中的每一个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，也就是table数组的大小，而used属性则记录了哈希表目前已有节点的数量（也就是键值对的数量）。sizemark属性的值总是等于size - 1，这个属性和哈希值一起决定了一个键应该被放到table数组的哪个索引上。

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

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对。dictEntry的定义如下：

/*
 * 哈希表节点
 */
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。

next属性是执行另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突（collision）的问题（这个解决方式和JDK中HashMap解决hash冲突的方式是类似的）。

下图展示了如何通过next指针，将两个索引值相同的键k0和k1连接在一起：

字典

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

/*
 * 字典
 */
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

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

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

/*
 * 字典类型特定函数
 */
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属性则保存了需要传给那些特定函数的可选参数；

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

除了ht[1]外，另一个和rehash相关的属性就是rehashidx了，它记录了目前rehash的进度，如果目前没有rehash，那么它的值为-1.

下图展示了一个普通状态下（没有进行rehash）的字典：

跳跃表

作用

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且实现比平衡树简单，所以有不少程序都使用跳跃表来代替平衡树。

跳跃表是Redis有序集合键的底层实现之一。举个例子，fruit-price是一个有序集合，这个有序集合以水果名作为成员，水果价作为分值。

redis> ZRANCE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"
redis> ZCARD fruit-price
(integer) 130

fruit-price有序集合的所有数据都被保存在一个跳跃表里面，其中每个跳跃表节点都保存了一种水果的价格，所有水果按照价格从低到高在跳跃表里排序：

跳跃表的第一个元素的成员为”banana”，它的分值是5；
跳跃表的第二个元素的成员为”cherry”，它的分值是6.5；
跳跃表的第三个元素的成员为”apple”，它的分值是8；

和链表、字典等数据结构被广泛应用在Redis内部不同，Redis只在2个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部结构，除此之外，跳跃表在Redis内部没有其他用途。

定义

我们先看下面一个跳跃表：

跳跃表节点

跳跃表节点的实现由redis.h/zskiplistNode结构定义，如下：

/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

层
跳跃表节点的level数组可以包含多个元素，每个元素都包含了一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快；
每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越低）随机生成一个介于1~32之间的值作为level数组的大小，这个大小就是层的”高度”。
下图分别展示了2个高度为1层和3层的节点。
前进指针
每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于表头向表尾方向访问节点。
跨度
层的跨度（level[i].span属性）用于记录两个节点之间的距离；
1.两个节点之间的跨度越大，他们相距得就越远；
2.指向NULL的所有前进指针的跨度都为0，因为他们没有连向任何节点。
看上去，很容易以为跨度和遍历操作有关，但实际上并不是遍历操作只使用前进指针就可以完成，跨度其实是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
后退指针
节点的后退指针（backward属性）用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点都只有一个后退指针，所以每次只能后退到前一个节点。
分值和成员
节点的分值（score属性）是一个double类型的浮点数，跳跃表的所有节点都按照分值从小到大排序。
节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象里面存着一个SDS值。
在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点的分值却是可以相同的：分值相同的节点将按照对象在字典序中的大小来排序。

跳跃表

跳跃表由redis.h/zskiplist结构定义，如下：

*
 * 跳跃表
 */
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

header
指向跳跃表的表头节点。
tail
指向跳跃表的表尾节点。
level
记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不算在内）。
lenght
记录跳跃表的长度，也就是，跳跃表目前包含的节点的数量（表头节点的层数不算在内）。

通过使用lenght属相来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性不会被用到，所以图中略去了，只显示了表头节点的各个层。

整数集合

作用

整数集合（intset）是集合键的底层实现之一。举个例子，当我们创建了一个只包含5个元素的集合键时，并且集合中的所有元素都是整数值，那么这个集合键的底层实现就会是整数集合：

redis> SADD numbers 1 3 5 7 9
(integer) 5
redis> OBJECT ENCODING numbers
"intset"

定义

整数集合（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数组的一个项，各个项在数组中按值的大小有序地排列，并且数组中不包含重复项。
length属性记录了整数集合包含的元素数量，也即是contents数组的长度。

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

如果encoding属性的值为INTSET_ENC_INT16,那么contents就是一个int16_t类型的数组，数组里面每个项都是一个int16_t类型的整数值（-32768 <= int16_t <= 32767）;
如果encoding属性的值为INTSET_ENC_INT32,那么contents就是一个int32_t类型的数组，数组里面每个项都是一个int32_t类型的整数值（-2147483648 <= int32_t <= 2147483647）;
如果encoding属性的值为INTSET_ENC_INT64,那么contents就是一个int64_t类型的数组，数组里面每个项都是一个int64_t类型的整数值（-9223372036854775808 <= int64_t <= 9223372036854775807）;

下图展示了一个整数集合：

升级

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

升级intset需要3步：

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

举个例子，假设现有一个intset，如下图：

因为每个元素都占用16位的空间，所以intset的contents数组的大小为 16 * 3 = 48位，下图展示了intset的3个元素在这48位的位置：

现在，我们要把类型为int32_t的整数值65535添加到intset中。因为65535的类型int32_t比intset里面当前所有元素的类型都要长，所以在添加65535到intset之前，需要对intset进行升级。

升级首先要做的是，根据新类型的长度，以及intset元素的数量（包括要添加的新元素），对contents数组进行空间再分配。intset目前有3个元素，加上新元素65535，一共需要4个元素的空间，所以占用的空间大小是32 * 4 = 128位。如下图所示。虽然程序对contents数组进行了空间再分配，但是数组里面原有的3个元素1、2、3仍然是int64_t类型，这些元素还被保存在前48位上。

所以程序接下来要将这3个元素转换为int32_t类型，并将转换的元素放置到正确的位上，而且在放置元素的过程中，需要维持contents数组的有序性质不变。首先，因为元素3在1、2、3、65535这4个元素中排名第三，所以它将被移动到contents数组的索引2位置上，也就是数组64~95位上，如下图所示：

依次移动元素2、元素1、元素65535，最后排列如下图所示：

最后，程序将intset的encoding属性从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32，并将length从3改为4。

因为每次添加新元素都有可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行转换，所以向intset添加新元素的复杂度为 O(N)。

升级的好处：

提升intset的灵活性：因为C语言是静态类型，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据类型里面。但是因为intset可以通过自动升级来适应新元素，所以我们可以随意地将int16_t、int32_t、int64_t类型的整数放到集合中，而不必担心类型错误，这种做法非常灵活；
节约内存：想要一个数据同时保存int16_t、int32_t、int64_t这3种类型，最简单的方法就是用int64_t来保存，但是用int64_t来保存int16_t、int32_t，会出现浪费内存的情况。

此外，intset支持升级，但是不支持降级。

压缩列表

作用

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

127.0.0.1:6379> RPUSH lst 1 3 5 "hello" "redis"
(integer) 5
127.0.0.1:6379> OBJECT ENCODING lst
"ziplist"

再比如，下面将会创建一个ziplist实现的哈希键：

127.0.0.1:6379> HMSET profiles "name" "archerda" "age" 23
OK
127.0.0.1:6379> OBJECT ENCODING profiles
"ziplist"

ziplist构成

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

下图展示了ziplist的各个组成部分，表格则描述了各个组成部分的类型、长度以及用途。

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个ziplist占用的内存字节数：在堆ziplist进行内存重分配或者计算zlend的位置时使用
zltail	uint32_t	4字节	记录ziplist表尾节点距离ziplist的起始地址有多少字节：通过这个偏移量，程序无需遍历就可以确定表尾节点的地址
zllen	unint16_t	2字节	记录ziplist包含的节点数量：当这个属性的值小于UINT16_MAX(65535)时，这个属性的值就是ziplist包含的节点的数量；当这个值等于UINT16_MAX的时候，节点的真实数量需要遍历整个ziplist才能够计算出来
entryX	列表节点	不定	ziplist包含的各个节点，节点的长度由节点保存的内容决定
zlend	uint8_t	1字节	特殊值0xFF（十进制255），用于标记ziplist的末端

下图展示了一个压缩列表sample：

zlbytes=0x50（十进制80），表示ziplist的总长为80字节；
zltail=0x3c（十进制60），表示如果我们有一个指向ziplist起始地址的指针p，那么只要用指针p加上偏移量60，就可以计算出entry3的地址；
zllen=0x3（十进制3），表示ziplist有3个entry节点；

最后

到这里，Redis底层的7种数据结构就介绍完了，接下来开始介绍基于这7种数据结构而创建的5种对象。

参考文档

Redis设计与实现（第二版）