关于数据库:图计算-on-nLiveNebula-的图计算实践

本文首发于 Nebula Graph Community 公众号

在 #图计算 on nLive# 直播流动中，来自 Nebula 研发团队的 nebula-plato 维护者郝彤和 nebula-algorithm 维护者 Nicole 别离同大家分享了他她眼中的图计算。

嘉宾们

• 王昌圆：论坛 ID：Nicole，nebula-algorithm 维护者；
• 郝彤：论坛 ID：caton-hpg，nebula-plato 维护者；

先收场的是 nebula-plato 的维护者郝彤。

图计算之 nebula-plato

nebula-plato 的分享次要由图计算零碎概述、Gemini 图计算零碎介绍、Plato 图计算零碎介绍以及 Nebula 如何同 Plato 集成形成。

图计算零碎

图的划分

图计算零碎概述局部，着重解说下图的划分、分片、存储形式等内容。

图本身由顶点和边形成，而图构造自身是个发散性构造没有边界。要对图进行切分，必然是切顶点或者是切边二选一。

切顶点意味着一个顶点切成多份，每个 partition 上会存储局部顶点，这样会引发两个问题：顶点数据的一致性和网络开销的问题。此外，切点也存在一个顶点存储多份带来的数据冗余。

而切边则一条边会切成两份，别离存储在两个 partition 上。在计算（迭代计算）过程中就会存在网络开销。同样，切边也会引发数据冗余带来的存储危机。

图的划分除了有图数据结构本身的切割问题，还有数据存储的分区问题。图数据分区通常有两种形式，一种是 Hash，还有一种是范畴分片。范畴分片指的是数据划分为由片键值确定的间断范畴，比如说 machine 1 有 bannana、car 等 key，machine 2 有 dark 范畴的 key，依照相似规定分片。

图存储的形式

图计算零碎的存储介质分为内存和外存，内存形式会把所有数据放内存中进行迭代计算；而外存存储则要不停地去读写磁盘，这种效率非常低。目前，支流图计算零碎都是基于内存存储，但内存有个毛病，如果内存放不下数据会十分麻烦。

图计算的存储形式次要有：邻接矩阵、邻接表、CSR/CSC，前两者大家比拟相熟，这里简略讲下 CSR/CSC。CSR 是压缩稠密行，存储顶点的出边信息。举个例子：

当初咱们对这个矩阵（上图）进行压缩，只压存储中有数据的内容，剔除矩阵中没有数据的内容，这样会失去最左边的这张图。然而这种状况如何去判断 2 和 5 是哪个顶点的出边呢？这里引入一个字段 offset。

比如说，当初要取顶点 1 的街坊，顶点 1 在 offset 第一个，那它的街坊是什么区段？如上图，红色框所示：1 的 offset 是 0~2，但不包含 2，对应的街坊就是 2 和 5。

取节点 2 的街坊，节点 2 的街坊是范畴是 2~6，这样对应的街坊就是 1、3、4、5，这就是 CSR。同理，CSC 为压缩稠密列，同 CSR 相似，不过是依照列的形式进行压缩，它存的是入边信息。

图计算模式

图计算模式通常有两种，一种是 BSP（Bulk Synchronous Parallel），一种是 GAS（Gather、Apply、Scatter）。BSP 是一个整体同步的计算模式，块外部会进行并行计算，块与块之间会进行同步计算。像常见的图计算框架 Pregel、Giraph 都是采纳的 BSP 编程模式。

再来说下 PowerGraph 它才用了 GAS 编程模型，相比 BSP，GAS 则细分成了 Gather 收集、Apply 利用、Scatter 散发等三个阶段，每次迭代都会通过这三个阶段。在 Gather 阶段先收集 1 度街坊的数据，再在本地进行一次计算（Apply），如果数据有变更将变更的后果 Scatter 散发进来，下面就是 GAS 编程模型的处理过程。

图计算的同步和异步

在图计算零碎中，常会见到两个术语：同步、异步。同步意味着本轮产生的计算结果，在下一轮迭代失效。而本轮产生的计算结果，在本轮中立刻失效则叫做异步。

异步形式的益处在于算法收敛速度特地快，但它有个问题。

因为异步的计算结果是在当轮立刻失效的，所以同节点的不同的执行程序会导致不同的后果。

此外，异步在并行执行的过程中会存在数据不统一的问题。

图计算零碎的编程模式

图计算零碎编程模型通常也分为两种，一种是以顶点为核心的编程模型，另外一种是以边为核心的编程模型。

