加一台机器,九成的 key 都要搬家

难度 ★★★☆☆ · 前置:三种语言的哈希表,各让了一步 | 一句话结论:取模换了除数就全乱,一致哈希只让新节点切走一段;虚拟节点少的时候搬家比例低,是因为那台新机器几乎没接到活。

产品在群里问,缓存这套服务从四台加到五台要停多久。我说先算个数,回头给答复。关掉窗口我写了个脚本:一百万个 key,形如 user:%020d,从全零数到九十九万九千九百九十九,CRC32 算哈希,四台算一遍落点,五台再算一遍,两边对不上的记一笔。

第一版跑完,799,770 条。

我盯着这个数看了半分钟,先怀疑是自己写错了下标。

想明白花了我一顿饭的工夫。hash % 4 和 hash % 5 同时等于同一个 i 的 key 会留在原来那台机器上,二十个余数组合里正好有四个满足,四台合起来是 4/20,正好两成。所以四台加到五台,取模的搬家比例是 80.0%,不是我原先以为的几乎全部。这个数我在别处也见过,可自己算出来那一次才算记住,因为前二十分钟我一直在翻自己的代码找 bug,查完发现代码没错,是我对除法的直觉错了。我 2023 年 6 月入职,到写这个脚本为止,第一次认真算扩容要搬多少东西。

四台,每份 25.0%,一分不差。

标题里我写的是九成,实测是八成。标题是我先想好的,数是后算的,差的那一成我没去改。

一边八成要搬,一边分得整整齐齐。

这两个事实摆在一起才是那天晚上的重点。均匀说明 CRC32 把一百万个 key 摊得很平,问题不在哈希函数这一层;八成说明毛病长在 % 4 和 % 5 这两个除数上。我原先以为取模的缺陷是散得不够开,跑完才发现它散得很好,坏在别的地方。同一个脚本再往下跑,一致哈希那边给出的数字更难解释,我把表拉到最下面一行,又从头看了一遍,越看越觉得这个结构的好处和它的坏处是同一件事。

取模死在那个 4 上

hash % N 里那个 N 是全局的,没有任何一台机器能给自己圈出一块固定地盘。四台的时候一个 key 去哪由它的哈希值和 4 的余数决定;N 换成 5,除数变了,余数跟着全变,绝大多数 key 的落点当场换掉,跟你搬没搬数据没关系。箱子和球都没动,是规矩变了,而这条规矩覆盖所有球,一个都不放过。你把一百万个球按编号分进四个箱,规则是编号除以四取余;现在要五个箱,重新除一遍,除了极少数编号,其他全都得重新走一趟。

麻烦在于你没法只让一部分 key 挪窝。除数是全局的,它一变所有余数一起变,你连自己会动多少人事先都算不出来——我那天能算出 80.0%,是因为一百万个 key 全在手上,线上没这种好事。所以扩容只能停工全量重算,把每个 key 重新推一遍,推完再按新地址搬数据,搬到一半还得防着有人往老地址写。

八十万条,一条都躲不掉。

节点也扔进同一个哈希

一致哈希换了个思路:既然余数是全局的,那就别用余数。节点先算哈希,node0 到 node3 各自的 CRC32 摆在 0 到 2³²−1 这个圆周上,四个点把圆切成四段。key 也算出哈希落在圆上,顺时针往前走,撞上的第一个节点就是它的家。整个结构只有一张有序数组,没有除法,没有全局的 N,节点和 key 用的是同一个哈希函数、同一根数轴。

1
2
3
4
5
i := sort.Search(len(ring), func(i int) bool { return ring[i].hash >= h })
if i == len(ring) {
i = 0 // 绕回环头
}
return ring[i].owner

加第五台的时候,给 node4 算一个落点插进去。它只从两个老节点中间切走一段:那段弧原先整段归顺时针方向紧挨着它的那个节点,现在前半段让给 node4,后半段还留在原主手里,其余三段一个字不动。N 在这里已经不是除数,而是一个个具体的点,多点少点只影响局部的一段弧,没法像除法那样把整个坐标系掀翻。这段我读源码时看了两遍才确认,因为它太简单,简单到我以为漏了哪一步。

四个节点把环切成长短不一的四段

强在少动,不强在分得匀。

后半句要赔账。

一个节点吃掉 97.9%

最朴素的一遍:每台机器在环上只放一个点。

方案 搬家比例(加一台后) 四台时各节点份额(理想 25%) 倾斜比(最大份额除以最小份额)
直接取模 80.0%(799,770 条) 每个节点正好 25.0% 1.0×
一致哈希,虚拟节点 1 0.30%(3,019 条) 0.7% ~ 97.9% 144.2×
一致哈希,虚拟节点 10 2.77%(27,718 条) 3.4% ~ 49.8% 14.6×
一致哈希,虚拟节点 100 14.85%(148,462 条) 18.7% ~ 34.0% 1.8×
一致哈希,虚拟节点 1000 18.21%(182,140 条) 21.9% ~ 31.3% 1.4×

四段弧,最长的那段吃掉 97.9%。

