Hi-ZNS: High Space Efficiency and Zero-Copy LSM-Tree Based Stores on ZNS SSDs

The Zoned Namespace (ZNS) interface is a novel storage interface tailored to enhance the performance and lifespan of flash-based SSD devices by organizing data into zones instead of traditional blocks. The ZNS interface provides several new commands to upper-level applications for managing zones and accessing data within ZNS SSDs, including management commands and data transfer commands. As illustrated in Figure  1(a), zone-open command permits an application to explicitly open a zone and indicates to the device that the resources necessary for writing the zone should remain available. zone-close command marks the current open zone as full or read-only, preventing further writes to it. zone-finish allows an application to move a zone's write pointer to the end of the zone, preventing any further write operations to the zone until it is reset. zone-reset command is provided to host software to clean all the data in a zone.

For data transfer commands, write command writes data to the currently open zone following the write pointer. append command is designed to improve the write performance by allowing a host to simultaneously submit several zone write operations and let the device process these in any order. read command reads data from a specific zone in random order. Host interface iogic divides data transfer commands into one or more transactions in the unit of flash-page size and inserts the transactions into the device-level queue.

Compared with traditional block-interface-based SSDs, the ZNS interface divides the logical address space into several fixed-size zones as shown in Figure 1(a). Each zone is equipped with a write pointer to monitor the position of the next write and sequential writes are enforced within the zone [18] [17] [3] [20]. The zone capacity denotes the total number of logical blocks within a zone, which is always smaller than or equal to the zone size.

Figure 1(a) also shows a zone physical view from flash media. Generally, each ZNS SSD device contains several flash chips, with each chip comprising multiple flash blocks. Each block consists of multiple pages, which is the basic unit of data storing and fetching [10] [5] [22]. In ZNS SSDs, a zone consists of multiple flash blocks, which span across multiple flash chips to take advantage of chip-level parallelism. For example, as shown in Figure 1(a), zone #0 consists of flash blocks (block offset 0 to 4) from all flash chips, zone #1 consists of flash blocks (block offset 5 to 9) from all flash chips. Currently, there are no restrictions to construct a zone using flash blocks in the ZNS specification, which opens design space for different configurations [7] [14]. In this paper, Hi-ZNS utilizes a novel method to construct a zone in the device to improve the space efficiency of ZNS SSDs.

A log-structured merge tree (LSM-tree) is a data structure designed to efficiently store key-value pairs for retrieval in disk- or flash-based storage systems. LSM-tree optimizes both read and write operations through a blend of in-memory and disk-based structures. As shown in Figure 1(b), incoming data is initially stored in an in-memory structure known as a memtable, serving as a temporary sorting area. As the memtable reaches capacity, its contents are flushed to disks in a batch of sorted data structures referred to as Sorted String Tables (SSTables/SSTs). SSTs form the core of the LSM-tree, organizing data in sorted order to facilitate efficient queries and range scans. Each SST file represents a snapshot of data at a specific moment in time. To optimize data management, SST files are arranged into levels (refer to L0, L1, L2 to Ln). Lower levels contain more recent data and higher levels house compacted data. This hierarchical approach ensures a balance between read and write performance, averting potential bottlenecks.

There are numerous well-known examples of the LSM-tree, including Apache Cassandra, RocksDB, LevelDB, HBase, Couchbase, and more. We choose RocksDB as the experimental subject to investigate the performance of LSM-tree on ZNS SSDs. RocksDB [6] is a high-performance, persistent key-value storage engine optimized for the specific traits of flash media, catering to large-scale (distributed) applications. In this paper, Hi-ZNS mainly focuses on enhancing performance during flushing SST files to ZNS SSDs.

