SuperDelta: Improving the Compression Ratio in the Fine-grained Deduplication Storage Systems

As a complement to data deduplication, delta compression further reduces the data volume by compressing non-duplicate data chunks relative to their similar base chunks in backup storage. However, we find that existing delta compression approaches suffer from several limitations that prevent them from achieving higher compression ratios. Specifically, (1) First-fit problem. They directly select the first-fit similar candidate chunk among several, which may miss a better candidate. (2) Old-compress-new problem. The similar base chunk is usually selected from older-version backups, since once a chunk in the new version has been delta-compressed, it can no longer be used as a base chunk. However, new chunks may be more suitable for compressing subsequent backups due to the locality of shorter “modification distance”. (3) One-to-one problem. The compression scope of delta encoding is restricted to only one base chunk and one delta chunk, which wastes opportunities to compress against other similar chunks. To address these problems, we propose SuperDelta, which exploits higher compression ratios in delta compression storage. It incorporates several techniques: (1) A chunking-boundary-assisted similarity detection method, which leverages the observation that highly similar chunks tend to share the same chunk boundaries with high probability, thereby enabling the system to select better similar candidate chunks. (2) A new-compress-old approach, which compresses old unique chunks using the newly incoming chunks. This allows the next backup version to perform delta compression against newer chunks that are closer in “modification distance”, resulting in more effective removal of similar redundancies. (3) A multi-referenced base chunk scheme that explores the redundancy among multi-pair similar chunks. Experiments on several real-world backup datasets show that SuperDelta improves the delta compression efficiency by 1.3 × –2.1 ×, and overall compression ratio of delta compression by 1.2 × –2.4 ×, compared with the existing approaches, without significantly degrading delta compression performance.