《大规模分布式计算深入解析》4.2 哈希/范围/启发式切分:分区策略谱系

对比哈希、范围与启发式三种切分:黄金比例哈希保证均衡,启发式用度数照顾热点,落点由负载差核算。

分区策略谱系

图切分的第一步是决定顶点落哪个分区。哈希、范围、启发式代表三种目标:哈希要均衡、范围要局部、启发式要照顾拓扑热点。

哈希切分:黄金比例的均衡

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 验证启发式把高度数顶点分到独立分区、低度数顶点留在原分区。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图