Free Space Management of Dedup-based PCM Storage Devices

近年來,智能儲存裝置的需求正不斷成長,特別是隨著硬件計算能力的迅速提 高。 這篇論文探討了在使用重複數據刪除技術於新興的非揮發性相變化記憶體時 其空間利用的設計問題。在基於相變化記憶體的儲存設備上,我們透過刪除與索 引潛在的重複數據,以提供比物理儲存更多的儲存空間。另外,我們提出一個空 間管理的設計以在系統性能和空間利用率之間取得良好平衡。設計原理是基於儲 存系統最初有較多的自由空間,但對內部數據的資訊較少。這意味著隨著使用時 間增長,對空間的管理應更加謹慎。最後,我們使用常用標竿以評估我們所提出 的設計並且得到相當好的成果。There is a growing demand to introduce more and more intelligence to storage devices in recent years, especially with the rapid increasing of hardware computing power. This paper explores essential design issues in space utilization together with the deduplica- tion technology over emerging non-volatile memory PCM. In particular, we exploit data deduplication and indexing of potential data duplicates over PCM-based storage devices to provide more storage space than the physical storage space does. A space manager is proposed to have a good balance between the system performance and the space utiliza- tion. The rationale behind the design is based on the fact that a storage system initially has more free space but less knowledge in data deduplication. It implies the value of space optimization should only grow with the time in device usages. The proposed design is evaluated over popular benchmarks, for which we have very encouraging results.Acknowledgment ii Abstract in Chinese iii Abstract iv Contents iv List of Figures vii List of Tables viii 1 Introduction 1 2 System Architecture and Motivation 5 3 Container-based Space Management for Dedup-based PCM Storage Device 9 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Address Mapping – A Two-Level Address Mapping . . . . . . . . . . . . 11 3.3 Space Allocator – A Container-based Allocation Strategy . . . . . . . . . 14 3.3.1 Containers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.2 Two-class Bucket List with a Worst-Fit Allocation Policy . . . . . 18 3.3.3 Container Merging with a Container-based Buddy System . . . . 24 4 Performance Evaluation 29 4.1 Performance Metrics and Experiment Setup . . . . . . . . . . . . . . . . 29 4.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.1 Space Utilization and Overhead . . . . . . . . . . . . . . . . . . 31 4.2.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.3 Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Conclusion 37 Bibliography 3