Similar Data Detection and Delta Compression for Data Reduction

Abstract

Modern society is experiencing an explosive growth of data, which places more and more heavy burden on data storage systems. Besides the effort in inventing new storage hardware with higher storage efficiency, data reduction techniques are also critical when facing this challenge for their ability to reduce the size of data directly. Traditional data reduction techniques include general lossless compression (like ZIP and RAR) and deduplication, which compresses backup data by identifying and removing duplicate blocks. However, deduplication can not detect when two blocks are very similar, which opens up opportunities for further data reduction using delta compression. Delta compression has attracted researchers’ interest in recent decades for its ability to eliminate redundant data in similar but not identical blocks. However, there is still a gap in the compression ratio between the state-of-the-art delta compression solution and the ideal case.

In this dissertation, we identify two crucial questions of delta compression: how can we find more similar blocks and how can we exploit those similar blocks better? We propose two novel solutions that can effectively find more similar blocks and achieve a higher compression ratio.

First, we investigate existing similarity detection algorithms and their mathematical foundation. Most existing works find similar blocks by characterizing each block by a set of features and matching similar blocks using coarse-grained super-features. If two blocks share a super-feature, delta compression only needs to store their delta for the new block. They constrain their super-features to find only matching blocks that are likely to be very similar. Therefore, we propose Palantir, a new delta compression solution that introduces hierarchical super-features with different sensitivities to block similarities to find more candidates of similar blocks and increase overall backup compression, including deduplication by 7.3% over N-Transform and Odess and 26.5% over Finesse. The overhead of Palantir for storing additional super-features is overcome by exploiting temporal localities of backup streams, and the throughput penalty is within 7.7%.

Second, we observe that Palantir introduces too much computational overhead, which limits its application in situations with insufficient computation resources. We propose Sylph, which explores more optimizations that can help improve delta compression without introducing much computational overhead. Sylph leverages a lower similarity detection threshold and builds a new systematic approach to identify those wrongly recognized similar blocks and prevent their harm to the compression ratio. Moreover, using lower detection thresholds with a base block extension can effectively utilize potential duplicate data adjacent to the base block and achieve a higher compression ratio. Sylph also optimizes the post-delta lossless encoding procedure by separating unique blocks and delta blocks. Evaluation with six datasets shows that our approach, on average, improves the overall compression ratio (including deduplication and lossless compression) by 13.2% and finds 26.1% more similar blocks over the state-of-the-art approach Odess, with a throughput degradation of 3.7%. Sylph controls the I/O overhead by building a two-layer cache and an extension size estimation algorithm to reduce the cache space consumption by 40% with a compression ratio loss of 1.5%.

Date of Award	22 Oct 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Nan GUAN (Supervisor), Chun Jason XUE (Supervisor), Jason XUE (External Co-Supervisor) & Hong XU (External Co-Supervisor)