RocksDB is a good fit for ZNS SSDs [9] [23] [15]. ZenFS [2] is a file system plugin that utilizes RocksDB's filesystem interface to place files into zones on a raw zoned block device. As shown in Figure 1(b), ZenFS builds a bridge between LSM-tree-based stores and ZNS SSDs. By employing lifetime hints to co-locate SST files with similar lifetimes into the same zone, ZenFS significantly mitigates system write amplification compared to conventional block-interfaced-based SSDs [2]. Furthermore, ZenFS eliminates background garbage collection within the file system or on the ZNS SSD device, thereby enhancing performance in terms of throughput, tail latencies, and device endurance. In this paper, Hi-ZNS extensively investigates the zone allocation strategy of ZenFS and integrates it with the characteristics of ZNS SSDs to enhance space utilization and minimize data migration for LSM-tree-based stores (such as RocksDB) on ZNS SSDs.

The ZNS interface provides a new zone-reset command for upper applications to erase all the flash blocks within a zone, which could reclaim the zone space for rewriting new data. That is to say, compared with the traditional block-interface SSDs, the erase unit of ZNS SSDs is a zone, not a flash block. Therefore, ZNS SSDs aim to group the data with a similar lifetime into a single zone. Once the data in the same zone is invalid, ZNS SSDs reset the zone directly without the need to move and rearrange data.

Figure 4(a) shows the expected situation, in which all data within a zone is invalid data. However, in reality, invalid data and valid data are always mixed together in a zone as shown in Figure 4(b), which makes a zone fail to be reset directly. With the invalid data increasing and the free space decreasing, upper applications would start garbage collection (GC) to reclaim zone space for writing the next SST/WAL files. Figure 4(c) shows the GC process, which migrates valid data (L1) from zone #1 to zone #n then reset zone #1. The next SST/WAL files would be written to zone #1. Furthermore, when a zone contains a large amount of valid data (as shown in Figure 4(d)), data migration will cause huge overhead. If invalid data resides in a zone for a long time, the occupied space fails to be reused until the zone is reset, which is called space amplification.

To illustrate data migration and space amplification of LSM-tree on ZNS SSDs, we evaluate six different workloads as shown in Figure 2. The detailed configurations of the ZNS SSDs and the experimental method are described in Section 5. In Figure 2, ValidData means the total volume of valid data in all the zones, InvalidData means the total volume of invalid data that still resides in all the zones, and Data Migration means the total volume of data migration at all the GC processes. Due to the placement of multiple SST or WAL files within the same zone, these files can not be invalidated simultaneously, resulting in garbage data occupying the zone space and lowering the space efficiency. Furthermore, the accumulation of garbage data results in extensive data migration during garbage collection of ZenFS, which reduces the I/O throughput of RocksDB.

Although RocksDB provides the lifetime hints of SST/WAL files to ZenFS for grouping data with the same lifetimes in a zone, ZenFS still faces the following problems in reality: (1) coarse-grained lifetime hints inaccurately separate data. For instance, at LSM-tree high levels (above L3), SST files have the same lifetime hint but do not have the same lifetime. Combining data from different lifetimes within a zone postpones the zone being reset, leading to low space efficiency and the need for extensive data migration during the compaction process. (2) ZenFS employs a lifetime-hint-based strategy that permits a zone to store data with a lower lifetime-hint value instead of strictly requiring the lifetime-hint to be equal. The write-ahead-log (WAL) files, which are considered the hottest data with a low lifetime-hint value, are frequently mixed with SST files within the same zone, further exacerbating space amplification and data migration problems.

An effective approach for maintaining a consistent data lifetime within a zone is to place only one SST/WAL file per zone while ensuring that the sizes of these files match the zone size to maximize space utilization. RocksDB offers two parameters to manage the SST/WAL file size: "TargetFileSizeBase" limits the file size, while "TargetFileSizeMultiple" scales up the file size.

We conducted experiments with the two parameters, as the detailed setting in Table 1. With a zone size of 512MB and the expected SST/WAL file size of 512MB (TargetFileSizeBase=512MB, TargetFileSizeMultiple=1), the results unfortunately indicate that only a fraction of the created SST and WAL files adhere to the intended size, with numerous SST files deviating significantly from the desired 512MB, as illustrated in Figure 3.

Therefore, we find that the zone size is always much larger than the SST/WAL file size, which allows multiple SST/WAL files to be stored in the same zone. As time passes, this mismatch results in a zone partially invalidated and fragmented, causing low space efficiency and extensive data migration within a ZNS SSD device. In this paper, we propose a novel mechanism to solve the two problems.

