Write amplification analysis in flash-based solid state drives

ABSTRACT

Write amplification is a critical factor limiting the random write performance and write endurance in storage devices based on NAND-flash memories such as solid-state drives (SSD). The impact of garbage collection on write amplification is influenced by the level of over-provisioning and the choice of reclaiming policy. In this paper, we present a novel probabilistic model of write amplification for log-structured flash-based SSDs. Specifically, we quantify the impact of over-provisioning on write amplification analytically and by simulation assuming workloads of uniformly-distributed random short writes. Moreover, we propose modified versions of the greedy garbage-collection reclaiming policy and compare their performance. Finally, we analytically evaluate the benefits of separating static and dynamic data in reducing write amplification, and how to address endurance with proper wear leveling.

REFERENCES

• 1: Nitin Agrawal , Vijayan Prabhakaran , Ted Wobber , John D. Davis , Mark Manasse , Rina Panigrahy, Design tradeoffs for SSD performance, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.57-70, June 22-27, 2008, Boston, Massachusetts
• 2: Avraham Ben-Aroya , Sivan Toledo, Competitive analysis of flash-memory algorithms, Proceedings of the 14th conference on Annual European Symposium, p.100-111, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_12]
• 3: Li-Pin Chang , Tei-Wei Kuo , Shi-Wu Lo, Real-time garbage collection for flash-memory storage systems of real-time embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.837-863, November 2004 [doi>10.1145/1027794.1027801]
• 4: Yuan-Hao Chang , Jen-Wei Hsieh , Tei-Wei Kuo, Endurance enhancement of flash-memory storage systems: an efficient static wear leveling design, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278533]
• 5: P. Erdös and A. Rényi. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutato Int. Kozl, 6:215--219, 1961.
• 6: A. Fazio. The real story about NAND flash and solid-state drive reliability. Intel Developer Forum US, Aug. 2008.
• 7: Atsuo Kawaguchi , Shingo Nishioka , Hiroshi Motoda, A flash-memory based file system, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.13-13, January 16-20, 1995, New Orleans, Louisiana
• 8: E. H. McKinney. Generalized birthday problem. American Mathematical Monthly, (73):385--387, 1966.
• 9: J. Menon, A performance comparison of RAID-5 and log-structured arrays, Proceedings of the 4th IEEE International Symposium on High Performance Distributed Computing, p.167, August 02-04, 1995
• 10: J. Menon and L. Stockmeyer. An age-threshold algorithm for garbage collection in log-structured arrays and file systems. In J. Schaeffler, editor, High Performance Computing Systems and Applications, pages 119--132. Kluwer Academic Publishers, 1998.
• 11: ONFi. Open NAND Flash Interface Specification 1.0. Specification, Open NAND Flash Interface (ONFi), Dec. 2006.
• 12: John Ousterhout , Fred Douglis, Beating the I/O bottleneck: a case for log-structured file systems, ACM SIGOPS Operating Systems Review, v.23 n.1, p.11-28, Jan. 1989 [doi>10.1145/65762.65765]
• 13: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• 14: D. Shmidt. TrueFFS wear-leveling mechanism. Technical report, M-Systems, May 2002.
• 15: Stec. The Zeus^IOPS enterprise SSD.
• 16: D. Woodhouse. JFFS: The journaling flash file system. In Ottawa Linux Symposium, July 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

General Terms:
Algorithms, Design, Performance

Keywords:
flash memory, solid state drives, solid state storage systems, write amplification