In Search of Optimal Data Placement for Eliminating Write Amplification in Log-Structured Storage

Qiuping Wang, Jinhong Li, Patrick P. C. Lee, Guangliang Zhao, Chao Shi, Lilong Huang

Abstract

Modern log-structured storage systems suffer from significant performance degradation and hardware wear due to write amplification (WA). This paper introduces SepBIT, a novel data placement scheme designed to minimize WA by predicting Block Invalidation Times (BIT). By leveraging the inherent write skewness found in large-scale cloud workloads, SepBIT groups blocks with similar predicted lifespans into distinct segments. This approach reduces the amount of live data moved during garbage collection (GC) by up to 20.2% and increases system throughput by 20% compared to existing state-of-the-art methods. SepBIT is currently deployed in production at Alibaba Cloud.

Introduction

Log-structured storage is a cornerstone of modern SSDs and cloud block services, converting random write patterns into sequential appends to improve performance. However, this design necessitates Garbage Collection (GC) to reclaim space from invalidated data. When a segment is reclaimed, any remaining "live" data must be rewritten to a new location, leading to Write Amplification (WA). High WA not only consumes I/O bandwidth but also accelerates the wear of flash-based storage media.

The optimal solution for eliminating WA is to group data that will be invalidated at the same time. If a segment contains only blocks that "die" simultaneously, GC can reclaim the entire segment without moving any live data. The primary challenge lies in predicting the future: determining exactly when a block will be invalidated (its Block Invalidation Time, or BIT).

System Architecture

SepBIT moves away from traditional "temperature-based" placement—which groups data by update frequency—to a "BIT-based" approach. The architecture integrates directly into the data placement and GC workflow of log-structured systems.

High-level architecture of SepBIT's data placement and garbage collection workflow.

As shown in the architecture, incoming user-written blocks and blocks rewritten by the GC are processed through a placement engine. This engine assigns blocks to specific segments based on their predicted BIT. By maintaining separate streams for different data types, the system ensures that short-lived data does not fragment segments containing long-lived data.

Dual-Stream Inference Logic

The core innovation of SepBIT is its dual-stream inference mechanism, which treats user writes and GC rewrites as distinct categories with different predictive markers.

Dual-stream inference logic for predicting block invalidation times (BITs) for user and GC writes.

User-Written Blocks

For new user writes, SepBIT employs a "short-lived vs. long-lived" heuristic. It tracks the lifespan of the block previously occupying the same Logical Block Address (LBA). If the previous block had a short lifespan, the system infers that the new write is also likely to be short-lived. This capitalizes on the temporal locality and repetitive patterns inherent in cloud workloads.

GC-Rewritten Blocks

For data being moved during garbage collection, the system uses the block's "age" (the time elapsed since its last user write) to infer its residual lifespan. The authors observed that older data is statistically more likely to remain valid for a longer period. Consequently, older blocks are placed into specialized "cold" storage classes to prevent them from being frequently moved by subsequent GC cycles.

Implementation and Memory Efficiency

To remain viable for production environments, SepBIT utilizes a lightweight tracking mechanism. Rather than maintaining a full mapping table for every LBA—which would be prohibitively memory-intensive—it uses a monotonic timer and a dynamic FIFO queue to track only the most recently written addresses. This design reduces memory overhead by over 70% compared to traditional tracking methods.

Evaluation and Results

The researchers evaluated SepBIT using massive production traces from Alibaba Cloud (1,000 virtual disks over one month) and Tencent Cloud (5,000 volumes over nine days).

Key findings include:

  • WA Reduction: SepBIT reduced write amplification by 8.6% to 20.2% on Alibaba traces compared to industry-standard Greedy and Cost-Benefit algorithms.
  • Throughput Gains: In prototype testing on a ZenFS-based system with Intel Optane memory, SepBIT achieved 20% higher median throughput by reducing the background I/O load required for GC.
  • Workload Skewness: The system effectively turned the high skewness of real-world workloads (where a small percentage of LBAs receive the majority of writes) into a predictive advantage.

Conclusion

SepBIT demonstrates that predicting invalidation times is a more effective strategy for data placement than simply tracking update frequency. By separating user and GC write streams and using age-based heuristics, the system significantly mitigates the "GC tax" in log-structured storage. Its successful deployment at Alibaba Cloud underscores its practical utility in large-scale cloud infrastructure.

Summary updated

BibTeX
@inproceedings{wang2022search,
  author = {Qiuping Wang and Jinhong Li and Patrick P. C. Lee and Guangliang Zhao and Chao Shi and Lilong Huang},
  title = {{In Search of Optimal Data Placement for Eliminating Write Amplification in Log-Structured Storage}},
  booktitle = {Fast},
  year = {2022},
}
Figure