原文：Sakr, Sherif, et al. "The future is big graphs: a community view on graph processing systems." Communications of the ACM 64.9 (2021): 62-71.
https://dl.acm.org/doi/abs/10.1145/3434642说明：本文作者于 2019 年 12 月在 Dagstuhl 参加了关于大图处理系统的研讨会19491。该研讨会聚集了来自数据管理和大规模系统社区的41名高素质研究人员组成的多元化小组。这是开始讨论图处理的下一个十年机遇和挑战的绝佳机会。
这是社区出版物。前四位作者共同组织了导致本文的社区活动，并协调了本手稿的创作。所有其他作者都对这项研究做出了同等贡献。不幸的是，Sherif Sakr 在事件发生后和本文完成期间去世。这篇文章发表以纪念。
我们正在见证互联数据的空前增长，这突显了图（graph）处理在社会中的重要作用。我们看到大图处理系统在许多社会热点领域不再是一个单一的、示范性的（杀手级的）应用程序，而是支持许多新兴但已经很复杂和多样化的数据管理生态系统。仅举几个最近著名的例子，这一领域对从业者的重要性的迹象有：一年半多时间里，大量（超过60,000）人注册下载 Neo4j 书籍《 GraphAlgorithms》， 以及对在人工智能 (AI) 和机器学习 (ML) 领域应用图处理的广泛兴趣。此外，及时的 Graphs 4 COVID-19 倡议证明了大图分析在缓解疫情方面的重要性。学术界、创业公司，甚至谷歌、Facebook 和微软等大型科技公司都推出了各种系统来管理和处理不断增长的大型图。Google 的 PageRank（1990年代后期）展示了Web级图形处理的强大功能，并推动了MapReduce编程模型的开发。而该模型最初用于简化构建用于处理搜索的数据结构，但此后被谷歌广泛用于实现大规模图处理算法。受可扩展性的推动，2010 年的GooglePregel “think-like-a-vertex”模型支持分布式PageRank计算，而Facebook、Apache Giraph和生态系统扩展支持对社交网络数据有用的更精细的计算模型（例如基于任务的而不总是分布式的）和数据模型（例如多样化的、可能是流式的、可能是广域数据源）。与此同时，越来越多的用例揭示了RDBMS在管理高度互联的数据方面的性能问题，激励了各种初创公司和创新产品，例如Neo4j、Sparksee和当前的AmazonNeptune。Microsoft Trinity和后来的AzureSQL DB为大图管理提供了一种早期的面向分布式数据库的方法。模型和系统的多样性最初导致了市场的碎片化和社区缺乏明确的方向。与这种趋势相反，我们看到了有望将编程语言、生态结构和性能基准结合起来的尝试。正如我们所说，没有任何杀手级应用程序可以帮助统一社区。本文由社区的一个代表性样本共同撰写（参见侧边栏“计算机系统和数据管理社区的联合努力”）。在本文中解决了以下问题：从数据管理和大型系统社区的观点来看，下一个十年的大图处理系统是什么样的？对于未来10年这些系统的设计指导原则，我们今天能说些什么？图 1 概述了未来大图处理系统的复杂管道。数据从不同的来源（已经建模成图形或者非图形）流入、存储、管理，并通过在线事务处理 (OLTP) 操作（例如插入、删除、更新、过滤、投影、连接、合并）。然后通过在线分析处理 (OLAP) 操作（例如分组、聚合、切片、切块和汇总）对数据进行分析、丰富和浓缩。最终，它被流通到各种应用程序中使用，包括机器学习（例如 ML 库和处理框架）、商业智能 (BI)（例如报告生成和规划工具）、科学计算、可视化、增强现实（供用户检查和交互）等。应当注意，这通常不是一个纯粹的线性过程，可能会出现混合 OLTP/OLAP 过程。相当大的复杂性源于（中间）结果反馈给早期流程步骤，如蓝色箭头所示。
例如，研究冠状病毒及其对人类和动物种群的影响（例如，COVID-19新型冠状病毒肺炎），图1中描绘的管道可用于两种主要类型的分析：基于网络的“组学”和药物相关搜索，以及基于网络的流行病学和传播预防。对于前者（基于网络的“组学”和药物相关搜索），管道可以有以下步骤：
1. 最初的基因组测序帮助识别相似的疾病。
2. 文本（非图形数据）和结构化（数据库）搜索帮助识别与疾病相关的基因。
3. 利用各种模拟，网络处理手段可以揭示各种药物靶点和有效的抑制剂，还可能对可用药物和治疗方法的有效性做排序。对于后者（基于网络的流行病学和传播预防），社交媒体和位置数据，以及来自其他隐私敏感来源的数据，可以被组合成社会互动图，通过遍历这些图来确定超级传播者和相关的超级传播事件。这些分析可以帮助制定预防政策和遏制行动。然而，目前这一代的图处理技术无法支持这样一个复杂的管道。例如，在COVID-19知识图谱上，可以针对单个图谱提出有用的查询（如检查论文、专利、基因和最具影响力的COVID-19相关作者等）。然而，如图1所示，在一个成熟的图处理管道中检查多个数据源，跨越多个图数据集，给目前的图数据库技术带来了许多挑战。在本篇文章中，我们形式化定义了这些挑战，并针对三个主要方面（抽象概念，生态系统和性能）提出我们对下一代大图处理系统的期望。我们提出了预期的数据模型和查询语言，以及它们在抽象网格中的内在关系，并讨论了这些抽象和网格结构为适应未来的图数据模型和查询语言的灵活性。这将巩固对图1所示图数据提取、交换、处理和分析的基本原则的理解。我们将要讨论的第二个重要问题是对能够管理大图处理系统并支持调整各种组件（例如OLAP/OLTP 操作、工作负载、标准和性能需求）的生态系统的期望。这些方面使大型处理系统比过去十年中看到的更加复杂。图1提供了一个高级别的在输入、输出、处理需求和图形数据的最终消费方面对这种复杂性的看法。第三个问题是理解和控制未来生态系统中的性能。我们有重要的性能问题需要克服，从关于执行有意义、易处理和可重复的实验的方法论方面，到关于可扩展性与可移植性和互操作性权衡的实际方面。抽象广泛用于编程语言、计算系统和数据库系统等领域，用于隐藏技术细节，以支持更用户友好、面向领域的逻辑视图。目前，用户必须从大量相似的图数据模型中进行选择，但这些数据模型在表达能力、代价以及查询和分析的预期用途方面有所不同。这种“抽象汤”提出了未来需要解决的重大挑战。
理解数据模型。现今面对这么多数据模型（有向图、RDF、属性图的变体等），图数据管理面临着关键挑战：决定每个用例选择哪种数据模型，以及控制来自不同模型的数据组合在一起的数据模型的互操作性（如图 1 左侧所示）。这两个挑战都需要对数据模型有更深入的了解：
1.人们如何定义数据和数据操作？数据模型及其各自的运算符如何支持或阻碍人类的思维过程？我们能否度量数据模型及其运算符有多“自然”或“直观”？
2. 我们如何量化、比较和（部分）排序数据模型的表达（建模和操作）能力？具体来说，图 2 展示了一个用于选择图形数据模型的网格。自下而上阅读，这个格子显示了必须将哪些特征添加到图数据模型中才能获得更丰富的表现力的模型。该图还强调了理论、算法、标准和相关行业系统中使用的数据模型的多样性。我们如何将这种比较理解扩展到多个数据模型系列，例如图形、关系或文档？选择一种模型而不是另一种模型的成本和收益是什么？
3. 不同数据模型之间的互操作性可以通过映射（跨不同数据模型中概念的语义断言）或直接翻译（例如，W3C 的 R2RML）来实现。是否有表达此类映射的通用方法或构建块（例如类别理论）？研究 (1) 需要专业应用数据和数据模型的研究人员。这类人员在数据管理领域并不常见，所以应与其他领域合作进行，例如人机交互 (HCI)。例如，在Sigmod的HILDA研讨会中存在有关HCI和图的工作。然而，这些并不是在探索图数据模型的搜索空间。(2)和(3)的研究可以建立在数据库理论的现有工作基础上，也可以利用相关计算机科学社区在比较、特征化、图形摘要、可视化和模型转换方面的发现。例如，图摘要已被广泛用于在图挖掘中提供图属性的简洁表示，但图处理系统很少使用它们来使处理更高效、更有效、更以用户为中心。例如，属性图的近似查询处理不能像其关系对应物那样依赖采样，并且可能需要使用商图摘要来回答查询。基于逻辑的声明式形式。逻辑为表达查询、优化、完整性约束和集成规则提供了统一的形式。从 Codd 将逻辑公式与关系查询相关联的开创性见解开始，许多一阶 (firstorder, FO) 逻辑片段已被用于正式定义具有所需属性（例如可判定求值）的查询语言。图查询语言本质上是增加了递归功能的FO句法变体。逻辑为推理图查询和图约束提供了一个尺度。事实上，一个有前景的研究方向是应用形式化工具，例如模型检查、定理证明和测试，以建立复杂图处理系统的功能正确性，尤其是图数据库系统的功能正确性。逻辑不仅对数据库语言有至关重要的影响，而且是将逻辑推理与人工智能中的统计学习相结合的基础。逻辑推理通过逻辑演绎推导出关于一段数据的分类概念。统计学习通过学习已知数据的统计模型并将其应用于新数据来推导出分类概念。两者都利用图的拓扑结构（本体和知识图谱或Node2vec等图嵌入，用以产生比非连接数据更好的发现）。然而，两者恰巧是孤立的。结合这两种技术可以带来重要的进步。例如，在图上做的深度学习（无监督特征学习）能让我们推断结构规律并获得图的有意义的表示。这些表示可以通过图数据库中的索引和查询机制进一步利用，并用于逻辑推理。再举一个例子，概率模型和因果关系可以自然地编码在属性图中，并且是高级图神经网络的基础。得益于它们内在的表达能力和嵌入的领域知识，属性图允许我们为ML管道生成更准确的模型。这些思考揭示了如下重要的开放性问题：如何将统计学习、图处理和推理结合起来？哪些潜在的形式会使这成为可能？我们如何权衡这两种机制？用于图形处理的代数运算符。目前，没有标准的图代数。图查询语言 (graph query language, GQL) 标准化项目的结果可能会影响图代数以及现有和未来用例的设计。然而，下一代图形处理系统应该解决有关其代数组件的问题。与其他代数（关系、群、有向图或路径、关联和一元代数推导式）相比，该代数的基本运算符是什么？图处理系统应该支持哪些核心图代数？此代数中是否包含图分析运算符？这个图代数能否与类型代数相结合和集成，使类型系统更具表现力并促进类型检查？ “类关系”图代数能够表达所有一阶查询，并使用可以使用图模式匹配运算符进行增强，这似乎是一个很好的起点。然而，最有趣的面向图的查询是导航性的，例如可达性查询，并且不能用关系代数的有限递归来表达。此外，关系代数是一个封闭代数。也就是说，每个操作的输入和输出都是一个关系，这使得关系代数操作可以组合。我们的目标应该是一个同时包含关系和图的封闭图代数吗？当前的图查询引擎将代数运算符和特定图算法结合到复杂的工作负载中，这使实现变得复杂，并会影响性能。基于单个代数的实现似乎也不现实。然而，具有通用图灵机功能（如编程语言）的查询语言会有易处理性和可行性问题。代数运算符同时运用在集中式和分布式环境中，并且可以被用在图算法和 ML 模型（例如 GNN、graphlets和图嵌入），这可能是未来非常需要的。生态系统不同于单纯的系统的系统，它们结合了为不同目的和不同流程开发的许多系统。图1举例说明了通过高性能OLAP和OLTP管道协同工作的图形处理生态系统的复杂性。那么，与生态系统相关的挑战是什么呢？图处理生态系统中的工作负载。工作负载影响功能需求（图处理生态系统能够做什么）和非功能需求（有多好）。如图 1 所示，调查数据指向管道：复杂的工作流，结合异构查询和算法，管理和处理不同的数据集，其特征总结在侧边栏“图形处理工作负载的已知属性”中。在图1中，图形处理连接到一般处理（包括ML），以及特定领域的处理生态系统，例如科学和工程中的模拟和数值方法、商务分析中的聚合和建模，以及社交媒体中的排名和推荐。数据模型和查询语言的标准。图处理生态系统标准可以提供通用的技术基础，从而增加应用程序、工具、开发人员、用户和利益相关者的流动性。OLTP和OLAP工作负载的标准应该标准化数据模型、数据操作和数据定义语言以及交换格式。它们应该很容易被现有实现采用，并且还可以在基于SQL的技术环境中启用新的实现。标准遵循广泛使用的图形查询语言，反映现有的行业实践非常重要。为此，ISO/IEC于2019 年启动了GQL标准化项目，将GQL定义为一种新的图查询语言。GQL得到10个国家标准机构的支持，其中包括来自主要行业供应商的代表，以及由关联数据基准委员会（Linked Data Benchmarks Council, LDBC）代表的属性图社区的支持。GQL最初专注于事务性工作负载，将支持使用增强的常规路径查询（regular path queries, RPQ）、图转换（视图）和图更新功能对多个可能重叠的图进行组合图查询。GQL通过模式量化、排名和路径聚合来增强RPQ。在语法上，GQL将SQL风格与Cypher开创的可视化图形模式相结合。从长远来看，标准化图形算法的构建块、分析API和工作流定义、图形嵌入技术和基准也是值得的。然而，这些方面的广泛采用需要技术成熟。参考架构。我们明确了为大图处理定义参考架构的困难。参考架构的早期定义极大利于围绕云和网格计算解决方案的设计、开发和部署的讨论。对于大图处理，我们从图3中得出的主要见解是，许多图处理生态系统都与数据中心的通用参考架构相匹配。此处描述的Spark生态系统是数以千计的可能实例之一。挑战在于捕捉不断发展的图形处理领域。超越纵向扩展与横向扩展。许多图形平台专注于纵向扩展或横向扩展，每个都有相对的优势。除了简单地协调纵向扩展和横向扩展之外，我们还设想了一个可扩展的连续体：给定多样化的工作负载，生态系统将自动决定如何运行它，以及在什么样的异构基础设施上运行，以满足服务级别协议 (service-level agreements, SLAs)。存在多种机制和技术来执行纵向扩展和横向扩展决策，例如数据和工作分区、迁移、卸载、复制和弹性扩展。这些决策都可以使用各种优化和学习技术静态或动态做出。动态图和流图。未来的图处理生态系统应该处理动态和流式图数据。动态图扩展了图的标准概念以支持更新（插入、更改、删除），以便可以无缝查询当前和以前的状态。随着数据的扩充，流式图可以一直增长。它们通常是无界的，因此底层系统无法保持整个图状态。滑动窗口语义允许将两个概念统一起来，插入和删除被视为到达窗口和从窗口删除。由于当前的流处理技术相当简单，例如工业图形处理库（例如Apache Flink中的Gelly）中的聚合和投影，对“复杂图形数据流”的需求是显而易见的，以及更高级的图形分析和ML临时操作符。另一个研究挑战是确定可以在动态和流图上评估的图查询处理运算符，同时考虑递归运算符和面向路径的语义，这是GQL和G-Core等标准查询语言所需要的。图处理平台也是动态的。发现、理解和控制复杂图形处理生态系统中发生的动态现象是一个开放的挑战。随着图形处理生态系统变得越来越主流，并嵌入到更大的数据处理管道中，我们期望越来越多地观察到已知的系统现象，例如性能可变性、级联故障的存在和自动缩放资源。会出现哪些新现象？哪些编程抽象和系统技术可以响应它们？图处理提出了独特的性能挑战，从缺乏广泛使用的性能指标（除了响应时间）到比较跨架构的图处理系统的方法论问题，以及调参过程中的性能可移植性和可复现性等。对于图形处理生态系统而言，此类挑战变得更加艰巨。
基准、性能度量和方法论方面。图处理存在与其他计算学科类似的方法论问题。实行全面的图处理实验缺乏易处理性，尤其是在规模上。即在合理的时间和成本内实施、部署和实验的能力。与其他计算学科一样，我们需要新的、可重复的、实验性的方法。图形处理还在与复杂工作负载和数据管道相关的性能度量和基准测试方面提出了独特的挑战（图1）。即使是看似微小的HPAD变化，例如图的度数分布，也会对性能产生重大影响。缺乏互操作性阻碍了公正比较和基准测试。索引和采样技术可能被证明有助于改进和预测图查询的运行时间和性能，这对大规模系统、数据管理、数据挖掘和机器学习的社区也是个挑战。图处理系统依赖于结合软件和硬件平台的复杂运行时。捕获被测系统的性能（包括并行性、分发、流与数据流和批处理），并测试实际部署中可能存在的数百个库、服务和运行时系统的操作可能是一项艰巨的任务。我们设想了多种方法的组合。与其他计算学科一样，我们需要新的、可重复的实验方法。这引发了具体的问题：我们如何促成快速而有意义的性能测试？我们如何为图算法、查询、程序或工作流的执行定义更可靠的指标？我们如何通过组合操作生成工作负载，涵盖时间、空间和流方面？我们如何对管道进行基准测试，包括机器学习和模拟？我们还需要像LDBC这样的组织来管理基准共享并在实践中审核基准使用情况。专用化与可移植性和互操作性。出于性能原因的专门图形处理堆栈与通过可移植性和互操作性为领域科学家提供生产力之间存在相当大的矛盾。专用化，通过定制软件，尤其是硬件加速，可以显著提高性能。如侧边栏中所述，专门研究图形工作负载，侧重于图处理中的多样性和不规则性：纯粹的数据集规模（由Pregel和后来的开源项目Giraph解决），顶点度的（截断的）幂律分布(PowerGraph)、本地化和面向社区的更新 (GraphChi)、跨数据集的不同顶点度分布（PGX.D、PowerLyra）、不规则或非本地顶点访问（Mosaic）、对专用硬件的亲和力（BGL系列、HAGGLE、rapids.ai）等。高性能计算领域为它们提出了专门的抽象和C++库，以及跨异构硬件的高性能和高效运行时，例如BGL、CombBLAS和GraphBLAS。包括Neo4j、GEMS、和Cray’sUrika在内的数据管理方法，侧重于方便的查询语言（如SPARQL和Cypher）以确保可移植性。目前的工作还侧重于（自定义的）加速器。通过可重用组件实现的可移植性看起来很有前景，但目前不存在标准图形库和查询语言。存在100多个大型图处理系统，但它们不支持可移植性：图系统很快将需要支持不断发展的过程。最后，互操作性意味着使用多领域工具将图处理集成到更广泛的工作流程中。与机器学习和数据挖掘过程以及模拟和决策工具的集成似乎很重要，但现有框架并不支持。用于大图处理系统的memex。受到Vannevar Bush 1940年代个人 memex 概念的启发，以及2010年代对分布式系统Memex的专业化，我们创建一个大图 Memex 来收集、存档和检索有关此类系统的有意义的操作信息将既有趣又有用。这可能有利于了解和消除性能和相关问题，实现更具创意的设计和扩展自动化，以及有意义和可复现的测试，例如智能图形处理中的反馈构建块。图是当今数据处理管道中的主要抽象概念。未来的大图处理和数据库系统如何提供高度可扩展、高效和多样化的查询和分析能力，以满足现实世界的需求？
为了解决这个问题，我们采取了社区方法。我们从 Dagstuhl 研讨会开始，不久之后，形成了此处介绍的结构化连接。我们在本文中关注三个相互关联的元素：抽象概念、生态系统和性能。对于这些元素，我们已经提供了对未来研究的看法。只有时间才能证明我们的预测是否为社区提供了有价值的指导。同时，与我们一起解决大图处理的问题吧！未来是属于大图的。
