如何减少B+Tree的写放大？

作为使用最广泛的索引数据结构，B+ Tree支持当今几乎所有的关系数据库管理系统 (RDBMS，例如 MySQL、PostgreSQL、MariaDB、Oracle、SQL Server 和 DB2）。最近，LSM-Tree作为 B+ Tree 的竞争者吸引了一部分的注意力，主要是因为 LSM-Tree 的两个被广泛引用的优点：更低的存储成本和更小的写放大。这里的写放大定义为B+Tree或LSM-Tree写入存储设备的数据总量与写入B+Tree或LSM-Tree的用户数据量的比值。例如，假设B+Tree需要向存储设备写入总共8KB的数据来服务用户对128B数据的写入请求，则写放大率为8KB/128B=64。一般来说，LSM-Tree 的写放大至少可以比 B+ Tree小 5~10 倍。存储内透明压缩的到来可以直接减少甚至消除 B+ Tree和LSM-Tree之间的存储成本差距。例如， 在键值对大小为 128B的情况下，我们将总共150G的键值对加载到WiredTiger（MongoDB的默认存储引擎，使用B+ Tree数据结构）和 RocksDB（使用LSM-Tree数据结构）中，它们都运行在我们的 CSD 2000 驱动器上并且支持存储透明压缩。下表列出了LBA空间上的逻辑存储使用量（即存储压缩前）和物理存储使用量（即存储压缩后）。由于LSM-Tree的数据结构比B+ Tree更紧凑，因此 RocksDB的逻辑存储空间使用量比WiredTiger更小（即 218GB vs.~280GB）。

然而，通过简单地部署具有内置透明压缩功能的存储驱动器，并不能减少B+ Tree与 LSM-Tree写放大的差距。为了进一步减少甚至消除写放大差距，必须适当修改B+Tree的实现以更好地适配存储设备的透明压缩功能 。这篇博客提出了这样一个解决方案，其来源于一个简单的观察：对于B+ Tree的一个page，Δ表示其内存映像和存储映像之间的差异。如果差异明显小于页面大小（B+ Tree页面大小通常为 4KB、8KB 或 16KB），我们可以通过记录页面修改来大大减少写放大，而不是将整个内存页面写入存储设备。这在概念上与基于相似性的重复数据删除和增量编码相同。不过，B+ Tree在没有内置透明压缩的普通存储设备上运行时，由于大量的操作开销，这个简单的想法变得难以实现：对于4KB  block I/O接口，我们必须合并多个来自不同B+Tree page的Δ到 一个4KB LBA block中以减少写放大。于是，与同一个B+Tree page相关的多个Δ会分布在存储设备的多个 4KB block上，然而这会导致两个问题：（1）对于每个页面，B+ Tree必须跟踪其所有关联的Δ并定期进行垃圾回收，导致存储管理复杂度高。(2) 要从存储上加载页面， B+ Tree必须从多个不连续的4KB LBA block中读取存储着的该page和多个Δ，导致页面加载延迟很长。因此，据我们所知，这个简单的设计概念还没有被现实中的B+ Tree所实现。

存储内透明压缩使上述想法变得可行。通过应用由存储透明压缩提供的可变大小的block I/O，我们不再需要合并多个来自不同页面的Δ到同一个4KB LBA block中。对于每个B+ Tree页面，我们专门指定一个4KB LBA作block为修改日志空间来存储所有与此页面关联的Δ 。当B+ Tree需要持久化内存中的脏页时，我们不会将整个内存中的页刷新到存储中，而是只将其Δ写入到相关的修改日志空间。由于每个Δ通常比4KB小得多 ，与将整个内存页面映像刷新到存储相比，我们可以实现更少的写放大。这可以在图 1 中进一步说明：假设B+ Tree的页面大小为8KB，并且需要在时间t1、t2 和 t3分别持久化一次。我们分别在 (0, t1)、(t1, t2) 和 (t2, t3) 期间修改了三个 128B 段 m1、m2 和 m3。如图1(a)所示，在常规设计实践中，B+Tree每次总是将整个8KB页面刷新到存储设备，而不管数据的修改量。这导致总共24KB的写入量。相比之下，如图1（b）所示，当我们使用存储透明压缩启用的新设计方法时，在时间t1，我们写[m1，O] 到4KB修改日志block，其中O代表一个全零向量，因此可以在存储设备内压缩掉。在t2时刻，我们将[m1，m2，O]写入4KB的修改日志空间，在t3时刻，我们再次写入[m1，m2，m3，O]。利用存储中透明压缩启用的虚拟可变大小block I/O，在t1时刻，我们通过4K block I/O接口写入128B有用数据，在t2时刻，我们通过4KB block I/O接口写入2x128B=256B有用数据，最后在t3时刻，通过4KB  block I/O 接口，我们写3x128B=384B有用数据。最终总共有128B+256B+384B=768B数据写入物理存储介质（在存储压缩之后）。与图 2(a) 所示的传统做法相比，这种简单的方法可以将B+ Tree写放大减少24KB/768B = 32。

为了更好的阐释，我们做了此实验，并与RocksDB和WiredTiger进行了比较。如上所述，RocksDB使用LSM-Tree数据结构，而 WiredTiger 使用B+ Tree数据结构。所有实验都是在我们支持内置透明压缩的CSD 2000驱动器上进行的。正如我们在之前的博客中所讨论的，当我们使用按事务刷新提交策略时，WAL引起的写放大可能很重要。因此，我们在所有实验中都禁用了WAL，以消除WAL对写放大的影响。我们将数据集大小设置为500GB，并考虑了不同的记录大小（即 128B、32B 和 16B）。对于改进的B+Tree和WiredTiger，我们设置页面大小为8KB，运行随机只写（ write-only ）工作负载。如图2所示，与RocksDB相比，普通B+Tree（即 WiredTiger) 具有更大的写放大，而我们改进的B+ Tree基本上可以缩小B+ Tree与LSM-Tree写放大的差距。例如，在32B记录大小和4个客户端线程的情况下，RocksDB的写放大为38，而WiredTiger的写放大为268，比RocksDB大7.1倍。相比之下，我们改进的B+ Tree的写放大率仅为 RocksDB写放大率的73.7%。

上述结果表明，存储中透明压缩的到来使得LSM-Tree相对于B+ Tree的两个优势在很大程度上消失了。同时，与LSM-Tree相比，B+Tree具有更高的读取和扫描性能、更好的并发性和一致性等明显优势。通过减轻B+ Tree的两个主要缺点，存储中透明压缩使B+ Tree成为（几乎）完美的数据结构。随着内置透明压缩的存储硬件越来越普及，B+ Tree将继续作为赋能数据管理基础设施的数据结构。