Redis 中 hash 扩容与缩容

Redis 中 hash 扩容与缩容 当哈希表中元素数量逐渐增加时，此时产生 hash 冲突的概率逐渐增大，且由于 dict也是采用拉链法解决 hash 冲突的，随着 hash冲突概率上升，链表会越来越长，这就会导致查找效率下降。相反，当元素不断减少时，元素占用 dict 的空间就越少，出现对于内存的极致利用，此时就需要进行缩容操作。 既然说到扩容和缩容，那就想到了负载因子。负载因子一般用于描述集合当前被填充的程度。在 Redis 的字典 dict 中，负载因子 = 哈希表中已保存节点数量 / 哈希表的大小，即： load factor = ht[0].used / ht[0].size   Redis中，三条关于扩容和缩容的规则： 1. 没有执行 BGSAVE 和 BGWRITEAOF 指令的情况下，哈希表的负载因子大于等于 1 时进行扩容。 2. 正在执行 BGSAVE 和 BGWRITEAOF 指令的情况下，哈希表的负载因子大于等于 5 时进行扩容。 3. 负载因子小于 0.1 时，Redis 自动开始对哈希表进行收索操作。   其中，扩容和缩容的数量大小也是有一定的规则： 1. 扩容：扩容后的 dicEntry 数组数量为第一个大于等于 ht[0].used * 2 的 2^n 2. 缩容：缩容后的 dicEntry 数组数量为第一个大于等于 ht[0].used 的 2^n     Redis 中 rehash 与 Java 中的 HashMap 类似，当 Redis 中的 dict 进行扩容或者缩容，会发生 reHash 过程。 Java 中 HashMap 的 rehash 过程如下：新建一个哈希表，一次性将当前所有节点进行 rehash 然后复制到新哈希表相对应的位置上，之后释放掉原有 hash 表，而持有新的表，这个过程有一个时间复杂度为 O(n) 的操作。而对于单线程的 Redis 而言很难承受这么高的时间复杂度的操作，因而其 rehash 的过程有所不同，使用一个称之为渐进式 rehash 的方式，一点一点地进行搬迁。其过程如下： 1. 假设当前数据在 dictht[0] 中，那么首先为 dictht[1] 分配足够的空间，如果是扩容，则 dictht[1] 大小就按照扩容规则设置；如果时缩减，则 dictht[1] 大小就按照缩减规则进行设置； 2. 在字典 dict 中维护一个变量，rehashidx = 0，表示 rehash 正式开始； 3. rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 dictht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 dictht[1]，当一次 rehash 工作完成之后，程序将 rehashidx 属性值 +1。同时在 saveCron 中调用 rehash 相关函数，在 1ms 的时间内，进行 rehash 处理，每次仅处理少量的转移任务(100个元素); 4. 随着字典表操作的不断执行，最终在某个时间点上 dictht[0] 的所对应的键值对都会被 rehash 至 dictht[1]，这时程序将 rehashidx 的属性值设置为 -1，表示 rehash 操作已完成；   redis 内有一个定时器，会定时去判断 rehash 是否完成，如果没有完成，则继续执行 rehash。从而解决上述 1，3问题，即：无访问数据如何进行rehash。 对于添加操作，会将新的数据直接添加到 dictht[1] 上面，这样就可以保证 dictht[0] 上的数量只减少不会增加。而对于删除、更新、查询操作，会执行在 dictht[0] 上进行，尤其是这三个操作，都会涉及到擦汗寻，当在 dictht[0] 上查询不到时，会接着去 dictht[1] 上查找，如果再找不到，则说明不存在该 k-v 值。   渐进式 rehash 的优缺点 优点：采用了分而治之的思想，将 rehash 操作分散到每一个对应该哈希表的操作上以及定时函数上，避免了集中式 rehash 带来的性能压力； 缺点：再 rehash 的时间内，需要保留两个 hash 表，对内存的占用稍大，而且如果在 redis 服务器本来内存满了的时候，突然进行 rehash 会造成大量的 key 被抛弃；