Compare-and-Swap Explained: Lock-Free Retry Loops and ABA

Two threads add to the same counter and one of the additions vanishes. The textbook fix is a mutex around the update. Compare-and-swap, CAS, is the other fix: a single atomic instruction that writes a new value only if the location still holds the value you read, and tells you whether it did. It is the building block under atomic counters, lock-free queues, and the optimistic locking that databases use for rows. Interviewers bring it up to see whether you understand what "lock-free" actually promises, and whether you know the ABA problem.

The problem it solves

counter += 1 is three steps: read the value, add one, write it back. If two threads both read 10, both compute 11 and both write 11, one increment is lost. That is the lost update behind most race conditions.

A mutex makes threads take turns, but a thread holding the lock can be descheduled while everyone waits for it. Locks also bring deadlock risk as soon as there are two of them. CAS removes the waiting: nobody holds anything, and a thread that loses a race finds out immediately.

The intuition

CAS takes three arguments: an address, the value you expect to find there, and the value you want to write. In one indivisible step the hardware compares, and writes only if the comparison holds. It returns success or failure.

That turns an update into a loop:

1. Read the current value.
2. Compute the new value from it.
3. CAS: "write the new value if the old one is still there".
4. If the CAS failed, someone else changed it in between. Go back to step 1.

The comparison is the whole safety argument. A thread can only publish a value computed from the latest state, so no update is overwritten blindly. A failed CAS is not an error; it is news that the world moved, and the answer is to re-read and redo the computation.

Lock-free means the system as a whole always makes progress: whenever a CAS fails, it is because another thread's CAS succeeded. It does not mean no thread ever retries, and under heavy contention a thread can retry many times.

Then there is ABA. CAS compares values, not history. If the value goes from A to B and back to A while you were computing, your CAS succeeds, even though the state you reasoned about is gone. For a counter that is harmless. For a lock-free stack, where A is a pointer to a node that was popped, freed and reused, it corrupts the structure. The fix is to compare a version along with the value, bumping the version on every write, so "A again" no longer looks like "still A".

Watch it run

The animation has one shared cell holding ten, and two threads that both want to change it, with no lock anywhere. Both read it, and both now believe the current value is ten. Thread two computes its new value and swaps first, while ten is still true: the cell becomes 15. Thread one then offers its own swap, "set to eleven, if it is still ten". It is not. The hardware refuses the write, and says so rather than silently overwriting; the lost update is prevented. A failed swap is news, not an error: thread one re-reads, sees 15, starts again, and since nobody intervenes this time, the second attempt succeeds and the cell reads 16, both updates applied. Neither thread ever waited on the other; that is what lock-free means, and it does not mean nobody retried. The final frame shows the trap: if the value goes ten, fifteen, ten again, the compare succeeds on stale history, and the fix is a version stamp.

The code

Python has no CAS instruction for user code, so this is a toy model: a lock makes the compare-and-write indivisible, which is what the hardware guarantees in one instruction. First, the animation's race replayed in order:

import threading

class AtomicCell:
    """Toy model: a lock stands in for the hardware's single atomic instruction."""
    def __init__(self, value):
        self._value = value
        self._guard = threading.Lock()

    def load(self):
        return self._value

    def compare_and_swap(self, expected, new):
        with self._guard:
            if self._value != expected:
                return False               # somebody changed it: refuse, and say so
            self._value = new
            return True

cell = AtomicCell(10)
t1_seen, t2_seen = cell.load(), cell.load()        # both read 10
print(cell.compare_and_swap(t2_seen, 15))          # True   thread two: 10 -> 15
print(cell.compare_and_swap(t1_seen, 11))          # False  thread one expected 10
t1_seen = cell.load()                              # re-read: 15
print(cell.compare_and_swap(t1_seen, t1_seen + 1), cell.load())   # True 16

The retry loop, under four real threads doing 10,000 increments each. Nothing is lost:

def increment(cell):
    while True:
        seen = cell.load()                         # read
        if cell.compare_and_swap(seen, seen + 1):  # compute, then publish or retry
            return

counter = AtomicCell(0)
workers = [threading.Thread(target=lambda: [increment(counter) for _ in range(10_000)]) for _ in range(4)]
for w in workers: w.start()
for w in workers: w.join()
print(counter.load())                              # 40000

Thread timing is not reproducible, so the cross-check drives the interleavings itself: each thread is a generator that pauses between read and write, over 500 seeded random schedules. Plain read-then-write loses updates on some; the CAS loop never does, though it retries:

import random

