企业官网建设流程全解析

1. 双表结构：为什么一个哈希表要维护两个底层数组

1.1 三个结构体，先混个脸熟

聊到Redis源码，我最想让人先读的就是dict.c。很多人把Redis当成缓存用，键值存取、过期删除、集群扩容用得飞起，但真正面对"为什么单线程还能扛住千万级QPS"这类问题时，答案往往不在网络层，而在这些最基础的数据结构里。这一讲我们接着漫话系列的节奏，从dict这张哈希表聊起，重点拆它的渐进式rehash：一个哈希表为什么要维护两张底层数组，为什么迁移一次只能搬一个桶，迁移过程中读写、遍历又如何保证不错不乱。

dict的实现在dict.h和dict.c两个文件里，核心就三个结构体：

typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; unsigned long iterators; } dict;

dictEntry就是哈希桶里挂的链表节点，冲突用链地址法解决；dictht才是真正的哈希表，有一个数组指针table、一个size、一个掩码sizemask、一个已用节点数used；最外层dict把两个dictht叠在一起，塞进ht[2]数组。

关键就在这个ht[2]上。平时数据都放在ht[0]，ht[1]只在扩容缩容时启用。Redis要扩容或者缩容时，先根据新容量计算出新表，然后把ht[1]指向新表，再一点一点把ht[0]的数据搬过去。搬完之后把ht[0]变成空表、把ht[1]切换成"正式表"，整个过程才算完成。

这里有个很直观的问题：为什么不能一次性把旧表数据全部搬过去？看看rehashidx这个字段就懂了，它记录的是当前搬到哪个桶了，等于一个游标或者进度条。一个字段的存在，恰恰说明了设计者本来就没打算"一口气搬完"。

1.2 一次性搬家的代价有多大

假设一张表里有1000万个key，如果dict决定扩容，按最简单的思路，应该重新分配一块更大的数组，把所有已有的dictEntry重新计算哈希位置、重新挂链，然后释放旧表。这件事本身不算复杂，复杂的是时间。

1000万个key重新哈希，算上哈希函数调用、取模定位、链表头插，单线程下至少是数百毫秒到数秒的量级。Redis的所有命令都在同一个事件循环里串行执行，这期间只要rehash一启动，别的客户端请求就全部排队等着。对于一个追求亚毫秒级延迟的缓存系统来说，这种"卡顿"是不可接受的。

更麻烦的是，内存分配本身也可能触发内存碎片整理或者系统调用，让耗时变得更加不稳定。这就是渐进式rehash存在的原因：把一次大搬家拆成无数次小搬家，每次命令执行时顺带搬一两个桶，搬完就走。这个思路说起来简单，真正落地时还要解决很多细节，我会在下面几节逐步拆开。

顺带说一句，学习这张表源码时，我用过一个笨办法：先把三个结构体画在纸上，手动模拟一次扩容，把10个key从容量4的表挪到容量8的表，每一步都标注rehashidx变化。模拟完一遍之后，再看代码里的while循环，瞬间就通了。我建议你也可以试试，尤其是后面讲dictScan那一节，纸笔模拟比盯着代码看十遍都管用。

2. 渐进式rehash的分批迁移：一次只搬一个桶

2.1 dictRehash主循环拆解

渐进式rehash的核心逻辑都集中在dictRehash函数里。我先贴一段带注释的代码，这是理解整个机制的重中之重：

int dictRehash(dict *d, int n) { int empty_visits = n * 10; if (!dictIsRehashing(d)) return 0; while (n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; /* 从当前游标位置开始，跳过空桶 */ while (d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits) return 1; } de = d->ht[0].table[d->rehashidx]; while (de) { uint64_t h = dictHashKey(d, de->key) & d->ht[1].sizemask; nextde = de->next; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } return 1; }

函数接收两个参数：d是字典本身，n是本次允许迁移的桶数上限。while循环里每迭代一次，就处理旧表的一个桶：把桶上挂的整条链表都取下来，逐个计算新哈希位置，用头插法挂到新表的对应桶里。每搬完一个桶，rehashidx就去掉旧表这个桶的指针，然后自增。

