Abstract

The NAND based SSD is a tremendous challenge for file system page cache management design as it possess inbuilt imbalance in reading and writing speeds. The present disk-based page cache management policies adopt strategies to maximize the page hit ratio and treat the cost of page read and writes are equal rather than fully exploiting the characteristics of the SSD. Therefore there exists slowness in SSD write which eventually affects the SSD endurance. In special cases like in random writes there exists a problem of augmented write amplification resulting in penalty of write performance. Therefore, a new page replacement algorithm is needed for storage systems based on NAND flash memory. The aim of this study is to propose a new page replacement algorithm for operating systems which focuses on reducing the replacement cost and I/O execution time. Trace-driven simulations show that the proposed algorithm performs better than existing algorithms in terms of the replacement cost and I/O execution time.

Keywords:

Data clusters, enlarged write, full merge, random write, switch merge, write amplification, write back cache,

References

1. Aloise, D., A. Deshpande, P. Hansen and P. Popat, 2009. NP hardness of Euclidean sum-of-squares clustering. Mach. Learn., 75(2): 245-248.
   CrossRef    
2. Chen, F., T. Luo and X. Zhang, 2011. CAFTL: A content-aware flash translation layer enhancing the lifespan of flash memory based solid state drives. Proceedings of the 9th USENIX Conference on File and Storage Technologies. San Joes, USA.
   
3. Cook, H., J. Ellithorpe, L. Keys and A. Waterman, Year. Iotafs: Exploring File System Optimizations for SSDs. University of California at Berkeley.
   
4. Gal, E. and S. Toledo, 2005. Mapping structures for flash memories: Techniques and open problems. Proceedings of the IEEE International Conference on Software Science, Technology and Engineering, pp: 83-92.
   CrossRef    
5. Gill, B.S. and D.S. Modha, 2005. WOW: Wise ordering for writes-combining spatial and temporal locality in non-volatile caches. Proceeding of the 4th USENIX Conference on File and Storage Technologies (FAST'05), pp: 129-142.
   PMid:15642392    
6. Gill, B.S., M. Ko, B. Debnath and W. Belluomini, 2009. STOW: A spatially and temporally optimized write caching algorithm. Proceedings of the USENIX Annual Technical Conference (USENIX'09), pp: 26-26.
   PMid:19832972 PMCid:PMC2770041    
7. Hitz, D., J. Lau and M. Malcolm, 1994. File system design for an NFS file server appliance. Technical Report 3002, Proceeding of USENIX Winter Technical Conference. USENIX Association, Berkeley, CA, USA, pp: 19-19.
   
8. Intel Corporation, 1998. Understanding the Flash Translation Layer (FTL) Specification. Application Note AP-684.
   
9. Jo, H., J.U. Kang, S.Y. Park, J.S. Kim and J. Lee, 2006. FAB: Flash-aware buffer management policy for portable media players. IEEE T. Consum. Electr., 52(2): 485-493.
   CrossRef    
10. Jung, H., H. Shim, S. Park, S. Kang and J. Cha, 2008. LRU-WSR: Integration of LRU and writes sequence reordering for flash memory. IEEE T. Consum. Electr., 54(3): 1215-1223.
    CrossRef    
11. Kim, H. and S. Ahn, 2008. BPLRU: A buffer management scheme for improving random writes in flash storage. Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST'08), pp: 239-252.
    
12. Lloyd, S.P., 1982. Least squares quantization in PCM. IEEE T. Inform. Theory, IT-28(2).
    
13. Megiddo, N. and D.S. Modha, 2003. ARC: A self-tuning, low overhead replacement cache. Proceeding of 2nd USENIX Conference File and Storage Technologies (FAST). San Francisco, CA, USA.
    
14. Microsoft, 2010. SSD Extension for Disksim Simulation Environment. Retrieved form: http:// research. microsoft.com/en-us/downloads/b41019e 2-1d2b-44d8-b512-ba35ab814cd4.
    Direct Link
15. Min, C., K. Kim, H. Cho, S. Lee and Y. Eom, 2012. SFS: Random write considered harmful in solid state drives. Proceedings of the 10th Conference on File and Storage Technologies in FAST'12.
    
16. Ou, Y. and T. Harder, 2010. Clean first or dirty first?: A cost-aware self-adaptive buffer replacement policy. Proceeding of the 14th International Database Engineering and Applications Symposium, ACM, pp: 7-14.
    CrossRef    
17. Ou, Y., T. Härder and G.P. Jin, 2010. CFDC: A flash-aware buffer management algorithm for database systems. Proceedings of the 14th East European Conference on Advances in Databases and Information Systems (ADBIS'10).
    CrossRef    
18. Park, S., D. Jung, J. Kang, J. Kim and J. Lee, 2006. CFLRU: A Replacement Algorithm for Flash Memory. Proceeding of International Conference on Compilers, Architecture and Synthesis for Embedded System (CASES, 2006), pp: 234-241.
    CrossRef    
19. Qiu, S. and A.L.N. Reddy, 2013. NVMFS: A hybrid file system for improving random write in NAND-flash SSD. Proceeding of the IEEE 29th Symposium on Mass Storage Systems and Technologies (MSST, 2013), pp: 1-6.
    
20. Rosenblum, M. and J.K. Ousterhou, 1992. The design and implementation of a log-structured file system. ACM T. Comput. Syst., 10(1): 26-52.
    CrossRef    
21. Russinovich, M., 2006. DiskMon for Windows v2.01.
    Direct Link
22. Shu, F. and N. Obr, 2007. Data Set Management Commands Proposal for ATA8-ACS2.
    Direct Link
23. Woodhouse, D., 2001. JFFS: The Journaling Flash File System. Proceeding of the Ottawa Linux Symposium 2001.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.