Once Rolling Hashing is Enough: Exploiting Rolling Hash Reuse in Delta Compression

In backup storage, delta compression successfully achieves a much higher data reduction ratio than chunk-level deduplication by applying a finer granularity in redundancy detection and elimination. However, it introduces additional, intensive computation overhead and results in a 50%–70% worsening backup throughput. We find that the computational inefficiency is due to the redundant byte-wise rolling hash computation across multiple stages of the delta compression, although they are merge-able. We therefore present FastDelta, a computationally efficient framework for delta compression that proposes a novel sampling-based rolling hash reuse approach. By caching and reusing sampled rolling hashes to avoid redundant computation, FastDelta achieves high-performance delta compression with a low memory overhead. Moreover, we propose a series of techniques, such as embedding-style sampling operation and locality-aware container compression, which mitigate the performance overhead and data reduction loss caused by sampling-based hash reuse. Evaluations show that FastDelta achieves 1.3×–2.1× higher end-to-end throughput while preserving a comparable data reduction ratio.