Compare-and-Swap Retry Loops and the ABA Problem on a Versioned Register

A coordination service without conditional writes is a bulletin board: clients can publish state and read state, but they cannot change state only if it has not changed underneath them. Conditional writes are what let a client act on a decision it made from an earlier read, and the standard form of that operation compares the whole stored value rather than a version number. Comparing the whole value is convenient and, in the presence of delete-and-recreate cycles, unsound.

The loop, and the assumption inside it

The pattern is a read-modify-write loop. Read the current value and its version, compute the desired new value, attempt a write that is conditional on the version still being the one read, and if the condition fails, start over. The loop terminates when a write succeeds or when the client decides the state has diverged too far from what it expected and gives up.

The assumption is that a failed condition means someone else wrote between the read and the write, so recomputing from a fresh read is the right response. That assumption holds when the state only moves forward and when every observed value is a consequence of the values before it. It fails when the value can return to a previously observed form. A cell that holds {"owner": "none"} can be read as none, written to {"owner": "A"} by another client, and then reset to none when A’s session expires, all between one client’s read and its write. The stale client’s conditional write then succeeds, because the value matches what it read, and it reinstalls a decision that was computed against a state that no longer exists.

This is the ABA problem, and the fix is to make the comparison include something that never repeats. A version counter that increments on every modification, including modifications that restore an earlier value, makes the stale client’s expectation (none, v3) while the cell is at (none, v7), and the write is refused. The client re-reads, sees the newer version, and recomputes. The version need not be meaningful; it need not reflect time, count operations of any particular kind, or be comparable across cells. It only has to change on every write, and it has to be assigned by the service so that two clients cannot choose the same one.

type Cell struct {
	Value   string
	Version uint64 // assigned by the service on every successful write
}

// Store is the service's conditional-write interface: the comparison and the
// write are one server-side operation, which is the whole point.
type Store interface {
	Read(path string) (Cell, error)
	CompareAndSwap(path string, expect uint64, v string) (Cell, bool, error)
}

// Update applies f to the cell until a conditional write succeeds. f returns
// the value to store, and false if the observed state needs no change.
func Update(s Store, path string, f func(Cell) (string, bool)) error {
	for {
		cur, err := s.Read(path)
		if err != nil {
			return err
		}
		next, change := f(cur)
		if !change {
			return nil
		}
		_, ok, err := s.CompareAndSwap(path, cur.Version, next)
		if err != nil {
			return err
		}
		if ok {
			return nil
		}
		// Version moved: recompute from the state we just failed against.
	}
}

What the version does not cover

A version number protects a single cell. It does not protect a decision that depends on several cells, and multi-cell updates are where most coordination logic actually lives. A 64-bit counter is the usual width, which makes wraparound a theoretical rather than practical concern, but the width does not help with the composition problem: a version on cell A says nothing about cell B. Moving a partition from one owner to another involves writing the new owner’s assignment, clearing the old owner’s assignment, and updating a generation counter, and those three writes must appear to other clients as one transition rather than three.

The service-side answer is a multi-operation that the service linearizes as a unit, with a single version check covering the whole set. The client-side answer is to order the writes so that intermediate states are safe, and to include the generation counter in every conditional so that a partially applied transition is detectable. Neither is free. The multi-operation holds a service-side lock across all the paths involved, which makes it a point of contention and a potential deadlock source if two clients take the same multi-path lock in different orders; the ordered individual writes expose intermediate states to readers and require every reader to understand them.

A version number also does not protect against a client that reads a valid version, stalls, and then writes. The conditional write succeeds because the cell has not changed, and the client’s decision is applied long after the state it was based on was still current. This is not the ABA problem, since nothing changed and changed back; it is a stale-decision problem, and the fix is a lease or an explicit deadline carried in the value rather than a version check. A client that holds a lock with an expiry should verify the expiry has not passed before writing, and the resource should reject writes carrying an expired grant.

Contention and the cost of retrying

Under low contention the loop is cheap: one read, one conditional write, two round trips, done. Under high contention it degrades in a way that is worse than its cost suggests, because every failed attempt is wasted work and because the failures are not independent. When many clients contend for the same cell, the winner’s write invalidates every other client’s read, so the losers all retry, and the next winner invalidates them again. Throughput does not merely plateau; it can fall as the number of contenders rises, because each successful write is surrounded by a growing number of doomed reads and failed conditional writes.

The standard mitigations are backoff and queueing. Backoff spreads the retries so that contenders do not all re-read at the same instant; a randomized delay proportional to the number of failures, capped, is enough to break the synchronization. Queueing removes the contention entirely by making clients take a ticket: instead of racing on one cell, each client creates a node whose sequence number is its position, and only the client at the front attempts the operation. That is the mechanism behind fair lock queues built from sequential nodes, and it trades a small fixed cost per waiter, one node creation, for the elimination of retry storms.

There is a third mitigation that is often the right one: change the data model so that the contended cell is not a single cell. A counter can be sharded across several cells and summed on read; a set of members can be a directory whose children are added and removed independently, so that two joins do not conflict. Both convert a serialized update into independent updates, at the cost of making reads more expensive and making multi-cell invariants approximate. Whether that is acceptable depends on whether the invariant needs to hold at every instant or only eventually, and the distinction should be made explicitly rather than discovered after the sharding is in place.

Optimistic versus pessimistic

A conditional write is optimistic concurrency control: no lock is taken, and conflicts are detected at write time. The alternative is to take a lock first, then write freely, then release. Pessimistic control avoids wasted work but pays for the lock acquisition, holds service-side state for the duration, and introduces the possibility that the holder dies and the lock must expire. For a short critical section with low contention, optimistic is usually better; for a long critical section with high contention, the retry storm is bad enough that queueing wins.

The decisive factor is often not throughput but the shape of the work. A client that can compute its new value cheaply from a read should retry; a client that must perform an expensive external side effect, such as writing to a storage system or sending a message, must not, because a retry after the side effect has already happened will duplicate it. In that case the write must be preceded by a durable record of intent, or the side effect must be idempotent, or the operation must be guarded by a lease so that a second attempt can recognize that the first one already ran. This is the boundary where a coordination service stops being sufficient on its own and where the protected resource’s own protocol has to take over.

Ordering of operations within a session

A subtle property of real services is that operations issued by one client on one connection are applied in the order issued. A client that writes a cell and then reads it back sees its own write, and a client that issues two conditional writes in sequence knows the second was evaluated after the first. That property is what makes a multi-step protocol expressible without extra synchronization: the steps are ordered by the connection, and the client can rely on the intermediate state being its own.

The property does not extend across connections. If a client’s connection breaks and it reconnects, operations in flight on the old connection may be applied before or after operations on the new one, and the service’s own guarantee is only that the order is consistent with the linearization points. A client that reconnects mid-protocol must therefore re-read the state and determine where it left off, rather than assuming its earlier writes were applied in the order it sent them. Session identity helps, because the service can reject operations from a superseded connection, but it does not make the reconnect transparent.