乐趣区

关于图数据库:GraphX-图计算实践之模式匹配抽取特定子图

jiezi

本文首发于 Nebula Graph Community 公众号

前言

Nebula Graph 自身提供了高性能的 OLTP 查问能够较好地实现各种实时的查问场景，同时它也提供了基于 Spark GraphX 的 nebula-algorithm 库以便反对实时的图算法，这里给 Nebula 点个赞，很不错！

但实际过程中，我发现局部 OLAP 场景中，想实现模式匹配剖析，Nebula 的撑持就显得不那么欠缺了。

这里我对模式匹配的解释是：在一张大图中，依据特定的规定抽取出对应的子图。

举一个简略的例子，比方想要对每个点都进行二度扩散，并依照肯定逻辑过滤，最终保留符合要求的二度扩散的子图，这样的工作用 nebula-algorithm 就不太好实现了。

当然，下面这个例子咱们能够通过编写 nGQL 语句——查问出对应的数据，但 Nebula 的劣势在 OLTP 场景，针对特定点进行查问。对于全图数据的计算，无论是计算架构还是内存大小都不是特地适宜的。所以，为了补充该局部（模式匹配）的性能，这里应用 Spark GraphX 来满足 OLAP 的计算需要。

GraphX 介绍

GraphX 是 Spark 生态的一个分布式图计算引擎，提供了许多的图计算接口，不便进行图的各项操作。对于 GraphX 的基础知识我这里不进行过多的介绍了，次要是介绍一下实现模式匹配的思路。

实现模式匹配次要是依赖于一个重要的 API：PregelAPI，它是一种 BSP（BSP：Bulk Synchronous Parallel，即整体同步并行）计算模型，一次计算是由一系列超步实现的。

只看定义不是特地好了解，所以间接介绍它在 GraphX 中的实现，理解它是如何应用的。

Pregel 运行原理

源码定义如下：

  def pregel[A: ClassTag](
      initialMsg: A,
      maxIterations: Int = Int.MaxValue,
      activeDirection: EdgeDirection = EdgeDirection.Either)(vprog: (VertexId, VD, A) => VD,
      sendMsg: EdgeTriplet[VD, ED] => Iterator[(VertexId, A)],
      mergeMsg: (A, A) => A)
    : Graph[VD, ED] = {Pregel(graph, initialMsg, maxIterations, activeDirection)(vprog, sendMsg, mergeMsg)
  }

相干参数含意如下：

  • initialMsg: 节点的初始化信息，调用 vprog 函数解决 initialMsg；
  • maxIrerations：最大迭代次数；
  • activeDiraction：管制 sendMsg 发送的方向，只有满足方向要求的三元组才会进入下一次迭代；
  • vprog：更新节点信息的函数。节点收到音讯后，执行相干逻辑更新节点信息；
  • sendMsg：节点和节点之间发送音讯，参数为一个三元组，并且满足 activeDiraction 的方向条件，把音讯 Msg 发送给 VertexID，VertexID 能够是 src 点也能够是 dst 点；
  • mergeMsg：当同一个 VertexID 接管到多条音讯时，合并多条音讯为一条，便于 vprog 解决。

只看定义和逻辑同样不太分明，所以下边再介绍一下 Pregel 的迭代流程：

  1. 对于一个 graph 对象，只有激活态的点才会参加下一次迭代，激活态的条件是实现了一次发送 / 收到音讯 A 的动作；
  2. 首先初始化所有节点，也就是每个点都调用一次 vprog 办法，参数为 initialMsg，这样使所有节点都在激活态；
  3. 而后是将图划分为若干三元组 Triplet，三元组的组成是：src 点，edge，dst 点，只保留激活点 activeDirection 方向的三元组；
  4. 执行 sendMsg 办法，将音讯 A 发送给一个 VertexID 的点，因为返回值是一个 Iterator，也就是能够同时给 src、dst 发送音讯，若发送 Iterator.empty 则认为没有发送音讯；
  5. 因为一个 VertexID 的点会收到多条音讯，所以调用 mergeMsg 办法合并音讯，合并为一个 A；
  6. 合并之后调用 vprog 更新节点的音讯，这样就实现了一次迭代；
  7. 反复 3-6 的步骤，执行 maxIterations 次迭代或者所有的点都不是激活态则退出，实现 Pregel 的所有计算。

模式匹配的思路

晓得 Pregel 的计算原理之后，那么怎么实现模式匹配呢，次要就是 依据迭代的思维，不停地将边信息聚合到点上，在迭代的过程中管制发送音讯的逻辑来实现特定模式的门路。

咱们能够定义音讯为多条门路的汇合，发送音讯时就是对发送点的门路汇合中，每条门路都减少一个边 e，这样就实现了门路的遍历，其实对于一个点来说，实质就是一个广度优先遍历的过程。

还是以二度查问为例，看如下例子：

首先，对每个点都执行一次初始化，每个点的属性为一个空的门路汇合，门路汇合应用 二维数组 示意，使所有点成为激活态。

