Compaction-Aware Flash Memory Remapping for Key-Value Stores.

Area of Science:

• Computer Science
• Data Storage Systems
• Database Management

Background:

• Log-Structured Merge Trees (LSM-trees) are crucial for efficient writing in key-value stores, widely used in systems like LevelDB and RocksDB.
• LSM-tree compaction, while necessary, causes significant write amplification, degrading performance and SSD endurance.
• Unchanged data blocks (UDBs) are frequently rewritten during compaction, leading to unnecessary I/O and performance bottlenecks.

Purpose of the Study:

• To introduce RemapCom, a novel KV store design for SSDs that addresses write amplification in LSM-tree compaction.
• To exploit the remapping of unchanged data blocks (UDBs) to improve I/O performance and SSD endurance.
• To reduce the performance degradation and write amplification inherent in traditional LSM-tree compaction processes.

Main Methods:

• RemapCom identifies UDBs using a lightweight state machine integrated into the LSM-tree compaction merge process.
• A UDB retention method is employed to maximize the benefits of remapping and further reduce write amplification.
• A prototype of RemapCom was implemented on LevelDB, incorporating two primitives for data remapping.

Main Results:

• RemapCom effectively reduces write amplification by up to 53% compared to state-of-the-art methods.
• The proposed approach improves write throughput by up to 30% in LSM-tree-based KV stores.
• Identification and remapping of UDBs significantly enhance I/O performance and SSD endurance.

Conclusions:

• RemapCom offers a practical solution to mitigate write amplification in LSM-tree compaction by intelligently handling unchanged data blocks.
• The proposed remapping strategy provides substantial performance gains, making it a valuable optimization for modern key-value stores.
• RemapCom demonstrates the potential of exploiting data block stability within LSM-trees for improved storage system efficiency.