这套逻辑有个很有意思的特性：一次dictRehash调用所消耗的时间，并不正比于n，而是正比于"被搬的桶里实际挂了多少个key"。如果运气好，连续遇到好几个空桶，可能搬了n个桶却只处理了几个节点。反过来，如果某个桶上挂了特别长的链表，一次调用也可能比较耗时。这也是后面要讲的时间片安排的起因。

2.2 empty_visits空桶安全阀

注意上面代码里的empty_visits，这是较新版本Redis加进去的一个限制。早期的实现里，跳过空桶就是一个简单的while，一直自增rehashidx直到找到非空桶。

表面上看没什么问题，但极端情况下会翻车。假如一张表扩容后比较稀疏，大量桶都是空的，rehashidx要连续越过成千上万个空桶才能找到一个非空桶，那么这个"看起来只搬了一小步"的调用，实际花的时间会突然变得不可控。

empty_visits的逻辑很朴素：每次调用只允许最多访问empty_visits个空桶，超过就立即返回，把这次迁移任务先"挂账"，下次再接着从当前位置继续。n是本次计划迁移的桶数，允许探测的空桶数限制是n的10倍。

这个细节完美解释了"渐进式"设计里一个经常被忽略的点：不仅要控制迁移的总量，还要控制空桶探测的代价。迁移任务本身可以被拆碎，但如果拆碎以后每一次获取的任务量会随机变大，延迟抖动依然存在。Redis用一个计数器把这个随机性也兜住了。

我最初读这段代码时，习惯性地以为while (d->ht[0].table[d->rehashidx] == NULL)就是一个简单的"找下一个非空桶"，后来在压测环境里用稀疏表模拟旧版逻辑，发现单次命令延迟确实会出现明显的尖峰。加上empty_visits之后，尖峰就被削平了。这个细节很小，但如果你在别的系统里见过"看上去是增量任务，实际某一次执行突然很慢"的诡异问题，往往就是缺少这一道安全阀。

2.3 时间片怎么分配：一步与一百毫秒

有了dictRehash这个"最小执行单元"，接下来就要解决什么时候调用它的问题。Redis里有两套调度逻辑：

一套是操作触发。在dictAddRaw、dictFind、dictDelete等常用操作里，都会先检查dictIsRehashing，如果正在rehash，就调用_dictRehashStep，这个函数每次只搬一个桶，也就是n=1。这样每一次普通命令，都顺带为迁移贡献一点点工作量，平摊在请求链路上，用户几乎感知不到额外延迟。

另一套是周期任务触发。Redis的serverCron会定期执行incrementalRehash逻辑，用一个专门的循环去调用dictRehashMilliseconds，让迁移在给定时间内持续进行，默认一般是1毫秒。这个函数内部会计算本次迁移开始前和开始后的CPU时间差，一旦超过设定上限就立即返回，哪怕任务没搬完也不继续。

理解这两套机制，等于理解了Redis对"单线程不能卡顿"的执念：既利用每一次请求把迁移任务悄悄地做一点，又利用周期任务在空闲时加速推进。搬迁的进度不是由"还剩多少数据"决定的，而是由"系统当前愿不愿意接受延迟代价"决定的。这种用时间片换平滑性的想法，在后面的scan遍历里还会再次出现。

3. 扩容和缩容的触发策略：负载因子里面的算盘

3.1 扩容的三个触发路径

rehash不能随便启动，Expansion or shrink都要有明确条件。Redis判断是否需要扩容时，主要走三个分支：

实现里最核心的是_dictExpandIfNeeded。真实代码逻辑会先看是否已经在rehash，是的话直接返回；接着看ht[0].used是否为0，是的话扩容到4；再看used是否大于等于size，满足则扩容到used的2倍。

这里有个容易误解的地方：扩容后的目标容量为什么是used2，而不是size2？考虑一种情况：表已经很大了，size是65536，但里面只存了100个key，此时不触发扩容，因为used远小于size。如果哪天这100个key涨到了65536个，那一刻扩容目标就是131072。这个数值更贴近"实际数据量需要翻倍"，而不是机械地把现有容量翻倍，能避免扩容后容量仍然不够用的尴尬。

至于dict_force_resize_ratio，它是个保底机制。Redis在处理某些后台任务时，可能临时设置dict_can_resize为0，不允许自动resize。如果这时候哈希表已经严重失衡，每个桶平均挂5个以上key，强制策略会把"禁止resize"这个开关一脚踢开，避免数据堆积太深导致查询效率崩塌。

