作为目前数据库引擎的两种次要数据结构，LSM-tree和B+-tree在业界曾经有十分宽泛的钻研。相比B+-tree，LSM-tree就义肯定的读性能以换取更小的写放大以及更低的存储老本，但这必须建设在已有的HDD和SSD的根底上。
摸索前沿钻研，聚焦技术创新，本期DB·洞见由腾讯云数据库高级工程师王宏博进行分享，次要介绍一篇2022年FAST的论文，主题为“基于硬件通明压缩的B+树优化”。本次分享的论文针对可计算存储SSD（反对硬件通明压缩）提出了三种乏味的设计办法，从而极大地缩小了B+-tree的写放大（10X）以使其靠近甚至超过LSM-tree。以下为分享实录：
残缺视频：[https://v.qq.com/x/page/p3342...]()
一、论文简介
本期分享的是2022年FAST的一篇论文，主题是基于硬件通明压缩的B+树优化，该论文在内容上次要分为三个局部：
第一局部是背景介绍，作者别离介绍了现有的B+树及其软件压缩、存储硬件通明压缩、B+树和LSM-tree的简要比照以及B+树写放大的形成剖析。
第二局部是算法局部，作者针对性地提出了三种设计来优化B+树的写放大:
确定性的page shadowing来解决页面原子写引入的写放大。
通过页面本地增量日志来缩小刷脏页引入的写放大。
通过稠密日志来缩小redo日志引入的写放大。
第三局部是试验局部，作者通过后面所述的三个办法实现了一个新的B+树（咱们称之为B−-tree为以示区别），并具体比拟了多种条件下的测试后果。
二、背景局部
2.1 现有的B+树及其软件压缩
咱们相熟的开源数据库有很多都应用B+树作为存储引擎，比方MySQL、MongoDB、PostgreSQL等，腾讯云数据库TDSQL-PG也是基于B+树来实现的。B+树的构造如下方的左图所示，它通过一个个的数据页面形成一个树状构造以提供索引减速数据查找。常见的数据页面大小有8k和16k，通过数据页面压缩能够缩小B+树的空间占用以降低成本，此外还能够缩小B+树的写放大。
在后面所提到的基于B+树实现的数据库中，MySQL、MongoDB都实现了B+树的软件压缩个性，TDSQL-PG的商业化版本也有实现。软件压缩具备不依赖于特定硬件、灵活性高的长处，但美中不足的是，受限于现有的IO 4K对齐的束缚会产生一些额定的空间节约。比方下方右图，一个16K的数据库页面通过压缩后产生了5K的数据。受限于IO 4K对齐的要求，当落盘时这5K的数据实际上要占用8K的空间，产生了额定的3K的空间节约。
常见的B+树压缩算法有Lz4、zlib、ZSTD，前面所提的LBA则是指logical block adressing，即逻辑上的磁盘块大小。
2.2 存储硬件通明压缩
咱们先简略回顾下闪存的个性。如下图所示，闪存反对三种基本操作：读、写、擦除。闪存的读、写都以page为单位，个别是4K，擦除则是以block为单位，一个block个别蕴含多个page，比方蕴含64个page。之所以闪存须要反对擦除，是因为闪存的写比拟非凡，一个page只能在擦除之后一次写入，而不能更新。但从用户的角度来看，SSD须要反对更新，因而咱们在SSD里会有一个FTL层来实现该逻辑，即下图两头蓝色局部所示。
CSD，顾名思义是一种带有计算能力的存储。如下图所示，一个通用的CSD在存储层能够反对API调用来进行计算下推。硬件通明压缩存储作为CSD的一种，反对在其外部对数据进行压缩和解压，后续咱们提到的CSD次要是指带有硬件通明压缩的CSD。
比照最下方的两张图，右边是一般的SSD，左边是CSD。能够看到一般SSD的LBA和闪存都是以页面为根底，且都是4K大小，能够由FTL间接进行映射。CSD和SSD相似，都对外提供了4K的LBA接口，但4K的数据通过压缩后长度不肯定，所以在CSD外部，FTL的闪存治理须要反对对变长数据的治理，这也使得CSD的FTL变得更加简单。如此一来CSD能带来什么益处呢？
总体来看，CSD的益处体现在它有更优的老本、更好的性能，但在此不做具体探讨，咱们次要关注CSD的技术特点。CSD能够实现逻辑地址和物理地址的解耦。如下方左图所示，对一个理论闪存大小只有4T的CSD来说，它能够对外提供远大于闪存大小的LBA。另外，如下方右图所示，对于稠密数据的写入能够进行通明压缩而不产生空间节约。基于CSD的这两个个性，咱们在下层利用如数据库中，能够做一些针对性的设计，以进一步利用CSD的个性。
2.3 B+树和LSM-tree的简要比照
咱们先回顾LSM-tree的写入流程。如右上图所示，一条数据记录的写入，会先写log，再进入memtbale，memtable写满之后会变成 immutable memtable， 再与L0的SSTable进行合并，下层的SSTbale也会在适合的机会与上层SSTable进行合并。
咱们再简要回顾B+树的写入流程。一条记录的写入也是先写入log，再写入B+树的数据页面，当数据页面写满时就须要进行页面决裂，所以大部分工夫B+树的页面其实是不满的。另外，因为B+树是间接操作指标页面，当内存不够时就会波及到页面的淘汰问题，这时就须要刷脏页。极其场景是每写一条记录就须要刷一次脏页，如果一条记录是128字节，页面是8k，那么对应的写放大就是64倍。
B+树和LSM-tree在写方面的次要区别是：LSM-tree是一个严密排布的构造，能够占用更小的写空间以及产生更小的写放大。B+树的写放大与数据集的大小成正相干，与单条记录的大小负相关。对于数据齐全能够放入内存的场景，B+树能够产生比LSM-tree更小的写放大。因而这篇论文聚焦在大数据集以及小数据记录的场景，也就是说，B+树在该场景下写放大显著劣于LSM-tree。
作者通过在CSD上执行一个随机写入的测试，初步展现了B+树和LSM-tree的差别。后果如右下图所示，能够看到LSM-tree占用的逻辑空间更小，这与LSM-tree的数据严密排列无关，通过CSD压缩之后，B+树的物理空间占用也大幅度减小。此外，通过比照发现，LSM-tree的写放大显著小于B+树，因而本论文的指标就是须要通过改良B+树的实现来大幅度减小B+树的写放大。
2.4 B+树写放大的形成剖析
B+树的写放大形成次要蕴含三个局部：
为了保障事务原子性采纳redo log引入的写放大 ；
因为lru buffer淘汰或者checkpoint 刷脏页而引入的写放大；
为了保障页面写的原子性而引入的写放大，如MySQL的 double write。
当思考CSD的压缩个性时，公式1所列的写放大会引入示意压缩比的系数 ，其含意为 压缩后的数据大小比压缩前的数据大小，其位于0-1之间，也就是说，CSD会升高写放大。
三、算法局部
3.1 Deterministic Page Shadowing
算法1是通过确定性的page Shadowing来缩小page原子写引入的写放大，其本质上是copy on write，一次页面刷盘写只须要写一次即可。具体实现如右图所示，1个数据页面在磁盘上会有2倍的间断LBA空间与之对应，这个LBA被划分为两个slot，两个slot轮流写入以实现copy on write，从而保障每次写入不论是否胜利，页面的前镜像总是保持稳定。在页面写入胜利后，能够通过trim 操作清理前一个slot的物理空间占用。在页面的写失败时，咱们能够通过 checksum进行检测，并通过页背后镜像+redo复原出最新的页面。对于写胜利后crash保留两个残缺页面的场景，则能够通过比拟页面的LSN找到最新的页面，并trim掉旧的页面。
本办法带来的一个负面影响就是每次读须要产生额定的数据传输，然而作者认为pcie的传输能力远大于flash的速度，因而不成问题。此外，对于反对计算下推的CSD，咱们能够将该逻辑下推，也能够防止掉额定的数据传输。
3.2 Localized Page Modification Logging
算法2是通过本地批改日志来缩小刷脏页引起的写放大。如右图所示，一个数据页面在存储层对应一个数据页面+一个4K增量log页面，两者的逻辑地址间断。在内存中数据页面被分为k个segment，每个segment大小是Ds，每次页面批改所波及到的segment会在bitmap f外面记录。当须要刷脏页时，咱们能够通过bitmap f找到所有的批改增量，并把它记为，再把、bitmap f、补零后的数据一起写入盘中。以一个16K的数据页面为例，对应的写放大会缩小75%。通过CSD通明压缩后，写放大可进一步减小。
在该办法中，因为额定引入了增量日志，会造成肯定的物理空间的放大，咱们能够通过参数T来管制物理空间的放大。当增量日志大于T时间接刷脏页并重置增量日志，T越大写放大越小，然而对应的物理空间放大就越大。读取页面时咱们须要读原始数据页面+增量日志局部，再结构最新的数据页面。因为读页面须要额定读所以会造成肯定的读放大，但因为数据页面的地址和增量日志LBA是间断的，因而一次读申请即可解决。另外，增量日志绝对较小，所以能够认为这部分的读放大影响较小。
3.3 Sparse Redo Logging
算法3是稠密日志，用于缩小Redo log造成的写放大。目前常见的Redo log的实现如左图所示，日志采纳间断严密排列，事务1提交时日志L1落盘，事务2提交时因为日志buffer未满，因而会在L1的buffer中追加L2，L1和L2一起落盘，事务3提交时，L1、 L2 须要连同L3再落盘一次，直到以后日志buffer页面被写满，才会开启新的页面。在该例子中，从flash的角度看，L1被写了3次，后两次都是额定的写放大。当采纳右图所示的稠密日志时，每次日志写入都是用一个新的页面，页面通过通明压缩后落盘，则齐全能够防止写放大的问题，另外因为通明压缩的存在也不会产生额定的空间占用。此外稠密日志也是能够用于LSM-tree的。
四、试验局部
在试验局部，作者通过前述的三个优化办法实现了一个新的B+树（命名为B-树以示区别），同时还实现了一个Baseline的B+树，并且与Rocksdb、WiredTiger做了比拟全面的试验比照。
4.1 Experiments with Log-Flush-Per-Minute
在试验1中，Redolog的刷盘频率被设置为每分钟1次，以屏蔽掉Redo log写放大的影响。通过不同的数据集大小、单条记录的大小以及B+树页面大小设置，作者比拟全面地评估了B-树的个性，得出初步的论断：B-树的写放大曾经比拟靠近于LSM-tree，即右图中所有的橙色、绿色和紫色的局部比拟靠近。而Baseline B+tree和WiredTiger这两种规范的B+Tree，它们的写放大都比拟大。
通过试验数据的比照，咱们还能够发现：
B+树的写放大与Record size负相关，即Record size越小其写放大越大。以后面提到的极其例子为例，每条Record都会引起一次刷脏页，这时的写放大是Page size比Record size。如果Page size固定，当Record size越小，其写放大会越大。
B+树的写放大与并发数负相关，即并发数越大其写放大越小。咱们能够了解为，当并发数比拟高时，一个页面里可能会产生更多的更新，一次刷脏页就会有更多的Record进来。
LSM-Tree的写放大与数据集正相干。当数据集比拟大时，做不同层之间的merge，它的写放大会变大。
4.2 Experiments with Log-Flush-Per-Commit
在试验2中，Redo log的刷盘频率被设置为每次事务提交，这也是咱们在理论生产中为保障不丢数据而罕用的办法。作者用一个独自的图来展现log局部的写放大，咱们能够看到LSM-tree和B+树的Redo log的写放大都跟Record size相干，Record size越小，写放大越大，同时与并发数负相关，随着并发数的回升写放大会减小。这是因为并发数的回升实际上会产生更多日志的合并，即每次写盘时会有更多的事务的提交日志一起写入，因而写放大缩小了。对B-树而言，因为采纳了稠密日志，所以其在不同Record size大小和不同并发数下都放弃很小的日志写放大。
图12展现了一个思考日志写放大后的整体写放大。咱们能够看到，B-树绝对LSM-tree而言，它的写放大进一步升高，除了图中红框局部外，其余场景都比LSM-tree更优。
如果把两个不同的日志刷盘形式放在一起比照，咱们能够发现，Redo log的写放大对B-树而言总体保持稳定，因为它应用了稠密Redo log。当其余B+树和LSM-tree采纳每事务提交时，两者的写放大显著进步，尤其是在并发数比拟小的状况下，Redo log日志所引起的写放大占比拟高。
4.3 Impact of Threshold T
在试验3中，作者对算法2中提到的本地页面批改增量日志的算法做了验证。参数T示意当增量日志达到多大量时间接刷数据页面并重置增量日志，参数Ds示意页面宰割的segment的大小。如图14和表格2，咱们能够看到当T越大时，B-树的写放大会越小，但物理空间占用则会越大，这与咱们之前的实践剖析统一，所以这两个参数在理论中须要trade off。
图13展现了压缩对于物理空间占用的影响。因为B-树须要额定的4k页面占用，所以B-树的逻辑空间占用显著高于其余B+树，但在通过CSD压缩后，理论物理空间的占用放大则放大了，相比B+树曾经不显著了。
4.4 Speed Performance Evaluation
在试验4中，作者比照了三种场景下的B-树绝对于其余几种树的性能。
在随机点查场景中， B- tree 和 LSM-tree 相当，但两者都小于B+树。这与B- tree采纳本地页面的增量日志刷脏页无关，因为每次读取须要从新通过增量日志来结构最新的数据页面，这会引入额定的开销 。
对随机范畴查问而言，B-树和B+tree的性能相当，优于LSM-tree。作者认为，因为一次查问多条记录，B-树引入的读开销占比变小了，所以其性能比拟高。
在随机写场景中，B-树略微优于LSM-tree，两者都显著优于B+树，这是因为前两者都领有更小的写放大。但须要强调的是，因为B-树和B+树都波及到buffer 淘汰问题，所以尽管是只写负载但理论的IO却是读写混合的，因为B-树须要读取额定的4k增量日志页面，因而读IO比B+tree有所放大，其绝对B+树的性能晋升也就没有像写放大缩小得那么显著。
五、拓展与总结
最初分享一个CSD和PG联合起来的乏味试验。PG中有个名为 heap only tuple update的机制，用于优化非索引列更新。如下图所示，当更新一个元组时，如果以后元组所在的heap表页面有闲暇空间，就能够间接在以后页面插入一条新的元组，再把老元组的ctid指向新元组即可，这样能够防止去找新的数据页面写入以及在索引页面中写入新的记录。PG中还有一个fillfactor的参数来管制heap表的填充率，咱们能够利用较小填充率来换取非索引列更新的性能。当引入CSD之后，还能够进一步防止造成物理空间占用的放大，比拟完满地解决了以往须要进行物理空间占用和性能trade off的问题。
综上所述，这篇论文提供了一个不同的视角去比拟B+树和LSM-tree，让咱们更深刻地了解B+树和LSM-tree。作者通过三种实现比较简单但却十分奇妙的办法来改良B+树，在CSD上也获得了很好的成果，为咱们带来了很好的启发。
参考文献
*[1] Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression
[2] The True Value of Storage Drives with Built-in Transparent Compression: Far Beyond Lower Storage Cost
[3] Understanding Flash: Blocks, Pages and Program / Erases
[4] B+Tree index structures in InnoDB
[5] PostgreSQL与通明压缩
[6] The Internals of PostgreSQL
[7] WiscKey: Separating Keys from Values in SSD-Conscious Storage*