Testing the failure modes that matter

In previous Jepsen testing, RethinkDB’s stable-membership behavior held up well under network partitions and process pauses. No nonlinearizable histories surfaced for single-document reads, writes, or conditional writes. But a stable set of nodes never changes during a partition—and that misses an entire class of failure.

A harder test involves reconfiguring the cluster membership while the system is under stress. This is a much more demanding problem than consensus with a fixed set of participants. Old and new sets of nodes must agree on a handoff, ensure that operations performed during that transition are agreed upon by both groups, and then settle into normal consensus on the new configuration. There is plenty of room for errors in that fragile window.

How RethinkDB manages table configurations

RethinkDB does not use Raft to reach consensus on individual data values. Instead, Raft governs the table configuration—metadata that defines which nodes are replicas for a table and which of those replicas is the default primary for coordinating linearizable reads and writes. This separation is what lets Rethink handle single-key operations without a global ordering across the whole system, and it allows data to be sharded so that only one shard’s replicas are involved in a given operation.

The Raft paper includes an extension for membership changes, and RethinkDB implements it for configuration transitions. The handoff has two phases:

  1. The leader enters joint-consensus mode, broadcasting to all nodes in both the old and new configurations. Committing an entry or becoming leader requires acknowledgment from a majority in both groups.
  2. Once joint consensus is committed, neither old nor new can act alone. The leader then broadcasts the final configuration—only new nodes—and followers apply it.

The danger emerges when nodes get isolated or crash mid-transition. A follower that misses the final configuration might keep believing it belongs to a cluster that no longer exists. Worse, a newly elected leader may overwrite logs that a stale node is still following. Network partitions widen these windows dramatically.

Designing the test

We ran reads, writes, and compare-and-set operations against single documents—the same workload from the earlier RethinkDB analysis, bucketed by key and checked independently for linearizability. The nemesis this time added reconfiguration operations:

  • A uniformly random replica count between one and five
  • A randomly selected set of replicas of that size
  • A randomly chosen default primary for the configuration

We combined that reconfiguration nemesis with partition-random-halves, which divides the network into two randomly chosen halves and later heals them. Reconnaissance operations were emitted between the partitioner’s start and stop cycles. If a reconfiguration failed because a node was unreachable or the table was down, we retried a limited number of times. For consistency, we only used majority reads and writes—anything lower is already known to break linearizability.

Race conditions in the test setup could deadlock, so we also made the nemesis wait until the client had already created the table it was about to re-configure.

