Redis底层数据结构

简单动态字符串(SDS)

redis构建了一种名为简单动态字符串(SDS)的数据结构,并将SDS作为redis的默认字符串表示。
除了用来保存字符串值外，SDS还被用作缓冲区：AOF模块中的AOF持久化，以及客户端状态中的输入缓冲区
SDS的结构:

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];

};

free 属性的值为 0 ，表示这个 SDS 没有分配任何未使用空间
len 属性的值为 5 ，表示这个 SDS 保存了一个五字节长的字符串
buf 属性是一个 char 类型的数组，数组的前五个字节分别保存了 ‘R’ 、 ‘e’ 、 ‘d’ 、 ‘i’ 、 ‘s’ 五个字符，而最后一个字节则保存了空字符 ‘\0’

SDS具有的优势：

常数复杂度获取字符串长度

因为SDS数据结构中保存了字符串的长度,所以与C语言遍历字符数组相比，SDS获取字符串长度的时间复杂度为O(1)

防止缓冲区溢出

C语言不记录自身长度带来的另一个问题是容易造成缓冲区溢出,比如对字符串append操作时,SDS会检查SDS的空间是否满足修改的需求，如果不满足的话，SDS会进行扩容操作, 防止缓冲区溢出，在SDS中,buf数组长度不一定就是字符串数量加一,数组可以包含未使用的字节,SDS使用free属性记录未使用空间，因为内存重分配是一个比较耗时的操作，当需要扩容时，SDS实现空间预分配操作，如果对SDS修改后的长度小于1MB，这里的修改后的长度是指的append操作之后的长度，SDS会分配和len长度一样的空间作为预备空间，当修改后的长度大于1MB，那么redis会为SDS分配1MB的未使用空间，当SDS进行类似trim操作时，SDS实现惰性空间释放操作，就是说，SDS并没有释放多出来的free空间，如果将来要对字符串增长的话，那么未使用空间将会派上用场

二进制安全

C字符串中的字符必须符合某种编码，除了字符串的末尾，字符串里面是不能包含空字符的，否则会被认为是字符串结尾，这些限制了C字符串只能保存文本数据，而不能保存像图片这样的二进制数据 , 而SDS的API都会以处理二进制的方式来处理存放在buf数组里的数据，不会对里面的数据做任何的限制。SDS使用len属性的值来判断字符串是否结束，而不是空字符

兼容部分C字符串函

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

链表

链表是一种比较常见的数据结构了，特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度，但随机访问困难。许多高级编程语言都内置了链表的实现，但是C语言并没有实现链表，所以Redis实现了自己的链表数据结构，链表在redis中应用非常广泛，列表的底层实现就是链表，redis的发布与订阅，慢查询，监视器等功能都用到了链表。 Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

链表节点的定义如下：

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

}
listNode;

多个listNode可以通过prev和next指针组成双端链表,如下图:

虽然仅仅使用多个 listNode 结构就可以组成链表，但使用 adlist.h/list 来持有链表的话，操作起来会更方便：

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;

list 结构为链表提供了表头指针 head 、表尾指针 tail ，以及链表长度计数器 len ，而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数：

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

链表特性

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

字典

Redis 数据库底层就是用字典实现的，对数据库的增、删、改、查操作都是构建在对字典的操作之上，比如：

1 2	`set msg "hello world" OK`

创建一个 key 为 “msg”，value 为 “hello world” 的键值对，保存在代表数据库的字典中
字典还是哈希键的底层实现之一：当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时， Redis 就会使用字典作为哈希键的底层实现。
哈希表结构定义

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 属性则记录了哈希表目前已有节点（键值对）的数量。
sizemask 属性的值总是等于 size - 1 ，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

哈希节点

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）的问题。

typedef struct dict {
    // 和类型相关的处理函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引，当rehash不再进行时，值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器数量
    unsigned long iterators; /* number of iterators currently running */
} dict;

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

rehashidx也是rehash相关的,rehash的操作不是瞬间完成的,rehashidx记录着rehash的进度,如果目前没有正在进行rehash,它的值为-1

哈希算法

当将一个新的键值对插入到字典,需要重新计算索引值,redis计算索引的方法是:

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

类似Java的HashMap,计算key的hash值,然后hash&(len-1),而redis的sizemask就是size-1

哈希冲突

当出现hash冲突时,redis使用的是链地址法来解决冲突,链地址法就是将冲突的节点构成一个链表放在该索引位置上,redis采用的是头插法,解决hash冲突的还有三种方法.分别是:开放地址法, 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）、再哈希法以及建立一个公共溢出区

rehash

随着不断的操作，hash表中的键值对可能会增多或减少，为了让哈希表的负载因子保持在一个范围内，需要对 hash表进行扩容或收缩，收缩和扩容的过程就叫 rehash。rehash 过程如下：

为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即是 ht[0].used 属性的值）
- 如果执行的是扩展操作，那么 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[0] ，将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备

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

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 ；
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5 ；
其中哈希表的负载因子可以通过公式：load_factor = ht[0].used / ht[0].size计算 ,比如说,对于一个大小为4,包含4个键值对的哈希表来说,这个哈希表的负载因子为:load_factor=4/4=1

