The 32nd International Symposium on the Modeling, Analysis, and Simulation of Computer (MASCOTS) 2024

Paper Accepted at an Outstanding International Conference

(Joint first authors: Hwangbo Ha-min and Noh Yo-seph; corresponding author: Professor Kim Young-jae)

▶ (From left) Hwangbo Ha-min, master's student; Noh Yo-seph, master's student; Byeon Seong-jin, master's student; Safdar Jamil, doctoral student

The paper 'Towards A Unified Garbage Collection Strategy in ZNS Key-Value Store File Systems Using Same-Victim GC', written by Hwangbo Ha-min and Noh Yo-seph (joint first authors), Byeon Seong-jin (master's) and Safdar Jamil (doctoral) of the Data-Centric Computing and Systems Laboratory with Professor Kim Young-jae (corresponding author), has been accepted for publication at The 32nd International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS '24).

The research proposes a technique for reducing the write amplification that increases when a log-structured merge-tree (LSM-tree) based key-value store is run on a Zoned Namespace SSD (ZNS SSD). In particular, it analyses BlobDB, proposed to resolve the compaction problem of existing LSM-tree based key-value stores such as RocksDB. It also analyses ZenFS, RocksDB's well-known user-level file system, and points out the problems of the BlobDB-ZenFS system.

Unlike traditional key-value stores, BlobDB first writes blob files containing only values in an append-only fashion and stores keys together with pointers to the values in SST files. BlobDB therefore additionally performs BlobGC, which reclaims invalidated values in blob files. Because BlobGC runs, the BlobDB-ZenFS system faces a GC-over-GC (GoG) situation in which two separate garbage collectors operate on blob files. To see how the composition of the two collectors' victims affects the system, the research first divides the relationship between the two victim sets into four cases and analyses each.

▲ Analysis of the four relationships according to the composition of the two collectors' victims

The analysis found that case (a) does not occur, and that in cases (b) and (c) the elements and sizes of the victim sets do not match, causing write amplification and unnecessary compaction overhead. In case (d), by contrast, no write amplification occurs and compaction overhead can also be reduced optimally. The research names this relationship Same-Victim GC and argues that the BlobDB-ZenFS system should perform Same-Victim GC.

To achieve Same-Victim GC, the research proposes Blob-Aware Zone Allocation (BAZA) at the file system level and Z_cutoff at the key-value store level. Both algorithms are designed from a close analysis of how each garbage collector works in the BlobDB-ZenFS system and achieve near-optimal Same-Victim GC. BAZA thereby eliminates the write amplification of zone cleaning (ZenFS's GC), and Z_cutoff doubles compaction performance. The two algorithms also improve the space utilization of the ZNS SSD by 1.28 times.

▲ Evaluation of file system GC efficiency under Same-Victim GC.

IEEE MASCOTS is a distinguished international conference for the latest research on measurement, modeling and analysis across a range of computer systems fields. This year's MASCOTS had an acceptance rate of 25%. The conference will be held in Krakow, Poland, from 21 to 23 October this year. MASCOTS is also listed among the outstanding conferences in the software field of the Korean Institute of Information Scientists and Engineers and among the outstanding international conferences in computer science under the BK21 Plus programme (BK IF=2).

References:

Conference: https://mascots24.iitis.pl/

Paper: to be added later