Reducing Write Amplification of LSM-Tree with Block-Grained Compaction
Reducing Write Amplification of LSM-Tree with Block-Grained Compaction
LSM-tree作为一种写优化的存储引擎，广泛应用于LevelDB和RocksDB等键值存储系统中。然而，传统的LSM-tree上的合并操作需要读取、合并和写入许多sstable，本文称之为表合并。表合并会导致两个主要问题，即写放大和块缓存失效。它们会降低lsm树的写和读性能。为了解决这些问题，我们提出了一种新的合并方案——块合并方案，该方案采用块粒度的合并策略来执行LSM-tree上的合并操作。块合并(Block Compaction)通过确定数据块的边界，尽量避免数据块的重复使用，既减少了写放大，又缓解了块缓存失效问题。通过代价分析，从理论上证明了块合并比表合并更高效。
此外，我们还分析了块合并的副作用，并提出了3种优化方法:(1)选择性合并，通过将表合并与块合并相结合来减少块合并带来的空间放大;(2)并行合并将合并任务划分为多个子任务，使用多个worker并行完成子任务。(3)延迟删除减少了在合并操作的末尾遍历文件所带来的开销。我们基于块合并及其优化实现了一个名为BlockDB的新的键值存储。然后，我们使用YCSB基准将BlockDB与LevelDB、RocksDB和L2SM进行比较。实验结果表明，BlockDB与同类算法相比，最高可降低32%的写放大，最高可降低43.6%的运行时间。此外，它还能保持点查找和范围扫描的高性能。
方法：
本文提出了一种新的合并方法，称为块合并(Block compaction)。与许多key-value存储如LevelDB和RocksDB采用的传统的SSTable-grained compaction(在本文中我们称之为表合并)不同，块合并只读取合并操作涉及的数据块，而不是读取整个SSTable。此外，它只是将数据块添加到sstable中，而不是回写整个sstable。因此，通过采用块粒度的合并单元，块合并可以显著减少写放大。 此外，通过块合并，许多数据块不需要重新构建，这意味着块缓存中的大多数块在块合并后仍然有效。因此，块合并可以缓解LSM-tree合并导致的块缓存失效问题。
二研究内容
1. BLOCK COMPACTION
我们观察到，新的sstable中的许多数据块与合并的sstable中的数据块相同。这意味着表压缩必须写入大量不必要的数据块，这将增加写放大的比例。为了处理这个问题，我们建议采用块粒度单元执行压实操作。
使用这种机制，我们只需要关注受影响的数据块(脏块)，并在合并过程中合并这些块中的键值对。与表合并相比，块合并不需要读写那些未受影响的数据块。因此，它可以显著减少重写数据块的数量，从而减少写放大。此外，块合并还有其他优点。它只重写少量的数据块，这意味着合并后许多数据块在块缓存中仍然有效。因此，可以缓解块缓存失效问题，提高LSM-tree的读性能。由于块合并只读写受影响的数据块，因此不需要创建新的SSTable来进行合并。相反，它会将修改后的数据块添加到底层sstable的尾部。基于追加的写方案可以保证顺序I/ o，充分利用磁盘带宽。为了在修改的sstable中搜索键值对，我们为sstable重建一个新的索引块来定位所有有效的数据块，包括修改的数据块和未受影响的数据块
2 Data Structure
块的压缩过程如图2所示。当Li(父级)已满时，我们在Li中选择一个SSTable，这类似于表合并中的SSTable。我们将它与Li+1(子层)中重叠的sstable合并。对于Li+1中每个重叠的SSTable，根据是否需要重写将其数据块分为干净块和脏块两种类型。
如果一个数据块的key范围可以覆盖所选SSTable中的多个key，我们认为它是一个脏块(例如图2中Li+1中的第一个和第三个数据块)，需要在后面重写。如果没有，则认为它是一个干净的块，我们可以在以后重用它。在合并过程中，对于每个脏块，我们将其加载到主内存中，并将其与所选SSTable中脏块的键范围内对应的键值对合并。然后，我们创建新的数据块，并将合并后的键值对写入SSTable的尾部。对于干净的块，我们不会重写它们。因此，干净的块可以在块缓存中保持有效。在重写所有脏块后，为所有有效数据块建立一个新的索引块，包括旧数据块(如图2中Li+1中的第二个和第四个数据块)和新的数据块。最后，创建一个新的页脚来存储索引块和其他元数据(如布隆过滤器)的偏移量。图2中的例子显示了块合并只需要重写几个数据块而不是整个SSTable
图3显示了我们设计中的索引块的数据结构。索引项由几个字段组成，表示数据块所需的信息。字段键字符串存储数据块中最大的键。Key Size存储了键字符串的长度。Shared Size存储最小键和最大键共享的公共前缀的长度。
3 OPTIMIZATIONS OF BLOCK COMPACTION
正如硬币有两面一样，块合并也会有一些副作用。首先，它会导致额外的空间消耗。在SSTable尾部添加脏块之后，底层所选的数据块将废弃。在最坏的情况下，如果重叠的SSTable中所有的数据块都是脏的，那么块合并将产生与表合并类似的写放大，但会导致2倍的空间开销。其次，在多次块合并操作后，有效数据块随机分布在SSTable中;这对范围查询并不友好。相反，表合并可以在每次合并操作后立即删除废弃的SSTable文件。
在本节中，我们提出三种针对块合并的优化，包括选择性合并、并行合并和延迟删除，以减少副作用并提高块合并的性能。此外，我们还将讨论如何使用布隆过滤器来配置块合并。
1）Selective Compaction
我们注意到，如果重叠的SSTable中的大多数数据块都是脏的，那么块合并也会引起与表合并类似的写放大，但会导致额外的空间开销。因此，我们建议将块合并和表合并结合起来，以充分利用不同级别的特性以及块合并和表合并的优势。
图4显示了选择性合并的主要思想。在一次合并操作中，对于每个重叠的SSTable，我们根据三个参数确定其合并类型，包括脏比率、有效比率和有效大小。下面，我们将给出这些参数的详细信息。
2）Parallel Merging
合并操作可以看作是一个任务。并且，一个任务处理来自两个相邻层(即Li和Li+1)的多个sstable。对于大多数key-value存储(例如LevelDB和RocksDB)，一个任务只由后台线程执行。本文建议利用多线程开发一种并行合并方案，以进一步加速块合并。
图4显示了并行合并的机制。我们在主内存中维护一个线程池和一个工作队列。当Li被填满，并触发一个合并操作时，我们像之前一样识别一个选定的SSTable和多个重叠的SSTable。然后，根据Li+1中重叠sstable的个数，将合并任务划分为多个独立的子任务;然后，我们让一个子任务在Li+1中处理一个重叠的SSTable。
通过这种方式，可以并行执行多个子任务，并利用空闲的CPU资源和存储设备的并行性来加速块合并。
3）Bloom Filter
布鲁姆过滤器用于提高LSM-tree的读取性能。LevelDB和RocksDB总是为新创建的SSTable构建新的布隆过滤器。一旦创建了布隆过滤器，它们将变得不可变。然而，块合并只重写脏块，并将新数据块添加到sstable的尾部。
因此，更新SSTable会导致布隆过滤器的重构，这会产生额外的开销。为了缓解这个问题，在块合并中，我们为布隆过滤器预留了额外的比特位，以减少重构布隆过滤器的开销。首先，当SSTable被创建并构造新的布隆过滤器时，我们为新的布隆过滤器分配一些额外的比特。当新键被添加到SSTable时，我们使用预留的比特位将新键插入到布隆过滤器中。其次，由于保留的比特会带来额外的空间开销，我们建议在LSMtree中为不同的级别保留不同长度的比特。
总结：文中提出的方法集中在对LSM-tree进行块压缩。