Compare-and-Swap and Optimistic Locking: How Every Database Implements It

Scenario context

Compare-and-Swap (CAS) is the CPU-level atomic instruction that makes lock-free concurrency possible. Optimistic locking builds on it at the database layer: read freely, compute locally, write only if the record has not changed. Every major database — PostgreSQL, MySQL, DynamoDB, Redis, MongoDB, CockroachDB, and Cassandra — implements CAS semantics differently. Choosing the wrong implementation, or retrying naïvely,…

This walkthrough focuses on The 47-Second Window That Broke a Ride-Share Platform.

Before making a design choice, clarify:

• At 08:14:32 UTC on a weekday morning, a ride-sharing platform's dispatch service and billing service both received an event for driver ID D-7741 .
• The dispatch service read the driver record: status = AVAILABLE , version = 42 .
• Simultaneously — 23 milliseconds later — the billing service read the same row: status = AVAILABLE , version = 42 .

Concepts in play: caching, transaction-isolation-distributed-acid, stack-and-queue-data-structures, consistency-replication

Stage 1 — The CPU Instruction Behind Every Database Concurrent Write

• Compare-and-Swap (CAS) is an atomic CPU instruction.
• "Atomic" means it executes as a single, indivisible operation — no other CPU core can observe an intermediate state.
• The semantics are simple: On x86-64 CPUs, this maps to the CMPXCHG instruction.
• On ARM processors, the equivalent is a LDREX / STREX pair (Load-Reserved / Store-Conditional).

CAS(memory_location, expected_value, new_value) → boolean
  if *memory_location == expected_value:
    *memory_location = new_value
    return true
  else:
    return false   // nothing changed

Observable outcome: On ARM processors, the equivalent is a LDREX / STREX pair (Load-Reserved / Store-Conditional).

Stage 2 — How CAS Propagates from Hardware to Distributed Storage — The Abstraction Stack

• CAS does not stay at the hardware level.
• Every layer of software above the CPU builds on it, abstracting the raw memory instruction into higher-level constructs.
• Understanding this stack tells you why database version columns and DynamoDB ConditionExpression s are not arbitrary design choices — they are CAS, two layers up.
• Each layer in this diagram adds latency and abstraction, but preserves the same semantic: compare the current state to what you expect, and only write if they match .

graph TD
    A[x86 CMPXCHG / ARM LDREX+STREX] --> B[OS mutex and spinlock primitives]
    B --> C[Language atomics - Java AtomicInteger - Go sync/atomic]
    C --> D[Database version column + conditional UPDATE]
    D --> E[Distributed conditional write - DynamoDB ConditionExpression - Cassandra LWT]

Observable outcome: Each layer in this diagram adds latency and abstraction, but preserves the same semantic: compare the current state to what you expect, and only write if they match .

Stage 3 — How Optimistic Locking Builds on CAS — The Version Column Pattern

• The version column pattern is the canonical database implementation of CAS.
• The mechanics are straightforward once you see them as a CAS in disguise: 1.
• Read: SELECT id, data, version FROM records WHERE id = ?
• — record the version number alongside the data.

sequenceDiagram
    participant T1 as Transaction T1
    participant DB as Database
    participant T2 as Transaction T2

    T1->>DB: SELECT id, status, version WHERE id=D-7741
    DB-->>T1: status=AVAILABLE, version=5
    T2->>DB: SELECT id, status, version WHERE id=D-7741
    DB-->>T2: status=AVAILABLE, version=5

    T1->>DB: UPDATE drivers SET status=ASSIGNED, version=6 WHERE id=D-7741 AND version=5
    DB-->>T1: rows_affected=1 - success

    T2->>DB: UPDATE drivers SET billing_cycle=OPEN, version=6 WHERE id=D-7741 AND version=5
    DB-->>T2: rows_affected=0 - conflict detected

    Note over T2,DB: T2 retries - re-reads fresh state
    T2->>DB: SELECT id, status, version WHERE id=D-7741
    DB-->>T2: status=ASSIGNED, version=6
    T2->>DB: UPDATE drivers SET billing_cycle=OPEN, version=7 WHERE id=D-7741 AND version=6
    DB-->>T2: rows_affected=1 - success

