写点什么

redis 渐进式 rehash

  • 2024-08-02
    北京
  • 本文字数:682 字

    阅读完需:约 2 分钟

本文分享自天翼云开发者社区《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]的顺序依次进行查询。

用户头像

还未添加个人签名 2022-02-22 加入

天翼云是中国电信倾力打造的云服务品牌,致力于成为领先的云计算服务提供商。提供云主机、CDN、云电脑、大数据及AI等全线产品和场景化解决方案。

评论

发布
暂无评论
redis渐进式rehash_数据库_天翼云开发者社区_InfoQ写作社区