  Solid state drives (SSDs) have seen wide deployment in mobiles, desktops, and
data centers due to their high I/O performance and low energy consumption. As
SSDs write data out-of-place, garbage collection (GC) is required to erase and
reclaim space with invalid data. However, GC poses additional writes that
hinder the I/O performance, while SSD blocks can only endure a finite number of
erasures. Thus, there is a performance-durability tradeoff on the design space
of GC. To characterize the optimal tradeoff, this paper formulates an
analytical model that explores the full optimal design space of any GC
algorithm. We first present a stochastic Markov chain model that captures the
I/O dynamics of large-scale SSDs, and adapt the mean-field approach to derive
the asymptotic steady-state performance. We further prove the model convergence
and generalize the model for all types of workload. Inspired by this model, we
propose a randomized greedy algorithm (RGA) that can operate along the optimal
tradeoff curve with a tunable parameter. Using trace-driven simulation on
DiskSim with SSD add-ons, we demonstrate how RGA can be parameterized to
realize the performance-durability tradeoff.
