redis渐进式rehash

本文分享自天翼云开发者社区《redis渐进式rehash》，作者:l****n
Redis是k-v型数据库，其内部计划了一种dict类型的数据结构用来存储键值结构。
dict 通常的存储结构是 Key-Value 情势的，通过 Hash 函数对 key 求 Hash 值来确定 Value 的位置，因此也叫 Hash 表，是一种用来解决算法中查找问题的数据结构，默认的算法复杂度接近 O(1)。
利用哈希表总是会碰到哈希碰撞问题，dict利用拉链法将发生碰撞的元素组成链表，挂在发生碰撞的桶下，但是随着存储元素的不断增加，碰撞发生的几率也不断增大，一个桶下链接的链表长度越来越长，定位一个key的时间复杂度就无法包管了，redis作为内存数据库，自己寻求的是更高的处理性能，线性增加的耗时无疑是不能担当的，为了减少hash碰撞，需要创建一个更长的hash表，让元素可以大概均匀的分布在hash表上。
所以，Dict内部定义了两个hashtable，分别是dictht[0]和dictht[1]，元素数量不多时，dict只在dictht[0]上存储元素，dictht[1]不分配空间。当dictht[0]的元素个数到达一定数量，会触发扩容过程，让dictht[1]指向一个2倍长度的空间，然后进行rehash， 将dictht[0]上的元素重新映射到dictht[1]上。
如果dictht[0]上有许多元素，进行rehash无疑是一个很耗时的过程，加上redis是单线程，如果想一次完成rehash，就会很长时间的阻塞业务，所以redis选择渐进式rehash。每次dictht[0]收到一个请求，只会将一个索引上的链表进行重新映射。
在将数据拷贝至dictht[1]时，dictht[0]仍然对客户端提供服务。Rehash期间，如果有新的插入元素请求时，直接将元素插入到dictht[1]中，有客户端查询请求到来, 按照dictht[0]->dictht[1]的顺序依次进行查询。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。