Benchmarking Content-Defined Chunking Algorithms for Data Deduplication

Benchmarking Content-Defined Chunking Algorithms for Data Deduplication Marcel Gregoriadis1 , Leonhard Balduf2 , Björn Scheuermann2 , Johan Pouwelse1 1

Delft University of Technology, Delft, The Netherlands Technical University of Darmstadt, Darmstadt, Germany m.gregoriadis@tudelft.nl, leonhard.balduf@tu-darmstadt.de, scheuermann@tu-darmstadt.de, j.a.pouwelse@tudelft.nl

arXiv:2610.13704v1 [cs.DB] 9 Oct 2026

2

Abstract—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 highlevel 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.1 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 lowentropy 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. Index Terms—content-defined chunking, deduplication, storage systems, distributed systems

I. I NTRODUCTION Generative AI is driving rapid data growth and increasing the pressure on storage capacity and network bandwidth. IDC projects global data generation to double between 2025 and 2029, reaching 527 zettabytes annually [1]. Yet across the global datasphere most stored data is redundant, with IDC estimating the ratio of unique to replicated data at roughly 1:9 [2]. This redundancy is highest in backup and archival workloads, including near-identical VM images, container layers, snapshots, and database backups [3], where successive versions overlap heavily. Chunk-based data deduplication [4]– [6] makes retaining and synchronizing this history affordable. Large-scale studies of Microsoft [7], [8] and EMC [9] report space savings of up to 83 %. Data deduplication has been studied directly in database and primary-storage settings, including online database deduplication and inline deduplication for primary storage [10], [11]. At the core of chunk-based storage deduplication sits a chunking algorithm that partitions an incoming byte stream into chunks for redundancy detection. 1 The popular benchmark tool DedupBench has since corrected it following our report.

Caching Dual-Divisor

Normalized Ch.

Normalized Ch.

Min/Max Thresh.

Min/Max Thresh.

Min/Max Thresh.

Rabin

Gear

Rabin

TTTD [22]

FastCDC [14]

QuickCDC [16]

Fig. 1: Most modern chunking algorithms can be decomposed into modular building blocks.

While partitioning data into fixed-size chunks is simple and efficient, modern deduplication systems employ content-defined chunking (CDC) algorithms that place boundaries based on a chunk’s content rather than its size. CDC improves resilience to byte insertions and deletions, thereby increasing the amount of redundant content that can be identified [4], [8]. The choice of the chunking algorithm directly governs both how much redundancy is exposed and how fast data can be ingested. Over the years, numerous chunking algorithms have been proposed, claiming higher throughput [12]–[16], improved deduplication ratios [17]–[19], and lower chunk-size variance [20]–[22]. We find that many proposed chunking algorithms are compositions of interchangeable techniques. Based on this observation, we advocate a modular view of chunking algorithms, distinguishing between base chunking algorithms (e.g., Rabin [4] and Gear [23]) and composite algorithms (e.g., TTTD [22] and FastCDC [20]), which augment base chunking algorithms with higher-level optimizations. Figure 1 illustrates three pervasive chunking algorithms and their decompositions. This perspective reveals that many composite algorithms are evaluated only in combination with a specific base chunking algorithm, despite being compatible with a broader range of alternatives. Consequently, identifying the strongest base chunking algorithm becomes a fundamental question. Yet the state of the art remains unclear. Existing studies often conflate the effects of high-level techniques and base chunking algorithms rather than evaluating them independently [13], [15], [24], [25]. For example, TTTD is frequently benchmarked using Rabin [13], [26], while newer composite algorithms such as RapidCDC [27], UltraCDC [28], and SuperCDC [29] largely recombine existing techniques in different ways. As a result, current benchmarks provide limited

Unique chunks: e3

Files

Chunking & fingerprinting

e3 39

6c b9 39

Metadata:

e3 a4

Indexing & storing

e3

6c

a4

39

File A:

b9

File B: File C:

b9

Fig. 2: Overview of data deduplication process.

insight into the relative merits of the underlying base chunking algorithms. The problem is further exacerbated by inconsistent evaluation methodologies. Existing benchmarks are typically conducted on different datasets and with custom metrics [15], [21], [23], [30], [31]. Moreover, several algorithms lack a principled method for selecting parameters that achieve a desired target chunk size, precluding fair comparisons based on deduplication efficiency, since smaller chunks generally yield higher deduplication ratios. For instance, we uncover a longstanding parametrization error in AE [21] that caused chunks to be 13–39 % smaller than the configured target size, artificially inflating reported deduplication ratios. In this paper, we conduct a rigorous analysis and benchmark of representative base chunking algorithms. Our goal is to determine which byte-level cut-point rules remain effective once high-level techniques are stripped away and algorithm settings are selected for common configured targets on uniformly random data before being evaluated unchanged on realistic workloads. Specifically, this paper makes the following contributions: • We release a new benchmark framework that supports modular CDC evaluations by separating base chunking algorithms from high-level techniques. • We benchmark eight representative base chunking algorithms—Rabin [8], Buzhash [32], Gear [23], AE [21], RAM [15], MII [30], PCI [31], and SeqCDC [13]—on four realistic workloads (Table II), measuring throughput, average chunk size, chunk-size variance, and deduplication ratio. • We derive parameter rules for common target chunk sizes, including formulas for AE, RAM, and MII, and assess their calibration on uniformly random data, distinguishing configured targets from empirical means. II. BACKGROUND AND M OTIVATION Data deduplication splits files into chunks, fingerprints them, creates reconstruction metadata, and stores unique chunks and metadata (see Figure 2). Our work focuses on the first stage of this pipeline. The algorithm by which files are chunked directly influences the probability of finding redundant chunks, which can then be deduplicated. The most efficient approach, Fixed-Size Chunking (FSC), splits a file into equal-sized chunks but suffers from the boundary-shift problem illustrated in Figure 3: inserted or removed content shifts boundaries and causes unchanged regions to appear

unique. Content-Defined Chunking (CDC) algorithms address this problem by forming chunk boundaries based on content rather than position. These failure modes and design goals motivate the main CDC families discussed below.

chunk boundary File A shifted File B inserted content Fig. 3: Boundary-shift problem.

A. Hash-Based CDC The earliest CDC algorithms used a sliding window of size w over a file and a hash function to determine chunk boundaries. The hash of each iteration of the sliding window is compared against a bitmask to determine new chunk boundaries. For efficiency this is done using rolling hash functions, such as Rabin [33]–[35], Buzhash [32], or Gear [23]. We refer to this approach generally as Basic Sliding Window (BSW), illustrated in Figure 4. Hash-based CDC yields higher deduplication ratios than FSC, but is criticized for low throughput and high chunk-size variance. Efficient rolling hashes such as Gear [23] mitigate the former, while the latter remains intrinsic to hash-based CDC.

h

e

l

l

o

w

o

r

l

d

w

o

r

l

d

w

o

r

l

d

sliding window w h

e

l

l

o ...

h

e

l

l

o

Fig. 4: Window sliding over a file byte-by-byte. At every offset, the fingerprint generated from the current window is matched against a bitmask.

B. Chunk-Size Variance High chunk-size variance gives rise to the issue of pathological, i.e. very large or very small, chunk sizes [22]. Very large chunks can be the product of a recurring pattern in the byte sequence that fails to meet the criteria for setting a cutpoint [36]. Large chunks are less likely to be duplicates and more likely to be affected by modifications, increasing the number of bytes that must be stored again [22]. Pathologically small chunks are undesirable as well because they produce more overhead due to additional metadata, processing, and, in distributed settings, additional round-trip times. In some use cases, high chunk-size variance is not a critical concern. For example, with MII [30] and PCI [31], Zhang et al. focus on the application of CDC for incremental file synchronization (e.g., with rsync [37]). This use case does not consider data reduction within long-term storage systems but instead a transaction of file synchronization between two machines. This relaxes the constraint on low chunk-size variance, as the overhead from excessively large or small chunks does not accumulate over multiple revisions of the dataset. C. Hashless CDC High chunk-size variance and low throughput led to the development of other approaches. MAXP [38] and LMC [39] were the first CDC algorithms to determine chunk boundaries based on local extrema in the data stream. As an illustrative example, Figure 5 presents AE [40], a representative hashless CDC algorithm. By using byte comparisons rather than hash functions, these algorithms claim to achieve higher throughput than hash-based algorithms. Furthermore, they are attributed with a significantly lower chunk-size variance [39], [40]. Modern adaptations of this technique can be found in AE [40] and RAM [15]. Alternative hashless CDC algorithms exist: PCI [31] compares the popcount of a sliding window to a threshold in order to determine chunk boundaries.

Byte value

c1

c2

c3

c4

200 h

III. M ETHODOLOGY

100 0 0

of several high-level techniques. Table I summarizes their compatibility with base algorithms beyond those used in the original papers. Chunking Throughput: A popular strategy for increasing chunking throughput and lowering chunk-size variance at the same time is the enforcement of minimum and maximum chunk sizes [13], [15], [20]. This ensures that chunk sizes remain within a desirable range and allows implementations to skip computation for the minimum chunk length within each new chunk. While effective at improving those two metrics, it contradicts the very idea of CDC: to set chunk boundaries based on content, not position. Inevitably, this technique trades off deduplication efficiency [8], [20], [40]. More sophisticated techniques include, e.g., a caching layer [16], [27] or normalization of the chunk-size distribution [20], [28], [29] to allow for skipping with no or negligible impact on deduplication ratio. Other efforts have explored parallelization by exploiting properties of modern hardware [12], [24], [42], [43]. Chunk-Size Variance: Hash-based chunking algorithms suffer from a highly skewed chunk size distribution [20], [21], [46]. A common approach to achieve a more uniform chunksize distribution while minimizing the impact on deduplication ratio is the use of multiple threshold bitmasks. Multiple thresholds enable dynamic adjustments to the probability of satisfying the chunking condition, increasing or decreasing it as needed. Most notable are the algorithms in TTTD [22] and Regression Chunking (RC) [8]. Similar algorithms have later been proposed under the label of Normalized Chunking (NC) [20], [28], [29]. Furthermore, a popular technique for eliminating pathologically small chunks involves merging adjacent chunks [12], [22], [42]. Similarly, pathologically large chunks can be eliminated by rechunking them with a more relaxed chunking condition. Deduplication Ratio: Rechunking large chunks also positively affects the number of redundant chunks that are detected in a dataset. Different variations of this technique have been formalized, e.g., within FBC [18] and Bimodal chunking [17], among other approaches [19], [44], [45].