Figure 6 shows an overview of Hi-ZNS. Upper applications send Get, Put, Delete commands to LSM-tree-based stores (such as RocksDB, LevelDB,...) for reading, writing, and deleting key-value pairs on ZNS SSDs. Hi-ZNS spans ZenFS and ZNS SSDs to ensure the efficiency of data access.

At the ZNS SSD device level, Hi-ZNS utilizes Strip to manage the flash resources. A Strip consists of only one flash block (block offset 0) from all flash chips, which is a more fine-grained resource management method compared with the traditional zone-based method. Strip Allocator resides in a ZNS SSD device to record the valid/invalid status of all the strips. Due to Hi-ZNS mapping strips to a zone at runtime, Zone mapping table records the mapping between the logic zone number and the strips.

At ZenFS level, since the zone size is not equal to the space that is mapped to the specific flash blocks in Hi-ZNS, Device Capacity Maintainer records the actual available capacity of the ZNS SSD device. Zone Management is a modified module of ZenFS to provide an infinite logic zone number for ensuring that all the strips are used.

Hi-ZNS dynamically constructs a physical zone on demand. As shown in Figure 7(a), initially, a logical zone is in the empty state and is not mapped to any strips within the device. When an SST/WAL file targets the zone, Hi-ZNS circularly allocates strips to the zone one by one at runtime. Once the SST/WAL file writing is finished, the zone is constructed by several strips, and the corresponding mapping information is recorded in the zone mapping table as shown in Figure 6.

Strip is the allocated unit of Hi-ZNS. However, an SST/WAL file size is not always strictly aligned with the strip size. Consequently, when an SST/WAL file is written to a zone, a small portion of the last strip is not used, as illustrated in Figure 7(c). We regard it as "fragment". We will discuss the fragment in Section 4.5 and evaluate it in Section 5.

Hi-ZNS discards the lifetime hints that are from RocksDB. Upon writing an SST/WAL file, Hi-ZNS allocates a new empty logic zone to hold the file. When the SST/WAL file is written finished, the zone state transitions to full, which is defined by the ZNS specification and means a zone has been finished by the host using the zone-finish command. It ensures a zone only containing an SST/WAL file at ZenFS level, and the zone can be reset immediately without any data migration once the SST/WAL file is invalidated. For other types of files, Hi-ZNS simply puts them to the same zone because their size is too small.

Hi-ZNS utilizes a zone to store an SST/WAL file and determines the actual zone mapping table at run time according to the SST/WAL file size. However, the SST/WAL file size is uncertain as illustrated in Figure 3. When these uncertain-size files are placed into the zones, each zone might be allocated to a different number of strips. Therefore, Hi-ZNS could not determine the exact number of strips for each zone in advance.

To ensure the full use of the strips in a ZNS SSD device, Hi-ZNS regards the logical zone number as infinite. As long as the strip remains, the logical zone number could continue to increase to use these strips. Hi-ZNS maintains the remaining number of strips using Device Capacity Maintainer. At initialization, Hi-ZNS sends the "zbd report" command to the ZNS SSD device to get two parameters: (1) total capacity of the ZNS SSD device, (2) strip size. After that, Hi-ZNS maintains the number of the available strips by zone-finish and zone-reset commands, which are from the ZNS specification.

Hi-ZNS utilizes strip as the basic unit to construct a zone. To leverage the internal parallelism of ZNS SSDs, a strip is composed of multiple flash blocks that are from different flash chips. In this paper, we mainly consider the chip-level parallelism within a ZNS SSD device. Each strip has a "width" attribute, which corresponds to the number of flash blocks it contains. As shown in Figure 6, the width of the strip is M, and the full chip-level parallelism also is M. Hi-ZNS has two typical configurations to form the strip, including the full-parallelism strip and the partial-parallelism strip, as shown in Figure 8.

