Stochastic modeling and optimization of garbage collection algorithms in solid-state drive systems

Markov chains and mean‐field analysis are powerful tools and widely used for performance analysis in large‐scale computer and communication systems. In this paper, we consider the application of Markov modeling and mean‐field analysis to solid‐state drives (SSDs). SSDs are now widely deployed in mobiles, desktops, and data centers due to their high I/O performance and low energy consumption. In particular, we focus on characterizing the performance–durability tradeoff of garbage collection (GC) algorithms in SSDs. Specifically, we first develop a stochastic Markov chain model to capture the I/O dynamics of large‐scale SSDs, then adapt mean‐field analysis to derive the asymptotic steady state, based on which we are able to easily analyze the performance–durability tradeoff of a large family of GC algorithms. We further prove the model convergence and generalize the model for all types of workload. Inspired by this model, we also propose a randomized greedy algorithm (RGA) which has a single tunable parameter to trade between performance and durability. Using trace‐driven simulation on DiskSim with SSD add‐ons, we demonstrate how RGA can be parameterized to realize the performance–durability tradeoff.