Concurrency
Part 6 of 6 · Distributed locksCompare-And-Swap & Optimistic Coordination — When You Do Not Need a Lock
Conditional writes (DynamoDB, etcd Txn, Redis WATCH, Postgres version columns) beat distributed locks under low contention; watch ABA and retry storms.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Do you need a distributed lock at all?
Prefer
Conditional write on the system of record
Read version V, compute, commit if version is still V. The version is the fence. No lock-service outage in the path. Best under low contention on a single key.
- DynamoDB, etcd Txn, Redis WATCH/Lua, Postgres version columns, S3 If-Match, Cassandra LWT.
- Avoids acquire + renew + release round trips.
- Hot keys: a queue / single-writer often beats N-way CAS fighting.
Alternative
Distributed lock for every update
Required when you cannot express a multi-record invariant as a transaction, or you are coordinating long external side effects (prefer outbox + idempotency instead).
- Lock service outage becomes your write outage.
- SELECT FOR UPDATE is pessimistic — not the same as UPDATE WHERE version.
- Lost update under READ COMMITTED is the bug CAS/FOR UPDATE exist to stop.
Optimistic path
Conflict is detected at commit, not by holding a mutex.
- 1
Read version V
Integer per row is enough for single-primary OLTP. Version vectors are for multi-replica concurrent writes. - 2
Compute the new state
No lock held. Another writer may commit in this window. - 3
CAS: commit only if version == V
On yes: store V+1. On no: backoff and retry with a cap. - 4
If retries melt the key
Architectural single-writer or a queue — not a bigger retry loop.
Overview
Optimistic coordination uses conditional writes (CAS): read a version, compute an update, commit only if the version is unchanged. Under low contention it beats distributed locks on latency and availability; under high contention it needs bounded retries and backoff.
Prefer CAS, idempotency keys, or single-writer partitions when you do not truly need a multi-step exclusive critical section.
You should be able to:
- Fill the lock vs CAS table.
- Show ABA on raw-value CAS and why a generation fixes it.
- Point at atomics vs locks for in-process RMW and stay on distributed stores here.
Locks vs CAS
| Axis | Distributed lock | CAS / conditional write |
|---|---|---|
| Mutual exclusion | Explicit critical section | Detect conflict at commit |
| Round trips | Acquire + work + release (+ renew) | Read + write (sometimes one) |
| Failure mode | Lock service outage | Retry storms |
| Best when | Multi-key / multi-step invariants | Single-row / single-key updates |
| Fencing | Token at storage | Version is the fence |
Pessimistic — hold exclusion, then work:
Flow
- 1
1 Acquire
- next2 Work
- 2
2 Work
- next3 Release
- 3
3 Release
Lesson map
Compare-And-Swap & Optimistic Coordination — When You Do Not Need a Lock
Conditional writes (DynamoDB, etcd Txn, Redis WATCH, Postgres version columns) beat distributed locks under low contention; watch ABA and retry storms.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a1["1 Acquire"] w1["2 Work"] r1["3 Release"] a1 -->|1 Acquire to 2 Work| w1 w1 -->|2 Work to 3 Release| r1
Optimistic — compute freely, then CAS:
Decisions
- 1
4 Read version V
- next5 Compute
- 2
5 Compute
- next6 CAS version==V?
- ?
6 CAS version==V?
- yes7 Commit V+1
- no8 Backoff retry
- 4
7 Commit V+1
- 5
8 Backoff retry
Conditional write APIs
| System | Primitive |
|---|---|
| DynamoDB | ConditionExpression attribute_equals / version |
| etcd | Txn compare revision / value |
| Redis | WATCH + MULTI/EXEC (or Lua compare) |
| Postgres | UPDATE … WHERE id=:id AND version=:v RETURNING * |
| S3 | If-Match ETag (limited) |
| Cassandra | LWT / IF conditions (costly) |
DynamoDB example: SET balance = :b, version = version+1 conditioned on version = :v.
Redis WATCH is optimistic multi-key; Lua is server-side atomic for scripted conditions — often clearer under load.
etcd Txn compares revisions — prefer for short state updates; locks for long critical sections.
SELECT FOR UPDATE is not optimistic — it is a pessimistic row lock. Optimistic is UPDATE … WHERE version.
Version vectors vs simple versions
- Monotonic integer version per row — simplest CAS.
- Version vector — multi-replica concurrent writes; conflict detect beyond single primary.
- For single-primary OLTP, integer versions win on clarity.
When CAS beats locks
- Low contention updates (user profile, cart item).
- System of record already supports conditions (DynamoDB, Postgres).
- You want to avoid lock-service dependency.
- Operation is a single atomic record transition.
When locks still win:
- Multi-record invariants without a txn API
- Long critical sections coordinating external side effects (prefer outbox + idempotency instead)
- Extremely hot keys where retries waste more than waiting (sometimes queue/single-writer is better than either)
Combine fencing tokens with CAS: fence from the lock service or a version column; both reject stale writers. Depth: fencing.
ABA problem
ABA: value goes A→B→A; naive pointer/value CAS succeeds though intermediate B mattered.
T1 reads A
T2 changes A→B→A
T1 CAS A→C succeeds — may be wrong if B had side effectsMitigations: monotonic version counters (not raw value), tagged pointers, generation numbers — same spirit as fencing tokens.
Sandbox: version CAS vs raw-value ABA (Python)
Raw CAS on the value lets A→B→A fool T1. A generation counter does not.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
A user profile update, a two-row transfer with no multi-key txn API, and a hot inventory SKU with 5k CAS retries/sec. Which is conditional write, which is a lock or txn, which is a single-writer queue? Where does ABA show up if you CAS the stock integer itself?
Interview Q&A
When do you not need a distributed lock?
Answer
Single-key conditional updates, idempotent APIs, or single-writer partitions already serialize.
Explain CAS in one sentence.
Answer
Commit the new state only if the observed version is still current.
DynamoDB example?
Answer
SET balance = :b, version = version+1 conditioned on version = :v.
What is ABA?
Answer
Value returns to A after B; naive value-CAS succeeds incorrectly; use generations.
How to tame retry storms?
Answer
Full jitter backoff, attempt caps, and architectural single-writer for hot keys.
Redis WATCH vs Lua?
Answer
WATCH is optimistic multi-key; Lua is server-side atomic for scripted conditions — often clearer under load.
etcd Txn vs lock?
Answer
Txn compares revisions — prefer for short state updates; locks for long critical sections.
Is SELECT FOR UPDATE optimistic?
Answer
No — pessimistic row lock. Optimistic is UPDATE … WHERE version.
Lost update under READ COMMITTED?
Answer
Two transactions read same row and write — CAS/version or FOR UPDATE prevents it.
Combine fencing tokens with CAS?
Answer
Yes — fence from lock service OR version column; both reject stale writers.
High contention inventory?
Answer
Prefer serialized worker / queue over N-way CAS fighting.
Interview closer?
Answer
I default to conditional writes on the system of record; I take a distributed lock only for multi-step exclusion I cannot express as a transaction.