Linearizability Low-Level Design: Single-Object Semantics, Fencing Tokens, and Atomic Register Implementation

What Is Linearizability?

Linearizability is the strongest consistency model for single-object operations. It guarantees that every operation appears to take effect atomically at some point between its invocation and its completion — equivalent to executing on a single, perfectly reliable server with no concurrency.

From a client's perspective: once a write completes, any subsequent read (by any client) must return that value or a newer one. There is no window where a read can return stale data after a write has been acknowledged.

Single-Object Atomic Register Model

The canonical linearizability model is the atomic register: a single key-value pair that supports read and write operations. Linearizability on an atomic register means:

• A read always returns the value of the most recently completed write.
• Concurrent reads and writes resolve in some total order consistent with real time.
• A read that overlaps with a write returns either the old or the new value — not an intermediate state and not a value older than the most recently completed write before the read started.

Implementation: Single Leader with Synchronous Replication

The standard implementation routes all reads and writes through a single leader:

1. Client sends write to leader.
2. Leader writes to its log and replicates to a quorum of followers synchronously.
3. Leader applies the write and sends the ack to the client.
4. All reads also go through the leader (or followers with a valid leader lease).

This guarantees linearizability because the leader serializes all operations and does not acknowledge writes until they are durably replicated. The cost: write latency includes replication round-trip; the system is unavailable during leader election (CP in CAP theorem).

Fencing Tokens

Fencing tokens prevent split-brain writes when a distributed lock is used. The problem: a lock holder pauses (GC, network partition) and loses the lock to a new holder. When it resumes, it may still think it holds the lock and issue writes, corrupting shared state.

Solution:

1. Each lock grant issues a monotonically increasing fencing token.
2. The lock holder includes the fencing token in every write to the protected resource.
3. The resource's storage server rejects any write with a token lower than the highest seen token.

Even if the old lock holder resumes and issues writes with an outdated token, those writes are rejected. The new lock holder's writes (with a higher token) succeed.

Compare-and-Swap (CAS)

CAS is the fundamental atomic primitive for lock-free concurrent updates. A CAS operation reads the current value, verifies it matches an expected value, and conditionally writes a new value — all atomically. If the value has changed since the read, CAS fails and the caller retries.

CAS enables linearizable concurrent updates without a mutex: multiple clients can compete to update a key, and only one succeeds per round. Used for: optimistic locking, counter increments, state machine transitions.

ZooKeeper's Linearizability Model

ZooKeeper provides a well-known linearizable coordination service. Key properties:

• Ordered updates: every write is assigned a monotonically increasing zxid. All writes are totally ordered by zxid.
• Linearizable writes: all write operations are linearizable — routed through the leader and replicated to a quorum before ack.
• Sequential reads (not linearizable by default): reads can be served by any ZooKeeper server and may be slightly stale. For linearizable reads, use sync() before read to force read from leader.
• Watchers: clients register watchers on znodes; ZooKeeper delivers exactly-once change notifications.

PACELC: The Latency Cost of Linearizability

The PACELC theorem extends CAP: even in the absence of a network partition (E — else), linearizable systems pay a latency cost (L) for consistency (C). An eventually consistent system can serve reads from local replicas with no coordination overhead — latency is bounded by local disk/memory speed. A linearizable system must coordinate with the leader or a quorum, adding network round-trips to every operation.

SQL Schema

CREATE TABLE AtomicRegister (
    key             TEXT PRIMARY KEY,
    value           JSONB NOT NULL,
    version         BIGINT NOT NULL DEFAULT 1,
    last_written_at TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE TABLE FencingToken (
    id           BIGSERIAL PRIMARY KEY,
    resource_id  TEXT NOT NULL,
    token_value  BIGINT NOT NULL,
    issued_at    TIMESTAMPTZ NOT NULL DEFAULT now(),
    holder_id    TEXT NOT NULL
);

CREATE INDEX idx_fence_resource ON FencingToken (resource_id, token_value DESC);

CREATE TABLE CASOperation (
    id               BIGSERIAL PRIMARY KEY,
    key              TEXT NOT NULL,
    expected_version BIGINT NOT NULL,
    new_value        JSONB NOT NULL,
    succeeded        BOOLEAN NOT NULL,
    attempted_at     TIMESTAMPTZ NOT NULL DEFAULT now()
);

Python Implementation Sketch

import threading

class LinearizableStore:
    def __init__(self, db):
        self.db = db
        self._lock = threading.Lock()

    def linearizable_read(self, key: str) -> dict:
        # Route through leader (or sync before read in ZK model)
        with self._lock:
            row = self.db.fetchone(
                "SELECT value, version FROM AtomicRegister WHERE key = %s", (key,)
            )
        return row

    def linearizable_write(self, key: str, value: dict) -> int:
        with self._lock:
            result = self.db.fetchone(
                """INSERT INTO AtomicRegister (key, value) VALUES (%s, %s)
                   ON CONFLICT (key) DO UPDATE
                   SET value = EXCLUDED.value,
                       version = AtomicRegister.version + 1,
                       last_written_at = now()
                   RETURNING version""",
                (key, value)
            )
        return result['version']

    def cas(self, key: str, expected_version: int, new_value: dict) -> bool:
        with self._lock:
            result = self.db.execute(
                """UPDATE AtomicRegister
                   SET value = %s, version = version + 1, last_written_at = now()
                   WHERE key = %s AND version = %s""",
                (new_value, key, expected_version)
            )
            succeeded = result.rowcount > 0
        self.db.execute(
            "INSERT INTO CASOperation (key, expected_version, new_value, succeeded) VALUES (%s, %s, %s, %s)",
            (key, expected_version, new_value, succeeded)
        )
        return succeeded

    def acquire_lock_with_fence(self, resource_id: str, holder_id: str) -> int:
        with self._lock:
            row = self.db.fetchone(
                "SELECT COALESCE(MAX(token_value), 0) + 1 AS next_token FROM FencingToken WHERE resource_id = %s",
                (resource_id,)
            )
            token = row['next_token']
            self.db.execute(
                "INSERT INTO FencingToken (resource_id, token_value, holder_id) VALUES (%s, %s, %s)",
                (resource_id, token, holder_id)
            )
        return token

    def validate_fence(self, resource_id: str, token: int) -> bool:
        row = self.db.fetchone(
            "SELECT MAX(token_value) AS max_token FROM FencingToken WHERE resource_id = %s",
            (resource_id,)
        )
        return token >= row['max_token']

See also: Netflix Interview Guide 2026: Streaming Architecture, Recommendation Systems, and Engineering Excellence

See also: Scale AI Interview Guide 2026: Data Infrastructure, RLHF Pipelines, and ML Engineering

See also: Stripe Interview Guide 2026: Process, Bug Bash Round, and Payment Systems