RethinkDB’s consistency model

RethinkDB is an open-source document store that shards data by primary key and keeps replicas across nodes. Each shard has a single designated primary that serializes all updates and strong reads to that shard’s documents. Documents are hierarchical, dynamically typed objects uniquely identified by an id key within a table, and only operations on a single document are atomic—queries touching multiple keys may read or write inconsistent data.

The big architectural change in RethinkDB 2.1 was automatic primary promotion using the Raft consensus algorithm. Every node hosting a shard maintains a Raft ensemble that stores table membership, shard metadata, primary roles, and related state. This enables automatic promotion of a new primary replica whenever a majority of the table’s nodes are fully connected and a majority of the shard’s replicas are available to that majority component. So a three-node cluster with three replicas per shard can tolerate one node failure; five replicas tolerate two, and so on. RethinkDB also supports non-voting replicas that asynchronously follow normal replicas, aren’t eligible for promotion, and don’t participate in the Raft ensemble; these don’t provide the usual consistency guarantees and are suited to geographic redundancy or read-heavy workloads where consistency isn’t critical.

Before 2.1, losing a primary meant operators had to remove the dead node and promote a replica by hand. Because every node is typically primary for some shard, dropping any single node rendered roughly 1/n of the keyspace unavailable. With automatic promotion, a standard 3×3 table survives single-node loss or isolation.

Consistency knobs and their defaults

This analysis concerns only single-key consistency, since RethinkDB—like MongoDB, Riak, and Cassandra—offers no atomic multi-key operations. The defaults favor strong writes and weak reads. Updates are linearizable by default, appearing to take effect atomically at some point between request and acknowledgement. Reads, however, default to being serviced by any primary from its in-memory state, which can return stale or dirty values.

Write safety is enforced at the table level through the write_acks setting rather than per transaction, avoiding confusing interleavings of weakly and strongly isolated writes:

  • single: a primary acknowledges a write without waiting on other replicas
  • majority: a majority of replicas must acknowledge before the write is confirmed

The distinction affects only latency, not throughput; writes always go through a primary, so majority write availability requires a quorum regardless. This differs sharply from AP databases like Cassandra or Riak, which offer total write availability at the price of weaker consistency.

Read safety, by contrast, is a per-request decision via the read_mode parameter:

  • outdated: the local in-memory state of any replica
  • single: the local in-memory state of any replica that believes it is primary
  • majority: values safely committed to disk on a majority of replicas

outdated and single are probably equivalent in safety guarantees, except that outdated shows anomalies constantly while single tends to show them only during failures. outdated improves availability and throughput by letting all replicas serve reads. majority offers linearizable reads but requires a sync request to every replica, with a majority needing to respond before the result is returned; that extra round trip is unavoidable for any linearizable operation.

w=single w=majority
r=outdated Lost updates, dirty reads, stale reads Dirty reads, stale reads
r=single Lost updates, dirty reads, stale reads Dirty reads, stale reads
r=majority Lost updates, stale reads Linearizable

What can go wrong

The documentation claims that majority/majority guarantees linearizability. The remaining combinations are more fragile. Relaxing writes to single permits an isolated primary to accept and acknowledge a write that another majority never sees; that write can later be lost, and a subsequent majority read may return an older value. Dirty reads are unlikely with r=majority, since a read against the isolated primary would fail.

Strong writes with weak reads also leave room for anomalies. With w=majority, writes must be acknowledged by a majority and hence survive election of a new primary. Yet stale reads still occur if an isolated primary (or any node under r=outdated) serves requests while a newer primary accepts writes. Dirty reads are possible too: a single or outdated read could observe a write that is propagating to replicas but hasn’t yet received acknowledgement from a majority. If that acknowledgement never comes and a new primary is elected without the write, the operation would be reported as failed even though a client saw its effect.

Finally, with both w=single and r=single, all the above failure modes—lost updates, plus dirty and stale reads—appear together.

Test setup

To probe whether RethinkDB delivers on linearizable majority/majority operations and to see whether the weaker modes produce real or merely theoretical anomalies, Jepsen used the standard install: add RethinkDB’s Debian repository, install the rethinkdb package, and configure a log file. Clock synchronization was avoided with a libfaketime shim that skews clocks and runs time at different rates per process.

The test configuration was built from the stock config, then tuned to maximize leadership transitions in a short window by lowering the heartbeat timeout to two seconds once the cluster was up. Jepsen handled installation, configuration, startup, log and data cleanup between runs, and log collection at the end of each test. After starting the database, Jepsen waited for connections to every node before beginning a run.

Operations

