Separating Data via Block Invalidation Time Inference for Write Amplification Reduction in Log-Structured Storage

Qiuping Wang, Jinhong Li, Patrick P. C. Lee, Tao Ouyang, Chao Shi, Lilong Huang

TL;DR

Modern log-structured storage systems suffer from write amplification (WA) due to garbage collection. This paper introduces SepBIT, a novel data placement algorithm that infers the Block Invalidation Time (BIT) of data blocks to group them by their expected lifespan. By intelligently separating data based on these inferred BITs, SepBIT significantly reduces WA and improves I/O throughput, as demonstrated on real-world cloud storage workloads.

What Problem Does This Paper Address?

Log-structured storage is widely used for its high write performance, but it faces a significant challenge: write amplification (WA). WA occurs during garbage collection (GC), where live data blocks must be rewritten to reclaim space occupied by deleted (stale) blocks. This rewriting process increases I/O operations, reduces storage device lifespan, and consumes more power. While an ideal data placement strategy exists that minimizes WA by knowing future block invalidation times (BITs), this future knowledge is impractical. Existing methods that group blocks by "temperature" (e.g., write frequency) are often inaccurate for predicting BITs, leading to suboptimal WA reduction. The paper aims to bridge this gap by proposing a practical approach to infer BITs and use this information for effective data placement.

Methods

The core of SepBIT lies in its ability to infer Block Invalidation Times (BITs) without future knowledge. It achieves this by:

  • Separating Block Types: SepBIT first distinguishes between "user-written blocks" (new writes) and "GC-rewritten blocks" (data rewritten during GC). This is based on the observation that these two types of blocks generally have different lifespan characteristics.
  • Inferring Lifespans:
    • For user-written blocks, SepBIT estimates their lifespan by looking at the lifespan of the block they are invalidating. The intuition is that if a block invalidates a short-lived block, it's likely to be short-lived itself.
  • For GC-rewritten blocks, SepBIT infers their "residual lifespan" (how long they will remain valid after being rewritten by GC) by considering their "age" (time since their last user write). The idea is that blocks with shorter ages are more likely to have shorter residual lifespans.
  • Data Placement: Based on these inferred lifespans, SepBIT groups blocks into different classes (segments). User-written blocks are split into "short-lived" and "long-lived" groups. GC-rewritten blocks are similarly categorized based on their inferred residual lifespans. This fine-grained separation allows blocks with similar BITs to be co-located.
  • Adaptive Thresholds: SepBIT dynamically adjusts its separation thresholds based on observed workload characteristics, particularly the average segment lifespan observed during GC.

Datasets

The paper evaluates SepBIT using real-world block-level I/O traces from:

  • Alibaba Cloud: 1,000 virtual disks over a one-month period.
  • Tencent Cloud: 4,995 volumes over a nine-day period.

The authors pre-process these traces, focusing on write requests and filtering volumes with insufficient write activity to ensure meaningful GC operations.

Key Insights and Ideas

  • User-written vs. GC-rewritten blocks have different lifespans: This fundamental observation drives the initial separation strategy, as GC-rewritten blocks tend to have longer lifespans than user-written blocks.
  • "Temperature" is a poor proxy for BIT: Existing methods relying on write/update frequency (temperature) are insufficient because frequently updated blocks can still have highly variable lifespans, making them poor indicators of BIT.
  • Skewed workloads are key: The effectiveness of SepBIT's BIT inference relies heavily on skewed access patterns, which are common in real-world cloud workloads. The more skewed the workload, the better SepBIT can predict BITs.
  • Fine-grained separation pays off: Separating both user-written and GC-rewritten blocks independently, and then further subdividing them based on inferred BITs, yields significant WA reductions beyond simpler separation schemes.

Key Results

  • WA Reduction: SepBIT significantly reduces write amplification. Compared to state-of-the-art schemes, it achieved an overall WA reduction of 8.6-15.9% on Alibaba Cloud traces. Per-volume WA reductions reached up to 44.1%.
  • Throughput Improvement: The prototype evaluation showed that SepBIT improves I/O throughput, with a median improvement of 20% over the second-best scheme.
  • Accurate BIT Inference: Trace analysis confirmed that SepBIT's inferred BITs are accurate, leading to higher garbage collection effectiveness (higher GP of collected segments).
  • Low Memory Overhead: SepBIT maintains low memory overhead for a majority of volumes, typically reducing memory usage by over 70%.
  • Performance on Tencent Cloud: SepBIT also demonstrated strong performance on Tencent Cloud traces, achieving the lowest WA among existing schemes.
  • Skewness Impact: SepBIT's effectiveness increases with workload skewness, showing substantial WA reduction on highly skewed workloads.

Limitations and Future Work

  • Ideal vs. Practical: The paper acknowledges that the ideal data placement scheme (WA=1) is infeasible due to the need for future knowledge. SepBIT is a practical approximation.
  • Memory Overhead: While generally low, SepBIT's memory overhead can be higher in worst-case scenarios or for less skewed workloads.
  • Future Work: The authors suggest extending SepBIT to be file-system aware and exploring its application in distributed storage systems. They also mention that SepBIT can be combined with advanced segment selection algorithms for further WA mitigation.

Summary updated

Abstract

Log-structured storage has been widely deployed in various domains of storage systems for high performance. However, its garbage collection (GC) incurs severe write amplification (WA) due to the frequent rewrites of live data. This motivates many research studies, particularly on data placement strategies, that mitigate WA in log-structured storage. We show how to design an optimal data placement scheme that leads to the minimum WA with the future knowledge of block invalidation time (BIT) of each written block. Guided by this observation, we propose InferBIT, a novel data placement algorithm that aims to minimize WA in log-structured storage. Its core idea is to infer the BITs of written blocks from the underlying storage workloads, so as to place the blocks with similar estimated BITs into the same group in a fine-grained manner. We show via both mathematical and trace analyses that InferBIT can infer the BITs by leveraging the write skewness property in real-world storage workloads. Evaluation on block-level I/O traces from real-world cloud block storage workloads shows that InferBIT achieves the lowest WA compared to eight state-of-the-art data placement schemes.
BibTeX
@inproceedings{wang2022separating,
  author = {Qiuping Wang and Jinhong Li and Patrick P. C. Lee and Tao Ouyang and Chao Shi and Lilong Huang},
  title = {{Separating Data via Block Invalidation Time Inference for Write Amplification Reduction in Log-Structured Storage}},
  booktitle = {Fast},
  year = {2022},
}
Figure