5

10 15 Byte position

20

25

Fig. 5: Illustration of the AE chunking algorithm on a sequence of 27 bytes and a horizon h = 4. The vertical red lines mark the cut points. D. High-Level Techniques Parallel to improvements in the basic chunking mechanism, researchers have proposed high-level methods to increase chunking throughput, lower chunk-size variance, or enhance the deduplication ratio. Often (e.g., with FastCDC [20] and QuickCDC [16]), proposed algorithms are a combination

We benchmark eight representative CDC algorithms— Rabin, Buzhash, Gear, AE, RAM, MII, PCI, and SeqCDC—in a standardized environment, measuring throughput, chunk-size distribution, and deduplication ratio across target chunk sizes from 512 B to 8 KiB. We isolate algorithmic performance from factors not inherent to the chunking algorithms themselves: deployed systems often combine a base algorithm with size thresholds, normalization, caching, skipping, and fingerprinting, which obscure which cut-point rule causes the measured effect. We therefore tune every algorithm to the same target chunk sizes on uniformly random data—analytically where possible and by simulation otherwise—freeze those settings, and then evaluate them unchanged on all realistic datasets. We discuss the implications of this choice in Section VIII. We run our benchmarks on a machine with an Intel Xeon Gold 6154 CPU at 3.00 GHz and 378 GB of mem-

TABLE I: Compatibility matrix between base chunking algorithms and high-level techniques. High-Level Techniques Throughput

Base Algorithm Hash-based Hashless

JC [41]

SIMD [12]

MUCH [42]

VectorCDC [24]

✓

✓

✓ ✓

✓

Chunk-Size Variance

Deduplication

GPU [43]

Caching [16], [27]

Multiple Thresholds [8], [20], [22], [28], [29]

Merging [12], [22], [42]

Rechunking [17]–[19], [44], [45]

✓

✓ ✓

✓ ✓

✓ ✓

✓ ✓

TABLE II: Datasets and their Gzip compression ratios. Name

Size

Compress. Ratio

RAND WEB DB VMB CODE

11 GB 46 GB 100 GB 285 GB 110 GB

100 % 88 % 31 % 25 % 18 %

Description Randomly generated binary file. One month of tar-ed daily website snapshots of nytimes.com using wget -l 1 and the Internet Archive. 25 snapshots of a MySQL VM running TPC-C [47]. 33 backups of a nightly Rust build server. 207 versions of tar-ed source code distributions for Linux, GDB, GCC, and Emacs.

TABLE III: Algorithmic parameter settings. Algorithm

Parameter Settings

Rabin, Buzhash Gear AE RAM MII PCI SeqCDC

w = 32, b = round(log2 (µ − w)) b = round(log2 µ) Horizons in Table IV Chosen in accordance with Equation (2). Chosen in accordance with Equation (3). Obtained through simulation. Obtained through simulation.

ory, running Debian 12. Throughput and microarchitectural findings describe this system and the evaluated implementations; their magnitude and ranking may change with the processor, compiler, or execution environment. For identical input bytes, parameters, and deterministic algorithm semantics, chunk boundaries and the resulting deduplication ratios and chunk-size distributions do not depend on execution speed. Our recommendations concern the evaluated base algorithms; they do not establish rankings for complete deduplication systems or for composites that add thresholds, normalization, caching, or skipping. To produce a desired mean chunk size, CDC algorithms must be tuned through their parameters. Section IV derives parameter rules from each algorithm’s stochastic properties, using simulation where analytical derivation is intractable. A. Datasets Because both deduplication ratio and chunk-size distribution strongly depend on the input data, we use multiple realistic datasets and one artificially generated dataset with maximal entropy. Our dataset selection follows standard practice in CDC algorithm evaluations [13]–[17], [24]. Table II lists the datasets and their Gzip compression ratio2 : Compression ratio =

Size After Gzip Compression . Original Size

2 We apply Gzip with the default compression level of 6.

Lower values indicate more compressible data. The datasets are chosen to reflect storage and data-management scenarios in which deduplication is typically deployed. RAND serves as a high-entropy calibration baseline for parameter tuning and throughput measurements, while the realistic datasets exercise different forms of temporal redundancy. WEB captures daily website snapshots, where HTML, scripts, metadata, and static assets evolve at different rates. DB represents repeated backups of a transactional database VM running TPC-C, a setting where database pages, logs, and filesystem layout can all influence redundancy. VMB captures nightly backups of a build server, combining operating-system state, source trees, package caches, and generated build artifacts. CODE contains many versions of large source-code distributions and stresses algorithms on compressible text, small files, and archive padding. For WEB and CODE, we store the file collections as uncompressed TAR archives, while DB and VMB are snapshot-style storage images. We evaluate these backups and snapshots as streams rather than isolated files. B. Benchmarking Framework To measure both algorithm throughput and the chunks produced, we implement a benchmarking framework in Rust, with a focus on performance and efficiency. The framework, including the algorithm implementations, is published on GitHub under permissive licenses.3 It simplifies the implementation of new base chunking algorithms and enables their performance to be tested either in isolation or together with high-level techniques such as NC, caching, and size limits. It also excludes overhead from fingerprinting and avoids disk I/O by reading data from a RAMdisk. The framework consists of a driver that reads the input file in large blocks and uses them to drive the selected algorithm. Each algorithm receives consecutive blocks of file data, identifies boundaries within them, and advances its internal state as it ingests data. The algorithms closely follow their original descriptions. All algorithms are integrated into a 3 https://github.com/mrd0ll4r/cdc-bench

single benchmark program, compiled with the release profile and tuned for the target machine. The throughput baseline uses Rust 1.82.0-nightly. The release configuration enables thin link-time optimization, one code-generation unit, and native CPU targeting (-C target-cpu=native). When evaluating algorithm throughput, we do not fingerprint the generated chunks. Instead, the benchmark program computes and reports a single aggregate value—the sum of all chunk sizes—to ensure that the compiler cannot eliminate the chunking code through optimization. We verify that file access does not limit performance by implementing and evaluating fixed-size chunking (FSC) within the same framework. Sufficient memory is reserved to prevent memory pressure during execution. Apart from the benchmark process itself, the system remains idle throughout the experiments. All performance measurements are conducted sequentially to avoid interference between benchmark runs. For each combination of dataset, algorithm, and target chunk size, the benchmark is executed n = 10 times. Additionally, we perform a single warm-up run for each dataset-algorithm combination before collecting measurements, and we capture performance counters using perf. Throughput measurements use RAND, copied to a tmpfs RAMdisk before execution. The warm-up uses a target chunk size of 512 B for each algorithm. The benchmark runs in a KVM virtual machine without explicit CPU affinity or NUMA placement controls. CPU frequency is controlled by the host firmware, with power saving disabled. Where applicable, we normalize measurements by dataset size. For microarchitectural counters such as instructions per cycle (IPC), instruction count, and branch count, we report mean values; the standard error is at most 0.01 for all reported metrics and is therefore omitted. For runtime and throughput, which are commonly skewed in benchmarking experiments [48], we report the median and interquartile range (IQR), calculated as Q3 − Q1 . IV. PARAMETER S ETTINGS AND D ERIVATIONS Every CDC algorithm operates based on specific parameter settings. We denote the configured target mean chunk size by µ and the empirical mean by c̄. While c̄ depends on both the parameter settings and the characteristics of the respective dataset, parameter selection can be theoretically grounded with the assumption of uniformly distributed random data. We therefore use uniformly random data as a common calibration baseline and then evaluate how well the resulting settings transfer to realistic datasets. This choice separates parameter tuning from dataset-specific behavior and avoids retuning algorithms on the same data used for comparison.

successive cut-point decisions are statistically independent. We set window size w = 32 for Rabin and Buzhash to align with the implicit window size in Gear. The implementation selects b = round(log2 (µ − w)) for Rabin and Buzhash, and b = round(log2 µ) for Gear, which does not impose the same explicit window-fill delay. For the five power-of-two targets in this study, both rules yield b = 9, 10, 11, 12, 13, respectively. B. Asymmetric Extremum (AE) The average chunk size in AE is largely determined by the horizon h. The original authors suggest that h = µ/(e − 1) [21], [40]. This formula has also been implemented in their open-source testing framework Destor [49], as well as another benchmarking tool DedupBench [26] (who corrected the formula following our report [50]). Following this, the formula was used to produce results for an evaluation of AE in various other works [20], [41], [51], [52]. However, preliminary experimental evaluations on random data show chunk size averages well below the desired target, motivating us to revisit the formula. Our theoretical analysis then reveals that this formula fails to account for the discrete value range of random variables within [0, 255], as well as the conditioning of probabilities on dependent events. Concretely, the maximum byte value in a horizon of length h equals 255 with probability 1 − (255/256)h . For large h, the cut predicate therefore approaches the event that the next unseen byte equals 255, 1 . Based on this reasoning, which occurs with probability 256 we propose using the approximation h ≈ µ−256 if µ ≥ 2 KiB and rely on simulations when target chunk sizes are smaller. At the 2 KiB threshold, the approximate horizon h = 1792 gives 1 − (255/256)1792 ≈ 0.999. This probability supports the large-horizon approximation; it is not a bound on its meansize error. Table IV lists the horizons obtained from simulation for the two smaller targets and from h = µ−256 for targets at or above 2 KiB. Appendix A provides the detailed stochastic analysis of AE. TABLE IV: AE horizon parameterization. µ bytes

h bytes

512 1024 2048 4096 8192

348 793 1792 3840 7936

A. Basic Sliding Window (BSW)

C. Rapid Asymmetric Extremum (RAM)

