Một Khung Dữ Liệu Khử Trùng Ảnh Đĩa Với Kỹ Thuật Bỏ Khối Tùy Biến

Springer Science and Business Media LLC - Tập 31 - Trang 820-835 - 2016
Bing Zhou1,2,3, Jiang-Tao Wen1,2,3
1State Key Laboratory on Intelligent Technology and Systems, Tsinghua University, Beijing, China
2Tsinghua National Laboratory for Information Science and Technology, Tsinghua University, Beijing, China
3Department of Computer Science and Technology, Tsinghua University, Beijing, China

Tóm tắt

Chúng tôi mô tả một khung khử trùng dữ liệu hiệu quả và dễ áp dụng với kỹ thuật bỏ khối dựa trên dự đoán Heuristic nhằm tiết kiệm chi phí khử trùng liên quan và cải thiện thông lượng khử trùng mà vẫn duy trì hiệu quả khử trùng tốt. Trong khung này, các thao tác khử trùng sẽ bị bỏ qua cho các khối dữ liệu được xác định là có khả năng không trùng lặp thông qua dự đoán Heuristic, kết hợp với một quy trình mở rộng phát hiện và khớp cho việc xác định trùng lặp trong các khối bị bỏ qua và một quy trình lập chỉ mục băm dựa trên cơ chế hồi tiếp để cập nhật các chỉ số băm cho các khối bị bỏ qua đã được tái gặp. Để đánh giá hiệu suất, khung đề xuất đã được tích hợp và triển khai trong các thuật toán khử trùng theo miền dữ liệu và chỉ mục thưa hiện có. Kết quả thí nghiệm dựa trên một tập dữ liệu thực tế 1.0 TB ảnh đĩa cho thấy chi phí liên quan đến khử trùng đã được giảm đáng kể với kỹ thuật bỏ khối tùy biến, dẫn đến sự cải thiện 30%~80% trong thông lượng khử trùng khi metadata khử trùng được lưu trên đĩa cho miền dữ liệu, và tiết kiệm 25%~40% không gian RAM với sự cải thiện 15%~20% trong thông lượng khử trùng khi một chỉ mục thưa trong RAM được sử dụng trong khử trùng thưa. Trong cả hai trường hợp, tỷ lệ khử trùng tương ứng giảm xuống dưới 5%.

Từ khóa

#khử trùng dữ liệu #kỹ thuật bỏ khối #dự đoán Heuristic #ảnh đĩa #thuật toán khử trùng

Tài liệu tham khảo

