Efficient Similarity Detection for Delta Compression

Abstract

Delta compression is a promising technique for reducing the storage footprint of similar data. As the first step in delta compression, similarity detection has a significant impact on both the delta compression ratio (DCR) and the compression throughput. Unfortunately, existing approaches often make a trade-off between these two metrics, struggling to optimize both simultaneously. This paper presents Sonic, a novel similarity detection methodology that achieves high DCR and high throughput simultaneously. We first conduct an experimental study to analyze the limitations of existing approaches. Based on our findings, we exploit fine-grained features rather than super-features to enable precise identification of low-similarity chunks. Sonic further exploits approximate matching rather than exhaustive searches to find the most similar chunk, significantly reducing the search space and improving throughput. In addition, we eliminate intra-chunk redundancies to improve the DCR. Our extensive experiments demonstrate Sonic’s superiority over state-of-the-art approaches. Compared with high-DCR approaches, Sonic achieves comparable DCR while improving throughput by 5.5× on average. Compared with high-throughput approaches, Sonic achieves comparable throughput while improving the DCR by at least 2×.