Given random data, a uniformly distributed hash function, and a bitmask of length b, hash-based algorithms find a chunk boundary at each byte with the probability of 2−b [35], [46]. Preliminary experiments confirmed uniform hash-value distributions for Rabin, Buzhash, and Gear. These measurements describe how often hash values occur, but do not test whether

The authors of RAM do not explicitly state how to tune the horizon h for a desired mean chunk size. Let Mh be the maximum of h independent, uniformly distributed bytes. Conditional on Mh = m, the number T of subsequent bytes up to and including the first matching byte is geometric with success probability (256 − m)/256. Averaging these

conditional waiting times gives the model-predicted mean chunk size µ(h): " # h  255 X m+1 m h 256 µ(h) = h + − . (1) 256 − m 256 256 m=0 This identity assumes an unbounded IID byte stream and counts the matching byte in the chunk. Minimizing |µ(h) − µ| over positive integer horizons provides a theoretical calibration rule for the configured target µ. The benchmark parameter calculation replaces the random horizon maximum by its expected value, giving the approximation 256 . (2) µ e(h) = h + 256 − E[Mh ] This substitution uses a single representative maximum instead of accounting for variation between chunks. It becomes accurate for large horizons, where Pr[Mh = 255] = 1 − (255/256)h approaches one and both means approach h+256. For smaller horizons, however, the maximum varies more, and the waiting time is a nonlinear function of that maximum: evaluating it at the expected maximum underestimates the mean waiting time by convexity. Solving Equation (2) for the target mean and rounding gives the benchmark horizons h = 327, 780, 1792, 3840, 7936 for targets 512, 1024, 2048, 4096, 8192 bytes, respectively. At the two smallest targets, Equation (1) predicts means of 544 B and 1030 B (rounded to whole bytes), matching the rounded RAND measurements in Table VIII. The unrounded predictions exceed the targets by 6.17 % and 0.57 %, respectively. The theoretically calibrated horizons are 300 and 774; they are not the settings used for these measurements. For the three larger targets, both rules select the same integer horizons. Appendix B provides the conditional waiting-time derivation and the detailed approximation-error analysis. D. Minimal Incremental Interval (MII) The average chunk size in MII depends on the interval parameter w. Our approximation starts from the boundary predicate used by MII: a chunk boundary is found when a window of w bytes is strictly increasing. Thus, w counts bytes and a matching window contains w − 1 increasing adjacent comparisons, consistent with the implementation. For uniformly random input, each window contains 256w possible byte sequences. For the predicate to hold, all w bytes must be distinct; for each set of w distinct byte values, exactly one ordering is strictly increasing. The number of satisfying
256 windows is therefore , yielding the approximate boundary w
−w probability 256 · 256 . Treating candidate windows as w independent gives an expected waiting time equal to the inverse of this probability, plus the window length w. This counting argument captures the factorial growth of the average chunk size with increasing w and the weak control over chunk sizes that follows from it, as also noted by the authors of MII [30]. We use the factor 1.14 as an empirical correction calibrated on RAND, fixed across target sizes and datasets. It scales the

inverse-probability term, not the additive window length, and is not a theoretical constant. Dependencies between overlapping windows are a possible explanation for the discrepancy with the independence approximation. This yields the following approximation:   −1 256 µ ≈ 1.14 · · 256−w +w (3) w MII presents a special case among the evaluated algorithms, as w = 5, 6, 7, 8 bytes give rounded predictions of 147, 877, 6248, 51341 bytes, respectively. This makes aligning MII to our range of target chunk sizes impossible. We use windows w = 6, 6, 6, 7, 7 for targets 512, 1024, 2048, 4096, 8192 bytes, respectively. For w = 6 and w = 7, the rounded RAND means are 887 B and 6242 B (Table VIII). E. Parity Check of Interval (PCI) The average chunk size produced by PCI depends on the setting of its two parameters w (window size) and θ (threshold). Specifically, it depends on the ratio wθ , as well as the absolute value of w (as the window acts as a lower bound on the chunk size). Because we are not aware of a tractable analytical mapping from (w, θ) to µ, we obtain suitable values across all target chunk sizes through simulation on RAND. For each target, we select the parameter pair whose simulated mean chunk size is closest to µ and use that pair unchanged for all datasets. TABLE V: Parameter settings for PCI. µ

w bytes

8w bits

θ

θ 8w

512 1024 2048 4096 8192

58 34 61 39 57

464 272 488 312 456

253 157 273 183 262

0.545 0.577 0.559 0.587 0.575

F. SeqCDC The average chunk size in SeqCDC is the product of three parameters: SeqLength, SkipTrigger, and SkipSize. For their experimental evaluation, the authors first generate candidate values via Monte Carlo simulation on randomized data [13]. Based on those results, they select a combination of values that performs best on one of their datasets. We note that the choice of those parameters has a large effect on chunking throughput and deduplication ratio. For example, a higher SkipSize is likely to improve chunking throughput at the cost of the deduplication ratio. Thus, multiple combinations of parameters can yield the same average chunk size and yet differ dramatically on the other metrics. Since no analytical framework is available, we compile a candidate set through simulation on RAND, analogous to the original paper. We then select one configuration per target size that matches µ while avoiding target-specific extremes in SkipSize; this keeps the throughput–deduplication tradeoff comparable across target sizes. The selected configurations are fixed before evaluating realistic datasets.

TABLE VI: Parameter settings for SeqCDC. µ

Seq Length

Skip Trigger

Skip Size

512 1024 2048 4096 8192

4 5 5 5 5

65 85 85 120 55

512 32 256 1024 1024

TABLE VII: Computational performance of chunking algorithms with µ = 2 KiB on RAND. Throughput (MiB/s) Alg. FSC RAM Gear AE SeqCDC Buzhash PCI MII Rabin

Median

IQR

Instr./B

IPC

Br./B

Br. Mispred.

1820 886 652 650 595 311 242 209 195

21 19 16 9 9 6 3 3 2

0.41 8.44 13.41 11.41 10.59 29.36 35.27 12.44 34.30

0.24 2.39 2.78 2.30 1.97 2.90 2.70 0.82 2.08

0.08 1.76 1.75 2.58 1.85 5.07 2.56 2.18 5.06

0.77 % 0.43 % 0.09 % 0.16 % 0.28 % 0.10 % 0.11 % 18.01 % 0.05 %

V. C OMPUTATIONAL E FFICIENCY Much of the discussion and development around chunking algorithms has been fueled by the need to achieve higher throughput while maintaining good deduplication. Rabin, one of the oldest CDC algorithms, is widely known to be slow, which has spurred the development of faster CDC algorithms. We evaluate the algorithms in terms of throughput and use microarchitectural details to explain observed performance differences. Throughput is reported as input processed per execution time. A. Results We first provide an overview of the achievable throughput using the various algorithms. To that end, we evaluate each of them on the RAND dataset with a target chunk size of 2 KiB. For better interpretability of the results, we provide them together with relevant microarchitectural counters in Table VII. We discuss these results in detail below. Hash-Based Algorithms: The hash-based algorithms Rabin and Buzhash have relatively low throughput in this RAND experiment, while Gear is faster. We discuss PCI alongside these sliding-window methods because it uses the same BSW scheme, but PCI is hashless: it replaces hashing with a rolling popcount. Although these algorithms all operate in O(1) per input byte, they differ substantially in constant complexity: Rabin and PCI require more than 30 instructions per input byte, while Buzhash falls just below that, resulting in the highest throughput of the three at 311 MiB/s. Gear uses only ≈ 13 instructions per byte, leading to a much higher throughput of 652 MiB/s. In terms of microarchitectural performance, all algorithms can be executed relatively well at > 2 IPC and solid branch predictability. Among the evaluated hash-based implementations, Gear combines low instruction count with high throughput. This

makes Gear a useful base for further evaluation with highlevel techniques such as SIMD or normalized chunking; those combinations are outside this comparison. Hashless Algorithms: The remaining hashless algorithms use extrema or byte comparisons (AE, RAM, SeqCDC, and MII) and generally perform well, with the exception of MII. Among them, RAM performs best at 886 MiB/s, markedly better than AE at 650 MiB/s. On this system and input, RAM thus achieves its goal of being faster than AE [15]. SeqCDC follows closely at 595 MiB/s. This is impressive, considering we elect to implement only the core SeqCDC algorithm, without the optimization of skipping the start of each chunk. MII, although algorithmically simple, performs poorly at only 209 MiB/s. It executes slightly more instructions per input byte than AE, RAM, and SeqCDC, but it uses the CPU poorly, reaching only 0.82 IPC. A closer look shows that this is due to the poor predictability of the branch comparing the current input byte to the previous one. We find that 18 % of branches are mispredicted (“Br. Mispred.”), by far the worst behavior of all examined algorithms. Among these algorithms (MII, RAM, SeqCDC, AE), MII performs poorly because its branch is difficult to predict. Both AE and SeqCDC perform well, while RAM has the highest throughput in this experiment. These throughput rankings apply to the evaluated base implementations on RAND at 2 KiB on the measured system. Finally, if CDC is not a concern, FSC unsurprisingly outperforms all CDC contenders at about 1.8 GiB/s of processed input. These results also show that our benchmarking system is not limited by I/O. B. Key Takeaways Modern CPUs are complex. It is not always obvious how an algorithm, given in pseudocode, performs on a real system. We were able to show that various factors of the compiled code and microarchitecture, in particular constant complexity and branch predictability, play an important role in achieving higher throughput. Some algorithms (e.g., MII) are algorithmically simple yet difficult for the machine to execute. Others (e.g., Gear) are both simple and fast to execute. VI. C HUNK S IZE D ISTRIBUTION Chunk-size distribution affects deduplication ratio, computational efficiency, and storage savings. Ideally, chunks have empirical mean c̄ close to the target µ without excessive variance: overly large chunks miss deduplication opportunities, while overly small chunks increase processing and metadata overhead. Because some variation is still needed to recover from boundary shifts, these distributions reveal both tuning accuracy and robustness across datasets with different byte patterns and compressibility. We characterize each CDC algorithm’s chunk-size distribution using two metrics: 1) The empirical mean c̄, whose proximity to µ indicates tuning accuracy. 2) The empirical standard deviation s, which measures spread around the mean.

