编程模型：FLASH

FLASH是一种分布式编程模型，用于编写广泛的图算法，包括聚类、中心性、遍历、匹配、挖掘等。FLASH遵循顶点中心理念，但通过提供灵活的控制流、对任意顶点集的操作以及超越邻域的通信，进一步提升了表达能力。FLASH使得各种复杂的图算法在分布式运行时环境中易于编写。用FLASH表达的算法只需几行代码，就能提供令人满意的性能。

动机

近年来大多数图处理框架仅专注于少数固定点图算法，如广度优先搜索、PageRank、最短路径等。这使得大量图算法的分布式计算在现有框架下面临效率低下、表达能力有限或实现复杂度高的问题。广为人知的以顶点为中心的图算法实现遵循一种常见的迭代式、单阶段、基于值传播（简称ISVP）的模式：算法迭代运行直至收敛，在每次迭代中，所有顶点接收来自邻居的消息以更新自身状态，然后将更新后的状态作为消息发送给邻居进行下一轮迭代。这种高层抽象在一定程度上为用户带来了生产力，但代价是牺牲了表达能力。该抽象虽然专为ISVP类算法设计，却几乎无法应用于大量非此类型的算法。与此同时，现代图场景对更先进、更复杂图算法的需求，给现有图处理框架带来了巨大挑战。

在研究了包括许多非ISVP算法在内的代表性分布式图算法后，我们提炼出三个对分布式环境下高效编程至关重要的需求，即：(1) 灵活的控制流；(2) 顶点子集操作；(3) 超越邻域的通信。然而，现有图计算框架均无法完全满足这些需求。因此，有必要设计一种新的编程模型，该模型需同时满足这三项需求，并支持分布式环境下的编程。

FLASH编程模型

概述

FLASH编程模型基于Ligra，继承了其对灵活控制流和顶点子集操作需求的支持。通过进一步实现超邻域通信能力，FLASH显著提升了编程表达力，可支持多样化图算法的开发。由于Ligra是单机并行库，FLASH将其扩展至分布式环境，为此必须处理通信、同步、数据竞争和任务调度等问题。为此，我们提出了名为FlashWare的中间件，它隐藏了所有分布式实现的底层细节，并能在运行时自动且自适应地应用多种系统优化。

我们已使用FLASH实现了70多种图算法，覆盖40多个不同的常见应用场景。现在，通过FLASH编程接口，我们可以编写更加简洁的代码，这也有助于提升开发效率。评估结果表明，FLASH能够高效表达许多高级算法（代码行数最多减少92%），同时提供令人满意的性能表现。

FLASH API

FLASH是一种专为分布式图处理设计的函数式编程模型。它遵循批量同步并行(BSP)计算范式，每个主要函数构成一个单独的超步。该模型使用VertexSubset类型来表示图G的顶点集合，其中包含该集合中所有顶点的索引集。图的顶点属性仅维护一次，由所有VertexSubset共享。下文将描述基于VertexSubset的FLASH API接口。

  • VSize: 该函数返回一个VertexSubset的大小。

size_t VSize(VertexSubset U);

  • VertexMap: 该接口将映射函数应用于U中通过条件检查函数F的每个顶点。输出顶点的索引构成最终的VertexSubset。特别地，为实现过滤语义可以省略M函数，此时顶点数据保持不变。

VertexSubset VertexMap(VertexSubset U, 
                       F(Vertex v) -> bool,
                       M(Vertex v) -> vertex);

  • 边映射(EdgeMap): 对于图G(V,E)，边映射会对源顶点在U中且目标顶点满足C条件的特定边应用更新逻辑。H表示待更新的边集，通常情况就是E。我们允许用户在运行时动态定义任意所需的边集，甚至包括算法执行过程中生成的虚拟边。边集可以通过定义将源顶点索引映射到目标顶点索引集合的函数来指定。为方便使用，我们还提供了一些预定义操作符，例如反向边或目标顶点位于特定顶点子集(VertexSubset)中的边。这一扩展使通信突破了邻域交换的限制。 当选定边通过条件检查F后，映射函数M将作用于该边。函数M的输出代表目标顶点的临时新值。在拉取模式下，这个新值会立即顺序应用；而在推送模式下，则需要另一个参数R来对特定顶点的所有临时新值进行归约得到最终值。更新后的目标顶点构成边映射的输出集。归约函数R应满足结合律和交换律以确保正确性，若仅需顺序应用M（即始终在拉取模式下运行边映射）则无需此要求。函数C在顶点关联值只需更新一次的算法中很有用。FLASH提供了默认函数CTrue（始终返回真值），因为用户有时并不需要此功能。同理，若不需要，边映射和顶点映射的F函数也可使用CTrue来提供。

