Lock-Free and Wait-Free Algorithms, the ABA Problem, Hazard Pointers and Epoch Reclamation TODO
Concept
Non-blocking algorithms are classified by the strength of progress guarantee they offer. Lock-free guarantees that even if some thread stalls, the system as a whole always has someone making progress; wait-free guarantees every thread finishes its own operation within a bounded number of steps; obstruction-free guarantees only that an operation finishes once contention disappears. Most of these are built on an atomic read-modify-write like CAS, and that's where the ABA problem comes from: if a location's value changes from A to B and back to A, CAS sees "no change" and succeeds, even though the data structure's actual state has changed underneath it. The fix is a tagged pointer — attaching a version counter to the pointer — and, more fundamentally, a safe memory reclamation scheme. Hazard pointers have each thread publish the pointer it's currently referencing so other threads can't free that node; epoch-based reclamation keeps a global epoch and batches up freeing nodes from epochs every thread has already passed.
If you write or use a lock-free queue or map and skip handling ABA and memory reclamation, you get use-after-free and data corruption that are extremely hard to reproduce and that only surface in production.
Code & Formula
# 락프리 CAS 와 ABA 문제 — 값이 A->B->A 로 되돌아오면 순진한 CAS 는 "안 변했다"고 착각한다.
# 해결책: 포인터에 버전(태그)을 붙여, 값이 같아도 버전이 다르면 CAS 가 실패하게 만든다.
import threading
lock = threading.Lock()
def cas_naive(cell, expected, new):
"""cell[0] 값만 비교하는 순진한 CAS — ABA 에 취약."""
with lock:
if cell[0] == expected:
cell[0] = new
return True
return False
def cas_tagged(cell, expected_value, expected_version, new_value):
"""(값, 버전) 쌍을 함께 비교하는 태그드 포인터 CAS — 값이 되돌아와도 버전은 못 되돌린다."""
with lock:
if cell[0] == expected_value and cell[1] == expected_version:
cell[0] = new_value
cell[1] += 1
return True
return False
# --- ABA 시나리오: 순진한 CAS ---
cell = ["A", 0] # [value, version] 이지만 naive CAS 는 version 을 무시
read_value = cell[0] # 스레드1이 "A" 를 읽었다(포인터를 들고 대기 중이라 가정)
cell[0] = "B" # 다른 스레드가 A -> B 로 바꿨다가
cell[0] = "A" # 다시 A 로 되돌려놓았다 (스택으로 치면 pop/push/pop/push)
naive_ok = cas_naive(cell, read_value, "C") # 스레드1은 "안 변했네" 하고 착각 -> 성공해버림 (버그)
print("naive CAS after A->B->A round-trip succeeded:", naive_ok, " <- ABA 로 인한 잘못된 성공")
# --- 같은 시나리오를 태그드 포인터로 방어 ---
cell2 = ["A", 0]
read_value2, read_version2 = cell2[0], cell2[1] # 스레드1이 값과 버전을 함께 읽음
cell2[0] = "B"; cell2[1] += 1 # A -> B, version 0 -> 1
cell2[0] = "A"; cell2[1] += 1 # B -> A, version 1 -> 2 (값은 되돌아왔지만 버전은 못 돌아옴)
tagged_ok = cas_tagged(cell2, read_value2, read_version2, "C")
print("tagged CAS after A->B->A round-trip succeeded:", tagged_ok, " <- 버전 불일치로 정확히 거부됨")
print("final tagged cell state:", cell2)
docs/code/algorithms/algorithms-37.py
Exercise
Implement a Treiber stack with CAS and deliberately trigger ABA, then add a tagged-pointer version and an epoch-reclamation version, and compare throughput and how much memory ends up in delayed-free state under contention.
Practical Connection
In Verex's off-chain order book matching engine, where multiple threads update the same price-level structure on a low-latency path, trying to eliminate lock contention can walk you straight into this trap.
Where it lands in Jayverse
- Verex: pick epoch-based reclamation for the tick-driven matcher. The CLOB's price-level structure updates in bursts per tick, which fits epoch batching better than per-node hazard pointers; make that choice explicit rather than defaulting to whichever is easier to implement.
- CI: add a dedicated ABA stress test. Beyond general contention testing, write a test that rapidly removes and reinserts an order at the same price level under concurrent access, the exact pattern that triggers ABA.
- Auditor: publish the concurrency invariant, not just the throughput number. "No lost or duplicate order under concurrent update" is a checkable invariant the Auditor row can cite when someone asks what was verified about matching-engine correctness.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| stall | 멈추다, 정체되다 · 스레드나 프로세스가 진행을 멈춘 상태. "even if some thread stalls" |
| bounded (number of steps) | 상한이 정해진, 유한하게 제한된 · 무한정이 아니라 정해진 한도 안에서 끝남을 보장할 때. "within a bounded number of steps" |
| underneath (it) | (모르는 사이에) 그 아래에서, 밑에서 · 겉으로는 안 변한 것 같지만 실제로는 바뀐 상태를 가리킬 때. "the data structure's actual state has changed underneath it" |
| batch up | 모아서 한꺼번에 처리하다 · 개별적으로 처리하지 않고 묶어서 나중에 처리할 때. "batches up freeing nodes from epochs" |
| surface (in production) | (문제가) 겉으로 드러나다, 표면화되다 · 숨어 있던 버그가 실제 서비스에서 터질 때. "only surface in production" |
| walk straight into (a trap) | 함정에 그대로 걸려들다 · 조심하지 않으면 뻔히 빠지는 문제를 경고할 때. "can walk you straight into this trap" |
| use-after-free | 해제 후 사용 오류 · 이미 반환된 메모리를 계속 참조해서 생기는 버그를 가리키는 표준 용어. "you get use-after-free and data corruption" |
| ABA | ABA 문제 · 값이 A→B→A로 바뀌었다가 되돌아왔을 때 CAS가 "변화 없음"으로 착각해 그 사이의 실제 상태 변화를 놓치는 동시성 버그. "that's where the ABA problem comes from" |
| CAS | 비교 후 교체(Compare-And-Swap) · 락 없이 원자적으로 값을 읽고 비교해 바꾸는 하드웨어 연산, 대부분의 lock-free 알고리즘의 기반. "an atomic read-modify-write like CAS" |
| Treiber stack | 트라이버 스택 · CAS만으로 구현하는 대표적인 lock-free 스택 자료구조, ABA 문제를 실습으로 겪어보는 표준 예제. "Implement a Treiber stack with CAS" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.