Redis：hash类型底层数据结构剖析_redis hash底层数据结构

Redis数据结构——哈希

哈希对象有两种编码方案，当同时满足以下条件时，哈希对象采用ziplist编码，否则采用hashtable编码：

• 哈希对象保存的键值对数量小于512个；
• 哈希对象保存的所有键值对中的键和值，其字符串长度都小于64字节。

其中，ziplist编码采用压缩列表作为底层实现，而hashtable编码采用字典作为底层实现。

ziplist：压缩列表

压缩列表（ziplist）：是Redis为了节约内存而设计的一种线性数据结构，它是由一系列具有特殊编码的连续内存块构成的。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。

压缩列表的结构如下图所示：

该结构当中的字段含义如下表所示：

其中，压缩列表的节点（entryX）由以下字段构成：

previous_entry_length（pel）属性以字节为单位，记录当前节点的前一节点的长度，其自身占据1字节或5字节：

1. 如果前一节点的长度小于254字节，则“pel”属性的长度为1字节（8bit，2⁸=256位），前一节点的长度就保存在这一个字节内；
2. 如果前一节点的长度达到254字节，则“pel”属性的长度为5字节，其中第一个字节被设置为0xFE，之后的四个字节用来保存前一节点的长度；

基于“pel”属性，程序便可以通过指针运算，根据当前节点的起始地址计算出前一节点的起始地址，从而实现从表尾向表头的遍历操作。

content属性负责保存节点的值（字节数组或整数），其类型和长度则由encoding属性决定，它们的关系如下（了解）：

hashtable：字典

字典（dict）又称为散列表，是一种用来存储键值对的数据结构。C语言没有内置这种数据结构，所以Redis构建了自己的字典实现。

Redis字典的实现主要涉及三个结构体：字典、哈希表、哈希表节点。其中，每个哈希表节点保存一个键值对，每个哈希表由多个哈希表节点构成，而字典则是对哈希表的进一步封装。

这三个结构体的关系如下图所示：

其中，dict代表字典，dictht代表哈希表，dictEntry代表哈希表节点。可以看出，dictEntry是一个数组，这很好理解，因为一个哈希表里要包含多个哈希表节点。而dict里包含2个dictht，多出的哈希表用于REHASH。

REHASH

REHASH 流程

当哈希表保存的键值对数量过多或过少时，需要对哈希表的大小进行扩展或收缩操作，在Redis中，扩展和收缩哈希表是通过REHASH实现的，执行REHASH的大致步骤如下：

1. 为字典的ht[1]哈希表分配内存空间

   如果执行的是扩展操作，则ht[1]的大小为第1个大于等于ht[0].used*2=n的2ⁿ（比如说ht[0]是6，6*2=12，大于等于12的第一个2的n次方是16=2⁴，所以ht[1]大小是16）。如果执行的是收缩操作，则ht[1]的大小为第1个大于等于ht[0].used=n的2ⁿ。

2. 将存储在ht[0]中的数据迁移到ht[1]上，重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

3. 将字典的ht[1]哈希表晋升为默认哈希表，迁移完成后，清空ht[0]，再交换ht[0]和ht[1]的值，为下一次REHASH做准备。

下面为一个rehash的实例 ：

h[0]的大小为4，那么2 * 4 = 8 ( 第一个大于等于8的 2的n次方是2 ^ 3 ) ，所以　h[1]大小设置为8

重新计算索引，并复制， h [0] 所有的键值都迁移到 h [1]
　　　 　

完成 rehash 之后的字典

REHASH 触发条件

当满足以下任何一个条件时，程序会自动开始对哈希表执行扩展操作：

1. 服务器目前没有执行bgsave或bgrewriteof命令，并且哈希表的负载因子大于等于1；
2. 服务器目前正在执行bgsave或bgrewriteof命令，并且哈希表的负载因子大于等于5。

Redis有一个机制,可以自动的扫描AOF文件,并且把冗余的操作进行合并，该机制由bgrewriteof命令实现,该命令在执行后,会将Redis中的数据以命令的方式保存起来,并替换原有的文件。

渐进式REHASH

为了避免REHASH对服务器性能造成影响，REHASH操作不是一次性地完成的，而是分多次、渐进式地完成的。

渐进式REHASH的详细过程如下：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表；
2. 在字典中的索引计数器rehashidx设置为0，表示REHASH操作正式开始；
3. 在REHASH期间，每次对字典执行添加、删除、修改、查找操作时，程序除了执行指定的操作外，还会顺带将ht[0]中位于rehashidx上的所有键值对迁移到ht[1]中，再将rehashidx的值加1；
4. 随着字典不断被访问，最终在某个时刻，ht[0]上的所有键值对都被迁移到ht[1]上，此时程序将rehashidx属性值设置为-1，标识REHASH操作完成。

REHSH期间键值对访问规则

REHSH期间，字典同时持有两个哈希表，此时的访问将按照如下原则处理：

1. 新添加的键值对，一律被保存到ht[1]中；
2. 删除、修改、查找等其他操作，会在两个哈希表上进行，即程序先尝试去ht[0]中访问要操作的数据，若不存在则到ht[1]中访问，再对访问到的数据做相应的处理。