3.2.1 查询模式

我们先来看看图计算中有哪些基础的查询模式。从不同角度来看有不同的分类方式，这里给出3种。

（1）离散查询与关联查询

最典型的离散查询是面向元数据的查询，在图计算、图数据库的语境下，元数据（Metadata）指顶点或边，因为这两者是最小颗粒度的图数据，通常用唯一的ID来标识它们，不需要再细分。所有仅面向顶点或边的操作，都是典型的离散类型操作。

有的读者对于边是否算作元数据表示困惑，认为边并非独立存在，因为它关联了顶点而看起来像是一个复合数据结构。需要指出的是，元数据的定义一方面是最小颗粒度、不可再分，另一方面是有唯一匹配的ID来定位它。而在图数据集中，只有顶点和边符合这两点。但必须承认的是，边的表达的确更为复杂，因为边除了ID外，还会关联起点与终点、方向以及其他属性。有一些图计算系统中会对边进行切割，也就是说一条边的两个顶点可能会被切分存储在不同的分片中，这种切边设计的分布式系统在进行关联查询与计算时，效率可能会比集中式系统低得多（至少降低10倍以上，后面的章节再展开论述）。

关联查询是图数据库相比于其他数据库而言最有特色的图计算操作。例如，路径查询、 k 邻查询、子图查询、组网查询、各类图算法等都属于典型的关联查询。关联查询通常是从某个顶点（或多个顶点）出发，沿边遍历多层点、边，并通过对点、边以及它们各自的属性进行剪枝过滤，直至返回满足条件的点、边数据集。从关系型数据库的视角来看，这种关联查询类似于表连接的操作，然而，图计算所能带来的灵活性与高性能是关系型数据库所无法比拟的。

（2）局部查询与全局查询

这种分类方式指的是当前查询的初始条件和查询过程与结果涉及图数据集的局部还是全局。以图上的度计算为例，可以面向任意单个顶点进行出、入度计算，也可以对全部顶点进行计算—对于后者而言，全部顶点的度计算的复杂度是单个顶点的复杂度的 N 倍，即如果单一顶点的度计算的（平均）复杂度为 O （ E / N ），其中 E 表示全部边的数量， N 表示全部顶点的数量，那么全局度计算的复杂度则可表示为 O （ N / E / N ）= O （ E ）。而另一种算法（全图 k 邻）的计算复杂度则高得多，因为计算每个顶点的 k 邻的算法复杂度为 O （（ E / N ） ^k ），而全部顶点的 k 邻的计算复杂度为 O （ N （ E / N ） ^k ）。例如，在一个典型的电商数据集中，有500万个顶点，1亿条边，计算单个顶点的 k 邻（3度邻居）的平均复杂度为 O （20 ³ ）=O（8000），而全图 k 邻的复杂度为 O （5000000×8000）= O （40000000000），这样的计算复杂度对于市面上大多数的图计算系统而言，意味着根本无法在合理的时间（比如10个小时）内完成计算。而这种全局型计算算法是检验一个图系统算力的一个非常有力的工具。当然，运行全图 k 邻算法前，建议循序渐进，先估算好算法复杂度，从 k =1开始，拾阶而上。像上面的电商数据集，如果一上来就是 k =5，恐怕目前世界上没有任何一个图系统可以承载这种计算量（达16万亿次计算），至少在量子计算能力普及之前没有。

上面这个全图 k 邻的例子对于分布式计算架构是非常不友好的，因为该类图算法既要求查询的广度又要求下钻的深度，而分布式系统只适合浅层计算（Shallow Computing）。假设上面的数据集只有约1GB的原始数据，现有两套硬件规格供选择，1台有16核、200GB内存的服务器与8台每台2核、25GB内存的服务器，哪种计算架构计算全图 k 邻更高效呢？前者一定是某种集中式架构，而后者如果采用某种切点又（或）切边的分布式，可以想见几乎没有可能完成 k ≥2的操作，或者说它的效率可能不及前者的百分之一。如果考虑并发计算的效率，16核的并发能力也要比8×2核高很多，这应该是所有写过高并发程序的工程师的共识—事实上，即便是在第二种架构中让每个服务器实例都存储全量的数据，在需要多层递归式下钻时，2核最大并发的约束性也是显而易见的，如果再加上多实例间不断进行的网络同步或I/O，延迟将是巨大的、指数级的。换言之，第一种架构如果需要1h完成计算，第二种架构（无论数据是否切片）则需要至少10h（不切片，全量存储8份）甚至100h以上（切片、水平分布式）。

表3-1中列出了12套不同图系统性能的比较。其中有7套开源、分布式图计算架构，3套商业化图数据库系统，以及2套采用C/C++实现的高性能单线程计算程序。由表3-1中的对比可知，几乎所有的（水平）开源分布式系统的图算法运算耗时都显著长于单线程程序的运行时间。另外，商业化系统通过多线程、多核的并发实现可以在效率上显著超越单线程（效率提升50%～800%甚至更多），但前提是不要贸然使用水平分布式架构，否则效率会回落到开源分布式图计算架构的水平。

