Redis是如何避免“数组+链表”的过长问题
目录
一、扩展和收缩
二、使用高质量的哈希函数
三、使用跳跃表（skiplist）或其他数据结构
四、哈希表分片
一、扩展和收缩
Redis通过动态调整哈希表的大小来解决“数组+链表”的长度问题，这涉及到两个过程：扩展(Expand)和收缩(Shrink)。
-
扩展:
- 当哈希表的负载因子(load factor)超过一个阈值时，Redis会进行扩展操作。
- 负载因子是哈希表已存储的元素数量与哈希表大小的比值。
- 扩展操作包括分配一个新的更大的哈希表，并逐渐将旧表中的所有键值对rehash到新表中。
-
收缩:
- 相对地，当负载因子低于另一个阈值时，Redis会执行收缩操作，减少哈希表的大小。
- 这通常发生在删除大量键值对后，为了节省内存空间，Redis会将键值对rehash到一个更小的哈希表中。
负载因子和rehash
-
负载因子的计算:
- 负载因子 = 哈希表中的元素数量 / 哈希表的大小
- 当负载因子太高时，意味着发生哈希冲突的可能性增加，链表会变得较长，影响性能。
- 当负载因子太低时，意味着内存使用不够高效。
- 默认扩展负载因子:
- 在没有进行BGSAVE或BGREWRITEAOF操作时，负载因子超过1时进行扩展。
- 如果正在进行BGSAVE或BGREWRITEAOF操作，则负载因子阈值提高到5，即负载因子超过5时进行扩展。这意味着在正常情况下，当哈希表的负载因子超过1时，Redis就会触发扩展操作。但是，如果Redis正在进行磁盘写操作，如BGSAVE或BGREWRITEAOF，为了避免在磁盘IO已经很高的情况下进一步增加内存重分配的负担，它会提高扩展操作的负载因子阈值到5。这样可以在一定程度上平衡内存使用和磁盘IO之间的性能。
- 当哈希表的负载因子小于0.1时，Redis会进行收缩操作。
-
rehash过程:
- rehash是将所有键值对从旧的哈希表移动到新的哈希表的过程。
- Redis使用渐进式rehash，它不是一次性完成，而是分多次进行，以避免长时间的阻塞。
渐进式rehash
- 渐进式rehash的实现:
- 在rehash期间，Redis同时保持旧表和新表。
- 每次对哈希表的操作（如添加、删除、查找）时，Redis会将旧哈希表的一部分键值对迁移到新哈希表。
- 这样可以将rehash的计算量分散到每个操作上，避免一次性的大量计算导致服务不可用。
二、使用高质量的哈希函数
Redis使用MurmurHash等高质量的哈希函数来减少哈希冲突。
三、使用跳跃表（skiplist）或其他数据结构
对于有序数据集合，Redis使用跳跃表而不是链表来存储元素，跳跃表的平均和最坏情况下的时间复杂度都比链表要好。
四、哈希表分片
在Redis集群模式下，哈希表会被分成多个分片，每个分片由不同的Redis节点管理，这样可以分散负载，减少单个链表过长的风险。