根据BGSAVE命令或者BGREWRITEAOF命令是否正在执行,服务器执行扩展操作所需要的负载因子并不相同,这是因为在执行BGSAVE命令或BGREWRITEAOF命令过程中,Redis需要创建当前服务器的子进程,而大多数操作系统都是采用写时复制(copy-on-write)技术来优化子进程的使用效率,所以在子进程存在期间,服务器会提高执行扩展操作所需要的负载因子,从而尽可能的避免在子进程存在期间进行哈希表扩展操作,这样可以避免不必要的内存写入操作,最大程度的节约内存.

渐进式rehash

当数据量大的时候一次性进行迁移会造成服务器在一段时间内定制服务,为了避免因为庞大的计算量导致服务器在一段时间内停止服务,redis采用渐进式将ht[0]键值对rehash到ht[1].

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

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

跳跃表

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

下面详细介绍跳跃表:

现在我们有个场景,想快速找到上图单链表中的这10歌元素,只能从头开始遍历,这样的查找效率很低,那么有没有提高查找效率的方法呢?如下图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引 7 的down指针可以找到原始链表的 7 。那现在怎么查找 10 这个元素呢

先在索引找1,4,7,9遍历到一级索引的9时,发现后继节点是13,比10大,于是不往下找了,而是通过9找到原始链表的9,然后再往后遍历找到了我们要找的10

那如果加二级索引呢？如下图所示，查找路径：1、7、9、10。是不是找 10 的效率更高了？这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率。

当数据量足够大时，效率提升会很大。如下图所示，假如有序单链表现在有1万个元素，分别是 0~9999。现在我们建了很多级索引，最高级的索引，就两个元素 0、5000，次高级索引四个元素 0、2500、5000、7500，依次类推，当我们查找 7890 这个元素时，查找路径为 0、5000、7500 … 7890，通过最高级索引直接跳过了5000个元素，次高层索引直接跳过了2500个元素，从而使得链表能够实现二分查找。由此可以看出，当元素数量较多时，索引提高的效率比较大，近似于二分查找。

跳表是可以实现二分查找的有序链表

更多跳表知识访问原链接:跳表

redis只有在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构

redis的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义，其中 zskiplistNode 结构用于表示跳跃表节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等

redis跳跃表

上图展示了一个跳跃表示例,位于图片最左边的是zskiplist结构,该结构包含以下属性:

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

位于 zskiplist 结构右方的是四个 zskiplistNode 结构，该结构包含以下属性：

层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

跳跃表节点

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

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

层

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

跨度

层的跨度（level[i].span 属性）用于记录两个节点之间的距离：两个节点之间的跨度越大，它们相距得就越远。

初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样 —— 遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

举个例子，下图用虚线标记了在跳跃表中查找分值为 3.0 、成员对象为 o3 的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为 3 ，所以目标节点在跳跃表中的排位为 3 。

后腿指针

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

分值和对象

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

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

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

zskiplist

通过使用一个 zskiplist 结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，又或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息，如下图所示。

zskiplist 结构的定义如下：

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

header 和 tail 指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为 O(1) 。

通过使用 length 属性来记录节点的数量，程序可以在 O(1) 复杂度内返回跳跃表的长度。

整数集合

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

举个例子，如果我们创建一个只包含五个元素的集合键，并且集合中的所有元素都是整数值，那么这个集合键的底层实现就会是整数集合：

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 数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

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

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：如果 encoding 属性的值为 INTSET_ENC_INT16 ，那么 contents 就是一个 int16_t 类型的数组，数组里的每个项都是一个 int16_t 类型的整数值（最小值为 -32,768 ，最大值为 32,767 ）。

下图是一个包含五个int16_t类型整数值的整数集合。

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

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

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

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

压缩列表

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

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

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

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

redis> OBJECT ENCODING lst
"ziplist"

因为列表键里面包含的都是 1 、 3 、 5 、 10086 这样的小整数值，以及 “hello” 、 “world” 这样的短字符串。

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

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

redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK

redis> OBJECT ENCODING profile
"ziplist"

压缩列表的构成

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

下图展示了压缩列表的各个组成部分。

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

压缩列表节点的构成

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成，如下图所示。

节点的 previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。
节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度
节点的 content 属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。
压缩列表是一种为节约内存而开发的顺序型数据结构。
压缩列表被用作列表键和哈希键的底层实现之一。
压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

Redis

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

二进制逻辑运算回顾 Previous

redis持久化 Next

Redis底层数据结构

Redis底层数据结构

简单动态字符串(SDS)

SDS具有的优势：

链表

链表特性

字典

哈希节点

哈希算法

哈希冲突

rehash

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

渐进式rehash

跳跃表

跳跃表节点

层

跨度

后腿指针

分值和对象

zskiplist

整数集合

压缩列表

压缩列表的构成

压缩列表节点的构成

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