Redis设计与实现-笔记（一）
数据结构与对象
Redis的底层数据结构，了解Redis的底层数据结构有助于我们更好的运用Redis。
SDS
Redis在实现上使用了，自定义的SDS(simple dynamic string)，来代替C语言传统的字符串表示方式。
- free 属性的值为 0 ， 表示这个 SDS 没有分配任何未使用空间。
- len 属性的值为 5 ， 表示这个 SDS 保存了一个五字节长的字符串。
- buf 属性是一个 char 类型的数组， 数组的前五个字节分别保存了 'R' 、 'e' 、 'd' 、 'i' 、 's' 五个字符， 而最后一个字节则保存了空字符 '\0' 。
SDS对比C语言传统的字符串有以下优点：
-
在常数时间复杂度获取字符串长度
因为在SDS结构中已经保存了字符串的长度信息，并且在修改字符串时，也会对其进行相应的修改，所以获取字符串长度，无需遍历整个字符串。 -
杜绝缓存区溢出
在C字符串中如果你要对一个字符串进行扩展的话，就必须预先计算空间，如果空间不足久，就需要再申请一些内存空间。但要是忘记了预先分配空间的话，就会参数缓存区溢出。而使用SDS的API会自动的帮你计算并分配空间，从而杜绝了缓存区溢出的可能。
-
减少内存分配次数
相比于C字符串不记录长度信息，导致每次修改都需要进行内存重新分配(分配内存是一个相对耗时的系统调用) SDS就要灵活的多了，SDS的API通过 空间预先分配 和 惰性空间释放 这两个方式去减少空间的重新分配，其中空间预先分配 是指当第一次对SDS字符串进行修改时，SDS不止分配足够的空间，而且会根据分配策略，多分配一些空间以备下次使用。惰性空间释放就是在缩短SDS字符串时仅仅删除字符内容，并不回收剩余的内存空间。 -
二进制安全
SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。
链表
链表是Redis的列表键的底层实现之一。
可以由上图结构看出，redis的链表底层是双端链表，并且由一个list结构表示，list结构为链表提供了表头指针 head 、表尾指针 tail ， 以及链表长度计数器 len ， 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数。
总结：
redis 链表是一个无换的双端链表，并且通过list结构的表头和表尾指针，达到O(1)复杂度的首尾节点获取，利用len属性进行O(1)复杂度的链表长度获取。
字典
字典在Redis中被用于实现数据库本身和哈希键，当我们使用HSET,HGET的时候底层就是使用redis的字典实现。
实现
Redis的底层使用字典作为哈希表的实现，一个哈希表有多个哈希节点，每个节点保存一个键值对。
哈希表中，table属性是一个数组，size属性记录了哈希表的大小，也就是table数组的大小，而used属性则记录了哈希表目前已有节点（键值对）的数量。sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
- type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
而 - privdata 属性则保存了需要传给那些类型特定函数的可选参数。
- ht属性是一个只有两个元素的哈希表类型的数组，h[0]用于正在的数据，h[-1]用于Rehash的中间过渡。
- rehashidx属性，用于表示哈希表rehash的状态
哈希算法
Redis使用MurmurHash2算法来计算哈希值，每次有新的键值对要被添加到字典中，redis会先使用 MurmurHash2哈希函数来计算出哈希值，然后在用哈希值与哈希表结构中的sizemask进行与运算，最后就会得出键值对要存储的下标位置了。
解决冲突
如上面的流程，当两个键值对最后计算出来的下标是一样的，那么Redis就会使用链地址法来解决冲突。
这里就使用到哈希节点中预留的next属性，指向下一个节点，后一个添加的节点，会被添加到头部，这样添加节点的复杂度就是O(1)了。
rehash
rehash(重新散列），被用于保证字典的负载因子在一个平衡的范围内(1-5之间)，也就是需要根据哈希表的大小进行相应的扩展和收缩。
rehash的过程：
- 给字典ht[1]分配空间，分配空间大小的公式是$2^n$，其中在扩展时: n=ht[0].used * 2, 在收缩时: n=ht[0].used。
- 设置字典的rehashidx为0，开始rehash。
- 每当对字典执行添加、删除、查找或者更新操作时，将rehashidx作为下标，对应在h[0]的节点取出，然后重新计算哈希值和下标，保存的对应的h[1]的位置上，最后自增字典的rehasidx属性。
- 当h[0]中的所有节点都被rehash到h[1]后，释放h[0]的空间，将h[1]设置成h[0]，再为h[1]设置一个空白哈希表，并且将字典的rehashidx设置为-1。
在rehash期间，如果添加键值对到字典的操作，都会被直接存储在h[1]中，而查找的时候会先从h[0]找，然后再到h[1]，这样就保证了h[0]的元素只减无增。
当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：
服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5
