Redis数据结构源码

简单动态字符串

简单动态字符串（Simple Dynamic Strings，SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数，且在此基础上保证了二进制安全。

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实现的。举个例子，如果客户端执行命令：

redis> SET msg "hello world"
OK

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

键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串“msg”的SDS。
键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS。又比如，如果客户端执行命令：
```
redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3
```
那么Redis将在数据库中创建一个新的键值对，其中：
键值对的键是一个字符串对象，对象的底层实现是一个保存了字符串“fruits”的SDS。
键值对的值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别由三个SDS实现：第一个SDS保存着字符串“apple”，第二个SDS保存着字符串“banana”，第三个SDS保存着字符串“cherry”。除了用来保存数据库中的字符串值之外，SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的。

SDS的实现

每个sds.h/sdshdr结构表示一个SDS值：

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

我们看上面对于SDS数据类型的定义，在64位系统下，字段len和字段free各占4个字节，紧接着存放字符串。

len 保存了SDS保存字符串的长度
buf[] 数组用来保存字符串的每个元素
free 记录了 buf 数组中未使用的字节数量

Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点。

有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。
内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。

展示了一个SDS示例：

  | sdshdr   |
  | free   0 |
  | len    5 |
  | buf      |  =》 ['R']['E']['D']['I']['S']['\0']
  

free属性的值为0，表示这个SDS没有分配任何未使用空间。
len属性的值为5，表示这个SDS保存了一个五字节长的字符串。
buf属性是一个char类型的数组，数组的前五个字节分别保存了’R’、’e’、’d’、’i’、’s’五个字符，而最后一个字节则保存了空字符’\0’。 SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

SDS与C字符串的区别

根据传统，C语言使用长度为N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一个元素总是空字符’\0’。 C语言使用的这种简单的字符串表示方式，并不能满足Redis对字符串在安全性、效率以及功能方面的要求，接下来的内容将详细对比C字符串和SDS之间的区别，并说明SDS比C字符串更适用于Redis的原因。

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

因为C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为O（N）。

和C字符串不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O（1）。设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，使用SDS无须进行任何手动修改长度的工作。

通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O（N）降低到了O（1），这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。例如，因为字符串键在底层使用SDS来实现，所以即使我们对一个非常长的字符串键反复执行STRLEN命令，也不会对系统性能造成任何影响，因为STRLEN命令的复杂度仅为O（1）。

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。举个例子，/strcat函数可以将src字符串中的内容拼接到dest字符串的末尾：

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

因为C字符串不记录自身的长度，所以strcat假定用户在执行这个函数时，已经为dest分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。

与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。

举个例子，SDS的API里面也有一个用于执行拼接操作的sdscat函数，它可以将一个C字符串拼接到给定SDS所保存的字符串的后面，但是在执行拼接操作之前，sdscat会先检查给定SDS的空间是否足够，如果不够的话，sdscat就会先扩展SDS的空间，然后才执行拼接操作。

  | sdshdr   |
  | free   0 |
  | len    5 |
  | buf      |  =》 ['R']['E']['D']['I']['S']['\0']
  

例如，如果我们执行：

sdscat(s," Cluster");

那么sdscat将在执行拼接操作之前检查s的长度是否足够，在发现s目前的空间不足以拼接”Cluster”之后，sdscat就会先扩展s的空间，然后才执行拼接”Cluster”的操作，拼接操作完成之后的SDS

  | sdshdr   |
  | free   13 |
  | len    13 |
  | buf      |  =》 ['R']['E']['D']['I']['S'][' ']['C']['l']['u']['s']['t']['e']['r']['\0']
  

sdscat不仅对这个SDS进行了拼接操作，它还为SDS分配了13字节的未使用空间，并且拼接之后的字符串也正好是13字节长，这种现象既不是bug也不是巧合，它和SDS的空间分配策略有关

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

