臺灣博碩士論文加值系統

近年來，使用者傾向將資料存放在共享儲存系統上。此舉不僅可以節省硬體建置成本，也節省管理上的成本。傳統上，共享儲存系統大多使用磁碟當作儲存媒介。然而，近年來固態硬碟的優異效能讓系統管理者開始將固態硬碟整合進儲存系統中。典型的儲存系統中，使用者通常會指定其所需要之服務目標(Service Level Objectives, SLO)，系統服務提供者使用效能隔離機制來滿足每一使用者的目標。達成此目的關鍵步驟就是精確估算每筆I/O的實際資源消耗。然而，使用者彼此間之互相干擾卻很可能會影響此估算，進而阻礙效能隔離之效果。
由於固態硬碟和傳統磁碟的物理及效能特性存在不少差異，使得使用者彼此間互相干擾的原因也有所不同。我們發現固態硬碟儲存系統中，阻礙效能隔離的干擾源有兩類: 排隊干擾(Queuing Interference)及垃圾收集干擾(Garbage Collection Interference)。為了因應這兩類干擾，本論文提出一個針對固態硬碟特性而設計的效能隔離方法，稱之為VSSD。在VSSD中，我們透過改良版的I/O排程方法及快閃記憶體轉換層來分別克服排隊干擾及垃圾清除干擾，以達成效能隔離的目標。
另外，由於在固態硬碟上，使用者獲得的效能和其在儲存系統佔有的空間大小有正向關係，而且儲存系統使用者不容易估算自己最適合的空間配置大小，此可能造成高估或低估所需空間的情形。因此，我們希望透過善用使用者配置空間將效能再提升。為此，我們額外設計了一個儲存空間暫時轉移方法，稱之為RALIS，企圖在盡量保持效能隔離的前提下，再進一步改善整體效能。RALIS能將一使用者(即Lender)之多餘空間暫時借給較需要的使用者(即Borrower)。另一方面，在Lender需要空間前，RALIS會啟動空間歸還機制，讓Lender免於受影響。
實驗中，我們模擬數個固態硬碟共用情景。實驗結果證明，VSSD能有效地克服干擾，使得多個共存使用者可以得到類似獨立使用儲存系統時的效能。此外，RALIS透過儲存空間暫時轉移分別可將效能改善高達374.1%，而且儲存系統的壽命也改善了35.9% 至85.6%。

Storing data in shared storage systems saves both hardware cost and management cost. Conventional shared storage systems use magnetic hard drives (HDDs) as the main storage media. In recent years, NAND flash-memory-based solid-state drives (SSDs) have been increasingly used in shared storage systems. Typically, storage users specify the target service-level objectives (SLO) for their virtual storage, and the system administrators need to provide performance isolation among the virtual storage to avoid SLO violations. To achieve performance isolation, accurate I/O cost accounting is crucial. However, the interferences among the competing virtual storage devices could lead to inaccurate I/O cost accounting and damage the performance isolation.
Since an SSD has very different features compared to a HDD, the interference sources could be also different. We have found that the main interference sources in the SSD-based shared system are queuing delay interference and the garbage collection interference. In this thesis, we propose a framework called VSSD to eliminate the interferences and then to achieve performance isolation. A novel I/O scheduler called FACO and a flash translation layer called ViSA are adopted to address the two interferences, respectively, in VSSD.
On the other hand, since the performance of a virtual storage device is usually highly related to the size of the provisioned space and it is difficult for users to estimate the actual required space, the space of the virtual storage devices may not be well-utilized. To address this, we design a run-time storage lending mechanism, called RALIS, to allow a virtual storage (i.e., borrower) to temporarily use the space belonging to other virtual storage that do not need the space in that moment (i.e., lenders), to boost the performance. RALIS dynamically determines the role (i.e., lender or borrower) of the virtual storage. To minimize the possible impact to the lenders, a block returning policy is used to make the borrowers to return the borrowed blocks before the lenders needs them.
Multiple sets of workloads were used to simulate the shared storage environment. The results show that the VSSD can eliminate the interferences and achieve performance isolation. In addition, RALIS can boost the performance of the borrowers effectively. The storage lifetime can also be extended significantly (35.9% to 85.6%) by RALIS.