3.2 为什么容量必须是2的幂

我在漫话系列的更早几讲里提到过，Redis在定位哈希桶时不用取模，而是用位与运算，这要求容量永远是2的幂。dictExpand函数里有一个_nextPower，专门计算大于等于目标值的最小2的幂。比如目标值是11，就扩到16；目标值是2000，就扩到2048。

使用位与替代取模，核心原因是速度。哈希值本身是个无符号整数，sizemask等于size-1，那么h & sizemask的结果，就等价于h对size取模。更重要的是，当表扩容到两倍大时，一个元素新位置的计算可以套在旧位置上做快速推导。

举个例子：某个key的哈希值是26，二进制是11010。容量8时sizemask是7，26 & 7等于2，所以它挂在桶2。容量翻倍到16以后，sizemask变成15，26 & 15等于10，也就是旧桶2加上8，新高位的那个二进制位直接决定了它会落在2还是2+8。这个"旧桶+新旧位偏移"的关系，是后面理解dictScan不重不漏遍历的关键，先记着。

3.3 缩容的尺度也别小看

哈希表不仅会变大，还会变小。当大量key被删除，表里元素变得很少时，如果不缩容，内存就白白浪费了。Redis缩容的触发点主要放在serverCron里，通过tryResizeHashTables去检查，如果used和size的比例关系变得极度不协调，就会调用dictResize。

dictResize的逻辑是找到大于等于used的最小2的幂，然后执行扩容流程。注意缩容和扩容走的是同一个expand流程，区别只在于目标容量怎么计算。缩容以后，表会变得紧凑，内存占用随之下降，但代价是可能很快又需要扩容。Redis对这个反复过程有一定容忍度，毕竟哈希表本来就是用内存换时间的数据结构，不能指望它像某些紧凑索引那样精打细算。

我刚开始读这份源码时，曾经想当然地认为缩容是"按比例缩小"，比如used到了50%就缩一半。看了代码才明白，缩容是直接按used的实际数量去凑一个2的幂，所以即使表缩了，新的容量依然有能力承载当前全部元素，不存在缩完以后稍微再写入几个key就立刻又要扩容的抖动。当然，这个判断也不是绝对的，具体的阈值和策略在不同版本里略有调整，核心思路是不变的。

4. 迁移进行时的读写细节：双表查询与只进新表

4.1 读路径为什么两个表都要看

一旦rehash开始，Redis就处在一种"一半在旧家一半在新家"的中间状态。此时读操作要怎么办？很简单，先查旧表，再查新表，两边都要看。

dictFind里有一个两层循环，table从0遍历到1，分别查ht[0]和ht[1]。第一遍先在旧表里定位，用旧表的sizemask计算桶下标，沿着链表依次比较key；如果找到了就直接返回，没找到且此时还在rehash中，就继续到新表里再找一遍。如果已经不在rehash阶段，第二遍干脆跳过。

为什么先查旧表而不是先查新表？因为rehash是渐进的，绝大多数数据仍然留在旧表里，先查旧表能更快命中，减少无谓的新表查询。尤其在rehash刚开始时，新表几乎是空的，先查新表等于多走一遍空流程。

需要特别注意的是，rehash过程中两次查询看到的表状态可能是变化的。比如第一次在旧表查某个key，没找到；等要查新表时，那个key的那个桶恰好已经从旧表搬了过来，于是新表命中。这种情况是允许的。但如果旧表里已经找不到，而且rehash正好完成了，新表又变成正式表，那么第二遍查询也不会漏。这个读路径设计把中间态的复杂性都兜住了。

4.2 写路径为什么只进新表

读操作两边都查，写操作反而只认一边——新表。dictAddRaw在插入新元素时，会先看dictIsRehashing，如果在rehash，就选择ht[1]作为插入目标表，否则才用ht[0]。

这个设计初看有点反直觉：旧表还剩下很多数据呢，新元素凭什么直接写新表？但仔细一想，这正是保证rehash能结束的关键。如果新元素还往旧表写，那么旧表一边被搬空、一边又被填满，ht[0].used永远降不到0，rehash就可能永远完不成。规定只往新表写，意味着旧表只有流出没有流入，总有一天会彻底清空。

