Analytical Modeling of Write Amplification for Garbage Collection in Solid-State Drives

Recent breakthroughs in NAND flash technology have made solid state drive (SSD) a viable storage device for data centers. While offering remarkable enhancement on density, reliability, speed against hard disk drives, every SSD can only sustain a limited number of writes, or its write budget. To prolong SSD lifespan, minimizing write amplification factor, a metric for the garbage collection (GC) algorithm overhead that unproductively consumes the write budget, becomes a central problem in the flash management software stack known as the flash translation layer (FTL). Unfortunately, prior works on the analytical modeling of write amplification tend to fall short of the promises of offering more design insights than simulations, either due to their complexity, or over-simplification of user write traffic. Towards the goal of finding more realistic models, this thesis discovers that practically enterprise workloads are not only skewed, but also following the Zipfâ s law. Leveraging this, we present, by rigorous probabilistic analysis, the first, highly accurate algebraic and closed-form solutions for predicting the write amplification factor for the greedy selection algorithm, known to approximate real world algorithms well, under skewed write traffic. The prediction errors against simulations are shown to be within 4%. Furthermore, we demonstrate, as a surprising corollary, that the write amplification under Zipfian write is analytically bounded. In parallel, we use the mean field analysis method and show that even under a multi-tier workload model, where uniform write is assumed within a tier, the system dynamics can be captured by a system of ordinary differential equations (ODEs), and hence the write amplification for the d-Choice scheme can be predicted, within 4% errors against simulation. We further propose a simpler system of algebraic equations for predicting steady-state write amplification under uniform traffic. We show that such a model retains predictive precision, while offering an average of 35% analysis running time reduction from ODE models.Ph.D