type
status
date
slug
summary
tags
category
icon
password
创建时间
Sep 21, 2024 07:05 AM
rehash 可能带来的操作阻塞
哈希冲突链上的元素只能通过指针逐一查找再操作。当哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。
因此，Redis 需要对哈希表做 rehash 操作：增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。
此外，渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，Redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时，这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。
Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。
rehash 过程：
- 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中──渐进式 rehash；
- 为什么采用渐进式 rehash？如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。
- 方法步骤：
- Redis 仍正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；
- 等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。
- 释放哈希表 1 的空间
集合数据操作效率
对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。
- 通过全局哈希表找到对应的哈希桶位置；
- 在集合中再增删改查
集合的操作效率和哪些因素相关？
- 集合的底层数据结构有关。使用哈希表实现的集合，要比使用链表实现的集合访问效率更高。
- 操作效率和这些操作本身的执行特点。读写一个元素的操作要比读写所有元素的效率高。
底层数据结构
- 整数数组
- 双向链表
- 哈希表
- 压缩列表
- 跳表 redis 中的跳表
不同操作的复杂度——四句口诀
- 单元素操作是基础；
- 单元素操作是指每一种集合类型对单个数据实现的增删改查操作。
- 例如：
- Hash 类型的
HGET、HSET和HDEL：用哈希表作为底层数据结构，复杂度是 O(1) - Set 类型的
SADD、SREM、SRANDMEMBER：用哈希表作为底层数据结构，复杂度是 O(1) - 注意：集合类型支持同时对多个元素进行增删改查。此时，这些操作的复杂度，就是由单个元素操作复杂度和元素个数决定的。
- 范围操作非常耗时；
- 范围操作是指集合类型中的遍历操作，可以返回集合中的所有数据。
- 例如：
- Hash 类型的
HGETALL和 Set 类型的SMEMBERS - List 类型的
LRANGE和 ZSet 类型的ZRANGE SCAN系列操作（包括HSCAN，SSCAN和ZSCAN），实现了渐进式遍历：每次只返回有限数量的数据。
- 统计操作通常高效；
- 统计操作是指集合类型对集合中所有元素个数的记录。
- 例如，
LLEN和SCARD：这类操作复杂度只有 O(1)，这是因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时，这些结构中专门记录了元素的个数统计。
- 例外情况只有几个
- 例外情况是指某些数据结构的特殊记录。
- 压缩列表和双向链表都会记录表头和表尾的偏移量。
- 例如，List 类型的
LPOP、RPOP、LPUSH、RPUSH这四个操作是在列表的头尾增删元素，可以通过偏移量直接定位。复杂度只有 O(1)
问题
整数数组和压缩列表作为底层数据结构的优势是什么？
整数数据和压缩列表在内存中是连续的，数据也是直接存储在其中，不需要额外使用指针来指向数据的地址。
📎 参考
- 极客时间，蒋德钧《Redis核心技术与实战》