Observable outcome: — record the version number alongside the data.

Stage 4 — How Each Database Implements CAS — Internals and Performance

• Each database engine exposes CAS semantics through a different internal mechanism — some via SQL predicates, some via distributed consensus protocols, and some via atomic scripting.
• This section covers the internal machinery of each and closes with a comparative latency analysis.
• CAS Internals: How Each Database Engine Handles the Compare-and-Swap PostgreSQL — Explicit Version Columns and the Hidden xmin PostgreSQL gives you two distinct approaches to optimistic locking, and choosing between the…
• Approach 1: Explicit version column.

-- Schema
ALTER TABLE drivers ADD COLUMN version INTEGER NOT NULL DEFAULT 1;

-- Read
SELECT id, status, billing_cycle, version
FROM drivers
WHERE id = 'D-7741';

-- Write (CAS attempt)
UPDATE drivers
SET    status       = 'ASSIGNED',
       ride_id      = 'R-9901',
       version      = version + 1
WHERE  id           = 'D-7741'
AND    version      = 5
RETURNING version;
-- If RETURNING returns a row: success (new version = 6)
-- If RETURNING returns no rows: conflict (version was not 5)

Observable outcome: Approach 1: Explicit version column.

Stage 5 — The Complete CAS Write Flow — From Client Request to Committed State

• The diagram below shows the complete request lifecycle for an optimistic write, from the client HTTP call through the service layer to the database, with explicit success and retry paths.
• This architecture shows three important design decisions.
• First, the service layer performs all computation locally — the database only executes the CAS predicate, not business logic.
• Second, the retry loop re-reads from the database before recomputing, ensuring each attempt operates on committed state.

graph TD
    A[Client - HTTP PATCH /drivers/D-7741] --> B[Service Layer]
    B --> C[Read driver record and version]
    C --> D[Database Read Replica or Primary]
    D --> E[Return record with version=N]
    E --> F[Compute new state locally]
    F --> G[Attempt CAS write - UPDATE WHERE version=N]
    G --> H{Database CAS result}
    H -->|rows_affected=1 - success| I[Return 200 OK with new version]
    H -->|rows_affected=0 - conflict| J[Re-read fresh state]
    J --> K{Retry count under limit?}
    K -->|Yes| L[Apply backoff and jitter]
    L --> F
    K -->|No| M[Return 409 Conflict to client]
    I --> N[Emit audit event and downstream notifications]

Observable outcome: Second, the retry loop re-reads from the database before recomputing, ensuring each attempt operates on committed state.

Stage 6 — How Stripe, GitHub, and Amazon Use CAS in Production

• Stripe uses version columns on PaymentIntent records.
• Every state transition (created → processing → succeeded → captured) is guarded by a CAS write against the current state value.
• If two webhook events try to advance the same intent simultaneously, only one succeeds.
• Stripe's idempotency key mechanism ensures safe retry of the losing event.

Observable outcome: Stripe's idempotency key mechanism ensures safe retry of the losing event.

End-to-end outcome

After working through the stages, you should be able to explain:

• Always re-read before recomputing on retry.
• A retry that reuses stale read data is not a retry — it is a repeated mistake.
• Compare-and-Swap is the hardware foundation of all lock-free concurrency.
• The CMPXCHG instruction on x86 CPUs provides an atomic compare-and-swap in a single clock cycle; every database optimistic locking primitive is this instruction expressed at a higher layer of abstraction.

Alternatives considered

Optimistic vs. Pessimistic Locking — Choosing the Right Concurrency Strategy

Before going database-by-database, it is worth internalising the trade-off between the two dominant concurrency strategies, because choosing the wrong one is a performance cliff.

When Optimistic Locking Fails — The High-Contention Decision Guide

Optimistic locking excels when conflicts are rare.

Failure and degraded modes

Retry Strategy Patterns and Their Production Trade-offs

• Detection: A CAS failure is not an error — it is a signal to retry.
• User or operator impact: A CAS failure is not an error — it is a signal to retry.