正如前两个小节所说，因为C字符串并不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组（额外的一个字符空间用于保存空字符）。因为C字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作：

如果程序执行的是增长字符串的操作，比如拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小——如果忘了这一步就会产生缓冲区溢出。
如果程序执行的是缩短字符串的操作，比如截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间——如果忘了这一步就会产生内存泄漏。

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

空间预分配

空间预分配用于优化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。

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

惰性空间释放

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

二进制安全

C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

为了确保Redis可以适用于各种不同的使用场景，SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但它们一样遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的数据的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的SDS可以重用一部分库定义的函数。

通过遵循C字符串以空字符结尾的惯例，SDS可以在有需要时重用函数库，从而避免了不必要的代码重复。

SDS新结构

动态字符串问题

动态字符串该结构是否有改进的空间呢？我们从一个简单的问题开始思考：不同长度的字符串是否有必要占用相同大小的头部？一个int占4字节，在实际应用中，存放于Redis中的字符串往往没有这么长，每个字符串都用4字节存储未免太浪费空间了。我们考虑三种情况：短字符串，len和free的长度为1字节就够了；长字符串，用2字节或4字节；更长的字符串，用8字节。这样确实更省内存，但依然存在以下问题。

问题1：如何区分这3种情况？问题2：对于短字符串来说，头部还是太长了。以长度为1字节的字符串为例，len和free本身就占了2个字节，能不能进一步压缩呢？

对于问题1，我们考虑增加一个字段flags来标识类型，用最小的1字节来存储，且把flags加在柔性数组buf之前，这样虽然多了1字节，但通过偏移柔性数组的指针即能快速定位flags，区分类型，也可以接受；对于问题2，由于len已经是最小的1字节了，再压缩只能考虑用位来存储长度了。结合两个问题，5种类型（长度1字节、2字节、4字节、8字节、小于1字节）的SDS至少要用3位来存储类型（23 ＝8），1个字节8位，剩余的5位存储长度，可以满足长度小于32的短字符串。

SDS新实现

在Redis 5.0中，我们用如下结构来存储长度小于32的短字符串：

struct __attribute__ ((__packed__))sdshdr5 {
    unsigned char flags; /* 低3位存储类型, 高5位存储长度 */
    char buf[];/*柔性数组，存放实际内容*/
};

sdshdr5结构中，flags占1个字节，其低3位（bit）表示type，高5位（bit）表示长度，能表示的长度区间为0～31（25 -1），flags后面就是字符串的内容。

在Redis的源代码中，对类型的宏定义如下：

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

在Redis 5.0中，sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下：

struct __attribute__((__packed__))sdshdr8 {
    uint8_t len; /* 已使用长度，用1字节存储 */
    uint8_t alloc; /* 总长度，用1字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr16 {
    uint16_t len; /*已使用长度，用2字节存储*/
    uint16_t alloc; /* 总长度，用2字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr32 {
    uint32_t len; /*已使用长度，用4字节存储*/
    uint32_t alloc; /* 总长度，用4字节存储*/
    unsigned char flags;/* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};
struct __attribute__((__packed__))sdshdr64 {
    uint64_t len; /*已使用长度，用8字节存储*/
    uint64_t alloc; /* 总长度，用8字节存储*/
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];/*柔性数组，存放实际内容*/
};

可以看到，这4种结构的成员变量类似，唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下。

len ：表示buf中已占用字节数。
alloc ：表示buf中已分配字节数，不同于free，记录的是为buf分配的总长度。
flags ：标识当前结构体的类型，低3位用作标识位，高5位预留。
buf ：柔性数组，真正存储字符串的数据空间。结构最后的buf依然是柔性数组，通过对数组指针作“减一”操作，能方便地定位到flags。

源码中的__attribute__((packed))需要重点关注。一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐，而用packed修饰后，结构体则变为按1字节对齐。以sdshdr32为例，修饰前按4字节对齐大小为12(4×3)字节；修饰后按1字节对齐，注意buf是个char类型的柔性数组，地址连续，始终在flags之后。

