《大规模分布式计算深入解析》15.1 图计算设计空间总结

九个 lab 区间汇成设计空间:表示、超步、切分、算法、存储、查询、事务、集群与索引。

图计算设计空间总结

图系统沿两条轴展开:计算范式(同步超步到异步图并行)与存储形态(原生图到键值之上)。九个 lab 区间正好对应九个决策维度。

计算范式:超步、切分与消息

bsp 区间验证同步 BSP:超步数 = 距离 + 1,消息数 = 边数,aggregator/combiner 压缩通信,活跃顶点无消息时投票收敛(用例 16-30)。partition 区间验证切分账本:哈希切分统计均衡、边切分与顶点切分的副本与跨区边数、启发式放热点、再平衡收敛负载差(用例 31-42)。

flowchart LR
    A["graph 图表示"] --> B["bsp 超步引擎"]
    B --> C["partition 图切分"]
    C --> D["algo 图算法"]
    D --> E["store 存储引擎"]
    E --> F["query 查询执行"]
    F --> G["txn 事务并发"]
    G --> H["cluster 集群"]
    H --> I["index 图索引"]

存储与查询:原生图记账

store 区间给出文件族字节账本:节点 25 字节、关系 34 字节、页缓存 8GiB 命中 0.1ms 对磁盘 8ms、写路径 0.2ms(用例 58-72)。query 与 index 区间验证执行:模式匹配组合计数、NodeIndexSeek 索引查找、子图同构与 motif 计数的组合爆炸(用例 73-91、113-130)。

系统属性:事务与集群

txn 区间验证 ACID 落地:提交应用写集、细粒度节点锁互斥、等待图成环判死锁(用例 92-101)。cluster 区间验证因果集群:leader 写、书签读己之写、3 节点多数派 2 容忍 1 台故障(用例 102-112)。图表示底座 graph 区间提供邻接表/矩阵的代价对照(用例 1-15)。

设计空间的取舍最终收敛为一个合同:遍历要快(免索引邻接)、写要一致(事务与多数派)、规模要线性(切分与集群)。Pregel 的同步模型换来确定性,原生图存储换来单跳延迟,两者不可兼得时要按工作负载选。

验证

从卷十一实验包 解包,运行 lab.RunAll,TOTAL 136 passed 覆盖九个区间:bsp 用例 16-30、partition 用例 31-42、algo 用例 43-57、store 用例 58-72、query 用例 73-91、txn 用例 92-101、cluster 用例 102-112、index 用例 113-130。原生探针 neo4j-probe.sh 的 NodeIndexSeek DB Hits=2 与手写 PageRank 0.3333 分别印证查询执行与算法收敛。

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

一手资料

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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