而后，进行第一次迭代，能够看到会有两个三元组 A-E1->B，B-E2->C，那么很容易能够失去这次迭代的后果：A：[]，B：[[E1]]，C：[[E2]]

再进行第二次迭代，这里要做限度，曾经发送过的门路不再发送，也就是判断 E 是否已被接管了，避免反复发送的状况。所以第二次迭代的后果就只有 B-E2->C 这个三元组无效，也就是把 B 的汇合中的每条门路别离减少一个 E2，并发给 C，C 将门路合并即可，那么后果就是：A：[]，B：[[E1]]，C：[[E2]，[E1,E2]]。

此时 C 节点上的汇合中就有了 E1，E2 两条边，刚好是 A 节点 2 度遍历的后果。

这里举的是简略例子，只是阐明这样的一个思路，外围逻辑就是传递边来实现门路遍历，实际上每个节点会收到许多点的信息，那么能够将点的后果进行过滤，依照头结点分组即可。实现看如下例子：

在这个例子中依据要求，能失去的后果就是 A 和 G 的 2 度门路子图，迭代的后果我不再赘述，间接列出 C，F 节点的属性：C：[[E2],[E6],[E1,E2],[E5,E6]]，F：[[E4],[E3,E4]]，当然点 H，B，D 也有门路，但其实能够分明的看到想要的后果是在 C，F 节点上的。

那么，后果有了但它是扩散的，怎么合并起来呢？咱们能够将每个点门路的第一个边的起始点拿进去作为 key，因为迭代时每条门路是有序的，其实这个 key 就是指标点，比方 E1，E3 的起始点都是 A，E5 的起始点是 G，咱们将每条门路都减少一个 key，变更为key:path，过滤掉小于 2 条边的门路，再依照 key 分组，就失去了指标点对应的子图门路了，这样是不是就拿到了 A 和 G 各自的 2 度点边了呢！

思路延长

2 度扩散这个例子还是比较简单的，理论业务中，会有很多的状况，当然图的构造也会比较复杂，比方：

  1. 不同标签的点如何遍历
  2. 不同类型的边如何遍历
  3. 呈现环路如何解决
  4. 边的方向是有向还是无向
  5. 多条边如何解决
  6. …

等等的这些问题，然而外围点不变，就是基于 Pregel 实现广度优先遍历，累积边造成门路信息，次要的逻辑根本都在于 sendMsg 这个办法，来管制发或者不发，来决定门路的走向，以满足模式匹配的业务要求。一次迭代就是积攒一层的门路信息，所以迭代次数与图的深度统一。在迭代实现后，每个点上都有一些后果，他们可能是两头后果，也可能是最终后果，个别依照指定 key（个别是头结点）分组再进行一些业务逻辑的过滤（比方门路长度），即可失去指定构造的子图，接下来就能够用于业务的剖析操作了。

此外，还能够借助 GraphFrames 来实现诸如：二度扩散，这种简略的模式匹配。通过应用相似 Spark SQL 的算子，非常容易的失去计算结果，大大减少代码的难度。然而因为文档较少，又不如 GraphX 多种算子的灵便，对于简单的模式还是不太举荐的，感兴趣的能够去理解一下。

总结

利用 GraphX 的 Pregel API 进行广度优先遍从来实现模式匹配的益处：

  1. GraphX 有多种图算子能够灵活处理图数据；
  2. 基于 Pregel，应用门路当做音讯能够灵便管制模式子图的构造，实践上能够实现任何构造的模式提取；
  3. 可能反对较大数据量的全图模式匹配，补救 Nebula 图库 OLAP 的有余；
  4. 无缝集成到大数据生态圈，不便后果的剖析应用。

应用这种形式尽管可能实现模式匹配，然而也有很多毛病，比如说：

  1. 每次迭代的音讯都是门路汇合，越往后音讯会越大，导致 JOIN 的数据量很大，内存占用较高。能够通过优化过滤掉不必要发送的信息来解决；
  2. 迭代的次数无限，太多了则会呈现内存爆炸，不过个别业务中超过 10 层以上的状况也很少；
  3. 因为节点 ID 通常是 String，须要提前做映射表，计算完又要转换回来，导致计算过程中 shuffle 的次数很多。

针对下面问题，如果你有更好的实现计划，或者通过其余计算引擎可能更好的实现，请务必与我交换领导！

最初，尽管 GraphX 应用起来上手有肯定难度，计算也高度依赖内存，但瑕不掩瑜它依然是一款优良的图计算框架，尤其是分布式的个性可能进行大量数据的计算，同时 Spark 又能较好地与大数据生态集成，又有官网提供的 nebula-spark-connector 不便读写 Nebula 数据，应用起来还是十分不错的。

我的分享就到这里了，欢送大家交换更好想法！

我是繁凡，一名大数据开发工程师，目前从事图谱产品开发，致力于大规模图数据在业务中的应用。最近应用 GraphX 实际了一些业务要求的模式匹配开发，在这里分享一些应用的思路。

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

退出移动版