京公网安备11010502063487号节点增减时有多少 key 要重新映射?虚拟节点数怎么影响均匀程度?nginx 的 hash 指令加 consistent 之后真实差多少?这篇用 100000 个 key 的环和 nginx 的 reload 量出来。
算法 | vnodes | 加 1 个节点:归属变了 | 去掉 1 个节点:归属变了 | 10 个节点时的负载不均(最忙 ÷ 平均) -------+--------+--------------+---------------+---------------------- 取模 | - | 90.8% | 89.8% | 1.01 一致性哈希环 | 1 | 12.1% | 21.8% | 2.26 一致性哈希环 | 10 | 7.2% | 13.7% | 1.44 一致性哈希环 | 100 | 8.2% | 10.2% | 1.20 一致性哈希环 | 1000 | 9.4% | 9.9% | 1.05
取模加减一个节点几乎所有 key 都搬;环只搬 1/N;虚拟节点越多越均匀。
指令 | 4 个后端时 A / B / C / D 各收到 | 加 E:归属变了 | 其中搬到了新节点 E 的占比 | 去掉 D:归属变了 | 去掉 D 时原本不在 D 上却被搬走的 key 数 -------------------+--------------------------+----------+----------------+-----------+-------------------------- 普通 hash | 499 / 501 / 501 / 499 | 79.7% | 26% | 74.0% | 980 consistent(ketama) | 477 / 535 / 458 / 530 | 23.8% | 100% | 26.5% | 0 理想值:加第 5 个节点只需搬 1/5 = 20% 的 key(都搬到 E);去掉 D 只需搬原本在 D 上的 key(约 25%),其余 key 不动
普通 hash 加一个后端时 key 在老节点之间乱搬;ketama 只搬向新节点,去掉一个后端时只搬它上面的 key。
按权重分:n0 = 24.5% (理论 25.0%);其余 9 个节点各自: 7.7% / 8.1% / 9.5% / 8.1% / 10.4% / 7.9% / 7.8% / 7.9% / 8.1% 热点 key 落在 n0(权重 3):它的负载占全部流量的 32.0%;按权重本来应该占 25.0%。其余各节点的负载占比: n0=32.0% / n1=6.9% / n2=7.3% / n3=8.7% / n4=7.3% / n5=9.3% / n6=7.1% / n7=7.0% / n8=7.1% / n9=7.3%
权重通过虚拟节点数实现;热点 key 落到哪个节点,哪个节点就多承担一块,一致性哈希不处理热度。