Systems Providing Strong Consistency

Understanding linearizability is valuable, but building systems on a solid foundation requires knowing which production systems actually provide these guarantees—and under what conditions. Not all "strongly consistent" databases are created equal, and the devil is in the details.

Some systems provide linearizability by default; others require specific configurations. Some maintain guarantees during network partitions (by sacrificing availability); others silently degrade. Some have been rigorously tested with tools like Jepsen; others rely on correctness claims that haven't been independently verified.

This page explores the major categories of systems providing strong consistency, their architectural approaches, and practical guidance for choosing among them.

Coordination services are specialized systems designed specifically to provide linearizable operations for distributed coordination tasks: leader election, distributed locking, service discovery, and configuration management.

Apache ZooKeeper

Architecture:

• Multi-node ensemble (typically 3, 5, or 7 nodes)
• ZAB (ZooKeeper Atomic Broadcast) protocol for consensus
• Hierarchical namespace (like a filesystem)
• Ephemeral nodes for liveness detection
• Sequential nodes for ordering

Consistency Model:

• Writes: Linearizable (go through leader, require quorum)
• Reads: NOT linearizable by default (served from local node)
• sync() + read(): Linearizable (sync forces read of committed state)

// Linearizable read in ZooKeeper
zk.sync("/important/path", (rc, path, ctx) -> {
    byte[] data = zk.getData("/important/path", false, null);
    // This read is linearizable
});

// Non-linearizable (but faster) read
byte[] staleData = zk.getData("/important/path", false, null);
// May return stale data!

Performance Characteristics:

• Write latency: 2-10ms (same datacenter), 100-300ms (multi-region)
• Read latency: <1ms (local), 2-10ms (sync read)
• Throughput: ~10,000 writes/second, ~100,000 reads/second

etcd

Architecture:

• Raft consensus for all operations
• Flat key-value namespace with prefix iteration
• Watch functionality for reactive updates
• gRPC API for efficiency
• MVCC for efficient range queries

Consistency Model:

• All operations: Linearizable by default
• Serializable mode: Optional, for stale reads with higher throughput
• Watch: Linearizable ordering of events

// etcd provides linearizable reads by default
resp, err := client.Get(ctx, "my-key")
// This read is linearizable

// Optional: serializable read (faster, may be stale)
resp, err := client.Get(ctx, "my-key", clientv3.WithSerializable())
// May return stale data

Why etcd Is Popular:

• Default linearizability reduces configuration errors
• Native gRPC provides efficient communication
• Kubernetes uses it as its source of truth
• Clear API semantics with strong Go library support

NewSQL databases combine the scalability of NoSQL with the strong consistency and SQL interface of traditional relational databases. They use consensus protocols to provide linearizability (or strict serializability) while sharding data across many nodes.

Google Spanner

Architecture:

• Global distribution across regions
• Paxos consensus within each Paxos group (shard)
• TrueTime: GPS + atomic clocks for bounded clock uncertainty
• Two-phase commit for cross-shard transactions
• Automatic sharding and load balancing

Consistency Model:

• Strict serializability (also called external consistency)
• All transactions appear to execute at a single instant
• Real-time ordering is preserved

The TrueTime Magic:

TrueTime.now() returns interval: [earliest, latest]
Uncertainty: typically 5-10ms

Commit wait:
  1. Assign commit timestamp T = TrueTime.now().latest
  2. Wait until TrueTime.now().earliest > T
  3. Transaction is now durable and globally ordered

Result: All transactions have globally consistent ordering
        without requiring global consensus for reads

Performance:

• Write latency: 10-100ms (single region), 200-500ms (global)
• Read latency: <10ms (local replica), requires commit wait for global
• Throughput: Scales linearly with nodes
• Cost: Premium (requires specialized infrastructure)

CockroachDB

Architecture:

• Spanner-inspired, open-source
• Raft consensus for each range (16MB-64MB)
• Hybrid Logical Clocks (HLC) instead of TrueTime
• Supports PostgreSQL wire protocol
• Can run on commodity hardware

Consistency Model:

• Serializable isolation level (default)
• Linearizable for single-key operations
• Read committed and snapshot isolation also available

HLC vs TrueTime Trade-off:

