Efficient identification of hot data for flash memory storage systems

ABSTRACT

Hot data identification for flash memory storage systems not only imposes great impacts on flash memory garbage collection but also strongly affects the performance of flash memory access and its lifetime (due to wear-levelling). This research proposes a highly efficient method for on-line hot data identification with limited space requirements. Different from past work, multiple independent hash functions are adopted to reduce the chance of false identification of hot data and to provide predictable and excellent performance for hot data identification. This research not only offers an efficient implementation for the proposed framework, but also presents an analytic study on the chance of false hot data identification. A series of experiments was conducted to verify the performance of the proposed method, and very encouraging results are presented.

REFERENCES

• 1: Aleph One Company. Yet another flash filing system.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: Chang, L. P. and Kuo, T. W. 2001. A dynamic-voltage-adjustment mechanism in reducing the power consumption of flash memory for portable devices. In Proceedings of the IEEE Conference on Consumer Electronic (ICCE), (Los Angeles, Calif., June).
• 4: Li-Pin Chang , Tei-Wei Kuo, An Adaptive Striping Architecture for Flash Memory Storage Systems of Embedded Systems, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.187, September 25-27, 2002
• 5: Chang, L. P. and Kuo, T. W. 2002b. A real-time garbage collection mechanism for flash memory storage system in embedded systems. In Proceedings of the 8th International Conference on Real-Time Computing Systems and Applications (RTCSA).
• 6: Li-Pin Chang , Tei-Wei Kuo, An efficient management scheme for large-scale flash-memory storage systems, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968076]
• 7: Chiang, M. L., Lee, P. C. H., and Chang, R. C. 1997. Managing flash memory in personal communication devices. In Proceedings of the 1997 International Symposium on Consumer Electronics (ISCE'97). (Singapore, Dec.). 177--182.
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: Compact Flash Association. 1998. Compact Flash#8482; 1.4 specification.
• 10: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 11: Inoue, A. and Wong, D. 2003. NAND flash applications design guide. http://www.semicon.toshiba.co.jp/eng/prd/memory/doc/pdf/nand_applicationguide_e.pdf.
• 12: Intel. Using the RDTSC instruction for performance monitoring. http://developer.intel.com/drg/pentiumII/appnotes/RDTSCPM1.htm.
• 13: Intel. Understanding the flash translation layer (FTL) specification.
• 14: Jenkins, B. 2006. A hash function for hash table lookup. http://burtleburtle.net/bob/hash/doobs.html.
• 15: Kawaguchi, A., Nishioka, S., and Motoda, H. 1995. A flash-memory based file system. In Proceedings of the 1995 USENIX Technical Conference (Jan.). 155--164.
• 16: M-Systems. Flash-Memory translation layer for NAND flash (NFTL).
• 17: 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]
• 18: SSFDC Forum. 1999. SmartMedia#8482; Specification.
• 19: Storagesearch. Increasing flash solid state disk reliability. http://www.storagesearch.com/siliconsys-art1.html.
• 20: Woodhouse, D. JFFS: The journaling flash file system. Red Hat, Inc.
• 21: Michael Wu , Willy Zwaenepoel, eNVy: a non-volatile, main memory storage system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.86-97, October 05-07, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories

General Terms:
Design, Performance

Keywords:
Storage system, flash memory, garbage collection, workload locality