Efficient Deduplication Techniques for Modern Backup Operation
- Title
- Efficient Deduplication Techniques for Modern Backup Operation
- Author
- 원유집
- Keywords
- Deduplication; chunking; backup; index partitioning; fingerprint lookup; SYSTEM
- Issue Date
- 2011-06
- Publisher
- IEEE INSTITUTE OF ELECTRICAL AND ELECTRONICS
- Citation
- IEEE Transactions on Computers, 2011, 60(6), P.824~840
- Abstract
- In this work, we focus on optimizing the deduplication system by adjusting the pertinent factors in fingerprint lookup and chunking, the factors which we identify as the key ingredients of efficient deduplication. For efficient fingerprint lookup, we propose fingerprint management scheme called LRU-based Index Partitioning. For efficient chunking, we propose Incremental Modulo-K(INC-K) algorithm which is optimized Rabin's algorithm where we significantly reduce the number of arithmetic operations exploiting the algebraic nature of modulo arithmetic. LRU-based Index Partitioning uses the notion of tablet and enforces access locality of the fingerprint lookup in storing fingerprints. We maintain tablets with LRU manner to exploit temporal locality of the fingerprint lookup. To preserve access correlation across the tablets, we apply prefetching in maintaining tablet list. We propose Context-aware chunking to maximize chunking speed and deduplication ratio. We develop prototype backup system and performed comprehensive analysis on various factors and their relationship: average chunk size, chunking speed, deduplication ratio, tablet management algorithms, and overall backup speed. By increasing the average chunk size from 4 KB to 10 KB, chunking time increases by 34.3 percent, deduplication ratio decreases by 0.66 percent and the overall backup speed increases by 50 percent (from 51.4 MB/sec to 77.8 MB/sec).
- URI
- https://ieeexplore.ieee.org/abstract/document/5669285/https://repository.hanyang.ac.kr/handle/20.500.11754/70444
- ISSN
- 0018-9340
- DOI
- 10.1109/TC.2010.263
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML