Incremental Backup Chains and Restore Depth

Backing up a terabyte every night is not possible for most systems, so backup software stores one complete copy and then a series of changes. The vocabulary that describes the result is borrowed from tape, where a full backup was followed by differential and incremental dumps, and the vocabulary hides a structural property that matters more than the storage saving: each backup after the first is a function of its predecessors, and it cannot be restored without them.

That dependency is the whole design. It determines how much a restore costs, how much damage a single corrupt file does, and what a retention policy actually deletes.

Two shapes of chain with the same name

A differential backup contains everything changed since the last full backup. A chain of differentials is flat: each one depends on the full and on nothing else, so a restore needs two members regardless of how many differentials exist. The cost is that each differential grows with the time since the full.

An incremental backup contains everything changed since the last backup of any kind. A chain of incrementals is linear: the fifth depends on the fourth, which depends on the third, and so on back to the full. Each member is small, and a restore needs the entire chain.

Most modern systems use the second shape because the backup window is the binding constraint, then add a mechanism to bound the depth. The depth is usually not a storage decision. It is a decision about how long a restore is allowed to take, expressed in a different unit.

Formally, the chain is a directed acyclic graph and in practice a path. That matters for one failure mode that is often overlooked: the graph is only a path if each link records its parent, and the parent is identified by something that survives renaming. A chain whose links are identified by timestamp alone breaks when two backups share a timestamp or when the clock moves backwards during a daylight-saving transition or an NTP correction.

Finding changed blocks without reading everything

The cost of an incremental is dominated by how the software discovers what changed, not by how much it stores.

At the block layer, a device mapper target can track writes per region, and a hypervisor’s changed-block tracking does the same for a virtual disk. The tracking granularity is typically a bitmap with one bit per fixed-size region, often 64 KiB, which bounds the resolution: a single 512-byte write dirties a 64 KiB region, and the backup reads and stores the whole region. The bitmap must be reset after each backup, and the reset is the point at which a failed backup becomes expensive, because a backup that dies after reading half the bitmap has already committed to those regions being clean.

At the filesystem layer, a snapshot diff compares two snapshots’ metadata. ZFS and btrfs can enumerate the blocks or extents that differ between a parent snapshot and a child, which is exact and cheap, and both can stream the difference as a first-class operation. The constraint is that the parent snapshot must still exist, which ties the backup’s validity to the snapshot retention policy inside the source system, not to the backup catalog.

At the file layer, a scanner compares metadata: path, size, modification time, inode number. This is fast because it reads directories rather than data, and it is wrong in two directions. It reports files as changed when only the timestamp moved, which is harmless. It reports files as unchanged when the content changed but the metadata did not, which is not: a file modified within the same timestamp granularity as the scan, with its size preserved, is indistinguishable from an untouched file. Filesystem timestamps have improved but a one-second granularity is still common, and tools compensate by re-reading files whose timestamp is close to the scan start, or by also comparing the inode change time, which cannot be set from userspace.

Content-defined chunking avoids the metadata question by reading everything and deciding what is new from the content. A rolling hash is computed over a window of bytes, typically a few dozen, and advanced one byte at a time. When the hash satisfies a mask, the position is a chunk boundary. Because the decision depends only on nearby bytes, inserting a block of data at the start of a file shifts the boundaries only until the next one that the content dictates, and every chunk after that point is unchanged. Fixed-size chunking has the opposite behaviour: a one-byte insertion shifts every subsequent boundary, and the entire rest of the file is stored again.

The average chunk size is set by the mask: a mask of n bits yields an average of 2^n bytes between boundaries, with explicit minimum and maximum sizes to prevent pathological runs. A smaller average deduplicates better and costs more metadata, since every chunk needs an entry in the index.

Why deduplication makes deletion expensive

In a deduplicated store, the unit of storage is not the file or the backup but the chunk, and a chunk is shared by every backup that contains it. A snapshot’s index lists chunk identifiers; the chunks themselves carry a reference count or are marked during a reachability sweep.

The consequence is that deleting a backup does not free the space that backup appears to occupy. Deleting the most recent incremental in a chain often frees nothing at all, because every chunk it references is also referenced by its parent. Deleting the oldest full backup may free a great deal, because it is the only holder of chunks that later backups overwrote. A retention policy expressed as “keep seven daily, four weekly” therefore has a storage cost that cannot be computed from the sizes of the individual snapshots, and the only way to know it is to simulate the policy against the repository.

Reclaiming space is a separate operation from deleting references. Removing a snapshot leaves unreferenced chunks in place; a repack or prune operation must read the remaining data, rewrite packs without the dead chunks, and update every index that pointed into the rewritten packs. That operation is proportional to the size of the repository, not to the amount deleted, and it needs temporary free space roughly equal to the largest pack it rewrites. Systems that skip this step do not reclaim space at all, which is a common source of confusion when a repository’s size does not fall after a deletion.

Restore time grows with depth

A full restore from a linear chain reads the full, then applies each incremental in order. The data volume is roughly the size of the final state plus the sum of the intermediate changes, but the time is not linear in that volume alone. Each link must be opened, its index read, and its chunks resolved against the store, and the resolution is random access into a repository that may be on object storage with per-request latency.

Two things follow. First, restore time is a function of chain depth even when the bytes restored are constant, because the per-link overhead is paid once per link. Second, the worst case for a restore is the backup that has the longest chain behind it, which is the oldest data and often the data that matters most after a slow-moving corruption is discovered.

There is a threshold beyond which the arrangement stops making sense: when a restore takes longer than the interval between backups, the system cannot recover from a failure before the next backup is due, and the backup schedule starts to interfere with recovery. A chain of nightly incrementals that takes thirty hours to restore has an effective recovery time objective of thirty hours, regardless of what the documentation claims.

Collapsing the chain without a new full

The standard fix is a synthetic full: the backup server reads the existing full and the incrementals, writes a new full representing the state at the end of the chain, and treats it as a new chain’s root. The client is not involved and does not resend data, so the backup window is unaffected. The cost is server-side I/O and temporary storage for the new full while the old chain still exists.

The inverse arrangement puts the full at the head of the chain and makes each older member a reverse delta: the latest backup is a complete image, and each earlier one is stored as the difference needed to walk backwards. Restoring the latest state is fast, which is the common case; restoring an older state requires applying reverse deltas, which is the uncommon case. The trade is between the two restore paths, and it assumes the frequency of restores is strongly skewed toward the most recent.

Neither arrangement removes the dependency; both change its shape. A synthetic full is still derived from the chain it collapses, and if that chain contained a logical error, the error is baked into the new root. A reverse-delta chain still cannot restore the past without the future.

The question of whether any of these restores produces usable data is separate from whether the chain is intact, and it is the subject of checksum verification and restore drills. How much data a restore can afford to lose is set by the log shipping design described in log shipping and the recovery point objective.