B-Graphless：基于批处理的服务器less图处理技术，适用于具身AI后端应用

《Future Generation Computer Systems》：B-Graphless: Batch-based serverless graph processing for embodied AI backends

　　孙一鸣|张佳琪|张杰|曹华为|张媛|安学军|叶小春
中国科学院计算技术研究所处理器国家重点实验室，北京，中国

**摘要**
具身人工智能系统越来越多地依赖于基于图的表示形式，例如导航图和知识图，以支持在动态物理环境中的在线推理和决策制定。在实际应用中，这些系统通常会从多个代理设备生成突发性和高频的图遍历请求，对后端计算基础设施的延迟、资源效率和弹性可扩展性提出了严格要求。虽然无服务器计算因其弹性和细粒度的资源管理而具有吸引力，但现有的无服务器图处理框架在资源利用方面较低，在水平扩展时存在冗余的图加载问题，并且在频繁的遍历负载下延迟严重。本文提出了B-Graphless，这是一个基于批处理的图处理框架，专为受无服务器思想启发的执行环境设计，作为图驱动的具身AI应用的弹性后端。B-Graphless在容器实例中聚合并发且同质的图遍历请求，并以协调的批处理方式执行它们，从而提高数据局部性并降低图访问开销。为了在动态负载下支持高效的批处理执行，B-Graphless引入了基于运行时负载动态的自适应批处理生成机制、通过路径融合实现的共享遍历、考虑通信的调度以减少跨节点消息传递、分散式同步以及用于负载平衡的工作窃取技术。我们使用在具身AI流程中常见的图遍历负载（包括BFS、SSSP、连通分量和PageRank）在真实世界图数据集上评估了B-Graphless的性能。实验结果表明，与最先进的无服务器图处理框架FaaSGraph相比，B-Graphless将端到端性能提升了高达3.6倍，将跨主机通信量减少到原来的19.4%，并在频繁查询负载下将请求延迟平均降低了4.0倍。这些结果表明，B-Graphless为具身AI系统中的可扩展图处理提供了一个有效且实用的解决方案。

**引言**
具身人工智能系统，包括移动机器人和自主代理，越来越多地依赖基于图的表示形式来支持在物理环境中的在线感知、推理和决策制定 [1][2]。导航图、语义图和知识图编码了空间连通性、语义关系和上下文信息，这些对于路径规划、场景理解和多代理协调等任务至关重要 [3]。基于此类图的遍历查询是具身决策的基础，因为代理会反复探索共享环境模型的局部邻域以支持增量规划和推理。随着具身系统在自主性和部署规模上的扩展，所产生的图负载变得越来越密集和时间敏感，这对后端计算基础设施的性能、效率和响应能力提出了严格要求。

在许多实际应用中，具身AI系统采用云和边缘协同执行模型，其中计算密集型推理任务被卸载到后端服务，而感知和控制任务仍然由代理设备完成 [4]。在这种架构中，无服务器计算由于其弹性、细粒度的资源 provisioning 和操作简便性而成为一个有吸引力的执行范式 [5]。无服务器平台非常适合处理由多个代理生成的动态和突发性负载。然而，当应用于图处理时，现有的无服务器框架及其无服务器适配版本经常存在资源利用率低、频繁遍历请求时出现冗余图加载和较长响应延迟的问题 [6][7][8][9][10][11]。一个关键原因是这些系统通常依赖于水平扩展，即动态启动额外的功能实例或容器来吸收传入的请求，这会导致相同的图结构被反复单独加载和处理。图遍历负载中的不规则内存访问模式和数据依赖的执行行为进一步加剧了这些效率问题，严重限制了无服务器平台作为具身AI应用弹性后端的有效性。

在负载层面，具身AI系统中的图处理请求具有当前无服务器设计未能充分利用的结构特性。多个代理频繁操作共享图结构（如公共导航图或全局知识图），并在重叠的时间间隔内发出同质的遍历请求。这种访问模式自然创造了跨并发请求共享数据访问和协调执行的机会。然而，大多数现有的无服务器图系统将每个请求单独处理，将并发调用视为独立任务。这种执行模型导致不必要的数据移动、冗余的图访问以及计算资源的低效利用，尤其是在高请求率下。与这种请求隔离的执行模型相比，B-Graphless引入了兼容请求之间的执行级协调机制，同时不同于之前的基于批处理的图系统，因为它明确针对动态的无服务器执行环境而不是静态集群设置。

在本文中，我们介绍了B-Graphless，这是一个为受无服务器思想启发的执行环境设计的基于批处理的图处理框架，作为具身AI系统的弹性后端。B-Graphless没有假设严格的功能级无状态性，而是针对基于容器的无服务器执行进行设计，从而实现了受控的状态共享和资源复用。该系统在容器实例中聚合并发图遍历请求，并以协调的批处理方式执行它们，从而提高数据局部性，减少冗余图访问，并降低端到端响应延迟。为了在动态负载下支持高效的批处理执行，B-Graphless集成了基于运行时负载动态的自适应批处理生成、通过路径融合实现的共享遍历、考虑通信的调度以减少跨节点消息传递以及分散式工作窃取进行负载平衡。这些技术共同使无服务器图处理符合具身AI后端的在线、并发和资源高效执行要求。

**主要贡献**
B-Graphless的主要贡献在于一个系统级的无服务器图处理执行设计，而不是新的图算法或图论优化。本文的贡献在于：
• 高并发图处理的工作负载特征分析。我们识别并形式化了一类以频繁、同质和时间重叠的请求为特征的图遍历负载，这些请求是在共享图结构上进行的。受图驱动的具身AI后端和其他对延迟敏感的服务的启发，我们分析了为什么现有的无服务器执行模型在在线和突发请求模式下无法高效处理此类负载。
• 高并发图遍历的执行级批量模型。我们提出了一个基于容器实例的批量执行模型，该模型将并发图遍历请求聚合在一起，从而将现有无服务器系统中的突发性水平扩展转化为协调的实例内执行，实现共享图访问并减少冗余的数据加载和通信开销。
• 针对批量图处理的系统级运行时优化。我们设计了一组针对批量图处理的运行时优化技术，包括基于运行时负载动态的自适应批处理生成、通过路径融合实现的共享遍历、考虑通信的任务调度以减少跨节点消息传递以及容器间的分散式工作窃取。这些技术在不修改图算法的情况下提高了资源利用率和延迟性能。

**实施和评估**
我们通过扩展FaaSGraph实现了B-Graphless，并使用代表性的图算法（包括BFS、SSSP、CC和PageRank）在真实世界图数据集上对其进行了评估。实验结果表明，与最先进的无服务器图处理系统相比，B-Graphless提高了资源利用率，降低了端到端响应延迟，并提高了通信效率。

本文的其余部分组织如下：第2节分析了具身AI系统中图遍历负载的特性，并讨论了现有无服务器图处理方法的局限性。第3节介绍了B-Graphless的设计和执行模型，第4节详细介绍了其运行时优化。第5节使用代表性的图算法和真实世界数据集评估了B-Graphless的性能。第6节回顾了相关工作，第7节总结了本文。