学习笔记-Redis设计与实现-字典

alonli

　　字典，有称为符号表(symboltable)、关联数组(associative array)或映射(map)，是一种用于保存键值对(key-value pair)的抽象数据结构。
4.1 字典的实现
　　Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
4.1.1 哈希表

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

4.2 哈希表节点

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

4.1.3 字典

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

• 　　ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
  
• 　　rehashidx记录了rehash目前的进度，如果没有进行rehash，值为-1。
  

4.2 哈希算法

4.3 解决键冲突

• 　　Redis的哈希表使用链地址法(separate chaining)来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，解决了键冲突的问题。
  
• 　　程序总是将新节点添加到链表的表头位置(复杂度为O(1))，排在其他已有节点的前面。
  

4.4 rehash

• 　　Redis对字典的哈希表执行rehash的步骤如下
  

　　为字典的ht[1]哈希表分配空间，空间的大小取决于要执行的操作，以及ht[0]当前包含的键值对数量(ht[0].used属性值)：
　　如果执行的是扩展操作，ht[1]的大小为第一个大于等于ht[0].used*2的2^n;
　　如果执行的是收缩操作，ht[1]的大小为第一个大于等于ht[0].used的2^n。
　　将保存在ht[0]中的所有键值对rehash到ht[1]上面
　　当ht[0]包含的所有键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表。

• 　　哈希表的扩展与收缩
  

　　当以下条件之一被满足，程序会自动对哈希表执行扩展操作：
　　服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；
　　服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于。
　　负载因子 = 哈希表已保存节点数量 / 哈希表大小    load_factor = ht[0].used / ht[0].size;
　　根据BGSAVE命令或BGREWRITEAOF命令是否正在这姓，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行BGSAVE命令或者BGREWRITEAOF命令的过程中，Redis需要创建当前服务器的子进程，而大多数操作系统都才有写时复制(copy-on-write)技术来优化子进程的使用率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要地内存写入，最大限度地节约内存。
　　当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。
4.5 渐进式rehash

• 　　为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面地键值对慢慢地rehash到ht[1]。
  

　　以下是哈希表渐进式rehash的详细步骤：
　　为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
　　为字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
　　在rehash执行期间，每次对字典执行添加、删除、查找或者更新操作时，程序出了执行指定的操作之外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash至ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
　　随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

• 　　渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。
  
• 　　渐进式rehash执行期间的哈希表操作
  

　　因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除(deltte)、查找(find)、更新(update)等操作会在两个哈希表上进行。
　　在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再执行任何添加操作。
4.6 字典API

4.7 重点回顾

• 　　字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。
  
• 　　Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅再进行rehash时使用。
  
• 　　当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
  
• 　　哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
  
• 　　在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成地。