Redis 为了操作效率使用哈希表来存储键值对,访问时只需要 O(1) 时间复杂度。

1. 全局哈希表

为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对

哈希表由多个哈希桶组成,哈希桶中的 entry 元素中保存了*key*value指针,分别指向了实际的键和值。

全局哈希表

哈希表让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值,就可以知道它所对应的哈希桶位置,然后就可以访问相应的 entry 元素。

key-value 访问过程:

  1. 通过 key 计算出对应的哈希值
  2. 根据哈希值计算出对应的哈希桶索引
  3. 根据索引找到对应 entry,如果是哈希链则挨个查找到对应的 entry
  4. String 类型则 entry 中的 value 就是要查找的值,集合类型则需要在 value 中进一步查找

2. 哈希冲突

当你往哈希表中写入大量数据时,哈希冲突是不可避免的问题。

哈希冲突也就是指,两个 key 的哈希值和哈希桶计算对应关系时,正好落在了同一个哈希桶中。

Redis 解决哈希冲突的方式,就是链式哈希(链地址法)。链式哈希也很容易理解,就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。

哈希冲突

但是,这里依然存在一个问题,哈希冲突链上的元素只能通过指针逐一查找再操作。

如果哈希表里写入的数据越来越多,哈希冲突可能也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。

所以,Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。

3. Rehash

为了使 rehash 操作更高效,Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2,下文将当前正使用的称作主哈希表,用于扩容的称作备用哈希表。

一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。随着数据逐步增多,Redis 开始执行 rehash,这个过程分为三步:

  1. 给哈希表 2 分配更大的空间,例如是当前哈希表 1 大小的两倍;
  2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
  3. 释放哈希表 1 的空间。

到此,我们就可以从哈希表 1 切换到哈希表 2,用增大的哈希表 2 保存更多数据,而原来的哈希表 1 留作下一次 rehash 扩容备用。

Rehash

为了避免第二步拷贝数据阻塞 Redis 主线程,Redis 采用了 渐进式 Rehash

简单来说就是在第二步拷贝数据时,Redis 仍然正常处理客户端请求。

  1. 每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;
  2. 等处理下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entries。

即 每处理一个请求就从主哈希表拷贝一个哈希桶到备用哈希表。将一次拷贝拆分为多次拷贝从而减少拷贝过程中对 Redis 主线程的影响。

4. 小结

  1. Redis 使用哈希表存储键值对
  2. 采用链地址法解决哈希冲突
  3. 为避免阻塞主线程,采用渐进式 Rehash

5. 参考资料

《Redis 设计与实现》

Redis 核心技术实战

https://en.wikipedia.org/wiki/Hash_table