PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking Content-Defined Chunking Algorithms for Data Deduplication

Marcel Gregoriadis, Leonhard Balduf, Björn Scheuermann, Johan Pouwelse

arXiv:2610.13704v1cs.DBcs.DC

TL;DR

Existing CDC benchmarks often combine base chunking rules with higher-level techniques, making algorithm comparisons difficult. The paper isolates and benchmarks eight base algorithms, calibrating settings on random data before evaluating realistic workloads. AE is the most robust tested algorithm overall, while RAM is sensitive to structured input and AE’s established parameterization produced chunks smaller than intended.

  • Problem

    Existing evaluations often conflate base algorithms with higher-level techniques and use inconsistent datasets, metrics, or parameter choices, limiting fair comparisons.

    Source: §I · pp. 1–2

  • Method

    The paper modularly benchmarks eight base algorithms, calibrating parameters on uniformly random data before evaluating them unchanged on realistic workloads.

    Source: §I · p. 2, §X · p. 12

  • Results

    Within the evaluated workloads and target range, AE is the most robust tested algorithm; RAM is sensitive to structured data, and the established AE formula produced chunks 13–39% below target.

    Source: A. Summary of Results · p. 11, B. Contrasting Results with Literature · p. 11, §X · p. 12

  • Takeaways & Limitations

    For target sizes beyond those tested, Gear may be a more robust alternative to AE.

    Source: A. Summary of Results · p. 11

    The paper’s conclusions about AE’s robustness are scoped to the evaluated workloads and target range.

    Source: §X · p. 12

Abstract

from arXiv · show

Data deduplication relies on content-defined chunking (CDC) algorithms to decide where data is split. We observe that most CDC algorithms are modular: a base chunking algorithm fixes the byte-level cut-point condition, while high-level techniques (size normalization, min/max thresholds, caching) layer on top. Existing benchmarks conflate the two, obscuring which design choices actually drive performance. We isolate and evaluate eight state-of-the-art base chunking algorithms across four realistic workloads and four metrics: throughput, deduplication ratio, mean chunk size, and chunk-size variance. Further, we derive new formulas relating algorithm parameters to expected chunk size for AE, RAM, and MII. In doing so, we uncover a longstanding error in the widely-used AE parameterization reproduced across multiple papers and evaluation tools that produces chunks 13-39% smaller than intended and inflates AE's reported deduplication. Across our evaluation, AE is the most balanced base chunking algorithm across all four metrics, RAM's similarity to AE does not carry over to low-entropy data, and MII and PCI show limited advantages over simpler alternatives in storage-oriented workloads. We release all implementations, datasets, and analysis scripts as open source.

I. INTRODUCTION

Chunking algorithms combine base cut-point rules with higher-level techniques, but existing benchmarks often conflate their effects and use inconsistent evaluation methods. This paper separates those layers and benchmarks representative base algorithms under common parameter settings and workloads.

I. INTRODUCTION

  • Existing benchmarks often conflate base cut-point rules with higher-level optimizations, leaving the relative merits of underlying algorithms unclear.Inconsistent datasets, metrics, and parameter selection further hinder fair comparisons.Source: §I · pp. 1–2
  • The paper releases a framework that separates base chunking algorithms from higher-level techniques for modular CDC evaluation..Source: §I · p. 2
  • The benchmark evaluates eight base algorithms across four realistic workloads using throughput, mean chunk size, chunk-size variance, and deduplication ratio.Parameters are selected for common configured targets on uniformly random data before evaluation on realistic workloads.Source: §I · p. 2
  • The paper derives parameter rules, including formulas for AE, RAM, and MII, and evaluates their calibration on uniformly random data.Configured targets are distinguished from empirical means.Source: §I · p. 2

II. BACKGROUND AND MOTIVATION

  • CDC places boundaries according to content, reducing the boundary-shift problem that makes unchanged regions appear unique after insertions or deletions.Chunking is the first stage of deduplication, which fingerprints chunks and stores unique chunks with reconstruction metadata.Source: §II · p. 2