Jepsen clients translate invocation operations into requests against the system under test and report completion operations back to the checker. For RethinkDB, individual operations are writes, reads, and compare-and-set (cas) ops over small integers, constructed via generator functions for each client process. Typical examples include a write like {:type :invoke, :f :write, :value 2} or a compare-and-set like {:type :invoke, :f :cas, :value [2 4]}, which atomically sets the value to 4 when the current value is 2.

Prior Jepsen analyses exercised a single key for the whole test. That approach works but degrades as the test runs: processes time out or crash over time, and it becomes impossible to know whether a dead process’s operations will ever apply. The number of concurrent pending operations rises, and the space of possible interleavings grows exponentially. With more than a few crashed processes, proving linearizability can take years. That places hard bounds on test duration and request rate, which makes anomalies harder to surface.

A redesigned Knossos linearizability checker, based on Gavin Lowe’s linear algorithm, brought substantial speedups to pathological histories. The just-in-time partial order reduction proposed by Lowe is augmented with a precomputed state space for the model: configurations are explored without invoking model transitions or allocating objects, hashcodes are precomputed, and reference equality replaces Lowe’s union-find structure. Best of all, deterministic state transitions let the checker skip equivalent configurations, pruning the search space dramatically.

Yet even these optimizations cap out at roughly 100 seconds of test history. That limitation proved removable with a different analytic lens: rather than tracking one register for the whole test, tests can operate across several distinct keys, analyzing each key’s history independently. Linearizability violations tend to occur on short timescales, so each individual key’s history remains tractable while the overall test exposes the system to tens or hundreds of times more operations—and correspondingly more chances to observe misbehavior. To support this pattern, the jepsen.independent namespace lifts operations on a single key into operations on [key value] tuples. A sequential generator emits a one-per-second mix of reads, writes, and compare-and-set operations for each integer key over a sixty-second window, then advances to the next key.

Ten client processes split their time between these streams: five are reserved for a random mixture of writes and compare-and-set operations, while the remaining five perform only reads. This reservation is essential for spotting dirty and stale reads. When the network partitions, updates stall for 5–10 seconds while the database loses a majority. If every process were to attempt writes, the whole cluster would periodically block on leader election and no operations—including reads—would complete. A dedicated read pool keeps observing the cluster through these transitions, revealing transient consistency failures that would otherwise escape detection.

Client Semantics and Error Handling

One client bootstraps the test by creating a fresh table on the cluster, configured with one replica per node (five total), and waits for that configuration to propagate. The table’s write-acks level is set top-of-test; that setting controls a small class of behavioral differences across runs. After setup, the client decomposes the [key, value] tuple from each operation and builds a Rethink query for the relevant document using the chosen read mode.

Read operations execute a simple get query that extracts the single val field, returning that value as the operation’s result. Writes issue an upsert with conflict: update to set the same field. Compare-and-set operations rely on Rethink’s functional API: an update against the row query takes a function of the current document, which compares the existing val to the cas predicate. On a match, the function returns value'; otherwise it aborts. Rethink replies with counts of replaced rows and errors, and the client uses those counts to decide whether the compare-and-set succeeded.

This functional style is more verbose than a native compare-and-set primitive, but Rethink’s query language composition, control flow, and first-class functions give fine-grained control over single-document mutations. Shipping logic into the database reduces round trips and improves locality, much like stored procedures in SQL systems. The API and AST also resemble the serialization format, which is easier to wrap in parameterized queries than the constant string-building common to SQL clients. The gap, however, is multi-document control: absent such concurrency control, safely reading one document and using it to update another—or guaranteeing the atomic visibility of two updates—is not generally possible.

RethinkDB distinguishes failed from indeterminate operations via a dedicated status code, and Jepsen traps these via a small macro that constructs an appropriate completion: definite failures become :fail; potentially-failed requests become :info. Since reads are pure, all read errors are conservatively treated as outright failures, reducing the number of crashed operations and the resulting load on the checker. Return values bear inspection as well: catastrophic cases throw, but to support partial failures Rethink’s client can also return maps containing error counts for some errors.

Availability During Partitions

Tests ran for 500 seconds while cutting the network in half every ten seconds. Partial isolation, SIGSTOP/SIGCONT, and single-primary isolation all produced results indistinguishable from the simple majority/minority split, so the simpler strategy stands. Shorter partition intervals force Rethink through multiple leader timeouts and elections, confusing it longer, but it reliably recovers once it sees a stable configuration for roughly heartbeat_timeout + 10 seconds—and often before that.

