一、是什么
Fast and ncurrent RDF queries using RDMA-assisted GPU graph exploration
现有问题：随着 RDF 图规模的增加和 SPARQL 查询的并发水平的增加，当前的 RDF 系统面临着处理海量数据并行性时的低效并发查询处理，这通常导致响应时间（延迟）和吞吐量的不理想。
Wukong+G： 第一个基于图形的分布式 RDF 查询处理系统，它有效地利用了 CPU 和 GPU 的混合并行性。利用分布式异构 CPU/GPU 集群加速基于分布式图形探索的异构 RDF 查询。
三个关键设计：
- Wukong+G 利用 GPU 来处理图形探索中的随机内存访问，通过有效地映射 CPU 和 GPU 之间的数据进行延迟隐藏，包括一组技术，如查询感知预取、模式感知流水线和细粒度交换。
- Wukong+G 通过引入一个 GPU 友好的 RDF 存储来扩展规模，以支持超过 GPU 内存大小的 RDF 图，使用谓词基础分组、成对缓存和向前替换等技术来缩小主机和设备内存规模之间的差距。
- Wukong+G 通过一个通信层来扩展规模，该通信层将查询元数据和中间结果的传输过程解耦，并利用本地和 GPUDirect RDMA 在 CPU/GPU 集群上实现高效通信。
二、为什么
2.1 RDF 图规模的急剧增加对大型 RDF 数据集上的快速和并发查询提出了巨大的挑战
Wukong 利用基于 RDMA 的图形探索来支持具有低延迟要求的大规模并发查询，并采用完全历史修剪来避免最终的连接操作。
2.2 许多 RDF 查询并行性不好，查询的异构性可以导致现有 RDF 存储库的巨大延迟差异
重型查询，通常使用图形探索在过多的路径上触及 RDF 图的大部分。一个重型查询阻塞其他查询，大大延长其他查询的延迟，并严重损害处理并发查询的吞吐量。
多线程机制被广泛用于以前的工作中，以提高重查询的性能。然而，这种方法本质上受限于 CPU 的有限计算资源。
先前的研究（例如 Wukong）已经成功地通过利用带有完整历史记录修剪的图形探索来展示运行轻查询的低延迟和高吞吐量，但它仍然无法有效地处理重查询。这导致面对包含轻和重查询的混合工作负载时性能不佳。
2.3 GPU 被设计为提供大规模简单控制流操作的高计算吞吐量，具有很少或没有控制依赖性
先前的研究面对包含轻和重查询的混合工作负载时性能不佳。该论文将此问题归因于处理混合工作负载（轻和重查询）时同质化硬件（CPU）的局限性，它既不能提供足够的计算资源（少数核心），也不能提供高效的数据访问（低带宽）
GPU 的一些特点为将重型查询放到 GPU 上分配混合工作负载提供了设计空间：
查询处理的图形探索策略严重依赖于在图形存储上遍历大量路径，这是 GPU 高内存带宽针对的典型内存密集型工作负载。
- GPU 的内存延迟隐藏能力天生适合于对 RDF 图形上的随机遍历。
- 每个使用完整历史修剪方案的遍历路径都是完全独立的，可以在数千个GPU核心上完全并行化。
然而 RDF 图查询是内存密集型而不是计算密集型：存在有限的算术操作，大部分处理时间花费在随机内存访问上。
这种独特的特征意味着 Wukong+G 性能优化的关键在于智能的内存使用而不是改进计算算法。
三、怎么做
3.0 系统架构
在连接具有 RDMA 功能的快速网络的现代集群上运行，每台机器都配备一个或多个 GPU 卡。
通过将 RDF 图分区到多台服务器上的大量碎片来进行扩展。
没有顶点的副本，因为不需要同步顶点数据。
在服务器端采用去中心化、共享无物和主存储模型。
每个服务器由两个独立的层组成：查询引擎和图存储。
查询引擎层通过在 N 个 CPU 内核上运行 N 个工作线程，并分配一个 CPU 内核来运行代理线程来采用工作线程模型；代理线程将协助 GPU 内的工作线程运行查询。每个 CPU 上的工作/代理线程都有一个任务队列，以持续处理客户端或其他服务器的查询，每次处理一个。
图形存储层采用分布式哈希表上的 RDMA 友好的键/值存储来支持分区全局地址空间。
Wukong+G 使用一组专用代理程序来运行客户端库并从大量客户端收集查询。每个代理将查询解析为一组存储过程，并使用基于成本的方法生成最佳查询计划。代理将进一步使用成本将查询分类为两种类型（轻型或重型），并相应地将其传递给工作线程或代理线程。
3.1 高效的 GPU 查询处理
3.1.0 概述
利用 GPU 的多核特性和延迟隐藏能力。还采用了查询感知预取来缓解对图形大小的限制，模式感知流水线来隐藏数据移动成本，并采用精细的交换来最小化数据传输大小。
基本方法是将一个 CPU 内核专用于执行查询的控制流，并使用大量的 GPU 内核来并行化查询的数据流。
三个挑战：GPU 内存小，PCIe 带宽受限，跨GPU通信。
提出三个技术来克服上述挑战。
3.1.1 查询感知预取
将 GPU 内存视为 CPU 内存的缓存，并在运行查询之前仅保留必要的数据在 GPU 内存中。
3.1.2 模式感知流水线
进一步观察到查询的三元组模式将按顺序执行，这意味着 Wukong+G 可以进一步将内存需求降至每个模式规模。
由于数据预取和查询处理被拆分为多个独立的阶段，Wukong+G 可以使用软件流水线在当前三元组模式的执行和下一个谓词的预取之间创建并行性。
3.1.3 细粒度交换
所有具有相同谓词的三元组将进一步分成多个固定大小的块，并且 GPU 内存将以最佳方式缓存三元组。因此，内存需求将进一步降至每块规模。
此外，数据传输成本也将变为每块规模，并且在 GPU 内存中的所有缓存数据可以被同一查询或甚至多个查询的多个三元组模式重复使用。
3.2 GPU 友好的 RDF 存储
3.2.0 概述
采用分布式内存键值存储，并提出了基于谓词的分组，以分别汇总具有相同谓词的键和值。
之前的工作使用分布式内存键值存储来物理存储 RDF 图，这种存储方式对于图探索中的随机遍历很有效。
然而，具有相同谓词的三元组（键和值）仍然分散在整个存储中。
Wukong+G 提出了以下三个新技术来构建一个GPU友好的键/值存储。
3.2.1 基于谓词的分组（CPU 内存）
Wukong+G 采用基于谓词的分组来利用三元组的谓词局部性，并保留键和值的编码。基本思想是将键空间划分为多个片段，由谓词和方向的组合（即 [pid，d]）来标识。
3.2.2 成对缓存（GPU 内存）
为了支持细粒度交换，Wukong+G 进一步将每个段分成多个固定大小的块，并将它们存储到 GPU 内存的不连续块中。
Wukong+G 遵循 CPU 内存上的设计将键和值块缓存到 GPU 内存的不同区域中，即键缓存和值缓存。Wukong+G 使用一个简单的表来映射键和值块，而从键到值的链接变成了值块内的偏移量。与通常的缓存不同，链接的键和值块必须成对地在（GPU）缓存中进行交换，因此，Wukong+G 在成对缓存的键值块之间维护双向映射。
3.2.3 Look-ahead 替换策略
RDF 存储和缓存之间的块 ID 映射表记录了块是否已被缓存。在运行查询的三元组模式之前，所有键和值块都应预取到 GPU 内存中。
Wukong+G 提出了一个前瞻的基于 LRU 的替换策略来决定存储预取的键和值块的位置。
具体来说，Wukong+G 首选使用空闲块，然后选择不会被本次查询的后续三元组模式使用的块（前瞻），具有最高 LRU 得分。最差的选择是将被后续三元组模式使用的块，然后替换最远三元组模式的块。
3.3 分布式查询处理
3.3.0 概述
Wukong+G 通过差异化分区算法将 RDF 图分成多个不相交的分区，每台计算机托管一个 RDF 图分区，并在 CPU 和 GPU 上启动许多工作线程来处理并发的轻型和重型查询。不同机器上的 CPU 工作线程仅用于（轻型）查询处理之间的通信，GPU 工作线程也是如此，仅用于（重型）查询处理。
在 CPU 上的处理与 Wukong 相类似。
在 GPU 上的处理会更复杂一些，因为需要 CPU 代理线程的协助和 GPU RDF 缓存的维护。
异构 RDMA 通信
将 SPARQL 查询的查询元数据和中间结果传输过程解耦。
Wukong+G 使用本地 RDMA 在 CPU 之间发送元数据，如查询计划和当前步骤，并使用 GPUDirect RDMA 在 GPU 之间直接发送当前中间结果（历史表）。
3.3.1 执行模式：fork-join
分布式图形探索的两种执行模式，in-place 和 fork-join，用于分别迁移数据和执行。in-place 执行模式同步地利用单向 RDMA 读取直接从远程机器获取数据，而 fork-join 模式则异步地将查询计算分成多个子查询在远程机器上运行。
3.3.2 Communication flow
为了支持 fork-join 执行，子查询将带有其元数据（例如查询计划和当前步骤）和历史记录表（中间结果）发送到目标机器.
查询元数据将通过两个机器之间的单向 RDMA 操作在 CPU 内存之间传递。
GPUDirect 提供了一个机会，使 Wukong+G 能够直接将历史记录表从本地 GPU 内存写入到远程 GPU 和 CPU 内存。
四、结果如何
使用 LUBM 基准测试的实验结果表明，Wukong+G 在单个重型查询延迟方面比 Wukong 快 2.3 倍至 9.0 倍，并且在面对混合工作负载时，延迟和吞吐量提高了一个数量级以上。
* 概念补充
1. RDF 图
RDF 图（Resource Description Framework graph）是一种用于表示 Web 上的语义数据的图形结构。它由一组节点和边组成，其中节点表示资源或字面值，边表示这些节点之间的关系。RDF 图的核心思想是将信息表示为三元组，即主题、属性和对象，这样可以使不同的应用程序之间更容易地共享和理解数据。RDF 图广泛应用于语义 Web 和 Linked Data 等领域。
每个三元组可以被视为连接两个顶点（从主题到对象）的有向边（谓词）。
为了加速对 RDF 图的查询处理，添加了两种类型的索引，谓词和类型
2. SPARQL 查询
SPARQL（SPARQL Protocol and RDF Query Language）查询是一种用于检索和操作 RDF 图数据的查询语言。它类似于 SQL 查询语言，但是专门用于查询 RDF 图数据。SPARQL 查询可以用于查询和处理包含大量语义数据的知识库。
定义了关于图模式（GP）的查询。
3. RDMA
RDMA（Remote Direct Memory Access）是一种高效的网络传输技术，它使得主机之间可以直接访问对方内存中的数据，可以绕过远程 CPU 和操作系统，无需通过中间缓冲区进行数据传输和复制。RDMA 技术可以通过网络适配器和网络协议栈的支持，实现零拷贝、低延迟和高吞吐量的数据传输。
4. GPUDirect with RDMA
目前支持各种高效的通信，包括节点间、节点内和 GPU 间。
5. LUBM 基准测试
LUBM（Lehigh University Benchmark）基准测试是用于评估 RDF 系统性能的基准测试之一。它是一种人工生成的 RDF 数据集，用于模拟大规模的语义 Web 应用程序。LUBM 基准测试被广泛用于研究 RDF 系统的性能，特别是在大规模数据和查询负载下的性能表现。
6. 完整历史剪枝
由于通过图探索处理 RDF 查询需要遍历 RDF 图，因此裁剪不可行的路径对于提高性能至关重要。基本上有两种方法：
部分历史剪枝 ，通过继承先前遍历步骤的部分历史信息（中间结果）来裁剪后续遍历路径；
完整历史剪枝，通过传递所有先前遍历步骤的历史信息来进行剪枝。
7. PCIe
GPU 通过 PCIe（PCI Express）连接到 CPU，该连接具有不足的内存带宽（10GB / s）