distributed-sql

How it is built

Architecture overview

A distributed SQL database presents one relational database with transactions over many machines, and keeps working when some of them fail. Google Spanner is the original; CockroachDB, TiDB and YugabyteDB are open designs in the same family. The idea that makes it work is a layering: SQL tables are encoded as rows in one huge sorted key-value map; the map is cut into contiguous ranges (TiKV calls them Regions, Spanner and YugabyteDB use tablets and directories); each range is a small replicated state machine run by a consensus group (Raft or Paxos), so its writes survive the loss of a minority of replicas; and a transaction layer with timestamped versions makes operations that touch several ranges atomic and consistently ordered. SQL planning sits on top and storage engines sit underneath. Everything interesting is in the seams: how a range is found, who may serve a read, and where the commit timestamp comes from.

Parts:

• SQL layer — parse, optimise, plan, execute on any node; turns rows and indexes into key-value operations — query-optimizer (no page yet), relational-algebra (no page yet), predicate-pushdown (no page yet), join-order-dynamic-programming (no page yet), cardinality-estimation (no page yet), subquery-decorrelation (no page yet), partition-pruning (no page yet), Hash join, HyperLogLog
• Distribution — splits the key space into ranges, finds the range for a key, moves ranges between nodes, shuffles intermediate data — Range partitioning, data-shuffle (no page yet), External merge sort, Fast hash functions
• Replication — one consensus group per range, leader and leases, snapshots for catch-up — multi-raft (no page yet), Raft, Leases, State-machine snapshots, Group commit, Write-ahead log, Exponential backoff with jitter, Fencing tokens
• Transactions — multi-version data, commit across ranges, isolation level — MVCC, Two-phase commit, serializable-snapshot-isolation (no page yet), Interval tree, Swiss table
• Time — timestamps that order transactions across nodes — truetime-commit-wait (no page yet), Hybrid logical clocks, Clock synchronization, Lamport clocks
• Storage engine — each node's local ordered store with versions — LSM-tree, LSM compaction, sstable (no page yet), Bloom filter, CRC32C checksums
• Cluster membership and operations — who is alive, graceful restarts, health, observability — SWIM gossip membership, epidemic-broadcast (no page yet), Health checking, Graceful draining, Process supervision, hdr-histogram (no page yet)
• Security — encrypted, authenticated links between nodes and clients — TLS 1.3, Mutual TLS
• Change and recovery — online schema change, backups, restore to a time — expand-contract-migration (no page yet), Chunked backfill, Point-in-time recovery, ARIES recovery, Object storage, Primary-backup replication
• Verification — how the consistency claims are tested — Deterministic simulation testing, Coverage-guided fuzzing, fault-injection (no page yet)

 client ──SQL──► any node = gateway ───────────────────────────────────────┐
                 parse → optimise → plan (rows/indexes → KV ops)            │
                          │                                                 │
                          ▼  KV batches, routed by key                      │
              range lookup (cached 2-level index)                           │
                          │                                                 │
        ┌─────────────────┼─────────────────┐                               │
        ▼                 ▼                 ▼                               │
   range A leader    range B leader    range C leader   ◄── 2PC / intents ──┘
   (consensus group) (consensus group) (consensus group)   transaction record + timestamps
    │ log │ log │      │ log │ log │
    ▼     ▼     ▼      ▼     ▼     ▼
   replicas: each node holds many ranges, one LSM store per node/disk (WAL + SST files)

How the parts fit together

SQL layer

Every node can accept SQL: in CockroachDB the node a client connects to is the gateway, it parses the statement, builds a logical plan, runs a cost-based optimiser, then plans physically across nodes and runs the plan by issuing key-value requests (source: CockroachDB docs, SQL layer). TiDB makes the split explicit: its SQL servers are stateless, "only for computing and SQL analyzing", and the data lives in TiKV (source: TiDB docs, Architecture). The planning blocks are the same as in any database (query-optimizer (no page yet) with relational-algebra (no page yet), cardinality-estimation (no page yet), join-order-dynamic-programming (no page yet) against the alternative of a Cascades-style search, subquery-decorrelation (no page yet)) with one addition that only distribution needs: predicate-pushdown (no page yet) and partition-pruning (no page yet) decide how much work can be done next to the data on the node that owns it, because moving rows across the network is the expensive step. Equi-joins that cannot be pushed down are run as a Hash join after a data shuffle (data-shuffle (no page yet)): rows are repartitioned between workers by Fast hash functions of the join key, or by range when a sorted result is needed (External merge sort). The contract between the SQL layer and everything below is a key-value interface: SQL never sees a replica, only keys, timestamps and batches.

For TiDB, table data and index data get key prefixes derived from the table and index ids, so all rows of a table sit together in the key space (source: TiDB docs, Computing). That is what makes a range scan of a table a range scan in the map, and what lets splits follow table boundaries.

Distribution: ranges and how to find them

