Paper Accepted at the Distinguished International Workshop ACM HotStorage (Authors: Lee Hee-rak, Lee Chang-gyu, Lee Seung-jin; corresponding author: Professor Kim Young-jae)

The paper 'Compaction-Aware Zone Allocation for LSM based Key-Value Store on ZNS SSDs', written by Lee Hee-rak (master's), Lee Chang-gyu (combined master's–doctoral) and Lee Seung-jin (master's) of the Department of Computer Science & Engineering under the supervision of Professor Kim Young-jae, has been accepted for publication at the 14th ACM Workshop on Hot Topics in Storage and File Systems (HotStorage '22).

ACM HotStorage is a distinguished international academic workshop for cutting-edge storage research, which reviews submissions for originality, technical merit and the likelihood of leading to insightful discussion that will influence future storage system design and applications. The workshop will be held online from 27 to 28 June this year. (HotStorage site: https://www.hotstorage.org/2022/)

The research proposes a data placement algorithm applicable when running a log-structured merge-tree (LSM-tree) based key-value store on a Zoned Namespace SSD (ZNS SSD). Through precise prediction of when LSM-tree data will be deleted, the proposed placement algorithm effectively reduces the write amplification caused by garbage collection (GC). Specifically, the algorithm reduced the copying of valid data due to GC by about half compared with the existing algorithm proposed in Facebook's RocksDB, lowering maximum write amplification by 7%.

Figure 1 shows compaction, an internal operation of the LSM-tree, and an example of data placement using it. The LSM-tree periodically updates SSTables — data files managed under a hierarchical structure — through the operation known as compaction. Compaction merges SSTables holding overlapping key ranges to create a new SSTable, and the existing SSTables subject to compaction are deleted at the same time. In the example in Figure 1(a), SSTables (A, B, C) are subject to compaction and are later deleted. The Compaction-Aware Zone Allocation algorithm proposed in this research places in the same zone within the ZNS SSD those SSTables that will be selected for compaction together and deleted together in future, on the basis of these characteristics of compaction. Figure 1(b) shows an example in which SSTables (A, B, C) are placed together in Zone0, so that only invalid data remains in that zone later and no copying of valid data due to GC occurs.

Figure 1. LSM-tree compaction and the compaction-aware zone placement technique

References

Paper: https://discos.sogang.ac.kr/file/2022/intl_conf/HotStorage_2022_H_lee.pdf