Redis中的数据结构

首先，我们需要指出的是String(字符串)、List(列表)、Hash(哈希)、Set(集合)和Zset(有序集合)并不是数据结构，这些都是Redis中常用的数据类型。所说的数据结构是指这些数据类型的底层实现方式。

Redis底层的数据结构一共有6种，其和数据类型的对应关系如下：

SDS

字符串在Redis中是很常用的，键值对中的键是字符串，值有时也是字符串。

Redis是使用C语言来实现的，但是它没有直接使用C语言中的char*字符串数组来实现字符串，而是自己封装了一个名为简单动态字符串(simple dynamic string，SDS)的数据结构来表示字符串，也就是说Redis的String数据类型的底层结构为SDS。

C语言字符串的缺陷

C语言的字符串其实就是一个字符数组，即数组中的每个元素都是字符串的一个字符。例如，下图就是字符串“xiaohupao”的char*字符数组的结构：

可以看到最后一个字符是“\0”。在C语言中，对字符串操作时，char*指针只是指向字符数组的起始位置，而字符数组的结尾位置就是使用“\0”表示，意思是指字符串的结束。

因此，在C语言标准库中字符串的操作函数，就是通过判断字符是不是“\0”，如果不是的话，说明字符串还没有结束，可以继续操作，如果是则说明字符串结束了，停止操作。

举个例子，C语言获取字符串长度的函数strlen，就是通过字符数组中的每一个字符，并进行计数，等遇到字符为“\0”后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度。可以看出，C语言获取字符串长度的时间复杂度为O(N)。

C语言的字符串用“\0”字符作为结尾标记有个缺陷。假设有个字符串中有个“\0”字符，这时在操作这个字符串就会提前结束，比如“xiao\0hupao”字符串，计算字符串长度的时候则会是4。

除此之外，用char*字符串中的字符必须符合某种编码(比如ASCII)。这些限制使得C语言的字符串只能保存文本数据，不能保存图像、音频、视频文件这样的二进制数据。

C语言标准库中字符串的操作函数是很不安全的，对程序员来说很不友好，稍不注意，就会导致缓冲区溢出。strcat函数是可以将两个字符串拼接在一起。

C语言的字符串是不会记录自身的缓冲区大小的，所以strcat函数假定程序员在执行这个函数时，已经为dest分配足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将会造成程序运行终止。

而且，strcat函数和strlen函数类似，时间复杂度也很高，也都需要通过遍历字符串才能得到目标字符串的末尾。然后对于strcat函数来说，还要再遍历源字符串才能完成追加，对字符串的操作效率不高。

综上所述，我们可以知道C语言中的字符串中的不足之处可以总结为：

获取字符串的长度的时间复杂度为O(N)
字符串的结尾是以“\0”字符标识，而且字符必须符合某种编码(例如ASCII)，只能保存文本数据，不能保存二进制数据；
字符串操作函数不搞笑且不安全，例如会发生缓冲区溢出，从而造成程序运行终止。

SDS的设计

如图为Redis5.0中SDS的数据结构：

结构中的每个成员变量分别介绍下：

len：SDS所保存的字符串长度。这样获取字符串长度的时候，只需要返回这个变量的值就行，时间复杂度只需要O(1)。
alloc：分配给字符串数组的空间长度。这样在修改字符串的时候，可以通过alloc-len计算出剩余的空间大小，然后用来判断空间是否满足修改需求，如果不满足的话，就会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出的问题。
flags：SDS类型，用来表示不同类型的SDS。一共设计了5中类型，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。
buf[]：字节数组，用来保存实际数据。不需要用“\0”字符来标识字符串结尾了，而是直接将其作为二进制数据处理，可以用来保存图片等二进制数据。它即可以保存文本数据，也可以保存二进制数据。

总的来说，Redis的SDS结构在原本字符数组之上，增加了三个原数据：len、alloc、flags，用来解决C语言字符串的缺陷。

O(1)复杂度获取字符串长度

C语言的字符串获取strlen函数，需要通过遍历方式来统计字符串长度，时间复杂度为O(N)。而Redis的SDS结构因为加入了len成员变量，那么获取字符串长度的时候，直接返回这个变量的值就行，所以时间复杂度只有O(1)。

