Zhibing Sha
Abstract
This article proposes a low I/O intensity-aware scheduling scheme on garbage collection (GC) in SSDs for minimizing the I/O long-tail latency to ensure I/O responsiveness. The basic idea is to assemble partial GC operations by referring to several determinable factors (e.g., I/O characteristics) and dispatch them to be processed together in idle time slots of I/O processing. To this end, it first makes use of Fourier transform to explore the time slots having relative sparse I/O requests for conducting time-consuming GC operations, as the number of affected I/O requests can be limited. After that, it constructs a mathematical model to further figure out the types and quantities of partial GC operations, which are supposed to be dealt with in the explored idle time slots, by taking the factors of I/O intensity, read/write ratio, and the SSD use state into consideration. Through a series of simulation experiments based on several realistic disk traces, we illustrate that the proposed GC scheduling mechanism can noticeably reduce the long-tail latency by between 5.5% and 232.3% at the 99.99th percentile, in contrast to state-of-the-art methods.
- W. Choi, and M. Kandemir. 2018. Parallelizing garbage collection with I/O to improve flash resource utilization. In HPDC’18.Google Scholar
- S. Choudhuri and T. Givargis. 2008. Deterministic service guarantees for NAND flash using partial block cleaning. In CODES+ISSS’08.Google Scholar
- J. Cui, Y. Zhang, and J. Huang. 2018. ShadowGC: Cooperative garbage collection with multi-level buffer for performance improvement in NAND flash-based SSDs. In DATE’18.Google Scholar
- C. Gao, L. Shi, and Y. Di. 2018. Exploiting chip idleness for minimizing garbage collection–induced chip access conflict on SSDs. ACM Trans. Des. Automat. Electron. Syst.2018. DOI:https://doi.org/10.1145/3131850Google Scholar
- S. Hahn, J. Kim, and S. Lee. 2015. To collect or not to collect: Just-in-time garbage collection for high-performance SSDs with long lifetimes. In DAC.Google Scholar
- T. Hatanakay, R. Yajima, and T. Horiuchi. 2010. Ferroelectric (Fe)-NAND flash memory with batch write algorithm and smart data store to the nonvolatile page buffer for data center application high-speed and highly reliable enterprise solid-state drives. IEEE Solid-state Circ., 2010. DOI:https://doi.org/10.1109/JSSC.2010.2061650Google Scholar
- D. Hong, and J. Park. 2019. Improving SSD performance using adaptive restricted-copyback operations. In NVMSA’19.Google Scholar
- Y. Hu, H. Jiang, and D. Feng. 2013. Exploring and exploiting the multilevel parallelism inside SSDs for improved performance and endurance. Trans. Comput., 2013. DOI:https://doi.org/10.1109/TC.2012.60Google Scholar
- M. Jung, R. Prabhakar, and M. Kandemir. 2012. Taking garbage collection overheads off the critical path in SSDs. In Middleware’12.Google Scholar
- M. Jung, W. Choi, and M. Kwon. 2019. Design of a host interface logic for GC-Free SSDs. J. Technol. Comput. Aided Des., 2019. DOI:https://doi.org/10.1109/TCAD.2019.2919035Google Scholar
- W. Kang, D. Shin, and S. Yoo. 2017. Reinforcement learning-assisted garbage collection to mitigate long-tail latency in SSD. Trans. Embed. Comput. Syst.2017.Google Scholar
- B. Kim, H. Yang, and S. Min. 2018. AutoSSD: An autonomic SSD architecture. In ATC’18.Google Scholar
- S. Kim, J. Bae, and H. Jang. 2019. Practical erase suspension for modern low-latency SSDs. In ATC’19.Google Scholar
- J. Kim, K. Lim, and Y. Jung. 2019. Alleviating garbage collection interference through spatial separation in all flash arrays. In ATC’19.Google Scholar
- C. Lee, T. Kumano, and T. Matsuki. 2017. Understanding storage traffic characteristics on enterprise virtual desktop infrastructure. In SYSTOR’17.Google Scholar
- J. Lee, Y. Kim, and G. Shipman. 2013. Preemptible I/O scheduling of garbage collection for solid state drives. In J. Technol. Comput. Aided Des.2013. DOI:https://doi.org/10.1109/TCAD.2012.2227479Google Scholar
- J. Li, X. Xu, and X. Peng. 2019. Pattern-based write scheduling and read balance-oriented wear-leveling for solid state drivers. In MSST’19.Google Scholar
- N. Masters. 1995. Novel and Hybrid Algorithms for Time Series Prediction. John Wiley & Sons, Inc..Google Scholar
- S. Tashpulatov. 2013. Estimating the volatility of electricity prices: The case of the England and Wales wholesale electricity market. Energy Policy 60 (2013), 81–90.Google ScholarCross Ref
- H. Nguyen, M. Naeem, and N. Wichitaksorn. 2019. A smart system for short-term price prediction using time series models. Comput. Electric. Eng., 2019. DOI:https://doi.org/10.1016/j.compeleceng.2019.04.013Google Scholar
- C. Matsui, C. Sun, and K. Takeuchi. 2017. Design of hybrid SSDs with storage class memory and NAND flash memory. In PIEEE’17.Google Scholar
- MSRC Traces. http://iotta.snia.org/traces/388.Google Scholar
- N. Shahidi, M. Arjomand, and M. Jung. 2016. Exploring the potentials of parallel garbage collection in SSDs for enterprise storage systems. In SC’16.Google Scholar
- H. Sorensen, D. Jones, and M. Heideman. 1987. Real-valued fast Fourier transform algorithms. In TASSP’87.Google Scholar
- F. Wu, J. Zhou, and S. Wang. 2018. FastGC: Accelerate garbage collection via an efficient copyback-based data migration in SSDs. In DAC’18.Google Scholar
- G. Wu and X. He. 2014. Reducing SSD read latency via NAND flash program and erase suspension. In FAST’14.Google Scholar
- S. Yan, H. Li, and M. Hao. 2017. Tiny-tail flash: Near-perfect elimination of garbage collection tail latencies in NAND SSDs. In FAST’17.Google Scholar
- Q. Zhang, Q. Li, and L. Wang. 2015. Lazy-RTGC: A real-time lazy garbage collection mechanism with jointly optimizing average and worst performance for NAND flash memory storage systems. ACM Trans. Des. Automat. Electron. Syst.2015. DOI:https://doi.org/10.1145/2746236Google Scholar
- Y. Gala, G. Moshe, and J. Shehbaz. 2021. SSD-based workload characteristics and their performance implications. ACM Trans. Stor.2021. DOI:https://doi.org/10.1145/3423137Google Scholar
- YCSB RocksDB SSD Traces. 2020. Retrieved from http://iotta.snia.org/traces/28568.Google Scholar
- MP5515. Retrieved from https://www.monolithicpower.com/en/mp5515.html.Google Scholar
- Samsung 970 EVO Datasheet. Retrieved from https://www.samsung.com/semiconductor/global.semi.static/Samsung_NVMe_SSD_970_EVO_Data_Sheet_Rev.1.0.pdf.Google Scholar
- F. Ulaby, E. Michielssen, and U. Ravaioli. 2010. Fundamentals of Applied Electromagnetics (6th ed.). Prentice Hall.Google Scholar
- M. Bouksiaa, and F. Trahay. 2019. Using differential execution analysis to identify thread interference. IEEE Trans. Parallel Distrib. Syst.2019. DOI:https://doi.org/10.1109/TPDS.2019.2927481Google Scholar
- B. Mao, S. Wu, and L. Duan. 2017. Improving the SSD performance by exploiting request characteristics and internal parallelism. J. Technol. Comput. Aided Des.2017. DOI:https://doi.org/10.1109/TCAD.2017.2697961Google Scholar
- T. Chen, Y. Chang, and C. Ho. 2016. Enabling sub-blocks erase management to boost the performance of 3D NAND flash memory. In DAC’16.Google Scholar
- H. Chang, C. Ho, Y. Chang. 2016. How to enable software isolation and boost system performance with sub-block erase over 3D flash memory. In CODES+ISSS’16.Google Scholar
- C. Liu, J. Kotra and M. Jung. 2018. PEN: Design and evaluation of partial-erase for 3D NAND-based high density SSDs. In FAST’18.Google Scholar
Index Terms
- Low I/O Intensity-aware Partial GC Scheduling to Reduce Long-tail Latency in SSDs
Recommendations
Reinforcement Learning-Assisted Garbage Collection to Mitigate Long-Tail Latency in SSD
Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017NAND flash memory is widely used in various systems, ranging from real-time embedded systems to enterprise server systems. Because the flash memory has erase-before-write characteristics, we need flash-memory management methods, i.e., address ...
Let It Go: Relieving Garbage Collection Pain for Latency Critical Applications in Golang
HPDC '23: Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed ComputingGarbage Collection (GC) is a representative automatic memory manager widely deployed in popular programming languages, such as Java, C\#, and Golang (Go). Through GC, these languages provide programmers with flexibility and safety. However, GC leads to ...
Impact of Data Locality on Garbage Collection in SSDs: A General Analytical Study
ICPE '15: Proceedings of the 6th ACM/SPEC International Conference on Performance EngineeringSolid-state drives (SSDs) necessitate garbage collection (GC) to erase data blocks and reclaim the space of invalidated data, and GC inevitably introduces additional writes due to data relocation. The performance of GC, which is quantified by cleaning ...
Comments