摘要
基于闪存的NVMe SSD具有低廉的价格并提供高吞吐量。将多个这些设备整合到单个服务器中，可以实现高达1000万IOPS。然而，我们的实验结果表明，现有的数据库系统和存储引擎仅能发挥这一性能潜力的一小部分。在本研究中，我们展示了通过I/O优化的存储引擎设计可以减小硬件和软件之间性能差距的可能性。在内存资源严重有限的情况下，数据集大小达到主内存的10倍时，我们的系统能够每秒处理超过100万个TPC-C事务。
1 引言
闪存性能。在过去的十年中，闪存SSD已经取代了传统硬盘，成为操作型数据库系统的默认持久存储介质。最近，SATA接口已被PCIe/NVMe所取代，释放了以前无法预见的存储吞吐量：使用四个PCIe 4.0通道，单个SSD可以实现超过100万的随机IOPS和7 GB/s的带宽。由于现代的商用服务器每个插槽最多有128个PCIe通道，一个单插槽服务器可以轻松承载8个（或更多）SSD，实现全带宽。不断增加存储带宽的趋势将继续：支持PCIe 5.0的服务器已经发布，相应的SSD每个设备的带宽已经宣布为12 GB/s。这意味着NVMe SSD阵列正在接近DRAM的带宽。
闪存容量。SSD不仅具有高吞吐量，而且价格相对较低：经过十年的DRAM价格停滞和闪存价格迅速下降后，企业级SSD的成本已低于每TB 200美元，约为DRAM的10-50倍的便宜。我们可以通过一个示例来说明这一点，假设我们有总共15,000美元的服务器预算。用一半的预算，可以配置一个合理的服务器，例如64核CPU，512 GB内存和快速网络。剩下的预算可以用于额外的DDR4内存模块或PCIe 4.0 NVMe SSD，得到以下两种配置：
这两种配置说明了将更多的资金用于SSD而不是内存将导致更大的存储容量（32 TB而不是2.5 TB）。这一观察也被公有云服务商所注意到：AWS提供了带有8个（i3en）NVMe闪存SSD的实例，而Azure则提供了带有10个（Lsv2）的实例。鉴于像Optane这样的替代存储技术没有取得商业成功，因此被终止，我们认为闪存将继续是以经济有效的方式存储大型数据集的唯一可行选择。
现有系统的性能差距。就其基本架构而言，用于闪存的数据库管理系统（DBMS）类似于基于磁盘的设计：它们依赖于缓冲池缓存、基于页的存储以及用于索引的B树或LSM树。包括RocksDB [36]和我们的LeanStore [1, 26]系统在内的多个现代存储引擎明确宣称其已经针对闪存存储进行了优化。然而，如图1所示，现有的内存不足系统无法充分利用现代NVMe阵列的性能。在实验中，我们在一台64核的AMD服务器上使用8个三星PM1733 SSD进行了一项简单的随机读基准性能测试，我们测试了5个系统的性能。根据其规格，这些SSD中的每个SSD可以达到150万随机4 KB读IOPS，因此预期可以在这个简单的工作负载下实现8×1.5M=12M的查找/秒。事实上，我们发现最佳系统只能实现360万次的查找/秒，存在3.5倍的差距。对于更复杂且写密集的TPC-C基准测试，我们发现现代NVMe SSD可以实现的性能与现有系统实现的性能之间存在更大的性能差距，高达4.7倍。正如本文所展示的，充分利用闪存存储需要仔细协同设计存储引擎和闪存NVMe SSD。
研究问题与论文大纲，我们试图解决的高层次问题可以分为以下研究问题：
- Q1：NVMe SSD阵列能否实现硬件规格中所承诺的性能？
- Q2：哪种I/O API（pread/pwrite，libaio，io_uring）最适合？是否需要依赖内核绕行技术（SPDK）？
- Q3：存储引擎应该采用何种页面大小，以在最小化I/O放大的同时实现出色的性能？
- Q4：如何管理需要高度SSD吞吐的并行性？
- Q5：如何使存储引擎运行速度足够快，以能够处理数千万的IOPS？
- Q6：是应该由专用I/O线程执行I/O，还是由每个工作线程执行？
为了回答这些问题，我们首先在第2节进行了有关NVMe闪存存储硬件特性的实验研究。基于这些研究结果，我们获得了设计高性能存储引擎的见解。第3节随后提出了一种能够充分利用NVMe阵列的I/O后端的蓝图。
系统集成和技术
我们已将本文中提出的技术集成到LeanStore中，这是一个开源存储引擎原型。LeanStore专为SSD设计，并已采用了早期研究[13]中提到的与I/O相关的重要优化，包括快速缓冲池、绕过文件系统使用O_DIRECT以及fsync批处理。这个基线版本足以充分利用单个NVMe SSD，但正如图1所示，不足以充分利用8个NVMe SSD。
前所未有的性能
LeanStore的新版本是第一个能够完全弥补这一性能差距的系统。尽管我们的技术相对较为精心设计，但它们共同实现了一个实用的系统设计，具有少量配置参数，能够实现前所未有的内存外性能。我们还认为本文中的发现和技术适用于大多数其他存储引擎和数据库系统。
结果
在第4节中，我们对我们的设计进行了评估。在一台具有64个核心和8个SSD的服务器上，最终的系统确实能够实现每秒1250万次的随机查找工作负载。在更具挑战性的TPC-C基准测试中，LeanStore在具有400 GB缓冲池和4 TB数据集的情况下每秒执行100万次TPC-C事务。对于20 TB数据集，我们仍然能够实现40万次事务/秒。对于所有工作负载，如果有足够的并发用户请求，机器将成为I/O限制，这正如我们所预期的那样，对于数据集远远大于缓冲池的工作负载来说是合理的。
2 现代NVMe存储的性能
在本节中，我们将呈现一系列微基准测试的结果，这些测试为我们提供了充分利用现代存储的必要背景信息。所有实验都在一台配备了8个3.8TB的三星PM1733 SSD的64核AMD Zen 4服务器上进行。关于实验硬件和软件设置的详细信息可以在第4.1节中找到。
2.1 SSD可扩展性
SSD可扩展性。根据硬件规格表，我们的三星PM1733 SSD能够执行150次随机4 KB读取IOPS。因此，使用8个SSD，我们应该能够达到惊人的1200万IOPS。如图2所示，吞吐量确实随着所使用的SSD数量的增加而完美扩展。实际上，我们实际实现了略高于预期的1250万IOPS，或每个SSD 156万IOPS。
读/写混合。需要注意事务性工作负载通常是写密集型的，而且众所周知，SSD的读/写速度不对称。如图2b所示，在空的SSD上进行随机写时，我们的硬件设置能够实现470万IOPS。值得注意的是，SSD的写性能会受到SSD的内部状态和写持续时间的影响。在SSD已满且写持续时间较长的最坏情况下，吞吐量会较低。规格表指定了每个SSD的最坏情况下的随机写吞吐量为13.5万 IOPS。对于OLTP系统，混合读/写工作负载更为常见。如图2b所示，我们以10%（25%）的写比例测得890万（700万）IOPS。这些微基准测试结果表明，现代NVMe存储为通常需要进行大量随机I/O操作的事务系统提供了出色的基础。
2.2 4KB页面的选择
页面大小的权衡。与持久内存的字节寻址不同，闪存的访问是以页面为单位进行的。许多数据库系统使用较大的页面大小，例如8 KB（PostgreSQL，SQL Server，Shore-MT），16 KB（MySQL，LeanStore），甚至32 KB（WiredTiger）作为其默认值。在LeanStore中，我们注意到对于内存工作负载，较大的页面大小通常可以提高性能，这也是我们最初选择16 KB的原因[26]。较大页面大小的第二个好处是可以减少缓冲池中不同条目的数量，因此减少了缓存管理的开销。
然而，较大页面的一个主要缺点是在内存不足的工作负载下可能出现I/O放大。例如，使用16 KB页面，读或写100字节的记录将导致I/O放大为160倍。较小的4 KB页面大小将I/O放大减少了4倍。
选择较小的页面（但不要太小）。对于数据中心级别的SSD，我们发现页面大小的最佳选择是4 KB，因为它允许获得最高的随机读性能和最低的延迟。如图3所示，使用4 KB页面和随机读可以实现接近全带宽（6 GB/s）的性能。这只比使用较大页面（或顺序访问）可以达到的6.5 GB/s的最大带宽慢了8%。从图3中不同页面大小的延迟来看，可以观察到延迟通常随页面大小的增加而增加，并在4 KB时达到最小值。从技术上讲，NVMe允许更小的页面，甚至可以降至512字节。从写放大的角度来看，这会更好，但我们的结果表明，使用小于4 KB的页面会显著降低性能。实际上，较小的页面大小实际上会导致我们的SSD上的更低IOPS和延迟，如图3所示。这是由于闪存转换层中的更高开销以及闪存硬件内部未经过优化以处理512字节页面的事实所致。我们认为，较低的延迟和I/O放大所带来的优势使4 KB页面成为优化内存外性能的系统的最佳选择。然而，要在性能方面从如此小的页面大小中受益，DBMS必须能够处理由此产生的高缓冲池和I/O管理工作。实际上，大多数DBMS将不仅从使用较小的页面中受益，因为I/O吞吐量不是限制因素（参见第4.2节）。
2.3 SSD并行性
SSD并行性。在内部，SSD是高度并行的设备，具有多个通道连接到独立的闪存芯片。将足够的I/O请求传递给SSD可能会很困难，因为要实现高性能，需要大量同时的请求。闪存的随机读延迟约为100微秒，比磁盘快100倍，但仍然比DRAM慢1000倍。通过同步访问（即在前一个I/O请求完成后才发送新的I/O请求），这将导致仅有1万 IOPS（或40MB/s）的微弱性能。因此，要从SSD获得良好的吞吐量，必须通过异步调度大量并发的I/O请求来利用其内部并行性。图4显示了I/O深度与整体吞吐量之间的关系，即在所有8个SSD上同时挂起的I/O请求数量。我们可以看到，大约需要1000个并发的I/O请求，即每个设备超过100个，才能获得良好的性能，而需要3000个才能充分饱和系统。利用NVMe阵列的数据库系统面临的主要挑战之一是管理如此大量的I/O请求。
2.4 I/O接口
现代操作系统提供了多种用于存储I/O的接口。在这里，我们讨论了Linux上最常见的I/O库。最终，所有接口都会对NVMe SSD执行相同的操作：接收I/O请求并将其放入主机系统用于与SSD通信的NVMe提交队列。当SSD完成任何请求时，它将写完成事件到完成队列，并如果使用中断，则通知主机。这些库在请求的提交方式以及如何获取已完成的操作方面有所不同。
阻塞POSIX接口。在Linux上进行I/O的经典和最常见方式是使用像pread和pwrite这样的POSIX系统调用。通常，POSIX用于文件操作的调用以阻塞方式使用，即一次只提交一个I/O请求。然后内核将会阻塞用户线程，直到该请求由驱动处理。如图5a所示。
libaio：传统的异步接口。libaio是一种异步I/O接口，允许一次使用一个系统调用提交多个请求。这可以节省用户模式和内核模式之间的上下文切换，并允许单个线程同时执行多个I/O操作。如图5b所示，I/O请求以非阻塞方式通过io_submit()提交，该方法立即返回，并且程序必须通过get_events()进行完成事件的轮询。
io_uring：现代的异步接口。io_uring [38]是libaio的指定后继者。io_uring实现了一种新的通用异步接口，可用于存储，也可用于网络。如图5c所示，它基于内核和用户态之间的共享队列。多个请求可以添加到提交队列中，并通过单个io_uring_enter()系统调用，内核可以得知可用请求。在内核内部，I/O请求实际上会经过与其他内核接口相同的抽象层（文件系统，缓存，块设备层等）。在经过所有这些内核层之后，请求最终会进入一个NVMe提交队列。Linux还实现了提交队列轮询模式（SQPOLL），在这种模式下，内核会生成内核工作线程（在图中标有*号）来轮询提交队列。在这种模式下，除了需要额外的内核工作线程外，不需要系统调用。
轮询I/O完成。到目前为止，所有讨论的接口中，通知主机关于已完成的I/O事件的默认方式是硬件中断。使用io_uring，可以禁用中断（IOPOLL）。在这种模式下，应用程序必须从完成队列中轮询完成事件（在图中标有**号）。在高IOPS的情况下，避免中断可以减少延迟和CPU开销。使用I/O轮询时，io_uring_enter()系统调用也用于在NVMe完成队列上轮询。当设置SQPOLL时，I/O轮询由内核工作线程处理，可以直接从用户态中获取完成，而不需要系统调用。
SPDK中的用户态I/O。英特尔的存储性能开发工具包（SPDK）是用于高性能存储应用程序的一组库和工具[39]。特别是SPDK的NVMe驱动程序，它是用于NVMe SSD的用户态驱动程序，对我们而言很重要。如图5d所示，要与NVMe SSD通信，SPDK直接在用户态分配NVMe队列对（用于提交和完成）。因此，提交I/O请求就像将请求写内存中的环形缓冲区并通过另一个写操作通知SSD有新请求一样简单。SPDK不支持基于中断的I/O，完成必须始终从NVMe完成队列中轮询。SPDK完全绕过了操作系统内核，包括块设备层、文件系统和页面缓存。
2.5 CPU资源短缺
可用的CPU周期。在第2.1节的实验中，我们发现现代存储硬件能够实现数千万IOPS。管理如此多的请求成为数据库系统的重要任务，可以占用大量的CPU时间。为了了解处理1200万IOPS的可用CPU预算，考虑以下简单的计算：使用我们的AMD CPU规格，我们得到每个I/O操作的CPU预算为13,000个周期（2.5 GHz × 64核心 / 1200万IOPS）。
I/O库的CPU影响。在图6所示的微基准中，我们测量了使用不同数量线程时可达到的吞吐量。图中显示，使用libaio和io_uring（基于中断的方式），无法达到完全带宽。使用32个线程时，最大吞吐量为1000万 IOPS，大部分时间都花在内核中。使用io_uring的轮询模式，结果更好：使用16个线程，可以接近完整的吞吐量。请注意，为了实现这些数字，我们必须禁用大部分操作系统功能，如文件系统、RAID和操作系统页面缓存[13]。在微基准中，SPDK取得了更好的结果，只需三个线程就可以达到完整的带宽。然而，使用用户态I/O对用户和I/O后端的设计产生了重大影响，我们将在本文后面讨论。
fio可能成为瓶颈。图6中所示的实验是使用自定义基准测试工具进行测量的。我们还使用标准的I/O基准测试工具fio [2] 执行了相同的基准测试，并出奇地获得了更差的结果。特别是，fio的基于中断的I/O实现无法实现随机4 KB读的完整带宽。一个专门的I/O基准测试工具可能成为一个瓶颈，这表明在成熟的数据库系统中实现高I/O吞吐量是困难的。
每个周期都重要。我们的实验表明，除非使用SPDK（这并不总是一个实际选择），否则大约一半可用的CPU核心会被操作系统消耗，用于提交和获取I/O请求。回到我们的简单计算，这让我们只有6500个周期用于所有剩下的DBMS工作。这包括查询处理工作、索引遍历、并发控制、日志记录、缓冲区管理器开销、页面淘汰和调度。请注意，我们的计算假定所有DBMS组件都具有完美的多核可扩展性，即，如果可扩展性不完美，预算将会减少。
2.6 高性能存储的影响
性能差距。我们的高性能存储引擎LeanStore专门为NVMe SSD设计。与旧系统不同，它不受CPU限制，并在多核CPU上具有良好的可扩展性。然而，正如图1所示，在应该能够实现1250万IOPS的情况下，它只能实现360万IOPS。本节的实验使我们能够准确找出这个3.5倍的性能差距的原因。
并行性不足。LeanStore将页面提供程序和工作线程区分开来。页面提供程序线程负责淘汰策略和写入脏页。为了在大型内存外工作负载中获得良好的性能，需要多个页面提供程序线程以找到足够多的需要淘汰的冷页面。工作线程负责处理用户查询，每个查询在自己的操作系统线程中独占运行。由于工作线程使用同步读操作（pread）来处理缓冲管理器页面故障，因此每个请求都需要切换到内核。线程将被阻塞，直到I/O请求完成。正如我们所看到的，SSD需要大量并发I/O操作来饱和 – 因此需要数千个工作线程。为了实现图1中显示的性能，必须将32个页面提供程序线程与工作线程隔离开，以获取足够的CPU时间，避免成为瓶颈。页面提供程序线程被固定在CPU核心上，而工作线程可以由内核按计划自由使用所有其他CPU核心。
过度订阅问题。这意味着数千个工作线程现在在竞争剩余的CPU核心，这会导致非常高的上下文切换开销。在启动500-1000个线程后，所有CPU核心都以100%的负载运行，大部分时间都花在内核中。在这种高度过度订阅的情况下运行系统既不高效也不稳定。
总结。本节的实验表明，现代NVMe存储提供了巨大的性能潜力。然而，即使在微基准测试中也很难接近这些硬件极限（正如fio瓶颈所证明的那样），而在成熟的存储引擎中则是一个重大挑战。我们还发现4 KB页面在随机IOPS、吞吐量、延迟和I/O增强之间提供了最佳的权衡。然而，如此小的页面大小会更加加重I/O后端的负担。
3 如何利用NVMe存储：面向I/O优化的存储引擎设计
利用NVMe阵列。在本节中，我们将描述一种能够充分发挥现代存储设备潜力的存储引擎设计。我们的出发点是LeanStore的基线版本。正如图1所示，这个版本的LeanStore比其他系统更快，但无法充分利用NVMe阵列。需要注意的是，仅仅切换到4KB页面和轮询I/O本身不会带来太大改善，因为会立即遇到软件瓶颈。高性能的内存外工作需要整个系统的改进。
并行性是问题的核心。在较高层次上，我们面临的主要挑战是现代硬件的并行性：首先，我们在请求级别具有并行性，这可以直接来自用户查询或来自DBMS本身（例如，通过查询内部并行性或预取）。其次，现代服务器具有数十个或数百个CPU核心，但不是数千个。第三，我们在任何时刻都有1000多个未完成的I/O操作，以保持SSD处于繁忙状态。
3.1 设计概述和大纲
解决方案是在系统的每个部分都充分采用并行性。图7显示了我们系统的高层视图以及它需要处理的并行性。从图中的左到右，我们可以看到一切都始于并发请求。为了管理所有这些请求，我们采用了由DBMS在用户态调度的协同多任务处理，如第3.2节所述。所有这些I/O请求最终导致对空闲页面的极高需求（例如，在图中为800万/秒）。这种需求必须由高效的页面替换算法和异步脏页写入来满足。在第3.3节中，我们认为这些消耗大量CPU的任务应该集成到工作线程中。最后，I/O后端将DBMS与存储硬件连接起来，使用了前面介绍的I/O库中的一种。第3.4节讨论了如何将工作请求连接到硬件的几种模型。由于整体的CPU预算有限，所涉及的每个组件都必须进行深度优化，并以可扩展的方式实现。这些优化在第3.5节中进行了描述。
3.2 由DBMS管理的多任务处理
高度超额订阅的问题。大多数数据库系统在独立线程中运行查询，并使用同步I/O请求（即pread）来处理页面故障。在这种设计中，为了保持SSD的繁忙状态，必须同时运行超过1000个线程，仅供用户请求使用。如果查询占用大量CPU时间，将生成更少的I/O请求，因此需要更多线程。即使大型服务器也没有数千个核心，这意味着同步I/O会导致极端的超额订阅和由于上下文切换开销而导致性能不佳。
轻量级任务。为了避免超额订阅，我们使用由数据库系统在用户态管理的轻量级协同线程。这减少了上下文切换开销，并允许系统在没有内核干扰的情况下完全控制调度。在这种设计中，如图8所示，系统启动了与系统中可用的硬件核心数相同数量的工作线程。其中每个工作线程运行一个执行这些轻量级线程的DBMS内部调度程序，我们称之为任务。为了实现用户态任务切换，我们使用了Boost上下文库[22]，具体是fcontext。因此，任务切换仅花费约20个CPU周期，而内核上下文切换需要几千个CPU周期。这使得在调用堆栈深处进行廉价和频繁的上下文切换成为可能，并且相对容易将现有代码库移植到这种新设计中。
协同多任务处理。从概念上讲，Boost上下文是不可抢占的用户态线程。因此，任务需要定期将控制权返回给调度程序。在我们的协同多任务处理设计中，当用户查询遇到页面故障，耗尽空闲页面或用户任务完成时，会发生这种情况。此外，为防止工作线程因锁定而陷入停滞状态，我们还修改了所有锁定，以最终将控制权归还给调度程序。
非阻塞I/O。使用不可抢占任务意味着不能使用阻塞I/O请求（例如pread），因为它会阻止整个工作线程。相反，我们采用一种设计，其中工作线程使用非阻塞I/O接口（如libaio、io_uring或SPDK）以异步方式提交请求。当任务遇到页面故障时，I/O请求将被提交到I/O后端，并相应的任务将执行控制权返回给调度程序。因此，每个工作线程可以具有多个未完成的I/O请求。当I/O完成时，工作线程将（最终）跳到相应的任务。这使得作为轻量级用户态线程同时运行数千个查询成为可行的。
3.3 通过系统任务进行后台工作
页面淘汰至关重要。数据库系统不仅运行用户查询，还执行性能关键的任务，如页面淘汰。一旦系统由于页面替换算法太慢而耗尽了空闲页面，系统将停顿。如果无法快速写出脏页面，也会出现相同情况。
后台线程的负担。出于效率原因，原始的LeanStore版本以批处理方式进行页面淘汰和写出，通过称为页面提供者的后台线程来完成[15]。由于每秒执行数百万次页面淘汰和因此I/O操作，需要多个这样的线程。后台线程的不足之处在于很难确定需要多少这些线程，特别是在工作负载发生变化时。
将后台工作作为任务。我们转向了完全异步和非阻塞的模型。由于我们的新方法已经使用任务来运行用户查询，我们还将后台工作作为（系统）任务来运行。这消除了需要后台线程的必要性，而页面淘汰可以直接在工作线程上运行。另一个优点是工作线程不会因页面提供者太慢而停滞不前，而是在系统开始耗尽空闲页面时自然开始花更多CPU时间在淘汰上。这是通过在每次上下文切换时检查是否有足够的空闲页面来实现的。作为一种优化，淘汰然后在主上下文中（而不是在单独的系统任务中）运行。
示例。图9显示了一个示例，说明工作线程如何执行任务。每个工作线程持续运行循环1，交替运行任务、提交I/O、页面淘汰，并轮询I/O完成。当调度程序决定运行用户任务2时，它将创建必要的上下文并将控制权传递给特定任务。在示例中，用户任务1是B-树中的查找。遍历树时，查找可能会遇到不在缓冲池中的节点。这将触发页面故障3，在其中设置I/O请求并推送到I/O后端。任务状态设置为waitIO，并执行返回到在主上下文中运行的调度程序。任务将保持阻塞状态，直到页面故障被解决。回到工作线程循环后，调度程序将触发提交5 I/O请求给SSD。接下来，替换策略将检查是否有足够的空闲页面可用，必要时运行页面淘汰例程。最后，将轮询I/O后端以获取完成情况。然后，工作线程将不断循环6执行这些任务。然后，用户任务2，仅包含CPU工作的任务，将执行7。只要它不遇到页面故障或被阻塞的锁，此任务就可以运行到完成。任务完成后，调度程序代码将恢复，之后之前提交的I/O请求将在某个时刻完成。I/O后端将运行与请求关联的回调8，将任务状态设置为IOdone（即准备就绪），并将任务推回准备队列。任务然后可以恢复执行9：页面故障得以解决，用户任务1的树遍历继续。
3.4 管理I/O
统一I/O抽象。我们的I/O后端支持所有主要的异步I/O库（libaio、io_uring和SPDK），并实现了低开销的RAID0式抽象（数据分条化），将多个SSD在逻辑上组合成一个逻辑设备。在DBMS中实现RAID0，而不是依赖于Linux软RAID实现，可以提高性能（参见图13），并在所有I/O库，包括SPDK中，实现统一接口。后端还将异步执行I/O操作的详细信息抽象掉。关于I/O管理，有两个开放性问题：首先，是否应该有专用的I/O线程，负责处理I/O，还是工作线程应同时处理用户任务和I/O？其次，是否应该一个线程仅负责处理一个SSD，还是所有线程都可以访问所有SSD？
I/O模型。在专用I/O线程模型（图10a）中，工作线程不能直接访问SSD，而必须与处理所有I/O的I/O线程进行通信。这需要在每个I/O操作之间在工作线程和I/O线程之间进行某种形式的消息传递。这可以在用户态中实现，或者本质上，就是使用SQPOLL模式的io_uring所做的，只是I/O线程是内核工作线程。灵感来自于将SSD分配给特定线程的I/O微基准的SSD分配（图10b）模型。同样，需要消息传递 – 在这种情况下，在工作线程之间。在所有对所有模型（图10c）中，每个工作线程都可以访问所有SSD，无需进行消息传递。这包括来自用户任务的读取以及来自后台的写入。模型a和b的优点是它们简化了请求批处理，需要更少的内存映射I/O（MMIO）调用，需要更少的轮询调用。对于内核I/O库，这可以减少上下文切换，并允许在微基准的高峰效率中实现更高的效率。然而，正如我们在下面讨论的那样，我们认为全对全模型是最佳选择。
专用I/O线程的问题。出于与第3.3节中讨论的原因相似，专用于I/O的后台线程存在重大弊端。可以考虑使用单个线程来处理所有I/O。然而，单个线程只能实现每秒630k（libaio、io_uring）到820k（io_uring poll）的IOPS。我们使用io_uring使用SQPOLL作为专用I/O线程进行了实验，但实际上降低了性能和效率。这是因为内核工作线程占用了本可以由工作线程使用的CPU核心。进一步调整I/O线程的数量是困难的，高度依赖于工作负载。与页面淘汰一样，更好的方法是将I/O工作直接作为调度程序循环的一部分在我们的工作线程上处理。
SSD分配模型。微基准实现通常将每个SSD分配给一个特定的线程，以改善缓存局部性并减少轮询。这意味着具有8个SSD的系统还需要至少8个线程。在微基准中，专用分配运行良好，因为每个线程仅为分配的SSD生成I/O操作。然而，真实系统需要线程之间的消息传递，涉及某种形式的同步。然而，如果这带来了更好的I/O性能，那么这种不足可能是可以接受的。为了找出是否是这种情况，我们在微基准中实现了SSD分配和全对全模型。如图11所示，这两种方法都实现了类似的性能。因此，我们采用了全对全模型。
通过I/O通道实现健壮的全对全通信。NVMe队列对抽象专门针对多线程进行设计。每个线程都可以有自己的队列对与每个SSD相关联。libaio和io_uring可以使用类似的设计。因此，我们的I/O后端实现了I/O通道抽象，该抽象封装了实现差异。每个工作线程都有一个I/O通道，用于处理所有SSD的I/O请求，而无需与其他线程同步。这是一种高效且健壮的解决方案，因为它不需要任何额外的消息传递或同步。所有工作线程具有相同的职责，没有线程具有特殊角色。这种对称性还意味着LeanStore可以在单个CPU核心上高效运行。
3.5 CPU 优化与可扩展性
CPU瓶颈的挑战。尽管前述技术在很大程度上解决了I/O管理的问题，但随着系统能够调度数百万IOPS，CPU性能往往成为性能的瓶颈。在传统系统中，I/O路径通常没有像内存中的部分那样进行了优化。针对这一问题，接下来我们将描述LeanStore必须实施的一些优化措施，以应对潜在的I/O受限制问题。
可扩展性问题。在原始的LeanStore设计中，使用了一个全局锁[26]来保护进行中的I/O操作和制冷阶段免受并发访问的影响。LeanStore的先前研究认为这个全局锁不会成为可扩展性的瓶颈，因为它只在制冷路径上需要，并且即使在使用快速SSD时，I/O操作的成本仍然远远高于锁获取成本。然而，使用现代NVMe SSD，这个全局锁很快成为性能瓶颈。为了解决这个问题，替换策略和I/O管理器都获得了独立的锁。为了避免这些锁上的竞争，它们在逻辑上由pageId进行了分区。因此，每个线程仍然可以访问所有页面，但锁争用得到减少。这也意味着可以有效地使用多个线程进行页面淘汰，从而大大提高了内存不足时的性能。图1中测量的LeanStore的数据已包含了这一优化，我们将其用作评估的基准。为了使LeanStore真正具有更好的可扩展性，必须对页面淘汰和I/O路径进行优化。页面淘汰已经过调整，以缩短关键部分并在必要时删除锁定，并使用无锁数据结构。此外，所有内存分配都已被删除，热代码路径必须进行微优化。
顺畅的页面淘汰。在原始的LeanStore版本中，页面淘汰分为两个阶段。在第一阶段，会选择随机页面并将其添加到制冷队列。在制冷阶段访问的页面将从中删除。在第二阶段，会将制冷队列末尾的页面淘汰。在这两个阶段中，需要访问父节点以更新扭曲指针中的制冷标签。LeanStore不使用父指针，因为这显著简化了锁定协议。没有父指针，每次访问父节点都需要从根节点进行树遍历（findParent()）。当系统在内存不足时以每秒淘汰数百万个页面运行时，这种频繁的树遍历需要大量的CPU周期（占总CPU时间的10%以上）。为了减少这种开销，我们在检查时引入了乐观的父指针，用于被访问的节点。有了这个功能，大多数findParent()调用都可以被省略，性能显著提高。
4 评估
4.1 实验设置
硬件环境。本实验在一台配置了AMD EPYC 7713 Milan CPU（64核/128线程，拥有128个PCIe 4.0通道）的Linux机器上进行。该机器运行Linux 5.19操作系统，具备512 GB的DRAM内存和8个三星PM1733 SSD，每个SSD容量为3.84 TB。正如我们在介绍中所阐述，每个SSD具备150万次IOPS的性能。当同时使用所有SSDs时，如果内核参数中启用了IOMMU，性能无法达到这一水平，因此我们在内核参数中禁用了IOMMU，并使用参数amd_iommu=off。在所有实验中，LeanStore使用了我们的RAID 0实现，同时运行在所有8个SSDs上。在每个实验之前，我们使用blkdiscard命令对SSDs进行了擦除，因为这是唯一能够轻松进行性能比较的状态。值得注意的是，当SSD已满或写入时间较长时，性能会下降，这是由于SSD的闪存转换层（FTL）执行垃圾回收引起的。
竞争对比。为了比较我们的结果，我们选择了流行的存储引擎RocksDB（v6.15.5）和WiredTiger（v3.2.1）。RocksDB是基于LSM树的键值存储，由Facebook开发和使用。与LeanStore一样，它针对多核CPU和快速存储进行了优化。WiredTiger是一个键值存储引擎，用作MongoDB的默认存储引擎。它支持LSM树和B树索引。在我们的实验中，我们使用B树作为存储引擎运行。
系统设置。为了专注于I/O处理，防止并发控制成为性能瓶颈，我们在所有系统中禁用了日志记录，并选择了最低的隔离级别。除非另有说明，我们配置了所有系统以使用4 KB页面。我们尝试了许多不同的配置，以确定能够为两个引擎提供最佳性能的设置。例如，在每个实验中，我们使用了理想数量的线程（例如，对于RocksDB，这是1024个线程用于随机查找，64个线程用于TPC-C）。所有存储引擎都在没有内核页缓存（O_DIRECT）的情况下运行。在实验中，我们使用了TPC-C基准测试和带有8字节键和120字节有效负载的随机查找基准测试。这两个基准测试是用C++实现的，并链接到了存储引擎。
4.2 系统比较
TPC-C性能比较。首先，在图12中，我们展示了三个存储引擎在使用16 GB缓冲池的条件下的性能，运行包含1000个仓库的TPC-C工作负载，对应大约160 GB的数据。这意味着数据集大小比缓冲池大10倍。LeanStore在其性能最佳的配置下运行，采用了用户态线程和SPDK作为I/O后端。在TPC-C工作负载下，LeanStore在使用64个线程时实现了超过一百万（107万）TPC-C每秒交易（tps）。相较之下，其他存储引擎可以利用所有128个硬件线程，我们使用了最佳数量的工作线程来实现最佳性能。对于RocksDB和WiredTiger，TPC-C工作负载的最佳线程数为64。具体而言，RocksDB实现了大约10,000 tps，WiredTiger实现了大约40,000 tps。TPC-C工作负载是相当复杂的，包含大量的插入和更新操作，这使得LeanStore的性能明显高于其他存储引擎。
随机查找性能。在第二个实验中，我们展示了具有均匀分布键的只读查找性能。在这个方面，WiredTiger实现了每秒180万次查找，RocksDB实现了每秒280万次查找。与此不同，LeanStore实现了每秒1320万次查找，相当于完全利用了理论上的SSD带宽，即每秒1200万IOPS，考虑到10%的查找是在内存中完成的。
页面大小的影响。在第2.2节中，我们论证了对于使用闪存SSD阵列的快速数据库管理系统，4 KB页面大小是最佳的页面大小。为了展示实际上数据库管理系统并没有因使用这些相对较小的页面而受益很多，我们运行了带有默认32 KB页面和带有4 KB页面的WiredTiger的性能比较。使用4 KB页面，TPC-C性能仅从25,000 tps增加到40,000 tps，远远低于理论上几乎高出8倍的IOPS SSD速度。随机查找工作负载使用较小的页面带来的性能提升更少，从每秒130万次增加到每秒170万次。
4.3 增量性能改进
让我们探讨第3节中讨论的不同优化和技术对性能的提升程度。为此，我们从原始LeanStore版本（但添加了分区优化以获得更好的可扩展性）作为基线开始，然后逐步引入附加功能：4 KB页面、CPU优化、自定义RAID、用户态线程以及SPDK用于内核绕行。我们使用10倍的内存因子、16 GB的缓冲池和160 GB的TPC-C和只读查找工作负载数据作为参数。结果如图13所示。
基线带有分区。原始LeanStore论文[26]使用全局锁来保护I/O阶段免受并发访问。尽管对于大多数内存中的工作负载来说，单个I/O分区可能足够，但当内存不足时，这很快成为性能瓶颈。为了避免这个问题，我们删除了全局锁，将其替换为分区化的页面淘汰和I/O管理，如第3.5节所述。我们使用带有分区的设置作为基线，就像在图1中一样。此时，瓶颈转移到了SSD带宽。可以从图13的I/O图表中看出，无论是在哪种基准测试中，吞吐量都已提高到SSD的最大吞吐量，使用16 KB页面。然而，就IOPS而言，TPC-C中的31 GB/s和只读工作负载中的53 GB/s仅相当于6 M到12 M IOPS中的约1.9 M和3.2 M IOPS，使用4 KB页面。
页面大小。为了充分利用IOPS方面的完整SSD带宽，有必要将页面大小切换到较小的页面大小。因此，在接下来的步骤中，我们对LeanStore进行了+4 KB页面的基准测试。预期之内，这对TPC-C的性能产生了很大的影响，性能提高了一倍，达到了超过500,000 tps。这种大幅提高是因为TPC-C具有很高的写百分比（总I/O的约40%），而SSD带宽比只读工作负载低很多。将页面大小缩小4倍有效地使IOPS吞吐量提高了4倍。只读性能提升较为适度。即使在使用16 KB页面的情况下，IOPS也远高于TPC-C中的IOPS，因为瓶颈在其他地方（Linux RAID）。
CPU优化和RAID。+CPU优化将TPC-C的性能提高了30%以上。这直接对应于通过微优化节省的CPU时间。类似地，自定义、更高效的+RAID 0导致了类似的性能提升。在只读工作负载中，性能改进甚至更高，因为吞吐量数字比TPC-C中要高得多，而Linux md raid在大约15 GB/s附近似乎有一个硬性限制。消除这一瓶颈几乎提高了只读查找速度的两倍。
避免过度订阅。所有先前的实验都是在高线程过度订阅的情况下运行的。已调整后台线程和工作线程的数量以获得最佳性能。这高达1500个工作线程和40个被隔离的页面淘汰后台线程。使用用户态+tasks消除了这种上下文切换开销和调整的必要性。这消除了这种上下文切换开销，将TPC-C的性能提高了16%，只读性能提高了25%。
用户态I/O。最后，我们使用+SPDK来进行I/O的内核绕行。在TPC-C中，这不会显著提高性能，因为即使使用libaio，LeanStore也已接近SSD的最大带宽（适用于混合读/写工作负载）。此外，我们为每个设置使用了最佳数量的线程，在+tasks（1.03 M tps和10.08 M查找/s）的情况下，这是128个线程。使用+spdk（1.07 M tps）只需要64个线程，因为这足以实现最高性能并充分饱和所有SSD。在随机/只读查找中，我们接近了中断基于I/O似乎存在的一个瓶颈，将吞吐量限制在大约10 M IOPS左右。使用SPDK（13.26 M查找/s，注意：10%的查找被缓冲）没有这个限制，并且可以使用完整的SSD带宽。在TPC-C工作负载中，I/O轮询中的io_uring可以实现与SPDK相同的吞吐量。然而，它需要超过64个线程（128个线程下的1.07 M tps）。io_uring实现的稍微少一些，128个线程下为12.2 M随机查找/s，显示出需要更多CPU周期的情况，在这种IOPS/CPU速度比下开始变得重要。
没有主要瓶颈。正如所见，所有的优化和技术都是为了充分利用快速NVMe阵列提供的全部潜力。
4.4 内存不足的可扩展性
内存中性能。LeanStore在内存中表现出与主存数据库系统相媲美的性能。对于内存中的工作负载，它能够在128个线程的情况下实现每秒超过300万个TPC-C事务。然而，在内存不足的情况下，将触发大量附加的代码调用，包括淘汰策略、页面错误处理、整个I/O路径以及上下文切换。因此，自然而然地，性能将因此额外的工作而下降，尤其是当CPU周期有限时。
百万级性能。如图14所示，LeanStore的内存不足可扩展性，通过增加数据集大小（例如仓库数量）并使用固定大小的400 GB缓冲池来进行测试。当数据完全适合内存时，LeanStore可以在64个线程的情况下实现每秒超过200万tps。然而，在内存不足的情况下，性能会逐渐下降。在一个内存不足的10倍设置中，数据集包含25,000个仓库或4 TB的数据，LeanStore仍然能够实现每秒110万tps。在这种配置中，充分利用了8个NVMe SSD提供的完整I/O带宽（25 GB/s），并采用56%的读取和44%的写入设置。为了突显LeanStore超越这一限制的潜力，我们测试了非常大的数据库大小，高达100,000个仓库，相当于16 TB的数据，或内存不足因子为40倍。在这种情况下，LeanStore仍然能够实现每秒40万个事务。
从技术上讲，运行更大的数据库是可能的。然而，以40倍内存不足的方式运行系统已经相当极端。目前，单位容量的DRAM与闪存SSD之间的价格差异约为20倍。因此，对于更大的数据库，也有必要为额外的DRAM预留更多的资金。
4.5 I/O 接口
真实工作负载。在这个实验中，我们评估了LeanStore支持的不同I/O后端。显然，选择正确的I/O接口取决于给定的约束条件，例如是否需要文件系统、缓冲或非缓冲I/O，是否可以让应用程序专用整个设备等。我们的评估仅基于性能和效率，LeanStore代表了一个比I/O微基准更真实的工作负载。
只读性能的差异更大。如第4.3节所示，对于TPC-C，使用用户态I/O的额外步骤并没有显著提高性能。与此同时，只读查找的性能差异相对较大。这可以归因于SSD的混合读/写性能明显低于只读（混合：6.7M IOPS vs. 只读：12.5M IOPS，闪存写入约比读取昂贵10倍）。因此，在为工作负载提供足够的CPU核心的情况下，可以使用每种接口来实现饱和。
限制CPU核心。为了展示内核I/O库的实际CPU开销，我们将它们与SPDK进行比较，并限制正在使用的CPU核心数量。通过这样做，我们可以观察在受限的核心数量上运行时系统性能的差异影响，从而揭示不同I/O库的效率。图15显示了使用io_uring、libaio和SPDK的只读和TPC-C中的相对性能，其中SPDK始终实现了最高性能。一般趋势是，可用的CPU核心越少，SPDK的性能越好，因为它在CPU使用效率上更高。对于只读工作负载，SPDK的性能平均比内核库快60%-80%。随着可用的CPU核心增加，差异减小到约50%。在TPC-C中，由于与只读查找相比，工作负载的I/O负载较低，差异较小。用于I/O的CPU周期较少，因此使用SPDK的优势较小。io_uring在默认设置中，禁用I/O轮询时令人惊讶地略慢于libaio（平均约2%）。启用I/O轮询时，io_uring比libaio快（约5-8%）。
可用标志。io_uring提供了许多标志，可以改变和改进其在特定用例下的行为。在第2.4节中，我们已经提到了在实验中使用的IOPOLL标志。还应该注意，要使用轮询I/O，必须通过设置nvme.poll_queue来指示内核nvme模块分配一定数量的队列以进行轮询。已经提到的另一个标志是SQPOLL。它消除了系统调用的必要性，因为它创建了轮询提交队列、处理SSD I/O提交和轮询的内核工作者。我们对这个设置进行了实验（包括ATTACH_WQ、SQ_AFF等），但在每个I/O操作的周期效率方面无法取得更好的效果。此外，这个标志再次引入了难以管理的后台线程，这不符合我们的设计。
对抗内核。在这一点上，还重要指出，批量提交和减少轮询调用主要有利于内核库。这在一定程度上是因为它减少了系统调用，但更多地是因为通过内核I/O堆栈（即块层）的开销较高。这对于所有内核I/O接口目前都是一样的。使用SPDK，批量处理将降低NVMe提交门铃上的MMIO调用次数。然而，SPDK显示提交和轮询实际上已经相对便宜。在微基准中，使用SPDK饱和所有SSD仅需要三个CPU核心。SPDK轮询调用仅需要约80纳秒（200个周期）。针对特定内核特性进行优化并不是一种有前途的方法，特别是因为Linux内核I/O子系统中的io_uring和nvme_passthrough等方面正在进行大量的积极开发。
4.6 CPU 使用率
从CPU周期的角度来看，不使用SPDK的成本相对较高。如图16所示，对于内存中的工作负载，所有CPU时间都用于实际的事务工作负载。在通常设置中，例如具有1000个TPC-C仓库和16GB RAM的情况下，当内存不足时，会花费大量时间进行驱逐和I/O提交。在所有的内存不足工作负载中，驱逐的情况都非常相似，大约为14%，除了在使用SPDK时略高（18%），因为它与事务份额成正比，而在使用SPDK时事务份额更高。这主要是因为在SPDK中提交I/O请求要高效得多（约2% vs. 16-19%）。这与接口有关较少，而与Linux内核中I/O路径的低效实现有关（v5.19.0-26）。我们还在进行了I/O提交批处理（+3%的内核库吞吐量）和禁用内核缓解（+4%的内核参数缓解=off）的情况下运行了实验。然而，这两个设置并没有改变内核I/O库之间的相对差异。
4.7 延迟
我们还测量了事务延迟，采用了目标事务速率和指数分布的交互到达时间。结果如图17所示。在随机查找工作负载中，延迟几乎完全对应于I/O延迟。在TPC-C工作负载中，延迟要高得多，因为每个事务平均需要进行3.5次同步读操作。TPC-C还包括将脏页异步驱逐到存储，平均每个事务有2.8个页面写入。这会导致读的尾部延迟较高，因为它们可能会被写入操作阻塞，而闪存上的写入操作需要更长的时间。
5 相关工作
在我们的了解范围内，尚无已知的OLTP系统可以充分利用NVMe阵列的性能潜力。闪存的低成本和高性能使得有关这一主题的研究相对有限，尤其是与已经优化为主内存或持久内存的系统研究相比。
初始的闪存研究。闪存SSD在约2008年开始引起广泛关注，这促使了如何将其整合到数据库系统中的研究。最初的研究主要关注闪存对数据库应用的潜在好处[10, 24, 25]。当时，闪存的性能和价格相对低，相对于现在的水平相差了几个数量级。因此，闪存主要被视为成本效益的主内存缓冲池扩展[5, 17-19]，或者用于特定数据库服务的缓存，例如恢复[3]、多版本存储[34]、更新缓存[35]或草图[12]。随着当前的价格下降，闪存现在已经成为主要的持久性存储介质，而不再是一个额外的存储层。
专用硬件。NAND闪存具有与传统硬盘不同的物理特性，例如不支持原地写入。商用SSD为了向后兼容，使用复杂的内部逻辑来模拟传统硬盘的行为。这可能导致性能低于所需且不可预测。因此，一些研究关注专用的SSD[14, 20, 37]，新颖的I/O接口[4, 29, 32, 33]以及数据库和存储硬件的共同设计[9, 28]。某些系统已经针对减少写入放大[11]进行了优化，而另一些系统[6, 7, 16, 21, 23]则专门设计用于Optane（3D Xpoint）内存，这些内存具有与闪存不同的硬件特性。相比之下，本文提出的技术适用于所有经济实惠的现成NVMe SSD。
高性能存储引擎。有许多为闪存优化的存储引擎和键值存储。例如，RocksDB [36]基于优化低写入放大的LSM树（以较高的读放大为代价）。虽然RocksDB是为闪存而设计的，但是在SATA SSD时代，无法充分利用大型NVMe阵列。我们所提出的技术是通用的，可以集成到基于LSM的存储引擎中。另一个高效的存储引擎是WiredTiger [30]，与我们的LeanStore系统类似，都是基于B树。LeanStore和WiredTiger之间的一个区别是后者对内存中和内存之外的节点使用不同的表示。这可以节省空间，但在使用高速存储设备时，表示之间的转换（“协调”）可能导致较高的CPU开销。
高性能键值存储。与我们的方法类似，PATree [41]使用SPDK作为高效的异步I/O库，但依赖于单个线程，因此无法充分利用NVMe阵列的全部潜力。Tucana [31]是基于𝐵𝜖-Tree的键值存储，经过了为SATA SSD进行优化。然而，它是在SATA SSD时代构建的，依赖于I/O的mmap，这已被认为不足以满足NVMe时代的性能需求[8]。KVell [27]最接近充分利用NVMe阵列带宽。与LeanStore不同，KVell是一个分区键值存储，不会在磁盘上存储按键排序。这对于范围查询和小负载来说是一个很大的限制，使其不适合作为DBMS的通用存储引擎。此外，即使在这些限制条件下，KVell也不能充分利用其实验中大型闪存NVMe阵列的性能。实际上，他们报告在一个具有3.3M IOPS的服务器上，被CPU限制，只能实现I/O能力的75%。因此，根据我们所了解，LeanStore与本文中讨论的技术是目前唯一能够充分利用NVMe阵列潜力的系统。
6 结论
本文深入研究了现代NVMe存储阵列的性能潜力以及高性能存储引擎如何充分利用这一性能。我们对引言中提出的问题进行了深入回答：
- Q1：NVMe SSD阵列能够实现硬件规格中所承诺的性能。实际上，我们在8×SSD配置下实现了超出承诺的吞吐量，达到1250万IOPS。
- Q2：通过所有异步I/O接口，都能够实现出色的性能。尽管内核绕过对于实现全带宽并非绝对必需，但在CPU使用效率上却表现更为出色，即使在使用小页面时也如此。
- Q3：在随机IOPS、吞吐量、延迟和I/O放大之间，最佳平衡点是使用4KB页面。
- Q4：为了管理大型NVMe SSD阵列所需的高并行性，数据库系统必须采用低开销的机制，以快速响应用户查询。为了应对这一挑战，我们采用了轻量级用户态线程以实现协作多任务处理。
- Q5：管理数千万IOPS的工作负载使得内存外代码路径变得至关重要，同时也对性能造成关键影响。解决这一问题需要通过对相关数据结构进行分区来实现可扩展的I/O管理，以避免竞争热点的出现。此外，替换算法必须经过优化，以每秒逐出数千万个页面。
- Q6：在我们的设计中，I/O操作由工作线程直接执行。这种对称的设计概念上更为优越，可实现更健壮的系统。
硬件和软件的进展。Linux内核I/O接口表现出乎意料的卓越性能，能够在我们的基准测试中实现1000万 IOPS。启用I/O轮询的io_uring是唯一能够实现我们NVMe阵列全带宽的内核接口。内核绕过的SPDK的最大优势在于CPU周期的效率。然而，SPDK也存在一些明显的缺点，如需要root权限和对整个SSD的独占访问。目前，对于效率较低的内核接口，有足够的CPU时间可供使用。随着即将推出的PCIe 5.0 SSD，CPU周期和I/O操作之间的比例将再次发生变化，这可能会使内核绕过更加重要。但是，内核开发不会停滞不前，将不断跟进这一发展。
闪存为王。正如我们在第1节中所讨论的，经济现实非常明确：NVMe SSD对高性能OLTP应用非常吸引人，而且随着带宽的进一步提升，其重要性将继续增加。随着更多的系统适应这一经济现实，我们相信我们的工作可以作为重要的基础。