本卷围绕一个问题组织 15 章:一份数据的关系如何被遍历、分析与查询。前十卷把数据当作「被计算、被存储、被流转、被检索」的对象,本卷拆开数据之间关系本身的主干——图:图模型与表示、BSP 超步引擎、图切分与分区、PageRank 与图算法、Neo4j 存储文件族与页缓存、Cypher/Gremlin 查询与执行、图事务与锁、因果集群与复制、Giraph/GraphX/TigerGraph/JanusGraph 生态、中心性与社区检测、子图同构与模式物化、RDF 与知识图谱、图向量混合检索,最后收口于图计算设计空间与自研取舍。
全书目录与章节索引 · 卷一 · 卷二 · 卷三 · 卷四 · 卷五 · 卷六 · 卷七 · 卷八 · 卷九 · 卷十 · 卷十一(本卷)
三条阅读路线
路线 A:图内核(按依赖顺序)
从图模型一路读到查询与算法,适合想理解「图的存储与计算为什么长这样」的读者。
- 第 1–2 章 图模型与表示、邻接表/矩阵、免索引邻接与属性图。
- 第 3–4 章 BSP 超步引擎、顶点程序与消息、图切分与分区。
- 第 5 章 图算法:PageRank、连通分量、最短路径与三角计数。
- 第 6 章 Neo4j 存储文件族与页缓存,把表示落到字节账本。
路线 B:图数据库进阶(面向图数据库开发者)
把存储、查询、事务与集群与前八卷的存储/一致性的语言对齐。
- 第 6 章 存储文件族、页缓存、可变长属性记录与写路径。
- 第 7 章 图查询语言:Cypher 模式匹配、Gremlin 与 GQL、查询编译。
- 第 8 章 查询执行与优化:展开、索引加速与代价估算。
- 第 9 章 图事务与并发:细粒度锁、隔离级别与死锁。
- 第 10 章 因果集群:角色、书签、复制与故障转移。
路线 C:选型与生态(面向架构)
从生态与设计空间切入,把内核章节当参考手册。
- 第 11 章 图计算生态:Giraph、GraphX、TigerGraph 与 JanusGraph。
- 第 12 章 中心性、社区检测与图嵌入。
- 第 13 章 子图同构、motif 与模式物化。
- 第 14 章 RDF 知识图谱、图向量混合检索与图数据库选型。
- 第 15 章 图计算设计空间总结与自研取舍。
十一卷主线对照
| 卷 | 核心问题 | 一致性边界 | 本卷关系 |
|---|---|---|---|
| 卷一 计算模型与分布式文件系统 | 计算如何被切分与重放 | 任务级重放 | BSP 超步把计算切成同步轮次 |
| 卷二 批处理引擎:Spark 内核 | 血缘如何驱动重算 | 血缘重算 | GraphX 把图算子融进 RDD 血缘 |
| 卷三 流计算与状态引擎:Flink 内核 | 状态如何被检查点化 | 状态检查点 | 超步状态与消息是图版的检查点 |
| 卷四 调度、数据湖与分布式训练 | 资源与目录如何被事务化 | 目录事务 / 梯度汇聚 | 分布式训练与图分区共享切分语言 |
| 卷五 执行引擎与存储格式内核 | 单机性能由什么决定 | 字节与时间账本 | 邻接表/矩阵与免索引邻接是单机地基 |
| 卷六 分布式 SQL 执行与 MPP 内核 | 算子如何跨节点执行 | 交换字节与调度账本 | 模式匹配执行与 MPP 展开对应 |
| 卷七 分布式一致性、复制与事务内核 | 多副本如何共同持有一份数据 | 日志前缀与多数派交集 | 因果集群与复制的协议层 |
| 卷八 分布式存储与 KV 引擎内核 | 数据到底怎么被持久化与检索 | 追加日志与层间合并 | 存储文件族、页缓存与索引的地基 |
| 卷九 分布式消息与事件流平台内核 | 一条消息如何被可靠写入、复制与读走 | 分区有序与 ISR 高水位 | 图变更事件流的写入上游 |
| 卷十 分布式检索与搜索引擎内核 | 一份数据如何被高效检索、打分与聚合 | 近实时可见与分片单元 | 向量 kNN 与图嵌入的检索侧 |
| 卷十一 图计算与图数据库内核 | 一份数据的关系如何被遍历、分析与查询 | 超步屏障与图事务边界 | 十一卷收口于第 15 章 |
动手复现
下载实验包后按 README 运行。136 条 Java 8 断言覆盖图表示、BSP 超步、消息账本、切分负载、PageRank、存储字节、模式匹配、事务锁、集群多数派与子图同构等算例。Neo4j 5.26.33 原生探针观察免索引邻接遍历、出度计数、shortestPath、NodeIndexSeek 执行计划与事务提交读回。
十五章依赖图
flowchart TD
C1[1 图计算问题域] --> C2[2 图存储模型]
C1 --> C3[3 BSP 超步引擎]
C2 --> C4[4 图切分与分区]
C3 --> C4
C3 --> C5[5 图算法]
C4 --> C5
C2 --> C6[6 图数据库存储引擎]
C1 --> C7[7 图查询语言]
C6 --> C8[8 查询执行与优化]
C7 --> C8
C6 --> C9[9 图事务与并发]
C8 --> C9
C6 --> C10[10 图数据库集群]
C9 --> C10
C3 --> C11[11 图计算生态]
C4 --> C11
C5 --> C12[12 图算法进阶]
C5 --> C13[13 图索引与子图查询]
C8 --> C13
C8 --> C14[14 图生态与混合检索]
C13 --> C14
C12 --> C14
C10 --> C15[15 卷十一收口]
C14 --> C15
C11 --> C15
五组问题追踪
| 问题 | 章节 | 关键结论 |
|---|---|---|
| 为什么图遍历能沿关系直达 | 1、2 | 邻接表 O(E),免索引邻接把遍历成本锁在 O(度数) |
| 图计算怎么跨机器同步 | 3、4 | BSP 超步屏障,边切分/顶点切分决定跨区消息量 |
| 一条关系怎么写进磁盘 | 6 | 节点 25B/关系 34B 记录,页缓存 8GiB 与写日志 0.2ms |
| 图查询怎么又快又对 | 7、8、13 | 模式匹配展开,NodeIndexSeek DB Hits=2,子图同构物化 |
| 图数据库怎么多机一致 | 9、10 | 细粒度节点锁,3 节点多数派 2 容忍 1 台故障 |
逐节索引
| 节 | 标题 | 读完可以核对 |
|---|---|---|
| 1.1 | 1.1 图模型与图数据:顶点、边与属性的世界 | 用顶点度数、边数与属性区分图数据与非图数据。 |
| 1.2 | 1.2 图 vs 关系/键值/向量:三种查询语义的边界 | 沿查询类型与关联深度比较四种存储的适用域。 |
| 1.3 | 1.3 分布式图计算的挑战:切分、通信与收敛 | 从切分、消息与迭代收敛定位分布式图难题。 |
| 2.1 | 2.1 邻接表与邻接矩阵:两种表示的代价账本 | 用 1000² 矩阵 1MB vs 邻接表 80KB 理解稀疏取舍。 |
| 2.2 | 2.2 属性图模型:标签、属性与关系类型 | 沿标签扫描与属性过滤核对属性图语义。 |
| 2.3 | 2.3 免索引邻接:Neo4j 为什么遍历快 | 用关系记录双端 next 链核对邻接遍历成本。 |
| 3.1 | 3.1 BSP 与超步:同步的图并行模型 | 用超步数与消息账本理解同步屏障。 |
| 3.2 | 3.2 顶点程序与消息传递:Pregel 的计算单元 | 沿 compute、sendTo 与 voteToHalt 追踪一轮超步。 |
| 3.3 | 3.3 aggregator、combiner 与收敛判定 | 用 aggregator 求和 6、combiner 取最大值 5.0 理解收敛。 |
| 4.1 | 4.1 边切分 vs 顶点切分:切哪个更省通信 | 用跨区边数与副本数比较两种切分。 |
| 4.2 | 4.2 哈希/范围/启发式切分:分区策略谱系 | 用黄金比例哈希与启发式把顶点归位。 |
| 4.3 | 4.3 负载均衡与再平衡:热点顶点怎么办 | 用负载差 4 与再平衡后差 1 核对均衡口径。 |
| 5.1 | 5.1 BFS/DFS 分布式化:宽度优先的消息波 | 用 BFS 超步数 = 距离 + 1 理解消息波。 |
| 5.2 | 5.2 PageRank:幂等收敛的迭代账本 | 用三角图 rank 均匀 1/3 与悬挂重分布核对守恒。 |
| 5.3 | 5.3 连通分量、最短路径与三角计数 | 用最小 id 归并、SSSP 距离与三角计数 1 复核算法。 |
| 6.1 | 6.1 Neo4j 存储文件族:节点、关系与属性文件 | 用节点 25B/关系 34B 记录账本理解文件族。 |
| 6.2 | 6.2 页缓存与写路径:图存储的 IO 账本 | 用页缓存命中 0.1ms vs 磁盘 8ms、写路径 0.2ms 核对。 |
| 6.3 | 6.3 属性存储与可变长记录:稀疏与稠密的取舍 | 用稀疏 1.6KB vs 稠密 160KB 理解内联/外链。 |
| 7.1 | 7.1 Cypher 模式匹配:声明式图查询 | 用标签扫描 3、组合 3×3=9 理解声明式语义。 |
| 7.2 | 7.2 Gremlin 与 GQL:遍历式与标准化的对照 | 用两跳遍历 2 步与选择率 5% 比较两种语言。 |
| 7.3 | 7.3 查询编译:模式解析与语义检查 | 沿解析、属性到标签、语义检查追踪编译链。 |
| 8.1 | 8.1 模式匹配执行:展开、半连接与切片 | 用 3 候选 × 2 展开 = 6 次访问核对执行成本。 |
| 8.2 | 8.2 索引加速:属性索引与邻接索引 | 用 NodeIndexSeek DB Hits=2 对照全表扫描 6。 |
| 8.3 | 8.3 优化器:代价估算与计划选择 | 用基数 3 × 每步 2 = 6 与 cost 2.0 比较计划。 |
| 9.1 | 9.1 图事务模型:ACID 在图上的落地 | 用提交=写集+释放锁、回滚=丢弃+释放理解 ACID。 |
| 9.2 | 9.2 锁与隔离级别:细粒度锁的账本 | 用节点 5 写锁互斥与另一节点成功核对细粒度。 |
| 9.3 | 9.3 并发更新与死锁:图写冲突怎么办 | 用等待图成环 1→2→3→1 判断死锁。 |
| 10.1 | 10.1 因果一致性集群:角色与书签 | 用写只发 leader、书签读己之写理解角色。 |
| 10.2 | 10.2 复制与故障转移:primary-backup 图版 | 用 3 节点多数派 2、容忍 1 台故障核对复制。 |
| 10.3 | 10.3 读偏好与一致性窗口:集群读的权衡 | 用 follower 滞后 5 条日志理解一致性窗口。 |
| 11.1 | 11.1 Giraph:Pregel 的 Hadoop 落地 | 用超步引擎与消息账本理解 Giraph 与 MR 的衔接。 |
| 11.2 | 11.2 GraphX:图关系代数与 RDD 融合 | 用图表示、PageRank 与三角计数核对血缘驱动的重算。 |
| 11.3 | 11.3 TigerGraph/JanusGraph:分布式图数据库的两种路线 | 用存储文件族与查询执行对照两种架构路线。 |
| 12.1 | 12.1 中心性:度、介数与接近中心性 | 用探针出度 alpha=2/beta=1/gamma=0 核对中心性口径。 |
| 12.2 | 12.2 社区检测:Louvain 与标签传播 | 用连通分量并入最小 id 0 与孤链 id 3 理解标签传播。 |
| 12.3 | 12.3 图嵌入与 GNN:从结构到向量 | 用 PageRank 迭代与子图同构对照图到向量的路径。 |
| 13.1 | 13.1 属性索引:点查的加速器 | 用索引命中 2、快于扫描 100、NodeIndexSeek 核对加速。 |
| 13.2 | 13.2 子图同构与 motif:模式计数的代价 | 用三角 motif 1、星形 k=2 计数 C(3,2)=3 理解代价。 |
| 13.3 | 13.3 图模式索引与聚类:提前物化 | 用物化维护=模式数 5 与有维护成本理解取舍。 |
| 14.1 | 14.1 RDF 与知识图谱:语义网上的图 | 用三元组存储与模式匹配 3×3=9 理解语义网。 |
| 14.2 | 14.2 图与向量混合检索:GNN 与 RAG 的结合 | 用图嵌入与卷十向量 HNSW 对照混合检索。 |
| 14.3 | 14.3 图数据库选型:Neo4j/JanusGraph/TigerGraph/ArangoDB | 用存储、查询、事务与集群四维核对选型。 |
| 15.1 | 15.1 图计算设计空间总结 | 并行评估表示、切分、执行与一致性的设计空间。 |
| 15.2 | 15.2 十一卷主线:从切分到图 | 从文件切分、批流、存储与检索追踪同一条图数据。 |
| 15.3 | 15.3 落地:从 Neo4j 到自研图引擎 | 用最小闭环逐步验证存储、遍历、事务与索引。 |
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。