Full-parallelism strip. The strip width is equal to the total number of flash chips in a device, allowing each strip to utilize the full parallelism of the device. Full-parallelism strip has a larger capacity but tends to generate a larger fragment. This is because that Hi-ZNS allocates strips on-demand at runtime and a smaller strip makes it easier to match SST/WAL file sizes. Although full-parallelism strips result in an increase in the total size of the fragment, it still boosts the space efficiency without decreasing the I/O performance (Section 5).

Partial-parallelism strip. The strip width is less than the total number of flash chips in a device, indicating that each strip can only exploit a portion of the device's parallelism. As shown in Figure 8, partial-parallelism strips have a smaller size and could reduce the fragment size because it is easier to match SST/WAL file sizes. However, the partial-parallelism strip sacrifices parallelism and decreases the I/O performance of a ZNS SSD device. Therefore, Hi-ZNS utilizes the full-parallelism strip to construct a zone at first. Then, we discuss the partial-parallelism strip in section 5.

We implement Hi-ZNS based on FEMU, which is a full I/O stack simulator. Table 1 shows the configuration of the target ZNS SSD device. The benchmark tool, $db\_bench$ in RocksDB, is used to generate different workloads for evaluating the effectiveness of Hi-ZNS. The parameters used by $db\_bench$ are detailed in Table 1. For the generating combined workloads, fillseq and fillrandom use the "num" parameter to set 6 million and 12 million, respectively. These two workloads initialize the write data into the device to serve for running overwrite and updaterandom workloads. For instance, the fillseq+overwrite workload entails initially executing fillseq to fill 6 million requests, followed by the overwrite workload with a "num" parameter of 50 million.

To simplify the notation, we adopt abbreviated forms. Specifically, "fillseq+overwrite" is shortened to "seq+ow", "fillseq+updater-

andom" is shortened to "seq+up", "fillrandom+overwrite" is shortened to "ran+ow", and "fillrandom+updaterandom" is shortened to "ran+up". Additionally, we also add the garbage collection (GC) thread to observe whether data migration exists in Hi-ZNS. It is worth noting that previous researches all have data migration. Therefore, we mainly evaluate RocksDB over ZenFS with/without GC.

As shown in Figure 9, Hi-ZNS shows the highest space efficiency under the six different workloads. The efficiency of Hi-ZNS is achieved through reset zone immediately upon deletion of SST/WAL files, ensuring timely release of occupied space previously taken by garbage data. During the running process of the six workloads, the amount of garbage data retained within Hi-ZNS is negligible (maximum of 1.7MB), which is from small files like DBTMP, MANIFEST, and CURRENT. These files reside in the same zone and do not directly trigger a zone reset upon deletion. Therefore, the GC thread in Hi-ZNS would not migrate any data.

Figure 9 also demonstrates that Hi-ZNS could store more valid data in a ZNS SSD device with identical storage capacity. Furthermore, as shown in Figure 9, ZenFS (GC Enabled) always stops running early because much garbage data can not be collected. Hi-ZNS could extend the running time to write more data into a ZNS SSD device. This is because Hi-ZNS resets the zone immediately after the SST/WAL file is deleted, thereby freeing up space for storing new SST/WAL files more quickly. Therefore, Hi-ZNS substantially improves space efficiency.

Figure 10 shows the number of completed requests. Hi-ZNS with exceptional space utilization efficiency allows the ZNS SSD device to accommodate a larger volume of write operations, resulting in a significant enhancement in the total number of requests that can be processed in RocksDB. Compared to ZenFS without garbage collection, Hi-ZNS shows a substantial improvement in the number of completed requests. Under the workloads of fillseq, fillrandom, seq+ow, seq+up, ran+ow, and ran+up, the respective improvements are 2.16x, 1.76x, 2.97x, 2.96x, 2.28x, and 2.84x. Furthermore, when ZenFS enables garbage collection, it incurs data migration as a trade-off to complete more write requests. The volume of the data migration in ZenFS with GC is 17GB, 108GB, 126GB, 166GB, 104GB, and 118GB under the six workloads. Note that although ZenFS with GC improves the number of completed requests, Hi-ZNS still significantly outperforms it in all the workloads.