VertexSubset EdgeMap(VertexSubset U, 
                     EdgeSet H,
                     F(Vertex s, Vertex d) -> bool,
                     M(Vertex s, Vertex d) -> Vertex,
                     C(Vertex v) -> bool,
                     R(Vertex t, Vertex d) -> Vertex);

FLASH还提供了其他辅助API，方便进行集合操作（包括Union、Minus、Intersect、Add、Contain等）、遍历集合中的所有顶点（Traverse）、获取单个顶点的数据值（GetV）等。

强大的表达能力

除了表达现有的顶点中心算法外，FLASH还提供了表达更高级算法的可能性。它是首个满足编程非ISVP算法三大关键要求的分布式图处理模型。

  • (1) FLASH允许用户通过组合原语来定义任意的控制流，因此它能够自然地支持多阶段算法。在传统的以顶点为中心的模型中，这些算法以一种笨拙的方式得到支持，因为它们只允许提供一个单一的用户自定义函数。

  • (2) VertexSubset结构补充了单个顶点的视角，允许对任意顶点进行更新。可以同时维护多个顶点子集，甚至可以在递归函数中定义它们。如果没有这一特性，框架每次都必须从整个图开始，并且每次都要挑选特定的顶点。

  • (3) FLASH允许用户指定任意想要传递消息的边集，即使这些边在原图中并不存在。因此，可以直观地表达包含超越邻域通信的算法。

实现

架构

FLASH的架构包含几个主要组件，如下图所示。首先是代码生成器，它以高级FLASH API作为输入，生成将在第二个组件FlashWare上运行的执行代码。FlashWare是为FLASH模型设计和优化的中间件，基于GraphScope的基础模块实现。FlashWare利用GraphScope的并行计算和通信能力，在分布式运行时执行代码生成器生成的代码。

The FLASH architecture

FLASH架构。

优化

在FLASH模型的实现中引入了一些优化:

  • (1) 在图处理过程中，活跃集的类型可能是密集或稀疏的，FLASH能够针对不同类型的活跃集分派不同的计算内核：稀疏活跃集采用推送模式，密集活跃集采用拉取模式。这种自动切换方案被证明对现实世界的图数据非常有效。此外，FLASH的双模式处理是可选的：用户可以通过调用EdgeMapDense/EdgeMapSparse（而非EdgeMap）选择仅执行单一模式。

  • (2) FLASH采用独立线程执行消息传递，而其他线程并行执行以顶点为中心的处理，从而实现计算与通信任务的协同调度，带来性能提升。

  • (3) 在某些情况下，顶点可能具有多个属性，但并非所有属性都至关重要。只有当某个属性会被其他顶点访问时，该属性才被视为关键属性，此时对主副本的更新需要广播到其镜像副本。反之，若属性仅用于本地计算，则不属于关键属性。这项优化将单条消息的大小从所有属性的总大小缩减为仅包含关键属性的大小。

  • (4) 另一种消除冗余消息的方式是仅与必要的镜像进行通信。对于常规图应用而言，消息会沿着边进行传递。因此，顶点只需向包含其至少一个邻居的分区进行广播。只有当程序员为EdgeMap定义超出E范围的虚拟边时（这种情况不在常规范围内），FlashWare才会将顶点更新同步到所有分区，此时该优化会被禁用。

内置算法

我们已基于FLASH模型实现了70多种图算法，覆盖40多个常见问题领域，包括聚类、中心性、遍历、匹配、挖掘等。此外，我们还在持续为FLASH添加更多算法，并鼓励用户基于FLASH模型开发自定义算法。GraphScope中内置的FLASH模型算法包括：

  • 中心性: 介数中心性, 卡兹中心性, 特征向量中心性, 调和中心性, 接近中心性

  • 聚类与社区: 聚类系数, 流体社区(两个版本), 图着色, 标签传播(两个版本)

  • 连通性: 双连通分量(两个版本), 桥检测(两个版本), 连通分量(七个版本), 强连通分量(两个版本), 割点检测(两个版本)

  • 核心功能: k-core图分解(两个版本)、k-core搜索、退化排序、洋葱层排序

  • 匹配与覆盖: 最大匹配(三个版本)、最大独立集(两个版本)、最小顶点覆盖(三个版本)、最小支配集(两个版本)、最小边覆盖

  • 图挖掘与子图匹配: 环+三角形计数、无环三角形计数、循环三角形计数、钻石结构计数、入+三角形计数、k-团计数(两个版本)、出+三角形计数、矩形计数、三角形计数、带尾三角形计数、最稠密子图问题的2-近似算法、3-路径计数

  • 排名算法: ArticleRank, 超链接主题搜索, PageRank, 个性化PageRank

  • 标准测量: 直径近似计算(两个版本), 最小生成森林(两个版本), k中心

  • 遍历: 广度优先搜索(四种版本), 随机多源广度优先搜索, 单源最短路径(四种版本)