分布式图计算的挑战:切分、通信与收敛
单机图计算受内存限制,把图摊到多机要过三道关:切分决定谁持有哪个顶点,通信决定跨区边怎么交换,收敛决定迭代何时停。卷六的 exchange 做通用数据交换,图的交换按超步同步结算。
切分:哈希把顶点摊平
最朴素的切分按顶点 id 哈希到分区。lab 用例 31 验证顶点 0 用 Knuth 黄金比例哈希落到分区 0;用例 32 提醒相邻顶点可能被哈希进不同分区,于是它们的边成为跨区边,切分代价从这里开始。用例 33 验证 1000 个顶点分到 3 个分区,计数和恰为 1000,没有丢顶点。
通信:跨区边变成消息
flowchart LR
subgraph P0["分区 0"]
V0["顶点 0"]
end
subgraph P1["分区 1"]
V1["顶点 1"]
end
V0 -- "超步消息" --> V1
V1 -- "超步消息" --> V0
跨区边每超步产出一条消息,本地边不占用网络。切分质量差会让消息数逼近跨区边数,把计算问题变成网络问题——这与卷六 exchange 一次 shuffle 的代价同源。
收敛:同步何时停
Pregel 用超步把「计算—通信—同步」切成离散节奏:每超步顶点消费上一批消息、更新状态、投票停止;全局无活跃顶点即收敛。同步带来可预测性,也让最慢分区拖慢整体。
验证
从卷十一实验包 解包,运行 partition 模块:用例 31 验证顶点 0 哈希到分区 0(Knuth 黄金比例哈希),用例 32 验证相邻顶点可落不同分区,用例 33 验证 1000 顶点 3 分区计数和 = 1000。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。