(nemesis/compose
  {#{:reconfigure} (reconfigure-nemesis "jepsen" "cas")
   #{:start :stop} (nemesis/partition-random-halves)})

                           (gen/nemesis
                             (gen/phases
                               (gen/await
                                 (fn []
                                   (info "Nemesis waiting")
                                   (deref (:table-created? (:client t)))
                                   (info "Nemesis ready to go")))
                               (->> (cycle [{:type :info, :f :start}
                                            {:type :info, :f :stop}])
                                    (interpose {:type :info, :f :reconfigure})
                                    (gen/seq))))

The test ran clean several times in a row.

The read anomaly

Then the checker flagged two reads of the value 0 after a writer had reported a successful write of 1. No legal state path explains this: once the register is 1, a legal later transaction must lead to a value of 3 or 4, not back to 0. The history was unequivocally nonlinearizable.

Those 0 reads could have come from a stale read—an earlier legal state before any write of 1 was visible. Or they could have come from a dirty read of a write that failed externally but left its data visible. It could even be a lost update: the write of 1 was acknowledged by the system and then discarded.

To distinguish those possibilities, we removed reads from the workload entirely, leaving only blind writes and compare-and-set. If writes alone could produce anomalous histories, no server could claim clean reads were at fault.

The write anomaly

It got worse. The test surfaced a history in which a writer sent write 0, and then a compare-and-set of 3 to 0 succeeded—with no other concurrent operations interleaving. Since neither the writers nor the network partition could explain that by a legal register state, RethinkDB itself was allowing lost updates.

Context makes the failure concrete. In the failing run—the same one referenced in the check’s 

:nemesis :info :reconfigure {:replicas (:n3),
                             :primary  :n3,
                             :grudge   {:n3 [(:n4)],
                                        :n4 [(:n3)]}}
12 :invoke :write 3
17 :invoke :cas   [4 2]
12 :ok     :write 3
17 :fail   :cas   [4 2]

... lots of failed ops ...

3  :invoke :write 0
3  :ok     :write 0
12 :invoke :cas   [0 0]
17 :invoke :cas   [1 4]
12 :fail   :cas   [0 0]
17 :fail   :cas   [1 4]
:nemesis :info :reconfigure {:replicas (:n4),
                             :primary  :n4,
                             :grudge   {:n4 [(:n3)],
                                        :n3 [(:n4)]}}

... more failed ops ...

12 :invoke :cas   [3 3]
17 :invoke :cas   [3 0]
12 :fail   :cas   [3 3]
17 :ok     :cas   [3 0] <--- Consistency violation
report—the initial primary n3 was isolated from n4. A process talking to n3 wrote 3. A process talking to n4 wrote 0. The nemesis renamed n4 as the new primary, while the partition kept the two apart. Then a separate process issued the compare-and-set of 3 to 0 against the still-isolated n3.

  • n3 saw a write of 3 and a CAS 3→0—legal within its own history.
  • n4 saw a write of 0—also legal in isolation.

Each node was effectively running an independent cluster, accepting writes without either observable replication nor union. The system was in split-brain mode.

These failures were rare—minutes to hours of repeated reconfiguration and partitioning were needed to trigger them. In production, where clusters are rarely reconfigured under a network partition, the likelihood of hitting this by accident is low.

But when the bug fires, failures are severe. Each split-brain ensemble assigns itself authority to serve reads and writes, and as far as we could tell the situation persists indefinitely until human intervention. The sane recovery route is to decide which configuration to keep, destroy or isolate the rival nodes, and potentially perform an emergency table repair to lay down a new final configuration. That emergency repair, by necessity, invalidates consistency guarantees—because the whole point is to recover from an already inconsistent state. The fix pairs one warning with another: if you ever have to use it, something has already gone seriously wrong. Versions 2.2.4 and 2.1.6, which were released last week, address this class of reconfiguration error.

Raft’s broken assumptions

The consistency violations observed in these tests suggest that RethinkDB’s Raft implementation was being driven into states its invariants are supposed to forbid. Several crash logs offered direct evidence of this. One recurring crash involves apply_log_entries, which validates that the range of entries being applied is well-formed—specifically, that the last index is not lower than the first. In a correctly operating cluster, a leader’s committed index should never be lower than a follower’s, so an invalid range implies something deeper has gone wrong. This is bug 4979, originally flagged by RethinkDB’s own fuzz testing in October 2015. The team committed a partial fix then, but the bug resurfaced both in their fuzzer and in Jepsen tests.

Other crashes pointed to a more fundamental problem: multiple nodes believing they are the leader for the same term. An assertion in the Raft core depends on the single-leader invariant, yet the test logs show that invariant being violated. Likewise, a follower-side assertion that all writes for a given term must come from the same leader was also tripped. These failures imply that two Raft nodes each believed they had won the election for the same term—something the protocol should guarantee cannot happen.

All of these symptoms pointed toward an inconsistency about committed log offsets, which in turn suggested that the Raft cluster had split into independent majorities. But the mechanism eluded both the RethinkDB team and this author for weeks. Only after lengthy code review and failure analysis did the root cause emerge: a violation of Raft’s stable-storage assumptions caused by a reconfiguration edge case.

Node ID reuse

RethinkDB manages membership for each table via a Raft cluster spanning all voting replicas. When a table is reconfigured—adding or removing replicas—the process is orchestrated through the multi table manager on each node. Replicas have Raft node IDs assigned by the cluster, and careful bookkeeping ensures those IDs are not reused. When a replica is removed, its Raft state is destroyed and storage is wiped. If a removed node is later re-added, the cluster assigns a fresh node ID so other members know the node has no historical state. Reusing an old ID on a wiped node would falsely imply the node had been in the cluster all along but lost its data—which would invalidate Raft’s requirement that node storage persists reliably.

To guarantee this, ACTIVE and INACTIVE messages—which create and destroy Raft instances—carry monotonic logical timestamps, and the multi table manager only applies them in timestamp order. The logic seems sound, with one exception. A bug in version 2.1.0 allowed replicas to generate timestamps of 263, the maximum representable integer, which would permanently prevent the multi table manager from ever applying subsequent configuration messages. As a workaround, the ordering code carries an escape hatch: INACTIVE → ACTIVE transitions are always honored, regardless of timestamp.

/* If we are inactive and are told to become active, we ignore the
timestamp. The `base_table_config_t` in our inactive state might be
a left-over from an emergency repair that none of the currently active
servers has seen. In that case we would have no chance to become active
again for this table until another emergency repair happened
(which might be impossible, if the table is otherwise still available). */
bool ignore_timestamp =
    table->status == table_t::status_t::INACTIVE
    && action_status == action_status_t::ACTIVE;

That special case is where things unravel. If message delivery is delayed or reordered—for example, during a network partition—and a replica receives a duplicate ACTIVE message after an INACTIVE, the escape hatch lets it rejoin the cluster using its old node ID while its persistent state has been erased. The replica enters the cluster as a blank slate but is treated as though it had been participating all along.

Chaos from amnesia

A replica in this state can wreak havoc on the Raft algorithm. It can re-cast votes in elections it already participated in, which can split the vote such that two leaders are elected for the same term. This explains the leader-invariant violations, the log-index crashes, and ultimately the independent primaries satisfying reads and writes in divergent ways—producing the stale reads, illegal compare-and-set operations, and acknowledged write loss observed in the Jepsen tests.

The trigger conditions are narrow. The fault requires a combination of large and small replica configurations, a network partition that isolates the small replicas from the larger ones, and enough message delay or reordering for a stale ACTIVE message to arrive after INACTIVE. In testing, it typically takes tens to hundreds of partition-and-reconfigure rounds to hit the bug.

With the timestamp special case removed, RethinkDB passed Jepsen’s linearizability tests across network partitions and reconfigurations in dozens of hours of testing. The fix is included in RethinkDB 2.2.4 and has been backported to 2.1.6.

Lessons from the boundary

The RethinkDB team drew several conclusions from this debugging effort. Fuzz-testing at both functional and integration levels proved valuable for exposing order-dependent failures. Runtime invariant assertions were equally important: Jepsen tests can reveal that a cluster is misbehaving, but not why. The crashes triggered by those assertions gave investigators a direct path to the underlying flaw. RethinkDB plans to add more such assertions going forward.

The deeper lesson is a familiar one for distributed systems. Even with a peer-reviewed consensus protocol and careful implementation, problems can emerge at the boundary surrounding the algorithm—the layer that manages node lifecycle rather than the consensus logic itself. Similar issues appeared in etcd and Consul, where write ordering was sound but coupling reads to local leader state allowed stale reads. In RethinkDB’s case, the Raft implementation’s assumptions about stable, persistent storage for each node were quietly violated by the node management layer’s exception to its own ordering rules. Runtime invariant checking, backed by generative testing, remains one of the most effective ways to uncover such subtle faults before they reach production users.