Latency traces over those 500 seconds show healthy operation shortly after each partition starts: blue ops succeed, red ops fail, and purple ops sit in the uncertain middle. Each cut induces roughly 2.5 seconds of elevated latency; after cluster reconfiguration, a few transient errors appear for all three operation classes, followed by partial errors until the partition heals.

Why partial failures rather than clean outages? Reads and writes require acknowledgment from only a single node, but Rethink routes them through the primary—and immediately after a partition, some nodes can neither reach the primary nor elect a new one. Single-node acks for single writes therefore offer no availability advantage while the minority side is cut off.

Majority reads widen that window: a majority read is implemented by issuing an empty write to confirm the primary is still legitimate. Read latencies, formerly two-to-three times faster than writes, rise to the level of write latencies. The difference is more visible in latency than in availability, because majority writes and single writes both depend on reaching a primary; majority state is required to have any primary, so writes of either sort wait for the same cluster quorum. In this low-latency network, other costs dominate the throughput difference.

Anomalies Under the Hood

With failover confirmed to complete within seconds of a partition, the next question is whether those transitions preserve safety. Testing across the four combinations of write_acks (single or majority) and read_mode (single or majority) reveals exactly which consistency guarantees hold during these shifts. Only the majority/majority pairing appears to be linearizable.

Single Writes, Single Reads

A history fragment captured just after a partition begins shows the kind of subtle breakage that can occur. In this excerpt, one process reads 0, another successfully writes 3, a third reads that 3, and then, unexpectedly, a fourth process reads 0 again—a value that should no longer be current.

9	:ok	:read	[15 0]
...
194	:invoke	:write	[15 3]
7	:fail	:read	[15 nil]	"Cannot perform read: lost contact with primary replica"
292	:info	:cas	[15 [0 1]]	"Cannot perform write: lost contact with primary replica"
194	:ok	:write	[15 3]
141	:info	:write	[15 3]	        "Cannot perform write: lost contact with primary replica"
6	:fail	:read	[15 nil]	"Cannot perform read: lost contact with primary replica"
8	:fail	:read	[15 nil]	"Cannot perform read: lost contact with primary replica"
373	:info	:cas	[15 [1 0]]	"Cannot perform write: lost contact with primary replica"
5	:invoke	:read	[15 nil]
5	:ok	:read	[15 3]
170	:invoke	:cas	[15 [1 4]]
170	:info	:cas	[15 [1 4]]	"Cannot perform write: The primary replica isn't connected to a quorum of replicas. The write was not performed."
9	:invoke	:read	[15 nil]
9	:fail	:read	[15 nil]	"Cannot perform read: The primary replica isn't connected to a quorum of replicas. The read was not performed, you can do an outdated read using `read_mode=\"outdated\"`."
7	:invoke	:read	[15 nil]
302	:invoke	:cas	[15 [0 0]]
7	:ok	:read	[15 0]
194	:invoke	:cas	[15 [3 0]]
302	:fail	:cas	[15 [0 0]]
194	:info	:cas	[15 [3 0]]	"Cannot perform write: The primary replica isn't connected to a quorum of replicas. The write was not performed."
151	:invoke	:cas	[15 [1 0]]
6	:invoke	:read	[15 nil]
6	:ok	:read	[15 0]

The anomaly is easy to miss by eye, but it is unambiguous: the later read of 0 is impossible to linearize with the earlier read of 3 unless some intervening write toggles the value back. Jepsen's analyzer flags this and can identify which crashed operations were pending at the moment of the illegal read:

  :failures
  {15
   {:valid? false,
    :configs
    ({:model   {:value 3},
      :pending [{:type :invoke, :f :read, :value 0,     :process 7,   :index 78}
                {:type :invoke, :f :cas,  :value [1 4], :process 170, :index 74}
                {:type :invoke, :f :cas,  :value [1 0], :process 373, :index 48}]}
       ... a few dozen other configurations
      })
    :previous-ok {:type :ok, :f :read, :value 3, :process 5, :index 73},
    :op          {:type :ok, :f :read, :value 0, :process 7, :index 80}}}},

To make the failure easier to trace, a visualizer renders the history with time flowing left to right. Each horizontal track represents a single process; bars indicate operation start and completion, colored green for successful ops and yellow for crashes. If a history is linearizable, a path can be drawn strictly moving right that touches every green operation—and possibly crashed ones, since they may have taken effect. Such legal paths appear in black, with their resulting states drawn as vertical lines. Illegal transitions show in red.

In this case, no legal path exists. The crashed operations from earlier in the history—a write of 3 and several compare-and-set operations—can't bridge the gap between a read 3 and a later read 0. The read of 3 is either a lost update or a stale read, both expected when consistency is weak.

