DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings

ABSTRACT

Recent technological advances in the development of flash-memory based devices have consolidated their leadership position as the preferred storage media in the embedded systems market and opened new vistas for deployment in enterprise-scale storage systems. Unlike hard disks, flash devices are free from any mechanical moving parts, have no seek or rotational delays and consume lower power. However, the internal idiosyncrasies of flash technology make its performance highly dependent on workload characteristics. The poor performance of random writes has been a cause of major concern, which needs to be addressed to better utilize the potential of flash in enterprise-scale environments. We examine one of the important causes of this poor performance: the design of the Flash Translation Layer (FTL), which performs the virtual-to-physical address translations and hides the erase-before-write characteristics of flash. We propose a complete paradigm shift in the design of the core FTL engine from the existing techniques with our Demand-based Flash Translation Layer (DFTL), which selectively caches page-level address mappings. We develop a flash simulation framework called FlashSim. Our experimental evaluation with realistic enterprise-scale workloads endorses the utility of DFTL in enterprise-scale storage systems by demonstrating: (i) improved performance, (ii) reduced garbage collection overhead and (iii) better overload behavior compared to state-of-the-art FTL schemes. For example, a predominantly random-write dominant I/O trace from an OLTP application running at a large financial institution shows a 78% improvement in average response time (due to a 3-fold reduction in operations of the garbage collector), compared to a state-of-the-art FTL scheme. Even for the well-known read-dominant TPC-H benchmark, for which DFTL introduces additional overheads, we improve system response time by 56%.

REFERENCES

• 1: Amir Ban. Flash File System. In United States Patent, No 5,404,485, 1993.
• 2: T. Chung, D. Park, S. Park, D. Lee, S. Lee, and H. Song. System Software for Flash Memory: A Survey. In Proceedings of the International Conference on Embedded and Ubiquitous Computing, pages 394--404, August 2006.
• 3: 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]
• 4: Flash Drives Hit by High Failure Rates. Flash Drives Hit by High Failure Rates. http://www.techworld.com/storage/news/index.cfm?newsid=11747.
• 5: G.R. Ganger, B.L. Worthington, and Y.N. Patt. The DiskSim Simulation Environment Version 3.0 Reference Manual.
• 6: Ajay Gulati , Arif Merchant , Peter J. Varman, pClock: an arrival curve based approach for QoS guarantees in shared storage systems, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 7: A. Gupta, Y. Kim, and B. Urgaonkar. DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings. In Technical Report CSE 08-012, Penn State University, August 2008.
• 8: Sudhanva Gurumurthi , Anand Sivasubramaniam , Mahmut Kandemir , Hubertus Franke, DRPM: dynamic speed control for power management in server class disks, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 9: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 10: HP Labs. Tools and Traces. HP Labs. Tools and Traces. http://tesla.hpl.hp.com/public_software/.
• 11: J. Kim, J.M. Kim, S.H. Noh, S. Min, and Y. Cho. A Space-Efficient Flash Translation Layer for Compactflash Systems. IEEE Transactions on Consumer Electronics, 48(2):366--375, 2002.
• 12: Dawoon Jung , Yoon-Hee Chae , Heeseung Jo , Jin-Soo Kim , Joonwon Lee, A group-based wear-leveling algorithm for large-capacity flash memory storage systems, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289911]
• 13: Jeong-Uk Kang , Heeseung Jo , Jin-Soo Kim , Joonwon Lee, A superblock-based flash translation layer for NAND flash memory, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176911]
• 14: Ramakrishna Karedla , J. Spencer Love , Bradley G. Wherry, Caching strategies to improve disk system performance, Computer, v.27 n.3, p.38-46, March 1994 [doi>10.1109/2.268884]
• 15: 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
• 16: Hyojun Kim , Seongjun Ahn, BPLRU: a buffer management scheme for improving random writes in flash storage, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-14, February 26-29, 2008, San Jose, California
• 17: Y. Kim, S. Gurumurthi, and A. Sivasubramaniam. Understanding the Performance-Temperature Interactions in Disk I/O of Server Workloads. In Proceedings of the International Symposium on High-Performance Computer Architecture (HPCA), Febuary 2006.
• 18: Sang-Won Lee , Bongki Moon, Design of flash-based DBMS: an in-page logging approach, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247488]
• 19: Sang-Won Lee , Dong-Joo Park , Tae-Sun Chung , Dong-Ho Lee , Sangwon Park , Ha-Joo Song, A log buffer-based flash translation layer using fully-associative sector translation, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.3, p.18-es, July 2007 [doi>10.1145/1275986.1275990]
• 20: S. Lee, D. Shin, Y. Kim, and J. Kim. LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems. In Proceedings of the International Workshop on Storage and I/O Virtualization, Performance, Energy, Evaluation and Dependability (SPEED2008), Feburary 2008.
• 21: Adam Leventhal, Flash storage memory, Communications of the ACM, v.51 n.7, July 2008 [doi>10.1145/1364782.1364796]
• 22: K. M. J. Lofgren, R. D. Norman, G B. Thelin, and A. Gupta. Wear Leveling Techniques for Flash EEPROM. In United States Patent, No 6,850,443, 2005.
• 23: Micron 16GB Mass Storage. Micron 16GB Mass Storage. http://www.micron.com/products/partdetail?part=MT29F16G08DAAWP.
• 24: Micron Technical Report (TN-29-07): Small-Block vs. Large-Block NAND Flash Devices. Technical Report (TN-29-07): Small-Block vs. Large-Block NAND Flash Devices. http://www.micron.com/products/nand/technotes.
• 25: OLTP Trace from UMass Trace Repository. OLTP Trace from UMass Trace Repository. http://traces.cs.umass.edu/index.php/Storage/Storage.
• 26: Websearch Trace from UMass Trace Repository. Websearch Trace from UMass Trace Repository. http://traces. cs.umass.edu/index.php/Storage/Storage.
• 27: White Paper: Datacenter SSDs: Solid Footing for Growth. White Paper: Datacenter SSDs: Solid Footing for Growth. http://www.samsung.com/global/business/semiconductor/products/flash/FlashApplicationNote.html.
• 28: Jianyong Zhang , Anand Sivasubramaniam , Hubertus Franke , Natarajan Gautam , Yanyong Zhang , Shailabh Nagar, Synthesizing Representative I/O Workloads for TPC-H, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.142, February 14-18, 2004 [doi>10.1109/HPCA.2004.10019]

INDEX TERMS

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

General Terms:
Measurement, Performance

Keywords:
flash management, flash translation layer, storage system