前言
《Redis设计与实现》数据结构部分有关字符串类型介绍。
@
目录一、数据结构——简单动态字符串
1.1 SDS定义
在Redis中，没有直接使用C语言的字符串来表示，而是采用自己构建的简单动态字符串(simple dynamic string，SDS) 的抽象类型，并将 SDS 用作默认字符串表示。Redis中，C字符串只会用在一些无须对字符串值进行修改的地方，比如说打印日志。而SDS用来保存数据库中的字符串、AOF模块中的缓冲区、客户端输入缓冲区。
SDS的结构：
struct sdshdr {
// 记录buf数组中已使用字节的数量
// 等于SDS所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
}
SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的 len 属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS 函数自动完成的。由于结构上的类似，SDS字符串也可以直接重用一部分C字符串函数库里面的函数。
1.2 SDS与C字符串的区别
1.2.1常数复杂度获取字符串长度
C字符串的最后一个元素总是空字符 '\0'，需要使用长度为N+1的字符数组来表示长度为N的字符串。由于C字符串本身不记录数组长度，因此需要遍历整个数组来获取字符串长度，这个操作的复杂度为 O(N)；而 SDS 在len属性中记录了 SDS 本身的长度，所以获取长度的复杂度为 O(1)；
通过使用 SDS 而不是 C字符串，Redis将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1)，这确保了获取字符串长度的工作不会成为 Redis的性能瓶颈。
1.2.2 杜绝缓冲区溢出
-
C字符串
C字符串不记录自身长度带来的另一个问题就是容易造成缓冲区溢出。
比如说 <string.h>/strcat 函数可以将 src字符串中的内容拼接到 dest字符串的末尾：char *strcat(char *dest，const char *src)；假设原程序里存在两个内存中紧邻着的C字符串 s1和s2，分别保存了 "Redis" 、"MongoDB"，如果执行strcat(s1, "cluster")那么总的字符串长度就超过了已经分配的空间大小，在没有重新分配空间的前提下就会出现内存溢出的问题。 -
SDS字符串
与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS 需要对 SDS进行修改时，API会首先检查 SDS空间是否满足修改所需的要求，如果不满足的话，API会自动将 SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。
在扩展空间时，除了扩展必要的空间，还会分配额外的空间给SDS(free部分)。
1.2.3 减少修改字符串时带来的内存重分配次数
由于C字符串不记录本身的长度，因此对于一个包含N个字符的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组。所以每次增长或者缩短一个C字符串，程序都要对保存这个C字符串的数组进行一次内存重分配操作。而内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作。
- 如果程序执行的是增长字符串的操作，比如拼接操作(append)，那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小，否则会出现缓冲区溢出的问题。
- 如果程序执行的是缩短字符串的操作，比如截断操作(trim)，那么在执行这个操作之后，程序需要先通过内存重分配来释放字符串不再使用的那部分空间，如果忘了这一步就会产生内存泄露的问题。
Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁地发生就会对性能造成影响。
SDS为了解频繁调用内存重分配，实现了空间预分配和惰性空间释放两种优化策略。
空间预分配
当对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。额外分配空间大小由下述方式决定：
- 如果对SDS进行修改之后，SDS 的长度(len属性大小) 将小于 1MB，那么程序分配和 len属性同样大小的未使用空间，此时SDS len属性值和 free属性值相同。
- 如果对SDS进行修改之后，SDS的长度将大于等于 1MB，那么程序会分配 1MB的未使用空间。
这样当下次需要使用空间时，如果预分配的空间足够满足就不需要去调用内存重分配的系统调用，有效减少了内存重分配的次数。
惰性空间释放
当需要对SDS进行空间回收时，程序不会立即使用内存重分配来回收缩短后多出来的字节，而是使用 free属性将这些字节的数量记录起来，并等待将来去使用。同时SDS也提供了相应的API让我们在有需要时，去真正释放SDS的未使用空间，所以不用担心惰性空间释放策略所造成的内存浪费。
1.2.4 二进制安全
C字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则中间的空格会被认为是字符串的结尾，这些限制使得C字符串只能保存文本数据，而不能保存图片、视频等这些二进制数据。
SDS会以处理二进制的方式来处理SDS存放在 buf 数组中的数据，程序不会对其中的数据做任何限制、过滤或者假设，数据在写入时是什么样的，它被读取的时候就是什么样的。
Redis不是通过数组来保存字符，而是保存一系列的二进制数据，并且通过len 来判断字符串是否结束。
Redis不仅可以保存文本数据，而且还可以保存任意格式的二进制数据。
1.2.5 兼容部分C 字符串函数
由于SDS与C字符串上结构的相似性(都是以空字符串结尾的惯例)。所以SDS可以在需要时使用 <string.h> 函数库。
1.3 SDS主要操作API
二、链表
链表在Redis中的应用十分广泛，比如列表键(list数据类型) 的底层实现之一就是链表。当一个list 集合包含了数量比较多的元素，又或者包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。
除了集合之外，发布订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用了链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。
2.1 链表的实现
链表节点：
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
}
list集合：
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值赋值函数
void *dup;
// 节点值释放函数
void *free;
// 节点值对比函数
int *match(void *ptr, void *key);
}
list 集合为链表提供了表头指针head、表尾指针tail、链表长度计数器len、dup(用于复制链表节点所保存的值)、free(用于释放链表节点所保存的值)、match(用于对比链表节点保存的值和另一个输入值是否相等)。
2.2 Redis链表特性
- 双端：链表节点都是带有prev、next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)；
- 无环：表头节点的prev指针和表尾节点next指针都指向NULL；
- 带表头和表尾指针：通过 head、tail指针可以直接获取到 表头/表尾 的节点值；
- 带链表长度的计数器：通过 len字段获取链表长度，时间复杂度为 O(1)；
- 多态： 链表中节点值使用
void *指针来保存，并且可以通过 list 结构的 dup、free、match 三种函数来设置节点值，所以链表可以用于保存各种不同类型的值。
三、字典
字典在Redis中应用十分广泛，字典是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。
3.1 字典的实现
Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
3.1.1 哈希表 dictht
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值，等于size-1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
其中 table 是一个数组，数组中的每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。
3.1.2 哈希表节点 dictEntry
typedef struct dictEntry {
// 键
void *key;
// 值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
key保存键，v保存值，其中值可以是指针、整数；next 属性是指向下一个节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，用来解决键冲突的问题。
3.1.3 字典 dict
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引,当 rehash不在进行时,值为-1
int trehashidx;
} dict;
type属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。
其中type 是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数。
privdata 则保存了需要传递给那些特定类型函数的可选参数。
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*hashFunction) (const void *key);
// 复制键的函数
void *(*keyDup) (void *privdata, const void *key);
// 复制值的函数
void *(*valDup) (void *privdata, const void *key);
// 对比键的函数
int (*keyCompare) (void *privdata, const void *key1, const void *key2);
// 销毁键的函数
void (*keyDestructor) (void *privdata, void *key);
// 销毁值的函数
void (*valDestructor) (void *privdata, void *key);
} dictType;
注意 ht 为一个大小为2 的哈希表数组，字典只会使用 ht[0]哈希表，ht[1]哈希表在进行rehash时使用。
3.2 哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后根据索引值将哈希表节点放到哈希表数组的指定索引上面。
- 哈希表计算哈希值的方法：
hash = dict -> type -> hashFunction(key);采用dict字典里面的 dictType类型指针type所指向的 hashFunction(key) 求哈希值的方法； - 哈希表计算索引的方法：
index = hash & dict->ht[x].sizemask;采用dictht的 sizemask 属性和哈希值相与运算来实现。
3.3 解决键冲突
当有两个或者两个以上的节点被分配到了哈希表数组的同一个索引上面时，就发生了键冲突的问题。Redis解决键冲突采用的是链地址法来解决。前面介绍过，哈希表中结点中包含了 key、value、*next，通过单向链表来连接起多个冲突节点。
3.4 rehash
3.4.1 rehash概念
随着操作不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子(load factor) 维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。扩展或者收缩操作可以通过rehash（重新散列）的操作来实现。
3.4.2 rehash执行步骤
-
为字典的ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作、以及ht[0] 当前包含的键值对数量（也就是 ht[0].used 属性的值）。
(1) 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于ht[0].used *2的 2^n；
(2) 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于ht[0].used的 2^n； -
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面，rehash是指重新计算哈希值和索引值，然后将键值对放到 ht[1] 哈希表的指定位置上；
-
当 ht[0] 包含的所有键值对都迁移到 ht[1] 之后，释放 ht[0] 的空间，将 ht[1] 设置为 ht[0] ，并且在 ht[1] 上创建一个空白哈希表，为下一次 rehash 做准备。
3.4.3 哈希表扩展与收缩
负载因子： load_factor = ht[0].used / ht[0].size
满足下列条件之一就会开始执行扩展操作：
- 服务器目前没有执行
BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1； - 服务器目前正在执行
BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
满足下列条件会开始执行收缩操作：
- 哈希表的负载因子小于0.1 时，自动开始执行收缩操作。
根据当前Redis是否执行BGSAVE、BGREWRITEAOF，负载因子的值不同。这是因为在执行上述命令时，Redis会创建当前服务器进程的子进程，而大多数操作系统都会采用写时复制(Copy-on-write)技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子来减少写操作的执行，避免不必要的内存写入操作，节约内存。
3.5 Copy-on-write 写时复制
3.5.1 概念介绍
Redis在执行 BGSAVE、BGREWRITEAOF 命令时，会fork() 出一个子进程来执行内存数据持久化到文件，而主进程继续处理客户端请求。在这个过程中，Redis 会采用写时复制(COW)来优化子进程的使用效率。
3.5.2 过程
- fork 出一个子进程，与父进程共享物理空间。也就是说如果父子进程不对内存空间进行写入操作的话，内存空间中的数据不会复制给子进程，子进程直接引用父进程的物理空间，这样效率更高；
- 当父子进程中有更改相应内存字段的行为发生时，再为子进程分配相应的物理空间。
3.5.3 原理
父进程fork()后，会把父进程中所有的内存页的权限设置为 read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时没有问题。但是当某一个进程执行写操作时，CPU检测到内存页是只读的，就会触发页异常中断(page-fault)，并且陷入一个中断例程。中断例程中，会把触发异常的页复制一份，于是父子进程各自持有独立的一份。
参考文章：
Copy-on-write实现原理