TrueTime (Spanner):
  - Requires specialized hardware (GPS, atomic clocks)
  - Bounded uncertainty enables external consistency
  - Commit wait adds latency but avoids remote coordination for reads

HLC (CockroachDB):
  - Works on commodity hardware
  - Cannot guarantee external consistency without coordination
  - May require remote reads to ensure consistency
  - Slightly higher read latency in some scenarios

TiDB

Architecture:

• MySQL-compatible SQL layer
• TiKV: Raft-based distributed key-value store
• PD (Placement Driver): cluster metadata and scheduling
• Designed for hybrid OLTP/OLAP workloads

Consistency Model:

• Snapshot isolation (default)
• Optimistic transactions with conflict detection
• Pessimistic transactions available (with locking)

FoundationDB deserves special attention as it represents a unique approach: provide a simple, rigorously correct linearizable key-value store, then build higher-level abstractions as "layers" on top.

Architecture

Core components:

• Coordinators: Cluster configuration and recovery
• Cluster Controller: Manages cluster state and roles
• Master Proxy: Receives transactions, assigns timestamps
• Storage Servers: Store data, serve reads
• Resolvers: Conflict detection
• Log Servers: Write-ahead log for durability

The Sequencer Model:

Unlike Raft/Paxos where each operation goes through consensus,
FoundationDB uses a centralized sequencer:

1. Client starts transaction, reads from storage servers
2. Client sends writes to proxies
3. Proxy requests commit timestamp from sequencer
4. Sequencer assigns monotonically increasing timestamp
5. Resolvers check for conflicts against committed transactions
6. If no conflicts, log servers persist the transaction
7. Transaction is committed with guaranteed ordering

Why FoundationDB's Model Works

Advantages:

• Single point for ordering (sequencer) is simpler than distributed consensus
• Very high throughput for non-conflicting transactions
• Deterministic conflict detection
• Rigorous testing (simulation testing)

Handling sequencer failure:

• Sequencer is replicated, coordinated by Paxos
• Recovery selects new sequencer
• State is reconstructed from log servers

The Layer Architecture

FoundationDB provides strict serializability for key-value operations. Higher-level abstractions are built as layers:

┌─────────────────────────────────────────────────┐
│           Application Layer                     │
├─────────────────────────────────────────────────┤
│  Document Layer │ SQL Layer │ Graph Layer │ ... │
├─────────────────────────────────────────────────┤
│              Record Layer                       │
│    (structured records, indexes, transactions)  │
├─────────────────────────────────────────────────┤
│            FoundationDB Core                    │
│    (ordered key-value, strict serializability)  │
└─────────────────────────────────────────────────┘

Notable users:

• Apple: iCloud backend, handling billions of transactions
• Snowflake: Metadata storage for data warehouse
• Wavefront: Time-series database backend

Simulation Testing

FoundationDB pioneered rigorous simulation testing:

Deterministic simulation:
  - Run entire cluster in single-threaded simulator
  - Control all randomness (network, disk, clocks)
  - Inject failures systematically
  - Replay bugs deterministically

Result: Millions of simulated hours of operation
        Bugs found before production
        High confidence in correctness claims

Major cloud providers offer managed services with strong consistency guarantees, often building on the technologies discussed above.

AWS Services

DynamoDB:

• Default mode: Eventual consistency
• Strong consistency mode: Linearizable reads available per-request
• Transactions: Serializable across items and tables

# DynamoDB with strong consistency
response = dynamodb.get_item(
    TableName='users',
    Key={'user_id': {'S': 'alice'}},
    ConsistentRead=True  # Linearizable read
)

# DynamoDB transaction (serializable)
response = dynamodb.transact_write_items(
    TransactItems=[
        {'Put': {...}},
        {'Update': {...}},
        {'Delete': {...}}
    ]
)  # All-or-nothing, serializable

Aurora:

• Multi-AZ with synchronous replication
• Read replicas have eventual consistency
• Writer endpoint provides linearizable writes
• Global Database: cross-region, eventually consistent

Amazon QLDB:

• Purpose-built for audit and ledger use cases
• Immutable, cryptographically verifiable
• Serializable transaction processing

Azure Cosmos DB

Cosmos DB offers five consistency levels, from strongest to weakest:

1. Strong (Linearizable)
   - Reads guaranteed to return most recent committed write
   - Single region only for writes
   - Highest latency