Zhu B, Li K, Patterson H. Avoiding the disk bottleneck in the data domain deduplication file system. In Proc. the 6th USENIX Conference on File and Storage Technologies (FAST), February 2008, pp.269-282. Lillibridge M, Eshghi K, Bhagwat D, Deolalikar V, Trezise G, Camble P. Sparse Indexing: Large scale, inline deduplication using sampling and locality. In Proc. the 7th FAST, February 2009, pp.111-123. Srinivasan K, Bisson T, Goodson G, Voruganti K. iDedup: Latency-aware, inline data deduplication for primary storage. In Proc. the 10th FAST, February 2012, pp.299-312. Wildani A, Miller E, Rodeh O. HANDS: A heuristically arranged non-backup inline deduplication system. In Proc. the 29th IEEE International Conference on Data Engineering (ICDE), April 2013, pp.446-457. Rabin M O. Fingerprinting by random polynomials. Technical Report, TR-15-81, Center for Research in Computing Technology, Harvard University, 1981. Black J. Compare-by-hash: A reasoned analysis. In Proc. the USENIX Annual Technical Conference (ATC), May 2006, pp.85-90. Meister D, Kaiser J, Brinkmann A, Cortes T, Kuhn M, Kunkel J. A study on data deduplication in HPC storage systems. In Proc. the International Conference for High Performance Computing, Networking, Storage and Analysis, November 2012. Bloom B H. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 1970, 13(7): 422-426. Jin K, Miller E L. The effectiveness of deduplication on virtual machine disk images. In Proc. the 2nd Annual International Systems and Storage Conference (SYSTOR), May 2009, pp.7:1-7:12. Muthitacharoen A, Chen B, Mazières D. A low-bandwidth network file system. In Proc. the 18th ACM Symposium on Operating Systems Principles (SOSP), October 2001, pp.174-187. Romar´ıski B, Heldt L, Kilian W et al. Anchor-driven subchunk deduplication. In Proc. the 4th Annual International Conference on Systems and Storage (SYSTOR), May 2011, pp.16:1-16:13. Bhagwat D, Eshghi K, Long D D E, Lillibridge M. Extreme Binning: Scalable, parallel deduplication for chunkbased file backup. In Proc. the IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS), September 2009. Tanenbaum A S. Modern Operating Systems (2nd edition). Prentice Hall PTR, 2001. Zhou B, Wen J. Hysteresis re-chunking based metadata harnessing deduplication of disk images. In Proc. the 42nd IEEE International Conference on Parallel Processing (ICPP), October 2013, pp.389-398. Fan L, Cao P, Almeida J, Broder A. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, June 2000, 8(3): 281-293. Guo F, Efstathopoulos P. Building a high-performance deduplication system. In Proc. the USENIX Annual Technical Conference (ATC), June 2011, Article No. 25. Botelho F C, Shilane P, Garg N, Hsu W. Memory efficient sanitization of a deduplicated storage system. In Proc. the 11th FAST, February 2013, pp.81-94. Debnath B, Sengupta S, Li J. ChunkStash: Speeding up inline storage deduplication using flash memory. In Proc. the USENIX Annual Technical Conference (ATC), June 2010, Article No. 16. Meister D, Brinkmann A. dedupv1: Improving deduplication throughput using solid state drives (SSD). In Proc. the 26th IEEE Symposium on Mass Storage Systems and Technologies (MSST), May 2010. Dal Bianco G, Galante R, Heuser C A. A fast approach for parallel deduplication on multicore processors. In Proc. the ACM Symposium on Applied Computing (SAC), March 2011, pp.1027-1032. Bobbarjung D R, Jagannathan S, Dubnicki C. Improving duplicate elimination in storage systems. ACM Transactions on Storage, November 2006, 2(4): 424-448. Kruus E, Ungureanu C, Dubnicki C. Bimodal content defined chunking for backup streams. In Proc. the 8th FAST, February 2010, Article No. 18. Lu G, Jin Y, Du D. Frequency based chunking for data deduplication. In Proc. IEEE International Symposium on Modeling, Analysis Simulation of Computer and Telecommunication Systems (MASCOTS), August 2010, pp.287-296. Meister D, Brinkmann A, Süβ T. File recipe compression in data deduplication systems. In Proc. the 11th FAST, February 2013, pp.175-182. Balachandran S, Constantinescu C. Sequence of hashes compression in data deduplication. In Proc. the Data Compression Conference (DCC), March 2008, p.505. Harnik D, Margalit O, Naor D, Sotnikov D, Vernik G. Estimation of deduplication ratios in large datasets. In Proc. the 28th IEEE Symposium on Mass Storage Systems and Technologies (MSST), April 2012. Xie F, Condict M, Shete S. Estimating duplication by content-based sampling. In Proc. the USENIX Conference on Annual Technical Conference (ATC), June 2013, pp.181-186. Constantinescu C, Lu M. Quick estimation of data compression and deduplication for large storage systems. In Proc. the 1st International Conference on Data Compression, Communications and Processing (CCP), June 2011, pp.98-102. Fu M, Feng D, Hua Y, He X, Chen Z, XiaW, Zhang Y, Tan Y. Design tradeoffs for data deduplication performance in backup workloads. In Proc. the 13th FAST, February 2015, pp.331-344. Fu M, Feng D, Hua Y, He X, Chen Z, Xia W, Huang F, Liu Q. Accelerating restore and garbage collection in deduplicationbased backup systems via exploiting historical information. In Proc. the USENIX Annual Technical Conference (ATC), June 2014, pp.181-192. Tang Y, Yang J. Secure deduplication of general computations. In Proc. the USENIX Annual Technical Conference (ATC), July 2015, pp.319-331. Zhang W, Yang T, Narayanasamy G, Tang H. Low-cost data deduplication for virtual machine backup in cloud storage. In Proc. the 5th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), June 2013, Article No. 12. Lin X, Lu G, Douglis F, Shilane P, Wallace G. Migratory compression: Coarse-grained data reordering to improve compressibility. In Proc. the 12th FAST, February 2014, pp.257-271.