需要指出的是，PageRank与LPA两个图算法是相对比较容易实现并发计算的反复迭代类算法，同时也较容易实现水平分布式存储与计算。然而，图计算的复杂之处在于，分布式存储容易实现，但是计算的逻辑如果不经过缜密的设计，效率会大打折扣（相对于集中式而言），而这种效率的下降是惊人的。例如表3-1中Spark系统，其128线程的PageRank计算与单线程内存相比，并没有表现出128倍的效率提升，而是比期望降低了近400倍（期望能用275/128≈2s完成查询，实际则用了857s）。当单线程程序进行排序优化（类比于分布式系统的点、边排序优化存储或计算逻辑）后，这种效率差会加大至1000倍以上！事实上，在进行分布式图计算的时候，更多的CPU核数、线程数并没有提供更高的算力，而是在空转并等待网络数据交换或磁盘I/O访问，这也是分布式系统在进行图计算时面临的最大挑战。

与效率相关的另一个无可规避的问题是编程语言的效率问题，越接近底层硬件的编程语言的效率越高，例如C比C++高出15%，C++是Java或Scala的5～7倍，Java又是Python的10倍以上，以此类推。

（3）广度优先与深度优先

广度优先遍历最典型的是 k 邻和最短路径查询。以 k 邻（ k -Hop Neighobr）为例，它的原始定义是，从某个顶点出发，查找和该顶点最短路径距离为 k 跳（步、层）的所有不重复的顶点集合。 k 邻计算的逻辑是，如果想知道某个顶点的第 k 层的全部邻居，需要先知道它的全部 k -1层邻居，以此类推。换个角度描述：从该顶点出发，先要找到它的第一层的全部邻居，再到第二层，直到找到所有的第 k 层邻居为止。

k 邻操作在数据量巨大且高度连通的数据集上的计算复杂度可能非常大，因为从任何一个节点出发，只要 k 值够大，就可以连通到所有节点上。在金融场景中，以信用卡交易数据的图计算为例，所有的信用卡和它们的交易对手POS机之间形成的交易网络几乎是完全连通的（这个假设的前提是，每一张卡只要消费，就会至少和某个POS机关联，而这个POS机还会与其他卡交易，其他卡还会与更多的POS机关联，这样的网络是高度连通的，甚至是不存在孤点的。在实际的图算法运算中，孤点可能会被直接剔除，因为它们对于关联查询是没有意义的），如图3-3所示。

图3-4演示了两种不同类型的 k 邻操作：

❑ 仅返回第 k 跳邻居。

❑ 返回从第1跳到第 k 跳的全部邻居。

其中，第 k 跳邻居指的是到原点的最短路径长度为 k 的所有邻居的数量。以上两种操作的区别仅仅在于到底返回的只是当前步幅（第 k 跳、第 k 层）的邻居，还是也包含前面所有层的邻居。

例如，当 k 为一个确定值3时，仅返回第3层邻居，但当 k 为一个范围值[1,3]时，将返回第1、2、3层邻居。后者的返回值显然大于前者，因为它还额外包含了 k =1和 k =2时的邻居的数量。当然如果第2、3层邻居数量为0的话，也有可能是两者相等。

如果把 k =[1,2]和 k =3的 k 邻的返回数值相加，总和应等于 k =[1,3]的 k 邻值（12843+1246=14089）。这也是通过 k 邻计算来验证一个图数据库或图计算系统准确性的一种典型手段。笔者注意到，由图计算的复杂性而造成的系统性的图计算准确性问题是普遍存在的，例如在图计算结果中，如果第 k -1层或其他更浅层的顶点重复出现在第 k 层，或者第 k 层中多次出现同一个顶点，这些都属于典型的图算法实现时的Bug。

典型的图算法实现中的错误有至少如下几种情形。

❑ 遍历模式使用错误：该采用广度优先算法的时候采用深度优先算法，例如 k 邻遍历。

❑ 没有去重：同层（深度）没有去重、多层间未去重。

❑ 没有完全遍历：以广度优先算法为例，没有完成当前层的遍历，就不应该展开下一层。

❑ 并发实现逻辑等造成的其他可能的数据同步、去重等问题。

图3-5所示的是典型的广度优先算法与深度优先算法在遍历一张有向图时经过节点的顺序的差异。

深度优先算法常见于环路查询、有权重的路径遍历，或按照某种特定的过滤规则在图中从某个顶点出发寻找到另外一个或多个顶点之间的连通路径。例如，在银行的交易网络数据中，寻找两个账户之间单一方向的、按时序降序或升序排列的全部转账路径。

理论上，广度优先算法和深度优先算法都可以完成同样的查询需求，区别在于算法的综合复杂度与效率以及对计算资源的消耗。另外，几乎所有的图上遍历算法一开始都是典型的单线程遍历逻辑，在多线程、多实例并发遍历的情况下，具体每个顶点被（多次）遍历时的处理逻辑会更为复杂，而这种复杂度的降维处理一方面受制于数据结构，另一方面直接影响最终的算法计算效率。 3jlmbGu7xCfTnCo9P0FYGDNNGI7vlRC06KyPAiqX4UzydGHXrCcZFQTUTO/KP4HZ