Skip to content

Latest commit

 

History

History
101 lines (57 loc) · 6.49 KB

2019-07-01-Redis数据结构之哈希表.md

File metadata and controls

101 lines (57 loc) · 6.49 KB

Redis 的字典底层使用哈希表实现，说到哈希表大家应该能联想到 HashMap 或者是 Hashtable，也应该能联想到 key、value 的存储形式，以及哈希表扩容，哈希算法等知识点。那么 Redis 字典是否也是通过这种形式实现的呢？带着这些疑问下面我们就来了解一下 Redis 中的哈希表。

一、 字典结构

Redis 的数据库本身是一个字典，所有对数据库的增、删、改、查操作都是在字典的基础上操作的。

在这里插入图片描述

字典是基于哈希表实现的，通过上图我们可以看出字典包含了 2 个哈希表，还有一些其他属性，比如 rehashindex，type 等。

为什么字典使用 2 个哈希表呢？原因是与 rehash 相关，与 rehash 相关的还有 rehashindex 属性，下面我们会具体看到字典 rehash 的过程。

二、 哈希表结构

在这里插入图片描述

  • table：用于存储键值对
  • size：表示哈希表的数组大小
  • used：表示哈希表中已经存储的键值对的个数
  • sizemask：大小永远为 size - 1

三、哈希算法

当我们把一个新的键值对添加到字典里时，会先根据键的哈希值计算其对应的索引值，然后根据索引值，将新的键值对放到哈希表数组指定的索引上面。哈希值是通过 MurmurHash2 算法计算出来的，有兴趣的可以自行搜索了解一下。

如果当 2 个或 2 个以上的键值对被分配同一个索引上面时，就发生了哈希冲突。我们联想下 HashMap 中时如何解决哈希冲突的呢？HassMap 会通过链地址法将新的键值对通过链表的形式追加在上一个键值对后面。

Redis 中的字典也是通过链地址法解决哈希冲突的，不过有一点不同的是 Redis 会将新添加的键值对放在链表的头节点位置上，也就是头插法。

3.1 负载因子

HashMap 中有一个 DEFAULT_LOAD_FACTOR 字段默认为 0.75，意思是当哈希表中键值对的数量达到哈希表容量的 0.75 倍时就需要对哈希表进行扩容。

Redis 哈希表的负载因子通过下面的公式计算：

	# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
	load_factor = ht[0].used / ht[0].size

3.2 rehash 条件

Redis 哈希表不仅提供了扩容还提供了收缩机制，扩容与收缩都是通过 rehash 完成的。与 HashMap 一样，Redis 中的哈希表想要执行 rehash 扩容操作也是需要一定条件的，主要为以下 2 个：

  • 服务器目前没有执行 BGREWRITEAOF 或者 BGSAVE 命令，且哈希表的负载因子大于等于 1
  • 服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5

PS：BGSAVE 与 BGREWRITEAOF 是 Redis 持久化相关的命令。

下面是收缩 rehash 的条件：

  • 哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作

上面扩容时根据 BGREWRITEAOF 或者 BGSAVE 命令是否执行分了两种情况，为什么要这么做呢？原因如下：

在执行 BGREWRITEAOF 或者 BGSAVE 命令 时，Redis 会为当前服务器进程创建一个子进程，所以在子进程存在期间，会提高执行扩容的负载因子，因为这样可以尽可能避免在子进程存在期间进行哈希表的扩容操作，从而避免不必要的内存写入操作，最大限度的节约内存。

下面以扩容为例，看下 Redis 中 rehash 的过程。

3.3 rehash 扩容过程

Redis 字典 rehash 过程比较有意思的是它通过 2 个哈希表实现，当没有在 rehash 时：rehashidx 的值为 -1，且使用哈希表 0 存储键值对，哈希表 1 什么也不存储。

rehash 过程：

  • 为字典的 ht[1] 哈希表分配空间，分配的大小如下
    • 扩容：ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n
    • 收缩：ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n
  • 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上，这个过程会重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上
  • 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备

下面是扩容前后的一个对比：

扩容前：

在这里插入图片描述

扩容后：

在这里插入图片描述

上面只给出了最终的结果对比，其实在 rehash 的过程中，每当一个键值对被 rehash 到 ht[1] 上时，对应的 rehashidx 属性就会加 1，因此也可以根据该字段判断字典是否正在 rehash。

3.4 渐进式 rehash

上面我们提到 Redis 字典的 rehash 过程，其实 rehash 并不是一次性，集中式的完成的，而是分多次，渐进式完成的。原因是 Redis 的字典字典有可能存储上百万个键值对，如果一次性完成的话，那么 Redis 可能会在一段时间内停止服务，为了保证 Redis 的可用性，这么做肯定是不允许的。

3.5 扩展问题分析

在 rehash 的过程中，如果我们对字典进行了增删改查，那么会操作哪个哈希表呢？是旧的还是新的？

其实不管执行任何操作，都不会允许有键值有丢失或者不一致的情况，有了这个前提后再进行分析就比较简单了。

在新增键值对的时候肯定会添加到新的哈希表中去，因为添加到旧的哈希表的话，最终还是被 rehash 到新的哈希表，就没有必要进行一次 hash 了。

删改查操作在保证一致性的前提下，一定会先操作旧的哈希表，如果在旧的哈希表中没有操作成功，会继续操作新的哈希表。我们想一下，如果先操作新的哈希表再操作旧的哈希表的话，那么在操作的过程中可能有一部分数据被 rehash 到新的哈希表中去，这些数据有可能因为重新哈希的原因而被忽略。

参考资料

《Redis 设计与实现》 黄健宏著