A. Hash-Based CDC

  • Basic Sliding Window (BSW) compares each sliding-window hash against a bitmask to determine chunk boundaries.Rabin, Buzhash, and Gear are examples of rolling-hash functions used for this approach.Source: A. Hash-Based CDC · p. 2

B. Chunk-Size Variance

High chunk-size variance can produce pathological chunks with storage costs, while chunking algorithms combine byte-level rules with higher-level techniques. This benchmark isolates base algorithms by fixing settings before realistic-workload evaluation.

B. Chunk-Size Variance

  • High variance produces pathological very large or small chunks, increasing storage, processing, metadata, and sometimes round-trip overhead.The concern is especially relevant to long-term storage, where these costs can accumulate across dataset revisions.Source: B. Chunk-Size Variance · p. 3

C. Hashless CDC

  • Hashless CDC uses byte comparisons or rolling popcount instead of hashes; local-extrema methods are attributed lower variance and higher throughput than hash-based methods.AE and RAM are modern local-extrema methods; PCI compares a sliding window’s popcount with a threshold.Source: C. Hashless CDC · p. 3

D. High-Level Techniques

  • The compatibility matrix summarizes how high-level techniques pair with base algorithms beyond the combinations used in their original papers.Composite algorithms such as FastCDC combine multiple high-level techniques.Source: D. High-Level Techniques · p. 3, Table I · p. 4
  • Minimum/maximum size limits can increase throughput and reduce chunk-size variance, but trade off deduplication efficiency by making boundaries partly position-based.Caching, normalization, and parallelization are other approaches to throughput or variance improvements.Source: D. High-Level Techniques · p. 3
  • Multiple threshold bitmasks can adjust boundary probability to produce more uniform chunks, while merging small chunks and rechunking large ones address pathological sizes.Rechunking large chunks can also increase detected redundant chunks; MII and PCI variance constraints are relaxed for incremental file synchronization.Source: D. High-Level Techniques · p. 3, B. Chunk-Size Variance · p. 3

III. METHODOLOGY

  • The benchmark tunes algorithms to common target sizes on uniformly random data, freezes settings, then evaluates them unchanged on realistic datasets.Its conclusions concern base algorithms, not complete systems or composites, and throughput rankings may vary with hardware and compiler.Source: §III · pp. 3–4

A. Datasets

The study uses datasets representing storage and data-management workloads, measures algorithms in a controlled benchmark framework, and calibrates parameter settings on random data before testing realistic inputs. It also revises AE’s horizon formula and uses simulation for smaller targets.

A. Datasets

  • The five datasets comprise a high-entropy RAND baseline and realistic WEB, DB, VMB, and CODE workloads representing distinct forms of storage and data-management redundancy.WEB and CODE are uncompressed TAR streams; DB and VMB are snapshot-style images, evaluated as streams rather than isolated files.Source: A. Datasets · p. 4

B. Benchmarking Framework

  • The Rust framework measures chunking without fingerprinting and avoids disk I/O; throughput runs use RAND on a RAMdisk, with ten measured runs per dataset-algorithm-target combination.The benchmark reports median and IQR for runtime and throughput; the virtual-machine setup lacks explicit CPU affinity and NUMA controls.Source: B. Benchmarking Framework · pp. 4–5

IV. PARAMETER SETTINGS AND DERIVATIONS

  • Parameters are calibrated on uniformly random data and then evaluated unchanged on realistic datasets, separating parameter tuning from dataset-specific behavior.This avoids retuning algorithms on the same data used for comparison.Source: §IV · p. 5

