Journal of Internet Computing and Services (인터넷정보학회논문지)

Korean Society for Internet Information (한국인터넷정보학회)
권호 표지
DOI QR코드

DOI QR Code

Block Replacement Scheme based on Reuse Interval for Hybrid SSD System

Hybrid SSD 시스템을 위한 재사용 간격 기반 블록 교체 기법

  • Yoo, Sanghyun (College of Information Communication and Engineering, Sungkyunkwan University) ;
  • Kim, Kyung Tae (College of Information Communication and Engineering, Sungkyunkwan University) ;
  • Youn, Hee Yong (College of Information Communication and Engineering, Sungkyunkwan University)
  • Received : 2015.08.18
  • Accepted : 2015.09.18
  • Published : 2015.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

Due to the advantages of fast read/write operation and low power consumption, SSD(Solid State Drive) is now widely adopted as storage device of smart phone, laptop computer, server, etc. However, the shortcomings of SSD such as limited number of write operations and asymmetric read/write operation lead to the problem of shortened life span of SSD. Therefore, the block replacement policy of SSD used as cache for HDD is very important. The existing solutions for improving the lifespan of SSD including the LARC scheme typically employ the LRU algorithm to manage the SSD blocks, which may increase the miss rate in SSD due to the replacement of frequently used block instead of rarely used block. In this paper we propose a novel block replacement scheme which considers the block reuse interval to effectively handle various data read/write patterns. The proposed scheme replaces the block in SSD based on the recency decided by reuse interval and age along with hit ratio. Computer simulation using workload trace files reveals that the proposed scheme consistently improves the performance and lifespan of SSD by increasing the hit ratio and decreasing the number of write operations compared to the existing schemes including LARC.

최근 SSD(Solid State Drive)는 빠른 읽기/쓰기, 저전력 등 다양한 장점을 가지고 있어 스마트폰, 노트북, 서버 등의 저장장치로 사용 영역이 확대되고 있다. 하지만, 플래시 메모리의 읽기 및 쓰기의 비대칭적 성능과 제한된 쓰기 횟수가 SSD의 수명을 단축시키는 문제가 있어서 캐쉬(cache)로 사용되는 SSD의 내용을 변경시키는 블록 교체 기법(block replacement policy)이 매우 중요하다. Hybrid SSD의 수명을 향상 시킬 수 있는 방법 중 하나로 LARC 기법이 있으나, LARC는 SSD블록 관리를 위해 기존 LRU알고리즘을 사용하기 때문에 빈번히 참조되는 블록이 오래된 블록 대신 교체되어 SSD 미스율을 증가시킴으로써 시스템의 성능이 저하되는 문제점이 발생한다. 따라서, 본 논문에서는 다양한 데이터 읽기, 쓰기 환경에 효과적으로 대응하기 위해 블록의 재사용 간격을 고려한 새로운 블록 교체 기법을 제안한다. 제안된 기법은 블록 재사용 간격(Reuse interval)과 Age를 기반으로 최근성(Recency)을 추출하고 참조빈도(Frequency)를 같이 고려하여 블록을 교체한다. Workload 기반 Trace를 이용한 실험결과, 제안하는 기법은 여러가지의 기존 블록 교체 기법 및 LARC 알고리즘과 비교하여 쓰기 횟수 감소와 히트율 향상을 통해 시스템 성능과 SSD의 수명을 연장시킨다.

Keywords

References

  1. S. Huang, Q. Wei, C. Chen, D. Feng, "Improving flash-based disk cache with lazy adaptive replacement", in Mass Storage Systems and Technologies (MSST), IEEE 29th Symposium on, IEEE, 2013, pp. 1-10. http://dx.doi.org/10.1109/MSST.2013.6558447
  2. Y. Liu, X. Ge, X. Huang, D. H. Du, "MOLAR: A Cost-Efficient, High-Performance SSD-Based Hybrid Storage Cache", The Computer Journal, 2015. http://dx.doi.org/10.1093/comjnl/bxu156
  3. Q. Wei, L. Zeng, J. Chen, C. Chen, "A Popularity-Aware Buffer Management to Improve Buffer Hit Ratio and Write Sequentiality for Solid-State Drive", IEEE Transactions on Magnetics, 49(6), 2013, pp. 2786-2793. http://dx.doi.org/10.1109/TMAG.2013.2249579
  4. A. Dan, D. Towsley, "An approximate analysis of the LRU and FIFO buffer replacement schemes", Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1990, pp. 143-152. http://dx.doi.org/10.1145/98460.98525
  5. J.T. Robinson and M. V. Devarakonda, "Data cache management using frequency-based replacement", Proceedings, ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1990, pp. 134-142. http://dx.doi.org/10.1145/98460.98523
  6. D. Lee, J. Choi, J. H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim, "LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies", IEEE Trans. Computers, vol. 50, no. 12, pp. 1352-1360, 2001. http://doi.ieeecomputersociety.org/10.1109/TC.2001.970573
  7. T. Johnson and D. Shasha, "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm," in VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 1994, pp. 439-450. http://www.vldb.org/conf/1994/P439.PDF
  8. S. Jiang, X. Zhang, "LIRS: An Efficient low interreference recency set replacement policy to improve buffer cache performance", 2002 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 2002, pp. 31-42. http://dx.doi.org/10.1145/511334.511340
  9. N. Megiddo, D. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache", in Proceedings of the 2nd USENIX Conference on File and Storage Technologies, 2003, pp. 115-130. http://dl.acm.org/citation.cfm?id=1090708
  10. S. Park, D. Jung, J. Kang, J. Kim, J. Lee, "CFLRU: A Replacement Algorithm for Flash Memory", In Proceedings of the international conference on Compilers, architecture and synthesis for embedded systems, ACM, 2006, pp. 234-241. http://dx.doi.org/10.1145/1176760.1176789
  11. H. Kim, S. Ahn, "BPLRU: A buffer management scheme for improving random writes in flash storage", In Proceedings of the FAST, Vol8, 2008, pp. 1-14. http://static.usenix.org/legacy/events/fast08/tech/full_papers/kim/kim.pdf
  12. G. Graefe, "The five-minute rule twenty years later, and how flash memory changes the rules", in Proceedings of the 3rd international workshop on Data management on new hardware. ACM, 2007, pp.6. http://dx.doi.org/10.1145/1363189.1363198
  13. UMass Trace Repository. [Online]. Available: http://traces.cs.umass.edu/index.php/Storage/Storage
  14. F. Chen, S. Jiang, X. Zhang, "SmartSaver: Turning Flash Drive into a Disk Energy Saver for Mobile Computers,", Proceedings of the International Symposium on Low Power Electronics and Design, pp.412-417, 2006. http://dx.doi.org/10.1109/LPE.2006.4271878
  15. Y. Kim, J. Kim, "ARC-H: Adaptive replacement cache management for heterogeneous storage devices", Journal of Systems Architecture Vol 58(2), 2012, pp. 86-97. http://dx.doi.org/doi:10.1016/j.sysarc.2011.12.002