To evaluate the I/O performance of Hi-ZNS, we conduct experiments comparing to the existing ZenFS, including ZenFS without GC, and ZenFS with GC. Due to the varying number of completed requests among Hi-ZNS, ZenFS, and ZenFS with GC, we use the segmented method to ensure the consistency of the key range and key distribution. For instance, in the "fillrandom" workload, the ’num’ parameter in db_bench is consistently set at 50 million. However, ZenFS without GC could only complete up to 19.5 million requests. Therefore, we evaluate the throughput which is the average of requests ranging from 0 to 19 million. Similarly, other workloads follow this testing method. The results of the I/O performance are illustrated in Figure 11.

In the comparison of Hi-ZNS and ZenFS without GC (Figure 11(a)), the I/O performance of both was nearly identical across most workloads. This is because Hi-ZNS can fully leverage the device's parallelism by taking full-parallelism strips to reconstruct a zone, ensuring no decrease in I/O performance.

In the comparison of Hi-ZNS and ZenFS with GC (Figure 11(b)), Hi-ZNS exhibits marginal improvements in each workload. Specifically, it shows improvements of 2.5% (fillseq), 4.1% (fillrandom), 4.3% (seq+ow), 5.4% (seq+up), 4.7% (ran+ow), and 7.0% (ran+up) compared to the baseline performance. The performance improvement is due to ZenFS's GC thread conducting data migration. Although Hi-ZNS also engages a GC thread, it performs no data migration, resulting in superior I/O performance.

In our simulated ZNS SSD device (Table 1), there are 8 channels and 2 chips in each channel (totaling 16 flash chips). In this study, the full-parallelism strip comprises 16 flash blocks sourced from these 16 flash chips. Each flash block has a capacity of 1MB, calculated by multiplying the page capacity (4KB) by the page count of a block (256). We discuss the performance among the full-parallelism strip (16M), the semi-parallelism strip (8M), and the one-fourth-parallelism strip (4M).

Figure 12 shows the fragment rate of these three strips under the six workloads. As described in Section 4, a strip with a smaller size could decrease the fragment rate because it is easier to match SST/WAL file sizes. We also find that the fragment rate of Hi-ZNS remains a low (2.5%-3.9%) rate across most workloads even with the full-parallelism strip (16M). However, fillseq shows an interesting phenomenon, which has the highest fragment rate (27.4%) with the full-parallelism strip. In reality, fillseq workload is unlikely to occur because it is a completely sequential access behavior. Furthermore, even though fillseq workload with the full-parallelism strip faces a higher fragment rate, the one-fourth-parallelism strip can lower the fragment rate to 3.2

Figure 13 shows the throughput of these three strips under the six workloads. The full-parallelism strip could utilize the full parallelism of the device and achieve the highest throughput. Comparing with the semi-parallelism strip and the one-fourth-parallelism strip, the full parallelism improves I/O performance by 12.9% and 40.1%(fillseq), 11.9% and 25.6% (fillrandom), 7.3% and 27.7% (seq+ow), 2.2% and 14.9% (seq+up), 15.3% and 28.1% (ran+ow), 8.5% and 22.6% (ran+up). Similarly, fillseq workload has the highest throughput due to its completely sequential access behavior.

Figure 14 shows the number of completed requests under the six workloads. Most workloads have a similar completed request except fillseq. There's still a little confusion. We believe that the smaller fragments will complete more requests. However, for seq+ow, the completed requests under the semi-parallelism strip (8M) are more than the one-fourth-parallelism strip (4M). We guess that (1) 8M strips and 4M strips already have high space utilization and the dropped fragment rate is so small (about 0.9%). (2) it is hard to guarantee that the running environment is consistent completely from software to hardware (such as different seeds). Due to these workloads with a similar completed request, we recommend using the full-parallelism strip as much as possible from the perspective of performance and fragment.

