A Register Built on etcd
Etcd, like Zookeeper, is built to hold small amounts of strongly-consistent state for coordination tasks. It organizes data as a tree of logical keys, each mapped to a JSON-encoded value and tracked with an index version. Because it exposes atomic compare-and-set by value and index over HTTP, etcd serves as a building block for service discovery, locking, and sequencing. To verify those consistency claims, we need a Jepsen test that treats etcd as a single, atomic register.
The Client Layer
Our Jepsen client applies operations to etcd by wrapping the v (Verschlimmbesserung) client. The CASClient datatype carries a key k and an active client connection. The setup function binds a latent client to a specific node and initializes the register: it connects to the node, resets the key to nil, and returns a new client with that connection set.
The invoke! function maps a Jepsen invocation to an etcd call. The three possible outcomes must be handled precisely for a correct consistency analysis:
:ok— the operation definitely took place.:fail— the operation definitely did not occur (e.g., a failed CAS).:info— indeterminate result, like a timeout.
Indeterminate reads can be treated as never having happened (:fail), since they don't alter state and impose a huge penalty on the linearizability checker if left unresolved. For writes and CAS operations, however, we must return :info on exceptions because a timeout could still result in a late commit.
We implement three functions. Reads use etcd's consistent read option, which claims to contact the leader for the latest value; the JSON result is parsed and returned. Writes serialize the value to JSON and reset the key. For compare-and-set, we extract the old and new values, serialize both, and call v/cas!, which returns a boolean indicating success. Error handling is a straightforward check: reads get a :fail, writes and CAS get :info.
The Single-Threaded Model
The companion CASRegister datatype tracks a single field, value. Reads are allowed only if the client's expected value matches the model's current value, or if the client doesn't specify one. Writes replace the state entirely. A CAS succeeds when the old value matches the register's current state; otherwise, it produces an explicitly inconsistent result for Knossos. The model starts at nil, matching the client's initialization, so the real etcd key and the model start in sync.
Running the Test
The test composes a client, the CASRegister model, and a linearizability checker. A generator drives phases: first, a random mix of reads, writes, and CAS operations with added latency, running for 20 seconds while a nemesis partitions the cluster and heals it. The final phase stops the partition, sleeps 10 seconds to allow convergence, and performs a final read from each client to observe stabilization. The checker then determines whether every operation's outcome could be linearized against the model.
Etcd in Practice: Fast Start, Fast Problems
Etcd converges quickly—often in milliseconds—making it unusually convenient for both production use and fault-injection testing. That speed, however, exposed race conditions in etcd's cluster state management. Even with deliberate delays between node startups, a known bug (Issue 716) caused the primary to crash-loop in nearly every cluster setup. The etcd team responded quickly with fixes, but similar concurrency issues in goraft, the underlying consensus implementation, remain a lingering concern.
With some effort, a reliable cluster can be established. In a typical Jepsen run, the cluster spans nodes :n1 through :n5, with five worker threads each issuing random operations against a single shared register. Each worker talks to a distinct etcd node per request but follows redirects to whichever node that node believes is the current leader.
INFO jepsen.system.etcd - :n4 etcd ready
INFO jepsen.system.etcd - :n1 etcd ready
INFO jepsen.system.etcd - :n5 etcd ready
INFO jepsen.system.etcd - :n2 etcd ready
INFO jepsen.system.etcd - :n3 etcd ready
INFO jepsen.core - Worker 0 starting
INFO jepsen.core - Worker 3 starting
INFO jepsen.core - Worker 2 starting
INFO jepsen.core - Worker 4 starting
INFO jepsen.core - Worker 1 starting
Workers begin by reading the initial nil value. Operations proceed normally—a compare-and-set from 2 to 4 fails because the value is still nil, and reads continue returning nil.
INFO jepsen.util - 2 :invoke :read nil
INFO jepsen.util - 4 :invoke :read nil
INFO jepsen.util - 0 :invoke :read nil
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 3 :invoke :read nil
INFO jepsen.util - 0 :ok :read nil
INFO jepsen.util - 3 :ok :read nil
INFO jepsen.util - 4 :ok :read nil
INFO jepsen.util - 2 :ok :read nil
INFO jepsen.util - 1 :ok :read nil
INFO jepsen.util - 0 :invoke :read nil
INFO jepsen.util - 3 :invoke :cas [2 4]
INFO jepsen.util - 4 :invoke :cas [4 4]
INFO jepsen.util - 2 :invoke :read nil
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 0 :ok :read nil
INFO jepsen.util - 2 :ok :read nil
INFO jepsen.util - 1 :ok :read nil
INFO jepsen.util - 4 :fail :cas [4 4]
INFO jepsen.util - 3 :fail :cas [2 4]
The nemesis process then induces a network partition, isolating nodes from one another. As expected, some operations time out—a normal consequence for a CP system.
INFO jepsen.util - :nemesis :info :start nil
INFO jepsen.util - 0 :invoke :write 4
INFO jepsen.util - 0 :ok :write 4
INFO jepsen.util - 3 :invoke :read nil
INFO jepsen.util - 3 :ok :read 4
INFO jepsen.util - 2 :invoke :cas [0 4]
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 1 :ok :read 4
INFO jepsen.util - 4 :invoke :write 1
INFO jepsen.util - 2 :fail :cas [0 4]
INFO jepsen.util - 4 :ok :write 1
INFO jepsen.util - 0 :invoke :read nil
INFO jepsen.util - 0 :ok :read 1
INFO jepsen.util - 3 :invoke :read nil
INFO jepsen.util - 3 :ok :read 1
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 1 :ok :read 1
INFO jepsen.util - :nemesis :info :start "Cut off {:n5 #{:n4 :n1}, :n2 #{:n4 :n1}, :n3 #{:n4 :n1}, :n1 #{:n3 :n2 :n5}, :n4 #{:n3 :n2 :n5}}"
INFO jepsen.util - 3 :info :cas :timed-out
INFO jepsen.util - 1 :invoke :write 3
INFO jepsen.util - 1 :ok :write 3
INFO jepsen.util - 2 :invoke :read nil
INFO jepsen.util - 2 :ok :read 3
INFO jepsen.util - 4 :invoke :cas [2 3]
INFO jepsen.util - 4 :fail :cas [2 3]
INFO jepsen.util - 0 :invoke :write 0
INFO jepsen.util - 8 :invoke :cas [1 2]
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 1 :ok :read 3
INFO jepsen.util - 2 :invoke :write 2
INFO jepsen.util - 2 :ok :write 2
INFO jepsen.util - 4 :invoke :cas [2 3]
INFO jepsen.util - 0 :info :write :timed-out
INFO jepsen.util - 4 :ok :cas [2 3]
INFO jepsen.util - 8 :info :cas :timed-out
But during one partition cycle, an unexpected "Raft Internal Error" appears:
FO jepsen.util - 4 :info :cas {:status 500, :errorCode 300, :message "Raft Internal Error", :index 41}
INFO jepsen.util - 10 :ok :write 0
INFO jepsen.util - :nemesis :info :start "Cut off {:n1 #{:n2 :n5}, :n4 #{:n2 :n5}, :n3 #{:n2 :n5}, :n5 #{:n3 :n4 :n1}, :n2 #{:n3 :n4 :n1}}"
Another failure mode surfaced: two nodes each believed they were the current leader, returning HTTP redirects to each other in an endless loop.
INFO jepsen.util - 1 :invoke :read nil
INFO jepsen.util - 2 :invoke :read nil
INFO jepsen.util - 2 :ok :read 0
INFO jepsen.util - 1 :fail :read :redirect-loop
Despite these anomalies, operations largely completed with low latency. An older version of Jepsen might have passed this test. Jepsen II, however, holds systems to a stricter standard.
INFO jepsen.util - 18 :ok :read 2
INFO jepsen.core - Worker 3 done
INFO jepsen.core - Run complete, writing
INFO jepsen.core - Analyzing
INFO jepsen.core - Analysis complete
The Results: Not Linearizable
The first test flagged a linearizability failure immediately. After an additional week of verifying both Jepsen and the custom etcd client, the conclusion was unambiguous: etcd's registers are not linearizable.
FAIL in (register-test) (etcd_test.clj:45)
expected: (:valid? (:results test))
actual: false
Not linearizable. Linearizable prefix was:
2 :invoke :read nil
4 :invoke :read nil
0 :invoke :read nil
1 :invoke :read nil
3 :invoke :read nil
0 :ok :read nil
3 :ok :read nil
4 :ok :read nil
2 :ok :read nil
1 :ok :read nil
0 :invoke :read nil
3 :invoke :cas [2 4]
4 :invoke :cas [4 4]
2 :invoke :read nil
1 :invoke :read nil
0 :ok :read nil
2 :ok :read nil
1 :ok :read nil
4 :fail :cas [4 4]
3 :fail :cas [2 4]
0 :invoke :read nil
0 :ok :read nil
2 :invoke :write 1
1 :invoke :cas [2 3]
2 :ok :write 1
1 :fail :cas [2 3]
4 :invoke :write 3
3 :invoke :write 1
4 :ok :write 3
3 :ok :write 1
0 :invoke :cas [4 1]
2 :invoke :write 2
1 :invoke :write 1
0 :fail :cas [4 1]
3 :invoke :read 1
4 :invoke :write 0
3 :ok :read 1
2 :ok :write 2
1 :ok :write 1
4 :ok :write 0
:nemesis :info :start nil
0 :invoke :write 4
0 :ok :write 4
3 :invoke :read 4
3 :ok :read 4
2 :invoke :cas [0 4]
1 :invoke :read 4
1 :ok :read 4
4 :invoke :write 1
2 :fail :cas [0 4]
4 :ok :write 1
0 :invoke :read 1
0 :ok :read 1
3 :invoke :read 1
3 :ok :read 1
1 :invoke :read 1
1 :ok :read 1
:nemesis :info :start "Cut off {:n5 #{:n4 :n1}, :n2 #{:n4 :n1}, :n3 #{:n4 :n1}, :n1 #{:n3 :n2 :n5}, :n4 #{:n3 :n2 :n5}}"
2 :invoke :cas [1 4]
4 :invoke :read 1
4 :ok :read 1
2 :ok :cas [1 4]
Followed by inconsistent operation:
0 :invoke :read 1
Knossos, the consistency checker, can enumerate possible orderings of the history leading up to the offending read. In all thirteen-thousand-plus interpretations examined, the register ended with value 4 after a successful compare-and-set operation.
World with fixed history:
1 :invoke :read nil
3 :invoke :read nil
2 :invoke :read nil
4 :invoke :read nil
0 :invoke :read nil
2 :invoke :read nil
1 :invoke :read nil
0 :invoke :read nil
0 :invoke :read nil
2 :invoke :write 1
4 :invoke :write 3
3 :invoke :write 1
3 :invoke :read 1
4 :invoke :write 0
1 :invoke :write 1
2 :invoke :write 2
0 :invoke :write 4
3 :invoke :read 4
1 :invoke :read 4
4 :invoke :write 1
0 :invoke :read 1
3 :invoke :read 1
1 :invoke :read 1
4 :invoke :read 1
2 :invoke :cas [1 4]
led to state:
{:value 4}
with pending operations:
(and 12928 more worlds, elided here)
Inconsistent state transitions:
([{:value 4} "can't read 1 from register 4"])
Once that CAS is acknowledged, a linearizable register cannot subsequently return an earlier value to a read. This is a direct violation of linearizability.
Root Cause: Local Reads From Self-Appointed Leaders
The failing history shows process 4 writing 1, several processes reading 1, then a successful compare-and-set from 1 to 4. After that CAS, some process still read 1—a classic stale read that violates not just linearizability but sequential consistency, causal consistency, and read-your-write guarantees.
The source of the problem: etcd's "consistent" reads do not go through the Raft log.
They return local state whenever the node considers itself the leader. Raft, however, does not guarantee leader exclusivity—multiple nodes can believe they are leader simultaneously. Under a partition, a new leader can accept a CAS, changing 1 to 4, but cannot propagate that change to the old leader, which continues serving stale reads until its heartbeat timeout expires and it steps down. Once the partition heals, the old leader receives the updated value and normal operation resumes.
This behavior is sometimes defended as "linearizable with respect to the Raft index." It is not. A consistent read can observe index 5, then index 4, then index 6. Sequential consistency could theoretically be restored by having the client track the etcd index and enforce a minimum-index constraint on requests—but that fix is optional, absent from current client libraries, and still does not deliver linearizability.
Consul's Similar Finding
Hashicorp's Consul, announced shortly after this etcd analysis, modeled its Jepsen testing on the etcd template. The team's public report claimed graceful recovery from partitions with no consistency issues—but that was incomplete. Jepsen did find a consistency issue in Consul, and it was the same class of bug: "consistent" reads returned local state from any node that regarded itself as leader, enabling stale reads. The initial fix reduced the leader timeout from one second to 300 milliseconds.
- LeaderLeaseTimeout: time.Second,
+ LeaderLeaseTimeout: 300 * time.Millisecond,
Timeout adjustments are a pragmatic workaround, not a correctness guarantee. Runtime interruptions—heavy I/O, blocking syscalls, vmotion pauses, or Go garbage collection (with documented pauses up to ten seconds)—can easily exceed a 700-millisecond safety margin. The robust solution is to eliminate the time dependency from the algorithm entirely.
A Path Forward
Discussions with both teams point toward three tiers of reads, trading off performance against consistency:
- Anything-goes reads: any node may return its last known value; fully available but with no monotonicity guarantees. Etcd does this by default; Consul calls it "stale."
- Mostly-consistent reads: only leaders respond, but stale reads can still slip through. This was etcd's default "consistent" mode and Consul's default behavior.
- Consistent reads: the leader performs a round trip to confirm it remains authoritative before responding. Consul now terms this "consistent."
Consul has already implemented these changes with thorough documentation of the tradeoffs. Etcd is still working toward the same design. Both teams have responded promptly to bug reports and take consistency seriously—an encouraging sign for the growing ecosystem of strongly consistent systems.