这样做有以下两个好处。

节省内存，例如sdshdr32可节省3个字节（12-9）。
SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针。因为此时按1字节对齐，故SDS创建成功后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过(char*)sh+hdrlen得到buf指针地址（其中hdrlen是结构体长度，通过sizeof计算得到）。修饰后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过buf[-1]找到flags，因为此时按1字节对齐。若没有packed的修饰，还需要对不同结构进行处理，实现更复杂。

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

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

链表在Redis中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）。

链表和链表节点的实现

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

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函数则用于对比链表节点所保存的值和另一个输入值是否相等。

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

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

字典

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

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

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

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

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

举个例子，当我们执行命令：

redis> SET msg "hello world"
OK

字典的实现

Redis字典实现依赖的数据结构主要包含了三部分：字典、哈希表、哈希表节点。字典中嵌入了两个Hash表，Hash表中的table字段存放着Hash表节点，Hash表节点对应存储的是键值对。 Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

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

typedef struct dictht {
    // 哈希表数组 指针数组，用于存储键值对
    dictEntry **table;
    // 哈希表大小 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数组的哪个索引上面。

sizemask字段用来计算键的索引值，sizemask的值恒等于size–1。我们知道，索引值是键Hash值与数组总容量取余之后的值，而Redis为提高性能对这个计算进行了优化，具体计算步骤如下。

第1步：人为设定Hash表的数组容量初始值为4，随着键值对存储量的增加，就需对Hash表扩容，新扩容的容量大小设定为当前容量大小的一倍，也就是说，Hash表的容量大小只能为4,8,16,32…。而sizemask掩码的值就只能为3,7,15,31…，对应的二进制为11,111,1111,11111…，因此掩码值的二进制肯定是每一位都为1。
第2步：索引值=Hash值&掩码值，对应Redis源码为：idx=hash&d->ht[table].sizemask，其计算结果等同Hash值与Hash表容量取余，而计算机的位运算要比取余运算快很多。

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

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union{
        void *val;  // db.dict中的val
        uint64_tu64;
        int64_ts64;
        double d;  // db.expires中存储过期时间 Redis新增
    } v;  // 值，是个联合体
    // 当Hash冲突时，指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

Hash表中元素结构体整体占用24字节，key字段存储的是键值对中的键。v字段是个联合体，存储的是键值对中的值，在不同场景下使用不同字段。例如，用字典存储整个Redis数据库所有的键值对时，用的是*val字段，可以指向不同类型的值；再比如，字典被用作记录键的过期时间时，用的是s64字段存储；当出现了Hash冲突时，next字段用来指向冲突的元素，通过头插法，形成单链表。 key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。 next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。

Redis字典实现除了包含前面介绍的两个结构体Hash表及Hash表节点外，还在最外面层封装了一个叫字典的数据结构，其主要作用是对散列表再进行一层封装，当字典需要进行一些特殊操作时要用到里面的辅助字段。 Redis中的字典由dict.h/dict结构表示：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    //rehash标识。默认值为-1，代表没进行rehash操作；不为-1时，代表正进行rehash操作，存储的值表示Hash表ht[0]的rehash操作进行到了哪个索引值
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 当前运行的迭代器数 Redis新增
    unsigned long iterators; 
} dict;

字典这个结构体整体占用96字节，其中type字段，指向dictType结构体，里面包含了对该字典操作的函数指针

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;

