LLSM: A Lifetime-Aware Wear-Leveling for LSM-Tree on NAND Flash Memory

Dharamjeet, Yi Shen Chen, Tseng Yi Chen, Yuan Hung Kuan, Yuan Hao Chang

Research output: Contribution to journalArticlepeer-review

Abstract

The advancement of non-volatile memory (NVM) technology reduces the cost-per-unit of solid-state drives (SSDs). Flash memory-based SSDs have become ubiquitous because they provide better performance and energy efficiency than hard disk drives. However, it suffers from wear-out problems caused by the out-of-place updates that limit its lifetime. Log-structured merge tree (LSM-tree) is a level-based data structure that is widely used in many database systems because it eliminates the random write operations to the storage devices. By transferring the random write operations into sequential write operations, the write performance of hard disk drives can be improved. However, LSM-tree is not efficient for SSDs because it is not aware of the access characteristics of flash memory. Moreover, the level-based indexing strategy of LSM-tree significantly shortens the lifetime of SSDs because the data must be frequently updated due to the compaction operations between different levels. In contrast to many previous works that focus on alleviating the write amplification on SSDs for the database systems implemented by LSM-tree, we propose LLSM, a lifetime-aware wear-leveling for LSM-tree on NAND flash memory with open-channel SSD. By considering the data access frequency of LSM-tree between different levels, LLSM rethinks the block allocation strategy during the compaction to evenly erase all the blocks of SSD storage devices, prolonging the SSD lifetime. Moreover, a proactive swapping strategy is designed to reorganize the data blocks for resolving the potential wear-leveling issues caused by the behaviors of LSM-tree. The extensive experiments show that the results of lifetime improvement are encouraging.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
DOIs
StateAccepted/In press - 2022

Keywords

  • Ash
  • Behavioral sciences
  • Compaction
  • Data structures
  • endurance
  • Hard disks
  • Information science
  • Lifetime
  • log-structured merge tree (LSM-tree)
  • Metadata
  • NAND flash memory
  • wear-leveling

Fingerprint

Dive into the research topics of 'LLSM: A Lifetime-Aware Wear-Leveling for LSM-Tree on NAND Flash Memory'. Together they form a unique fingerprint.

Cite this