图计算前世今生(一)

Jin's Blog

2021-06-01 (Updated: 2021-10-15)

图

mr, pregel, 图计算

今天开始了解图计算系统的前世今生, 为后续理解自研的图计算框架, 以及计算存储一体化 /分离化做铺垫

0x00. Preface

首先, 图计算不同于图存储, 相关的 paper 和框架资料要多不少, 个人推测可能有以下几个原因:

计算与 CPU 和内存靠得很近 , 有很多单点可优化的地方
计算更贴近业务系统, 最近几年又与 AI 相关(图神经网络)结合较多
图论 / 图的常见算法侧重计算部分, 存储讲的很少
Google 在 2010 年公开了自己的图计算论文 Pregel

然后基于 Pregel 的思想模型, 以及 MPP 等系列并行计算思想, 就是本文需要介绍的图计算的核心轴, 然后因为这块已经有许多前辈总结的优秀资料或图文, 在粗读核心 paper 之后, 会大量参考已有的资料, 然后大体有下面几个模块:

为什么需要(分布式)图计算框架 (Why)
图计算的定义与起源 (What + When)
核心论文 Pregel 的浅析
图计算的发展与结构/原理 (How)

因为篇幅原因, 后续随着文章的扩展会考虑耽误拆分部分模块, 不过这篇仍然会是开篇 & 汇总篇

0x01. Why need graph computing?

篇幅所限, 就不单独讨论单机下的图计算需要

1. 图计算的需求

2. 传统计算引擎?

3. 对比图数据库

一般大家通俗的说, 认为图数据库适合 OLTP 类查询, 图计算适合 OLAP 类查询, 虽然现在 TP/AP 的说法很模糊, 不过大概意思说是:

图数据库适合高并发, (带事务), 实时的小规模子图查询 (输入小, 输出较少)
图计算适合低并发, (不带事务)的离线全图迭代类计算 (输入大, 输出大)

Feature / Type	图数据库	图计算	备注
存储介质	外存为主 + 内存为辅	内存为主 + 外存为辅	图 DB 逐渐朝内存方向发展
存储方式	行式非压缩存储	列式压缩存储	计算也可采用行存, 但效率不大
点 / 边的增删改查	非常擅长	不擅长 / 不可用	列存无法改删
时效性	强, 在线 (毫秒级)	弱, 离线 (小时级)	时差来自读 + 算的耗时
ACID	可支持 / 不完善	不支持

至于现在商业图或者宣传比较火的 HTAP (混合TP + AP)在一个系统的, 因为暂没成熟的开源方案, 也有一些没有解释清楚的点, 在末尾的展望和趋势处再说

0x02. History of graph computing

先说一下“图计算”的基本概念和定义, 然后列一下与图数据库之间的对比, 这里会大量参考业内图计算比较有代表性的说法,

1. 定义

参考: 华为云定义, 参考费马文档图计算定义, Wiki 百科定义?

BSP(bulk sync parallel) 在图计算系统中是一个常见的概念, 直译是 “块同步并行模型” 比较拗口, 因为它原本是一篇计算模型的 paper , 简单来说它提供了一个新的计算模型 (相对于传统的),

2. xx

3. 图计算的单机与多机之选?

如果按大部分情况下惯性思维考虑, 多机带来的并行计算提升, 在数据量稍大一些的情况下, 不说线性或者远快于单点计算, 至少也不会慢多少, 但是在图计算领域却有很大不同, 有写图算法实现本身不具备并行性, 以至于多机带来的网络等通信开销反而大于计算上的开销, 所以直到现在你仍然可以看到大量图计算相关的 paper, 是基于单机的计算模型来优化改善, 而且效果可能还很显著 (10X 以上提升)

至于图计算的内存/外存之选, 一般由于性能影响, 纯外存性能会低太多, 所以这里暂不提及, 以后有需要再单独分析.

因为关于图数据库本身的介绍, 之前有写单独的文章, 也有不少类似白皮书的

0x03. Pregel

如 pregel 标题 “Pregel: a system for large-scale graph processing” 所说, pregel 是 google 内部一个用于大数据量下的(分布式)图计算系统, 与 google 的分布式三架马车类似, 论文正文仅 10 页, 但包含了系统核心和应用的完整介绍, 虽然图计算的论文看起来不少, 但是总得来说, pregel 至于图计算的地位可能类似于 GFS 之于分布式文件系统, 作为开山祖师, 对学习图计算的同学来说, 应该是最核心的一篇 paper.

pregel 的计算模型本质也是基于最经典的 MapReduce 归并模型改进而来, 这里列一下文中出现的一些核心术语:

