Research On LSM-tree Key-value Store Based On High-density SSD

The Log-Structured Merge-tree(LSM-tree)based key-value(KV)store is widely employed in write-intensive workloads due to its excellent write performance.As NAND Flash technology moves toward higher storage densities,the operation units of NAND flash are becoming larger and the capacity of NAND flash-based SSD is also increasing.On the one hand,a larger SSD requires a deeper LSM-tree on it,and more KV data is stored in each level of the LSM-tree.Hence,higher read and write amplification is caused.On the other hand,larger operation units in SSD make the existing software and hardware collaborated designs less effective.Storing an SSTable in a flash block may not take full advantage of the internal parallelism of SSD,and setting an SSTable to the size of a super-block(containing multiple flash blocks)will cause compaction to involve more data migration.To address the above issues,we propose m LSM,a flash-aware LSM-tree-based keyvalue store running upon high-density SSD.There are mainly three key designs included in m LSM.First,m LSM adopts multiple LSM-trees to manage high-density SSD.KV data is distributed to each LSM-tree through the source address hash algorithm,which helps to limit the depth per tree and reduce the amount of data involved in every single compaction,thus reducing read and write amplification.Second,m LSM employs the parallel data layout to store one SSTable in a super-sub-block(a superblock contains more than one super-subblock),avoiding the excessive overhead of every single compaction.Besides,the super-subblock spans all the flash chips,so as to utilize the multi-level parallelism of SSD.Third,a lazy garbage collection strategy(Lazy GC)is proposed to reduce write amplification.By delaying garbage collection,more data in the victim block becomes invalid,thus reducing data migration.We demonstrate the advantages of m LSM with both YCSB workloads and db?bench workloads.YCSB workloads results show that,compared with the conventional LSM-treebased KV stores(LSM),m LSM optimizes the read and write amplification by up to 75.95%and 88.74%,respectively,and the throughput is improved by 1.84× to 2.47×.Compared with Flash KV,the read and write amplification of m LSM is reduced by up to 95.41% and81.64%,respectively,and the throughput is improved by 1.56× to 3.01×.Under db?bench workloads,m LSM reduces the read/write/erase counts of flash by up to85.21%/87.44%/91.38% and 84.73%/86.76%/91.11%,respectively,compared with LSM and FlashKV.