二进制安全

因为SDS不需要使用“\0”字符来标识字符串结尾了，而且SDS的API都是以处理二进制的方式来处理SDS存放在buf[]里的数据，程序不会对其中的数据做任何限制，数据写入的时候什么样的，它被读取时就是什么样的。

通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，也可以保存任意格式的二进制数据。

不会发生缓冲区溢出

C语言的字符串标准库提供的字符串操作函数，大多数都是不安全的(例如strcat追加字符串函数)，因为这些函数把缓冲区大小是否满足操作的工作交由开发者来保证，程序内部并不会判断缓冲区大小是否足够用，当发生了缓冲区溢出就有可能造成程序异常结束。所以Redis的SDS结构中引入了alloc和len成员变量，这样SDS API通过alloc-len计算，可以算出剩余可用的空间大小，这样在对字符串做修改操作的时候，就可以由程序内部判断缓冲区大小是否足够用。而且，当缓冲区大小不够用时，Redis会自动将扩大SDS的空间大小，以满足修改所需要的大小。在扩展SDS空间之前，SDS API会优先检查未使用空间是否足够，如果不够的话，API不仅会SDS分配修改所需要的空间，还会给SDS分配额外的未使用空间。这样的好处是，下次在操作SDS时，如果是SDS空间，API就会直接使用未使用空间，而无须执行内存分配，有效的减少内存分配次数。所以，使用SDS即不需要手动修改SDS的空间大小，也不会出现缓冲区溢出的问题。

节省内存空间

SDS结构中有个flags成员变量，表示的是SDS类型。Redis一共设计了5种类型，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。这5种类型的主要区别就在于，它们数据结构中的len和alloc成员变量的数据类型不同，例如sdshdr16和sdshdr32这两个类型，它们的定义分别如下：

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};

可以看到sdshdr16类型的len和alloc的数据类型都是unit16_t，表示字符数组长度和分配空间大小不能超过2的16次方。sdshdr32则都是uint32_t，表示字符数组长度和分配空间大小不能超过2的32次方。

之所以SDS设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。

除了设计不同类型的结构体，Redis在编程上还使用了专门的编译优化来节省内存空间，即在struct声明了__attribute__((packed))，它的作用是：告诉编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐。例如，sdshdr16类型的SDS，默认情况下，编译器会按照16字节对齐的方生给变量分配内存，这意味着，即使一个变量的大小不到16字节，编译器也会给它分配16个字节。例如，假设下面这个结构体，它有两个成员变量，类型分别是char和int，如下所示：

#include <stdio.h>

 struct test1 {
    char a;
    int b;
 } test1;

int main() {
     printf("%lu\n", sizeof(test1));
     return 0;
}

这个结构体大小是8字节。这是因为默认情况下，编译器是使用字节对齐的方式分配内存，虽然char类型只占1个字节，但是由于成员变量有int类型，它占用了4个字节，所以在成员变量为char类型分配内存时，会分配4个字节，其中这多余的3个字节是为了字节对齐和被分配的，相当于有3字节被浪费掉了。

如果不想编译器使用字节对齐的方式进行分配内存，可以采用__attribute__ ((packed))属性定义结构体，这样一来，结构体实际占用多少内存空间，编译器就会分配多少空间。例如，使用__attribute__ ((packed))属性定义下面的结构体，同样包含char和int两个类型的成员变量，代码如下所示：

#include <stdio.h>

struct __attribute__((packed)) test2  {
    char a;
    int b;
 } test2;

int main() {
     printf("%lu\n", sizeof(test2));
     return 0;
}

这时候打印的结构为5(1个字节char+4个字节int)。

链表

Redis的list数据类型的底层实现之一就是链表。C语言本身也是没有链表这个数据结构的，所以Redis自己设计了一个链表数据结构。

链表节点结构设计

先来看看链表节点结构的样子：

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

有前置节点和后置节点，可以看出，这是一个双向链表。

链表结构设计

不过，Redis在listNode结构基础上又封装了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函数。

Redis的链表实现优点如下：