2. Bounded Staleness
   - Reads lag behind writes by at most K versions or T time
   - Configurable K and T

3. Session
   - Monotonic reads/writes within a session
   - Different sessions may see different orders

4. Consistent Prefix
   - Reads never see out-of-order writes
   - May be arbitrarily stale

5. Eventual
   - No ordering guarantees
   - Highest throughput

Important: Strong consistency in Cosmos DB restricts writes to a single region, eliminating the multi-region write capability. This is a direct manifestation of the CAP theorem.

Google Firestore

Firestore provides linearizable consistency by default:

// All Firestore operations are linearizable
await db.collection('users').doc('alice').set({name: 'Alice'});

// This read will see the write above
const doc = await db.collection('users').doc('alice').get();

Firestore uses a similar architecture to Spanner, providing external consistency for all operations.

Not all consistency claims are equally trustworthy. Here's how to evaluate whether a system actually provides the guarantees it claims.

Red Flags in Marketing Materials

Watch out for:

1. Vague terminology: "Strong consistency" without defining what operations are covered
2. Asterisks and footnotes: "Consistent*" where * = "in single-region configurations only"
3. Missing failure semantics: No mention of behavior during partitions
4. Untested claims: No Jepsen report or equivalent independent verification
5. Configuration complexity: Consistency depends on subtle configuration options

Questions to Ask

For any system claiming linearizability:

1. Which operations are linearizable?
   - All operations? Writes only? Specific APIs?
   
2. What happens during network partitions?
   - Operations fail? Silent degradation? Best-effort?
   
3. What's the default configuration?
   - Is linearizability default or opt-in?
   
4. Has it been independently tested?
   - Jepsen report? Academic analysis? Internal testing?
   
5. What's the latency and availability trade-off?
   - How much latency does strong consistency add?
   - What's the availability target?

Jepsen: The Consistency Verifier

Jepsen (jepsen.io) has become the industry standard for testing distributed systems' consistency claims:

What Jepsen does:

1. Runs concurrent operations against the system
2. Injects failures (network partitions, node crashes, clock skew)
3. Records complete history of operations
4. Verifies history is consistent with claimed model

Selected Jepsen findings:

Key insight: Many systems that claim linearizability have had violations discovered by Jepsen. Check for a Jepsen report and whether issues were fixed.

With the landscape understood, here's how to choose the right linearizable system for your needs.

Decision Matrix

Key Trade-offs to Consider

1. Self-Hosted vs Managed

Self-hosted (etcd, CockroachDB, FoundationDB):
  + Full control, no vendor lock-in
  + Potentially lower cost at scale
  - Operational complexity
  - Must handle upgrades, monitoring, recovery

Managed (Spanner, Cosmos DB, Firestore):
  + Zero operational overhead
  + Provider handles consistency verification
  - Vendor lock-in
  - Higher cost, especially at scale

2. Generality vs Specialization

General-purpose (CockroachDB, Spanner):
  + SQL interface, broad use cases
  + Feature-rich (transactions, indexes, schemas)
  - Higher overhead for simple use cases

Specialized (etcd, ZooKeeper):
  + Low overhead for coordination tasks
  + Purpose-built APIs
  - Not suitable for application data
  - Limited data model

3. Geographic Distribution

Single-region:
  - Most systems work well
  - Lower latency
  - Simpler operations

Multi-region:
  - Spanner: Best-in-class (TrueTime)
  - CockroachDB: Good (HLC)
  - Most others: Significant latency penalty

We've surveyed the landscape of systems providing strong consistency, from specialized coordination services to globally distributed databases. Each approach has trade-offs, and the right choice depends on your specific requirements.

Module Complete: Strong Consistency Mastery

Across five pages, you've developed a deep understanding of strong consistency in distributed systems:

1. Linearizability: The gold standard consistency model and its formal definition
2. Implementation Costs: The coordination overhead, latency, and availability trade-offs
3. Performance Implications: How linearizability affects latency, throughput, and user experience
4. When Strong Consistency Is Required: Use cases where linearizability isn't optional
5. Systems Providing Strong Consistency: Real-world implementations and selection criteria

You're now equipped to make informed decisions about consistency requirements in your distributed systems—knowing when to pay the linearizability tax and when weaker consistency suffices.