作者：沈雯婷

GraphLearn 是阿里云机器学习平台 PAI 团队和达摩院智能计算实验室图计算团队共建的工业界大规模图神经网络训练框架, 也是一站式图计算平台 GraphScope 的图学习引擎。GraphLearn 最新开源了面向动态图的 GNN 在线推理实时采样服务(DGS)。DGS 具备处理实时高吞吐图更新的能力，并能保证低时延、高并发的推理采样查询处理。其图更新和采样查询的性能在分布式环境下线性可扩展。近期，GraphLearn 团队和浙大联合发表的《Dynamic Graph Sampling Service for Real-time GNN Inference at Scale》被评选为 EuroSys2023 best poster。

Poster 地址：https://2023.eurosys.org/docs/posters/eurosys23posters-final40.pdf

开源项目地址: GraphLearn, GraphScope

背景介绍

GNN 模型通过图结构表征高阶邻域信息，在大规模工业落地中，一种常用的训练方式是通过邻域采样的方式来降低通信和计算的开销，从而获得分布式的扩展性。与此同时，在推荐、金融反欺诈等真实业务场景中，图的结构和属性往往会随着时间动态变化，GNN 模型需要能实时采样并表征这些邻域的动态信息。

由于在线学习容易造成模型的抖动，在实际生产应用中，模型的部署也通常需要经过复杂的生产链路，因此一般采用近线模型进行部署，为了让 GNN 模型能够实时表征邻域信息，在 GNN 模型的推理过程中，需要通过实时的采样图结构和属性来进行实时推理。

为保证用户体验，这种实时推理的任务具有极低时延的需求，留给采样查询的时延空间非常小。同时，由于工业大图的数据规模和在线推理服务的 QPS 往往超出单机的存储和计算能力。因此，我们需要提供一个在大规模的动态图上保障极低时延的面向 GNN 模型推理的实时采样服务（P99 在 20 毫秒以内），并具备在分布式环境下线性扩展的能力。

挑战

实时图采样服务的直观做法是维护一个动态图的存储和查询模块，在推理请求到达时对请求的点进行邻居采样计算和属性收集，采样计算得到的样本作为模型服务的输入进行推理。但是图数据的分布和推理采样的负载特性，导致这种直观的做法难以在分布式的动态图上实现稳定的低延时采样，具体地，存在以下挑战：

1. 邻居采样需要遍历所有的邻居，并且随着图的动态变化，邻居不断变化，难以保证复杂的采样计算的低时延，超点的存在也造成了时延的不稳定。

2. 由于图数据分布存在不均衡的特点，各个图分片上的存储和计算负载分布不均，造成采样延时的不稳定，也为分布式下线性扩展带来挑战。

3. 推理采样一般为多跳采样，并且需要收集顶点或边上的动态属性，在分布式图上，多跳采样和属性访问带来的网络和本地 I/O 开销，对时延造成很大的影响。

关键设计

与一般图数据库的负载不同，动态图推理采样服务在服务于一个给定的模型的在线推理时，其对应的图采样具有固定的 pattern。如一个常见 User-Item，Item-Item 二部图上的 GraphSAGE 模型，这个图采样的 pattern 一般是对于请求的用户 ID（feed_id），根据时间戳作为概率采样它最新 2 个最新购买的商品，对这 2 个商品采样他们相关系数最高的 2 个商品。用 GraphLearn 提供的 GSL（Graph Sampling Language）表达成如下 Query：

图1: 二跳采样Query

这种固定 pattern 的 Query，给大规模的动态图采样提供了稳定的低延时服务的机会。

DGS 系统设计的关键点：

1. 存算分离和感知 Query 的 Cache

DGS 将图存储和采样计算进行分离。采样计算一般是指随机采样，最新邻居采样（topk timestamp），或通过边权重（或边 timestamp）做概率分布采样。前两种采样的时间复杂度为 O(1)，概率分布采样通常使用 Alias Method 实现，在动态图中变化的概率分布上需要反复计算 Alias Table，其时间和空间复杂度均为 O(N), 其中，N 为顶点的邻居数，并不断发生变化。与图存储的简单读写不同，图采样过程包含存储的读写与复杂的计算，因此我们首先将存储和计算进行分离，并且在计算侧，系统预先将服务的特定 Query 所需要访问的数据 cache 起来，以提升图采样计算的空间局部性。

2. Event-driven 预采样

