Adaptive range-based address mapping for the flash storage devices with explosive capacity

ABSTRACT

Due to the fast-growing amount of data in mobile applications and big data applications, there is a strong demand for the capacity of flash storage devices. Due to the fast-growing capacity, flash storage devices face a serious challenge on reducing their RAM space consumption for the address mapping information without sacrificing device performance. In contrast to the existing table-based address mapping designs, we propose an adaptive range-based address mapping scheme whose RAM space requirement is minimized and independent of the storage capacity. In this scheme, an unbalanced range-based binary search tree with an efficient space allocator and garbage collection policy is designed to minimize the RAM space for the address mapping information with optimized performance to search for the address mapping information. Some evaluations were conducted to evaluate the capability of the proposed scheme, and the results are encouraging.

References

1. Understanding the Flash Translation Layer (FTL) Specification, http://developer.intel.com/. Technical report, Intel Corporation, Dec 1998.
2. N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse, and R. Panigrahy. Design Tradeoffs for SSD Performance. In the Proceedings of the USENIX Technical Conference, pages 57--70, June 2008.
3. A. Ban. Wear Leveling of Static Areas in Flash Memory. US Patent 6,732,221, 2004.
4. L.-P. Chang and T.-W. Kuo. An Adaptive Striping Architecture for Flash Memory Storage Systems of Embedded Systems. In the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 187--196, 2002.
5. Y.-H. Chang, J.-W. Hsieh, and T.-W. Kuo. Endurance enhancement of flash-memory storage systems: an efficient static wear leveling design. In Proceedings of the 44th annual Design Automation Conference, DAC '07, pages 212--217, New York, NY, USA, 2007. ACM.
6. Y.-H. Chang and T.-W. Kuo. A Commitment-based Management Strategy for the Performance and Reliability Enhancement of Flash-memory Storage Systems. In ACM/IEEE Design Automation Conference (DAC), pages 858--863, July 2009.
7. Y.-H. Chang, M.-C. Yang, T.-W. Kuo, and R.-H. Hwang. A reliability enhancement design under the flash translation layer for mlc-based flash-memory storage systems. ACM Trans. Embed. Comput. Syst., 13(1):10:1--10:28, Sept. 2013.
8. H. Cho, D. Shin, and Y. I. Eom. KAST: K-associative sector translation for NAND flash memory in real-time systems. In the ACM/IEEE Design, Automation and Test in Europe (DATE), pages 507--512, April 2009.
9. E. Deal. Trends in NAND Flash Memory Error Correction. Technical report, Cyclic Design, June 2009.
10. A. Gupta, Y. Kim, and B. Urgaonkar. Dftl: a flash translation layer employing demand-based selective caching of page-level address mappings. SIGPLAN Not., 44:229--240, March 2009.
11. 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. ACM.
12. J. Kim, J. M. Kim, S. H. Noh, S. L. Min, and Y. Cho. A Space-Efficient Flash Translation Layer For CompactFlash Systems. IEEE Transactions on Consumer Electronics, Nov 2002.
13. S. Lee, D. Shin, Y.-J. Kim, and J. Kim. Last: locality-aware sector translation for nand flash memory-based storage systems. SIGOPS Oper. Syst. Rev., 42:36--42, October 2008.
14. S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Lee, S. Park, and H.-J. Song. A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation. In ACM Transactions on Embedded Computing Systems (TECS), July 2007.
15. D. Ma, J. Feng, and G. Li. Lazyftl: a page-level flash translation layer optimized for nand flash memory. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, SIGMOD '11, pages 1--12, New York, NY, USA, 2011. ACM.
16. Micron Technology, Inc. FNNB63A 128Gbit NAND Flash Memory Data Sheet, 2011.
17. Micron Technology, Inc. FNNB74A 64Gbit NAND Flash Memory Data Sheet, 2011.
18. M. Murugan and D.-C. Du. Rejuvenator: A static wear leveling algorithm for nand flash memory with minimized overhead. In Mass Storage Systems and Technologies (MSST), 2011 IEEE 27th Symposium on, MSST '11, 2011.
19. C. Park, W. Cheon, J. Kang, K. Roh, W. Cho, and J.-S. Kim. A reconfigurable ftl (flash translation layer) architecture for nand flash-based applications. ACM Trans. Embed. Comput. Syst., 7:38:1--38:23, August 2008.
20. D. Park, B. Debnath, and D. Du. Cftl: a convertible flash translation layer adaptive to data access patterns. In Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '10, pages 365--366, New York, NY, USA, 2010. ACM.
21. Z. Qin, Y. Wang, D. Liu, Z. Shao, and Y. Guan. Mnftl: An efficient flash translation layer for mlc nand flash memory storage systems. In Design Automation Conference (DAC), 2011 48th ACM/EDAC/IEEE, pages 17--22, 2011.
22. Samsung Electronics. K9F8G08UXM 1G x 8 Bit NAND Flash Memory Data Sheet, March 2007.
23. SpecTek Technology, Inc. MT29F256G08CUCBB 256Gbit NAND Flash Memory Data Sheet, September 2008.
24. C.-H. Wu and T.-W. Kuo. An Adaptive Two-level Mnagement for the Flash Translation Layer in Embedded Systems. In the IEEE/ACM Iinternational Conference on Computer-Aided Design (ICCAD), pages 601--606, 2006.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • External storage

  • Integrated circuits

    • Semiconductor memory

      • Non-volatile memory

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Secondary storage