Single Writes, Majority Reads

Moving to majority reads while keeping single writes still leaves the door open to lost updates. A successful write of 1 by process 580 is followed by two operations that complete requiring the value to be 3—yet no crashed operation could have produced that state. The write of 1 effectively vanished. This happens when a primary acknowledges a write before fully replicating it, then loses leadership before that write propagates.

{:valid? false,
 :previous-ok {:type :ok, :f :write, :value 1, :process 580, :index 181},
 :op          {:type :ok, :f :read,  :value 3, :process 8,   :index 200}}}},
 :configs
    ({:model {:value 1},
      :pending [{:type :invoke, :f :read, :value 3,     :process 8,   :index 199}
                {:type :invoke, :f :cas,  :value [3 4], :process 580, :index 196}
                ... eighty zillion lines ...]})}

Majority Writes, Single Reads

The opposite pairing—majority writes with single reads—also yields linearizability violations. Before a partition, the register holds 0. A few crashed writes of 1 become visible to some processes, but a later operation still reads 0. The likely sequence: a primary accepts a write of 1, that state becomes visible to other nodes just before the primary is partitioned, and the write crashes because its acknowledgement never returns. Until the old primary steps down, reads on that side of the partition see the uncommitted state—a dirty read. Once a new primary takes over without that write, the value reverts to 0.

8       :ok     :read   [10 0]
...
133     :invoke :write  [10 1]
131     :invoke :write  [10 1]
:nemesis        :info   :start  "Cut off {:n4 #{:n3 :n2 :n5}, :n1 #{:n3 :n2 :n5}, :n3 #{:n4 :n1}, :n2 #{:n4 :n1}, :n5 #{:n4 :n1}}"
5       :invoke :read   [10 nil]
5       :ok     :read   [10 1]
9       :invoke :read   [10 nil]
8       :invoke :read   [10 nil]
8       :ok     :read   [10 1]
5       :invoke :read   [10 nil]
5       :ok     :read   [10 1]
8       :invoke :read   [10 nil]
8       :ok     :read   [10 1]
...
5       :invoke :read   [10 nil]
5       :ok     :read   [10 1]
...
6       :invoke :read   [10 nil]
141     :invoke :cas    [10 [4 0]]
6       :ok     :read   [10 0]

Majority Writes, Majority Reads

Across hundreds of runs with majority/majority, varying timescales, request rates, concurrency levels, and failure types, no linearization failures appeared. Combined with hard durability, single-document operations under these settings appear safe.

Practical Implications

RethinkDB's documented safety claims hold up: anything less than majority writes risks lost updates, and single or outdated reads permit a range of anomalies from dirty to stale reads. The defaults provide linearizable writes—including compare-and-set—but allow stale reads, which is often a reasonable latency tradeoff.

The real hazard is in read-modify-write cycles built on weaker read modes. Rendering a page from a stale or dirty read could prompt a user action that writes invalid data back. Similarly, inter-process state handoffs through the database can corrupt or lose state when reads are stale. These sidechannels deserve close attention.

Where such anomalies matter, majority reads eliminate the problem without a significant availability cost, though read latency rises. Conversely, if read performance is the priority, outdated reads offer essentially the same safety as single—with the difference that anomalies become continuous rather than occasional.

Assessment

RethinkDB's consistency documentation is solid, though it stops short of enumerating the specific read anomalies permissible under weaker settings. The client API could be improved by standardizing on checked or thrown errors instead of a mix, which risks callers missing errors when exceptions aren't thrown. The newer Clojure client's error codes for indeterminate versus definite failures are welcome despite requiring knowledge of magic constants.

Earlier releases demanded manual operator intervention on network or node failures, which made recommending RethinkDB difficult. Version 2.1's automatic failover converges promptly and its safety invariants appear to hold under partitions. For applications needing a schemaless single-key document store without inter-document consistency requirements, RethinkDB is a reliable choice. MongoDB offers comparable options for stronger read consistency with similar data models and availability profiles.

For multi-key consistency, a configuration store like Zookeeper or a synchronously replicated SQL database such as Postgres is a better fit. Where availability trumps all else, an AP document store or KV store—Couch, Riak, or Cassandra—merits consideration.

Reproduction requires setting up a Jepsen cluster, checking out the Jepsen repository at 6cf557a, and running lein test in the rethink/ directory. All four read/write combinations are executed, with analyses output to store/. The test depends on unreleased features from clj-rethinkdb 0.12.0-SNAPSHOT, which can be built locally via lein install.