Message (消息): 每个顶点都拥有的, 也是消息传输的基本单位 (类似网络中的 packet)
Superstep (超级步): 可理解为一轮迭代, 一个图计算过程可能有多轮迭代 (多个Superstep)

然后里面有一些初听会云里雾里的话, 比如 “Think like a vertex”, 实际不用太在意这种抽象话, 按顶点为消息传递发起点来看就行,

然后随着 pregel 的发表, 业内很快就有了开源的实现, 比如大家熟知的 GraphX (Spark), Giraph (Facebook), 以及许多借鉴了它的思想的框架, 那么既然有了数个基于 pregel 的实现了, 后续大家为啥还是要重新开发新的图计算模型, 或者重写改进呢?

这是由于早些时候基于 pregel 实现的框架大部分有比较重的历史包袱, 也缺少很多论文外的定制优化:

GraphX 作为依赖 spark 的一个框架, 更像是一个插件, 好处是天然和大数据生态连通, 但带来巨大的劣势是 Spark-RDD 带来的巨大内存消耗, 以至于迭代数据量超过50亿, 可能就会吃爆内存.
Giraph 因为推出的更早, 基于 Hadoop 的 MR 为底层实现支撑来设计实现(类似使用 Mapper 封装, 不使用 Reducer), 虽然最早是 Facebook 推出, 但是并没有享受到 RocksDB 或者 Trift 类的亲儿子待遇, 性能和稳定性都不尽人意, 后面被送给 Apache 社区, 现在基本无人维护
类似的还有不同于 pregel 计算模型, 性能相对 GraphX 和 Giraph 好许多的 GraphLab1.x/2.x (PowerGraph), 在被 Apple 收购后数年没有新的音讯
pregel 的设计实现里运用 BSP 同步模型是重要的一环, 但是由于哈希的边切方式, 在部分算法下收敛性会很差 (可能带来很大的网络通信开销)

后续的代表如 GraphLab/PowerGraph, 或是较近的 Gemini, 在 pregel 的设计思想基础上, 采用了点切 + 数据预处理分区 + 各种硬件 Numa/AEP 等优化, 更适合偏社交场景(超级顶点占总点数少, 但占总边数巨大)的场景, 目前图计算领域还没有一个说通用于稀疏和稠密图, 并达到很好的平衡或自适应的实现, 可能是一个未来的趋势, 在离散的图使用边切 + pregel 模式, 在稠密图使用点切 + GAS 的模式.

0x04. Model & Trend

1. 业内

除了早些年传统的 GraphX 类实现, 近些年图计算领域也有了不少的进展, 业内目前已知的几个生产使用的分布式图计算框架:

腾讯的 Plato (开源)
腾讯的 Angle-Graph 模块 (开源)
阿里的 GraphScope (开源, 重点关注)
百度的 Hugegraph-computing (开源)

然后也有数个闭源商业的图计算框架, 例如较早的华为的 GES, 费马科技的 PandaGraph (Gemini的商业版), 以及最近出现的 Ultipa 等, 由于商业闭源类图大多不介绍具体的实现原理, 所以目前这里只引用公开过数篇图存储/图计算重要 paper 的费马科技作为资料引用以保证相对严谨性.

3. HTAP On Graph?

把存储和计算整合与一体, 只用起一套服务, 用户就可以轻易的即可做高效的 TP 类点查, 小范围遍历, 也可以做 AP 类大范围迭代, 并且还可用统一的 DSL— 图查询语言来实现, 听起来似乎很好?

以 TigerGraph 为代表, 其实也离不开几个根本的问题, 第一个是混合两种的时候, 资源一定会互相影响, 因为图计算的读写 IO 都会特别大, 即使做限流和增加机器配置, 也会有缺乏弹性和高可用性的问题, 也许这类服务后续能和 K8s 等弹性调度框架组合是一个趋势

4. GPU On Graph Processing?

随着现在万物皆可 GPU 的炼金时代到来, GPU 用于图计算的加速其实也有了不少相关研究, 不过据之前 Fma 图的同学表示实测来看益+处并不明显(提升 1 倍左右), 但是带来的限制要求和其他方面影响却很明显

所以直至 2021年, 暂时这块还没有达到生产可用的状态, 个人理解可能也是先确定瓶颈点在哪的问题, GPU 能解决的是什么方面的瓶颈, 如果瓶颈在于通信代价, 在于通用型, 或在于自适配性, 它是否是当前大规模图计算的瓶颈呢?

未完待续, 缺乏补paper的时间呀

参考资料: