Solid-State drives（SSDs）是廣泛用於消費者和企業系統中的儲存系統。由於SSDs具有Erase-Before-Write的特性，因此我們需要Flash-translation layer (FTL)進行Address translation和Garbage collection，特別是，Garbage collection (GC)會造成long tail latency(長時間等待)，使得IO request可能會有比平常多出數百倍的等待時間，這會造成整體系統的不穩定，特別造成嵌入式系統和企業儲存系統的可靠度問題。
本文提供一個能偵測短程與長程閒置時間的方法，透過運用閒置時間進行Garbage Collection來減少Long-tail latency。我們運用Short-term Idle time detector預測IO Request後的短程閒置時間，以此進行partial GC的live page copy，並運用Long-term Idle time detector預測較長程閒置時間，以此進行partial GC的Erase。我們透過P-table進行online learning，並且嚴格篩選預測的準確度來避免錯誤。在我們的實驗環境下，我們的方法相比RLGC能找出更多閒置時間，穩定維持SSDs的有效空間，來降低SSDs的long tail latency。

Solid-State Drives (SSDs) are widely used in consumer and enterprise storage systems. SSDs require Garbage collection due to its Erase-Before-Write characteristic. However, Garbage collection, which consists of read, write, and erase operation, may spend lots of time and block other requests. Moreover, Garbage collection could cause long-tail latency, which means hundreds of times longer response time than the usual one. Long-tail latency may cause system instability, especially on embedded systems and enterprise storage systems.
In this study, we propose Short-Term and Long-Term Idle Time Detector to exploit idle time. Afterward, we could reduce long-tail latency by doing Garbage Collection on idle time. We use the Short-term Idle Time Detector to predict short-term idle time after IO request to execute live page copy of partial GC. Then we use Long-term Idle Time Detector to predict the longer-term idle time to execute block erase. We conduct online learning through P-table. We select the prediction with high accuracy to avoid errors. The experimental results show that our method could find more idle time than RLGC, maintain the free blocks stably, and reduce the long tail latency of the SSDs.

[1] Gupta, Aayush, Youngjae Kim, and Bhuvan Urgaonkar. "DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings." ACM Trans. Des. Autom. Electron. Syst. 20, 3. ACM 2009.
[2] Bux W, Iliadis I. Performance of greedy garbage collection in flash-based solid-state drives. Performance Evaluation. 2010
[3] Compagnoni, Christian Monzio, et al. "Reviewing the evolution of the NAND Flash technology." Proceedings of the IEEE 105.9. IEEE, 2017.
[4] Micheloni, Rino, Seiichi Aritome, and Luca Crippa. "Array architectures for 3-D NAND flash memories." Proceedings of the IEEE 105.9. IEEE, 2017.
[5] Chang, Li-Pin, Tei-Wei Kuo, and Shi-Wu Lo. "Real-time garbage collection for flash-memory storage systems of real-time embedded systems." ACM Transactions on Embedded Computing Systems (TECS).ACM, 2004.
[6] Wei, Qingsong, et al. "WAFTL: A workload adaptive flash translation layer with data partition." 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST). IEEE, 2011.
[7] Wang, Yi, et al. "A real-time flash translation layer for NAND flash memory storage systems." IEEE Transactions on Multi-Scale Computing Systems 2.1. IEEE, 2016.
[8] Yan, Shiqin, et al. "Tiny-tail flash: Near-perfect elimination of garbage collection tail latencies in NAND SSDs." ACM Transactions on Storage (TOS) 13.3. ACM, 2017
[9] Zhang, Qi, et al. "Lazy-RTGC: A real-time lazy garbage collection mechanism with jointly optimizing average and worst performance for NAND flash memory storage systems." ACM Transactions on Design Automation of Electronic Systems (TODAES) 20.3. ACM, 2015.
[10] Kang, Wonkyung, Dongkun Shin, and Sungjoo Yoo. "Reinforcement learning-assisted garbage collection to mitigate long-tail latency in SSD." ACM Transactions on Embedded Computing Systems (TECS) 16.5s (2017): 1-20.
[11] Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 135. Cambridge: MIT press, 1998.
[12] Kang, Wonkyung, and Sungjoo Yoo. "Dynamic management of key states for reinforcement learning-assisted garbage collection to reduce long tail latency in SSD." Proceedings of the 55th Annual Design Automation Conference, 2018.
[13] Kang, Wonkyung, and Sungjoo Yoo. "Q-Value Prediction for Reinforcement Learning Assisted Garbage Collection to Reduce Long Tail Latency in SSD." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019.
[14] Lee, Junghee, et al. "Preemptible I/O scheduling of garbage collection for solid state drives." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32.2. IEEE, 2013.
[15] Samsung Electronics Co., Ltd., “Samsung v-nand technology,”2014. [Online]. Available: https://www.samsung.com/us/business/oemsolutions/pdfs/V-NAND technology P.pdf
[16] Kwon, Miryeong, et al. "TraceTracker: Hardware/software co-evaluation for large-scale I/O workload reconstruction." 2017 IEEE International Symposium on Workload Characterization (IISWC). IEEE, 2017
[17] SNIA, “I/o trace data files,” 2008. [Online]. Available: http://iotta.snia.org/traces