Deterministic service guarantees for nand flash using partial block cleaning

ABSTRACT

NAND flash idiosyncrasies such as bulk erase and wear leveling results in non-linear and unpredictable read/write access times. In case of application domains such as streaming multimedia and real-time systems, a deterministic read/write access time is desired during design time. We propose a novel NAND flash translation layer called GFTL that guarantees fixed upper bounds (i.e., worst case service rates) for reads and writes that are comparable to a theoretical ideal case. Such guarantees are made possible by eliminating sources of non-determinism in GFTL design and using partial block cleaning. GFTL performs garbage collection in partial steps by dividing the garbage collection of a single block into several chunks, thereby interleaving and hiding the garbage collection latency while servicing requests.

Further, GFTL guarantees are independent of flash utilization, size or state. Along with theoretical bounds, benchmark results show the efficacy of our approach. Based on our experiments, GFTL requires an additional 16% of total blocks for flash management. GFTL service guarantees can be calculated from flash specifications. Thus, with GFTL, a designer can determine the service guarantees and size requirements apriori, during design time.

REFERENCES

• 1: New techniques for real-time fat filesystem in mobile multi media devices. IEEE Transactions on Consumer Electronics, 52:1--9, 2006.
• 2: A. Ban. Flash file system optimized for page-mode flash technologies. US Patent 5,937,425, Aug 10, 1999
• 3: Canon. Vixia HD Camcoder, January 2008.
• 4: Li-Pin Chang , Tei-Wei Kuo, Efficient management for large-scale flash-memory storage systems with resource conservation, ACM Transactions on Storage (TOS), v.1 n.4, p.381-418, November 2005 [doi>10.1145/1111609.1111610]
• 5: 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]
• 6: Siddharth Choudhuri , Tony Givargis, Performance improvement of block based NAND flash translation layer, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289816.1289878]
• 7: Siddharth Choudhuri , Tony Givargis, Real-Time Access Guarantees for NAND Flash Using Partial Block Cleaning, Proceedings of the 6th IFIP WG 10.2 international workshop on Software Technologies for Embedded and Ubiquitous Systems, October 01-03, 2008, Anacarpi, Capri Island, Italy [doi>10.1007/978-3-540-87785-1_13]
• 8: Fred Douglis , Ramón Cáceres , Frans Kaashoek , Kai Li , Brian Marsh , Joshua A. Tauber, Storage alternatives for mobile computers, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.3-es, November 14-17, 1994, Monterey, California
• 9: Eran Gal , Sivan Toledo, Algorithms and data structures for flash memories, ACM Computing Surveys (CSUR), v.37 n.2, p.138-163, June 2005 [doi>10.1145/1089733.1089735]
• 10: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 11: J. Katcher. Postmark: A new file system benchmark. Technical report, Net App. Inc, TR 3022, 1997.
• 12: George Lawton, Improved Flash Memory Grows in Popularity, Computer, v.39 n.1, p.16-18, January 2006 [doi>10.1109/MC.2006.22]
• 13: MemCon. MemCon, July 2007. http://linuxdevices.com/news/NS6633183518.html.
• 14: W. Norcutt. IOZONE benchmark, www.iozone.org.
• 15: One Laptop Per Child Project. http://laptop.org.
• 16: D. Parthey. Analyzing real-time behavior of flash memories. Diploma Thesis, Chemnitz University of Technology, April, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Design, Performance

Keywords:
determinism, embedded systems, file systems, nand flash, qos, real-time, storage