Let's consider an extreme scenario where the host continually expands the logical zone number and only writes a small-sized SST/WAL file into each zone. This leads to each zone only being mapped to one strip until the device is filled. Eventually, the number of logical zones becomes equal to the total number of strips in a ZNS SSD device, causing the mapping table to expand to its maximum size. Each zone item in the mapping table has a base size of 8 bytes, and each strip requires an 8-byte pointer for locating. In this paper, we simulated a 128GB ZNS SSD and estimated the actual size of the mapping table to be 128KB (8192 * (8B + 8B)), which occupies a mere 0.00009% of the total device capacity. In practice, the mapping table overhead is typically much lower than this value since such extreme scenarios are highly unlikely to occur.

The new emerging ZNS interface divides the logical address space into multiple zones and provides a serial new command to upper-level applications to operate these zones. Compared with the traditional block interface, the ZNS interface is more friendly to flash media. Currently, several recent studies deploy efficient space management from upper-level applications to optimize the performance of LSM-tree-based stores (like RocksDB [6]) using these new ZNS commands. Furthermore, ZenFS [2] is a file system plugin that utilizes RocksDB's file system interface to place files into zones on a raw-zoned block device. In ZenFS, zone allocation strategies are based on the lifetime hint provided by RocksDB. Files with the same lifetime hint are prioritized to be placed within the same zone. Compared to random file placements, this strategy ensures that data within a zone has a more uniform lifetime, accelerating zone reclaims and garbage data cleanup. In this paper, we use $db\_bench$ in RocksDB to generate different workloads, to evaluate the effectiveness of Hi-ZNS.

Since files with the same lifetime hint do not always have closely aligned lifetimes [9], ZenFS still encounters space amplification and frequent garbage collection issues. To alleviate these issues, several researches primarily concentrate on distinguishing the lifetimes of SSTs in some fine-grained manners [11] [16] [12] [11], aiming to allocate data with similar lifetimes to the same zone. ZoneKV [16] utilizes a lifetime-based zone storage model and a level-specific zone allocation algorithm to store data to reduce space amplification and maintain higher throughput. Lee et al. [12] propose a novel compaction-aware zone allocation algorithm to co-locate data with overlapping key ranges in the same zone, thus providing a more precise prediction of SSTable lifetimes. LL-Compaction [11] proposes a lifetime-leveling Compaction algorithm for LSM-tree on ZNS SSDs, which allocates dedicated zones for each level since different levels have different lifetime SSTs and avoids mixing long-lived SSTs and short-lived SSTs in the same zone. Unfortunately, it is hard to put the same lifetime SST/WAL files into a zone perfectly and fail to completely eliminate data migration.

A small zone configuration means the zone size is as small as possible. Due to the smaller zone size, a file would easily fill the entire zone and the data within the small zone has a higher possibility to be invalidated at the same time. When zone-reset commands arrive, ZNS SSD devices can directly erase all the flash blocks within the small zones without redundant data migration. Small zone configurations are better than large zone configurations as large zones can reduce the degree of freedom for upper-level application data placement. Hanyeoreum et al. [1] focus on analyzing the challenges of ZNS using small zones and studies a simple, but efficient scheduling mechanism to improve the parallelism by being aware of inter-zone interference. SplitZNS [9] introduce small zones by adjusting the zone-to-chip mapping to enhance garbage collection efficiency for LSM-trees on ZNS SSDs. Capitalizing on the multi-level nature of LSM-trees and the inherent parallel architecture of ZNS SSDs, SplitZNS proposes several techniques to harness and expedite small zones, thereby mitigating the performance impact resulting from underutilized parallelism. FlexZNS [21] provides reliable zoned storage allowing host software to configure the zone size flexibly as well as multiple zone sizes to reduce the overhead of data migrations during zone garbage collection. Han et al.[8] propose a new checkpoint scheme based on ZNS SSDs with small zones, which could reduce interference when multiple dockers perform checkpoints concurrently by workload separation and performance isolation.

However, a small zone configuration fails to fully exploit the multi-level parallelism inherent in flash media, leading to diminished read and write performance of ZNS SSDs. Furthermore, the small zone configuration still could not completely eliminate data migration, because the zone size is fixed and always fails to align the varying SST/WAL sizes. In this paper, Hi-ZNS leverages the full parallelism of flash media to reconstruct a zone and allocate the resources on demand, which guarantees both high access performance and space efficiency.