本文内容为《redis设计与实现》一书学习笔记。本文主要概述二到四章内容。
第2章 简单动态字符串
2.1 SDS的定义
2.2 SDS与C字符串区别
常数复杂度获取字符串长度；SDS中len属性记录了SDS自身长度。
减少修改字符串时带来的内存重分配次数，并杜绝缓冲区溢出（增长字符串时未内存重分配来扩展底层数组的大小）和内存泄露（缩短字符串时未内存重分配来释放字符串不再使用的那部分空间）； 通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略；
空间预分配策略：当需要对SDS进行空间扩展的时候，不仅分配修改所必要的空间，还会分配额外的未使用空间；具体如下：
（1）如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。
（2）如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
惰性空间释放：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用（SDS也提供了专门的API用来真正释放空间，所以不用担心会造成内存浪费）；
通过惰性空间释放策略，避免了缩短字符串时的内存重分配操作，为将来可能有的增长提供了优化。
二进制安全；所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样，所以SDS不仅仅可以保存文本数据。（因为SDS使用len属性的值而不是空字符来判断字符串是否结束），这也是SDS的buf属性称为字节数组的原因（redis不是用这个数组来保存字符，而是保存一系列二进制数据）
兼容部分C字符串函数；
5.总结
第3章 链表
链表节点定义：
链表结构定义：
链表特性：双端无环带表头表尾和长度计数器 常数级O（1）
第4章 字典
字典是一种用于保存键值对的抽象数据结构。Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。
举个例子，当执行以下命令时
redis> SET msg "hello world"
OK
Redis将在数据库中创建一个新的键值对，其中键是一个字符串对象，对象的底层实现是一个保存着字符串“msg”的SDS。值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS，这个键值对就是保存在数据库的字典里的。
4.1 字典的实现
哈希表：
table属性是一个数组，数组中的每个元素是一个指向dict.h / dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
下图是一个大小为4的空哈希表的示意图：
哈希表节点定义：哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对：
next属性是指向另一个哈希表节点的指针，可以将多个哈希值相同的键值对连接在一起来解决键冲突问题。
字典：
redis中的字典由dict.h / dict结构表示：
type属性是一个指向dictType结构的指针（dictType结构见下图），每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。而privdata属性则保存了需要传给那些类型特定函数的可选参数。
ht属性是一个包含两个项的数组，数组中每项都是一个dictht哈希表，一般情况下字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
普通状态下的字典实例如下：
4.2 哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
redis计算哈希值和索引值方法如下：
Redis使用MurmurHash算法来计算键的哈希值，这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。
4.3 解决键冲突
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，称这些键发生了冲突。Redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来.
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。
4.4 rehash
当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。这可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：
- 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）。
- 如果执行的扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used * 2 的2次幂；
- 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2次幂；
- 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
- 当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
（负载因子= 哈希表已保存节点数量/ 哈希表大小 ）
- 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
- 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
- 另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。
在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
4.5 渐进式hash
为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]。下面是Redis进行渐进式rehash的详细步骤：
- 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
- 在字典中维护一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始；
- 在rehash进行期间，每次对字典的访问操作，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到ht[1]，当rehash完成之后，rehashidx + 1，表示下一次rehash操作的键值对索引是rehashidx + 1
- 随着字典的不断操作，到某个时间点，ht[0]上的所有键值对都会rehash到ht[1]，此时设置rehashidx = -1，表示rehash已经完成；
在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。（例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找。在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作）
注意1：在rehash过程中，如果ht[0]中某些key很长时间都没有访问，这些key什么时候更新到ht[1]中？答：dictRehash过程中，并不是操作哪个键值就更新哪个键值，而是根据rehashidx对ht[0]进行遍历hash的。
注意2：在渐进式hash过程中，增删查改操作的index如果大于rehashidx，就访问ht[0]，否则访问ht[1]。
关系型数据库与非关系型数据库可以参考此链接
