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:

Client sends write to leader.
Leader writes to its log and replicates to a quorum of followers synchronously.
Leader applies the write and sends the ack to the client.
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:

Each lock grant issues a monotonically increasing fencing token.
The lock holder includes the fencing token in every write to the protected resource.
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']

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the difference between linearizability and serializability?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Linearizability is a per-object (single-key) consistency guarantee: operations on a single key appear atomic and respect real-time order. Serializability is a multi-object (transaction) consistency guarantee: transactions appear to execute in some serial order, but that order need not respect real time. Strict serializability combines both: transactions are serializable AND the serial order respects real-time order. Linearizability does not say anything about multi-key atomicity; serializability does not say anything about real-time ordering of individual reads.”
}
},
{
“@type”: “Question”,
“name”: “What is the fencing token pattern and when is it needed?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A fencing token is a monotonically increasing number issued with each distributed lock grant. The lock holder includes the token in every write to the protected resource. The resource storage server rejects writes with a token lower than the highest seen. This prevents a paused or delayed lock holder (e.g., after a GC pause or network partition) from issuing writes after it has lost the lock to a new holder. Without fencing tokens, process pauses can cause split-brain writes even when using distributed locks.”
}
},
{
“@type”: “Question”,
“name”: “When should CAS be used instead of a mutex?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “CAS is preferred over a mutex when contention is low and the update is short. CAS avoids the overhead of lock acquisition and is immune to lock-holder failures (a failed CAS simply retries). Under high contention, many CAS retries waste CPU (livelock risk), making a mutex more efficient. CAS is ideal for: optimistic locking in databases, atomic counter increments, state machine transitions where the new state depends on the current state.”
}
},
{
“@type”: “Question”,
“name”: “What is the latency and availability cost of linearizability vs eventual consistency?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Linearizability requires every read and write to coordinate with a leader or a quorum, adding at least one network round-trip per operation. This means write latency includes replication time (typically 1-10ms within a datacenter, 30-100ms cross-region). The system is unavailable during leader election. Eventual consistency serves reads from any local replica with no coordination, giving sub-millisecond read latency. The tradeoff is stale reads and the need for conflict resolution. Most production systems use linearizability for coordination primitives (locks, sequences) and eventual consistency for data reads.”
}
}
]
}

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is linearizability and how does it differ from serializability?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Linearizability is a single-object consistency model guaranteeing that every operation appears to take effect atomically at some point between its invocation and completion, making the system behave like a single copy of the data. Serializability is a multi-object transaction model that guarantees transactions execute in some serial order but does not constrain where within a transaction's real-time interval that order is placed; linearizability adds this real-time ordering constraint on top of atomicity.”
}
},
{
“@type”: “Question”,
“name”: “How do fencing tokens enforce linearizable writes?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A fencing token is a monotonically increasing number (e.g., the Raft term or ZooKeeper epoch) issued to a leader when it acquires a lock; the leader includes this token on every write to the storage node, which rejects any write carrying a token lower than the highest it has seen. This prevents a slow or network-partitioned former leader from completing stale writes after a new leader has been elected, ensuring linearizable semantics even under split-brain scenarios.”
}
},
{
“@type”: “Question”,
“name”: “How does Raft achieve linearizable reads?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Raft achieves linearizable reads by having the leader send a heartbeat and wait for acknowledgment from a quorum of followers before serving the read, confirming it is still the authoritative leader and has not been superseded. Alternatively, the read can be appended to the Raft log as a no-op read entry and executed only after it is committed, ensuring it observes all previously committed writes.”
}
},
{
“@type”: “Question”,
“name”: “What is the performance cost of linearizability?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Linearizability requires at least one round trip to a quorum of replicas for every read and write, adding network latency proportional to the distance between nodes and reducing throughput compared to eventually consistent or read-local alternatives. Under the CAP theorem, linearizability (consistency) requires sacrificing availability during network partitions, meaning the system must reject or stall requests rather than serve potentially stale data.”
}
}
]
}