Content-defined chunking (CDC) based data deduplication is a complex process, leading to the use of rule-of-thumb approaches and standardized parameter values. However, our work challenges these standard approaches which can lead to worse deduplication ratios, and reemphasizes that parameters need to be optimized for each dataset. We expose new pitfalls, analyze the behaviour of the underlying deduplication process, and provide solutions to aid future deduplication work.Deduplication research often solely reports the expected chunk length of their system without providing the low-level parameters. Our results show that expected chunk length is inadequate for properly describing deduplication, making empirical reproducibility challenging. In fact, different parameter sets with the same expected chunk length can yield different deduplication ratios. We further show that this discrepancy can be explained by chunk length variance.We find that because expected average and standard deviation of chunk length do not account for file boundaries and fingerprint value noise, they can significantly differ from observed values. We show that these phenomena can also cause the same parameter set to give different chunk length distributions on different datasets, explaining why parameters must be tuned to each dataset. However, we find on our datasets that the maximum chunk length parameter does not need to be tuned, and that a rule-of-thumb value of 216is a reasonable selection. We provide our datasets in full to promote reproducibility and further work.

Deduplication is a technique to find and eliminate redundant blocks of data for efficient data backups, efficient versioning, reduced data transfers, and reduced data-storage overheads. For large datasets, especially with incremental updates over time (e.g., instrumentation data) and subsetting (e.g., for auxiliary experiments), deduplication makes data management faster and more efficient. The primary parameter of deduplication systems is the expected chunk size, and while many existing systems use accepted default values (e.g., 4 KB or 8 KB chunks), our experiments find that these values are suboptimal for finding duplicate data. Suboptimal deduplication and data management makes it harder for researchers to manipulate, share, and experiment with large datasets.We present the design, implementation, and an empirical validation of our analytical model that predicts the performance of deduplication parameters (i.e., ability to find duplicate data) on any given dataset. The empirical evaluation includes workloads based on source code (i.e., Linux kernel, Kubernetes, TensorFlow), an open-research dataset (i.e., CORD-19), and Wikipedia. Our experiments show that our model finds deduplication parameters that reduce the storage requirements by up to an additional 30.72% compared to a commonly used baseline. Our model is up to 19.8x faster than scanning, and the resulting deduplicated datasets are all within 5.14% of the deduped sizes found via the scan-based search.

Summarizing, comparing, and indexing large data files are common operations in information retrieval and data-storage systems. Consequently, Rabin fingerprinting is a common technique for string matching, and to cut a file into variable-length chunks for faster pattern matching of large datasets. Ordered lists of hashes (of the chunks), representing the original files, can require fewer bytes to store and to transmit across a network than the files themselves. Lists of hashes can also be compared like substrings to find files with common chunks of data. Finally, lists of hashes can also be used for data deduplication to save on storage (and transmission) or to synchronize two similar copies of the same file. However, it is important to make appropriate choices for Rabin fingerprinting parameters such as the sliding window size, the degree of the irreducible polynomial, the mask size, and the cut value for the hash. Therefore, we present an empirical, parameter-sweep study of Rabin fingerprinting on a non-trivial workload based on the Linux kernel source code. As a result, we make some best-practice recommendations for using Rabin fingerprinting. For example, we characterize how a cut value of one is less problematic than a natural choice of zero for the cut value.