分区策略谱系
图切分的第一步是决定顶点落哪个分区。哈希、范围、启发式代表三种目标:哈希要均衡、范围要局部、启发式要照顾拓扑热点。
哈希切分:黄金比例的均衡
Knuth 黄金比例哈希把顶点 id 映射到分区:h(k) 取 k × 0.618… 的小数部分所在区间。顶点 0 落在分区 0,但相邻顶点经哈希后可散到不同分区。
1000 顶点 3 分区,哈希计数和 = 1000,实测最重与最轻分区负载差 4(断言 ≤ 10)。均衡好,却丢掉邻居局部性,跨区边直接变成超步消息。
范围切分与启发式:局部性与热度
范围切分按 id 连续区间落分区,保留局部性;但幂律度分布会让含高度数顶点的区间过载,出现热点分区。
启发式读度数:高度数顶点 1 单独成区,减少副本与跨区边;低度数顶点 0 留在原分区。代价是先知道全局度数或做采样估计。
验证
从卷十一实验包 解包,用 partition 用例 31 验证顶点 0 经 Knuth 黄金比例哈希落在分区 0;用例 33 验证 1000 顶点 3 分区计数和 = 1000;用例 38 验证哈希负载差实测 4;用例 39、40 验证启发式把高度数顶点分到独立分区、低度数顶点留在原分区。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。