The question this answers
What is actually inside a "distributed database", and which layer owns which guarantee?
The system as a whole guarantees the *conjunction* of its layers’ guarantees, restricted to the narrowest scope any layer imposes. In the common configuration that resolves to: linearizable single-key operations within one partition, no atomicity across partitions, and durability equal to the replication layer’s acknowledgement rule — not to the storage engine’s.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A node in this stack knows its own partition assignment as of the last routing update it received, the contents of its own storage engine, and the replication state it has itself observed. It does not know whether its partition map is current, whether another node believes it owns the same key range, or whether a write it acknowledged has survived on any machine but this one. Every one of those is an inference from a layer above.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
The six layers, and who you already know
Strip the marketing from any distributed store and the same stack appears. A request enters at an API layer that decides what an operation even is — a key-value get, a row read, a range scan. A partitioning layer turns the operation’s key into a partition, and the partition into a set of nodes. A replication layer decides how many of those nodes must participate before the client hears an answer. Underneath, a consensus or conflict-resolution layer decides what to do when two nodes disagree about what the value is. Below that sits an ordinary single-node storage engine — a B+ tree or an LSM tree, exactly the thing the Database domain teaches — and below that, a disk that lies about when it has actually written.
Nothing in that list is unfamiliar. Hash Partitioning and the Modulo Trap and Range Partitioning: Scans You Keep, Hotspots You Inherit are the second layer. Leader-Based Replication: Buying Order With a Single Writer and Quorums: What R + W > N Does and Does Not Buy are the third. The Raft Log: Commit Index, Divergence and Reconciliation and CRDTs: Deterministic Merge, Not Correct Merge are two different answers at the fourth. The interesting question is not what each layer does — you know that — but what happens to a guarantee as it travels up the stack.
The short answer is that guarantees are lost going up, never gained. An LSM tree that fsyncs before acknowledging gives you single-machine durability; the replication layer above it can *weaken* that to "durable on one machine, replicated later" but cannot strengthen a storage engine that does not fsync at all. A consensus layer can give you a total order over commits; a partitioning layer above it can hand that away by routing two related keys to two independent Raft groups that never talk.
Where each guarantee is actually decided
The most common design error in this area is attributing a property to the wrong layer. Teams say "the database is consistent" when they mean the storage engine is crash-safe, or "the data is durable" when they mean one replica fsynced. Each of those is a real property owned by a real layer, and each has a different failure that breaks it.
Read the table below as a routing guide for blame. When something goes wrong, the layer named in column two is the one to interrogate — and the failure in column three is what you would see if that layer were the culprit.
| Property you were promised | Layer that decides it | What its failure looks like |
|---|---|---|
| Atomicity of one operationprotocol | Storage engine (WAL) | Torn record after a crash — rare, and a genuine engine bug |
| Durability of an acknowledged writeassumption | Replication layer’s ack rule, not the engine | The write is gone after one node is replaced, and no error was ever returned |
| Single-key linearizabilityassumption | Consensus or a strict quorum over one partition | A read returns a value older than one a previous read returned |
| Atomicity across two keystypical | Nobody, unless the keys share a partition | Half of a logical change is visible; the other half never lands |
| Ordering between two partitionsprotocol | Nobody, unless a total-order layer exists | A downstream consumer sees effect before cause |
| Availability during a node losstypical | Replication factor + placement policy | A partition goes read-only, or the whole key range 503s |
The seam that surprises people: partition boundaries
Layers three and four — replication and agreement — do their work *inside* a partition. That is not an implementation detail; it is the whole economics of the design. Consensus over a hundred nodes is unusably slow, so real systems run a hundred independent consensus groups of three or five nodes each, one per partition. Each group is beautifully linearizable. Between groups there is nothing.
So a store can be entirely honest in saying "linearizable" and still let you observe an update to key A that logically precedes an update to key B, with a reader seeing B before A. The linearizability was per-partition, and your two keys hashed to different partitions. This is why Cross-Partition Operations: Paying for What the Split Took Away is its own hard problem and why Distributed Uniqueness: One Name, Many Shards is not free: a uniqueness constraint spans the whole key space and therefore spans every partition.
The practical move is to make the partition boundary a design decision rather than an accident. If two pieces of data must change atomically, co-locate them under one partition key and the whole stack gives you atomicity for free. If they cannot be co-located, you are in Atomicity Stops at the Process Boundary territory and the answer is a saga or a reconciliation job, not a configuration flag.
- One consensus group per partition is the standard shape — not one group per cluster.
- A guarantee stated without a scope ("linearizable") almost always means "per key" or "per partition".
- Co-locating related keys converts a distributed-transaction problem into a local one, and is usually cheaper than any protocol.
- A secondary index is a second partitioning of the same data, so it inherits the cross-partition problem by construction.
Reading a real system’s claims
The stack gives you a checklist for reading documentation. For any store, ask each layer’s question in order and refuse to move on until you have an answer with a scope attached.
Most vendor pages answer three of the six and leave the other three to a footnote or a blog post. The unanswered ones are where your incident will come from.
API What is one operation? → "single-key get/put; multi-key batch is NOT atomic" Partitioning How is the key mapped? → "hash of the first component of the primary key" Replication How many acks before 200? → "1 local fsync + async fan-out" ← the durability answer Agreement Who wins a conflict? → "last write wins, by node wall clock" ← the data-loss answer Engine Crash-safe on one node? → "WAL, fsync per commit group" Disk fsync honoured? → "depends on the volume; cloud disks vary"
Key points
- A distributed store is six familiar layers stacked, not a new primitive.
- Guarantees weaken going up the stack and never strengthen: no layer can add durability the disk below it does not provide.
- Replication’s acknowledgement rule — not the storage engine — decides what "durable" means to a client.
- Consensus runs per partition, so "linearizable" almost always means "linearizable per key".
- Two keys that must change together should share a partition; that turns a distributed problem into a local one.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • The API layer turns a request into one or more keyed operations and decides whether they are atomic together.
- • The partitioner applies a partition function to each key and looks the partition up in a routing table it may hold a stale copy of.
- • The replication layer selects the replica set for that partition and applies the write rule — leader-only, W of N, or all.
- • If replicas can disagree, an agreement layer resolves it: a consensus log imposes an order, or a conflict-resolution rule merges values.
- • The chosen mutation is handed to a single-node storage engine, which writes it to a log and then to its main structure.
- • The engine calls fsync (or does not), and the disk reports completion (or lies about it).
- • An acknowledgement travels back up. Each layer decides how much of the stack below it had to finish before it answers.
- • The routing table is stale and the request is sent to a node that no longer owns the partition.
- • A replica accepts a write and then fails permanently before the write reaches any other replica.
- • The partition’s consensus group loses its majority and the whole key range becomes unavailable while the rest of the cluster is healthy.
- • Two operations that the application thought were atomic land in different partitions and are ordered independently.
- • The disk acknowledges an fsync that is still sitting in a volatile write cache.
- • Half-applied logical change: the operator sees an order row with no matching payment row, no error in any log, and both writes reported 200 — the two keys were in different partitions.
- • Silent durability gap: a node is terminated and replaced; some writes that returned 200 are simply absent. Error rate never moved, because the loss produced no error anywhere.
- • Cluster-healthy, key-range-dead: dashboards are green at the cluster level and one partition returns errors for every request, because that partition’s replica set lost quorum.
- • Routing flap after rebalance: clients get a burst of "not the owner of this key" retries whose rate correlates exactly with partition movement, not with load.
- • Stale-read staircase: a read returns a value, a later read on a different connection returns an older one, and both are legal because the guarantee was per-partition and the reads went to different replicas.
- • Inside a partition: whatever the replication and agreement layers require — one round trip to a majority for a consensus write, or W acknowledgements for a quorum write.
- • Across partitions: none by default, which is exactly why cross-partition atomicity is missing. Adding it means adding a coordinator, and that coordinator becomes the availability floor of every operation that touches it.
- • Routing changes are themselves coordinated state: the partition map must be agreed on, or two nodes will each believe they own the same key range.
- • Each partition’s guarantee holds or fails independently — the blast radius of a lost replica set is one key range, not the cluster.
- • Writes already acknowledged under a strict quorum survive a minority loss; writes acknowledged under a local-fsync-only rule may not survive any loss at all.
- • Range scans and secondary index reads degrade first, because they touch more partitions and therefore have more ways to be partially unavailable.
- • Detect: alert per partition, not per cluster. Cluster-level availability hides a dead key range behind ninety-nine healthy ones.
- • Contain: fence the stale owner before letting a new owner accept writes — Fencing Tokens: Making the Stale Actor Safe, Not Just Unlikely exists precisely for this seam between the routing layer and the storage layer.
- • Recover: re-replicate the under-replicated partitions before touching anything else; an under-replicated partition is one failure away from data loss, not from an outage.
- • Reconcile: for cross-partition changes that half-landed, a reconciliation job comparing the two sides is the only cure — the stack never promised to prevent it.
- • Verify: read back a sample of recently acknowledged writes from a replica that was *not* the one that accepted them.
- • Per-partition availability and per-partition p99, not cluster aggregates — the aggregate is the metric that hides this class of failure.
- • Under-replicated partition count, with the age of the oldest one. Age matters more than count.
- • Routing-table version skew across clients: the spread between the newest and oldest map version in use.
- • Ratio of cross-partition operations to single-partition ones — it tells you how much of your traffic has no atomicity guarantee.
- • Acknowledgement rule in effect per table or keyspace, exported as a metric rather than read from a config file during an incident.
- • Reading a new system’s documentation: the six questions turn a marketing page into a list of things you do or do not know.
- • Incident triage: the layer that owns the broken property tells you where to look first, instead of bisecting the whole stack.
- • Design review: asking "which partition are these two keys in?" catches most missing-atomicity bugs before they are written.
- • For a single-node database with a read replica, this decomposition is overhead — there is one partition, the layers collapse, and the reasoning adds nothing.
- • Treating the layers as independently swappable in your own build invites a system where each layer is defensible and the composition is not.
- • Use one node until it genuinely stops fitting. A single Postgres with a well-tuned engine gives you every guarantee in this table without any of the seams.
- • Buy the composition rather than assembling it: a managed store that publishes its per-layer guarantees is cheaper than a stack you have to reason about yourself.
- • Keep data that must be atomic together in one system and accept eventual consistency at the boundary between systems, rather than trying to make the boundary transactional.
Six layers, and which one owns the guarantee you were promised
API What is one operation? → "single-key get/put; multi-key batch is NOT atomic" Partitioning How is the key mapped? → "hash of the first component of the primary key" Replication How many acks before 200? → "ack after local fsync" <- the durability answer Agreement Who wins a conflict? → "last write wins, by node wall clock" <- the data-loss answer Engine Crash-safe on one node? → "WAL, fsync per commit group" Disk fsync honoured? → "yes, verified on this volume"
| Property you were promised | Layer that decides it | What its failure looks like |
|---|---|---|
| Atomicity of one operationprotocol | Storage engine (WAL) | Torn record after a crash — rare, and a genuine engine bug |
| Durability of an acknowledged writeassumption | Replication layer's ack rule, not the engine | The write is gone after one node is replaced, and no error was ever returned |
| Single-key linearizabilityassumption | Consensus or a strict quorum over one partition | A read returns a value older than one a previous read returned |
| Atomicity across two keystypical | Nobody, unless the keys share a partition | Half of a logical change is visible; the other half never lands |
| Ordering between two partitionsprotocol | Nobody, unless a total-order layer exists | A downstream consumer sees effect before cause |
| Availability during a node losstypical | Replication factor + placement policy | A partition goes read-only, or the whole key range 503s |
What people believe, and what is true
A distributed database is fundamentally different from a normal one.
The bottom two layers are the same B+ tree or LSM tree and the same disk. Everything above them is partitioning and replication, which you can name individually.
If the storage engine fsyncs, the write is durable.
It is durable on that machine. Whether it survives that machine being deleted is decided by the replication layer above, which may have answered the client already.
"Linearizable" means the whole database is linearizable.
It almost always means per key, sometimes per partition. Two keys in different consensus groups have no defined order between them.
Adding a strong consistency setting fixes cross-partition anomalies.
It strengthens what each partition promises. If the two writes are in different partitions there is no layer for the setting to act on.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
A distributed store is an API, a partitioner, a replicator, an agreement rule, a storage engine and a disk. Ask each layer what it guarantees and with what scope; the answer to the whole is the narrowest of the six.
Practical
For every system you depend on, write down its six answers, especially the acknowledgement rule and the conflict rule. Then look at your own access patterns and count how many operations cross a partition boundary — that count is your exposure to anomalies no setting will fix.
Advanced
The composition failure that matters is not a weak layer but a *scope mismatch* between adjacent layers. A consensus layer whose scope is one partition sitting under an API whose scope is a multi-key batch produces a system that is correct at every layer and wrong end to end. When you design one, make each layer state its scope in the same vocabulary as the layer above, and the mismatches become visible instead of emergent.
Apply it
- 💬 Your store advertises linearizability. A colleague says two writes were reordered. Both statements are true — explain how.
- 💬 Where in the stack is "durable" decided, and why is it usually not the storage engine?
- 💬 You need two rows to change atomically in a partitioned store. What are your options, cheapest first?