边切分 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。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。