Redis字典这个数据结构，除了主数据库的K-V数据存储外，还有很多其他地方会用到。例如，Redis的哨兵模式，就用字典存储管理所有的Master节点及Slave节点；再如，数据库中键值对的值为Hash类型时，存储这个Hash类型的值也是用的字典。在不同的应用中，字典中的键值对形态都可能不同，而dictType结构体，则是为了实现各种形态的字典而抽象出来的一组操作函数。 type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
privdata字段，私有数据，配合type字段指向的函数一起使用。
ht字段，是个大小为2的数组，该数组存储的元素类型为dictht，虽然有两个元素，但一般情况下只会使用ht[0]，只有当该字典扩容、缩容需要进行rehash时，才会用到ht[1]，rehash介绍详见5.3.2节。
rehashidx字段，用来标记该字典是否在进行rehash，没进行rehash时，值为-1，否则，该值用来表示Hash表ht[0]执行rehash到了哪个元素，并记录该元素的数组下标值。
iterators字段，用来记录当前运行的安全迭代器数，当有安全迭代器绑定到该字典时，会暂停rehash操作。Redis很多场景下都会用到迭代器，例如：执行keys命令会创建一个安全迭代器，此时iterators会加1，命令执行完毕则减1，而执行sort命令时会创建普通迭代器，该字段不会改变

哈希算法

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

Redis计算哈希值和索引值的方法如下：

#使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFunction(key);
#使用哈希表的sizemask属性和哈希值，计算出索引值
#根据情况不同，ht[x]可以是ht[0]或者ht[1]
index = hash & dict->ht[x].sizemask;

举个例子，如果我们要将一个键值对k0和v0添加到字典里面，那么程序会先使用语句：

hash = dict->type->hashFunction(k0);

计算键k0的哈希值。

假设计算得出的哈希值为8，那么程序会继续使用语句：

index = hash&dict->ht[0].sizemask = 8 & 3 = 0;

计算出键k0的索引值0，这表示包含键值对k0和v0的节点应该被放置到哈希表数组的索引0位置上。

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

MurmurHash算法最初由Austin Appleby于2008年发明，这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

MurmurHash算法目前的最新版本为MurmurHash3，而Redis使用的是MurmurHash2，关于MurmurHash算法的更多信息可以参考该算法的主页：http://code.google.com/p/smhasher/。

解决键冲突

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

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

举个例子，假设程序要将键值对k2和v2添加到哈希表里面，并且计算得出k2的索引值为2，那么键k1和k2将产生冲突，而解决冲突的办法就是使用next指针将键k2和k1所在的节点连接起来。

因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。

rehash

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

扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行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做准备。

跳跃表

有序集合在生活中较常见，如根据成绩对学生进行排名、根据得分对游戏玩家进行排名等。对于有序集合的底层实现，我们可以使用数组、链表、平衡树等结构。数组不便于元素的插入和删除；链表的查询效率低，需要遍历所有元素；平衡树或者红黑树等结构虽然效率高但实现复杂。Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树，然而其实现却远比红黑树简单。

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

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

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

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

举个例子，fruit-price是一个有序集合键，这个有序集合以水果名为成员，水果价钱为分值，保存了130款水果的价钱：

redis> ZRANGE 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有序集合的所有数据都保存在一个跳跃表里面，其中每个跳跃表节点（node）都保存了一款水果的价钱信息，所有水果按价钱的高低从低到高在跳跃表里面排序：

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

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

跳跃表的实现

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

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

typedef struct zskiplistNode {
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    // robj *obj;
    sds ele;
} zskiplistNode;

该结构体包含如下属性。

ele：用于存储字符串类型的数据。
score：用于存储排序的分值。是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。
backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点——backward指向NULL，从后向前遍历跳跃表时使用。
level：为柔性数组。每个节点的数组长度不一样，每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1～64之间的值作为level数组的大小，这个大小就是层的“高度”。

level数组的每项包含以下两个元素。

forward：指向本层下一个节点，尾节点的forward指向NULL。
span：用于记录两个节点之间的距离。forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多。

跳跃表是Redis有序集合的底层实现方式之一，所以每个节点的ele存储有序集合的成员member值，score存储成员score值。所有节点的分值是按从小到大的方式排序的，当有序集合的成员分值相同时，节点会按member的字典序进行排序。

