[Redis设计与实现] Part1. 数据结构与对象（1）

前言
以下的内容是笔者阅读学习《redis设计与实现(第二版)》的一个读书笔记，主要是对书中提到的一些关键点进行归纳总结。此外，配合redis3.0的源码进行学习效果更佳。

ch2 简单动态字符串

redis没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（SDS）的抽象类型，并将SDS用作redis的默认字符串表示。

在redis里面，C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，比如日志打印：

日志打印

当redis需要的不仅仅是一个字符串字面量，而时一个可以被修改的字符串值时，redis就会使用SDS来表示字符串值，比如在redis的数据库里面，包含字符串值的键值对在底层都是由SDS实现的。

SDS的定义

SDS的定义
SDS与C字符串的区别
1. 常数复杂度获取字符串长度
  C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，知道遇到代表字符串结尾的空字符为止，这个操作的复杂度为O(N)。SDS在len属性中记录了本身的长度，所以获取一个SDS的长度复杂度为O(1)。
2. 杜绝缓冲区溢出
  例如，<string.h>/strcat函数可以将src字符串的内容拼接到dest字符串的末尾。
  
  strcat
  
  C字符串不记录自身的长度，所以strcat假定用户在执行这个函数时，已经为dest分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立，就会产生缓冲区溢出。
3. 减少修改字符串时带来的内存重分配次数
  SDS实现两种空间优化策略：
  - 空间预分配
    
    空间预分配
  - 惰性空间释放
    当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来挥手缩短多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。
4. 二进制安全
  C字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则会被认为是字符串的结尾。SDS中用char数组来保存数据，并且使用len属性来记录数据的长度。
5. 兼容部分C字符串函数
  虽然SDS的API都是二进制安全的，但他们一样遵循C字符串以空字符结尾的惯例，所以保存在SDS的文本数据可以重用一部分<string.h>库定义的函数。
总结

C字符串与SDS的总结

ch3 链表

链表和链表节点的实现

链表节点

双向链表（adlist.h/listNode）

链表
redis链表特性
- 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
- 无环：表头节点的pre指针和表尾的next指针都指向NULL，对链表的访问以NULL为终点
- 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链接的表头节点和表尾节点的复杂度为O(1)
- 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度O(1)
- 多态：链表节点使用void*指针来保存节点值

ch4 字典

redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
- redis字典使用的哈希表由dict.h/dictht结构定义：
  
  dictht
- 哈希表节点：
  
  dictEntry
- 字典：
  
  dict
  - type：一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，redis会为用途不同的字典设置不同的类型特定函数。
  - privdata：保存了需要传给那些类型特定函数的可选参数

普通状态下的字典

哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
解决键冲突
当由两个或以上数量的键被分配到哈希表数组的同一个索引上面时，我们称这些键发生了冲突。

redis的哈希表使用链地址发来解决键冲突，没个哈希表节点都有一个next指针，多个哈希表节点可以以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。

因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置，排在其他已有节点的前面。
rehash
随着操作的不断执行，哈希表保存的键值对会逐渐增多或者逐渐减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序要对哈希表进行相应的扩展或收缩。
过程：
1. 为字典的ht[1]哈希表分配空间，空间的大小取决于要执行的操作以及ht[0]当前包含的键值对数量
  - 扩展：ht[1]的大小为第一个大于等于ht[0].used*2的2^n
  - 收缩：ht[1]的大小第一个大于等于ht[0].used的2^n
2. 将保存在ht[0]中所有的键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
3. 当ht[0]包含的所有键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]上新创建一个空白哈希表，为下一次rehash做准备。
哈希表的扩展与收缩
当以下条件中的任意一个被满足时，程序会自动对哈希表执行扩展操作：
1. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5
```
负载因子 = 哈希表已保存节点数量 / 哈希表大小
```
在执行BGSAVE命令或BGREWRITEAOF命令的过程中，redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时拷贝（copy-on-write）技术来优化子进程使用效率，所以在子进程存在期间，服务器会提高扩展操作所需的负载因子，尽量避免在子进程存在期间进行哈希表扩展操作，避免不必要的内存写入操作，最大限度节约内存。
1. 当负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。
渐进式rehash
扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。若一次性完成，当哈希表里的键值对数量十分大（百万、千万级），庞大的计算量可能会导致服务器在一段时间内停止服务。
redis采用渐进式rehash，步骤如下：
1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2. 在字典中维持一个rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3. 在rehash期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的增一
4. 随着字典操作的不断执行，最终在某个时间上，ht[1]的所有键值对都会被rehash至ht[1]，这是将rehashidx设置为-1，表示rehash操作完成。
在渐进式rehash期间，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash期间，字典的删除、查找、更新等操作会在两个哈希表上进行。

待续...

如果觉得还不错，关注公众号获取更多优质文章 ~

微信搜一搜四方云和