本文内容参考《redis设计与实现》一书总结归纳而得。

本系列文章主要向大家介绍redis中的数据结构，主要借鉴《redis设计与实现》一书归纳其重点而写出的。这本书告诉了我们其实学习redis不只是学习怎么用redis，以及redis可以用在什么适用场景，更重要的是告诉我们redis服务如何使用这些数据结构提升其查询性能，作为一个服务器如何高效接收和处理客户端请求这样的网络通信操作，作为一个非关系型数据库如何设计，这些内容远远超过了redis本身。或者说这本书是在教我们学习数据结构，网络通信等，这才是这本书和本系列文章的本质和精髓。

下面我们正式开始第一节 的内容

简单动态字符串（SDS）

Redis构建了一种名为简单动态字符串SDS的抽象类型作为redis的字符串（string类型）存储的数据结构。

当我们执行一个命令

Set name zbp

Redis会创建2个SDS结构，分别用来存储键”name”和值”zbp”。

又或者是

Rpush fruits apple banana cherry

会创建4个SDS结构分别存储 apple、banana和cherry，并将这3个SDS对象经过封装为stringObj后写入到fruits对应的列表中。而键fruits也会被存在一个SDS结构中。

除了用来保存字符串之外，SDS还被用作缓冲区buffer，例如AOF缓冲区，客户端状态中的输入缓冲区等。

下面我们看看SDS的结构，它本质是一个sdshdr结构体：

struct sdshdr {

    int len; // 记录字符串的长度(buf数组已使用的字节数)

    int free;  // buf数组未使用的字节数

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

}

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，这样的好处是SDS可以直接重用一部分C字符串函数库的函数。

SDS的特性（比对C字符串和redis字符串）

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

因为每次修改redis字符串时SDS都会维护其中的len属性，直接取len属性即可获取长度。而对于C语言中的字符串获取长度需要遍历字符串序列，复杂度为O(n)。

2. 杜绝缓冲区溢出

当C字符串被分配了指定的长度之后，往这个字符串追加其他字符串时使得字符串超过了分配的空间时会发生溢出，溢出的部分会修改其他内存的数据。

例如里有两个在内存中紧邻着的C字符串s1和 s2，其中s1保存了字符串"Redis"，而s2则保存了字符串"MongoDB":

当执行一个追加字符串的函数时

strcat(s1, " Cluster");

字符串s1的数据会溢出到s2的空间，导致s2字符串被意外修改。

如果要避免这种情况，我们要在修改s1前修改其分配空间大小。

对于修改redis字符串而言，SDS的API会检查SDS空间是否满足修改的需求，不满足则会扩展其空间大小从而避免溢出。

3. 预分配空间和惰性空间释放

C字符串每次修改时，程序都要对保存这个C字符串的数组进行内存重新分配。

如果是增长字符串的操作（append），忘记扩展底层数组的空间会产生缓冲区溢出；

如果是缩短字符串的操作（trim），忘记释放掉字符串不使用的那部分空间会产生内存泄露；

而频繁的重新分配内存涉及复杂的算法并可能需要执行系统调用，是一个耗时的操作，对于redis这种速度要求严苛的数据库是不被允许的。

redis的SDS实现了空间预分配和惰性空间释放的优化策略：

空间预分配

当对SDS进行修改时（如增加字符串），SDS的API不仅会扩展底层数组buf所需空间，还会为SDS分配额外的未使用空间。规则如下：

对SDS进行修改之后，SDS的长度（也即是len属性的值）如果小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。举个例子，如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节。如果在追加一个5字节的字符串，由于未用完剩余的13字节空间，因此SDS不会再重新分配空间，减少了分配的次数。

如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

通过预分配空间可以减少连续执行字符串增长操作的内存重分配次数。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来。这样的好处也是减少内存分配次数，例如一个原本len为100，free为20的SDS做了字符串缩减操作变成len为50，free为70，之后SDS又做了一次增长操作需要增长60个字节，此时SDS就不会再重新分配空间，直接使用free中的70个空闲字节空间。

读者们也不用担心这样会发生内存泄露，因为当redis内存不足时，SDS会释放未使用的空间以供redis其他需要的地方使用。

二进制安全

C字符串时以\0空字符（null）为结尾，所以字符串中间不能有空字符，这使得C字符串不能存储图片等二进制数据，只能存文本数据。而Redis的SDS的API都是二进制安全的，这些API会以处理二进制的方式处理SDS的buf中的数据。

兼容部分C字符串函数

应为SDS遵循C字符串以空字符结尾的惯例，这样SDS可以重用<string.h>函数库，避免不必要的代码重复。

链表

链表结构应用于redis的列表(list)、发布订阅、慢查询、监视器以及构建客户端输出缓冲区等。

下面我们看看redis中的链表是如何实现的：

每个链表节点是一个listNode结构体

typedef struct listNode{		// 节点对象
    struct listNode * prev;	// 向前指针（节点指针）
    struct listNode * next;	// 向后指针
    void * value;			// 节点的值,一般是字符串的RedisObj对象
}listNode;

多个listNode节点通过prev和next指针连接组成双向链表。

redis会使用list结构表示一个双向链表，该对象只需包含头部节点和尾部节点，通过指针就能访问到链表的所有节点

typedef struct list{  // 链表对象
    listNode * head;	//头部节点
    listNode * tail;		//尾部节点
    unsigned long len;	//节点数量
    void * (*dup)(void *ptr);		//节点值复制函数、
    void * (*free)(void *ptr);		//节点值释放函数
    void * (*match)(void *ptr);		//节点值对比函数
}list;

dup函数用于复制链表节点所保存的值； 

free函数用于释放链表节点所保存的值； 

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

其实这就是一个普通的双向链表。节点值可以使任意类型的值。

更多内容请关注微信公众号