Empirical CDF

0.2

0.8 0.5 0.2

00

00

40

30

00

00 10

20

0

0 40 0

00

00

0.0 30

0

0

40 00

30 0

20 0

00

0

0.0 10

00 40

00 30

00 20

10

00

0.0 0

0.0

0.2

0.5

20

0.2

0.5

0.8

0

0.5

0.8

1.0

10 00

0.8

1.0

Empirical CDF

1.0

Empirical CDF

Empirical CDF

1.0

Chunk Size (B)

Chunk Size (B)

Chunk Size (B)

Chunk Size (B)

(a) VMB

(b) DB

(c) WEB

(d) CODE

AE

Buzhash

Gear

MII

PCI

Rabin

RAM

SeqCDC

Fig. 6: Chunk-size distributions for target chunk size µ = 1024 truncated at [0, 4µ].

A. General Overview We first compare the empirical chunk-size distributions for all algorithms on the realistic datasets at target chunk size µ = 1024. Figure 6 presents these distributions as empirical cumulative distribution functions (CDFs), truncated to the range [0, 4µ] for readability. For most algorithms and datasets, the empirical CDF is already close to 1 near 4 KiB, indicating that almost all chunks remain within four times the target size. The CODE dataset is the main exception: in Figure 6d, PCI and RAM show pathological size distributions, with approximately 15 % of chunks exceeding 4µ. More generally, the BSW algorithms produce many below-target chunks together with heavy-tailed distributions, especially on more compressible datasets. This is because all BSW algorithms follow the same stochastic property: Each position of the data stream, looked upon independently, is equally likely to become a chunk cut-point (cf. Section II). However, each position’s probability also depends on all previous positions not having fulfilled the same matching condition. Therefore, we observe that these distributions produce the bulk of chunks at a small size, determined by the window size or other feature of the algorithm, and then decay, forming a heavy-tailed distribution. This shifts the mean closer to the target, but inevitably results in a large chunk-size variance. AE and RAM, in contrast, impose a lower bound through their horizon, so complete chunk sizes cannot fall far below the target µ. This lower bound does not constrain the upper tail: AE concentrates chunk sizes near the target, whereas RAM can still produce pathological distributions on realistic datasets. B. Mean and Variance We report the mean chunk size c̄ and standard deviation s across all datasets and algorithms. A detailed quantitative table is provided in Table VIII. Cell colors follow a continuous scale, with lighter shades indicating values closer to the optimum, which for c̄ corresponds to µ. The color range reaches its maximum where the mean deviates ±100 % from the target µ. For the standard deviation s, the color range is relative to the empirical mean c̄, in a range [0, 2c̄]. Values are

aggregated across all evaluated target chunk sizes. Recall from Section III that we examine algorithms without constraining chunk sizes through minimum or maximum thresholds. We make the following observations: Firstly, RAND provides an empirical calibration check for AE and MII. For RAM, the measured means agree closely with the expectation in Equation (1) at the benchmark horizons. In particular, the configuration at a 512 B target produces a mean of 544 B, consistent with the parameter-selection approximation error quantified in Section IV-C. In general, all algorithms perform predictably within acceptable bounds on artificial pseudorandom data. On real-world datasets, results are much more varied. For many algorithms, the more compressible datasets tend to yield greater chunk-size variance. The compression ratios in Table II summarize dataset compressibility. Often, with hash-based algorithms, we furthermore observe an increase in variance when target chunk sizes are higher. Hash-Based Algorithms: Different hash functions within hash-based algorithms yield slightly different chunk-size distributions. While Gear tends to maintain mean sizes closer to the target, all hash-based methods struggle with chunk-size variance. In particular, Rabin and Buzhash perform poorly on the more compressible datasets DB, CODE, and VMB. One hypothesis is that Gear’s chunking rule interacts more favorably with the byte patterns in these datasets; isolating that mechanism requires further experiments. Hashless Algorithms: The lowest levels of variance overall are produced by AE. RAM achieves similarly low variance only on the RAND dataset. On the realistic datasets, RAM often fails to find chunk boundaries frequently enough, resulting in pathological chunk-size distributions. The authors of RAM warn against poor performance on files containing lowentropy data. In their paper [15], the experiments yield very similar results in comparison with AE. We find pathological performance on all realistic datasets, including WEB, whose Gzip compression ratio is comparatively high. SeqCDC also produces means close to the target on all datasets except CODE, indicating a potential sensitivity to CODE’s byte patterns.

TABLE VIII: Extensive results on empirical means and standard deviations of produced chunk sizes. Algorithm

512 B

1024 B c̄

s

2048 B c̄

s

4096 B c̄

s

8192 B c̄

c̄

s

RANDOM Rabin Buzhash Gear AE RAM PCI MII SeqCDC

s

542 544 511 512 544 506 887 506

511 512 510 136 234 465 881 698

1054 1057 1024 1024 1030 1017 887 1026

1023 1026 1022 209 252 990 881 1036

2078 2084 2047 2048 2048 2085 887 2069

2046 2053 2045 252 255 2038 881 2185

4123 4137 4094 4095 4096 4290 6242 4110

4096 4106 4088 255 255 4257 6238 4578

8213 8240 8197 8191 8193 8693 6242 8544

8185 8208 8181 255 255 8637 6238 9024

CODE Rabin Buzhash Gear AE RAM PCI MII SeqCDC

278 351 572 484 32663 6609 333 191

1201 1317 1718 147 3620803 116719 2977 1521

364 476 1165 1046 61202 10722 333 318

1507 1668 2706 313 4955982 259899 2977 2794

427 628 2305 2228 120909 22598 333 373

1869 2395 4496 588 6989936 948426 2977 3199

478 720 4706 4594 219247 30252 481 420

2471 3234 8450 1135 9411473 883873 6299 3731

517 775 9358 9332 387964 44879 481 561

3475 4437 15605 2266 12516487 1627986 6299 4782

WEB Rabin Buzhash Gear AE RAM PCI MII SeqCDC

444 551 523 517 672 357 841 424

525 542 561 147 53567 2007 1304 744

717 1058 1039 1048 1256 491 841 943

1002 1082 1103 245 73244 3523 1304 1424

1071 2090 2076 2124 2435 739 841 1805

1868 2195 2173 374 101956 4617 1304 2665

1422 4009 4189 4224 4764 994 4970 3377

3255 4252 4491 536 142598 7760 8797 5158

1702 7740 8498 8406 9414 1323 4970 6572

5231 9274 9534 904 200436 15125 8797 9467

DB Rabin Buzhash Gear AE RAM PCI MII SeqCDC

95 823 524 448 886 4481 1490 631

277 47860 38456 220 58702 376356 69072 43950

101 1579 1531 949 1741 1968 1490 1591

402 66862 65776 339 82555 264093 69072 71362

104 3050 3006 2079 3601 8546 1490 2785

571 93309 92557 618 117545 1670258 69072 95023

106 5670 6162 4328 7147 7853 8724 5039

796 127677 134051 1107 166900 1121784 185368 128883

107 10108 12129 8780 13830 11720 8724 9401

1081 172277 190428 2180 231920 2037800 185368 180942

VMB Rabin Buzhash Gear AE RAM PCI MII SeqCDC

170 676 602 471 1298 2150 1619 503

653 16728 15855 163 112214 93943 34972 17570

194 1312 1222 1047 2603 3166 1619 1538

843 23348 23730 352 160204 127712 34972 34052

212 2455 2435 2297 5141 5365 1619 2391

1143 32106 33795 706 256212 167882 34972 42843

222 4949 4867 4807 9595 6063 10623 3717

1549 46735 48583 1438 351555 197997 122867 57142

227 9063 9184 9542 17255 8925 10623 6565

2144 66011 69614 2664 415735 253655 122867 77491

CDC for Data Synchronization: PCI exhibits a significant deviation from the target chunk size and high chunk-size variance across most settings. Its predecessor, MII, although restrictive in the targets it can tune to, performs slightly better in this regard. However, since chunk-size variance is not a critical concern in the application for data synchronization, this may not be a substantial drawback.

and RAM both impose a horizon-based lower bound near the configured target, reducing the opportunity for very small chunks. Only AE consistently achieves low variance in our realistic workloads; RAM’s long upper tails remain pathological despite that lower bound.

C. Key Takeaways

Performance on Real-World Datasets: We find that all algorithms can be tuned to perform well on pseudorandom data, which often forms the basis for their theoretical analyses. On real-world data, however, we see mixed results, depending on the algorithm and dataset combination. Among the evaluated base chunking algorithms, AE is the most consistent across datasets, with Gear and SeqCDC also performing well on several metrics.

The results on synthetic and real-world datasets lead to the following conclusions about CDC chunk-size distributions: Chunk-Size Variance: Almost all algorithms produce many small chunks near an algorithm-defined minimum, followed by a heavy tail that moves the mean closer to the target. Rolling hash-based algorithms use relatively small windows and generally exhibit longer tails and greater variance. AE

0.7 0.7 0.6

0.8 0.6 0.4

Dedup. ratio

0.8

Dedup. ratio

0.9

0.8

Dedup. ratio

0.8 0.7 0.6 0.5

51 2 10 24 20 48 40 96 81 92

51 2 10 24 20 48 40 96 81 92

0.0

2 81 9

24

48 40 96

20

(b) DB

Buzhash

0.2

Target chunk size (B)

(a) VMB

AE

0.5

Target chunk size (B)

51

Target chunk size (B)

0.8

Target chunk size (B)

2

92

96

81

48

40

20

10

51

2

24

0.4 10

Dedup. ratio

0.9

FSC

(c) WEB

Gear

MII

PCI

(d) CODE

Rabin

RAM

SeqCDC

0.6 0.5

Mean chunk size (B)

FSC

Gear

0.2

PCI

Rabin

0

0

00 0 10

10

Mean chunk size (B)

(c) WEB

MII

00

00

0

00 30

00 10

Mean chunk size (B)

(b) DB

Buzhash

0.4

0.0

0 00 10

10

Mean chunk size (B)

(a) VMB

AE

00

0 10

0 00 10

00 30

10

30

00

0.4

