Deduplication ratio does not predict restore cost

11 October 2026 / Literature review and synthetic trace

Two layouts containing the same chunks can require different numbers of reads to restore the same bytes. In our six-request example, changing locality doubles fetched bytes with a two-container cache. This is an accounting result, not a measured slowdown.

The overlooked cost is reconstructing the stream

Lillibridge and colleagues model restore from a recipe of chunk references. Reused chunks stay in older containers, so logical order need not match physical grouping. Their 2013 study uses a simulator, a workgroup collection and a synthetic stress workload. Its speed factor is an I/O proxy, not directly measured seconds. [1, sections 2 and 4]

Fu and colleagues distinguish sparse containers, which contribute little useful data, from out-of-order containers revisited after eviction. Cache can help the latter without eliminating the former. Their evaluation includes VM backups, Linux source versions and synthetic data. The default comparison uses OPT caching, not LRU, with a memory-resident fingerprint index. [2, sections 4 and 6]

Same six chunks, different container visits

Hesela's model restores distinct chunks 1 through 6 in that order, each 4 KiB. There are three 64 KiB containers, A, B and C. Each holds two requested chunks plus 56 KiB of other data not needed by this restore. Both layouts therefore have the same 24 KiB output and 192 KiB of occupied containers. Only placement changes.

Clustered placement maps the six chunks to A A B B C C. Interleaved placement maps them to A B C A B C. The letters identify containers, not duplicate chunk contents. This is not a comparison between a deduplicated and a non-deduplicated backup.

Computed from the downloadable model. Cold LRU cache; every miss fetches one whole 64 KiB container; 1 KiB = 1,024 bytes. Amplification = fetched bytes / restored bytes.
Layout	Cache slots	Reads	Fetched KiB	Restored KiB	Amplification
clustered	1	3	192	24	8x
clustered	2	3	192	24	8x
clustered	3	3	192	24	8x
interleaved	1	6	384	24	16x
interleaved	2	6	384	24	16x
interleaved	3	3	192	24	8x

At two slots, the clustered layout reads each container once: three reads, 192 KiB, an 8x byte ratio. Interleaving makes all six requests miss: six reads, 384 KiB, a 16x ratio. A deduplication ratio cannot encode this order-dependent difference.

Three slots retain all three containers and remove the extra reads. The ratio remains 8x: each first fetch still contains only 8 KiB needed by this restore. More cache does not make those initial 56 KiB disappear. A warm cache, smaller range reads or a different layout would change the problem and must be reported as different assumptions.

Why every interleaved request misses

The two-slot cache starts empty. Its oldest entry is evicted when a new container arrives; a hit would refresh recency. The order below is least to most recently used.

Chunk 1: container A, miss; cache A.
Chunk 2: container B, miss; cache A B.
Chunk 3: container C, miss; cache B C.
Chunk 4: container A, miss; cache C A.
Chunk 5: container B, miss; cache A B.
Chunk 6: container C, miss; cache B C.

The fourth request needs A, but C has already displaced it. Fetching A displaces B, just before B is needed again. Counting only the three unique containers would miss this repeated traffic.

Six-row CSV, JSON provenance and dependency-free reproduction code. The article's table and trace are generated from the same model at build time.

Improving locality has a price

Container capping limits references to old containers within a segment by writing some duplicate chunks again. A forward assembly area instead places needed chunks into a buffer in future output order. These are different interventions: one trades space for locality, the other changes restore buffering. [1, section 3]

History-aware rewriting uses information from earlier backups to identify sparse containers for later rewriting. The assumed similarity between successive backups matters; it is not a universal guarantee for unrelated data. [2, section 5]

Our model implements none of those algorithms. It isolates the baseline read cost that an optimization would need to improve. We do not infer a capping threshold, rewrite budget or RAM requirement for a production system from six requests.

What the numbers do not say

No backup appliance, HDD, SSD or object store was measured. The model has no seek cost, bandwidth, parallelism, decompression, output-write time, metadata I/O, prefetching, deduplication index or operating-system cache. A 16x fetched-byte ratio is not a 16x elapsed-time multiplier. Deterministic examples have no sample size or confidence interval.

Deduplication shares content within an implementation's matching scope; it does not specify physical replica count. Logical references are not independent recovery copies. Nor is this trace a durability or corruption model. See the separate integrity-boundary analysis.

For a useful restore test, Hesela recommends recording restored logical bytes, fetched bytes at a named layer, cache state and budget, restore-point age, concurrent streams and elapsed time to usable output. Hold these conditions fixed when comparing layouts. Storage savings and recovery completion belong in separate columns.

Corpus: deduplication, chunk fragmentation, container capping and forward assembly area.

Primary sources

Sources reviewed 11 October 2026. Historical methods, not a claim about current products. No paper benchmark has been reproduced here.