A mean field model for a class of garbage collection algorithms in flash-based solid state drives

ABSTRACT

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class C of GC algorithms. Apart from the Random GC algorithm, class C includes two novel GC algorithms: the d-Choices GC algorithm, that selects d blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50000$ blocks). We further show that the d-Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small d values, e.g., d = 10, and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for b ≥ 64).

References

1. R. Agarwal and M. Marrow. A closed-form expression for write amplification in NAND flash. In IEEE GLOBECOM Workshops (GC Wkshps), pages 1846--1850, 2010.
2. Y. Azar, A.Z. Broder, A.R. Karlin, and E. Upfal. Balanced allocations. In SIAM Journal on Computing, pages 593--602, 1994.
3. A. Ban. Wear leveling of static areas in flash memory. US patent 6,732,221. Filed June 1, 2001; Issued May 4, 2004; Assigned to M-Systems., 2004.
4. M. Benaım and J. Le Boudec. A class of mean field interaction models for computer and communication systems. Performance Evaluation, 65(11--12):823--838, 2008.
5. W. Bux and I. Iliadis. Performance of greedy garbage collection in flash-based solid-state drives. Perform. Eval., 67(11):1172--1186, November 2010.
6. F. Chen, D.A. Koufaty, and X. Zhang. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. ACM SIGMETRICS Perform. Eval. Rev., 37(1):181--192, 2013.
7. P. Desnoyers. Analytic modeling of SSD write performance. In Proceedings of International Systems and Storage Conference (SYSTOR 2012), 2012.
8. X. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka. Write amplification analysis in flash-based solid state drives. In Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, SYSTOR '09, pages 10:1--10:9, New York, NY, USA, 2009.
9. J.-U. Kang, H. Jo, J.-S. Kim, and J. Lee. A superblock-based flash translation layer for NAND flash memory. In Proceedings of the 6th ACM & IEEE International conference on Embedded software, EMSOFT '06, pages 161--170, New York, NY, USA, 2006.
10. Y. Li, P.P.C. Lee, and J.C.S. Lui. Stochastic modeling of large-scale solid-state storage systems: Analysis, design tradeoffs and optimization. ACM SIGMETRICS Perform. Eval. Rev., 41(1), 2013.
11. J. Menon. A performance comparison of RAID-5 and log-structured arrays. In Proceedings of the 4th IEEE International Symposium on High Performance Distributed Computing, HPDC '95, pages 167--178, Washington, DC, USA, 1995.
12. M. Mitzenmacher, A. Richa, and R. Sitaraman. The power of two random choices: a survey of techniques and results. Handbook of Randomized Computing, 1, 2001.
13. J.T. Robinson. Analysis of steady-state segment storage utilizations in a log-structured file system with least-utilized segment cleaning. SIGOPS Oper. Syst. Rev., 30(4):29--32, October 1996.
14. M. Rosenblum and J. K. Ousterhout. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst., 10(1):26--52, February 1992.
15. N.D. Vvedenskaya, R.L. Dobrushin, and F.I. Karpelevich. Queueing system with selection of the shortest of two queues: an asymptotic approach. Problemy Peredachi Informatsii, 32:15--27, 1996.
16. L. Xiang and B. Kurkoski. An improved analytical expression for write amplification in NAND flash. In International Conference on Computing, Networking, and Communications (ICNC), pages 497--501, 2012.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Stochastic control and optimization