0.6

10

0.4

0.7

00

0.6

0.8

10

0.5

0.8

Storage savings

0.6

Storage savings

Storage savings

0.7

0

Storage savings

Fig. 7: Deduplication ratios at configured targets; note that the y-axis scales differ between plots.

(d) CODE

RAM

SeqCDC

Fig. 8: Empirical mean chunk size and metadata-adjusted storage savings under 64 B metadata cost per emitted chunk. Each plot uses its own axis limits; x-axes are logarithmic; rings mark configurations nondominated among the evaluated points.

VII. D EDUPLICATION R ATIO The degree of achievable deduplication is a key metric for evaluating CDC algorithms. It determines how effectively an algorithm identifies and eliminates redundant data, thereby reducing storage requirements. We compare the selected algorithms by deduplication ratio and examine how dataset characteristics, such as compressibility and repeated byte patterns, relate to this metric. The deduplication performance of CDC algorithms is typically measured using the following metric: Dedup. ratio = 1 −

Sdedup , Soriginal

where Soriginal represents the original size of the dataset and Sdedup represents the deduplicated size, which is equivalent to the total size of unique chunks. The dedup. ratio indicates the fraction of storage space saved by eliminating redundant chunks. For instance, a deduplication ratio of 0.4 on a dataset of 1 GB indicates that the same dataset can be represented using 600 MB of unique emitted chunks. Note that this metric

excludes any metadata overhead. Moreover, in Table VIII, we show that achieved mean chunk sizes can deviate strongly from the configured target. Small chunks have implications on the potential storage savings as they produce greater metadata overhead. We therefore complement our study with Figure 8, which plots the metadata-adjusted storage savings against the achieved mean chunk size and highlights the Pareto frontier of measured configurations. For this figure, we employ the more practically oriented metric of storage savings: Storage savings = 1 −

Sdedup + βN , Soriginal

where N represents the total number of emitted chunks and β denotes the metadata cost per chunk. Fingerprint, indexing, and placement designs can produce different overheads. We model metadata overhead according to Debnath et al. [53] and assume 64 bytes per emitted chunk (i.e., β = 64): 20byte SHA-1 fingerprints with an additional 44 bytes to contain chunk length and location.

A. Results and Key Observations Deduplication ratios generally decline as the target chunk size grows (Figure 7). Rabin attains the highest ratios and the flattest curves, but this mostly reflects its unresponsiveness to the configured target. On DB its mean chunk size grows only from 95 B to 107 B as µ increases from 512 B to 8 KiB, and on CODE it reaches just 517 B at µ = 8192 (Table VIII). AE, RAM, and MII degrade faster because they reach larger targets by scaling a horizon or window (e.g., h = 7936 for AE at 8 KiB). This makes cut-points depend on longer stretches of content, so we expect the trend to continue beyond the tested range. MII’s curves change in a single step, since only w = 6 and w = 7 fall within our target range. FSC performs well because every target is a multiple of the 512-byte TAR block [54], and VM images are similarly block-organized. Fixed boundaries therefore often align with unchanged blocks across versions. RAM and PCI fail on CODE, where zero padding in block-aligned archives suppresses cut-points and inflates their mean chunk sizes to tens or hundreds of kilobytes. Plotting metadata-adjusted storage savings against the empirical mean chunk size removes Rabin’s apparent advantage (Figure 8). At 64 B per chunk, metadata alone costs 60– 67 % of the original size on DB, lowering Rabin’s worst-case savings to around 30 %. RAM and PCI fail in the opposite direction: their oversized chunks miss most redundancy, with storage savings very close to 0 on CODE. With the exception of FSC on DB, AE achieves both the highest best-case savings and the highest worst-case savings. Raw deduplication ratios thus favor algorithms that silently produce small chunks. Once granularity and metadata are accounted for, AE offers the most favorable and stable tradeoff, with Gear as the strongest hashbased alternative. VIII. D ISCUSSION We synthesize our results into guidance for selecting base chunking algorithms within the tested workloads and target range. Our comparisons isolate the base chunking algorithm; they do not rank composite algorithms or end-to-end deduplication systems, whose behavior also depends on size thresholds, normalization, caching, fingerprinting, and storage organization. A. Summary of Results Our benchmark indicates that traditional hash-based algorithms, such as Rabin and Gear, still offer competitive deduplication efficacy, even when accounting for achieved mean chunk sizes. However, we find that AE attains similar or better performance while closely adhering to the configured target chunk size and exhibiting low chunk-size variance. Our experiments show that, depending on the structure of the dataset, Rabin can produce pathologically small chunks. These yield impressive deduplication ratios, but once metadata overhead is accounted for, a different picture emerges (see Figures 8a and 8b). We also discussed in Section VII-A that AE’s deduplication may degrade when operating with target

TABLE IX: Summary of key success metrics, based on experiments configured at µ = 2 KiB. Superscripts identify every dataset attaining the extremum: C = CODE, W = WEB, V = VMB, D = DB. Bold: best; underline: second best. Algorithm

Rabin Buzhash Gear AE RAM PCI MII SeqCDC

Throughput

Chunk Sizes

Storage Savings

(MiB/s) ↑

Max. Err. ↓

Max. CV ↓

Min. ↑

Max. ↑

195 311 652 650 886 242 209 595

0.95D 0.69C 0.47D 0.12V 58.04C 10.03C 0.84C 0.82C

5.45D 30.59D 30.79D 0.31V 57.81C 195.44D 46.33D 34.11D

0.33D 0.60C 0.66C 0.71C 0.01C 0.09C 0.54C 0.53C

0.85W 0.85W 0.84W 0.89D 0.79D 0.74W 0.81W 0.83W

chunk sizes larger than those considered in our experiments, owing to the scaling-window problem. In those settings, Gear may represent a more robust alternative. Moreover, given the wide range of higher-level techniques that build upon hash-based algorithms, Gear remains an appealing choice for a variety of applications. RAM, which has the highest measured throughput on RAND at 2 KiB, proves sensitive to structured input: On highly compressible data, such as the source-code archives in CODE, the algorithm fails to find chunk boundaries, resulting in the generation of pathologically large chunks. MII and PCI were proposed specifically for data synchronization applications, where chunk-size variance is of lesser importance. Nevertheless, in our storage-oriented evaluation, we do not observe clear advantages over alternatives such as AE or Gear, which offer comparable or higher deduplication and throughput. Likewise, the more recently published SeqCDC shows no benefit in our evaluated settings over, for instance, Gear or AE. Table IX summarizes results at µ = 2 KiB with two measures of chunk-size calibration and variability: “Max. Err.” measures the maximum error |c̄−µ| across datasets; “Max. µ CV” measures the maximum coefficient of variation sc̄ across datasets. B. Contrasting Results with Literature While our study confirms many of the claims made by the original algorithms’ developers, we also encounter several discrepancies. These differences arise from factors such as dataset characteristics, experimental setups, and implementation details. We therefore contrast our results with those from the literature and reflect on their implications. AE: As shown in Section IV, the formula by which the parameterization in AE is derived does not reflect the actual behavior of the algorithm fully, but has been disseminated in this form throughout several studies [20], [21], [40], [41], [51], [52], and moreover, the open-source chunking algorithm evaluation platforms Destor [49] and DedupBench [26]. Following our report, DedupBench corrected its AE parameterization [50]. According to our own experiments on RAND, the previously established formula renders chunks 13 % smaller than the target when it is set to 512 B, and 39 % smaller

with a target of 8 KiB. Because smaller chunks can improve deduplication ratios while increasing chunk and metadata counts, earlier AE comparisons must be interpreted with this size shift in mind. The 13–39 % range quantifies the meansize deviation in our RAND experiments, not a bound on deduplication gains across other workloads. If a reported advantage could be explained by the size shift, the comparison remains unresolved without a re-evaluation controlling for empirical mean chunk size. We do not claim a ranking reversal: reproducing the affected studies would require their datasets, minimum/maximum constraints, fingerprinting, and other configuration details, and is outside our scope. In the original paper [40], the authors suggest that AE is superior to hash-based algorithms in terms of deduplication. While AE shows superior performance in some of our experiments and is competitive in most, its performance sometimes degrades with higher target chunk sizes. RAM: Our results show that RAM performs poorly on low-entropy datasets, most notably in the case of CODE (see Table VIII). The authors of RAM notice this flaw [15]; however, the full extent of this shortcoming was not evident from prior experiments. In their study, the authors evaluate RAM on high-entropy datasets that may not represent the lower-entropy inputs often encountered in data deduplication workloads. Indeed, deduplication is only evaluated in the form of “bytes saved per second”, which counterintuitively conflates throughput with deduplication. Moreover, the paper suggests chunk-size variances similar to AE, while none of our experiments on real-world datasets support this statement. Recently, Al Jarah et al. [25] evaluate the impact of low entropy with synthetic datasets. While imposing a maximum chunk size constraint, the authors quantify an algorithm’s robustness to low-entropy data by measuring the rate of artificial boundaries. Interestingly, in their study, RAM exhibits better robustness than Rabin or FastCDC, which stands in contrast to our results. This divergence may be explained by their reliance on synthetic datasets and the maximum chunk size constraint. IX. R ELATED W ORK Previous works have studied the state-of-the-art of data deduplication and chunking algorithms [6], [55], [56]. These studies primarily focus on theoretical discussions based on the original works that introduced the algorithms. Liu et al. [26] experimentally evaluate FSC, AE, Gear, and Rabin. Interestingly, their benchmark considers two AE configurations, with chunk boundaries determined by either local maxima (AEMax) or minima (AE-Min). AE-Min yields slightly higher deduplication efficacy than AE-Max. However, the authors only evaluate on a single dataset based on VM images. We argue that performance differences (on any metric) between AE-Max and AE-Min are most likely based on the dataset’s data distribution. We further note that their evaluation relied on an incorrect formula for the AE window size, resulting in an average chunk size nearly half of the expected value (see Section IV-B). Most other experimental evaluations and comparisons of chunking algorithms are part of works introducing