（图：以顶点为核心的编程模型）

（图：以边为核心的编程模型）

这两种模式以顶点为核心的编程模型比拟常见，以顶点为核心意味着所有的操作对象为顶点，例如上图的 vertex v 便是一个顶点变量 v，而所有诸如 scatter、gather 之类的操作都是针对这个顶点数据进行。

Gemini 图计算零碎

Gemini 图计算零碎是以计算为核心的分布式图计算零碎，这里次要说下它的特点：

• CSR/CSC
• 稠密图 / 浓密图
• push/pull
• master/mirror
• 计算 / 通信 协同工作
• 分区形式：chunk-base，并反对 NUMA 构造

Gemini 中文的含意是“双子座”，在 Gemini 论文中提到的很多技术是成双成对呈现的。不仅在存储构造上 CSR 和 CSC 成双成对呈现，在图划分上也分为了稠密图和浓密图。

稠密图采纳 push 的形式，能够了解为将本人的数据发送进来，更改别人数据；对于浓密图，它采纳 pull 的形式把 1 度街坊数据拉过来，更改本人的数据。

此外，Gemini 把顶点分为 master 和 mirror。在计算和通信方面进行协同工作，以便升高工夫晋升整体效率。最初是分区形式，采纳 chunk-base 分区，并反对 NUMA 构造。

上面来举个例子减速了解：

上图黄色和粉色是 2 个不同的 partition 分区。

• 在稠密图的 push 操作时，master 顶点（上图左图黄色区域的 v 顶点）会通过网络将数据同步给所有的 mirror 顶点（上图左图粉色区域的 v 顶点），mirror 节点执行 push，批改它的一度街坊节点数据。
• 在浓密图的 pull 操作中，mirror 顶点（上图右图黄色区域的 v 节点）会拉取它 一度街坊的数据，再通过网络同步给它的 master 顶点（上图右图粉色区域的 v 节点），批改它本人的数据。

联合上图例子深刻了解下，这是一个浓密图，采纳 CSC 存储形式。这里上图左侧 Example Graph 中的顶点 0 要进行 pull 操作，这时候 0 的 mirror 节点（Node1 和 Node2）会拉取它的 一度街坊数据，而后同步给 master（Node0）更改本人的数据。

上述便是浓密图 0 对应的 pull 操作。

接着来简略介绍下 Plato。

图计算零碎 Plato 介绍

Plato 是腾讯开源的图计算框架，这里着重讲下 Plato 和 Gemini 的不同点。

下面咱们科普过 Gemini 的 pull/push 形式：csr: part_by_dst 实用于 push 模式以及 csc: part_by_src 实用于 pull 模式。相比拟 Gemini，Plato 在它 pull 和 push 形式根底上新增了实用于 pull 模式的 csr: part_by_src 和实用于 push 模式的 csc: part_by_dst。这是 Plato 在分区上同 Gemini 的不同，当然 Plato 还反对 Hash 的分区形式。

在编码方面，Gemini 是反对 int 类型的顶点 ID 并不反对 String ID，但 Plato 反对 String ID 的编码。Plato 通过对 String ID 进行 Hash 解决计算出对应的机器，将 String ID 发送给对应机器进行编码再传回进行编码数据聚合。在一个大的 map 映射之后，每台机器都能拿到一个全局的 String ID 编码。在零碎计算完结的时候须要将后果输入，这时候全局编码就能够在本地将 int ID 转回 String ID。这便是 Plato String ID 编码的原理。

Nebula Graph 与 Plato 的集成

首先 Nebula 优化了 String ID 的编码，下面说到的全局编码映射是十分耗费内存的，尤其是在生产环境上。在 Nebula 这边每台机器只保留局部的 String ID，在后果输入时由对应的机器进行 Decode 再写入磁盘。

此外还反对了 Nebula Graph 的读取和写入，能够通过 scan 接口来读取数据，再通过 nGQL 写回到 Nebula Graph 中。

在算法下面，Nebula Graph 也进行了补充，sssp 单源最短门路、apsp 全对最短门路、jaccard similary 类似度、triangle count 三角计数、clustering coefficent 汇集系数等算法。

咱们的 Plato 实际文章也将会在近期公布，会有更具体的集成介绍。

图计算之 nebula-algorithm

在开始 nebula-algorithm 介绍之前，先贴一个它的开源地址：https://github.com/vesoft-inc/nebula-algorithm。

Nebula 图计算

目前 Nebula 图计算集成了两种不同图计算框架，共有 2 款产品：nebula-algorithm 和 nebula-plato。

