Modeling SSD Garbage Collection as a Gambler's Ruin Problem: Probabilistic Analysis and Control Strategies

The article begins with a historical anecdote about Edward Thorp’s 21‑card strategy and the gambler’s ruin theorem, illustrating how probability can determine outcomes in seemingly fair games.

It then connects this gambling analogy to solid‑state drive (SSD) garbage collection, explaining that SSDs must periodically reclaim space (victim blocks) and that the variability of valid data in those blocks causes bandwidth fluctuations similar to a gambler’s fluctuating bankroll.

Using Einstein’s 1905 Brownian‑motion paper as a foundation, the author derives a series of stochastic models: the expected chip count after n bets, the probability p(r,n) of ruin before n steps, and extensions to biased games where the win probability α exceeds 0.5.

These probabilistic results are mapped onto SSD behavior: r represents the number of free blocks, v the proportion of valid data in a victim block, and q the ratio of garbage‑collection writes to total writes. The analysis shows that if q equals the mean valid‑data proportion μ, the system eventually exhausts its free blocks, so q must be set greater than μ to maintain long‑term stability.

The paper further incorporates a Wiener process to model the random evolution of free‑block resources over time, demonstrating that the variance of r grows linearly, leading to eventual depletion unless proactive control is applied.

Three control schemes are simulated: (1) fixed q = v (no reserve blocks), (2) a modest reserve pool (r_m = 4), and (3) a larger reserve pool (r_m = 8). Results show that reserving free blocks smooths IOPS (input/output operations per second) and reduces bandwidth jitter, while the fixed‑q approach yields large fluctuations.

Finally, iterative formulas for updating r and q are presented, revealing a Markov‑chain structure that can be analyzed via MCMC to obtain steady‑state distributions. The study concludes that modestly over‑provisioning garbage‑collection resources (q > μ) and maintaining a buffer of free blocks significantly improve SSD write‑bandwidth stability.