共计 3656 个字符，预计需要花费 10 分钟才能阅读完成。
作者：沈雯婷
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-final4…\
开源我的项目地址: GraphLearn, GraphScope
背景介绍
GNN 模型通过图构造表征高阶邻域信息，在大规模工业落地中，一种罕用的训练形式是通过邻域采样的形式来升高通信和计算的开销，从而取得分布式的扩展性。与此同时，在举荐、金融反欺诈等实在业务场景中，图的构造和属性往往会随着工夫动态变化，GNN 模型须要能 实时采样 并表征这些邻域的动静信息。
因为在线学习容易造成模型的抖动，在理论生产利用中，模型的部署也通常须要通过简单的生产链路，因而个别采纳近线模型进行部署，为了让 GNN 模型可能实时表征邻域信息，在 GNN 模型的推理过程中，须要通过实时的采样图构造和属性来进行 实时推理。
为保障用户体验，这种实时推理的工作具备极低时延的需要，留给采样查问的时延空间十分小。同时，因为工业大图的数据规模和在线推理服务的 QPS 往往超出单机的存储和计算能力。因而，咱们须要提供一个在 大规模的动态图上保障极低时延 的面向 GNN 模型推理的实时采样服务（P99 在 20 毫秒以内），并具备在分布式环境下线性扩大的能力。
挑战
实时图采样服务的直观做法是保护一个动态图的存储和查问模块，在推理申请达到时对申请的点进行街坊采样计算和属性收集，采样计算失去的样本作为模型服务的输出进行推理。然而图数据的散布和推理采样的负载个性，导致这种直观的做法难以在分布式的动态图上实现稳固的低延时采样，具体地，存在以下挑战：
- 街坊采样须要遍历所有的街坊，并且随着图的动态变化，街坊一直变动，难以保障简单的采样计算的低时延，超点的存在也造成了时延的不稳固。
- 因为图数据分布存在不平衡的特点，各个图分片上的存储和计算负载散布不均，造成采样延时的不稳固，也为分布式下线性扩大带来挑战。
- 推理采样个别为多跳采样，并且须要收集顶点或边上的动静属性，在分布式图上，多跳采样和属性拜访带来的网络和本地 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 零碎设计的关键点：
- 存算拆散和感知 Query 的 Cache
DGS 将图存储和采样计算进行拆散。采样计算个别是指随机采样，最新街坊采样（topk timestamp），或通过边权重（或边 timestamp）做概率分布采样。前两种采样的工夫复杂度为 O(1)，概率分布采样通常应用 Alias Method 实现，在动态图中变动的概率分布上须要反复计算 Alias Table，其工夫和空间复杂度均为 O(N), 其中，N 为顶点的街坊数，并一直发生变化。与图存储的简略读写不同，图采样过程蕴含存储的读写与简单的计算，因而咱们首先将存储和计算进行拆散，并且在计算侧，零碎事后将服务的特定 Query 所须要拜访的数据 cache 起来，以晋升图采样计算的空间局部性。
- Event-driven 预采样
为了减速采样申请的响应，DGS 将每个顶点的采样计算从申请输出的时刻提前到图更新事件产生的时刻，利用空间换取工夫，使得采样申请产生时仅须要实现点查。同时，为了升高图更新事件从产生到样本生成之间的 staleness，DGS 采纳流采样的形式，通过带权重的蓄水池采样算法，在每个更新达到时，依据预装置的 Query，进行流式采样。这种图更新事件驱动的采样前置的形式，使得对每个顶点的图数据存储空间和计算工夫都变成了常数 *O(K)，其中 K 为蓄水池大小。通过将图采样计算的后果事后存储在 cache 中解决了挑战 1 中的问题。
- Multi-hop 拆解和 Lazy 拼接
至此，DGS 解决了输出顶点的实时一跳采样。然而 DGS 次要服务于多跳采样，以二跳采样为例，输出顶点的一跳后果更新后，对应的二跳后果也须要更新（同时更新收集的属性）。在跳数更多的状况下，这种连锁反应造成的指数级增长的读写开销，对采样申请的时延产生微小的影响。DGS 解决该问题的形式是依据预装置的 Query，将图采样依照每一跳进行拆解。对于每一跳采样，对图中对应顶点类型的所有顶点进行对应的流式预采样和存储。例如，图 1 中的 Query 能够拆解位图 2 所示，联合 Event-driven 预采样，每个顶点对应的样本在蓄水池中存储和更新如图 3 所示。
并且，DGS 将多跳样本的拼接推延到对应的推理采样申请产生的时刻（Lazy 拼接），以防止提前拼接后继续更新。
图 2: 二跳采样 Query 拆解
图 3: Event-driven 更新
- 订阅 - 公布机制
咱们将多跳的拼接提早到申请产生的时候，然而，多跳后果往往存储在不同分片上，跨机通信带来了大量的网络通信开销。因而，DGS 设计了一套订阅 - 公布机制，行将申请的 id 依据特定的分片算法路由到对应的服务机器上，该机器上订阅这些 id 和它的多跳街坊的更新。随着街坊关系的扭转，订阅表也不断更新。
- 读写隔离
依据以上的零碎设计，当采样申请产生时，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，欢送试用！更多细节请参考源码和技术文档。
