《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)

卷十一 15 章 45 节学习路径。从图模型与表示出发,经免索引邻接、BSP 超步引擎、图切分与分区、PageRank 与图算法、Neo4j 存储文件族、图查询语言与执行、图事务、因果集群、图计算生态、中心性与社区、子图同构与模式物化、知识图谱与图向量混合检索,到图计算设计空间与自研取舍,含 Java 8 模型和 Neo4j 5.26.33 原生探针。

本卷围绕一个问题组织 15 章:一份数据的关系如何被遍历、分析与查询。前十卷把数据当作「被计算、被存储、被流转、被检索」的对象,本卷拆开数据之间关系本身的主干——图:图模型与表示、BSP 超步引擎、图切分与分区、PageRank 与图算法、Neo4j 存储文件族与页缓存、Cypher/Gremlin 查询与执行、图事务与锁、因果集群与复制、Giraph/GraphX/TigerGraph/JanusGraph 生态、中心性与社区检测、子图同构与模式物化、RDF 与知识图谱、图向量混合检索,最后收口于图计算设计空间与自研取舍。

全书目录与章节索引 · 卷一 · 卷二 · 卷三 · 卷四 · 卷五 · 卷六 · 卷七 · 卷八 · 卷九 · 卷十 · 卷十一(本卷)

系列导读与实验 · 下载卷十一实验包

三条阅读路线

路线 A:图内核(按依赖顺序)

从图模型一路读到查询与算法,适合想理解「图的存储与计算为什么长这样」的读者。

  1. 第 1–2 章 图模型与表示、邻接表/矩阵、免索引邻接与属性图。
  2. 第 3–4 章 BSP 超步引擎、顶点程序与消息、图切分与分区。
  3. 第 5 章 图算法:PageRank、连通分量、最短路径与三角计数。
  4. 第 6 章 Neo4j 存储文件族与页缓存,把表示落到字节账本。

路线 B:图数据库进阶(面向图数据库开发者)

把存储、查询、事务与集群与前八卷的存储/一致性的语言对齐。

  1. 第 6 章 存储文件族、页缓存、可变长属性记录与写路径。
  2. 第 7 章 图查询语言:Cypher 模式匹配、Gremlin 与 GQL、查询编译。
  3. 第 8 章 查询执行与优化:展开、索引加速与代价估算。
  4. 第 9 章 图事务与并发:细粒度锁、隔离级别与死锁。
  5. 第 10 章 因果集群:角色、书签、复制与故障转移。

路线 C:选型与生态(面向架构)

从生态与设计空间切入,把内核章节当参考手册。

  1. 第 11 章 图计算生态:Giraph、GraphX、TigerGraph 与 JanusGraph。
  2. 第 12 章 中心性、社区检测与图嵌入。
  3. 第 13 章 子图同构、motif 与模式物化。
  4. 第 14 章 RDF 知识图谱、图向量混合检索与图数据库选型。
  5. 第 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、4BSP 超步屏障,边切分/顶点切分决定跨区消息量
一条关系怎么写进磁盘6节点 25B/关系 34B 记录,页缓存 8GiB 与写日志 0.2ms
图查询怎么又快又对7、8、13模式匹配展开,NodeIndexSeek DB Hits=2,子图同构物化
图数据库怎么多机一致9、10细粒度节点锁,3 节点多数派 2 容忍 1 台故障

逐节索引

