图计算设计空间总结
图系统沿两条轴展开:计算范式(同步超步到异步图并行)与存储形态(原生图到键值之上)。九个 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 分别印证查询执行与算法收敛。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。