这个"存量搬走、增量直入新家"的思路，在工程上非常常见。做在线数据迁移时，数据同步工具往往也是这个套路：先把存量数据分批拷贝，增量变更进新的存储系统，最后切换读流量。Redis在哈希表这个微观场景里把同一套原则执行得干干净净。

对于更新操作，比如replace或者delete，Redis的处理是：先在新表里找，找不到再去旧表里找。更新时如果key在新表里，直接改新表的节点；在旧表里，就改旧表的节点。删除也是同样，两边都可能删，重要的是删除时要维护对应表的used计数。只要记住"增量入新、查找双表、更新删除双表处理"，读写基本就不会出错。

4.3 完成那一刻的原子动作

当旧表最后一个元素也被搬走时，dictRehash的收尾动作值得一提。函数检测到ht[0].used变成0，于是释放整个旧表的数组内存，然后做一次结构体级的"换血"操作：

d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1;

这三行做的事情是：把ht[1]整块赋值给ht[0]，于是ht[0]变成了新的正式表；然后把ht[1]结构体清零，等待下次扩容再复用；最后把rehashidx重置为-1，表示rehash结束。

整个切换过程没有任何数据移动，纯粹是结构体赋值，所以速度极快。rehashidx这个"进度指针"在此刻失效，哈希表从"迁移中"变回"静止状态"。如果你在调试时打印dict的内部结构，能看到rehashidx的值从非负数突然变成-1，就意味着经历了一轮完整的扩容或缩容。

这里有一个小经验：调试rehash最好用gdb或者日志方式，观察rehashidx和ht[0].used、ht[1].used三个值的变化。光是盯着这三个数演变，你就能把整个流程了然于心。比死记代码清晰得多。

5. 边迁移边遍历的难题：dictScan的二进制反转算法

5.1 单调递增的游标为什么一定会出错

rehash期间如果需要遍历整个字典，比如执行SCAN命令，问题就来了。普通哈希表的遍历可以很简单：游标从0递增到size-1，依次访问每个桶。但在rehash进行中，这个办法是行不通的。

回到前面的例子。容量8的表扩容到16时，旧桶2里的元素会按哈希值的高位，被分到新桶2或者新桶10。如果游标按0、1、2、3这样的顺序递增，走到旧桶2时，桶里可能只剩下还没迁移掉的部分；那些已经搬到新桶10的元素，在这次遍历里就被漏掉了。有人可能会说，那我在遍历旧桶2时，同时去新桶10看一眼。可一旦游标按顺序走到10，又会把新桶10再访问一遍，之前访问过的元素被重复返回。

所以这里要解决的，是"迁移过程中，一个key要么被遍历恰好一次，要么恰好某个时刻在旧表被访问、要么在新表被访问，但不能两次都访问，更不能一次都不访问"。单调递增天然做不到，因为桶分裂后两个桶之间的访问顺序，跟迁移发生的时刻没有固定关系。

5.2 二进制反转的巧妙之处

Redis的解决方案是reverse binary iteration，也就是二进制反转游标。核心代码只有四行：

v |= ~m0; v = rev(v); v++; v = rev(v);

看起来像故意写反了，但它干的其实是：在原始游标空间里，不是从最低位递增，而是从最低位的"镜像"递增，等效于按二进制反转后的顺序去扫桶。

举一个具体例子。容量4的表，sizemask是3，正常递增游标是0、1、2、3。二进制反转之后，访问顺序变成0、2、1、3（二比特反转：00->00, 01->10, 10->01, 11->11）。容量8时，sizemask是7，反转后顺序是0、4、2、6、1、5、3、7。

这个顺序有个了不起的性质：在扩容时，旧桶k分裂出的两个新桶k和k+旧容量，在反转序列里是相邻的。比如旧容量4时，桶0分裂到新桶0和4；反转序列里0和4正好紧挨着。这意味着，只要游标扫到这对桶中的任何一个，另一个要么已经被扫过，要么马上就会被扫到，不会出现一个元素落进两个桶之间"夹缝"的情况。

读代码时我一直有个困惑：为什么SCAN返回的游标看起来毫无规律，有时是0，下一次是4，再下一次是2，跟纯递增完全不一样。后来自己在纸上列了一遍反转序列才明白，这不是为了乱序而乱序，而是为了配合哈希表的"桶分裂"特性，让遍历在迁移过程中也能保持不重不漏。

