《大规模分布式计算深入解析》11.2 GraphX:图关系代数与 RDD 融合

GraphX 把属性图表达为顶点 RDD 与边 RDD 的关系视图,算子映射为 RDD 变换、血缘提供容错;三角形图 PageRank 均匀 1/3。

GraphX:图关系代数与 RDD 融合

GraphX 不造专用存储:属性图是 VertexRDD 与 EdgeRDD 两张 RDD 的关系视图,图算子映射为 RDD 变换,血缘提供与卷二一致的容错。

图表示与关系算子

graph 用例 1-2:无向图 5 顶点 5 边,邻接表槽位 2E = 10;用例 4-5:稀疏图邻接表 80KB 远小于矩阵 1MB。subgraph 按谓词裁剪顶点与边,aggregateMessages 把邻居消息按目标顶点聚合,等价一次 reduceByKey;mapVertices 只改属性不改结构。

图算法账本

PageRank 在 RDD 上每轮 aggregateMessages 分发 rank:三角形图 damping 0.85、20 轮 rank 均匀 1/3(algo 用例 45-46),无悬挂节点总和恒为 1(47)。三角计数(用例 54-55)全图仅 1 个三角形、顶点 0 命中 1 个。每轮中间结果是一次血缘链上的新分片,失败只重算缺失分片。

对齐卷二:RDD 血缘与图的交界

卷二血缘记录变换序列;GraphX 把图算法变成同一机制上的迭代:顶点/边 RDD 的依赖决定重算代价,aggregateMessages 是宽依赖。取舍:通用 RDD 的表达力换专用图引擎每轮预分区、跨轮缓存等优化空间。

验证

从卷十一实验包 解包,graph 用例 1、2、4、5 验证邻接表槽位 2E 与稀疏/稠密空间账本;algo 用例 45-46 验证三角形图 PageRank 均匀 1/3、47 验证总和 1;用例 54-55 验证三角计数全图 1。

一手资料

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

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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