=================
== Time Stream ==
=================
一个小学生

Redis字典

redis

Redis字典使用哈希表作为底层实现,一个哈希表可以有多个哈希节点,每个哈希表节点就保存了字典中的一个键值对。

哈希表

Redis字典使用哈希表作为底层实现,一个哈希表可以有多个哈希节点,每个哈希表节点就保存了字典中的一个键值对。

哈希表:

hashtable-1

哈希表就类似Java中的Map实现。

  1. table,哈希表数组
  2. size,哈希表大小
  3. sizemask,哈希表大小掩码,用于计算索引,等于size-1
  4. used,哈希表已有节点数量

哈希表节点

  1. key,键
  2. v,保存着键值对中的值,可以是一个指针,也可是一个uint64_t整数,也可以是int64_t整数
  3. next指向另外一个哈希表节点的指针,处理冲突。

字典

字典:

dict-1

  1. type,指向一个dictType结构指针,为不同字典设置不同类型特定函数。
  2. privdata,保存了需要传给那些类型特定函数的可选参数
  3. ht,包含两个dictht哈希表的数组,ht[0]是哈希表,ht[1]只会在堆ht[0]哈希表进行rehash时使用。
  4. rehashidx,记录了rehash目前的进度,没有rehash时为-1

哈希算法

根据键值对的键计算出哈希值和索引值,根据索引值将键值对哈希节点放到哈希表数组的指定索引上面。类似Java中HashMap的算法。

解决键冲突

采用链地址法解决冲突,多个哈希表节点用next指针形成一个单向链表,新节点添加到链表表头。跟Java的HashMap一样。

rehash

对字典的哈希表进行扩展和收缩通过rehash实现:

扩容:

  1. 为字典ht[1]分配空间,ht[1]大小为ht[0].used * 2,但是要保持大小为2的n次方
  2. 把ht[0]中所有键值对rehash到ht[1]上
  3. 完成后将ht[0]释放,将ht[1]设置为ht[0],并在ht[1]新建一个空白哈希表,为下次rehash做准备

收缩:

  1. 为字典ht[1]分配空间,ht[1]大小为2的n次方,其中n=ht[0].used
  2. 把ht[0]中所有键值对rehash到ht[1]上
  3. 完成后将ht[0]释放,将ht[1]设置为ht[0],并在ht[1]新建一个空白哈希表,为下次rehash做准备

哈希表的扩展和收缩

负载因子 = 已保存节点数量 / 哈希表大小

  1. 服务器没有执行BGSAVE和BGREWRITEAOF命令,且哈希表负载因子大于等于1时,会自动对哈希表进行扩展操作。
  2. 服务器正在执行BGSAVE和BGREWRITEAOF命令,且哈希表负载因子大于等于5,时,会自动对哈希表进行扩展操作。

BGSAVE或BGREWRITEAOF命令执行过程中,Redis需要创建当前进程的子进程,操作系统一采用copy-on-write技术来优化使用效率,在子进程存在期间,需要尽可能避免进行哈希表扩展操作,所以会使用一个高的负载因子,最大限度的节约内存。

负载因子小于0.1时,程序会自动对哈希表执行收缩操作。

渐进式rehash

rehash的时候会将ht[0]的所有键值对rehash到ht[1]里,如果说数据量非常大,一次性全部rehash会导致服务器暂停服务,所以Redis采用分多次、渐进式的将ht[0]里的键值对慢慢rehash到ht[1]中:

  1. 位ht[1]分配空间,字典同时持有ht[0]和ht[1]
  2. 字典中维持一个索引计数器rehashidx,并设为0,表示开始工作,从第0个索引位置开始
  3. rehash期间对字典执行的增、删、查、改,都会顺带将ht[0]上对应rehashidx索引的键值对rehash到ht[1],完成后rehashidx增1
  4. 等所有键值对都被rehash到ht[1]后,将rehashidx设置-1,表示已完成

在渐进式rehash期间,删除、查找、更新会在两个哈希表上都进行,而新增则只在ht[1]上进行。

参考

  • 《redis设计与实现》(第二版)