节标题读完可以核对
1.11.1 图模型与图数据:顶点、边与属性的世界用顶点度数、边数与属性区分图数据与非图数据。
1.21.2 图 vs 关系/键值/向量:三种查询语义的边界沿查询类型与关联深度比较四种存储的适用域。
1.31.3 分布式图计算的挑战:切分、通信与收敛从切分、消息与迭代收敛定位分布式图难题。
2.12.1 邻接表与邻接矩阵:两种表示的代价账本用 1000² 矩阵 1MB vs 邻接表 80KB 理解稀疏取舍。
2.22.2 属性图模型:标签、属性与关系类型沿标签扫描与属性过滤核对属性图语义。
2.32.3 免索引邻接:Neo4j 为什么遍历快用关系记录双端 next 链核对邻接遍历成本。
3.13.1 BSP 与超步:同步的图并行模型用超步数与消息账本理解同步屏障。
3.23.2 顶点程序与消息传递:Pregel 的计算单元沿 compute、sendTo 与 voteToHalt 追踪一轮超步。
3.33.3 aggregator、combiner 与收敛判定用 aggregator 求和 6、combiner 取最大值 5.0 理解收敛。
4.14.1 边切分 vs 顶点切分:切哪个更省通信用跨区边数与副本数比较两种切分。
4.24.2 哈希/范围/启发式切分:分区策略谱系用黄金比例哈希与启发式把顶点归位。
4.34.3 负载均衡与再平衡:热点顶点怎么办用负载差 4 与再平衡后差 1 核对均衡口径。
5.15.1 BFS/DFS 分布式化:宽度优先的消息波用 BFS 超步数 = 距离 + 1 理解消息波。
5.25.2 PageRank:幂等收敛的迭代账本用三角图 rank 均匀 1/3 与悬挂重分布核对守恒。
5.35.3 连通分量、最短路径与三角计数用最小 id 归并、SSSP 距离与三角计数 1 复核算法。
6.16.1 Neo4j 存储文件族:节点、关系与属性文件用节点 25B/关系 34B 记录账本理解文件族。
6.26.2 页缓存与写路径:图存储的 IO 账本用页缓存命中 0.1ms vs 磁盘 8ms、写路径 0.2ms 核对。
6.36.3 属性存储与可变长记录:稀疏与稠密的取舍用稀疏 1.6KB vs 稠密 160KB 理解内联/外链。
7.17.1 Cypher 模式匹配:声明式图查询用标签扫描 3、组合 3×3=9 理解声明式语义。
7.27.2 Gremlin 与 GQL:遍历式与标准化的对照用两跳遍历 2 步与选择率 5% 比较两种语言。
7.37.3 查询编译:模式解析与语义检查沿解析、属性到标签、语义检查追踪编译链。
8.18.1 模式匹配执行:展开、半连接与切片用 3 候选 × 2 展开 = 6 次访问核对执行成本。
8.28.2 索引加速:属性索引与邻接索引用 NodeIndexSeek DB Hits=2 对照全表扫描 6。
8.38.3 优化器:代价估算与计划选择用基数 3 × 每步 2 = 6 与 cost 2.0 比较计划。
9.19.1 图事务模型:ACID 在图上的落地用提交=写集+释放锁、回滚=丢弃+释放理解 ACID。
9.29.2 锁与隔离级别:细粒度锁的账本用节点 5 写锁互斥与另一节点成功核对细粒度。
9.39.3 并发更新与死锁:图写冲突怎么办用等待图成环 1→2→3→1 判断死锁。
10.110.1 因果一致性集群:角色与书签用写只发 leader、书签读己之写理解角色。
10.210.2 复制与故障转移:primary-backup 图版用 3 节点多数派 2、容忍 1 台故障核对复制。
10.310.3 读偏好与一致性窗口:集群读的权衡用 follower 滞后 5 条日志理解一致性窗口。
11.111.1 Giraph:Pregel 的 Hadoop 落地用超步引擎与消息账本理解 Giraph 与 MR 的衔接。
11.211.2 GraphX:图关系代数与 RDD 融合用图表示、PageRank 与三角计数核对血缘驱动的重算。
11.311.3 TigerGraph/JanusGraph:分布式图数据库的两种路线用存储文件族与查询执行对照两种架构路线。
12.112.1 中心性:度、介数与接近中心性用探针出度 alpha=2/beta=1/gamma=0 核对中心性口径。
12.212.2 社区检测:Louvain 与标签传播用连通分量并入最小 id 0 与孤链 id 3 理解标签传播。
12.312.3 图嵌入与 GNN:从结构到向量用 PageRank 迭代与子图同构对照图到向量的路径。
13.113.1 属性索引:点查的加速器用索引命中 2、快于扫描 100、NodeIndexSeek 核对加速。
13.213.2 子图同构与 motif:模式计数的代价用三角 motif 1、星形 k=2 计数 C(3,2)=3 理解代价。
13.313.3 图模式索引与聚类:提前物化用物化维护=模式数 5 与有维护成本理解取舍。
14.114.1 RDF 与知识图谱:语义网上的图用三元组存储与模式匹配 3×3=9 理解语义网。
14.214.2 图与向量混合检索:GNN 与 RAG 的结合用图嵌入与卷十向量 HNSW 对照混合检索。
14.314.3 图数据库选型:Neo4j/JanusGraph/TigerGraph/ArangoDB用存储、查询、事务与集群四维核对选型。
15.115.1 图计算设计空间总结并行评估表示、切分、执行与一致性的设计空间。
15.215.2 十一卷主线:从切分到图从文件切分、批流、存储与检索追踪同一条图数据。
15.315.3 落地:从 Neo4j 到自研图引擎用最小闭环逐步验证存储、遍历、事务与索引。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图
  3. 《大规模分布式计算深入解析》15.1 图计算设计空间总结