I/O scheduling with mapping cache awareness for flash based storage systems

ABSTRACT

NAND flash memory has been the default storage component in mobile systems. One of the key technologies for flash management is the address mapping scheme between logical addresses and physical addresses, which deals with the inability of in-place-updating in flash memory. Demand-based page-level mapping cache is often applied to match the cache size constraint and performance requirement of mobile storage systems. However, recent studies showed that the management overhead of mapping cache schemes is sensitive to the host I/O patterns, especially when the mapping cache is small. This paper presents a novel I/O scheduling scheme, called MAP, to alleviate this problem. The proposed scheduling approach reorders I/O requests for performance improvement from two angles: Prioritizing the requests that will hit in the mapping cache, and grouping requests with related logical addresses into large batches. Experimental results show that MAP improved upon traditional I/O schedulers by 30% and 8% in terms of read and write latencies, respectively.

References

1. Data tag mechanism, eMMC 5.0, JEDEC Standard.
2. Packed commands, eMMC 5.0, JEDEC Standard.
3. umass trace repository. http://traces.cs.umass.edu/index.php/storage.
4. Snia. iotta repository. http://iotta.snia.org/, Jan. 2009., 2007.
5. Y. K. A. Gupta and B. Urgaonkar. DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings. In Proceedings of ASPLOS. ACM, 2009.
6. N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. S. Manasse, and R. Panigrahy. Design tradeoffs for ssd performance. In Proceedings of ATC, pages 57--70, 2008.
7. C. Gao, L. Shi, M. Zhao, C. J. Xue, K. Wu, and E. H. Sha. Exploiting parallelism in i/o scheduling for access conflict minimization in flash-based solid state drives. In Proceedings of MSST, pages 1--11, 2014.
8. L. Goasduff and C. Pettey. Gartner says worldwide smartphone sales soared in fourth quarter of 2011 with 47 percent growth. Visited April, 2012.
9. Y. Hu, H. Jiang, D. Feng, L. Tian, S. Zhang, J. Liu, W. Tong, Y. Qin, and L. Wang. Achieving page-mapping ftl performance at block-mapping ftl cost by hiding address translation. In Proceedings of MSST, pages 1--12, 2010.
10. S. Jiang, L. Zhang, X. Yuan, H. Hu, and Y. Chen. S-ftl: An efficient address translation for flash memory by exploiting spatial locality. In Proceedings of MSST, pages 1--12, 2011.
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, pages 161--170. ACM, 2006.
12. J. Kim, J. M. Kim, S. H. Noh, S. L. Min, and Y. Cho. A space-efficient flash translation layer for compactflash systems. Consumer Electronics, IEEE Transactions on, 48(2):366--375, 2002.
13. J. Kim, Y. Oh, E. Kim, J. Choi, D. Lee, and S. H. Noh. Disk schedulers for solid state drivers. In Proceedings of EMSOFT, pages 295--304. ACM, 2009.
14. J. Kim, S. Seo, D. Jung, J.-S. Kim, and J. Huh. Parameter-aware i/o management for solid state disks (ssds). Computers, IEEE Transactions on, 61(5):636--649, 2012.
15. K. Kim. Map cache design in mobile storage (SK hynix). http://dcslab.hanyang.ac.kr/nvramos14/presentation/s9.pdf, NVRAMOS (2014).
16. J. Lee, Y. Oh, H. Kwon, J. Choi, D. Lee, and S. H. Noh. Tinyftl: An ftl architecture for flash memory cards with scarce resources. In Proceedings of APSYS. ACM, 2013.
17. S. Lee, M. Liu, S. Jun, S. Xu, J. Kim, and Arvind. Application-managed flash. In 14th USENIX Conference on File and Storage Technologies (FAST 16), pages 339--353, Santa Clara, CA, Feb. 2016. USENIX Association.
18. S. Lee, D. Shin, Y.-J. Kim, and J. Kim. Last: locality-aware sector translation for nand flash memory-based storage systems. ACM SIGOPS Operating Systems Review, 42(6):36--42, 2008.
19. Y. Lee, J.-S. Kim, S.-W. Lee, and S. Maeng. Zombie chasing: Efficient flash management considering dirty data in the buffer cache. Computers, IEEE Transactions on, 64(2):569--581, 2015.
20. B. Mao and S. Wu. Exploiting request characteristics and internal parallelism to improve ssd performance. In Computer Design (ICCD), 2015 33rd IEEE International Conference on, pages 447--450. IEEE, 2015.
21. D. Marcus and A. Narasimha Reddy. A new i/o scheduler for solid state devices. Technical report, TAMU-ECE-2009--02, 2009.
22. J. Ouyang, S. Lin, S. Jiang, Z. Hou, Y. Wang, and Y. Wang. Sdf: software-defined flash for web-scale internet storage systems. In ACM SIGPLAN Notices, volume 49, pages 471--484. ACM, 2014.
23. Z. Qin, Y. Wang, D. Liu, and Z. Shao. A two-level caching mechanism for demand-based page-level address mapping in nand flash memory storage systems. In Proceedings of RTAS, 2011.
24. 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 Proceedings of the 48th Design Automation Conference, pages 17--22. ACM, 2011.
25. C. Wu and T. Kuo. An adaptive two-level management for the flash translation layer in embedded systems. In Computer-Aided Design, 2006. ICCAD'06. IEEE/ACM International Conference on, pages 601--606. IEEE, 2006.
26. M. Yang, Y. Chang, T. Kuo, and P. Huang. Capacity-independent address mapping for flash storage devices with explosively growing capacity. IEEE Trans. Computers, 65(2):448--465, 2016.
27. Y. Zhou, F. Wu, P. Huang, X. He, C. Xie, and J. Zhou. An efficient page-level ftl to optimize address translation in flash memory. In Proceedings of EuroSys. ACM, 2015.