《大规模分布式计算深入解析》4.1 边切分 vs 顶点切分:切哪个更省通信

顶点切分每顶点一主、跨区边产生消息;边切分顶点可复制、通信变本地;取舍账本。

边切分 vs 顶点切分:切哪个更省通信

把图分到多台机器,先决定切什么:切顶点让边跨机器,切边让顶点跨机器。两者换来不同的通信与副本账本。

两种切分

flowchart TD
    A["顶点切分:顶点 0/1 在 P0,顶点 2/3 在 P1"]
    M1["跨区边 0-2、1-2 各发一条消息"]
    B["边切分:边按端点归区,顶点 2 复制两份"]
    M2["顶点 2 副本使遍历本地完成"]
    A --> M1
    B --> M2

顶点切分:跨区边 = 通信

partition 用例 34:顶点切分下跨边数在 0..3 之间(路径图 3 边)。用例 35:跨区边数 = 每超步消息数——跨区边就是消息源,通信账本由切分质量决定。

边切分:副本换本地

用例 36:边切分下顶点 1 至少 1 个副本。用例 37:边切分下中心顶点副本 1..2(2 分区)。副本越多遍历越本地,但要维护副本一致。

对齐卷八:range/hash 分片

卷八 KV 按 key 哈希分片,点查单机完成;图的「key」是顶点,跨区边就是遍历的通信。顶点切分省副本但跨边多,边切分省通信但副本多——没有免费午餐。

验证

从卷十一实验包 解包,运行 Java 账本:partition 用例 34-35 验证顶点切分跨边数 0..3、跨区边数 = 每超步消息数;用例 36-37 验证边切分顶点 1 至少 1 副本、中心顶点副本 1..2。

一手资料

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

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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