作为使用最广泛的索引数据结构,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)。

逻辑空间 | 物理空间 | |
RocksDB | 218GB | 129GB |
WiredTiger | 280GB | 104GB |
然而,通过简单地部署具有内置透明压缩功能的存储驱动器,并不能减少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将继续作为赋能数据管理基础设施的数据结构。