除了跳跃表节点外，还需要一个跳跃表结构来管理节点，Redis使用zskiplist结构体，定义如下：

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

该结构体包含如下属性。

header：指向跳跃表头节点。头节点是跳跃表的一个特殊节点，它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值，ele值为NULL，score值为0；也不计入跳跃表的总长度。头节点在初始化时，64个元素的forward都指向NULL，span值都为0。
tail：指向跳跃表尾节点。
length：跳跃表长度，表示除头节点之外的节点总数。
level：跳跃表的高度。

通过跳跃表结构体的属性我们可以看到，程序可以在O(1)的时间复杂度下,快速获取到跳跃表的头节点、尾节点、长度和高度。

整数集合

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

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

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

在两种情况下，底层编码会发生转换。一种情况为当元素个数超过一定数量之后（默认值为512），即使元素类型仍然是整型，也会将编码转换为hashtable，该值由如下配置项决定：

set-max-intset-entries 512

另一种情况为当增加非整型变量时，例如在集合中增加元素’a’后，testSet的底层编码从intset转换为hashtable：

redis> sadd testSet  'a'
(integer) 1
redis> object encoding testSet
"hashtable"

整数集合的实现

整数集合（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），然后才能将新元素添加到整数集合里面。

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

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
将新元素添加到底层数组里面。因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O（N）。

降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。举个例子，对于一个整数集合来说，即使我们将集合里唯一一个真正需要使用int64_t类型来保存的元素4294967295删除了，整数集合的编码仍然会维持INTSET_ENC_INT64，底层数组也仍然会是int64_t类型的

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。压缩列表ziplist本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表（quicklist）数据结构存储，而快速链表就是双向链表与压缩列表的组合。

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么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），每个节点可以保存一个字节数组或者一个整数值。

Redis使用字节数组表示一个压缩列表，压缩列表结构

zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最多有232 -1个字节。
zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节。
zllen：压缩列表的元素个数，占2个字节。zllen无法存储元素个数超过65535（216 -1）的压缩列表，必须遍历整个压缩列表才能获取到元素个数。
entryX：压缩列表存储的元素，可以是字节数组或者整数，长度不限。
zlend：压缩列表的结尾，占1个字节，恒为0xFF。

假设char*zl指向压缩列表首地址，Redis可通过以下宏定义实现压缩列表各个字段的存取操作。

//zl指向zlbytes字段
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//zl+4指向zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//zl+zltail指向尾元素首地址；intrev32ifbe使得数据存取统一采用小端法
#define ZIPLIST_ENTRY_TAIL(zl)                                               ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) 

//zl+8指向zllen字段
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//压缩列表最后一个字节即为zlend字段
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

了解了压缩列表的基本结构，我们可以很容易地获得压缩列表的字节长度、元素个数等，那么如何遍历压缩列表呢？对于任意一个元素，我们如何判断其存储的是什么类型呢？我们又如何获取字节数组的长度呢？

quicklist

quicklist是Redis 3.2中新引入的数据结构，能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义，quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。当ziplist节点个数过多，quicklist退化为双向链表，一个极端的情况就是每个ziplist节点只包含一个entry，即只有一个元素。当ziplist元素个数过少时，quicklist可退化为ziplist，一种极端的情况就是quicklist中只有一个ziplist节点。

Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。现在list只是用quiklist保存

quicklist实现

quicklist是一个由ziplist充当节点的双向链表。

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

其中head、tail指向quicklist的首尾节点；count为quicklist中元素总数；len为quicklist Node（节点）个数；fill用来指明每个quicklistNode中ziplist长度，当fill为正数时，表明每个ziplist最多含有的数据项数 fill取负数时，必须大于等于-5。我们可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小。实际上每个ziplist节点所占的内存会在该值上下浮动；考虑quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩，通过修改参数list-compress-depth进行配置，即设置compress参数，该项的具体含义是两端各有compress个节点不压缩。

