Checkpointing and the Cost of a Consistent Snapshot

A checkpoint is a durable copy of a data structure at a single logical instant. The word “instant” is where the difficulty lies. A structure large enough to need a checkpoint is also large enough that writing it out takes many seconds, and during those seconds it changes. If the checkpoint copies page 1 at the start and page 900 at the end, the result is not any state the structure ever had: page 1 is from before some updates, page 900 from after them. A recovered system that loads such an image has silently lost or duplicated work, and no checksum on the image will detect it, because every individual page is valid.

Consistency is a relationship between pages, not a property of each

The failure is easy to state and easy to miss. Suppose a counter’s value lives on page 10 and the total it contributes to lives on page 40. An update writes both. The checkpoint copies page 10 before the update and page 40 after it, and the sum on page 40 includes a contribution whose source value on page 10 is the old one. Each page passed its checksum; the image is internally inconsistent.

Every consistent-snapshot mechanism is a way of ensuring that the set of versions captured is closed under the “was read by” relation of the application. There are only a few ways to get that closure: stop the world while copying, copy the structure in a way that the application cannot modify what is being copied, or record enough information to reconstruct the missing pieces. Each has a distinct cost, and the choice is the central design decision in a checkpointing system.

Stop-the-world and its variants

The simplest mechanism suspends all writers, copies the structure, and resumes. Correctness is immediate because nothing changes during the copy. The cost is the copy time itself, which for a structure of many gigabytes and a device at hundreds of megabytes per second is tens of seconds, a pause no interactive system can accept, and a pause that grows with the size of the data rather than with the rate of change.

Two refinements keep the mechanism and shrink the pause. The first copies only the metadata and the root, not the data: if the structure is arranged so that all pages reachable from a root are immutable while a checkpoint is in progress, the copy is one page and the pause is one write. The second relies on the memory system’s own copy-on-write: the checkpoint’s writer walks the structure and duplicates only the pages that change afterwards, so the copy is proportional to the update rate during the checkpoint window rather than to the size of the data.

Both refinements move work out of the pause and into the steady state. The first makes the pause constant but makes every subsequent update allocate, because the page being modified cannot be written in place while the checkpoint might still need the old version. The second does the same for the duration of the window only. Either way the pause is traded for allocation traffic, which is the trade that makes copy-on-write filesystems attractive for snapshots and expensive for write-heavy workloads.

Copy-on-write roots

The copy-on-write arrangement is worth describing in its own terms because it generalizes. The persistent structure is a tree whose internal nodes hold pointers to children. A checkpoint records the root pointer. An update copies every node on the path from the root to the modified leaf, modifies the copy, and rewires the parent to point to it; the old nodes remain, reachable from the old root and untouched. The new root pointer is installed with a single atomic store, and the checkpoint becomes durable when the new root’s block reaches media.

The property this buys is that a checkpoint costs one write, no matter how large the structure. The property it costs is that an update costs a path copy, depth times node size, rather than a single page write. For a tree of depth four and 4 KiB nodes, that is 16 KiB per update, four times the payload. The amplification is the price of constant-time checkpoints, and it is why the technique is paired with batching: many updates to the same leaf share one path copy if they are applied before the path is published.

Publication of the root has an ordering requirement that is easy to get wrong. Every block reachable from the new root must be durable before the root pointer is written, or a crash leaves a root that points at blocks which do not exist. This is a flush before the root write, and the root write itself needs to be atomic with respect to a torn write, which generally means it is a single sector or it is written to one of two alternating slots with a sequence number and a checksum.

/* Publish a new tree root only after everything it points to is durable. */
write_subtree(new_root);        /* allocate and write children first */
flush_cache();                  /* children and interior nodes on media */
write_root_slot(new_root, seq); /* one sector, checksummed */
flush_cache();                  /* the root itself durable */

The sequence number in the root slot is what lets recovery pick the newer of two roots when both are valid. If the newer one is torn or fails its checksum, recovery falls back to the older, which is complete by construction because it was published by the same protocol earlier. The cost of this fallback is that a crash during publication loses the checkpoint that was in progress, which is acceptable: the checkpoint’s purpose is to bound how much log must be replayed, and losing the newest one only means replaying further.

Double buffering and the alternating image

An older and still common arrangement keeps two full copies of the metadata and writes alternately into them. Checkpoint N writes image A while readers use image B; when A is complete and durable, a pointer switch makes it current, and checkpoint N+1 writes into B. The pause is the switch, not the copy, so the pause is one atomic store plus the flush that makes the new image durable.

The cost is that half the metadata space is unavailable at any time, and that each checkpoint writes the entire metadata image whether or not it changed. For a metadata set of a few hundred megabytes, that is a few hundred megabytes of writes per checkpoint, which sets a floor on the checkpoint interval for a device of known bandwidth. The technique is attractive when the metadata is small relative to the data and the update rate is high, because it decouples the checkpoint cost from the update rate entirely.

Fuzzy checkpoints

A fuzzy checkpoint writes pages while the system continues to modify them, and records in the log which pages were copied at which log sequence number. Recovery replays the log from the checkpoint’s starting sequence number, which re-applies every update that happened during the copy. The image after recovery is consistent not because the copy was consistent but because replay repaired it.

The correctness argument has two parts. Every page in the image is some version of that page that existed at some point during the copy window, so replay from a sequence number at or before the window’s start will bring it forward to the recovery point. And replay must be idempotent, since it may apply an update to a page that already has it, which is why the log records full after-images rather than increments, the same requirement that makes interrupted recovery safe, described in Write-Ahead Logging and the Commit Record.

The cost of fuzziness is that the checkpoint does not bound recovery time by itself; it bounds it together with the amount of log written during the window. A long checkpoint window on a busy system produces a long replay. The mechanism that keeps this bounded is a rate limit on the checkpoint’s writes, chosen so that the window’s duration times the update rate stays below the log’s capacity. That is a feedback loop, and getting it wrong produces the classic failure: the checkpoint cannot finish before the log fills, writers stall, and the stall makes the checkpoint slower because its own writes are competing with the foreground.

Choosing between them

The three mechanisms differ along the same axis: how much work is moved out of the pause, and what structure has to be maintained to move it. Stop-the-world moves nothing and needs nothing. Copy-on-write moves everything and needs an immutable-node discipline plus allocation for every update. Double buffering moves the copy and needs double the metadata space. Fuzzy moves the copy and needs a log that can replay the window.

The choice also depends on what the checkpoint is for. If it exists to bound recovery time, a fuzzy checkpoint with a rate limit is the natural fit because it spreads the cost. If it exists to provide a point-in-time image that can be read or cloned, copy-on-write roots are the natural fit because the old root remains valid and can be mounted or opened directly. If it exists to survive a device failure with minimal complexity, double buffering is the natural fit because the recovery procedure is a pointer read.

One further constraint applies to all of them: the checkpoint must not be confused with a backup. A checkpoint on the same device shares the device’s failure domain, and a device that loses a block loses it from both the checkpoint and the log. The mechanisms that address that are checksums and redundancy, which are the subject of Torn Writes and the RAID Write Hole, and the structures that avoid rewriting unchanged data are the subject of Shadow Paging and Copy-on-Write Trees.