skip to content

In Java's atomic classes, what does a successful compareAndSet prove about the value since you read it, and when is that not enough?

level: principalimportance: nice to knowfreq 34%

answer

  1. A→B→A: value matches but history changed; stale CAS wrongly succeeds
  2. CAS checks value equality, not change history
  3. Harmless for monotonic counters; dangerous for node-reuse lock-free structures
  4. Fix: AtomicStampedReference — CAS the (ref, version stamp) pair, bump stamp each update
  5. AtomicMarkableReference = single boolean mark variant

basics

~20 s

A successful CAS proves only that the value equalled the expected one (== for a reference) when it ran, not that it never changed, so A to B to A passes unseen. AtomicStampedReference adds a version number you also compare.

solid answer

~50 s

A successful CAS proves only that the current value *equals* the expected value at the moment of the swap (by `==` for a reference), not that it never changed. The ABA problem is when another thread changes the value A→B→A between your read and your CAS: your `compareAndSet(A, …)` still succeeds. For a plain monotonically-increasing counter this is harmless, but for lock-free structures (e.g. popping a node off a stack and reusing it) ABA can corrupt the structure — you swap in a stale node believing nothing changed. Java's fix is `AtomicStampedReference<V>`, which pairs the reference with an `int` **stamp**; your code passes a new stamp on every update, typically the old one plus 1, and `compareAndSet(expectedRef, newRef, expectedStamp, newStamp)` requires *both* to match. Because the stamp keeps moving, an A→B→A cycle leaves a different stamp, so the stale CAS fails. `AtomicMarkableReference` is the lighter variant carrying a single boolean mark instead of a counter.

code

java · 13 lines
java
AtomicReference<String> plain = new AtomicReference<>("A");
String seen = plain.get();
plain.set("B");                                     // another thread: A -> B
plain.set("A");                                     // ... and back to A
System.out.println(plain.compareAndSet(seen, "C")); // true: the round trip is invisible

AtomicStampedReference<String> stamped = new AtomicStampedReference<>("A", 0);
int[] holder = new int[1];
String s = stamped.get(holder);                     // reads "A" and stamp 0 together
int stamp = holder[0];
stamped.set("B", 1);                                // the same round trip,
stamped.set("A", 2);                                // with a new stamp on each write
System.out.println(stamped.compareAndSet(s, "C", stamp, stamp + 1)); // false: stamp is 2, not 0

go deeper

for a junior

Generally not expected to know ABA. Recognizing the term and that 'CAS only checks the current value' is a bonus.

for a middle

Can state the A→B→A definition and that CAS checks value equality not history, and name AtomicStampedReference as the Java fix at a high level.

for a senior

Explains where ABA actually bites (lock-free node-reuse structures vs harmless monotonic counters), and uses AtomicStampedReference (and AtomicMarkableReference) correctly, bumping the stamp each update.

for a principal

Reasons about identity-vs-history, designs or reviews lock-free structures for ABA hazards, weighs stamped references vs avoiding reuse vs GC-based safety, and is aware of stamp wrap-around and the limits of a single boolean mark.

## What a successful CAS proves `compareAndSet(expected, newValue)` performs an atomic *compare-then-conditional-write*: it writes `newValue` **only if** the cell currently equals `expected`, compared with `==`, so for an `AtomicReference` it must be the same object. Crucially, it checks **equality of the value right now**, not the *history* of the cell. It cannot tell the difference between "the value never changed" and "the value changed several times but happens to equal `expected` again now." ## The ABA scenario Name the value transitions by letters: 1. Thread T1 reads the shared cell and sees **A**. It intends to do `CAS(A, …)` shortly. 2. Before T1's CAS, thread T2 changes the cell **A → B**, then changes it **B → A** again. 3. T1 now runs `CAS(A, …)`. The cell currently holds **A**, so the CAS **succeeds** — even though the world moved through B and back. T1 believes "nothing changed since my read," which is **false**. That is the **ABA problem**: same value, different history. ## When that is enough, and when it is not For a counter that only ever **increases** (or otherwise never revisits a prior value), ABA can't occur: the value can't come back to a number it already passed. So `AtomicInteger`/`AtomicLong` counters are fine. More generally, equality is enough whenever the new value is computed from the compared value alone: an `A` now means the same as an `A` before. ABA bites **lock-free data structures that recycle objects**. In a lock-free stack, `pop` reads the head node A and its `next`, then CASes head from A to that `next`. If A is popped and pushed back while the thread stalls, head equals A again, the CAS succeeds, and it installs a `next` that another thread has already popped. The reference `A` *equals* the expected `A`, but its meaning (its `next`) changed. CAS can't see that. ## The fix: a version stamp The cure is to make every modification observable even when the value returns to a prior one — attach to the value a **version counter (stamp)** that every write advances, and CAS the **(value, stamp)** pair together. If every writer moves the stamp, an A→B→A round trip moves it twice, so the stamp differs from what T1 read, and T1's combined CAS fails. Java provides this as **`AtomicStampedReference<V>`**: ```java AtomicStampedReference<Node> head = new AtomicStampedReference<>(a, 0); int[] stampHolder = new int[1]; Node current = head.get(stampHolder); // read value AND stamp int stamp = stampHolder[0]; // ... compute newValue ... boolean ok = head.compareAndSet( current, newValue, // expected vs new reference stamp, stamp + 1); // expected vs new stamp (bump it) ``` `compareAndSet` succeeds only if **both** the reference **and** the stamp still match. The class stores whatever `newStamp` you pass and never increments it on its own; because each writer passes a new one, the A→B→A cycle leaves a stamp that no longer equals T1's expected stamp, so the stale CAS fails and T1 retries with fresh state. `AtomicMarkableReference` carries a single `boolean` mark instead of a stamp; a mark can flip back, so it is no version. ## Practical guidance - Most application code never meets ABA because it isn't writing lock-free recycling structures — prefer the JDK's concurrent collections, which already handle it. - If you *are* building lock-free structures with node reuse, assume ABA is possible and use a stamped reference (or avoid reuse, e.g. allocate fresh immutable nodes / let GC prevent reuse of live addresses). - ABA is fundamentally about *identity vs history*: CAS guards identity-now, the stamp restores a notion of history.

  • Why doesn't a simple incrementing AtomicLong counter suffer from ABA?
    ABA requires the value to return to a previously-seen value. A counter that only increases never revisits an earlier number, so the A→B→A pattern can't occur for it. ABA is a hazard for values that can cycle back — typically reused object references in lock-free structures, not monotonic counters.
  • How does AtomicStampedReference make the stamp itself immune to wrap-around or reuse?
    It doesn't fully — the int stamp can in theory wrap after ~4 billion updates and collide. In practice the window for an ABA with the exact same stamp is astronomically unlikely, and you bump the stamp on every update so collisions require both the reference and the stamp to coincide at the same instant. For stronger guarantees you'd use a wider counter or a design that avoids address reuse.

  • Believing a successful CAS proves the value was untouched since your read
  • Thinking ABA affects ordinary AtomicInteger counters in normal use (monotonic values can't ABA)
  • Confusing the fix: ignoring the stamp and only comparing the reference still allows ABA
  • Assuming AtomicMarkableReference's single boolean fully prevents ABA (the mark itself can ABA; the stamp counter is stronger)
  • Hand-rolling lock-free recycling structures without considering ABA at all

AtomicReference.compareAndSet
Java 1.5
AtomicStampedReference
Java 1.5

context