The key space is one sorted map, cut into contiguous half-open ranges (Range partitioning). This is the alternative to hash partitioning, chosen because ordered data keeps range scans and index lookups local; the cost is hot spots on sequential keys, which splitting and load-based rebalancing have to handle. CockroachDB describes it as a "monolithic sorted map" where every key lives in exactly one range, and a range splits when it grows past its maximum (source: CockroachDB docs, Distribution layer). TiKV's Regions are left-closed, right-open key intervals with a default size limit of 256 MiB (source: TiDB docs, Storage). A directory of boundaries is needed to route a request: CockroachDB keeps a two-level index in the key space itself (meta ranges), caches it on every node, and distributes the location of the first level by gossip; the docs' arithmetic for the address space assumes 2^26-byte ranges (source: the distribution-layer page). TiDB instead has a central service, PD (Placement Driver), which stores the region map and issues scheduling commands (source: TiDB docs, Architecture). The trade is a lookup that is cached and decentralised against a simple, central brain that can become a dependency.

Which nodes are alive is a separate question. CockroachDB's docs name gossip for distributing some cluster metadata; SWIM gossip membership is the failure-detecting variant (probe, indirect probe, piggybacked updates), with a phi-accrual detector as the alternative. Health checking and Graceful draining let a node being restarted hand off its leases and connections first.

Replication: one consensus group per range

Each range is replicated by its own consensus group, so a node runs thousands of groups at once. That arrangement is multi-raft (no page yet): heartbeats are batched across groups so that idle ranges cost almost nothing, the groups share a log engine, and ranges split and merge without a reconfiguration of the whole cluster. The protocol is Raft in CockroachDB, TiKV and YugabyteDB, and Paxos in Spanner; Multi-Paxos is the closest alternative. CockroachDB's docs give the quorum arithmetic: three is the smallest count that can lose one replica and still reach quorum, so high availability needs three nodes (source: CockroachDB docs, Replication layer). A write is a command proposed to the leader, appended to the log, replicated to a majority and applied; the log is a Write-ahead log in all but name, and Group commit lets many proposals share one log write and fsync. Spanner's paper notes that its Paxos leaders hold timed leases of 10 seconds by default and that every Paxos write is logged twice, once in the tablet's log and once in the Paxos log (source: Spanner, OSDI 2012).

A lease (Leases) is how reads avoid consensus. In CockroachDB one replica, the leaseholder, serves reads and proposes writes; the docs say it is also kept as the Raft leader, and that reads at the leaseholder bypass Raft because the data was already committed by consensus (source: replication-layer page). A lease only works with bounded clock drift, and a deposed leaseholder that does not know it yet is the classic hazard that Fencing tokens address. Lagging or new replicas catch up from the log, or, if the log has been truncated, from a snapshot of the range (State-machine snapshots). Retried RPCs use Exponential backoff with jitter. Non-voting replicas, which CockroachDB documents, serve reads in far regions without adding to write latency, because they are outside the quorum.

Storage engine

Each node stores its replicas in a local ordered key-value engine; CockroachDB uses Pebble, TiKV uses RocksDB, and Spanner stored tablet state in B-tree-like files plus a write-ahead log on its distributed file system (sources: CockroachDB docs, Storage layer; TiDB docs, Storage; Spanner paper). The usual pick is the LSM-tree with LSM compaction, sstable (no page yet) files and per-file Bloom filters, and the alternative is the B+ tree. The reasons are workload-driven: replication already makes every write sequential through the Raft log, so an engine that also turns random updates into sequential file writes fits, and MVCC versions (below) are naturally append-only. The lsm-engine system page shows that engine as a system of its own. Contract: the replicated state machine applies committed commands to the engine in log order, and the engine returns versions by timestamp. Block checksums (CRC32C checksums) catch silent corruption, which consensus alone does not.

Transactions: versions, intents and atomic commit across ranges

All of these systems store several versions per key, stamped with a timestamp (MVCC); CockroachDB states that its MVCC values are stored in Pebble and used throughout the transaction layer (source: storage-layer page). A reader at timestamp t sees the newest version at or below t and never blocks on writers, which is also what makes historical and follower reads possible. For writes that span ranges the shape is Two-phase commit, over replicated participants so a coordinator crash cannot stall the system for ever. Spanner's participant leaders coordinate two-phase commit, with state stored in the replicated groups, and read-write transactions take locks in a lock table at each leader (source: Spanner paper). CockroachDB writes write intents, provisional values that point to a transaction record on the range holding the transaction's first key; committing flips the record and the intents are resolved lazily, and "Parallel Commits" lets a transaction be treated as committed once its intents are replicated (source: transaction-layer page). TiKV exposes snapshot isolation by default at the key-value level (source: TiDB docs, Architecture). The alternative is serializable-snapshot-isolation (no page yet), which detects dangerous read-write dependency cycles on top of snapshot isolation, as the route to serializability (an Interval tree for overlapping key ranges and a Swiss table for fast lock and intent lookup support it); it sits against Two-phase locking and Optimistic concurrency control. Isolation levels differ per system and per version, and that should be checked in each product's documentation.

Time

