欢迎访问 内存溢出 —— 独立后端与系统工程技术博客

专注于分布式系统、Linux内核、数据库存储与后端工程实践

Redis 核心数据结构底层源码与渐进式 Rehash

发表于:|最后更新:|分类:数据库与存储|阅读:6124 次

Redis 凭借单线程事件循环(Reactor 模式)实现亚毫秒级的高吞吐,其底层的内存数据结构设计堪称极致。以常见的哈希类型(Hash)为例,其底层在元组较少且短时采用紧凑列表(Listpack/Ziplist)以最大化节省内存开销并规避内存碎片,当键值规模超过阈值后转换为真正的字典(dict)。Redis 的 dict 结构内部包含两个哈希表:ht[0] 与 ht[1]。在普通运行时,所有读写均作用于 ht[0]。当哈希表元素过多(负载因子超过 1)或过少(低于 0.1)时,系统需要进行扩缩容(Rehash)。如果对包含数千万个键的哈希表进行一次性内存拷贝与重哈希,单线程将被完全卡死,造成严重的不可用风险。为解决这一问题,Redis 采用了“渐进式 Rehash”(Incremental Rehash):为 ht[1] 分配更大(通常为下一个 $2^n$)或缩容后的内存空间。内部维护计数器 rehashidx = 0。在后续对该字典的每一次增删改查操作中,顺带将 ht[0] 在 rehashidx 索引桶位上的所有键值迁移至 ht[1],并将 rehashidx 递增。后台定时任务(serverCron)也会在空闲时段主动执行渐进式迁移。迁移全部完成后,释放 ht[0],将 ht[1] 设置为 ht[0]

,rehashidx 重置为 -1。