A. Basic Sliding Window (BSW)

  • For hash-based algorithms, a bitmask of length b gives a boundary probability of 2^-b under the stated random-data assumptions; the benchmark uses w=32 for Rabin and Buzhash.For five power-of-two targets, both Rabin/Buzhash and Gear parameter rules yield b values from 9 to 13.Source: A. Basic Sliding Window (BSW) · p. 5

B. Asymmetric Extremum (AE)

  • The commonly used AE rule h=µ/(e−1) underestimates target chunk sizes because it omits byte-value discreteness and dependent-event conditioning; the paper proposes h≈µ−256 for targets at least 2 KiB.Smaller targets use simulation; at 2 KiB, h=1792 gives a maximum-byte probability of approximately 0.999, not a bound on mean-size error.Source: B. Asymmetric Extremum (AE) · p. 5, Table IV · p. 5

C. Rapid Asymmetric Extremum (RAM)

For RAM, the paper models expected chunk size from the horizon maximum and conditional waiting time, then uses the model to calibrate horizons. For MII, it estimates boundary probability from strictly increasing windows, but the resulting chunk sizes constrain target matching.

C. Rapid Asymmetric Extremum (RAM)

  • RAM’s mean chunk size is modeled by conditioning on the maximum of h random bytes and averaging the geometric waiting time until a matching byte.The calibration minimizes the difference between the model-predicted mean and target µ over positive integer horizons, assuming an unbounded IID stream and counting the matching byte.Source: C. Rapid Asymmetric Extremum (RAM) · pp. 5–6
  • Replacing the random horizon maximum with its expected value underestimates mean waiting time at small horizons, but becomes accurate as the probability of a maximum value of 255 approaches one.The waiting time is nonlinear in the maximum, so evaluating it at the expected maximum misses variation between chunks.Source: C. Rapid Asymmetric Extremum (RAM) · p. 6
  • For targets of 512, 1024, 2048, 4096, and 8192 bytes, the benchmark uses RAM horizons of 327, 780, 1792, 3840, and 7936, respectively.At the two smallest targets, the model predicts 544 B and 1030 B means; the stated unrounded prediction errors are 6.17% and 0.57%.Source: C. Rapid Asymmetric Extremum (RAM) · p. 6

D. Minimal Incremental Interval (MII)

  • MII’s boundary predicate requires a strictly increasing window, whose probability estimate yields factorial growth in mean chunk size as w increases.The estimate treats candidate windows as independent; the paper applies an empirical 1.14 correction to the inverse-probability term, not the window-length term.Source: D. Minimal Incremental Interval (MII) · p. 6
  • MII cannot align its available rounded predictions of 147, 877, 6248, and 51341 bytes to the full target range; the benchmark uses w=6 or 7.For w=6 and w=7, the rounded RAND means are 887 B and 6242 B, respectively.Source: D. Minimal Incremental Interval (MII) · p. 6

E. Parity Check of Interval (PCI)

The paper calibrates PCI and SeqCDC parameters before evaluating throughput, and reports substantial throughput differences among base algorithms on RAND. It relates those differences to instruction counts and branch predictability.

E. Parity Check of Interval (PCI)

  • PCI’s chunk size depends on both θ/w and the absolute window size, so the authors select parameters by RAND simulation and reuse them across datasets.The window acts as a lower bound on chunk size.Source: E. Parity Check of Interval (PCI) · p. 6

F. SeqCDC

  • SeqCDC’s mean chunk size is the product of SeqLength, SkipTrigger, and SkipSize, but different parameter combinations can produce the same mean and different throughput-deduplication tradeoffs.The study selects simulated configurations per target while avoiding target-specific extremes in SkipSize, then fixes them before realistic-dataset evaluation.Source: F. SeqCDC · p. 6

A. Results

  • On RAND at 2 KiB, Gear reaches 652 MiB/s, Buzhash 311 MiB/s, RAM 886 MiB/s, AE 650 MiB/s, SeqCDC 595 MiB/s, and MII 209 MiB/s.Rabin and PCI require more than 30 instructions per byte, while Gear uses approximately 13; MII’s 18% branch-misprediction rate accompanies its 0.82 IPC.Source: A. Results · p. 7