def plain_steps(shared, n):
    for _ in range(n):
        seen = shared[0]
        yield                                      # another thread may run here
        shared[0] = seen + 1

def cas_steps(cell, n, stats):
    for _ in range(n):
        while True:
            seen = cell.load()
            yield                                  # another thread may run here
            if cell.compare_and_swap(seen, seen + 1):
                break
            stats["retries"] += 1

def run(seed, threads):
    rng, live = random.Random(seed), list(threads)
    while live:
        t = rng.choice(live)                       # one random interleaving per seed
        try:
            next(t)
        except StopIteration:
            live.remove(t)

lost_somewhere, cas_always_right, retries = 0, True, 0
for seed in range(500):
    shared = [0]
    run(seed, [plain_steps(shared, 5) for _ in range(3)])
    lost_somewhere += shared[0] < 15
    cell, stats = AtomicCell(0), {"retries": 0}
    run(seed, [cas_steps(cell, 5, stats) for _ in range(3)])
    cas_always_right &= cell.load() == 15
    retries += stats["retries"]
print(lost_somewhere > 0, cas_always_right, retries > 0)   # True True True

ABA, and the version stamp that fixes it. The plain cell accepts a swap on a value that changed and changed back; the stamped cell compares the version too:

class StampedCell:
    """Compare (value, version); every successful write bumps the version."""
    def __init__(self, value):
        self._pair = (value, 0)
        self._guard = threading.Lock()

    def load(self):
        return self._pair

    def compare_and_swap(self, expected_pair, new_value):
        with self._guard:
            if self._pair != expected_pair:
                return False
            self._pair = (new_value, expected_pair[1] + 1)
            return True

plain = AtomicCell(10)
seen = plain.load()
plain.compare_and_swap(10, 15); plain.compare_and_swap(15, 10)   # A -> B -> A behind our back
print(plain.compare_and_swap(seen, 11))                          # True  (stale history accepted)

stamped = StampedCell(10)
seen = stamped.load()                                            # (10, 0)
stamped.compare_and_swap((10, 0), 15); stamped.compare_and_swap((15, 1), 10)
print(stamped.load(), stamped.compare_and_swap(seen, 11))        # (10, 2) False

The same idea one level up: optimistic locking in a database is a CAS on a row, with a version column as the stamp:

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE seat (id INT PRIMARY KEY, holder TEXT, version INT)")
db.execute("INSERT INTO seat VALUES (7, NULL, 0)")

def claim(who, seen_version):
    cur = db.execute(
        "UPDATE seat SET holder = ?, version = version + 1 WHERE id = 7 AND version = ?",
        (who, seen_version))
    return cur.rowcount == 1                       # 0 rows: the version moved, we lost

v = db.execute("SELECT version FROM seat WHERE id = 7").fetchone()[0]
print(claim("ana", v), claim("ben", v))            # True False
print(db.execute("SELECT holder, version FROM seat").fetchone())   # ('ana', 1)

The complexity

• One CAS: constant time, a single instruction, though contended cache lines make it slower than a plain write.
• One update under contention: unbounded retries for an unlucky thread in the worst case, but some thread always succeeds.
• Compared with a mutex: no thread ever sleeps waiting for another, so a descheduled thread cannot hold everyone up.

Where it goes wrong

• Computing outside the loop. The new value must be recomputed from each fresh read, not reused from the first attempt.
• Updating two locations. A single CAS covers one word. Two fields that must change together need a lock, or both packed into one value.
• Ignoring ABA with reused memory. Pointer-based lock-free structures need version stamps or safe memory reclamation.
• Hot spots. Hundreds of threads retrying on one counter waste work; striped counters spread it out.
• Spurious failure. In C++, compare_exchange_weak may fail even when the value matches, so it belongs inside a loop.

When it shows up in interviews

CAS comes up as "implement a thread-safe counter without a lock", as "what does lock-free mean", and in design rounds as optimistic concurrency: two users edit the same record, and the second save must not flatten the first. Java's AtomicInteger.compareAndSet and AtomicStampedReference, and C++'s std::atomic, are the usual vocabulary; the version-column update above is the database form. It pairs naturally with the atomic operations lesson.

How to say it in an interview

"Compare-and-swap writes a new value only if the location still holds what I read, atomically, and reports whether it did. So an update is a loop: read, compute, CAS, and on failure re-read and recompute. No thread waits on another, and every failure means someone else succeeded, which is the lock-free guarantee, though an unlucky thread can retry. The trap is ABA: a value that changes and changes back passes the comparison, so for pointer structures I pair the value with a version that every write increments."