new algorithms [15], [31], [40], [51]. These works do not provide a consistent set of datasets or comparable evaluation methodologies for judging the algorithms against one another. For example, Manogar and Abirami [51] present the superior throughput of their algorithm. In their measurements, however, they do not isolate the effects of the chunking algorithm from the computationally expensive SHA-1 fingerprinting of the produced chunks. Consequently, the resulting throughput is heavily skewed in favor of algorithms that generate a lower number of chunks. Notably, their own algorithm produces the fewest chunks across all evaluated algorithms and datasets. The authors of PCI [31] compare their algorithm against Rabin, LMC, AE, RAM, and MII. The datasets used in the experiments are artificial, based on sequences of zeros with random byte insertions or deletions in defined intervals. In practice, chunking algorithms are applied to real-world data, which is not reflected in the datasets used by the authors. For instance, the issue of low-entropy strings is disregarded within this experiment. Recently, Al Jarah et al. [25] benchmark AE, FastCDC, Rabin, and RAM on synthetic datasets simulating low-entropy data. Interestingly, using our methodology, we reach different conclusions, which we briefly discuss in Section VIII-B. Viji and Revathy [57] compare specifically the throughput of Rabin, LMC, AE, RAM, and PCI on random datasets. In their experiment, RAM significantly outperforms the other algorithms, followed by AE and PCI; our experimental study confirms this ordering on random data. X. C ONCLUSION We showed that CDC algorithms are best understood and evaluated modularly: a base algorithm supplies the cut-point rule, while high-level techniques such as normalization, size thresholds, caching, and skipping change its operating envelope. By isolating this base layer, benchmarking eight algorithms on realistic backup-oriented datasets, and calibrating parameters on uniformly random data before freezing them for realistic workloads, we expose effects that prior composite evaluations obscure. We correct a widely propagated AE parameterization error, derive tuning rules for RAM and MII, and show that behavior on uniformly random data does not necessarily transfer to realistic workloads. Within the evaluated workloads and target range, AE is the most robust of the tested base chunking algorithms, Gear remains a strong hash-based choice, RAM is fast but fragile on low-entropy inputs, and Buzhash, MII, PCI, and SeqCDC offer limited advantages for storage-oriented deduplication. We hope that our framework supports future advances in CDC algorithms and enables more systematic evaluations of high-level techniques under the same modular discipline. ACKNOWLEDGMENTS The authors thank Asterios Katsifodimos for his valuable feedback and support. This work has been partly funded by the Dutch National NWO/TKI Science Grant BLOCK.2019.004 and the Federal Ministry of Research, Technology and Space of Germany within the project “Open6GHub+” (grant number:

16KIS2407). Generative AI tools were used to improve the linguistic clarity and quality of the manuscript and to assist in writing R code for visualizing existing data. No scientific content, software, results, or conclusions were generated using AI. All content was reviewed and verified by the authors. R EFERENCES [1] A. Wright, G. Ireland, and E. Burns. (2025, October) Content creation in the age of generative ai: Implications for value and scale. Accessed: 2026-06-08. [Online]. Available: https://www.seagate.com/content/dam/seagat e/assets/resources/How-Generative-AI-Is-Transformin g-Content-Creation-and-Data-Value-/files/US5381762 5-WP.pdf [2] D. Reinsel, J. Gantz, and J. Rydning. (2018) Data age 2025: The digitization of the world from edge to core. Accessed on 2025-03-17. [Online]. Available: https://www.seagate.com/files/www-content/our-story/t rends/files/idc-seagate-dataage-whitepaper.pdf [3] X. Peng, X. Fan, S. Cheng, L. Meng, C. Fu, W. Zhou, and C. Weng, “Bbs: Batch-based snapshot for the cloud database backup,” in 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 2025, pp. 4248–4261. [4] A. Muthitacharoen, B. Chen, and D. Mazières, “A low-bandwidth network file system,” in Proceedings of the 18th ACM Symposium on Operating System Principles, SOSP 2001, Chateau Lake Louise, Banff, Alberta, Canada, October 21-24, 2001, K. Marzullo and M. Satyanarayanan, Eds. ACM, 2001, pp. 174–187. [Online]. Available: https://doi.org/10.1145/502034.502 052 [5] S. Quinlan and S. Dorward, “Venti: A new approach to archival data storage,” in Conference on File and Storage Technologies (FAST 02). Monterey, CA: USENIX Association, Jan 2002. [Online]. Available: https://www.usenix.org/conference/fast-02/venti-new-a pproach-archival-data-storage [6] W. Xia, H. Jiang, D. Feng, F. Douglis, P. Shilane, Y. Hua, M. Fu, Y. Zhang, and Y. Zhou, “A comprehensive study of the past, present, and future of data deduplication,” Proceedings of the IEEE, vol. 104, no. 9, pp. 1681–1710, 2016. [7] D. T. Meyer and W. J. Bolosky, “A study of practical deduplication,” ACM Transactions on Storage (ToS), vol. 7, no. 4, pp. 1–20, 2012. [8] A. El-Shimi, R. Kalach, A. Kumar, A. Ottean, J. Li, and S. Sengupta, “Primary data deduplication - large scale study and system design,” in Proceedings of the 2012 USENIX Annual Technical Conference, USENIX ATC 2012, Boston, MA, USA, June 13-15, 2012, G. Heiser and W. C. Hsieh, Eds. USENIX Association, 2012, pp. 285–296. [Online]. Available: https://www.usenix.org/c onference/atc12/technical-sessions/presentation/el-shimi [9] G. Wallace, F. Douglis, H. Qian, P. Shilane, S. Smaldone, M. Chamness, and W. Hsu, “Characteristics of backup

workloads in production systems,” in Proceedings of the 10th USENIX conference on File and Storage Technologies, FAST 2012, San Jose, CA, USA, February 14-17, 2012, W. J. Bolosky and J. Flinn, Eds. USENIX Association, 2012, p. 4. [Online]. Available: https://www.usenix.org/conference/fast12/characteristics -backup-workloads-production-systems [10] L. Xu, A. Pavlo, S. Sengupta, and G. R. Ganger, “Online deduplication for databases,” in Proceedings of the 2017 ACM International Conference on Management of Data, 2017, pp. 1355–1368. [11] A. Wildani, E. L. Miller, and O. Rodeh, “Hands: A heuristically arranged non-backup in-line deduplication system,” in 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 2013, pp. 446–457. [12] F. Ni, X. Lin, and S. Jiang, “Ss-cdc: A two-stage parallel content-defined chunking for deduplicating backup storage,” in Proceedings of the 12th ACM Intl Conf on Systems and Storage, 2019, pp. 86–96. [13] S. Udayashankar, A. Baba, and S. Al-Kiswany, “Seqcdc: Hashless content-defined chunking for data deduplication,” in Proceedings of the 25th International Middleware Conference, MIDDLEWARE 2024, Hong Kong, SAR, China, December 2-6, 2024, J. Cao, Z. Jin, V. Schiavoni, and J. Edinger, Eds. ACM, 2024, pp. 292–298. [Online]. Available: https://doi.org/10.1145/3652892.3700766 [14] W. Xia, Y. Zhou, H. Jiang, D. Feng, Y. Hua, Y. Hu, Q. Liu, and Y. Zhang, “Fastcdc: a fast and efficient content-defined chunking approach for data deduplication,” in Proceedings of the 2016 USENIX Annual Technical Conference, USENIX ATC 2016, Denver, CO, USA, June 22-24, 2016, A. Gulati and H. Weatherspoon, Eds. USENIX Association, 2016, pp. 101–114. [Online]. Available: https://www.usenix.o rg/conference/atc16/technical-sessions/presentation/xia [15] R. N. S. Widodo, H. Lim, and M. Atiquzzaman, “A new content-defined chunking algorithm for data deduplication in cloud storage,” Future Gener. Comput. Syst., vol. 71, pp. 145–156, 2017. [Online]. Available: https://doi.org/10.1016/j.future.2017.02.013 [16] Z. Xu and W. Zhang, “Quickcdc: A quick content defined chunking algorithm based on jumping and dynamically adjusting mask bits,” in 2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), New York City, NY, USA, September 30 - Oct. 3, 2021. IEEE, 2021, pp. 288–299. [Online]. Available: https://doi.org/10.1109/IS PA-BDCloud-SocialCom-SustainCom52081.2021.00049 [17] E. Kruus, C. Ungureanu, and C. Dubnicki, “Bimodal content defined chunking for backup streams.” in Fast, 2010, pp. 239–252. [18] G. Lu, Y. Jin, and D. H. Du, “Frequency based chunking for data de-duplication,” in 2010 IEEE International

Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. IEEE, 2010, pp. 287–296. [19] B. Romanski, L. Heldt, W. Kilian, K. Lichota, and C. Dubnicki, “Anchor-driven subchunk deduplication,” in Proceedings of of SYSTOR 2011: The 4th Annual Haifa Experimental Systems Conference, Haifa, Israel, May 30 - June 1, 2011. ACM, 2011, p. 16. [Online]. Available: https://doi.org/10.1145/1987816.1987837 [20] W. Xia, X. Zou, H. Jiang, Y. Zhou, C. Liu, D. Feng, Y. Hua, Y. Hu, and Y. Zhang, “The design of fast content-defined chunking for data deduplication based storage systems,” IEEE Trans. Parallel Distributed Syst., vol. 31, no. 9, pp. 2017–2031, 2020. [Online]. Available: https://doi.org/10.1109/TPDS.2020.2984632 [21] Y. Zhang, D. Feng, H. Jiang, W. Xia, M. Fu, F. Huang, and Y. Zhou, “A fast asymmetric extremum content defined chunking algorithm for data deduplication in backup storage systems,” IEEE Trans. Computers, vol. 66, no. 2, pp. 199–211, 2017. [Online]. Available: https://doi.org/10.1109/TC.2016.2595565 [22] K. Eshghi and H. K. Tang, “A framework for analyzing and improving content-based chunking algorithms,” Hewlett-Packard Labs Technical Report TR, vol. 30, no. 2005, 2005. [23] W. Xia, H. Jiang, D. Feng, L. Tian, M. Fu, and Y. Zhou, “Ddelta: A deduplication-inspired fast delta compression approach,” Perform. Evaluation, vol. 79, pp. 258–272, 2014. [Online]. Available: https://doi.org/10.1016/j.peva.2014.07.016 [24] S. Udayashankar, A. Baba, and S. Al-Kiswany, “Vectorcdc: Accelerating data deduplication with vector instructions,” in 23rd USENIX Conference on File and Storage Technologies, FAST 2025, Santa Clara, CA, February 25-27, 2025, H. S. Gunawi and V. Tarasov, Eds. USENIX Association, 2025, pp. 513–522. [Online]. Available: https://www.usenix.org/conference/fast25/pre sentation/udayashankar [25] M. A. Jarah, S. Udayashankar, A. Baba, and S. AlKiswany, “The impact of low-entropy on chunking techniques for data deduplication,” in 17th IEEE International Conference on Cloud Computing, CLOUD 2024, Shenzhen, China, July 7-13, 2024. IEEE, 2024, pp. 134–140. [Online]. Available: https://doi.org/10.110 9/CLOUD62652.2024.00025 [26] A. Liu, A. Baba, S. Udayashankar, and S. AlKiswany, “Dedupbench: A benchmarking tool for data chunking techniques,” in IEEE Canadian Conference on Electrical and Computer Engineering, CCECE 2023, Regina, SK, Canada, September 24-27, 2023. IEEE, 2023, pp. 469–474. [Online]. Available: https: //doi.org/10.1109/CCECE58730.2023.10288834 [27] F. Ni and S. Jiang, “Rapidcdc: Leveraging duplicate locality to accelerate chunking in cdcbased deduplication systems,” in Proceedings of the ACM Symposium on Cloud Computing, SoCC