listNode链表节点带有prev和next指针，获取某个节点的前置节点或后置节点的时间复杂度只需要O(1)，而且这两个指针都可以指向NULL，所以链表是无环链表；
listNode结构因为提供了头指针head和表尾节点tail，所以获取链表的表头结点和表尾结点的时间复杂度为O(1)；
listNode结构因为提供了链表结点数量len，所以获取链表中的结点数量的时间复杂度只需要O(1)；
listNode链表使用void*指针保存节点值，并且可以通过list结构的dup、free、match函数指针为节点设置该结点类型特定的函数，因此链表节点可以保存不同类型的值。

链表也是有缺陷的，链表每个节点之间的内存都不是连续的，意味着无法很好利用CPU缓存。能很好利用CPU缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用CPU缓存来加速访问。因此，Redis的list数据类型在数据量比较少的情况下，会采用压缩列表作为底层数据结构的实现，压缩列表就是由数组实现的。

压缩列表

压缩列表是Redis数据类型为list和hash的底层实现之一。

当一个列表键(list)只包含少量的列表项，并且每个列表项都是小整数值，或者长度比较短的字符串，那么Redis就会使用压缩列表作为列表键(list)的底层实现。
当一个哈希值(hash)只包含少量键值对，并且每个键值对的键和值都是小整数值，或者长度比较短的字符串，那么Redis就会使用压缩列表作为哈希键(hash)的底层实现。

压缩列表结构设计

压缩列表是Redis为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类型于数组。

压缩列表在表头有三个字段：

zlbytes，记录整个压缩列表占用对内存字节数；
zltail，记录压缩列表尾部节点距离起始地址由多少字节，也就是列表尾的偏移量；
zllen，记录压缩列表包含的节点数量；
zlend，标记压缩列表的结束点，特殊值0xFF(十进制255)。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度为O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是O(N)了。

另外，压缩列表节点(entry)的构成如下所示：

压缩列表节点包含三部分内容：

prevlen，记录了前一个节点的长度；
encoding，记录了当前节点实际数据的类型以及长度；
data，记录了当前节点的实际数据。

当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及它们的大小会在prevlen和encoding这两个元素里保存不同的信息，这种根据数据大小进行对应信息保存的设计思想，正是Redis为了节省内存而采用的。

连锁更新

压缩列表除了查找复杂度高的问题，压缩列表在插入元素时，如果内存空间不够了，压缩列表还需要重新分配一块连续的内存空间，而这可能会引发连锁更新的问题。

压缩列表里的每个节点中的prevlen属性都记录了前一个结点的长度，而且prevlen属性的空间大小跟前一个结点长度值有关，比如：

如果前一个结点的长度小于254字节，那么prevlen属性需要用1字节的空间来保存这个长度值；
如果前一个结点的长度大于等于254字节，那么prevlen属性需要5字节的空间来保存这个长度值。

现在假设一个压缩列表中有多个连续的、长度在250~253之间的结点，如下图：

因为这些字节长度值小于254字节，所以prevlen属性需要用1字节的空间来保存这个长度值。

这时，如果将一个长度大于等于254字节的新节点加入到压缩列表头结点，即新结点将成为e1的前置结点，如下图：

因为e1结点的prevlen属性只有1个字节大小，无法保存新结点的长度，此时就需要对压缩列表的空间重新分配操作，并将e1的结点prevlen属性从原来的1字节大小扩展到5字节大小。

多米诺牌的效应就此开始。

e1原本的长度在250~253之间，因为刚才的扩展空间，此时e1的长度就大于等于254了，因此原本e2保存e1的prevlen属性也必须从1字节扩展至5字节大小。正如扩展e1引发了对e2扩展一样，扩展e2也会引发对e3的扩展，而扩展e3又会引发对e4的扩展…一直持续到结尾。

这种在特殊情况下产生的连续多次空间扩展操作就叫做连锁更新，就像多米诺骨牌的效应一样。

连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。所以说，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或者是元素变大了，压缩列表就会面临连锁更新的风险。

因此，压缩列表只会用于保存的结点数量不多的场景，只要结点数量足够小，即便发生连锁更新，也是能接收的。