核心概念¶

本文档介绍了GraphScope分析引擎中的一些重要概念，包括图加载策略、内部/外部顶点以及消息传递与同步策略。

加载策略¶

在GraphScope分析引擎中，有三种方式可以维护跨越不同分片的节点。

仅输出¶

每个分片$F_{i}$维护其"本地"节点v，以及一组其他分片中节点v'的"镜像"节点（这些节点与v存在边(v, v')）。例如，在使用OnlyOut策略时，图G中的分片$F_{1}$除了本地节点{4, 5, 6, 7}外，还会存储一个"镜像"节点3以及边(5, 3)，如下图所示。

仅限¶

在这种情况下，每个分片$F_{i}$维护其"本地"节点v以及一组来自其他分片的节点v'的"镜像"节点，这些镜像节点满足存在边(v', v)。在图G中，$F_{1}$除了其本地节点外，还维护着镜像节点{1, 9, 12}。

BothInOut¶

每个片段$F_{i}$维护"本地"节点v以及一组其他片段中节点v'的"镜像"节点，这些镜像节点满足存在边(v, v')或(v', v)。因此，在应用BothInOut策略时，图G中的"镜像"节点{1, 3, 9, 12}会被存储在$F_{1}$中。

分区策略¶

边切割¶

一种边切割分区方式将图的顶点分割成大小大致相等的集群。边会被存储在其一个或两个端点所在的同一集群中。端点分布在多个不同集群之间的边被称为交叉边。

顶点切割¶

一种顶点切割分区方式将图的边划分为大小基本相等的片段。边所连接的顶点也会与该边本身放置在同一个片段中。当一个顶点的相邻边被分配到不同片段时，该顶点需要进行复制。

GraphScope分析引擎上的顶点¶

节点v被称为

外部顶点¶

片段$F_{i}$的OuterVertex（外部顶点）是指位于另一个片段$F_{j}$中的顶点，且在$F_{i}$中存在节点v'使得(v, v')或(v', v)构成一条边；例如，在图G中，节点{1, 3, 9, 12}就是片段$F_{1}$的OuterVertex。

内部顶点¶

如果分配到片段$F_{i}$中，则称为该片段的InnerVertex；例如在图G中，节点{4, 5, 6, 7}就是片段$F_{1}$的InnerVertex。

带出边的内部顶点¶

片段$F_{i}$的InnerVertexWithOutgoingEdge（内部顶点带出边），如果该顶点存储在$F_{i}$中且存在一条邻接边(v, v')指向另一个片段$F_{j}$中的节点v'；例如，在图G中，节点5是$F_{1}$的InnerVertexWithOutgoingEdge，其出边为(5, 3)；

带传入边的内部顶点¶

如果片段$F_{i}$中的InnerVertexWithIncomingEdge被维护在$F_{i}$中，则它具有来自另一个片段$F_{j}$中节点v'的入边(v', v)；例如，在G中，节点{4, 5, 7}是$F_{1}$的InnerVertexWithIncomingEdge，而(1,4)、(9,5)和(12,7)是对应的入边。

消息管理器与消息策略¶

在GAE的每个图应用中，都会创建一个MessageManager来管理不同分片之间传递的消息。考虑到图应用的多样性，我们提供了多种消息传递策略，这些策略定义在MessageStrategy中。

以下是GAE支持的消息传递和同步策略。

沿出边到达外部顶点¶

这里消息沿着从InnerVertexWithOutgoingEdge到OuterVertex的交叉边传递。例如，在图G中消息从节点5传递到节点3。

沿入边到达外部顶点¶

在这种情况下，消息会沿着从InnerVertexWithIncomingEdge到OuterVertex的交叉边传递。例如，在图G中，消息从节点5传递到节点9。

沿边到外部顶点¶

每条消息都沿着从既是InnerVertexWithIncomingEdge又是InnerVertexWithOutgoingEdge的节点到OuterVertex的交叉边传递，例如在图G中，消息从节点5传递到节点3和9，反之亦然。

同步外部顶点作为目标¶

它与OnlyOut加载策略配合使用。这里每个片段$F_{i}$会将其OuterVertex v的"镜像"节点状态发送到v所在的$F_{j}$片段，如果存在边(v', v)且v'是$F_{i}$的"本地"节点，目的是同步v的不同状态。例如，节点3的"镜像"状态会从$F_{1}$发送到$F_{0}$，以便在$F_{0}$进行同步。

SyncOnOuterVertexAsSource¶

它与OnlyIn加载策略一起使用。类似于SyncStateOnOuterVertexAsTarget，每个片段$F_{i}$会将其"镜像"节点v的状态发送到对应片段进行同步。不同之处在于，对于每个这样的"镜像"节点，都存在到$F_{i}$中某个"本地"节点v'的出边(v, v')。例如，"镜像"节点1、9和12的状态会从$F_{1}$发送到$F_{0}$和$F_{2}$，以便与其他状态进行同步。

同步外部顶点¶

这与BothInOut加载策略一起应用。在这种情况下，每个分片$F_{i}$会将其所有"镜像"节点v的状态发送给对应的分片进行同步，而不管与v相邻的边的方向如何。例如，"镜像"节点1、3、9和12的状态会从$F_{1}$发送到$F_{0}$和$F_{2}$以进行进一步的同步。