共计 6393 个字符，预计需要花费 16 分钟才能阅读完成。
本文系北京大学智能学院在读博士生胡琳所著，目前于 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]
- 动机
图 7：rocksDB 在不同 CPU overhead 下的性能
Compaction 是 RocksDB 中十分重要的操作，能够缩小读放大；数据库系统自身对于 CPU 有很高的占用率，而 compaction 操作也是计算密集型操作，导致对于计算资源的竞争十分激烈。例如在图 7 中，当数据库自身对于 CPU 的占用比拟高的时候，略微减少一点 compaction 的工作负载就会导致十分所须要的工夫急剧减少。咱们须要一个无效的形式，缩小计算资源的竞争。
- 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 之间进行数据传输时，采纳的是异步的数据传输，能够无效地进步计算和数据传输的并行性，覆盖数据传输提早。
- 试验
图 10：不同 CPU 负载下的吞吐量
图 11：不同 CPU 负载下的运行工夫
最终 LUDA 实现了比拟好的减速成果，相比拟于单纯地应用 CPU，实现了 2 倍以上的 compaction 减速和 2 倍以上的数据吞吐量。
OurRocks：利用 GPU 减速 LSM-tree 的 SCAN 操作[2]
- 动机
基于 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 的访存开销和计算代价。
- 背景常识
LSM-tree 中的读操作，因为 LSM-tree 自身的个性，会带来额定的代价，称为读放大。
NVIDIA GPUDirect RDMA（remote direct memory access）为 GPU 和其余第三方设施（例如网卡，SSD 等）的间接数据传输提供了可能，而不是仅仅通过 PCIe 总线，这大大加重了 CPU 的数据传输累赘。
图 14：DMA 传输的吞吐量
如图 14 所示，通过对于 GPU 和 SSD 之间间接进行数据传输的带宽测试，发现当数据传输的大小达到肯定程度时，数据的传输带宽能够稳固在一个程度，这远远高于数据库理论业务场景中的 SSD 和 CPU 之间的数据传输带宽。
- 利用过滤下压使 GPU 进行预扫描
图 15：思考查问下压的架构图
本来的 LSM-tree 数据库包含 SQL 执行引擎和数据存储引擎，MyRocks 减少了一个 GPU manager，利用 GPU 进行计算工作的局部预计算。具体过程如下：SQL 执行引擎首先对查问语句解析，将其中的谓词（过滤条件）传给 GPU Manager；随后数据从 SSD 传输到 CPU，再通过异步形式传输 GPU；GPU 有了谓词和数据，事后进行数据的筛选，将通过筛选后有用的数据块的地位记录下来，传给 CPU；这样 CPU 就能够省去大量的 SCAN 操作，间接解决 GPU 传输上来的过滤之后的数据，大大减少了 CPU 的工作量。
- 利用 DMA（Direct memory access）放慢 GPU 和 SSD 之间的数据传输
图 16：思考查问下压和 GPU DMA 的架构图
上一个设计中的问题是 GPU 依然通过 CPU 获取 SSD 的数据，这样一方面导致不必要的数据传输提早，另一方面也减少了 CPU 的累赘。于是在思考了 GPU DMA 的个性之后，将原来的架构批改如上。原来通过 CPU 传输到 GPU 的数据，不再是大块的数据，而是对于数据块进行形容的元数据，记录数据块的地位和大小等信息，这部分数据的大小相比拟于原来数据的大小能够忽略不计。而后 GPU 能够间接与 SSD 进行数据的通信，对失去的数据进行扫描。
能够看出 DMA 的应用大大减少了数据传输的代价，也解放了 CPU。
- 试验
图 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
公布于 2022-04-27 21:03
