Write contention and the CRDT alternative

When two clients update the same key at the same time, you face a write contention. The standard toolkit ranges from strong consistency (locking, optimistic concurrency, Paxos, two-phase commit) to AP-style systems where both writes are accepted and reconciled later. If that reconciliation is monotonic, the system is eventually consistent.

Timestamp-based last-write-wins is the simplest resolution rule, assuming clocks are synchronized more tightly than the interval between conflicting writes. But it is not always correct. If you are storing a set of 500,000 followers for an account and two people follow it at the same time, last-write-wins can drop one of them. At Showyou, this occurred in about 1% of follower lists. OR-sets—a class of CRDT—solve the problem by reducing contention to individual elements instead of the entire set, but they have only been formally described for a couple of years.

Locking on top of Riak

Assume instead that you serialize writes with a lock service. Before writing an object, a client acquires a lock from a reliable network service, performs the Riak write, and releases the lock. With tightly synchronized clocks and aggressive monitoring, no two clients write concurrently and write contention is eliminated—in theory. In practice, this does not prevent write contention.

The coordinating node for a write computes the preflist for the key and, with replication factor N=3, sends the write to three vnodes. It waits for W=(N/2+1) confirmations and DW=(N/2+1) confirmations that the write is on disk. A node crash or partition during this window does not cause a conflict, because the lock service prevented one; the crashed node's old value is discarded once it returns. The guarantee requires that every read checks at least R=(N/2+1) copies so a new copy can win conflict resolution. Reading with R=1 can surface a days-old copy from a crashed node, and writing that data back would obliterate days of writes.

The partition problem

Now consider a node that fails to respond because of a partition, not a crash. On the other side of the partition, other parts of the app are also adding followers. The coordinator completes two of three writes, and because W=quorum, the client is told the write succeeded. Riak detects the partition and spins up new vnodes on both sides. Each side now has a complete set of vnodes, and writes to either side succeed even with W=DW=quorum or W=all.

When the partition resolves, the most recent timestamp decides which copy wins. Writes on the losing side are lost despite being acknowledged. W & DW >= quorum is insufficient; you need PW >= quorum so writes to fallback vnodes are treated as failures. But that only tells the client the write failed. The fallback vnodes still accepted the write and stored it. Those writes can win last-write-wins when the partition heals, obliterating acknowledged writes from the primary side—or the primary side wins and minority writes are lost. Either way, data is guaranteed to be lost.

This scenario never requires two writes to happen simultaneously. The lock service is working as intended, keeping writes sequential. The point: simultaneous is about causality, not clocks. For the lock service to help, it must understand the partition shape. Events on both sides of the partition are concurrent from Riak's perspective, so granting locks to the minority side breaks mutual exclusion in the logical history of the object.

The lock service must therefore be distributed and isomorphic to the Riak topology—partitioned in the same way Riak is—so it can identify safe and dead nodes. Clients must acquire locks for hosts, not just keys. One option is to build locking into Riak itself (which jtuple has explored), or run a consensus protocol like Zookeeper on the Riak nodes.

With that in place, a partition shuts down the minority side. This is consistent and unavailable in the CAP sense, but the load balancer can route to the majority partition.

Quorums are not what they seem

The notion of a "larger" side is murky with vnodes. Key "A" might live on nodes 1, 2, and 3; "B" on 3, 4, and 5; "C" on 6, 7, and 8. A partition separating nodes 1-4 from 5-8 leaves the first side with all copies of A, one of B, and none of C. There are M ensembles (M = ring_size). Fallback vnodes spin up for the missing ring sections, but they may have no data. Without PR >= quorum, you could read an outdated object—or get a not_found when the data exists. Treating a not_found as an empty set and adding a user would overwrite the entire record when the partition resolves, losing half a million followers except for the one you just added.