摘要 I
ABSTRACT II
誌謝 IV
目錄 V
LIST OF FIGURES VII
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 Motivation Example of VSSD 6
1.1.1 Garbage Collection Interference 6
1.1.2 Queuing Delay Interference 7
CHAPTER 2 BACKGROUND 10
2.1 Solid-State Drives 10
2.2 Shared Storage 12
CHAPTER 3 RELATED WORK 14
3.1 Performance Isolation 14
3.1.1 Fair Sharing on HDD-based Systems. 14
3.1.2 Fair Sharing on Flash-memory-based Systems. 17
3.1.3 Data Separation on Flash-memory-based System. 19
3.2 Space Allocation 21
3.2.1 Cache Space Allocation 21
3.2.2 Primary Storage Allocation 24
CHAPTER 4 DESIGN AND IMPLEMENTATION 26
4.1 Design of VSSD 26
4.1.1 FACO I/O Scheduler 30
4.1.2 ViSA Flash Translation Layer 38
4.2 DESIGN OF RALIS 46
4.2.1 Determining the User Roles 48
4.2.2 Block Lending and Returning 51
4.2.3 Estimating the Borrowing Limits 54
CHAPTER 5 PERFORMANCE EVALUATION 62
5.1 EVALUATION of VSSD 66
5.1.1 Effectiveness of the FACO Scheduler and the ViSA FTL 66
5.1.2 Effectiveness of VSSD 70
5.1.3 Performance under Different Levels of Space Separation 79
5.1.4 CPU Overhead and Code Size 82
5.2 EVALUATION of RALIS 86
5.2.1 Evaluating the Effectiveness of PRR 86
5.2.2 Evaluating the Effectiveness of RALIS 90
5.2.3 CPU Overhead and Code Size 97
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 99
REFERENCES 101

