Hash 冲突怎么办?

Redis 通过链式哈希解决冲突:也就是同一个 桶里面的元素使用链表保存。但是当链表过长就会导致查找性能变差可能,所以 Redis 为了追求快,使用了两个全局哈希表。用于 rehash 操作,增加现有的哈希桶数量,减少哈希冲突。

开始默认使用 「hash 表 1 」保存键值对数据,「hash 表 2」 此刻没有分配空间。当数据越来越多触发 rehash 操作,则执行以下操作:

  1. 给 「hash 表 2 」分配更大的空间;
  2. 将 「hash 表 1 」的数据重新映射拷贝到 「hash 表 2」 中;
  3. 释放 「hash 表 1」 的空间。

值得注意的是,将 hash 表 1 的数据重新映射到 hash 表 2 的过程中并不是一次性的,这样会造成 Redis 阻塞,无法提供服务。

而是采用了渐进式 rehash,每次处理客户端请求的时候,先从「 hash 表 1」 中第一个索引开始,将这个位置的 所有数据拷贝到 「hash 表 2」 中,就这样将 rehash 分散到多次请求过程中,避免耗时阻塞。

发表评论

后才能评论