Redis设计与实现读书笔记

Redis设计与实现[^1]
- 简单动态字符串
- - SDS的基础定义
  - 与C字符串的差别
  - - 常数获取长度
    - 杜绝缓冲区溢出
    - 减少修改字符串时带来的内存重分配次数
    - 二进制安全
    - 函数兼容
- 链表
- - 链表和链表节点的实现
- 字典
- - 字典的实现
  - - 哈希表定义
    - 哈希表节点定义
    - 字典定义
  - 哈希算法
  - 解决键冲突

Redis设计与实现¹

简单动态字符串

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遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

与C字符串的差别

C语言使用的这种简单的字符串表示方式，并不能满足Redis对字符串在安全性、效率以及功能方面的要求，所以Redis的作者开发了SDS这种字符串数据结构

常数获取长度

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

这是属于功能和效率上的考虑，使用更加简洁高效

杜绝缓冲区溢出

因为C字符串不记录自身的长度，内存和长度担保需要手动控制，否则不小心就会导致溢出覆盖掉其他内存中存储的字符串值，安全性上是有隐患的。
与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。

这是属于安全性上的考虑

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

为了避免c字符串的内存重新分配动态变化带来的性能损耗而设计，这应该也是SDS设计的主要原因
SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

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

二进制安全

SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。这是安全性和功能性上的胜利。

函数兼容

通过遵循C字符串以空字符（即/0）结尾的惯例，SDS可以在有需要时重用＜string.h＞函数库，从而避免了不必要的代码重复。

链表

链表和链表节点的实现

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

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

虽然仅仅使用多个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图示
Redis的链表实现的特性可以总结如下：

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

链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

字典

字典的实现

哈希表定义

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

typedef struct dictht {//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码，用于计算索引值//总是等于size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used;
} dictht;

table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小，也即是table数组的大小，而used属性则记录了哈希表目前已有节点（键值对）的数量。sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。

哈希表节点定义

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

typedef struct dictEntry {//键void *key;//值union{void *val;uint64_tu64;int64_ts64;} v;//指向下个哈希表节点，形成链表struct dictEntry *next;
} dictEntry;

key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题。

字典定义

Redis中的字典由dict.h/dict结构表示：

typedef struct dict {//类型特定函数dictType *type;//私有数据void *privdata;//哈希表dictht ht[2];// rehash索引//当rehash不在进行时，值为-1in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
而privdata属性则保存了需要传给那些类型特定函数的可选参数。

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;

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。除了ht[1]之外，另一个和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;