PRUNE: Efficient Backup system for Massive Scale Data Storage = PRUNE: 대용량 저장장치를 위한 효율적인 백업 시스템

다국어 초록 (Multilingual Abstract)

As the importance of digital data has been increasing day after day, Backing up regularly is essential so as to prevent an unexpected damage. But many parts of data involve lots of the same contents because of increasing backup data. Therefore, many parts of storage are being wasted. Suggested PRUNE, De-duplication Backup System, enables the waste of storage capacity and time to be minimized by backing up new data through redundancy check. PRUNE removes Redundancy data through three steps: divides file using Basic Sliding Windows, calculates SHA-1 Hash Value of each field and redundancy check using Hash Table of B+ Tree structure. On this paper, I prove plenty of efficiency by demonstrating a real implementation of server which stores and manages backed- up data with client performing redundancy check and verifying all functions

국문 초록 (Abstract)

디지털 데이터의 중요성이 날로 증가하면서 예기치 않은 훼손을 방지하기 위하여 주기적으로 백업을 하는 것은 필수적인 사항이 되었다. 하지만 백업 데이터가 증가함에 따라 자료의 많은 부분은 동일한 내용을 중복 포함하게 되었고 그로 인하여 저장장치의 많은 부분이 낭비되고 있다. 제안하는 Deduplication 백업 시스템인 PRUNE 는 중복 검사를 통하여 새로운 데이터 만을 백업 함으로서 소모되는 시간과 저장장치의 용량 낭비를 최소화 시킨다.
PRUNE 는 Basic Sliding Windows 방식을 이용한 파일 분할, 각 영역의 SHA1 해시값 계산, B+ Tree 구조의 해시 테이블을 이용한 중복검사의 세 단계를 통하여 중복되는 데이터를 제거하게 된다. 본 논문에서는 중복 검사를 수행하는 클라이언트와 백업된 데이터를 저장 및 관리하는 서버의 실제 구현방식을 설명하고 모든 성능을 검증함으로써 충분한 효율성을 보임을 입증하고 있다.

목차 (Table of Contents)

• 1. Introduction = 1
• 1.1 Motivation = 1
• 1.2 Related works = 3
• 2. Backup system = 5
• 2.1 Storage Management Technique = 5
• 2.2 Backup Technique = 6
• 2.3 The form of Backup = 7
• 2.4 Backup software = 8
• 2.5 De-duplication backup system = 9
• 3. Prune: System Structure = 11
• 3.1 Prune Structure = 11
• 3.2 Backup File Structure = 12
• 3.3 Structure of Chunk Hash Table = 14
• 3.3.1 Chunk Hash Table of Client = 15
• 3.3.2 Chunk Hash Table of Server = 15
• 3.3.3 Split / Merge of Chunk Hash Table = 16
• 4. Checking Redundancy = 18
• 4.1 Fixed Sized Chunking vs Variable Sized Chunking = 18
• 4.2 Content-based chunking = 20
• 4.3 Choice of Hash Algorithm = 23
• 4.4 Redundancy check using Chunk Hash Value = 24
• 5. Implementation = 25
• 5.1 Client Implementation = 26
• 5.2 Server Implementation = 27
• 6. Performance Evaluation = 29
• 6.1 Selection of Magic number = 30
• 6.2 Performance of MOD-K Algorithm = 35
• 6.3 The capability of Redundancy Check. = 36
• 7. Conclusion = 39
• Reference = 40
• 국문요약 = 43