Building Lock-Free Counters, Stacks, and Queues

Sat Sep 12 2026

Without locks, shared state is a race condition waiting to happen. A mutex works, but it serializes access — every thread blocks when another holds the lock, and context-switch overhead compounds under contention.

Compare-and-Swap (CAS) offers an alternative: read the current value, compute the next one, and attempt to publish it only if nobody else changed the value in the meantime. If someone else did, you retry with the new value. No thread ever blocks waiting for another; they just keep going until their own CAS succeeds.

Go’s sync/atomic package exposes this via CompareAndSwapInt64, and Go 1.19+ adds atomic.Pointer[T] for lock-free linked data structures. In this post we build three classic concurrent data structures — a counter, a stack (Treiber), and a queue (Michael-Scott) — all without locks.

Lock-free counter

The simplest CAS structure is a counter. The idea is almost trivially simple: load the current value, compute old+1, and try to swap. If someone else incremented in between, your CAS fails and you retry with whatever the new value is now.

Ten thousand goroutines each increment 100,000 times — one hundred million total CAS operations across all goroutines, all converging on the correct value of 100000000. No mutex, no channel, just a loop and a hardware-atomic compare-and-swap.

Under light contention this is usually a one-shot CAS — the first attempt succeeds. Under heavy contention, goroutines retry more often, but they never block; each spin-loop iteration either wins or learns to pick a new old value and tries again.

The Treiber stack

A lock-free stack builds on the same pattern but adds a linked list. Each node carries its value and a pointer to the next item. The stack’s head (top) is an atomic.Pointer[Node], and both push and pop loop with CAS.

Push creates a new node whose next points at the current top, then attempts to swing top from old-top to the new node. If another thread pushed in between, the CAS fails and you re-read top, set your node’s next to whatever you just saw, and try again.

Pop reads the current top. If it’s nil, the stack is empty. Otherwise you save the value, read its next, and attempt to swing top from the old head to oldHead.next. The key insight: even if your CAS fails and a different thread pops that same old head in the meantime, the popped node is already linked into the stack — it just points somewhere else now. You re-read and try again.

Fifty goroutines each push 20,000 values (one million total). Every item is eventually popped exactly once with nothing lost or duplicated.

Lock-free queue: Michael-Scott algorithm

A lock-free queue is the hardest because it manages two shared pointers — head and tail — and you have to ensure they stay consistent. The Michael-Scott queue uses a sentinel (dummy) node so that the queue is never truly empty from the perspective of the linked list: head always has a valid next to work with.

Enqueue works in two CAS steps:

Attach your new node as tail.next — if tail.next is nil, you successfully link the node.
Swing tail forward from the old tail to your new node so future enqueues start from here.

Dequeue swaps head forward: read head.next, and if it’s non-nil (there’s a real item past the sentinel), CAS head from the current node to its successor, returning that successor’s value.

Both operations use a “help advance” step: if you observe that tail is lagging behind head during dequeue (they point to the same node but tail.next is nil), you try to swing tail forward before retrying. This prevents tail from falling so far behind that new enqueues spin forever on it — a subtle but important liveness guarantee.

Fifty goroutines enqueue 10,000 items each (500,000 total). Every item is dequeued in FIFO order, and the count matches exactly.

Takeaway

Lock-free data structures trade complexity for throughput: instead of one lock protecting everything, each operation spins on a CAS loop that succeeds once its attempt is the first to claim the current state. The pattern is always the same — read, compute, CAS, retry — but the linked-structure versions add real subtlety about stale nodes, lagging pointers, and when help-forwarding matters.

For counters under any reasonable contention a lock-free version usually wins. For stacks and queues the picture is more nuanced — the overhead of spinning on CAS can exceed a mutex’s context-switch cost when contention is low, but at high contention lock-free structures tend to scale better because threads make progress in parallel instead of waiting in line.