We use cookies to improve your experience with our site.

dCompaction:基于延迟的日志结构合并树的合并方法

dCompaction: Speeding up Compaction of the LSM-Tree via Delayed Compaction

  • 摘要: 键值存储系统在当今互联网应用中发挥着巨大的作用。写优化的数据结构,例如日志结构合并树以及它的变种,被广泛应用于各类键值存储系统中,如Bigtable,RocksDB等。传统的日志结构合并树通过两层有序数据集或者多层有序数据集对索引变更进行延迟及批量处理,并通过类似于归并排序的方式高效地将磁盘上的多个有序数据集进行合并,而在多层合并过程中会由于大量键值对重复读写引发写放大问题,导致性能下降。本文针对合并过程中的写放大问题,提出了一种新的合并方法—dCompaction,其核心思想是通过延迟调度部分合并操作方式,来减少合并过程中的键值对重复读写的问题,从而提升了系统的吞吐率。本文以RocksDB为原型在其上实现了dCompaction策略,并利用YCSB进行大量的测试,其结果表明与RocksDB相比,dCompaction在保持读性能不变的情况下,写性能提升40%左右。

     

    Abstract: Key-value (KV) stores have become a backbone of large-scale applications in today's data centers. Writeoptimized data structures like the Log-Structured Merge-tree (LSM-tree) and their variants are widely used in KV storage systems like BigTable and RocksDB. Conventional LSM-tree organizes KV items into multiple, successively larger components, and uses compaction to push KV items from one smaller component to another adjacent larger component until the KV items reach the largest component. Unfortunately, current compaction scheme incurs significant write amplification due to repeated KV item reads and writes, and then results in poor throughput. We propose a new compaction scheme, delayed compaction (dCompaction) that decreases write amplification. dCompaction postpones some compactions and gathers them into the following compaction. In this way, it avoids KV item reads and writes during compaction, and consequently improves the throughput of LSM-tree based KV stores. We implement dCompaction on RocksDB, and conduct extensive experiments. Validation using YCSB framework shows that compared with RocksDB, dCompaction has about 40% write performance improvements and also comparable read performance.

     

/

返回文章
返回