B. Key Takeaways

  • Compiled-code constant complexity and branch predictability help explain throughput differences: MII is simple but difficult for the machine to execute, whereas Gear is both simple and fast.These findings concern the measured implementations and system.Source: B. Key Takeaways · p. 7

VI. CHUNK SIZE DISTRIBUTION

Chunk-size distributions expose differences in tuning accuracy, variance, and behavior on realistic data. AE is the most consistent overall, while RAM and other algorithms show important workload-specific weaknesses.

VI. CHUNK SIZE DISTRIBUTION

  • Chunk-size distributions are assessed by empirical mean, whose proximity to the target indicates tuning accuracy, and standard deviation, which measures spread.Source: §VI · p. 7

A. General Overview

B. Mean and Variance

  • Gear tends to keep mean sizes closer to target, but hash-based methods struggle with variance; Rabin and Buzhash fare poorly on DB, CODE, and VMB.Source: B. Mean and Variance · p. 8
  • PCI has substantial target-size deviation and high variance across most settings; MII performs slightly better, though variance may matter less for synchronization.Source: B. Mean and Variance · p. 9

C. Key Takeaways

  • Only AE consistently achieves low variance on realistic workloads; RAM retains pathological long upper tails despite its horizon-based lower bound.Source: C. Key Takeaways · p. 9
  • AE is the most consistent across datasets, while Gear and SeqCDC perform well on several metrics.Source: C. Key Takeaways · p. 9

VII. DEDUPLICATION RATIO

Deduplication ratios generally fall as target chunk size increases, but raw ratios can favor algorithms that produce unusually small chunks. Accounting for metadata and achieved granularity gives AE the most favorable and stable storage tradeoff in most cases.

VII. DEDUPLICATION RATIO

  • The study complements deduplication ratio with metadata-adjusted storage savings plotted against empirical mean chunk size, using a 64-byte cost per emitted chunk.Source: §VII · p. 10

A. Results and Key Observations

VIII. DISCUSSION

The paper argues for evaluating base cut-point rules separately from higher-level techniques, then compares their behavior under a common benchmark. Within the tested workloads and target range, AE is the most robust tested base algorithm, while the discussion qualifies that conclusion by workload and chunk-size calibration.

VIII. DISCUSSION

  • The guidance ranks base algorithms only; it does not rank composite algorithms or end-to-end systems that also depend on thresholds, normalization, caching, fingerprinting, and storage organization.Source: §VIII · p. 11

A. Summary of Results

  • Rabin and Gear retain competitive deduplication after accounting for achieved mean chunk sizes, but Rabin can produce pathological small chunks whose metadata changes the apparent benefit.The discussion points readers to Figures 8a and 8b for the metadata-adjusted comparison.Source: A. Summary of Results · p. 11
  • At target chunk sizes larger than those tested, AE may degrade because of the scaling-window problem, and Gear may be a more robust alternative.Source: A. Summary of Results · p. 11
  • On CODE, RAM can fail to find boundaries and produce pathologically large chunks; MII, PCI, and SeqCDC show no clear storage-oriented advantage over AE or Gear.Source: A. Summary of Results · p. 11

B. Contrasting Results with Literature

  • The propagated AE parameterization error produced chunks 13% smaller than target at 512 B and 39% smaller at 8 KiB in RAND experiments.The authors caution that these mean-size deviations do not bound deduplication gains on other workloads or establish a ranking reversal.Source: B. Contrasting Results with Literature · pp. 11–12
  • Earlier RAM evaluations focused on high-entropy datasets and conflated throughput with deduplication, while this study finds poor performance on low-entropy data such as CODE.The authors note that synthetic-data and maximum-chunk-size choices may explain divergent robustness findings in another study.Source: B. Contrasting Results with Literature · p. 12

