编者按
本文系北京大学智能学院在读博士生胡琳所著，目前于 OceanBase 存储组实习，本篇也是 OceanBase 学术系列稿件第二篇。
「胡琳：北京大学智能学院在读博士生，博士期间在北京大学数据管理组从事GPU加速图算法的研究，在图算法加速领域取得了一定的成果，发表在SIGMOD等知名会议上，将继续在图计算领域努力探索。」
OceanBase 等以 LSM tree 为存储架构的数据库的 compaction 是一个比较耗时的操作，近年来 GPU 越来越多地被用在高性能计算领域。本文主要探讨 GPU 对基于 LSM tree 的数据库的性能提升。
希望阅读完本文，你可以有所收获，有什么疑问也可以在底部留言探讨，与作者一起探索。
GPU 是一种新硬件，相比较于 CPU，有较高的读写带宽和更强的并行能力，在很多领域都有非常好的应用。今天我们以 LSM-tree 上的 compaction 和 scan 为例，介绍 GPU 如何在加速数据库的操作中发挥作用。
GPU 的发展历程
图1：GPU 的发展
GPU 发展之初，是作为集成单元与其他硬件聚合在一起，也就是我们所熟知的显卡。1999 年，NVIDIA 发布 Geforce256，正式提出 GPU 概念；2006 年，NVIDIA 发布 GeForce8800，发布 CUDA，一种后面得到广泛使用的 GPU 编程语言；2011 年，NVIDIA 发布 Tesla 系列，形成计算产品线，GPU 开始更多地应用于科学计算领域。2011 年至今，GPU 快速发展，主要被 NVIDIA 和 AMD 所垄断，一些国产公司也开始研发一些替代品。
现在，GPU 在 CUDA 语言的基础上，提供了对于多种语言如 C++、python 的支持，并且有很多现成的算法库用来进行深度学习，矩阵乘法，通用计算等等。这些很大程度上降低了 GPU 编程的门槛，使得 GPU 的进一步广泛应用成为了可能。
目前 GPU 的主要应用有三个领域：
1） 通用高性能计算，例如自动驾驶、智慧医疗、生命科学、云计算、数据处理、金融等方面。
2） 人工智能计算。
3） 图形计算。
2021 图灵奖于近日揭晓，高性能计算先驱 Jack Dongarra 获奖，以表彰他在高性能计算领域所做出的突出贡献。他曾经说“未来的计算结构会是 CPU 和 GPU 的结合。”可见 GPU 正越来越受到大家的关注和认可。
提到 GPU 的发展，我们就不得不提 NVIDIA 一年一度的技术大会（GTC），每次都会发布最近的技术或产品。GTC 2022于3月22日召开，发布了 NVIDIA 的最新一代 GPU H100。它采用的是台积电 4nm 工艺， 拥有 800 亿晶体管；对比 A100，有 300%~600% 的性能提升；一块 H100 的 IO 带宽就是 40 terabyte 每秒。
“为了形象一点说明这是个什么数字，20 块英伟达 H100 带宽就相当于全球的互联网通信。”黄仁勋说道。
同时，NVIDIA 宣布基于 H100 芯片即将自建一个名叫 EoS 的超级计算机，其由 18 个 DGX POD 组成，一共 4608 个 H100 GPU，从 AI 计算的角度来看，EoS 输出 18.4 Exaflops，是当今全球第一超算富岳的四倍。NVIDIA 表示，阿里云、亚马逊 AWS、谷歌云和微软 Azure 等大公司都将采用英伟达的新芯片。此外，戴尔和惠普企业等计算机制造商将提供基于这些新芯片的计算机。除此之外，新一代的 H100 也提供了许多新特性，例如支持机密计算、加速动态编程算法、新一代 NVLink 等等。
可以看出 H100 相比较于上一代的 A100，有巨大的性能优势，是 NVIDIA 发布的又一个里程碑式的产品。
近年来，国产 GPU 也有了长足的发展。3 月 30 日下午，北京 GPU 创企摩尔线程推出基于架构 MUSA 的首款 GPU 苏堤，以及基于苏堤的首款台式机显卡 MTT S60、首款服务器产品 MTT S2000。摩尔线程创始人兼 CEO 张建中为前英伟达全球副总裁、中国区总经理。苏堤是摩尔线程的全功能 GPU，有图形、智能多媒体、AI、物理四大引擎，在此之上有各种编译工具及平台，并支持 OpenCL、SYCL、CUDA、Vulkan、DirectX、OpenGL/GLES 等主流编程接口，还有针对具体应用的各类行业解决方案。特别地，基于苏堤的首款台式机显卡 MTT S60，据张建中介绍，是第一款能打英雄联盟游戏的国产显卡，支持所有主流国产 PC 操作系统。
苏堤对于 GPU 全功能的实现，对于各种主流编程接口的支持，使得它在各种服务器或数据中心中有一席之地；而对于主流游戏的支持，也使得它出现在个人 PC 上成为可能。总之，这是国产 GPU 发展的一个重要里程碑，虽然比 NVIDIA 的旗舰 GPU 还有一些性能差距，但是国产 GPU 首次发布出来，并且在商业市场上有一定的竞争力。
图2：摩尔线程发布会现场
GPU 架构的简单介绍
图3：H100 的架构示意图
图 3 是 H100 的架构图，可以看出，GPU 的架构已经非常复杂，包含了非常多的并行单元和访存控制单元。为了方便介绍，我们还是采用更加抽象和简单的架构图来进行介绍，如图 4 所示。
图4：GPU 和 CPU 的架构比较
从图 4 中可以看出，GPU 与 CPU 相比，有非常多的计算单元，但是每个计算单元的逻辑控制器和本地 cache 都比 CPU 少。通常这会导致一个结论：CPU 适合处理逻辑复杂的任务，GPU适合处理简单但是并行度高的任务。关于这个结论，我们在后文会给出更进一步的解释。同时 GPU 的内存带宽也比 CPU 高的多，一般 CPU 的内存带宽在 100GB/s 左右，而 GPU 的内存带宽可以达到 CPU 的 5～8 倍。可见 GPU 相较于 CPU，有巨大的硬件优势，但是 GPU 的硬件架构有自己的特性，要充分发挥出性能优势的条件也更严苛。
图5：硬件层面和软件层面的 GPU 架构
接下来我们从硬件架构和软件层面对 GPU 进行介绍，如图 5 所示。硬件上，一个GPU 有多个stream multiprocessor（SM），每个 SM 上有许多核，并且拥有自己的 cache。所有的SM都可以访问全局内存（global memory），global memory 通过 PCIe 总线和 CPU 相连。通过 PCIe 方式进行的CPU和GPU的通信带宽并不高，只有十几 GB/s 的速度，但是通过 NVLink 相连的方式，能够实现接近十倍的数据传输带宽。软件层面，程序员每次启动的 GPU 上的核函数称为一个grid，其中有许多的 block，block 可以被分派到 SM 上运行。每个 block 中又有许多 warp。Warp 是 GPU 上线程并行和访存的基本单位，其中的线程是按照单指令多线程（Single instruction multiple threads）的形式运行的，也就是说，warp 内部线程的中的分支或者循环结构会导致并行度下降。同时 warp 也是基本的访存单元，warp 里的线程的访存任务都是通过 warp 统一完成的。
图6：warp 中线程访存的几种方式
Warp 每次取回一个 cacheline 大小的数据（通常是 128Byte）。考虑图 6 中的访存方式，当一个 warp 中的四个线程访问的都是连续并且相邻的地址时，所有的访存请求都可以在一次内存访问操作中满足，称为 coalesced memory access；如果线程访问的地址空间是相邻并且不连续的，就需要更多的访存操作才能将所有需要的数据取回来，也就是图中的 strided memory access；最后如果所有的线程随机访问，那么需要很多次的访存操作才能满足所有的请求，并且取回来的数据中有效的数据非常少。
Warp 的并行和访存特性，决定了 GPU 更加适合处理规则的，简单的任务，也是“GPU 不适合处理复杂逻辑”的原因。因而我们在算法设计的时候，必须注意到这一点，充分考 warp 的特性，尽量避免线程发散，尽量让线程进行合并访存，这是 GPU 上进行程序设计的基本原则。
两个 GPU 上的工作
接下来我们将通过 levelDB 和 RocksDB 上的两个例子，介绍 GPU 在基于 LSM-tree 的数据库上可以做什么。
LUDA--利用 GPU 加速 LSM-tree 的 compaction 操作[1]
1. 动机
图7：rocksDB 在不同 CPU overhead 下的性能
Compaction 是 RocksDB 中非常重要的操作，可以减少读放大；数据库系统本身对于 CPU 有很高的占用率，而 compaction 操作也是计算密集型操作，导致对于计算资源的竞争十分激烈。例如在图 7 中，当数据库本身对于 CPU 的占用比较高的时候，稍微增加一点 compaction 的工作负载就会导致非常所需要的时间急剧增加。我们需要一个有效的方式，减少计算资源的竞争。
2. compaction 的实现
图8：CPU 上 compaction 操作流程
图 8 展示了常规 compaction 操作的流程图。CPU 从磁盘上读取出相应的 SSTable，经过解码排序编码的方式，将 LSM-Tree 的不同层合并，然后再写回到磁盘上。
图9：使用 GPU 加速的 compaction 流程
在 LUDA 的设计中，将原本计算操作比较密集的部分-对于 SSTable 的编码和解码部分的工作交给了 GPU，基本流程如上。在 LUDA 的设计中，GPU 对于 SSTable 的访问需要经过 CPU 作为中介进行数据的传输。同时对于 SSTable 进行排序和多版本信息管理的操作放在了 CPU 上，这是因为多个 SSTable 之间可能存在范围交叠，这部分任务如果放在 GPU 上处理会导致 CPU 和 GPU 之间大量的数据传输，可能带来非常严重的性能下降。
GPU 在进行数据的编码和解码的同时，也会进行其他一些计算密集型的操作，例如构建 bloom filter 和 checksum 检查等等，有效地减少了 GPU 的工作量。
在图 9 中的步骤二和步骤四中，也就是 GPU 和 CPU 之间进行数据传输时，采用的是异步的数据传输，可以有效地提高计算和数据传输的并行性，掩盖数据传输延迟。
3. 实验
图10：不同 CPU 负载下的吞吐量
图11：不同 CPU 负载下的运行时间
最终 LUDA 实现了比较好的加速效果，相比较于单纯地使用 CPU，实现了 2 倍以上的 compaction 加速和 2 倍以上的数据吞吐量。
OurRocks：利用 GPU 加速 LSM-tree 的 SCAN 操作[2]
1. 动机
基于 NVMe 协议的 SSD 最高能够实现GB/s的数据传输带宽，但是目前基于 CPU 的 LSM-tree 数据库对于 SSD 的带宽应用非常有限，哪怕考虑上多线程技术，AVX 技术，异步 IO 等等，如图 11 所示，哪怕是在 8-client 的环境下，在实际业务场景中 SSD 的真实带宽也仅仅有十几 GB/s 或者几十 GB/s，仅仅是理论 SSD 最高带宽的几十分之一。
图12：MyRocks 处理分析性查询时 NVMe 的实际带宽
同时，在数据库的扫描操作中，数据从 SSD 拿入 CPU 之后，CPU 还会消耗大量的时间在计算上，如图 13 所示，在不同 client 数目下，系统空间和用户空间的 CPU 运行占据了绝大多数的时间，花费在系统 IO上的时间是很少的。这体现了对于 CPU 计算任务卸载的需求，和提升 SSD 实际使用带宽的需求。
图13：Myrocks 中处理每个分析性查询时 CPU 每个核的利用率
同时，利用 CPU 作为 GPU 和磁盘之间的数据传输跳板会带来很严重的性能损失，参见 LUDA 的实现，带来了很多不必要的数据传输开销。
所以 MyRocks 想利用 GPU 和 SSD 之间直接进行数据通信的特性，辅助 CPU 进行 SCAN 操作，减少 CPU 的访存开销和计算代价。
2. 背景知识
LSM-tree 中的读操作，由于 LSM-tree 本身的特性，会带来额外的代价，称为读放大。
NVIDIA GPUDirect RDMA（remote direct memory access）为 GPU 和其他第三方设备（例如网卡，SSD 等）的直接数据传输提供了可能，而不是仅仅通过 PCIe 总线，这大大减轻了 CPU 的数据传输负担。
图14：DMA 传输的吞吐量
如图 14 所示，通过对于 GPU 和 SSD 之间直接进行数据传输的带宽测试，发现当数据传输的大小达到一定水平时，数据的传输带宽可以稳定在一个水平，这远远高于数据库实际业务场景中的 SSD 和 CPU 之间的数据传输带宽。
3. 利用过滤下压使 GPU 进行预扫描
图15：考虑查询下压的架构图
原本的 LSM-tree 数据库包括 SQL 执行引擎和数据存储引擎，MyRocks 增加了一个 GPU manager，利用 GPU 进行计算任务的部分预计算。具体过程如下：SQL 执行引擎首先对查询语句解析，将其中的谓词（过滤条件）传给 GPU Manager；随后数据从 SSD 传输到 CPU，再通过异步方式传输 GPU；GPU 有了谓词和数据，预先进行数据的筛选，将通过筛选后有用的数据块的位置记录下来，传给 CPU；这样 CPU 就可以省去大量的 SCAN 操作，直接处理 GPU 传输上来的过滤之后的数据，大大减少了 CPU 的工作量。
4. 利用 DMA（Direct memory access）加快 GPU 和 SSD 之间的数据传输
图16：考虑查询下压和GPU DMA的架构图
上一个设计中的问题是 GPU 仍然通过 CPU 获取 SSD 的数据，这样一方面导致不必要的数据传输延迟，另一方面也增加了 CPU 的负担。于是在考虑了 GPU DMA的特性之后，将原来的架构修改如上。原来通过 CPU 传输到 GPU 的数据，不再是大块的数据，而是对于数据块进行描述的元数据，记录数据块的位置和大小等信息，这部分数据的大小相比较于原来数据的大小可以忽略不计。然后 GPU 可以直接与 SSD 进行数据的通信，对得到的数据进行扫描。
可以看出 DMA 的使用大大减少了数据传输的代价，也解放了 CPU。
5. 实验
图17: 在YCSB数据集上的实验结果
在 TPC-H 数据集上执行带有 SCAN 操作的典型查询，性能比原来提升了 6.2 倍。
图18：TPC-H的scan操作中各个时间阶段所占据的比例
从整体运行时间中各个阶段所占据的比例来看，使用 DMA 技术加速的 OurRocks 也带来了很明显的性能提升，并且 CPU 的扫描时间和数据传输时间都大大降低。
总结与展望
我们介绍了如何利用 GPU 高带宽和高并行的特点，帮助减少 CPU 或者内存的压力，从而实现性能提升的例子。原本 GPU 更加适合计算密集的 workload，但是 GPU direct RDMA 的引入，使得 GPU 在访存型任务上也获得了很大的发挥空间，很大程度上缓解了 CPU 的数据传输压力。但是，卸载给 GPU 的工作做好能够完全跟 CPU 解耦，否则任务运行过程中依赖 CPU 实施产生的数据等会导致性能大幅降低。
GPU 在各种对性能有需求的场景下的使用是未来的发展趋势。在基于 LSM-tree 数据库的优化上也有很多潜在的方向。例如利用 DMA 对于 LUDA 的改进，encoding 过程和 decoding 过程摆脱对于内存的依赖；在 compaction 过程的 encoding 中加一些计算密集型任务，对每个数据块中数据特性进行预计算，方便后续查询时的快速获取；GPU 的使用给很多之前被有缺陷的数据库架构设计也带来了一些新的可能，例如 Wisckey[3] 提出 KV 分离的设计思路，可以大大减少合并过程中的写放大，但是会带来范围查询性能下降，并且 GC 过程中存在大量点查的问题，但是合并和 GC 都是不在数据库查询相应路径上的，GPU 可以作为专门的合并或者 GC 单元。
*参考文献：
[1] LUDA: Boost LSM- Key Value Store Compactions with GPUs, arXiv Peng Xu et.al
[2] OurRocks: Offloading Disk Scan Directly to GPU in Write-Optimized Database System，Won Gi Choi, IEEE TRANSACTIONS ON COMPUTERS, 2021
[3] WiscKey: Separating Keys from Values in SSD-conscious Storage, Lanyue Lu et.al , FAST 2016
