검색 상세

A High Performance and Secure Flash Storage System for Next Generation DBMSs

초록/요약

More and more computing devices such as smartphones, tablet PCs, datacenters are equipped with flash memory because of its many advantage, such as shock resistance, fast access, and low power consumption. However, its distinguishing characteristics, including erase-before-update, asymmetric read/write/erase cost and limited number of erase cycles, make it necessary to reconsider existing database design in order to explore the hardware potential. For example, the buffer replacement scheme for flash-based databases should not only consider the cache hit ratio, but also the relatively heavy write and erase costs that are caused by flushing dirty pages. The frequent changes of B+-trees of database systems can degrade the performance and negatively influence the lifespan of flash memory. Furthermore, Reliable erasing of data from storage devices is a critical component of secure data management and is well understood for magnetic disks. However, flash memory has unusual electronic limitations that make in-place updating impossible. Most of the recent studies on buffer design focus on a clean-first LRU (Least Recently Used) strategy that evicts clean pages prior to dirty pages, in order to minimize the write access to flash. However, all of them failed to distinguish the cached pages that may have different effects on the flash device under various storage mangers. Meanwhile, most state-of-the-art studies on flash-aware index design focused mainly on buffer and storage mechanisms whereby they can obtain efficient I/Os to flash memory. In this dissertation, I first propose a three-state log-aware buffer management scheme, called TSLA, which considers not only the imbalance of read/write costs of flash memory but also the log block thrashing, associativity, and space utilization problems of log-based FTLs (flash translation layers). I then introduce the concepts of lazy-split, modify-two-node, which make possible the construction of a novel index solution, the Lazy-Split B+-tree (LSB+-tree). In detail, by their introduction, the first concept of LSB+-tree can efficiently reduce the number of node splits, the second can reduce the number of node modifications. A group round robin based B+-tree index storage scheme (GRR) is also discussed which applies a dynamic grouping and round robin techniques for erase-minimized storage of B+-tree in flash memory under heavy-update workload. Lastly, this dissertation investigates secure deletion and modification module, ESK, to improve both information security and erasing reliability of flash based systems. Experimental results show that the proposed TSLA buffer solution is effective for reducing the garbage collection overhead under various FTLs, such as BAST, FAST and IPL. GRR is efficient for frequently changed B+-tree structure and improves the I/O performance by 2.14X at best, compared to the related work. ESK module can improve the level of information safety as well as reduce the number of page copies and block erases due to reliable erasing.

more

목차

ACKNOWLEDGEMENTS 2
ABSTRACT 5
TABLE OF CONTENTS 7
LIST OF FIGURES 11
LIST OF TABLES 14
CHAPTER 1. INTRODUCTION 15
1.1 CONTRIBUTIONS OF THIS DISSERTATION 16
1.1.1 Buffer Replacement Policy 16
1.1.2 Lazy-Split B+-tree 18
1.1.3 Group round robin based B+-tree storage scheme 20
1.1.4 An Encryption Approach to Secure Modification and Deletion 21
CHAPTER 2. BACKGROUND 24
2.1 FLASH MEMORY 24
2.2 RELATED WORK 25
2.2.1 Log Buffer-based FTL 25
2.2.2 Flash-Aware Buffer Scheme 28
2.2.3 The log-based B+-tree implementations 30
2.2.4 The disk-based B+-tree implementations 32
2.2.5 The hybrid approach 33
2.2.6 In-Page Logging Storage Manager 34
2.3 CHALLENGES OF THE DATABASE SYSTEMS OVER FLASH MEMORY 35
CHAPTER 3. A HIGH PERFORMANCE AND SECURE FLASH STORAGE SYSTEM FOR NEXT GENERATION DBMSS 37
3.1 THREE-STATE LOG-AWARE BUFFER MANAGEMENT 37
3.1.1 Overview 37
3.1.2 Three-State Scheme 38
3.1.3 Flash Log-Aware Architecture 42
3.2 A NOVEL B+-TREE INDEX SCHEME 44
3.2.1 The Lazy-Split Index Manager 48
3.2.2 The Three-State based Buffer Manager 52
3.3 A GROUP ROUND ROBIN BASED STORAGE SCHEME 67
3.3.1 System Architecture 67
3.3.2 Dynamic Block Grouping 68
3.3.3 Round Robin Logging 69
3.3.4 Operations 70
3.4 ENCRYPTION APPROACH TO SECURE MODIFICATION AND DELETION 71
3.4.1 Overview 71
3.4.2 System Architecture 73
3.4.3 Sanitization Level 75
3.4.4 Key Management Scheme 76
3.4.5 Encryption-based File-level Secure Sanitization 78
3.4.6 A Secure Modification and Deletion Algorithm 80
CHAPTER 4. PERFORMANCE EVALUATION 82
4.1 TEST ENVIRONMENT 82
4.2 EVALUATION OF TSLA 82
4.2.1 Comparing Execution Times 83
4.2.2 Garbage Collection Efficiency 87
4.2.3 Buffer Hit Ratio 90
4.2.4 Varying Read/Write Ratio 90
4.3 EVALUATION OF LSB+-TREE 91
4.3.1 Preliminary Analysis 91
4.3.2 Implementation of B+-tree 93
4.3.3 Effect of LS-LRU 95
4.3.4 Simulation Results of Indices Managers 98
4.4 EVALUATION OF GRR 101
4.4.1 Cost Model 101
4.4.2 Experiment Settings 102
4.4.3 Varying m and k 103
4.4.4 Buffer Hit Ratio 103
4.4.5 Varying Read/Write Ratio 103
4.5 EVALUATION OF ESK 105
4.5.1 Experimental Settings 105
4.5.2 Varying File Deletion/Modification Coefficient 106
4.5.3 Garbage Collection Efficiency 107
CHAPTER 5. CONCLUSIONS 110
REFERENCES 113
APPENDIX 120
A. LIST OF PUBLICATIONS 120
A.1 SCI/SCIE Journal Papers 120
A.2 International Conference Papers 121
B. LIST OF PATENTS 123

more
반출 Meta View 목록