《大规模分布式计算深入解析》1.3 分布式图计算的挑战:切分、通信与收敛

用哈希切分账本讲透分布式图计算的三重挑战:切分、跨区通信与超步收敛,对齐卷六的 exchange 交换账本。

分布式图计算的挑战:切分、通信与收敛

单机图计算受内存限制,把图摊到多机要过三道关:切分决定谁持有哪个顶点,通信决定跨区边怎么交换,收敛决定迭代何时停。卷六的 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。

一手资料

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

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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