一个节点扛 97.9%,另外三台加起来 2.1%,这不像集群,像一台机器带着三个看客。倾斜比 144.2 倍,取模那边是 1.0 倍,一致哈希在最朴素的形态下把均匀性输掉了两个数量级。我第一反应是这玩意儿怎么还会有人用,第二反应是回头看同一行里那个 0.30%,两个数挨着放才说得通:九成七的 key 本来就压在同一个节点上,新插进来的 node4 正好落在它背后很窄的一段弧里,只从它那儿切走一小片。

付了一台机器的钱,买到 0.3% 的分流。

搬家 0.30% 是最难看的那个数

整张表里这两个数一路反着走:搬家比例涨上去,倾斜比降下来。虚拟节点 1 是搬迁最省的一档,也是分配最烂的一档。四台加到五台,机器总数从四变五,总容量从四份变五份,新来的那台该吃掉五分之一;要让它承接五分之一的流量,就必然有五分之一的 key 得换地方。20% 是这道题的标准答案,也是物理下限,掉不下去,除非新机器不打算干活。

任何低于 20% 的搬家比例,都说明有台机器在空转。

所以这张表要反过来读。虚拟节点越少,新节点越难切到自己该得的那一份,搬得才少。0.30% 省下的那十七个百分点,全变成新节点上闲置的容量:你多付了一份机器的钱,新那台只接了三千个 key,剩下九十九万七千个还在四台老机器上,压力一点没减。真正要看的是两列配不配,一头 0.30% 配 144.2 倍倾斜,另一头 18.21% 配 1.4 倍,中间三档连续过渡,没有哪一档能同时把两个数压下去。

搬家比例往上走,倾斜比往下走

段越短,切走的越接近五分之一

一个物理节点在环上放 V 个点,四台就是 4V 个点,把环切成 4V 段,每段归顺时针方向前一个点所在的机器。每台的份额是它名下所有段的总长度。V 越大段越多、越短,一段长一段短互相抵消得越彻底,总长度越贴近四分之一,倾斜比越接近 1。V=1 的时候四台只有四个点,四段弧纯粹靠运气,最长那段占九成七;V=1000 的时候四台有四千个点,四千段里最长的那段只比平均值长一点,再长也翻不出几倍。加节点的算术是同一套:node4 放 V 个点,每个点切走它前面那一段,在均匀假设下切下来的总和正好是环的 V/(5V),也就是五分之一。

0.30、2.77、14.85、18.21,就是这么爬上去的。

收敛速度差不多是 1/√V。虚拟节点从 100 加到 1000,离 20% 的差从 5.15 个百分点压到 1.79 个百分点,十倍的点换来三分之一的误差,再往上加十倍也就再省一半。这里最拧巴的一处是两个数同源:倾斜是段长不均,搬家是新点切走一段,段越均匀切走的就越接近五分之一;想把搬家压回去,只能让段重新长短不一,那等于把倾斜请回来。一个管分配,一个管迁移,两个指标被同一根杠杆撬着。

杠杆只有一根。

线上没人真用 1000 个虚拟节点

我把几个常见实现翻了一遍,数都对不上 1000。Nginx 的 hash $request_uri consistent,内部是 ketama 那一套,每个后端默认 160 个点。Redis Cluster 干脆不用环,key 空间切成 16384 个槽,CRC16 取模,扩缩容靠迁移槽。Cassandra 3.x 的 num_tokens 默认 256,4.0 之后降到 16。这三个数都是按内存和运维成本定的,不是按最优定的,把倾斜比从 1.4 挤到 1.1 的那部分收益,得用别的东西来换。

16384 个槽,一个槽记一条归属,整张表 32 KB,随便哪台机器都存得下。160 和 256 是同一个量级,都比 1 多得多、比 1000 少得多。这个数再往上,环上的点翻着涨:一千个虚拟节点配十台机器就是一万个点,每个客户端要维护这张有序表,每次查找还要在里头二分一次;一百六十个点的时候这笔开销看不见,一万个点的时候能测得出来。

键盘上多打一个零,线上多背一张表。

一百五,和那天少搬的五万条

现在我给一套新集群做方案,先算两个数:四台时各节点份额的最大值除以最小值,和加一台时的搬家比例。前者决定要不要加虚拟节点,后者决定加到多少。默认取 100 到 200 之间,倾斜落在 1.4 到 1.8 倍,搬家 15% 到 18%,离 20% 差的那口气就是段还没切匀,不是哪里配错了。

单 key 贵,往上取。

每个 key 背后是一次大对象读、搬迁要预热缓存的场景,倾斜的代价立刻放大,一台机器多扛一点就是它的网卡先满,500 以上不冤。key 有几亿条、搬迁本身要跑几个小时的时候往下取,100 以内,接受 1.8 倍倾斜,用扩容当天的分钟数换平时的均匀度。有一道下限别破:搬家比例掉到 5% 以下,新节点基本没接到活,这台机器加了等于没加,先回头修环。

我那套缓存定了 150,那天搬十五万条,比理论值少五万,少的那五万还在老机器上。

新节点接不走五分之一,你加进去的就不是容量,是一台闲着还照样烧电的机器。