quicklistNode是quicklist中的一个节点，其结构如下：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10;     /* more bits to steal for future usage */
} quicklistNode;

其中，prev、next指向该节点的前后节点；zl指向该节点对应的ziplist结构；sz代表整个ziplist结构的大小；encoding代表采用的编码方式：1代表是原生的，2代表使用LZF进行压缩；container为quicklistNode节点zl指向的容器类型：1代表none，2代表使用ziplist存储数据；recompress代表这个节点之前是否是压缩节点，若是，则在使用压缩节点前先进行解压缩，使用后需要重新压缩，此外为1，代表是压缩节点；attempted_compress测试时使用；extra为预留。

Stream

消息队列是分布式系统中不可缺少的组件之一，主要有异步处理、应用解耦、限流削峰的功能。目前应用较为广泛的消息队列有RabbitMQ、RocketMQ、Kafka等。Redis在5.0.0版本中也加入了消息队列的功能，这就是Stream。

Redis Stream的结构主要由消息、生产者、消费者、消费组4部分组成。

Redis中的消息，通过如下指令可以创建一个消息流并向其中加入一条消息：

xadd mystream1 * name hb age 20

其中，mystream1为Stream的名称；*代表由Redis自行生成消息ID；name、age为该消息的field；hb、20则为对应的field的值。每个消息都由以下两部分组成。

每个消息有唯一的消息ID，消息ID严格递增。
消息内容由多个field-value对组成。生产者负责向消息队列中生产消息，消费者消费某个消息流。消费者可以归属某个消费组，也可以不归属任何消费组。当消费者不归属于任何消费组时，该消费者可以消费消息队列中的任何消息。

消费组是Stream的一个重要概念，具有以下特点。

每个消费组通过组名称唯一标识，每个消费组都可以消费该消息队列的全部消息，多个消费组之间相互独立。
每个消费组可以有多个消费者，消费者通过名称唯一标识，消费者之间的关系是竞争关系，也就是说一个消息只能由该组的一个成员消费。
组内成员消费消息后需要确认，每个消息组都有一个待确认消息队列（pending entry list，pel），用以维护该消费组已经消费但没有确认的消息。
消费组中的每个成员也有一个待确认消息队列，维护着该消费者已经消费尚未确认的消息。

Stream实现

Redis源码对于listpack的解释为A lists of strings serialization format，一个字符串列表的序列化格式，也就是将一个字符串列表进行序列化存储。Redis listpack可用于存储字符串或者整型。

listpack由4部分组成：Total Bytes、Num Elem、Entry以及End，下面介绍各部分的具体含义。

Total Bytes为整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes。
Num Elem为listpack中的元素个数，即Entry的个数，占用2个字节，值得注意的是，这并不意味着listpack最多只能存放65535个Entry，当Entry个数大于等于65535时，Num Elem被设置为65535，此时如果需要获取元素个数，需要遍历整个listpack。
End为listpack结束标志，占用1个字节，内容为0xFF。
Entry为每个具体的元素。 Entry为listpack中的具体元素，其内容可以为字符串或者整型，每个Entry由3部分组成，每部分的具体含义如下。 Encode为该元素的编码方式，占用1个字节，之后是内容字段content，二者紧密相连。

yangjava

Redis数据结构源码

Redis数据结构源码

简单动态字符串

SDS的实现

SDS与C字符串的区别

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

杜绝缓冲区溢出

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

空间预分配

惰性空间释放

二进制安全

兼容部分C字符串函数

SDS新结构

动态字符串问题

SDS新实现

链表

链表和链表节点的实现

字典

字典的实现

哈希算法

解决键冲突

rehash

跳跃表

跳跃表的实现

整数集合

整数集合的实现

升级

降级

压缩列表

压缩列表的构成

quicklist

quicklist实现

Stream

Stream实现

Search

微信好友

Table of Contents