5.3 rehash期间scan还要双表配合

当dictScan运行时，如果字典正在rehash，它会同时记录ht[0]和ht[1]两张表。遍历时，先按ht[0]的sizemask算出要访问的桶，把桶里的节点交给回调函数；再按ht[1]的sizemask算出对应游标在新表里的桶，同样交给回调。

因为反转序列保证了"旧桶和新分裂桶访问顺序相邻"，所以即使一个元素在两次scan调用之间完成了迁移，它要么在旧表时被访问过，要么赶到新表时正好在轮到的桶里。整个过程中，游标v本身会在两张表之间同步推进。

我第一次展开这个逻辑时，觉得它简直像魔术。但要理解它，并不需要读完整版dictScan代码，只需要把"二进制反转+桶分裂相邻"这个直觉建立起来。真正写并发遍历工具时，你也可以借这个思路：当遍历目标会被中途改写时，选择一种能感知"分裂方向"的游标序列，比事后去重要优雅得多。

6. 从一张哈希表到背后的工程思想

6.1 渐进式迁移不是Redis独有的技巧

把大任务拆成许多小步骤，在操作间隙逐步完成，这个思想远不止出现在Redis的哈希表里。在线数据库做DDL，比如给大表加一个二级索引，通常不是一次性建完，而是先创建索引结构，然后分批扫描存量数据，同时持续同步增量，最后切换。文件系统做碎片整理时，也会把"搬动块"这件事拆成多次执行，避免长时间锁盘。云服务做实例热迁移，同样是一边跑业务一边同步数据，最后短暂切换。

Redis因为单线程，对"任何单一操作都不能占用太久"的要求最为苛刻，所以在哈希表这一层就做了非常细致的拆分。但反过来看，如果你设计的系统本身是多线程的，也不代表可以随便放大单步任务量；长任务带来的不只是CPU占用，还有锁等待、内存抖动、GC压力。渐进式思想的价值是通用的。

如果你认真读过其它语言的标准库，会发现不少语言里的哈希表扩容是"全量搬移"的，搬移期间可能直接阻塞调用线程。Redis能扛住高并发场景，很大程度上不是因为它用了多高深的技术，而是把"扩容"这种看似不可拆分的基础操作，硬生生设计成了带进度指针的可中断任务。

6.2 想亲手验证的话，可以这样玩

纸上谈兵不如跑一遍。我建议你用一个自己熟悉的语言，手写一个模拟dictRehash的小实验：初始容量4，随机塞进一些key，然后扩容到8，每次调用只搬一个桶，并统计每次调用访问了多少个空桶。你很快会发现，如果表比较稀疏，访问空桶的数量会不均匀，这时再按Redis的方式给空桶探测数量设一个上限，延迟曲线会立刻平滑下来。

这个实验不需要多大工程量，几十行代码就够。做的时候建议把"每次rehash步进"和"空桶探测次数"分别打点记录，画出来看，效果比任何文字解释都直观。我第一次模拟完，最大的感触是：旧版那种"跳到下一个非空桶"的做法，在数据密集时表现还好，数据一旦稀疏，确实会出现单次调用的长尾延迟。空桶安全阀不是什么复杂的优化，但它是从真实生产数据里踩出来的经验。

我自己后来写一个本地缓存工具，需要定期清理过期条目的祖先数据，本来也想用一次性大扫除，深思以后还是改成了带进度标记的分批清理。每次请求顺带清理一小段，后台定时器再兜底推进，整体延迟曲线非常平稳。这套模式几乎可以原样照搬到很多"看起来只做一次就好"的场景里。

6.3 这一讲的收工感言

现在再看dict.c里那些while循环，应该能明白，作者并不追求一次把活干完，而是设计了一套每次都能安全停下、下次还能接着往前走的进度系统。rehashidx是进度指针，empty_visits是步数限制，dictScan用二进制反转来适配分裂，每个细节都在回答同一个问题：在不能暂停世界的约束下，怎么优雅地完成一次大地图搬迁。真正值钱的源码细节，往往就藏在这些看似"多此一举"的进度变量和奇怪算法里。