臺灣博碩士論文加值系統

固態硬碟是當前主流的儲存裝置，而在多進程系統中，公平資源分配是一件需要考慮的事情。現有的公平調度器都設計再主機端，然而程序公平性卻有可能會因為固態硬碟觸發垃圾回收而被破壞。我們發現現有的主機公平調度器並沒有考量到垃圾回收帶來的負擔，並導致太慢處理硬碟的資源再分配。這篇論文考量將公平性延伸到儲存裝置內部，並設計一個讓程序不會承擔太多額外的垃圾回收負擔。另外為了讓主機端的調度器能夠及時針對垃圾回收有所反應，我們讓固態硬碟主動告知主機一些資訊，以便讓主機調度器能夠正確分配硬碟資源給各個程序。實驗結果顯示，所設計的機制可以再達到公平性的同時也增加吞吐量。

Solid-state disk (SSD) drives are the mainstream solutions for massive data storage today. For modern computer systems, fair resource assignment is a critical design consideration and has drew great interests in recent years. Although there are several fairness I/O schedulers proposed on the host side for SSDs, process fairness could still be dramatically degraded if garbage collection (GC) is triggered in the device side. We found that existing host-side I/O schedulers cannot achieve fairness because they did not consider the GC cost and update the assigned resource with GC cost too late. This paper proposed a novel device side I/O scheduling strategy in SSD controllers to achieve true fairness working with existing I/O schedulers of SSDs. This work is the first to consider fairness down to the device level. The proposed scheduling approach can guarantee that the processes will suffer little GC overhead if the processes barely introduce GCs. Experimental results with a wide range of workloads verify that the proposed technique can achieve fairness as well as improve the throughput significantly.

Abstract iii
List of Figures vi List of Tables viii
Chapter 1 Introduction 1
Chapter 2 Background and Related Work 4
2.1 SSD storage system . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Fairness I/O Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 3 Motivation 11 Chapter 4 Mechanism 16
4.1 Device Side module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1.1 GC-Penalty Quota Allocation . . . . . . . . . . . . . . . . . . 18
4.1.2 GC-Penalty Quota Update . . . . . . . . . . . . . . . . . . . . 19
4.2 Host side module: GC-Timer Setup . . . . . . . . . . . . . . . . . . . 20
4.3 Implementation Complexity . . . . . . . . . . . . . . . . . . . . . . . 22
Chapter 5 Experiment 24 5.1
Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Synthetic Workload Evaluation . . . . . . . . . . . . . . . . . . . . . 27
5.2.1 Fairness and Throughput . . . . . . . . . . . . . . . . . . . . . 27
5.2.2 Request Size Sensitivity . . . . . . . . . . . . . . . . . . . . . 29
5.2.3 FGC vs. Preemptive GC . . . . . . . . . . . . . . . . . . . . . 29
5.3 Real Workload Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 30
Chapter 6 Conclusion 38
Bibliography 39

[1] NVM Express. http://www.nvmexpress.org/. Accessed: 2017-09-26.
[2] Micron Technology. MT29F512G08CUAAA NAND Flash Memory Datasheet, 2009.
[3] N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. S. Manasse, and R. Panigrahy. Design tradeos for ssd performance. In USENIX Annual Technical Conference, volume 8, pages 57–70, 2008.
[4] O. Application. I/o. umass trace repository, 2007.
[5] S. N. I. Association et al. Snia iotta repository. Microsoft Enterprise Traces, Colorado Springs, Colorado (iotta. snia. org/traces/130), 2011.
[6] J. Axboe. Linux block io—present and future. In Ottawa Linux Symp, pages 51–61, 2004.
[7] L.-P. Chang, T.-W. Kuo, and S.-W. Lo. Real-time garbage collection for flashmemory storage systems of real-time embedded systems. ACM Transactions on Embedded Computing Systems (TECS), 3(4):837–863, 2004.
[8] M. Jung, W. Choi, S. Srikantaiah, J. Yoo, and M. T. Kandemir. Hios: A host interface i/o scheduler for solid state disks. ACM SIGARCH Computer Architecture News, 42(3):289–300, 2014.
[9] M. Jung, R. Prabhakar, and M. T. Kandemir. Taking garbage collection overheads off the critical path in ssds. In Proceedings of the 13th International Middleware Conference, pages 164–186. Springer-Verlag New York, Inc., 2012.
[10] B. S. Kim and S. L. Min. Qos-aware flash memory controller. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2017 IEEE, pages 51– 62. IEEE, 2017.
[11] J. Kim, D. Lee, and S. H. Noh. Towards slo complying ssds through ops isolation. In FAST, pages 183–189, 2015.
[12] J. Lee, Y. Kim, G. M. Shipman, S. Oral, and J. Kim. Preemptible i/o scheduling of garbage collection for solid state drives. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(2):247–260, 2013.
[13] J. Lee, Y. Kim, G. M. Shipman, S. Oral, F. Wang, and J. Kim. A semi-preemptive garbage collector for solid state drives. In Performance Analysis of Systems and Software (ISPASS), 2011 IEEE International Symposium on, pages 12–21. IEEE, 2011.
[14] S. Park and K. Shen. Fios: a fair, ecient flash i/o scheduler. In FAST, pages 1–1, 2012.
[15] S.-H. Park, D.-g. Kim, K. Bang, H.-J. Lee, S. Yoo, and E.-Y. Chung. An adaptive idle-time exploiting method for low latency nand flash-based storage devices. IEEE Transactions on Computers, 63(5):1085–1096, 2014.
[16] N. Shahidi, M. Arjomand, M. Jung, M. T. Kandemir, C. R. Das, and A. Sivasubramaniam. Exploring the potentials of parallel garbage collection in ssds for enterprise storage systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–1. IEEE Press, 2016.
[17] K. Shen and S. Park. Flashfq: A fair queueing i/o scheduler for flash-based ssds. In USENIX Annual Technical Conference, pages 67–78, 2013.
[18] W. Wu, S. Traister, J. Huang, N. D. Hutchison, and S. Sprouse. Pre-emptive garbage collection of memory blocks, Jan. 7 2014. US Patent 8,626,986.
[19] Q. Xu, H. Siyamwala, M. Ghosh, T. Suri, M. Awasthi, Z. Guz, A. Shayesteh, and V. Balakrishnan. Performance analysis of nvme ssds and their implication on real world databases. In Proceedings of the 8th ACM International Systems and Storage Conference, page 6. ACM, 2015.