IX. RELATED WORK

  • Prior algorithm comparisons often lack consistent datasets and methods; some reported throughput also includes fingerprinting costs or relies on artificial inputs.The cited examples include SHA-1 fingerprinting that favors algorithms producing fewer chunks and synthetic zero sequences that omit low-entropy strings.Source: §IX · p. 12

X. CONCLUSION

  • Modular evaluation separates base cut-point rules from higher-level techniques; within the tested scope, AE is most robust, Gear remains a strong hash-based choice, and RAM is fragile on low-entropy inputs.The conclusion limits this guidance to the evaluated workloads and target range.Source: §X · p. 12

APPENDIX A STOCHASTIC ANALYSIS OF AE

The appendix models AE cut points under uniformly distributed random bytes by analyzing the maximum over a byte horizon and the conditioned matching process. It derives a simple parameter approximation for large targets, but finds exact analysis impractical for small targets.

AE cut-point rule

  • In AE, a cut point occurs at the first position where the byte is at least the maximum of the following h-byte horizon.Source: Appendix A · p. 16

Conditioned matching probabilities

  • Matching events are sequentially conditioned because prior bytes must fail the matching condition, and overlapping horizons are not independent.The analysis expresses this dependence as a chain of recursive conditional probabilities.Source: Appendix A · p. 16

Maximum-byte distribution

  • Mh denotes the maximum value among h uniformly distributed bytes; its expected value approaches 255 as h increases.Figure 9 plots its probability mass function, with discrete m shown as a line plot for readability.Source: Appendix A · p. 16, Figure 9 · p. 16

Large-target approximation

  • For target chunk sizes beyond 2 KB, the approximation gives µ ≈ h + 256, so the parameter can be set using h ≈ µ − 256.This follows from the approximation that a cut point is found after evaluating 256 bytes on average.Source: Appendix A · p. 16

Small-target limitation

  • Exact analysis for small target sizes is computationally impractical, so the authors recommend experimental tuning of h there.The authors recommend the approximation for targets beyond 2 KB instead.Source: Appendix A · p. 17

APPENDIX B STOCHASTIC ANALYSIS OF RAM

The appendix models RAM chunk lengths through a maximum-byte threshold and a geometric waiting time, then examines how an approximation affects benchmark horizon selection. It also gives large-horizon behavior and notes implementation factors needed to relate the IID model to measurements.

APPENDIX B STOCHASTIC ANALYSIS OF RAM

  • RAM sets M_h to the maximum of the first h IID uniform bytes, then cuts after the first subsequent byte at least M_h, making L = h + T.Conditional on M_h = m, T is geometric with success probability p_m = (256 − m)/256; averaging over the maximum distribution yields a mixture of geometric waiting times.Source: Appendix B · p. 17
  • 32 B and 6 B: Equation (2) underestimates Equation (1) by approximately these amounts at horizons 327 and 780, respectively.The approximation uses the reciprocal of the average success probability rather than averaging conditional waiting times; Jensen’s inequality gives E[1/p_Mh] ≥ 1/E[p_Mh].Source: Appendix B · p. 17
  • Solving Equation (2) gives benchmark horizons 327, 780, 1792, 3840, and 7936 for target sizes 512, 1024, 2048, 4096, and 8192 bytes, respectively.At the two smallest targets, exact-model predictions and measured RAND means round to 544 B and 1030 B; integer optimization instead selects horizons 300 and 774 for those targets.Source: Appendix B · p. 17
  • As h grows, Pr[M_h = 255] approaches 1, E[T] approaches 256, and the mean chunk length is approximately h + 256.At h = 1792, this approximation differs from the exact mean by less than 1 B.Source: Appendix B · p. 17
  • Relating the IID model to measurements requires accounting for implementation-specific boundary indexing and terminal chunks.Source: Appendix B · p. 17
Loading 2610.13704v1…