Because M ensembles partition in varying ways, no authoritative side can keep running. The system must either shut down entirely or let some fraction of requests fail—the fraction depends on ring size, node count, replica count, and partition shape. Multi-key operations fail rapidly as the number of keys grows. This is not high availability, even with a perfect coordination service: if more than N/2+1 nodes are partitioned, failure is partial or complete.

Partial failure is not really an option. If the cluster partitions after a read, subsequent writes still go to fallback vnodes, and PW does not stop them—it only returns an error code. Those writes sit in the minority cluster until resolution, where they conflict with their siblings. The only correct solution is shutting down everything during the partition, assuming you can reliably detect it.

Partitions happen—in more ways than you think

Network reliability cannot be assumed. In EC2, partitions occur. On dedicated hardware in a single rack with redundant bonded interfaces and meshed switches, you still face asymmetric partitions from firewall changes, Erlang cookie changes, and NIC driver bugs under load. A node that hangs on compaction or list-keys can cause timeouts that make other nodes consider it down, leading to failover and rolling brownouts lasting hours—with an unclear window during ring convergence.

Recovery from backups is another partition. With n_val=3, you restore at most one node at a time and read-repair every key afterward. Restoring two old nodes—or skipping read-repair—can let two copies of stale data form a quorum and be written back. The author has done this to millions of keys.

Partitions are about lost messages, not just the network. They appear in unexpected places, and planning for them makes Riak CP to a decent approximation. Otherwise, the assumptions that prevent write contention collapse.

Why Last-Write-Wins Loses Data

At first glance, the data loss we kept hitting seems impossible. Riak is eventually consistent — it should converge. The locking service is rock solid. So why do writes keep vanishing?

The answer lies in what "convergence" actually means. Eventually consistent systems are monotonic: they move steadily toward the most recent state, driven by message flow. They never regress to an older causal version. With vector clocks identifying conflicts and a monotonic resolution function, convergence is guaranteed.

Last-write-wins (LWW) is, on paper, a perfect monotonic function. It is associative, commutative, and idempotent — the order in which versions arrive doesn't matter. Riak will always converge on the value with the highest timestamp.

But monotonicity does not imply information preservation. A function like f(a, b) = 0 is also associative, commutative, and idempotent — and it destroys every input. LWW behaves the same way. It is a monotonic convergence function that, regardless of message order, can burn away knowledge like the Library of Alexandria. Write a value, write an older timestamp over it, and the first write is gone forever — no matter how the system reorders or retries.

When Convergence Is the Wrong Tool

LWW is only appropriate when the client can be certain that the currently read state is the correct, complete state. That's rarely the case in practice, because most application servers are deliberately stateless. State belongs to the database. The app server reads a value, mutates it (say, adding a follower), and writes the result back. Under that pattern, LWW is a razor's edge — a single stale read or misordered write permanently loses data.

Eventual consistency is not the culprit. Had we merged our follower lists using set union instead of replacing the whole list, every failure mode in this saga would have disappeared. The system's convergence would preserve our writes even during partitions. Deletes remain possible, over a time horizon, by coordinating through the lock service and a queue.

Structured Merges Instead of Blind Replacement

A straightforward fix is to model updates as operations. Represent a follower set as a log of follow and unfollow events with timestamps, and merge by union on conflict. The statebox library takes this approach. If the coordination service stamps those operations, you recover apparent serializability — albeit not full CP semantics — and Riak's eventual consistency guarantees preserve every write up to N-1 simultaneous failures, depending on your r/pr/w/pw/dw settings. Such a system can remain highly available so long as both sides of a partition retain a path and load balancers behave. Without a coordination service, correctness depends on clock accuracy; GPS offers 100-nanosecond precision and NTP may suffice.

Alternatively, use an observed-remove set (OR-set). Reference implementations run to about 130 lines of Ruby, so a working version with tests can be built in days, or you can adopt an existing library such as Eric Moritz's CRDT or knockbox. Unlike LWW, OR-sets require no coordination service and do not depend on reliable clocks. For highly available, eventually consistent stores, they are the natural choice.