Optimistic Concurrency and the Conflict Check That Arrives Too Late

Every replicated data store faces the same fork. A write can be admitted as soon as it reaches one node, or it can be held until a quorum agreed on ordering. The first choice is fast and allows progress when the network is partitioned, which is often the whole reason the store exists. The second is safe and can block indefinitely. Optimistic concurrency is the family of designs that take the first branch and pay for it later, by detecting conflicts after they have already been admitted, and it consistently turns out that “later” is too late for the thing users most want protected.

Where the version token actually goes

The canonical optimistic mechanism is a version token, sometimes a counter, sometimes a vector of per-replica counters. A client reads a record; the read returns the value together with a token. The client modifies the value and submits it back with the token. The accepting node compares the presented token against the record’s current token. If they match, the write is sequenced after the version the client saw, and the token advances. If they differ, the write is rejected and the client is expected to re-read and retry.

The critical detail is what “rejected” means. It does not mean the write was rolled back. It means this particular replica declined to sequence it after a version it did not observe. In a quorum-replicated system with a single ordering authority, this reduces to compare-and-swap with an honest serialization point, and the mechanism is genuinely safe. In a system where multiple replicas can accept writes independently, the token comparison happens at each acceptor, at different times, against different local states. Two replicas can each accept a write against the same base version and each be locally correct. The conflict exists only in the union.

Bayou, developed at Xerox PARC in the mid-1990s for weakly connected mobile clients, is the clearest documented articulation of the problem. Sessions are allowed to read and write while disconnected; each write carries a dependency check recorded when the write was first accepted, and later, when sessions merge, those checks are re-evaluated against the merged state. A dependency check that no longer holds means the write’s premise was false at the point of application: the seat was already taken, the document section was already edited, the inventory had already gone negative. The system can detect that with certainty. It cannot undo the fact that the user was told the operation succeeded.

The failure is a promise, not a write

The instinct on first encountering this is to treat the discarded write as the loss. That framing is wrong and leads to the wrong fixes. The discarded write is cheap; a few hundred bytes that never reached a second replica. What was lost is the acknowledgement, and acknowledgements propagate outward into every external effect the client performed on their basis.

A mobile sales application accepts an order while disconnected, prints a receipt, and moves the customer’s money. The conflict is discovered hours later when the device reconnects and the item’s stock has been exhausted by another session. The write is rejected. The receipt is paper. Rejection and rollback are different operations, and only the first is available.

Coda, the predecessor of the Coda filesystem’s disconnected operation model, made this explicit for files. During disconnection, a client with a cached copy is permitted to open, modify and close files, producing local logs of modifications. On reconnection, Coda compares modification logs against the server’s state. Files that changed on only one side are simply merged or transferred. Files changed on both sides are placed in what Coda called conflict files: both versions are preserved, side by side, and the user is notified. The system never pretended the merge succeeded. It moved the ambiguity into the namespace, where it became a visible object rather than a silent overwrite.

That design choice, preserving both versions rather than picking a winner, is the honest form of optimistic concurrency. Any design that resolves a conflict by silently choosing one branch, whether by last-writer-wins timestamps or by replica identifier tiebreak, converts a detectable conflict into an undetectable semantic error.

Timestamps are not versions

A single scalar timestamp is tempting because it makes comparison trivial and last-writer-wins resolution automatic. It also fails in ways that are invisible from inside the system. Clocks on different hosts disagree, so a write made later in real time can carry an earlier timestamp and lose. A clock adjustment can move backwards and cause a previously ordered pair to reorder. Clock skew on the order of seconds is ordinary on commodity hardware without specialized synchronization, which means two writes separated by a fraction of a second may be ordered arbitrarily.

Version vectors replace the single clock with one counter per replica. Write A happened-before write B exactly when A’s vector is pointwise less than or equal to B’s and strictly less in at least one component. When neither vector dominates, the writes are concurrent, and the system knows it knows them to be concurrent, because domination failure is a positive signal rather than an absence of one. This is the formal content of causality that a timestamp throws away.

The vector does not resolve conflicts either. It tells the system when it must ask, which is exactly the condition the timestamp resolves away.

Why optimistic check-and-retry leaks at the edges

The retry loop looks harmless in isolation. Read token, attempt write, on mismatch re-read and try again. Under contention it produces the familiar pathology: two clients retrying against each other converge only if the rate of conflicts decreases, and near-saturation it does not. Livelock is possible and no individual client can escape it alone.

The more serious problem is that the retry loop requires the client to hold the whole transaction. Any system that exposes optimistic concurrency at the storage layer while permitting side effects between the read and the write has exported its consistency problem to the application, and the application rarely implements the rollback that would make it sound.

This is the structural reason quorum systems with genuine ordering authorities exist at all, and why the version-token pattern survives mostly inside single-node database engines, where the token comparison and the write are under one lock. The token is not the flaw. The flaw is the assumption that a check that runs at a different place and time than the write can still be called a check.

For the correct reading of these systems, the useful habit is to ask a specific question of any optimistic design: after the conflict is detected, which external promise was already made? The Bayou work answered it by narrowing the writes it would accept to ones with reproducible merge procedures; Coda answered it by refusing to guess. Both traded availability of the merge for the availability of the guarantee. Related questions about when concurrency can be excluded at all are covered in Isolation Levels and the Anomalies They Permit.

The merge procedure as a precondition

Bayou’s other contribution is often quoted and rarely followed. It required that every write be accompanied by a merge procedure, an executable description of how to combine the operation with state it may not have anticipated. A counter increment merges by adding the two deltas. A calendar appointment merges by re-checking whether the invitee is still free. A text edit merges by transforming the offset against intervening edits.

The design constraint is stark: if a write cannot be described as a function of the state it lands on, the write cannot be replicated optimistically, because the system has no way to produce a sensible successor state when the write’s premise is stale. That rules out, by construction, most writes whose correctness depends on a read the client performed rather than on the state itself. Booking the last seat is not a mergeable operation. It is a condition, and a condition needs a point at which someone decides.

Following the rule has a cost that Bayou’s own authors documented: merge procedures are code, they run on committed data, and a bug in one produces a result no replica checked. The system’s consistency argument rests on the merge functions being deterministic and total, and enforcing that on application authors is not something a storage layer can do. Coda avoided the problem entirely by never merging file content, deferring the decision to the user, which is safe and also the reason conflict files were an operational burden rather than a feature users welcomed.

What the mechanism can honestly claim

Optimistic concurrency does one thing well: it lets a system make progress without coordination, and it can prove, for writes it can reason about, that one write did not see another. That proof is worth having. It is not the same as a guarantee about the outcome of a transaction that included the write.

The published Bayou and Coda designs both landed on the same boundary. Detection is cheap and can be exact. Repair is expensive and cannot be exact when it involves a human-facing promise. The version token belongs at the boundary where a client can still choose whether to act, not at the boundary where the action has already been taken.

Where the cost shows up in the token

Every version vector grows with the number of replicas that ever wrote to a record, not with the number currently live. Long-lived records in a large deployment accumulate components from replicas that have been decommissioned. Implementations prune by determining which components can no longer advance, which requires a membership protocol more sophisticated than the one that motivated optimistic replication in the first place. The representation chosen to avoid coordination eventually requires coordination to remain small.