本文共 5187 字，大约阅读时间需要 17 分钟。
简单动态字符串SDS
SDS 实现：
Redis 没有直接使用 C 语言的字符串，而是构建了自己的抽象类型：简单动态字符串（Simple Dynamic String）。
struct sdshdr { // 记录buf数组中已使用字节的数量 // 等于SDS所保存字符串的长度 int len; // 记录buf数组中未使用字节的数量 int free; // 字节数组,用于保存字符串 char buf[];}
free属性的值为0，表示这个 SDS 没有分配任何未使用空间
len属性的值为5，表示这个 SDS 保存了一个五字节长的字符串，结尾的 '\0' 空字符不计算在内。
buf属性是一个 char 类型的数组，数组的前五个字节分别保存了 'R'、'e'、'd'、'i'、's' 五个字符，而最后一个字节则保存了空字符 '\0'。
SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在 SDS 的 len 属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的，所以这个空字符对于 SDS 的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS 可以直接重用一部分 C 字符串函数库里面的函数。
SDS 与 C 字符串的区别：
1、常数复杂度获取字符串长度
C 字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为O(N)。
SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为O(1)。
2、杜绝缓冲区溢出
C 字符串不记录自身的长度，所以 strcat() 假定用户在执行这个函数时，已经为 dest 字符串分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。
SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时，API 会先检查SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。
3、减少修改字符串时带来的内存重分配次数
C 字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个 C 字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作。
通过未使用空间，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 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。
举例：sdstrim 函数接受一个 SDS 和一个 C 字符串作为参数，移除 SDS 中所有在 C 字符串中出现过的字符。
sdstrim(s, "XY"); // 移除 SDS 字符串中所有'X'和'Y'这个例子将空余出来的字节空间，作为未使用空间 free 保留在 SDS 中，如果将来要对 SDS 进行增长操作的话，这些未使用空间就可能会派上用场。
通过惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。
与此同时，SDS 也提供了相应的 API，让我们可以在有需要时，真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。
4、二进制安全
C 字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
举例：如果有一种使用空字符来分割多个单词的特殊数据格式，那么这种格式就不能使用 C 字符串来保存，因为C 字符串所用的函数只会识别出第一个 '\0' 之前的字符串，而忽略第一个 '\0' 之后的字符串。
使用 SDS 保存之前提到的特殊数据格式就没有任何问题，因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束。
通过使用二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。
5、兼容部分C字符串函数
说简单点就是，C 字符串和 SDS 可以混合使用。
举例：可以将 SDS 保存的字符串和 C 字符串进行一些操作，比如，对比、追加等等。我们不需要专门再写一个 C 字符串或者 SDS，将两个字符串转换成相同的类型。
通过遵循 C 字符串以空字符结尾的惯例，SDS 可以在有需要时重用＜string.h＞函数库，从而避免了不必要的代码重复。
面试题：
为什么会选择 44 作为两种编码的分界点？在 3.2 版本之前为什么是 39？这两个值是怎么得出来的呢？
首先不管是 embstr 还是 raw 都需要计算两部分内容，第一部分是 redisObject 占用大小，第二部分是 SDS 占用大小。
// 第一部分 redisObjecttypedef struct redisObject { // 类型,占用 4bits unsigned type:4; // 编码,占用 4bits unsigned encoding:4; // 记录对象的 LRU 信息,占用 24bits int lru; // 引用计数器,占用 32bits int refcount; // 指向底层实现数据结构的指针,需要 64bits void *ptr; // ...} robj;// 计算：4 + 4 + 24 + 32 + 64 = 128bits = 16bytes// 第二部分,旧版本的 SDSstruct sdshdr { // unsigned int = 4bytes unsigned int len; // unsigned int = 4bytes unsigned int free; // 字节数组,用于保存字符串,结尾要以 '\0' 结尾,因此这里多出一个字节 char buf[];}// 计算：4 + 4 + 1 = 9bytes// 字节数组 buf 大小 = 64bytes - 16bytes - 9bytes = 39bytes// 第二部分,新版本的 SDSstruct sdshdr { // 等于 SDS 所保存字符串的长度 uint8_t len; // 记录了当前字节数组总共分配的内存大小 uint8_t alloc; // 记录了当前字节数组的属性,用来标识到底是 sdshdr8 还是 sdshdr16 等 unsigned char flags; // 字节数组,用于保存字符串 char buf[];}// 这里 unsigned int 变成了 uint8_t,uint16_t 等,其中一个 uin8_t 占了 1 字节,还加了一个 char flags 标识占了 1 字节,总共只用了 3 个字节的大小,相当于优化了 SDS 的内存使用,相应的用于存储字符串的内存就会变大。// 字节数组 buf 大小 = 64bytes - 16bytes - 3bytes - 1bytes = 44bytes// 可能还会有疑问：64bytes 是怎么来的？？？// 解答：64 位的系统，CPU 寻址一次 64 位。
链表 (Linked List)
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
作为一种常用数据结构，链表内置在很多高级的编程语言里面，因为 Redis 使用的 C 语言并没有内置这种数据结构，所以 Redis 构建了自己的链表实现。
链表在 Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。
除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis 服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（outputbuffer）。
链表实现：
每个链表节点使用一个 listNode 结构来表示：
typedef struct listNode { // 前置节点 struct listNode * prev; // 后置节点 struct listNode * next; // 节点的值 void * value;} listNode;多个 listNode 可以通过 prev 和 next 指针组成双端链表，如下图所示。
虽然仅仅使用多个 listNode 结构就可以组成链表，但使用 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 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数：
dup 函数用于复制链表节点所保存的值
free 函数用于释放链表节点所保存的值
match 函数则用于对比链表节点所保存的值和另一个输入值是否相等
list 结构和三个 listNode 结构组成的链表，如下图所示。
Redis 的链表实现的特性可以总结如下：
双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)。
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点。
带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1)。
带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1)。
多态：链表节点使用 void * 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
有兴趣的同学可以关注我的个人公众号，期待我们共同进步！！！
转载地址：http://exzad.baihongyu.com/