1.C.R. Lumb, A. Merchant, and G.A. Alvarez. Façade: virtual storage devices with performance guarantees. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies. 2003.
2.M. Karlsson, C. Karamanolis, and X. Zhu, Triage: performance differentiation for storage systems using adaptive control. ACM Trans. Storage, 2005. 1(4): p. 457-480.
3.A. Gulati, I. Ahmad, and C.A. Waldspurger. PARDA: proportional allocation of resources for distributed storage access. In Proceedings of the 7th USENIX Conference on File and Storage Technologies. 2009.
4.M. Wachs, M. Abd-El-Malek, E. Thereska, and G.R. Ganger. Argon: performance insulation for shared storage servers. In Proceedings of the 5th USENIX Conference on File and Storage Technologies. 2007.
5.S. Park and K. Shen. FIOS: a fair, efficient flash I/O scheduler. In Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012.
6.P. Gang and T. Chiueh. Availability and fairness support for storage QoS guarantee. In Proceedings of the 28th International Conference on Distributed Computing Systems. 2008.
7.W. Jin, J.S. Chase, and J. Kaur. Interposed proportional sharing for a storage service utility. In Proceedings of International Conference on Measurement and Modeling of Computer Systems. 2004.
8.J. Axboe. Linux block IO—present and future. In Proceedings of Ottawa Linux Symposium. 2004.
9.X. Zhang and S. Jiang. InterferenceRemoval: removing interference of disk access for MPI programs through data replication. In Proceedings of the 24th ACM International Conference on Supercomputing. 2010.
10.D. Li, X. Liao, H. Jin, B. Zhou, and Q. Zhang, A new disk I/O model of virtualized cloud environment. IEEE Trans. Parallel and Distributed Syst., 2012. 24(6): p. 1129-1138.
11.Y. Oh, J. Choi, D. Lee, and S.H. Noh. Caching less for better performance: balancing cache size and update cost of flash memory cache in hybrid storage systems. In Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012.
12.S. Byan, J. Lentini, A. Madan, L. Pabón, M. Condict, J. Kimmel, S. Kleiman, C. Small, and M. Storer. Mercury: Host-side flash caching for the data center. In Proceedings of the 28th Symposium on Mass Storage Systems and Technologies. 2012.
13.Y. Klonatos, T. Makatos, M. Marazakis, M.D. Flouris, and A. Bilas. Azor: Using Two-level Block Selection to Improve SSD-based I/O caches. In Proceedings of IEEE Networking, Architecture and Storage. 2011.
14.J. Schindler, S. Shete, and K.A. Smith. Improving throughput for small disk requests with proximal I/O. In Proceedings of the 9th USENIX Conference on File and Stroage Technologies. 2011.
15.S. Im and D. Shin, Flash-aware RAID techniques for dependable and high-performance flash memory SSD. IEEE Trans. Comput., 2010. 60(1): p. 80-92.
16.S. Im and D. Shin. Delayed partial parity scheme for reliable and high-performance flash memory SSD. In Proceedings of the IEEE 26th Symposium on Mass Storage Systems and Technologies. 2010.
17.M. Balakrishnan, A. Kadav, V. Prabhakaran, and D. Malkhi. Differential RAID: Rethinking RAID for SSD Reliability. In Proceedings of the 5th European Conference on Computer Systems. 2010.
18.D. Malkhi, M. Balakrishnan, J.D. Davis, V. Prabhakaran, and T. Wobber, From paxos to CORFU: a flash-speed shared log. ACM SIGOPS Operating Systems Review, 2012. 46(1): p. 47-51.
19.M. Stokely, A. Mehrabian, C. Albrecht, F. Labelle, and A. Merchant. Projecting disk usage based on historical trends in a cloud environment. In Proceedings of the 3rd workshop on Scientific Cloud Computing Date. 2012.
20.D. Petcu, H. González–Vélez, B. Nicolae, J.M. García–Gómez, E. Fuster–Garcia, and C. Sheridan. Next Generation HPC Clouds: A View for Large-Scale Scientific and Data-Intensive Applications. In Proceedings of Euro-Par 2014: Parallel Processing Workshops. 2014.
21.G. Laatikainen, O. Mazhelis, and P. Tyrväinen, Role of acquisition intervals in private and public cloud storage costs. Decision Support Systems, 2014. 57: p. 320-330.
22.S.T.N.W. Paper, Start Thin, Get Thin, and Stay Thin with Thin Provisioning Technology from Symantec and 3PAR. 2009.
23.L. Cherkasova and L. Staley. Measuring the capacity of a streaming media server in a utility data center environment. In Proceedings of the 10th ACM international conference on Multimedia. 2002.
24.C. Park, P. Talawar, D. Won, M. Jung, J. Im, S. Kim, and Y. Choi. A high performance controller for NAND flash-based solid state disk (NSSD). In Proceedings of IEEE 21st Non-Volatile Semiconductor Memory Workshop. 2006.
25.J. Kang, J. Kim, C. Park, H. Park, and J. Lee, A multi-channel architecture for high-performance NAND flash-based storage system. Journal of Systems Architecture, 2007. 53(9): p. 644-658.
26.D.W. Chang, H.H. Chen, D.J. Yang, and H.P. Chang, BLAS: block-level adaptive striping for solid-state drives. ACM Trans. Des. Autom. Electron. Syst., 2014. 19(2): p. 21-49.
27.J. Hsieh, H. Lin, and D. Yang, Multi-channel architecture-based FTL for reliable and high-performance SSD. IEEE Transactions on Computers, 2013. 63(12): p. 3079-3091.
28.P.C. Huang, Y.H. Chang, and T.W. Kuo, An index-based management scheme with adaptive caching for huge-scale low-cost embedded flash storages. ACM Trans. Des. Autom. Electron. Syst., 2013. 18(4): p. 56-81.
29.L.P. Chang and C.Y. Wen, Reducing asynchrony in channel garbage-collection for improving internal parallelism of multichannel solid-state disks. ACM Trans. Embed. Comput. Syst., 2014. 13(2s): p. 63.
30.L.P. Chang, T.W. Kuo, and S.W. Lo, Real-time garbage collection for flash-memory storage systems of real-time embedded systems. ACM Trans. Embed. Comput. Syst., 2004. 3(4): p. 837-863.
31.Q. Zhang, X. Li, L. Wang, T. Zhang, Y. Wang, and Z. Shao. Optimizing deterministic garbage collection in NAND flash storage systems. In Proceedings of the 21st IEEE Real-Time and Embedded Technology and Applications Symposium. 2015.
32.J. Lee, Y. Kim, G.M. Shipman, S. Oral, F. Wang, and J. Kim. A Semi-Preemptive Garbage Collector for Solid State Drives. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software. 2011.
33.J. Lee, Y. Kim, J. Kim, and G. Shipman, Synchronous I/O Scheduling of Independent Write Caches for an Array of SSDs. IEEE Computer Architecture Letters, 2014. 14(1): p. 79-82.
34.L.P. Chang and C.D. Du, Design and implementation of an efficient wear-leveling algorithm for solid-state-disk microcontrollers. ACM Trans. Des. Autom. Electron. Syst., 2009. 15(1): p. 1-36.
35.L.P. Chang and T.W. Kuo, Efficient management for large-scale flash-memory storage systems with resource conservation. ACM Trans. Storage, 2005. 1(4): p. 381-418.
36.M. Murugan and H.C. Du. Rejuvenator: a static wear leveling algorithm for NAND flash memory with minimized overhead. In Proceedings of the 27th Symposium on Mass Storage Systems and Technologies. 2011.
37.M.C. Yang, Y.H. Chang, C.W. Tsao, and P.C. Huang. New ERA: new efficient reliability-aware wear leveling for endurance enhancement of flash storage devices. In Proceedings of the 50th Annual Design Automation Conference. 2013.
38.P. Desnoyers. Analytic modeling of SSD write performance. In Proceedings of the 5th Annual International Systems and Storage Conference. 2012.
39.X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka. Write amplification analysis in flash-based solid state drives. In Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference. 2009. Haifa, Israel.
40.N. Jeremic, G. Muhl, A. Busse, and J. Richling. The Pitfalls of Deploying Solid-State Drive RAIDs. In Proceedings of the 4th Annual International Conference on Systems and Storage. 2011.
41.W.-H. Lin and L.-P. Chang. Dual greedy: Adaptive garbage collection for page-mapping solid-state disks. In Proceedings of Design, Automation ＆ Test in Europe Conference ＆ Exhibition (DATE), 2012. 2012.
42.D. Park and D.H.C. Du. Hot and Cold Data Identification for Flash Memory Using Multiple Bloom Filters. In Proceedings of the 27th Symposium on Mass Storage Systems and Technologies. 2011.
43.J. Hsieh, L. Chang, and T. Kuo. Efficient on-line identification of hot data for flash-memory management. In Proceedings of the 2005 ACM symposium on Applied computing. 2005.
44.J. Kim, D. Lee, and S.H. Noh. Towards SLO Complying SSDs Through OPS Isolation. In Proceedings of the 13th USENIX Conference on File and Storage Technologies. 2015.
45.X. Lin, Y. Mao, F. Li, and R. Ricci. Towards fair sharing of block storage in a multi-tenant cloud. In Proceedings of the 4th USENIX Conference on Hot Topics in Cloud Computing. 2012.
46.A. Gulati, C. Kumar, and I. Ahmad. Storage workload characterization and consolidation in virtualized environments. In Proceedings of Workshop on Virtualization Performance: Analysis, Characterization, and Tools. 2009.
47.M. Wachs, L. Xu, A. Kanevsky, and G.R. Ganger. Exertion-based billing for cloud storage access. In Proceedings of the 3rd USENIX Conference on Hot Topics in Cloud Computing. 2011.
48.F. Chen, R. Lee, and X. Zhang. Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing. In Proceedings of the 17th IEEE International Symposium on High Performance Computer Architecture. 2011.
49.J. Zhang, A. Sivasubramaniam, Q. Wang, A. Riska, and E. Riedel, Storage performance virtualization via throughput and latency control. ACM Trans. Storage, 2006. 2(3): p. 283-308.
50.X. Ling, H. Jin, S. Ibrahim, W. Cao, and S. Wu. Efficient disk I/O scheduling with QoS guarantee for Xen-based hosting platforms. In Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. 2012.
51.J. Bruno, J. Brustoloni, E. Gabber, B. Ozden, and A. Silberschatz. Disk scheduling with quality of service guarantees. In Proceedings of Multimedia Computing and Systems, 1999. IEEE International Conference on. 1999.
52.A. Povzner, T. Kaldewey, S. Brandt, R. Golding, T.M. Wong, and C. Maltzahn. Efficient Guaranteed Disk Request Scheduling with Fahrrad. In Proceedings of EuroSys’08. 2008.
53.D.J. Shakshober, Choosing an I/O scheduler for Red Hat Enterprise Linux 4 and the 2.6 kernel. In Red Hat magazine, 2005.
54.D. Skourtis, S. Kato, and S. Brandt. QBox: guaranteeing I/O performance on black box storage systems. In Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing. 2012.
55.J. Kim, C. Lee, S. Lee, I. Son, J. Choi, S. Yoon, H. Lee, S. Kang, Y. Won, and J. Cha. Deduplication in SSDs: Model and quantitative analysis. In Proceedings of the IEEE 28th Symposium on Mass Storage Systems and Technologies. 2012.
56.S. Boboila and P. Desnoyers. Write endurance in flash drives: measurements and analysis. In Proceedings of the 8th USENIX Conference on File and Storage Technologies. 2010.
57.C.H. Wu, An energy-efficient I/O request mechanism for multi-bank flash-memory storage systems. ACM Trans. Des. Autom. Electron. Syst., 2009. 14(1): p. 6.
58.M.L. Chiang, P. Lee, and R.C. Chang, Using data clustering to improve cleaning performance for flash memory. Software-Practice and Experience, 1999. 29(3): p. 267-290.
59.L.P. Chang, A hybrid approach to NAND-flash-based solid-state disks. IEEE Trans. Comput., 2010. 59(10): p. 1337-1349.
60.S. Im and D. Shin, ComboFTL: improving performance and lifespan of MLC flash memory using SLC flash buffer. Journal of Systems Architecture, 2010. 56(12): p. 641-653.
61.P.L. Wu, Y.H. Chang, and T.W. Kuo. A file-system-aware FTL design for flash-memory storage systems. In Proceedings of Design, Automation ＆ Test in Europe Conference ＆ Exhibition. 2009. Nice, France.
62.J. An and D. Shin. Offline deduplication-aware block separation for solid state disk. In Proceedings of the 11st USENIX Conference on File and Storage Technologies. 2013.
63.T. Luo, S. Ma, R. Lee, X. Zhang, D. Liu, and L. Zhou. S-CAVE: effective SSD caching to improve virtual machine storage performance. In Proceedings of the 22th international conference on Parallel architectures and compilation techniques. 2013.
64.F. Meng, L. Zhou, X. Ma, S. Uttamchandani, and D. Liu. vCacheShare: Automated Server Flash Cache Space Management in a Virtualization Environment. In Proceedings of USENIX Annual Technical Conference. 2014.
65.R. Koller, L. Marmol, R. Rangaswami, S. Sundararaman, N. Talagala, and M. Zhao. Write policies for host-side flash caches. In Proceedings of FAST. 2013.
66.Q. Yang and J. Ren. I-CASH: Intelligently Coupled Array of SSD and HDD. In Proceedings of the 17th International Symposium on High Performance Computer Architecture. 2011.
67.D.A. Holland, E.L. Angelino, G. Wald, and M.I. Seltzer. Flash caching on the storage client. In Proceedings of USENIX ATC'13 Proceedings of the 2013 USENIX conference on Annual Technical Conference. 2013.
68.D. Qin, A.D. Brown, and A. Goel. Reliable writeback for client-side flash caches. In Proceedings of Proceedings of the 2014 USENIX conference on USENIX Annual Technical Conference. 2014.
69.C. Li, P. Shilane, F. Douglis, H. Shim, S. Smaldone, and G. Wallace. Nitro: A Capacity-Optimized SSD Cache for Primary Storage. In Proceedings of USENIX Annual Technical Conference. 2014.
70.R. Koller, A.J. Mashtizadeh, and R. Rangaswami. Centaur: Host-side SSD Caching for Storage Performance Control. In Proceedings of the 12th IEEE International Conference on Autonomic Computing.
71.P. Sehgal, K. Voruganti, and R. Sundaram. SLO-aware hybrid store. In Proceedings of the 28th Symposium on Mass Storage Systems and Technologies. 2012.
72.C. Albrecht, A. Merchant, M. Stokely, M. Waliji, F. Labelle, N. Coehlo, X. Shi, and C.E. Schrock. Janus: optimal flash provisioning for cloud storage workloads. In Proceedings of the 2013 USENIX conference on Annual Technical Conference. 2013.
73.D.W. Chang, H.H. Chen, and W.-J. SU, VSSD: Performance Isolation in a Solid-State Drive. ACM Trans. Des. Autom. Electron. Syst., 2015.
74.M. Saxena, M.M. Swift, and Y. Zhang. Flashtier: a lightweight, consistent and durable storage cache. In Proceedings of the 7th ACM european conference on Computer Systems. 2012.
75.K. Qian, L. Yi, and J. Shu. ThinStore: Out-of-Band Virtualization with Thin Provisioning. In Proceedings of Networking, Architecture and Storage (NAS), 2011 6th IEEE International Conference on. 2011.
76.P. Ruiu, G. Caragnano, and L. Graglia. Automatic Dynamic Allocation of Cloud Storage for Scientific Applications. In Proceedings of Complex, Intelligent, and Software Intensive Systems (CISIS), 2015 Ninth International Conference on. 2015.
77.S. Kang and A.N. Reddy. Virtual Allocation: A scheme for flexible storage allocation. In Proceedings of OASIS workshop in conjunction with ASPLOS. 2004.
78.B. Nicolae, P. Riteau, and K. Keahey. Transparent Throughput Elasticity for IaaS Cloud Storage Using Guest-Side Block-Level Caching. In Proceedings of Utility and Cloud Computing (UCC), 2014 IEEE/ACM 7th International Conference on. 2014.
79.M. Huang, Y. Wang, Z. Liu, L. Qiao, and Z. Shao. A garbage collection aware stripping method for solid-state drives. In Proceedings of the 20th Asia and South Pacific Design Automation Conference. 2015.
80.M.L. Chiang, P.C.H. Lee, and R.C. Chang, Cleaning policies in mobile computers using flash memory. J. Syst. Software, 1999. 48(3): p. 213-231.
81.C.W. Tsao, Y.H. Chang, and M.C. Yang. Performance enhancement of garbage collection for flash storage devices: an efficient victim block selection design. In Proceedings of the 50th Annual Design Automation Conference. 2013.
82.J.W. Hsieh, Y.C. Zheng, Y.S. Peng, and P.H. Yeh, VAST: virtually associative sector translation for MLC storage systems. IEEE Trans. Computer-Aided Design of Integrated Circuits and Syst., 2013. 32(8): p. 1137-1150.
83.M.L. Chiao and D.W. Chang, ROSE: a novel flash translation layer for NAND flash memory based on hybrid address translation. IEEE Transactions on Computers, 2011. 60(6): p. 753-766.
84.Y.H. Chang, J.W. Hsieh, and T.W. Kuo, Improving flash wear-leveling by proactively moving static data. IEEE Trans. Comput., 2010. 59(1): p. 53-65.
85.J. Bucy, J. Schindler, S. Schlosser, and G. Ganger, The DiskSim simulation environment version 4.0 reference manual. 2008, Carnegie Mellon University.
86.R. McDougall and J. Mauro. FileBench. Available from: http://filebench.sourceforge.net.
87.T. Austin, E. Larson, and D. Ernst, An infrastructure for computer system modeling. IEEE Computer, 2002. 32(2): p. 59-67.
88.D. Tiwari, S. Boboila, S.S. Vazhkudai, Y. Kim, X. Ma, P.J. Desnoyers, and Y. Solihin. Active flash: Towards energy-efficient, in-situ data analytics on extreme-scale machines. In Proceedings of the 11st USENIX Conference on File and Storage Technologies. 2013.