Why Zookeeper Implements Sequential Consistency and What It Really Means

Zookeeper Consistency Model

Zookeeper does not provide eventual consistency nor strong consistency in the sense of Paxos. Its guarantees are best described as sequential consistency for read operations and linearizability for write operations.

Sequential Consistency

Defined by Lamport (1979), sequential consistency requires that the result of any execution be indistinguishable from some total order of all operations where each process’s operations appear in program order. In other words, all operations across processes can be arranged in a single sequence that respects the order each process issued its commands.

Any execution – every possible interleaving of operations.

Sequential order – a total order that preserves each process’s program order.

Difference from Linearizability

Linearizability (strong consistency) demands that each operation appear atomically at a single instant between its invocation and response. Sequential consistency relaxes the timing requirement, allowing more implementations while still preserving program order. Zookeeper’s reads satisfy the weaker sequential consistency, while writes are linearizable.

Illustrative Execution Scenarios

Consider two programs P1 and P2 each performing a write followed by a read:

P1_write(x);
P1_read(y);

P2_write(u);
P2_read(v);

All 4! = 24 possible interleavings constitute "any execution". Sequential consistency disallows those interleavings that cannot be mapped to a total order respecting each program’s order. For example, an execution where P1 reads before its own write (due to cache reordering) would violate sequential consistency.

Typical allowed executions (A and B) can be mapped to a sequential order; a disallowed execution (C) cannot.

Why Zookeeper Needs Sequential Consistency

Zookeeper is a coordination service that implements distributed locks and leader election. To guarantee correctness without additional synchronization, client‑visible operations must appear sequentially consistent. This ensures that a client’s sequence of reads and writes behaves as if executed on a single logical replica.

Practical Implications

Understanding the consistency model helps developers reason about distributed algorithms built on Zookeeper and avoid bugs caused by assuming stronger guarantees than provided. For instance, a read may return an older value even after a majority of replicas have committed a newer write, because reads are only sequentially consistent.

Key References

Zookeeper official guarantees (v3.4.9): http://zookeeper.apache.org/doc/r3.4.9/zookeeperProgrammers.html#ch_zkGuarantees

Lamport, "How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs" (1979)

Andrew S. Tanenbaum & Maarten Van Steen, Distributed Systems: Principles and Paradigms

Community discussion on Zookeeper consistency: http://comments.gmane.org/gmane.comp.java.hadoop.zookeeper.user/5221