nebula-algorithm 是社区版本，同 nebula-plato 的不同之处在于，nebula-algorithm 提供了 API 接口来进行算法调用，最大的劣势在于集成了 [GraphX](https://spark.apache.org/docs/latest/graphx-programming-guide.html)，可无缝对接 Spark 生态。正是因为 nebula-algorithm 基于 GraphX 实现，所以底层的数据结构是 RDD 形象，在计算过程中会有很大的内存耗费，绝对的速度会比较慢。

nebula-plato 下面介绍过，数据外部要进行 ID 编码映射，即使是 int ID，但如果不是从 0 开始递增，都须要进行 ID 编码。nebula-plato 的劣势就是内存耗费是比拟小，所以它跑算法时，在雷同数据和资源状况下，nebula-plato 速度是绝对比拟快的。

上图左侧是是 nebula-algorithm 和 nebula-plato 的架构，二者皆从存储层 Nebula Storage 中拉取数据。GraphX 这边（nebula-algorithm）次要是通过 Spark Connector 来拉取存储数据，写入也是通过 Spark Connector。

nebula-algorithm 应用形式

jar 包提交

nebula-algorithm 目前是提供了两种应用形式，一种是通过间接提交 jar 包，另外一种是通过调用 API 形式。

通过 jar 包的形式整个流程如上图所示：通过配置文件配置数据起源，目前配置文件数据源反对 Nebula Graph、HDFS 上 CSV 文件以及本地文件。数据读取后被结构成一个 GraphX 的图，该图再调用 nebula-algorithm 的算法库。算法执行实现后会失去一个算法后果的 data frame（DF），其实是一张二维表，基于这张二维表，Spark Connector 再写入数据。这里的写入能够把后果写回到图数据库，也能够写入到 HDFS 上。

API 调用

更举荐大家通过 API 调用的形式。像下面通过 jar 包模式在前面的数据写入局部是不解决数据的。而采纳 API 调用形式，在数据写入局部可进行数据预处理，或是对算法后果进行统计分析。
API 调用的流程如上图所示，次要分为 4 步：

1. 自定义数据源 df（id 为数值型数据）
2. 定义算法配置 louvainConfig
3. 执行算法
4. 对算法后果统计计算或间接展现

上图的代码局部则为具体的调用示例。先定义个 Spark 入口：SparkSession，再通过 Spark 读取数据源 df，这种模式丰盛了数据源，它不局限于读取 HDFS 上的 CSV，也反对读取 HBase 或者 Hive 数据。上述示例实用于顶点 ID 为数值类型的图数据，String 类型的 ID 在前面介绍。

回到数据读取之后的操作，数据读取之后将进行算法配置。上图示例调用 Louvain 算法，须要配置下 LouvainConfig 参数信息，即 Louvain 算法所需的参数，比方迭代次数、阈值等等。

算法执行完之后你能够自定义下一步操作后果统计分析或者是后果展现，下面示例为间接展现后果 louvain.show()。

ID Mapping 映射原理与实现

再来介绍下 ID 映射，String ID 的解决。

相熟 GraphX 的小伙伴可能晓得它是不反对 String ID 的，当咱们的数据源 ID 是个 String 该如何解决呢？

同社区用户 GitHub issue 和论坛的日常交换中，许多用户都提到了这个问题。这里给出一个代码示例：https://github.com/vesoft-inc/nebula-algorithm/blob/master/example/src/main/scala/com/vesoft/nebula/algorithm/PageRankExample.scala

从下面的流程图上，咱们能够看到其实同之前调用流程雷同，只是多两步：ID Mapping 和 对结算后果做 ID & 后果的反 Mapping。因为算法运行后果是数值型，所以须要做一步反 Mapping 操作使得后果转化为 String 类型。

上图为 ID 映射（Mapping）的过程，在算法调用的数据源（方框 1）显示该数据为边数据，且为 String 类型（a、b、c、d），当中的 1.0、2.0 等等列数据为边权重。在第 2 步中将会从边数据中提取点数据，这里咱们提取到了 a、b、c、d，提取到点数据之后通过 ID 映射生成 long 类型的数值 ID（上图蓝色框）。有了数值类型的 ID 之后，咱们将映射之后的 ID 数据（蓝色框）和原始的边数据（方框 1）进行 Join 操作，失去一个编码之后的边数据（方框 4）。编码之后的数据集可用来做算法输出，算法执行之后失去数据后果（黄色框），咱们能够看到这个后果是一个相似二维表的构造。

为了不便了解，咱们假如当初这个是 PageRank 的算法执行过程，那咱们失去的后果数据（黄色框）右列（2.2、2.4、3.1、1.4）则为计算出来的 PR 值。但这里的后果数据并非是最终后果，别忘了咱们的原始数据是 String 类型的点数据，所以咱们要再做下流程上的第 5 步：对结算后果做 ID & 后果的反 Mapping，这样咱们能够失去最终的执行后果（绿色框）。

要留神的是，上图是以 PageRank 为例，因为 PageRank 的算法执行后果（黄框右列数据）为 double 类型数值，所以不须要做 ID 反映射，然而如果下面的流程执行的算法为连通重量或是标签流传，它的算法执行后果第二列数据是须要做 ID 反映射的。

节选下 PageRank 的代码中的实现

def pagerankWithIdMaping(spark: SparkSession, df: DataFrame): Unit = {val encodedDF      = convertStringId2LongId(df)
    val pageRankConfig = PRConfig(3, 0.85)
    val pr             = PageRankAlgo.apply(spark, encodedDF, pageRankConfig, false)
    val decodedPr      = reconvertLongId2StringId(spark, pr)
    decodedPr.show()}

咱们能够看到算法调用之前通过执行 val encodedDF = convertStringId2LongId(df) 来进行 String ID 到 Long 类型的映射，语句执行完之后，咱们才会调用算法，算法执行之后再来进行反映射 val decodedPr = reconvertLongId2StringId(spark, pr)。

在直播视频（B 站：https://www.bilibili.com/video/BV1rR4y1T73V）中，讲述了 PageRank 示例代码实现，有趣味的小伙伴能够看下视频 24‘31 ~ 25’24 的代码解说，当中也讲述了编码映射的实现。

nebula-algorithm 反对的算法

上图展现的是咱们在 v3.0 版本中将会反对的图算法，当然当中局部的图算法在 v2.0 也是反对的，不过这里不做赘述具体的能够查看 GitHub 的文档：https://github.com/vesoft-inc/nebula-algorithm。

依照分类，咱们将现反对的算法分为了社区类、节点重要性、关联性、图构造类、门路类和图示意等 6 大类。尽管这里只是列举了 nebula-algorithm 的算法分类，然而企业版的 nebula-plato 的算法分类也是相似的，只不过各个大类中的外部算法会更丰盛点。依据目前社区用户的发问反馈来讲，算法使用方便次要以上图的社区类和节点重要性两类为主，能够看到咱们也是针对性的更加丰盛这 2 大类的算法。如果你在 nebula-algorithm 应用过程中，开发了新的算法实现，记得来 GitHub 给 nebula-algorithm 提个 pr 丰盛它的算法库。

下图是社区发现比拟常见的 Louvain、标签流传算法的一个简略介绍：

因为之前写过相干的算法介绍，这里不做赘述，能够浏览《GraphX 在图数据库 Nebula Graph 的图计算实际》。

这里简略介绍下连通重量算法

连通重量个别指的是弱连通重量，算法针对无向图，它的计算流程绝对简略。如上图右侧所示，以虚线划分的 5 个小社区，在计算连通重量过程中，每个社区之间的连线（红色框）是不做计算的。你可了解为从图数据库中抽取出 1 个子图来进行 1 个联通重量的计算，计算出来有 5 个小连通重量。这时候基于全图去数据分析，不同的小社区之间又减少了连贯边（红色框），将它们连接起来。

社区算法的利用场景

银行畛域

再来看个具体的利用场景，在银行中存在这种状况，一个身份证号对应多个手机号、多台手机设施、多张借记卡、多张信用卡，还有多个 APP。而这些银行数据会扩散存储，要做关联剖析时，能够先通过联通重量来去计算小社区。举个例子：把同一个人所领有的不同的设施、手机号等数据信息归到同一连通重量，把它们作为一个持卡人实体，再进行下一步计算。简略来说，将扩散数据通过算法聚合成大节点对立剖析。

安防畛域

上图是 Louvain 算法在安防畛域的利用，能够看到其实整个业务解决流程中，算法自身的比重占比并不高，整个解决流程 80% 左右是在对数据做预处理和后续后果进行统计分析 。不同畛域有不同的数据，畛域源数据按业务场景进行理论的图建模。
以公安为例，通过公安数据进行人、车、网吧、酒店等实体抽取，即图数据库中能够分成这 4 个 tag（人、车、网吧、酒店），基于用户的动静数据抽象出领有关系、同行关系、同住关系，即对应到图数据库中的 Edge Type。实现数据建模之后，再进行算法建模，依据业务场景抉择抽取全图，还是抽取子图进行图计算。数据抽取后，须要进行数据预处理。数据预处理包含很多操作，比方将数据拆分成两类，一类进行模型训练，另外一类进行模型验证；或是对数据进行权重、特色方面的数值类转换，这些都称为数据的一个预处理。

数据预处理完之后，执行诸如 Louvain、节点重要水平之类的算法。计算实现后，通常会将基于点数据失去的新特色回溯到图数据库中，即图计算实现后，图数据库的 Tag 会新增一类属性，这个新属性就是 Tag 的新特色。计算结果写回到图数据库后，可将图数据库的数据读取到 Studio 画布进行可视化剖析。这里须要领域专家针对具体业务需要进行可视化剖析，或者数据实现计算后进入到 GCN 进行模型训练，最终失去黑名单。
以上为本次图计算的概述局部，上面为来自社区的一些相干发问。

社区发问

这里摘录了局部的社区用户发问，所有问题的发问能够观看直播视频 33‘05 开始的问题回复局部。

算法外部原理

dengchang：想理解下图计算各类成熟算法的外部原理，如果有结合实际场景跟数据的解说那就更好了。

Nicole：赵老师能够看下之前的文章，比方：

• 《GraphX 在图数据库 Nebula Graph 的图计算实际》
• 《基于 Nebula Graph 的 Betweenness Centrality 算法》

一些绝对比较复杂的算法，在直播中不便开展解说，后续会公布文章来具体介绍。

图计算的布局

en,coder：目前我看到 Nebula Algorithm 计算要将数据库数据导出到 Spark，计算完再导入到数据库。后续是否思考反对不导出，至多轻量级算法的计算，后果展现在 Studio。

Nicole：先回复后面的问题，其实用 nebula-algorithm 计算完不肯定要将后果导入到图数据库，目前 nebula-algorithm 的 API 调用和 jar 包提交两种形式均容许把后果写入到 HDFS。是否要将后果数据导入图数据库取决于你后续要针对图计算结果进行何种解决。至于“后续是否反对不导出，至多轻量级的计算”，我的了解轻量级的算法计算是不是先把数据从图数据库中查出来，在画布展现，再针对画布中所展现进去的一小部分数据进行轻量级计算，计算结果立马去通过 Studio 展现在画布中，而不是在写回到图数据库。如果是这样的话，其实后续 Nebula 有思考去做个图计算平台，联合了 AP 和 TP，针对画布中的数据，也能够思考进行简略的轻量级计算，计算结果是否要写回到图数据库由用户去配置。回到需要自身，是否进行画布数据的轻量级计算还是取决于你的具体场景，是否须要进行这种操作。

潮与虎：nebula-algorithm 打算反对 Flink 吗？

Nicole：这里可能指的是 Flink 的 Gelly 做图计算，目前临时没有相干的打算。

繁凡：有打算做基于 nGQL 的模式匹配吗？全图的 OLAP 计算工作，理论场景有一些模式匹配的工作，个别本人开发代码，然而效率太低。

郝彤：模式匹配是个 OLTP 场景，TP 受限于磁盘的速度较慢，所以想用在 OLAP 上，然而 OLAP 通常是解决传统算法，不反对模式匹配。其实后续 AP 和 TP 交融之后，图数据放在内存中，速度会晋升。

图计算的最佳实际案例

戚名钰：利用图计算能力做设施危险画像的问题，业界有哪些最佳实际？比方在群控辨认、黑产团伙开掘下面，有没有相干业界的最佳实际分享？

Nicole：具体业务问题须要依附经营同学同社区用户约稿，从理论案例中解说图计算更有价值。

图计算内存资源配置

刘翊：如何评估图计算所需的内存总量。

郝彤：因为不同的图计算零碎设计不同，内存使用量也就不一样。即使是同一个图计算零碎，不同的算法对于内存的需要也存在些差别，能够先通过 2、3 种不同数据进行测试，以便评估出最佳的资源配置。

以上为图计算 on nLive 的分享，你能够通过观看 B 站视频：https://www.bilibili.com/video/BV1rR4y1T73V 查看残缺的分享过程。如果你在应用 nebula-algorithm 和 nebula-plato 过程中遇到任何应用问题，欢送来论坛同咱们交换，论坛传送门：https://discuss.nebula-graph.com.cn/。

交换图数据库技术？退出 Nebula 交换群请先填写下你的 Nebula 名片，Nebula 小助手会拉你进群~~