Abstract:

Key-value stores based on LSM-Tree have been widely used.LSM-Tree gains excellent write performance by collecting updated data in memory and then flushing data into storage in batches.However, in LSMTree-based key-value stores, old data generated by update operations will not be eliminated immediately from the storage system, resulting in a large amount of invalid data accumulated in the entire storage system, which will eventually significantly reduce the read performance of key-value stores.For the above problems, an active compaction method was proposed.By recording the history information of updated key-value pairs, recognizing hot-updated keys, finding SSTables that contain a large amount of invalid data in the storage system, and triggering compaction as soon as possible to clear much more invalid data, the proposed method could reduce write amplification and improve the read performance of LSM-Tree based key-value stores.Experiments showed that this method could reduce the average read latency of LevelDB by 65.2%, 99% read tail latency by 69.4%, and write amplification by 71.4%.

Key words: key-value stores, log-structured merge tree, read performance optimization, write amplification