Taking Garbage Collection Overheads Off the Critical Path in SSDs

Myoungsoo Jung, Ramya Prabhakar, Mahmut T. KandemirMiddleware 2012 · DOI

TL;DR

This paper tackles the performance bottleneck of garbage collection (GC) in Solid State Drives (SSDs), which causes unpredictable latency spikes. They propose a novel strategy, AGC+DGC, that intelligently shifts GC operations to idle periods, significantly reducing worst-case response times and providing stable performance without increasing the total number of GCs.

What Problem Does This Paper Address?

Solid State Drives (SSDs) offer significant advantages over traditional Hard Disk Drives (HDDs), including faster random access speeds and lower power consumption. However, a critical challenge hindering their widespread adoption, especially in performance-sensitive applications, is the overhead introduced by garbage collection (GC). NAND flash memory, the core component of SSDs, has a unique erase-before-write property. This means data cannot be overwritten directly; instead, valid data must be relocated to new blocks before old blocks can be erased to make space for new writes. This process, known as garbage collection, can introduce substantial latency spikes, leading to unpredictable performance variations that are unacceptable in many I/O-intensive computing environments. Existing GC strategies often focus on reducing the frequency or duration of GC operations, but they still struggle to completely hide these latencies during busy periods.

Methods

The paper introduces a novel garbage collection strategy called Advanced Garbage Collection (AGC) and Delayed Garbage Collection (DGC), collectively referred to as AGC+DGC. This strategy aims to move GC operations away from critical I/O paths and into idle periods.

  • Idle Period Classification: The core idea is to leverage device-level idle times. The authors classify these idle periods into two types:
  • Short Idle Periods: These are brief intervals between I/O requests, detectable by examining the device-level command queue.
  • Long Idle Periods: These are longer periods with no enqueued I/O commands.
  • Advanced Garbage Collection (AGC): AGC proactively prepares free blocks and attempts to defer on-demand GCs from busy periods. It has two implementations:
  • Look-ahead Garbage Collection: Utilizes short idle periods to predict upcoming GC needs by analyzing the command queue and performing GCs in advance.
  • Proactive Block Compaction: Exploits long idle periods to compact fully occupied blocks, reclaiming free space.
  • Delayed Garbage Collection (DGC): DGC acts as a fallback when AGC cannot fully handle on-demand GCs. It delays GC operations to future idle periods.
  • Update Block Replacement: When an on-demand GC is triggered during a busy period, DGC allocates a free block as an "update block" and records the pending GC operation in a DGC job list. This allows the SSD to serve the immediate I/O request without performing the costly page migration.
  • Retroactive Block Compaction: During subsequent idle periods, DGC processes the DGC job list, performing the delayed page migrations and reclaiming blocks.

The AGC+DGC scheme is designed to be compatible with existing Flash Translation Layers (FTLs) without requiring major modifications or additional non-volatile memory.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Enterprise Workloads: Traces collected from the MSN file server storage over 5 days, totaling up to 1.8TB of I/O traffic. These traces are characterized by varying levels of idle periods and write intensity.
  • Simulated SSDs: The authors implemented a simulation platform that models a typical SSD storage stack, including flash drivers, translation layers, and host interface controllers. This platform allows for accurate simulation of different idleness types and workloads.

Key Insights and Ideas

  • Idle Time is a Valuable Resource: The most significant insight is that device-level idle periods, often overlooked, can be effectively utilized to offload computationally intensive tasks like garbage collection.
  • Proactive vs. Reactive GC: The paper elegantly combines proactive (AGC) and reactive (DGC) strategies. AGC aims to prevent GC from ever hitting the critical path, while DGC ensures that even if it does, the latency is deferred.
  • No Additional GC Operations: A crucial aspect of their approach is that AGC+DGC reschedules existing GC operations rather than creating new ones, thus not impacting SSD endurance negatively.
  • Compatibility is Key: The proposed scheme's ability to work with existing FTLs without major changes makes it highly practical for real-world adoption.
  • Worst-Case Latency is the Real Problem: The paper strongly emphasizes that it's not the average GC overhead but the unpredictable worst-case latencies that are detrimental to SSD performance in demanding applications.

Key Results

The experimental evaluation, conducted using both simulations and real SSDs, demonstrates the effectiveness of the AGC+DGC strategy:

  • Significant Reduction in Worst-Case Response Time (WCRT): AGC+DGC reduced WCRT by an average of 66.7% compared to P-FTL, 96.7% compared to L-FTL, and 98.2% compared to H-FTL.
  • Stable I/O Performance: The proposed strategy provides stable performance, making it indistinguishable from a pristine SSD in terms of user-perceived latency.
  • Elimination of GC Overheads During Busy Periods: AGC+DGC successfully hides GC latencies during busy periods, ensuring applications do not experience performance degradation.
  • Reduced Block Erase Operations: The proactive block compaction aspect of AGC reduced block erase operations by 16.6% compared to a conventional FTL.
  • No Increase in Total GC Operations: The authors confirmed that their approach does not increase the total number of GC operations, thus preserving SSD endurance.

Limitations and Future Work

  • Free Block Threshold Impact: The paper notes that the effectiveness of proactive block compaction is sensitive to the free block threshold. If this threshold is too high, it can negatively impact wear-leveling characteristics compared to L-FTL. They suggest that a threshold less than 43% of the original GC threshold is optimal for wear-leveling.
  • Future Work: While not explicitly detailed, the success of AGC+DGC in various scenarios suggests its applicability to a wider range of SSD configurations and workloads. Further research could explore finer-grained idle period detection and more adaptive scheduling of AGC and DGC components. The paper also mentions that their approach can be applied to other NAND flash device models, implying potential for broader validation.

Summary updated

BibTeX
@inproceedings{jung2012taking,
  author = {Myoungsoo Jung and Ramya Prabhakar and Mahmut T. Kandemir},
  title = {{Taking Garbage Collection Overheads Off the Critical Path in SSDs}},
  booktitle = {Middleware},
  year = {2012},
  doi = {10.1007/978-3-642-35170-9\_9},
}
Figure