最近,小黑哥的一个敌人进来面试,回来跟小黑哥埋怨,面试官不按套路出牌,间接打乱了他的节奏。
事件是这样的,后面面试问了几个 Java 的相干问题,我敌人答复还不错,接下来面试官就问了一句:看来 Java 根底还不错,Java HashMap 你相熟吧?
我敌人答复。工作常常用,有看过源码。
我敌人原本想着,你轻易来吧,这个问题之前曾经筹备好了,轻易问吧。
谁晓得,面试官上面一句:
那好的,咱们来聊聊 Redis 字典吧。
间接将他整蒙逼。
小黑哥的敌人因为没怎么钻研过 Redis 字典,所以这题就间接答复不晓得了。
当然,如果面试中真不知道,那就答复不理解,间接下一题,不要乱答。
不过这一题,小黑哥感觉还是很惋惜,其实 Redis 字典基本原理与 HashMap 差不多,那咱们其实能够套用这其中的原理,不求答复满分,然而怎么也能够得个及格分吧~
面试过程真要碰到这个问题,咱们能够从上面三个方面答复。
- 数据结构
- 元素减少过程
- 扩容
字典数据结构
说起字典,兴许大家比拟生疏,然而咱们都晓得 Redis 自身提供 KV 查问的形式,这个 KV 就是其实通过底层就是通过字典保留。
另外,Redis 反对多种数据类型,其中一种类型为 Hash 键,也能够用来存储 KV 数据。
小黑哥刚开始理解的这个数据结构的时候,原本认为这个就是应用字典实现。其实并不是这样的,初始创立 Hash 键,默认应用另外一种数据结构 -ZIPLIST(压缩列表),以此节俭内存空间。
不过一旦以下任何条件被满足,Hash 键的数据结构将会变为字典,放慢查问速度。
- 哈希表中某个键或某个值的长度大于
server.hash_max_ziplist_value
(默认值为64
)。 - 压缩列表中的节点数量大于
server.hash_max_ziplist_entries
(默认值为512
)。
Redis 字典新建时默认将会创立一个哈希表数组,保留两个哈希表。
其中 ht[0]
哈希表在第一次往字典中增加键值时分配内存空间,而另一个 ht[1]
将会在下文中扩容 / 缩容才会进行空间调配。
字典中哈希表其实就等同于 Java HashMap,咱们晓得 Java 采纳数组加链表 / 红黑树的实现形式,其实哈希表也是应用相似的数据结构。
哈希表构造如下所示:
其中 table
属性是个数组,其中数组元素保留一种 dictEntry
的构造,这个构造齐全相似与 HashMap 中的 Entry
类型,这个构造存储一个 KV 键值对。
同时,为了解决 hash 碰撞的问题,dictEntry
存在一个 next 指针,指向下一个dictEntry
,这样就造成 dictEntry
的链表。
当初,咱们回头比照 Java 中 HashMap,能够发现两者数据结构基本一致。
只不过 HashMap 为了解决链表过长问题导致查问变慢,JDK1.8 时在链表元素过多时采纳红黑树的数据结构。
上面咱们开始增加新元素,理解这其中的原理。
元素减少过程
当咱们往一个新字典中增加元素,默认将会为字典中 ht[0]
哈希表调配空间,默认状况下哈希表 table 数组大小为 4(DICT_HT_INITIAL_SIZE)。
新增加元素的键值将会通过哈希算法,确定哈希表数组的地位,而后增加到相应的地位, 如图所示:
持续减少元素,此时如果两个不同键通过哈希算法产生雷同的哈希值,这样就产生了哈希碰撞。
假如当初咱们哈希表中领有是三个元素,:
咱们再减少一个新元素,如果此时刚好在数组 3 号地位上产生碰撞,此时 Redis 将会采纳链表的形式解决哈希碰撞。
留神,新元素将会放在链表头结点,这么做目标是因为新减少的元素,很大概率上会被再次拜访,放在头结点减少访问速度。
这里咱们在比照一下元素增加过程,能够发现 Redis 流程其实与 JDK 1.7 版本的 HashMap 相似。
当咱们元素减少越来越多时,哈希碰撞状况将会越来越频繁,这就会导致链表长度过长,极其状况下 O(1) 查问效率进化成 O(N) 的查问效率。
为此,字典必须进行扩容,这样就会使触发字典 rehash 操作。
扩容
当 Redis 进行 Rehash 扩容操作,首先将会为字典没有用到 ht[1]
哈希表调配更大空间。
画外音:
ht[1]
哈希表大小为第一个大于等于ht[0].used*2
的 2^2(2 的 n 次方幂)
而后再将 ht[0]
中所有键值对都迁徙到 ht[1]
中。
当节点全副迁徙结束,将会开释 ht[0]
占用空间, 并将 ht[1]
设置为 ht[0]
。
扩容 操作须要将 ht[0]
所有键值对都 Rehash
到 ht[1]
中,如果键值过多,假如存在十亿个键值对,这样一次性的迁徙,势必导致服务器会在一段时间内进行服务。
另外如果每次 rehash
都会阻塞以后操作,这样对于客户端解决十分不敌对。
为了防止 rehash
对服务器的影响,Redis 采纳渐进式的迁徙形式,缓缓将数据迁徙扩散到多个操作步骤。
这个操作依赖字典中一个属性 rehashidx
, 这是一个索引地位计数器,记录下一个哈希表 table 数组上元素,默认状况为值为 -1。
假如此时扩容前字典如图所示:
当开始 rehash 操作,rehashidx
将会被设置为 0。
这个期间每次收到减少,删除,查找,更新命令,除了这些命令将会被执行以外,还会顺带将 ht[0]
哈希表在 rehashidx
地位的元素 rehash 到 ht[1]
中。
假如此时收到一个 K3 键的查问操作,Redis 首先执行查问操作,接着 Redis 将会为 ht[0]
哈希表上 table
数组第 rehashidx
索引上所有节点都迁徙到 ht[1]
中。
当操作实现之后,再将 rehashidx
属性值加 1。
最初当所有键值对都 rehash
到 ht[1]
中时,rehashidx
将会被从新设置为 -1。
尽管渐进式的 rehash 操作缩小了工作量,然而却带来键值操作的复杂度。
这是因为在渐进式 rehash
操作期间,Redis 无奈明确晓得键到底在 ht[0]
中,还是在 ht[1]
中, 所以这个时候 Redis 不得不查找两个哈希表。
以查找为例,Redis 首先查问 ht[0]
,如果没找到将会持续查找 ht[1]
, 除了查问以外,更新,删除也会执行如上的操作。
增加操作其实就没这么麻烦,因为 ht[0]
不会在应用,那就对立都增加到 ht[1]
中就好了。
最初咱们再比照一下 Java HashMap 扩容操作,它是一个一次性操作,每次扩容须要将所有键值对都迁徙到新的数组中,所以如果数据量很大,耗费工夫就会久。
总结
Redis 字典应用哈希表作为底层实现,每个字典蕴含两个哈希表,一个平时应用,一个仅在 rehash 操作中应用。
哈希表总的来说,跟 Java HashMap 真的很相似,底层实现也是一个数组加链表数据结构。
最初,当对哈希表进行扩容操作工夫,将会采纳渐进性 rehash 操作,缓缓将所有键值对迁徙到新哈希表中。
其实理解 Redis 字典的其中的原理,再去比拟 Java HashMap,其实能够发现这两者有如此多的类似点。
所以学习这类常识时,不要仅仅去背,咱们要理解其底层原理,知其然知其所以然。
帮忙材料
- https://redisbook.readthedocs…
欢送关注我的公众号:程序通事,取得日常干货推送。如果您对我的专题内容感兴趣,也能够关注我的博客:studyidea.cn