Commit order across nodes needs a clock that is comparable across nodes. Spanner's answer is TrueTime: the API returns an interval guaranteed to contain absolute time, built from GPS and atomic clocks, with uncertainty generally below 10 ms and a typical bound of about 4 ms (the paper reports a sawtooth between 1 and 7 ms). A transaction picks its commit timestamp and then waits until that time has definitely passed, commit wait, so that any transaction that starts after it commits gets a larger timestamp: external consistency (source: Spanner paper; truetime-commit-wait (no page yet)). The price is the wait, equal to the clock uncertainty. Hardware time references are not available everywhere, so the open systems use Hybrid logical clocks, which combine a physical component with a logical counter; CockroachDB and YugabyteDB both do, and YugabyteDB's docs say the maximum clock skew influences conflict resolution and so the number of conflicts and the latency (sources: CockroachDB docs, Transaction layer; YugabyteDB docs, Transactions overview). TiDB's PD allocates transaction ids centrally, trading a shared service for no dependence on clock quality. All of these rest on Clock synchronization (offset estimation, outlier filtering) and on ordering rules like Lamport clocks. The choice between TrueTime-with-wait, HLC-with-uncertainty and a timestamp oracle is the central design decision of the family.

CockroachDB also uses closed timestamps: the leaseholder promises that no new writes will arrive at or below a timestamp that trails the present, and followers can serve reads at or below it once they have applied the log (source: transaction-layer page). This is how follower reads give stale-but-consistent data from the nearest replica.

Operations, change and recovery

Schema changes must not stop the world: add the new structure, backfill existing rows in bounded chunks (Chunked backfill), switch, then remove the old one (expand-contract-migration (no page yet)). Backups combine periodic base copies with the archived change log on cheap storage (Point-in-time recovery, Object storage); on one node, crash recovery follows ARIES recovery, while across nodes the Raft log and snapshots do that job. Traffic is encrypted and mutually authenticated (TLS 1.3, Mutual TLS). Consensus and clock bugs do not show up in ordinary tests, so the system is run in a deterministic simulator with seeded fault injection (Deterministic simulation testing, fault-injection (no page yet)) and fuzzed (Coverage-guided fuzzing).

Raft keeps the replicas of one range consistent inside a cluster, but a whole-cluster loss (a region outage, an operator error that deletes the cluster) needs a copy outside it. Primary-backup replication is that second layer: the live cluster is the primary and orders all writes, and it ships its committed change stream to a standby cluster in another region. The acknowledgement rule is chosen deliberately, because waiting for the standby on every commit adds a cross-region round trip while not waiting means a disaster loses the last few seconds of writes; most deployments accept the loss window. Promotion of the standby is decided by an external arbiter (an operator or a separate witness), never by the two clusters themselves, so a network split cannot leave two primaries. The standby's change stream is also the source for point-in-time restores.

Data and control flow

A single-range write (UPDATE accounts SET balance = balance - 10 WHERE id = 7).

1. The gateway parses and plans the statement. The optimiser chooses the primary-key lookup. The row key is computed.
2. The cached range index maps the key to a range and its leaseholder. On a miss the index is read through the meta ranges (or PD), which takes more round trips.
3. The request goes to the leaseholder. It reads the latest version at the transaction's timestamp, checks for conflicting intents and writes a new version.
4. The write is proposed to the Raft group, appended to the leader's log, sent to the followers, and applied once a majority has acknowledged. This costs one round trip to the nearest majority plus the log fsync on each member; across regions that round trip dominates, so replicas are placed to keep a majority close to the leader.
5. The gateway receives the acknowledgement and answers the client.

A multi-range transaction (transfer between two accounts on different ranges).

1. The transaction gets a timestamp from the HLC (or TSO, or TrueTime).
2. It writes provisional versions on each range's leader. Each write is replicated by that range's group (step 4 above).
3. At commit, the coordinator (gateway or participant leader) records the decision in the transaction record, which is itself replicated, so a coordinator crash does not lose the decision.
4. Commit is acknowledged after the decision is durable. With commit wait (Spanner) the acknowledgement is further delayed by the clock uncertainty. Intents are then converted to committed versions in the background.
5. A reader who meets an unresolved intent consults the transaction record and either waits, helps resolve, or aborts it.

Scaling

The first limit is single-range throughput, because one range's writes go through one leader and one log. Levers, in order: split hot ranges and move leaders, choose keys that do not append at the end of the key space, and use Group commit to batch log writes. The second limit is cross-range transactions: every extra range adds a consensus round and widens the failure window of two-phase commit, so schema design that keeps a transaction on one range (interleaving or co-locating, partitioning by tenant) is the strongest lever. The third limit is geography: write latency is the round trip to the nearest majority, plus commit wait where it applies, so place voters in a few nearby zones, add non-voting or follower replicas for far readers, and use stale reads where the application allows.

Failure modes

Real implementations

Sources

• J. C. Corbett et al., "Spanner: Google's Globally-Distributed Database", OSDI 2012: USENIX page, PDF; also Google Research.
• CockroachDB architecture docs: Overview, SQL layer, Transaction layer, Distribution layer, Replication layer, Storage layer.
• TiDB docs: Architecture, Storage, Computing.
• YugabyteDB docs: Architecture, Key concepts, Transactions overview.