为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有的键值对。
介绍哈希表
哈希表是键值对的集合，通过键（key）即可快速取出对应的值（value），可以用来提高等值查询的效率。
一个哈希表，其实就是一个数组，数组的每个元素被称为一个哈希桶，每个哈希桶中保存了键值对数据。
键 key 通过 Hash 函数映射到哈希桶，那么无法避免的会产生 Hash 冲突，也就是说多个不同的 key 映射到相同的哈希桶。常用的解决 Hash 冲突的办法有：
- 链地址法：如果出现了 Hash 冲突，产生 Hash 冲突的键值对，形成一个链表。
- 开放寻址法：如果出现了 Hash 冲突，我们就重新探测一个空闲位置，将其插入。
技术是为了解决问题而生的，哈希表的作用是：让我们可以用 O(1) 的时间复杂度，来快速查找到键值对。我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry。
介绍 Redis 的哈希表方案
- 全局哈希表
- rehash 操作
Redis 使用一个全局哈希表来保存所有的键值对。
全局哈希表
在 Redis 中，value 可以是不同的类型，那么哈希桶是如何统一的保存 entry 的呢？其实，哈希桶中的 entry 保存的并不是 key 和 value 的值，而是 key 和 value，即指向具体值的指针。这样就统一的保存了不同类型的 value。
rehash 操作
如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的 entry 查找耗时长，效率降低。
为了解决哈希冲突链过长，导致查找效率低的问题，随着 Entry 数量的增多，Redis 会对哈希表做 rehash 操作。并且 Redis 采用了渐进式 rehash 来避免执行 rehash 这个耗时操作导致的线程长时间阻塞。
渐进式 rehash 扩容
rehash 就是增加现有的哈希桶数量，让逐渐增多的 entry 能在更多的哈希桶之间分散保存，减少单个桶中的entry 数量，从而减少单个桶中的冲突。
为了使 rehash 操作更高效，Redis 使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配内存空间。随着 Entry 数量的增多，Redis 开始执行 rehash 操作，这个过程分为三步：
- 给哈希表 2 分配更大的内存空间，例如是当前哈希表 1 大小的两倍；
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
- 释放哈希表 1 的内存空间。
到此，我们就可以从哈希表 1 切换到哈希表 2，用哈希桶更多的哈希表 2 保存 Entry，而原来的哈希表 1 留作下一次 rehash 扩容备用。
rehash 的过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据全部迁移，会造成 Redis 线程长时间阻塞，无法服务其他请求。
为了避免 Redis 线程长时间阻塞这个问题，Redis 采用了渐进式 rehash。
渐进式 rehash，简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。
这样就巧妙地把一次性大量数据拷贝的开销，分摊到了多次处理请求的过程中，避免了线程长时间阻塞，保证了数据的快速访问。
我的疑问：是主线程执行 rehash 操作吗？为什么要用主线程执行 rehash 操作，用另外一个线程不行吗 数据拷贝是拷贝什么？是拷贝指针吗
参考资料
若有收获，就点个赞吧
0 人点赞