2019, Santa Cruz, CA, USA, November 20-23, 2019. ACM, 2019, pp. 220–232. [Online]. Available: https://doi.org/10.1145/3357223.3362731 [28] P. Zhou, Z. Wang, W. Xia, and H. Zhang, “Ultracdc:a fast and stable content-defined chunking algorithm for deduplication-based backup storage systems,” in IEEE International Performance, Computing, and Communications Conference, IPCCC 2022, Austin, TX, USA, November 11-13, 2022. IEEE, 2022, pp. 298–304. [Online]. Available: https://doi.org/10.1109/IPCCC55026.2022.9894295 [29] B. Wan, L. Pu, X. Zou, S. Li, P. Wang, and W. Xia, “Supercdc: A hybrid design of high-performance content-defined chunking for fast deduplication,” in IEEE 40th International Conference on Computer Design, ICCD 2022, Olympic Valley, CA, USA, October 23-26, 2022. IEEE, 2022, pp. 170–178. [Online]. Available: https://doi.org/10.1109/ICCD56317.2022.00034 [30] C. Zhang, D. Qi, Z. Cai, W. Huang, X. Wang, W. Li, and J. Guo, “MII: A novel content defined chunking algorithm for finding incremental data in data synchronization,” IEEE Access, vol. 7, pp. 86 932– 86 945, 2019. [Online]. Available: https://doi.org/10.110 9/ACCESS.2019.2926195 [31] C. Zhang, D. Qi, W. Li, and J. Guo, “Function of content defined chunking algorithms in incremental synchronization,” IEEE Access, vol. 8, pp. 5316–5330, 2020. [Online]. Available: https://doi.org/10.1109/ACCE SS.2019.2963625 [32] J. D. Cohen, “Recursive hashing functions for n-grams,” ACM Trans. Inf. Syst., vol. 15, no. 3, pp. 291–320, 1997. [Online]. Available: https://doi.org/10.1145/2561 63.256168 [33] M. O. Rabin, “Fingerprinting by random polynomials,” Technical report, 1981. [34] R. M. Karp and M. O. Rabin, “Efficient randomized pattern-matching algorithms,” IBM J. Res. Dev., vol. 31, no. 2, pp. 249–260, 1987. [Online]. Available: https: //doi.org/10.1147/rd.312.0249 [35] A. Z. Broder, “Some applications of rabin’s fingerprinting method,” in Sequences II. Springer, 1993, pp. 143– 152. [36] S. Schleimer, D. S. Wilkerson, and A. Aiken, “Winnowing: Local algorithms for document fingerprinting,” in Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, A. Y. Halevy, Z. G. Ives, and A. Doan, Eds. ACM, 2003, pp. 76–85. [Online]. Available: https://doi.org/10.1145/872757.872770 [37] A. Tridgell, P. Mackerras et al., “The rsync algorithm,” 1996. [38] A. Anand, C. Muthukrishnan, A. Akella, and R. Ramjee, “Redundancy in network traffic: findings and implications,” in Proceedings of the Eleventh International Joint Conference on

Measurement and Modeling of Computer Systems, SIGMETRICS/Performance 2009, Seattle, WA, USA, June 15-19, 2009, J. R. Douceur, A. G. Greenberg, T. Bonald, and J. Nieh, Eds. ACM, 2009, pp. 37–48. [Online]. Available: https://doi.org/10.1145/1555349.1555355 [39] N. S. Bjørner, A. Blass, and Y. Gurevich, “Contentdependent chunking for differential compression, the local maximum approach,” J. Comput. Syst. Sci., vol. 76, no. 3-4, pp. 154–203, 2010. [Online]. Available: https://doi.org/10.1016/j.jcss.2009.06.004 [40] Y. Zhang, H. Jiang, D. Feng, W. Xia, M. Fu, F. Huang, and Y. Zhou, “AE: an asymmetric extremum content defined chunking algorithm for fast and bandwidth-efficient data deduplication,” in 2015 IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015. IEEE, 2015, pp. 1337–1345. [Online]. Available: https://doi.org/10.1109/INFOCOM.2015.7218510 [41] X. Jin, H. Liu, C. Ye, X. Liao, H. Jin, and Y. Zhang, “Accelerating content-defined chunking for data deduplication based on speculative jump,” IEEE Trans. Parallel Distributed Syst., vol. 34, no. 9, pp. 2568–2579, 2023. [Online]. Available: https: //doi.org/10.1109/TPDS.2023.3290770 [42] Y. Won, K. Lim, and J. Min, “Much: Multithreaded content-based file chunking,” IEEE Transactions on Computers, vol. 64, no. 5, pp. 1375–1388, 2014. [43] P. Bhatotia, R. Rodrigues, and A. Verma, “Shredder: Gpu-accelerated incremental storage and computation,” in Proceedings of the 10th USENIX conference on File and Storage Technologies, FAST 2012, San Jose, CA, USA, February 14-17, 2012, W. J. Bolosky and J. Flinn, Eds. USENIX Association, 2012, p. 14. [Online]. Available: https://www.usenix.org/conference/fast12/shr edder-gpu-accelerated-incremental-storage-and-computa tion [44] B. Zhou and J. Wen, “Hysteresis re-chunking based metadata harnessing deduplication of disk images,” in 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, October 1-4, 2013. IEEE Computer Society, 2013, pp. 389–398. [Online]. Available: https://doi.org/10.1109/ICPP.2013.48 [45] D. Bobbarjung, C. Dubnicki, and S. Jagannathan, “Fingerdiff: Improved duplicate elimination in storage systems,” Proc. Mass Storage Syst. Technol, pp. 1–5, 2006. [46] B. Chapuis, B. Garbinato, and P. Andritsos, “Throughput: A key performance measure of content-defined chunking algorithms,” in 36th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS Workshops, Nara, Japan, June 27-30, 2016. IEEE Computer Society, 2016, pp. 7–12. [Online]. Available: https://doi.org/10.1109/ICDCSW.2016.32 [47] S. T. Leutenegger and D. Dias, “A modeling study of the tpc-c benchmark,” ACM Sigmod Record, vol. 22, no. 2, pp. 22–31, 1993. [48] D. Lemire. (2023) Are your memory-bound benchmark-

ing timings normally distributed? https://lemire.me/blog /2023/04/06/, visited 2024-08-25. [Online]. Available: https://lemire.me/blog/2023/04/06/are-your-memory-bou nd-benchmarking-timings-normally-distributed/ [49] M. Fu, D. Feng, Y. Hua, X. He, Z. Chen, W. Xia, Y. Zhang, and Y. Tan, “Design tradeoffs for data deduplication performance in backup workloads,” in Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16-19, 2015. USENIX Association, 2015, pp. 331–344. [Online]. Available: https://www.usenix.org/conference/fast15/technical-sessi ons/presentation/fu [50] “AE does not yield expected chunk size - Issue #37,” https://github.com/UWASL/dedup- bench/issues/37, 2024, [Accessed 04-09-2025]. [51] E. Manogar and S. Abirami, “Dynamic prime chunking algorithm for data deduplication in cloud storage,” KSII Transactions on Internet Information Systems, vol. 15, no. 4, pp. 1342–1359, 2021. [Online]. Available: https://doi.org/10.3837/tiis.2021.04.009 [52] E. Manogar and A. Murugappan, “A smart hybrid content-defined chunking algorithm for data deduplication in cloud storage,” Soft Comput., vol. 28, no. 15-16, pp. 9037–9052, 2024. [Online]. Available: https://doi.org/10.1007/s00500-023-09290-7 [53] B. K. Debnath, S. Sengupta, and J. Li, “Chunkstash: Speeding up inline storage deduplication using flash memory,” in Proceedings of the 2010 USENIX Annual Technical Conference, USENIX ATC 2010, Boston, MA, USA, June 23-25, 2010, P. Barham and T. Roscoe, Eds. USENIX Association, 2010. [54] “GNU tar 1.35: Basic Tar Format — gnu.org,” https://ww w.gnu.org/software/tar/manual/html_node/Standard.html, [Accessed 18-03-2025]. [55] A. Goel and C. Prabha, “A detailed review of data deduplication approaches in the cloud and key challenges,” in 2023 4th International Conference on Smart Electronics and Communication (ICOSEC). IEEE, 2023, pp. 1771– 1779. [56] Y. Fu, J. Su, J. Ning, J. Wu, Y. Lu, and N. Xiao, “Distributed data deduplication for big data: A survey,” ACM Computing Surveys, 2025. [57] D. Viji and D. Revathy, “Comparative analysis for content defined chunking algorithms in data deduplication,” Webology, vol. 18, no. SpecialIssue2, pp. 255–268, 2021.