为了加速采样请求的响应，DGS 将每个顶点的采样计算从请求输入的时刻提前到图更新事件发生的时刻，利用空间换取时间，使得采样请求发生时仅需要完成点查。同时，为了降低图更新事件从发生到样本生成之间的 staleness，DGS 采用流采样的方式，通过带权重的蓄水池采样算法，在每个更新到达时，根据预安装的 Query，进行流式采样。这种图更新事件驱动的采样前置的方式，使得对每个顶点的图数据存储空间和计算时间都变成了常数*O(K)，其中 K 为蓄水池大小。通过将图采样计算的结果预先存储在 cache 中解决了挑战 1 中的问题。

3. Multi-hop 拆解和 Lazy 拼接

至此，DGS 解决了输入顶点的实时一跳采样。然而 DGS 主要服务于多跳采样，以二跳采样为例，输入顶点的一跳结果更新后，对应的二跳结果也需要更新（同时更新收集的属性）。在跳数更多的情况下，这种连锁反应造成的指数级增长的读写开销，对采样请求的时延产生巨大的影响。DGS 解决该问题的方式是根据预安装的 Query，将图采样按照每一跳进行拆解。对于每一跳采样，对图中对应顶点类型的所有顶点进行对应的流式预采样和存储。例如，图 1 中的 Query 可以拆解位图 2 所示，结合 Event-driven 预采样，每个顶点对应的样本在蓄水池中存储和更新如图 3 所示。

并且，DGS 将多跳样本的拼接推迟到对应的推理采样请求发生的时刻（Lazy 拼接），以避免提前拼接后持续更新。

图2: 二跳采样Query拆解

图3: Event-driven更新

4. 订阅-发布机制

我们将多跳的拼接延迟到请求发生的时候，然而，多跳结果往往存储在不同分片上，跨机通信带来了大量的网络通信开销。因此，DGS 设计了一套订阅-发布机制，即将请求的 id 根据特定的分片算法路由到对应的服务机器上，该机器上订阅这些 id 和它的多跳邻居的更新。随着邻居关系的改变，订阅表也不断更新。

5. 读写隔离

根据以上的系统设计，当采样请求发生时，DGS 将它路由到指定 worker，进行本地的查询即可获得多跳采样结果。为了优先保障读的 latency，同时保证写的 staleness，DGS 在调度读写 task 时进行优先级调度。同时，在系统架构上，将频繁计算和更新存储（写）的任务和响应采样请求（读）的任务放在不同的机器上，进行读写的隔离。

系统架构

DGS 系统的核心组件架构如下图所示，主要为 Sampling Worker 和 Server Worker 组件。

图4: DGS系统核心架构

图更新根据 Key（例如顶点 ID）分片发给 Sampling Worker 的对应分区。每个 Sampling Worker 负责特定的分区：进行一跳预采样并将结果发给 Serving Worker。每个 Serving Worker 缓存从 Sampling Worker 接收到的 K 个一跳查询的采样结果，并响应全图中某一特定分片的顶点的推理采样请求。

Sampling Workers 和 Serving Workers 可以独立的进行弹性扩缩容，以应对图更新和推理请求的负载变化。为了让生成完整 K 跳采样结果的延迟最小化，DGS 将顶点$V_i$的所有 K 跳采样结果提前发送给响应$V_i$推理请求的 Serving Worker，使得 K 跳图采样计算转化为仅需要访问 Serving Worker 上本地缓存的操作。为了实现这一点，每个 Sampling Worker 维护每个一跳查询的订阅表，记录订阅一跳查询结果的 Serving Worker 列表。例如，将顶点

$V_j$从$V_i$的一跳样本中增删会触发消息来将该事件发送到包含$V_j$的分区的 Sampling Worker，并相应地更新$V_j$的订阅信息。

通过这种设计，DGS 可以在高并发的推理采样的负载下，表现出非常稳定的延迟性能。

性能

在真实的阿里巴巴电子商务数据集上进行的实验表明，DGS 可以将推理请求 (两跳随机采样查询)的 P99 延迟保持在 20ms 毫秒之内，单个 Serving Worker 的 QPS 约 20,000，并可以线性扩展。图数据更新的吞吐达到 109MB/s，也同样可以线性扩展。

图5: 实验配置和性能数据

结语

本文对 DGS 进行了技术解读，介绍了 DGS 核心模型的设计思路。实际上，DGS 作为服务还包含了服务拉起模块、高可用模块、数据加载模块，以及和模型服务对接的客户端，借助 DGS，用户可以基于实时变化的图结构和特征来推理得到最新的图表征。我们提供了一个端到端的基于 GraphLearn 的训练、模型部署和基于 DGS 在线推理的tutorial，欢迎试用！更多细节请参考源码和技术文档。