Lock-Free Data Structures Architecture

The CAS primitive

compareAndSet(expected, new). Hardware atomic. Either succeeds (value was expected, now new) or fails (value changed).

The CAS primitive

compareAndSet(expected, new). Hardware atomic. Either succeeds (value was expected, now new) or fails (value changed).

The retry pattern

AtomicReference ref;
T current;
T next;
do {
  current = ref.get();
  next = compute(current);
} while (!ref.compareAndSet(current, next));

The ABA problem

Value goes X → Y → X between your read + CAS. CAS succeeds but state changed. Use versioned refs (AtomicStampedReference) for safety.

Contention vs progress

High contention = many retries. Under extreme contention, lock-free can be slower than a mutex. Measure.

What's built-in

ConcurrentHashMap, AtomicInteger, ConcurrentLinkedQueue — production-tested lock-free. Use these before rolling your own.