·10−2

Definition 1. In AE, i + h marks a cut-point if it is the first position for which Bi ≥ max{Bj }i+h j=i+1 . In order for any byte Bi at position i to become subject to the matching condition, all previous bytes Bj<i must have failed the matching condition Bj ≥ max{Bk }j+h k=j+1 . However, these are not independent events. The event Bi−1 < max{Bj }i+h−1 influences the expectation of Bi , . . . , Bi+h , j=i and therefore affects the probability Bi < max{Bj }i+h j=i+1 . So does every previous condition back to Bi−h−1 < max{Bj }ij=i−h , as it influences the expected value of Bi . This leads to a chain of recursive conditional probabilities that we express as

For the purpose of readability, we introduce the abbreviation Mh := max{Bi }hi=1 to denote the maximum value among h bytes. As we are assuming uniformly distributed random data, and bytes are discrete variables in [0, 255], the probability for any byte X to take any value 0 ≤ x ≤ 255 is P (X = x) = x , P (X ≥ x) = 256−x 1/256. Furthermore, P (X < x) = 256 256 , 257 1 P (X < Y ) = 2 , and P (X ≤ Y ) = 512 . Lemma 1. The cumulative distribution function FM (m) = P(max{Bi }hi=1 ≤ m) follows h  m+1 FMh (m) = P(B1 ≤ m ∧ . . . Bh ≤ m) = 256 for 0 ≤ m ≤ 255 and can be used to express the probability mass function of Mh : P(Mh = m) = FMh (m) − FMh (m − 1) h   m h m+1 − = 256 256

2 0

m−x+1 256 − x

h

 −

m−x 256 − x

m

200

The practical implication of this is that when AE is used with target chunk sizes beyond 2 KB, the approximation that Mh ≈ 255 can be used to simplify the problem to P(i + h is cut-point) = P(Bi = 255) =

1 . 256

On average, therefore, a chunk cut-point will be found after the evaluation of 256 bytes. Hence, target chunk size for AE is µ ≈ h + 256 for large values of h; the parameterization is determined by h ≈ µ − 256. We continue with extended calculations for small target chunk sizes. The probability for a random byte to fail the matching condition is

P(X < max{Bi }hi=1 ) =

255 X

P(X < m)·P(max{Bi }hi=1 = m).

m=0

The probability in this form would apply to the first byte of the sequence, i.e., it is equivalent to P(B1 < max{Bi }h+2 i=2 ). The second byte B2 , which only gets evaluated under the pre-condition that B1 < max{Bi }h+1 i=2 , faces the same condition as its precursor, but has a different probability as it is conditioned: h+1 P(B2 < max{Bi }h+2 i=3 | B1 < max{Bi }i=2 )

(4) =

255 X

P(B2 = x | B1 < max{Bi }h+1 i=2 )·

x=0 h+1 P(x < max{Bi }h+2 i=3 | B1 < max{Bi }i=2 )

= 

100

Fig. 9: Probability mass function for Mh . Note, m is discrete; line plots were chosen for readability. As h increases, the expected value for Mh converges to 255.

for 0 ≤ m ≤ 255. Further, a lower bound x changes this distribution to

P(Mh = m | Mh ≥ x) =

h=4 h=8 h=16

4

0

P(i + h marks cut-point) = P(Bi ≥ max{Bj }i+h j=i+1 | Bi−1 < max{Bj }i+h−1 ∧ . . . ∧ Bi−h−1 < max{Bj }ij=i−h )· j=i h+1 . . . · P(B2 < max{Bj }h+2 j=3 | B1 < max{Bj }j=2 )· P(B1 < max{Bj }h+1 j=2 ).

6

P (Mh = m)

A PPENDIX A S TOCHASTIC A NALYSIS OF AE

h

for 0 ≤ m ≤ 255 and 0 ≤ x ≤ 255. Intuitively, as h increases, the probability of observing small values of Mh diminishes, since more bytes contribute to the maximum. We illustrate this in Figure 9. Further, limh→∞ E(Mh ) = 255. For instance, with h = 2000, P(Mh = 255) > 0.999. That is, P(Mh = m | Mh ≥ x) ≥ P(Mh = m) for any 0 ≤ x ≤ 255.

255 X

(5)

P(B2 = x | B1 < max{Bi }h+1 i=2 )·

x=0 255 X

! h+1 P(max{Bi }h+2 i=3 = m | B1 < max{Bi }i=2 )

m=x+1

The expectation of B2 and the expectation of max{Bi }h+2 i=3 are shifted towards higher values, given that B1 < max{Bi }h+1 i=2 . The two conditional probabilities needed to solve (5) are less trivial. We are deriving P(B2 = x | B1 < max{Bi }h+1 i=2 ) using Bayes’ formula, which transforms the expression to

P(B1 < max{Bi }h+1 i=2 | B2 = x) · P(B2 = x) . P(B1 < max{Bi }h+1 i=2 )

A PPENDIX B S TOCHASTIC A NALYSIS OF RAM (6)

We derive the inversed conditional probability P(B1 < max{Bi }h+1 i=2 | B2 = x) in the following lemma. Lemma 2. The probability of a byte B1 being smaller than the maximum value among the h bytes in its horizon, given that one of the bytes B2 is known, can be expressed as h+1 P(x ≥ max{Bi }h+1 i=3 ) · P(B1 < x) ⊕ P(max{Bi }i=3 > x) h+1 ·P(B1 < max{Bi }h+1 i=3 ) | max{Bi }i=3 > x) (7)

Proof. Given B2 = x, we know that max{Bi }h+1 i=2 ≥ x. That is, either x is the maximum in this horizon and x ≥ h+1 max{Bi }h+1 i=3 , or the remaining bytes are max{Bi }i=3 > x. Lemma 3. The probability distribution for the maximum value among h bytes, given that the preceding byte is smaller than the maximum value in its horizon, can be expressed as h+1 P(max{Bi }h+2 i=3 = m | B1 < max{Bi }i=2 ),

which can be evaluated as P(B3 = m ∧ Bj ≤ m ∀j ∈ [4, h + 1] | B1 < max{Bi }h+1 i=2 )· (h − 1) · P(Bh+3 ≤ m)+ h−1 P(Bh+3 = m) · P(B3 ≤ m | B1 < max{Bi }h+1 i=2 ) (8)

Proof. The expectation about a subset of bytes {Bi }h+2 i=3 ∩ h+1 {Bi }h+1 = {B } is influenced by the given condition, i i=3 i=2 i.e., all bytes in the target sequence except for its final byte Bh+2 . Intuitively, one byte will be m while the remaining h−1 bytes of the intersecting horizon are ≤ m. By multiplying the chance for one of these bytes by h − 2, we account for every byte in the intersecting horizon to be in place of the maximum value. In the formula, we used B3 as an arbitrary placeholder, as any byte in the affected sequence yields identical chances. Simultaneously, we also verify that the final (non-intersecting) byte Bh+3 ≤ m. Finally, we account for the case that the final byte Bh+3 = m and all bytes in the conditioned sequence ≤ m. Evaluating (5) using Lemmas 2 and 3 accumulates six hierarchies of sum-loops. The complexity further depends on the size of h. Even with low values for h, the evaluation turns out too computationally expensive (we interrupted the execution after two hours). Therefore, we deem exact analytical solutions impractical. We recommend an experimental approach for tuning h for low target chunk sizes, and making use of the approximation h ≈ µ − 256 for target chunk sizes beyond 2 KB.

Definition 2. Let B1 , B2 , . . . be independent bytes uniformly distributed on {0, . . . , 255}, and let h ≥ 1 be an integer. RAM fixes Mh = max{B1 , . . . , Bh } and cuts after the first subsequent byte at least as large as Mh . Thus T = min{t ≥ 1 : Bh+t ≥ Mh } and the chunk length is L = h + T . Conditional on Mh = m, each subsequent byte succeeds with probability pm = (256 − m)/256, independently of the preceding subsequent bytes. Hence T | Mh = m is geometric on {1, 2, . . .}, with E[T | Mh = m] =

256 1 = . pm 256 − m

(9)

Averaging over the maximum distribution in (4) gives a mixture of geometric waiting times:   µ(h) = h + E E[T | Mh ] " # h  255 X (10) m h 256 m+1 =h+ − . 256 − m 256 256 m=0 The benchmark horizons were selected using the approximation in Equation (2). This approximation takes the reciprocal of the average success probability, rather than averaging the conditional waiting times. By convexity, Jensen’s inequality gives E[1/pMh ] ≥ 1/E[pMh ]; thus (2) underestimates (1). For horizons 327 and 780 the differences are approximately 32 B and 6 B, respectively. Solving (2) and rounding gives the benchmark horizons 327, 780, 1792, 3840, 7936 for targets 512, 1024, 2048, 4096, 8192 bytes, respectively. At the two smallest targets, both the exact-model predictions and the measured RAND means round to 544 B and 1030 B, respectively (Table VIII). Minimizing |µ(h) − µ| over positive integer horizons for each configured target µ instead selects 300 and 774 for the two smallest targets and the same benchmark horizons for the three larger targets; these are calculated parameter choices, not additional measurements. Strictly increasing means permit binary search, with the smaller horizon selected on ties. Finally, Pr[Mh = 255] = 1 − (255/256)h → 1 implies E[T ] → 256 and µ(h) ≈ h + 256. At h = 1792, this approximation differs from the exact mean by less than 1 B. Relating this IID model to measurements also requires accounting for implementation-specific boundary indexing and terminal chunks.

Related documents

• Benchmarking Content-Defined Chunking Algorithms for Data Deduplication#1298200
• SnapShare: Isolation-Preserving Deduplication for Serverless Snapshots#1297670
• SnapShare: Isolation-Preserving Deduplication for Serverless Snapshots#1291774
• Lower Layer Guidelines for Robust RTP/UDP/IP Header Compression#208907
• RObust Header Compression (ROHC): Requirements and Assumptions for 0-byte IP/UDP/RTP Compression#132727