Chandy-Lamport Snapshots: Capturing a Consistent Global State

How do you take a "photo" of a distributed system when there's no global clock and messages are in flight? The Chandy-Lamport algorithm records a consistent global state without pausing the system, and it underpins checkpointing in modern stream processors.

What "consistent" means

A snapshot is consistent if, for every message recorded as received, its send is also recorded. Equivalently, it's a cut where no effect appears without its cause. Messages sent before the cut but received after must be captured as channel state.

The algorithm (FIFO channels assumed)

1. The initiator records its local state and sends a marker on every outgoing channel.
2. When a process receives a marker for the first time on channel c, it records its local state, records c as empty, sends markers on all its outgoing channels, and starts recording messages on its other incoming channels.
3. When a process receives a marker on a channel it was recording, it stops recording that channel; the recorded messages are that channel's state.
4. The snapshot is complete when every process has received a marker on every incoming channel.

Why FIFO matters

The marker separates "before the snapshot" from "after" on each channel. If channels could reorder, a post-snapshot message could overtake the marker and be wrongly included in the recorded state.

In practice: stream processing checkpoints

Apache Flink uses a variant called asynchronous barrier snapshotting. Sources inject barriers into the stream; an operator with multiple inputs aligns barriers (buffering inputs that are ahead) and then snapshots its state to durable storage. Because the dataflow is mostly acyclic, channel state often doesn't need recording, and unaligned checkpoints trade larger snapshots for lower latency under backpressure.

What to mention in an interview

• No global pause: processes keep working while the snapshot propagates.
• Uses: deadlock detection, termination detection, failure recovery checkpoints, debugging.
• Cost: O(E) markers per snapshot, plus buffering of in-flight messages.
• The recorded state may never have existed at a single instant, but it's one the system could have passed through, which is all recovery needs.

Disclosure: from the people building Linkjob AI, an AI copilot for system design interviews.