Distributed Key-Value Store Tradeoffs: Partitioning, Replication, Consistency, Storage Engine & Region Decisions

A distributed key-value store is a stack of choices, and every one of them is a bet about which failure you would rather have. This page reopens 28 of them for a fictional product, Meridian Profiles, and for each one asks what went wrong that forced the choice, what the options cost, what the reference design picks, and what would have to change for a different answer to win.

Meridian Profiles is invented for teaching: a B2B platform that stores user preferences, account settings and tenant configuration as durable records. Atlas is its large, hot tenant; Birch and Cedar are smaller. Keys are tenant-scoped, such as atlas/user42/settings, and one famous key, atlas/feature=checkout_policy, is read far more than anything else. Every number below is either a hypothetical planning input from the complete design (2,000,000,000 records of about 1 KiB, 200,000 reads/s on average and 1,000,000 at a short peak, 40,000 writes/s on average and 200,000 at peak) or is labeled *assumed*. None of it is a measurement.

The reference design is deliberately singular, so the comparisons have something to push against. Data is cut into 1,024 logical partitions; each partition has three replicas in different failure domains (separate racks, power feeds or zones, so one fault cannot take two copies), one of them leader; writes go through a replicated commit log (an ordered, append-only record of every change) and are acknowledged once a majority has them durably; a conditional write is part of that replicated state machine, not something a client simulates with read-then-write. The word *Raft-like* describes the conceptual model (term, log index, committed index, leader id). It is not a claim that any particular product matches it, and replication factor 3 on its own is not consensus: three copies without an agreed order are just three places for different answers to live.

The decisions are grouped by the layer they act on rather than listed in a flat table, because most of them only make sense next to their neighbors: the replication choices constrain what a read can promise, and the storage-engine choices decide what a repair costs. A summary table at the end compares three conceptual families (leaderless, range tablets, leader-based consensus) once the individual arguments are on the table.

Before any replication question there is a prior one: what kind of system is this, and how does a key get to the machine that owns it? The first four decisions settle the role of the store and the geometry of its keyspace, and they are the hardest to change later because every client and every byte on disk depends on them.

Decision 1 · Durable key-value database or in-memory cache?

The incident is an ordinary Tuesday. An admin at Atlas switches atlas/feature=checkout_policy from permissive to strict, and the change lives in a cache node that holds the only copy. The node restarts for a kernel patch, comes back empty, the application reloads defaults, and checkout quietly reverts to the permissive policy. Nobody lost a cache entry; they lost a decision somebody made.

The options are a pure cache (fast, memory-sized, and by contract allowed to forget), a cache with optional persistence, and a durable store whose acknowledgement means the write survives a crash. The cache is far cheaper per read, but its promise is about latency, not about keeping what you gave it. Persistence modes in caching products can narrow the gap, yet they usually trade durability against throughput through a flush interval, and the product's defaults and failure behavior are what you inherit. In Redis, for example, the append-only file defaults to an fsync once per second, so a crash can lose roughly the last second of acknowledged writes; that is a deliberate speed-for-durability trade, and stricter settings cost throughput. A durable key-value database spends a write-ahead log (WAL: a file to which every change is appended and flushed before the write is acknowledged) fsync and a majority of replicas on every write to buy the opposite promise. See Redis fundamentals for a cache-shaped use of Redis, and read its persistence documentation before treating it as equivalent to a disk-first store.

The reference chooses the durable store as system of record for settings, with caches allowed in front as an optimization that is always reconstructible from it. The reason is the direction of loss: a stale or empty cache costs a reload, an empty system of record costs a customer's configuration. This is also why the sizing in the complete design is about throughput rather than capacity: 2.048 TB of logical data is modest, and the expensive part is 600,000 replica write-applies per second at peak.

A cache wins when every value can be rebuilt from somewhere authoritative, the hit rate matters more than any single entry, and a cold start is survivable. Choosing durability also means you now own backups, repair, upgrades that must not lose quorum, and a latency budget in which fsync is a line item. A cache in front is fine, but it is a second consistency domain, and any page that says "strongly consistent" must say which side of the cache it means.

Decision 2 · Hash partitioning or range partitioning?

Birch's onboarding job writes birch/user0001/settings through birch/user9999/settings in order, and a team wants to list everything under birch/. Those are opposite requests. The ordered writes want to be spread out; the listing wants neighbors kept together.

With hash partitioning the key is hashed and the hash picks the partition, so sequential keys scatter evenly and no partition collects a monotonic hot tail. The cost is that prefix and range queries become a fan-out across every partition, which is why the reference does not promise them on hashed data. Range partitioning keeps keys sorted and splits by key interval, so a prefix scan touches a few partitions; the cost is that sequential or time-ordered keys all land on the last range, and a popular prefix becomes a hot partition that has to be split by hand or by policy.

The reference hashes the key for the point-lookup workload, which is almost everything Meridian does, and offers Scan(prefix) only for tables explicitly declared range-partitioned, with the limits spelled out in the API. That keeps the common path free of hot tails and keeps the scan promise honest. The alternative wins when the dominant query is a range (time-series, ordered logs, leaderboards) and the key design can avoid a single moving hot edge, for instance by prefixing a bucket or tenant. Day to day, hash placement means rebalancing is about whole partitions and per-partition metrics, while range placement adds split and merge events and a need to watch for skew by key interval.

Decision 3 · Modulo hashing, virtual partitions or tablets?

A team starts with partition = hash(key) mod 3 and it works until the fleet goes from three nodes to four. A key stays put only if h mod 3 == h mod 4, which holds for 3 of every 12 residues: 25% of keys stay and 75% move. At 2.048 TB logical, that is 1.536 TB of data relocating, or 4.608 TB counting RF=3 copies, to add one machine.

Three families address it. Plain modulo is trivial and shuffles almost everything on any change. Consistent hashing, or equivalently a large fixed set of virtual partitions assigned to nodes, moves only what the new node should own: going from three nodes to four, ideally 25% of the data (0.512 TB logical), all of it onto the new node, and in the scene illustration 3 of 12 virtual partitions. That is not zero movement; it is the minimum that rebalancing physically requires. Tablets (the range-partitioned cousin) split and merge by size or load, which adapts to uneven data but needs a metadata service to track boundaries. See consistent hashing for the ring variant.

The reference uses 1,024 fixed logical partitions mapped to nodes through a versioned partition map. Fixed partitions make the unit of movement, repair and metrics constant (about 2.0 GB logical each), and the map makes ownership explicit rather than computed. The price is that 1,024 is a ceiling on how finely load can be spread, and that the number should be chosen with generous headroom because changing it is a re-partitioning project, not a configuration edit. Tablets win when range scans matter or data is very uneven. Treat the partition map as critical metadata: it needs its own replication, an epoch (a version number that rises on every ownership change) on every entry, and alerts when two nodes believe they own the same partition.

Decision 4 · Client-direct routing or coordinator/proxy routing?

During a migration, an SDK in Atlas's checkout service still holds the old partition map. It sends Put(atlas/user42/settings) to the node that used to own the partition. If that node accepts the write, the write lands on a replica group that no longer owns the data, and the mistake is only found when somebody reads it back.

Client-direct routing gives one fewer hop and no proxy fleet, but it pushes the partition map and its refresh logic into every client language and every client version. A proxy or coordinator tier centralises the map and the retry policy, costs an extra network hop and its own capacity, and becomes one more thing to keep available. In between sits the hybrid that most mature stores converge on: clients cache a map hint, but the server is the authority.

The reference uses a thin routing tier with a cached partition map for ordinary traffic, and makes the *nodes* the safety mechanism: every request carries the map epoch, and a node that does not own the partition at that epoch answers with a retryable WRONG_EPOCH or a redirect instead of serving. Staleness in a cache then costs one extra round trip, never a misplaced write. Direct routing wins when latency is tight and the client population is small and controlled. You will want a redirect-rate metric (a spike means a map is stale somewhere), versioned and monotonic partition-metadata changes, and the freedom to upgrade servers before clients without breaking correctness.

One copy of a partition dies with its machine, so the next decisions are about copying: who orders writes, when the client hears "done", and which copy may answer a read. These choices decide what the word *consistent* means in the product, and they are the place where intuition from quorum arithmetic most often misleads.

Decision 5 · Leader-based replication or leaderless replication?

Two writers update atlas/user42/settings at nearly the same moment, one from a browser session in Frankfurt and one from a batch job. In a leader-based design both requests reach the same leader, which puts them into one order in the log, and the second observes the first. In a leaderless design they can reach different replicas, both succeed, and the store now holds two versions that nobody ordered.

Leader-based replication buys a single sequence per partition: followers apply what the leader committed, a conditional write is just another log entry, and a read through the leader can be linearizable. The costs are a failover (election, fencing of the old leader, a window with no leader) and a leader that is a throughput ceiling for its partition. Leaderless replication sends writes to several replicas through a coordinator and converges afterwards with read repair (fixing a stale replica when a read notices it), hinted handoff (another node holds a write for a replica that was down and replays it later) and anti-entropy (background comparison and repair of replica contents). It stays writable through more failure shapes and has no election, but concurrent writes must be resolved with last-write-wins, which can discard an update silently, or with version vectors and siblings, which hand the merge to the application. The Cassandra documentation states plainly that hints do not guarantee eventual consistency the way anti-entropy repair does, which is a good reminder that the repair machinery is part of the design, not an afterthought.

The reference is leader-based because Meridian's records are settings with real consequences and a conditional-update requirement; what it cannot tolerate is silently merging two versions of a policy. Leaderless wins for workloads where the write must be accepted somewhere almost always and conflicts are rare or mergeable (carts, counters, presence, and many time-series shapes). Choosing leader-based means you monitor election rate, leader balance across nodes, and commit latency; choosing leaderless means you monitor repair age, sibling counts and hint backlogs instead.

Decision 6 · Strong consistency or eventual consistency?

A network partition cuts rack 2 off from the rest. Inside it, a follower holds atlas/user42/settings at v7; on the other side the leader has committed v8. A client in rack 2 asks for the settings. Whatever the system does now is the consistency decision, not a sentence in a brochure.

Under partition the store must choose for the affected operations: refuse or delay the request (consistency), or answer from what it has (availability). CAP is about exactly this moment and is not a "pick any two" menu for ordinary days. Strong consistency here means single-key linearizability: once a write is acknowledged, every later read observes it or something newer. That requires the read or write to involve a majority, so the minority side must reject. Eventual consistency lets every side answer and promises that replicas converge once the partition heals, with no bound on how stale an answer may be and nothing that says which of two concurrent writes wins.

The reference chooses linearizable single-key operations in the home region as the default and exposes weaker read modes by name (follower-stale, read-your-writes, eventual), so a caller opts into staleness deliberately. Eventual wins when the cost of a stale answer is smaller than the cost of an error: recommendation feeds, view counters, cached profile fragments. The price of the strong default is that it converts a partition into visible 503s on the minority side, which means error budgets, client retry policy and alerting on lost quorum have to exist before the incident rather than during it.

Decision 7 · Quorum write or asynchronous follower replication?

The leader appends a write for atlas/user42/settings, replies 200 to the client, and crashes before it has sent the entry anywhere. A follower is elected. It does not have the write. The client was told it succeeded, and the data is gone.

Asynchronous replication acknowledges after the leader's local durability and ships to followers later: the lowest write latency, but the acknowledged window is exactly the replication lag and can be lost if the leader dies. A quorum write acknowledges only when a majority has the entry durably, so with RF=3 two copies exist when the client hears success, and any newly elected leader is guaranteed to include it. The cost is that commit latency is set by the second-fastest replica, not the leader, and that losing two of three replicas stops commits entirely. RF=3 tolerates one failure for writes; "any two lost and writes still succeed" is false. RF=5 with a majority of 3 tolerates two.

The reference commits on a majority. Asynchronous replication is reserved for the remote region in Decision 23, where the distance makes synchrony expensive and the loss window is named explicitly. Async wins within a region only when the data is cheap to regenerate and the latency saved matters more than the loss. Watch commit latency (it hides a slow follower), under-replicated partitions, and the count of partitions with exactly a bare majority; the last one is the early warning that the next failure is an outage.

Decision 8 · Read from the leader, a follower, or a quorum?

Atlas rolls out a new checkout policy, and a minute later one pod in the fleet still enforces the old one. It read from a follower that was lagging behind the leader. The write was acknowledged and visible to anyone who asked the leader; the follower simply had not applied it yet.

A leader read is cheap and, if the leader confirms it is still the leader (through a read-index round, where it checks with a majority before answering, or through a lease, a time-limited promise from followers not to elect someone else), it is linearizable. A quorum read asks a majority and takes the freshest answer: it works without leader trust but multiplies read traffic. A follower read spreads load and can be served near the caller, with the price of an explicit staleness bound or none at all. Leases are fast because they replace a network round trip with a time check, and for the same reason they depend on bounded clock drift and careful fencing.

The reference serves linearizable from the leader with read-index or a lease, and offers follower-stale as a labeled mode (bounded by a version floor or maximum lag when the caller supplies one). The 60,000 reads/s hot key later in Decision 25 is the case that tempts teams toward followers; it works only when the caller accepts the staleness. Quorum reads win in leaderless designs and in rare moments when leader trust is in doubt. The operational need is a replica-lag metric per partition, a read-mode tag in every trace, and a rule that dashboards compare leader and follower versions.

Decision 9 · Strict linearizability or bounded-staleness reads?

A support dashboard polls every tenant's settings once a second, and its traffic is about to be a large share of leader load. Nothing about a dashboard needs the answer that is true this microsecond; it needs one that is true within a few seconds.

Strict linearizability gives the simplest mental model, since a read never goes backwards, at the cost of routing each read through the leader and paying its confirmation. Bounded staleness lets a follower answer if its applied index is within a stated lag of the leader's committed index, or at least as new as a version the client already observed (read-your-writes via a session token or version floor). It lowers leader load and latency but demands that the bound is measured, not promised: a follower that cannot prove its freshness must redirect or refuse. See the contrast below.

The reference defaults to linearizable and supports bounded-stale reads only when the caller asks and the follower can prove its position. Read-your-writes is the pragmatic middle for user-facing flows: after a save the client carries committedVersion and later reads must be at least that new. Strictness wins for decisions that gate money or access; boundedness wins for read-dominant reporting. This is where lag histograms earn their keep, and a slow follower must degrade into redirecting traffic back to the leader rather than serving stale data without a label.

Replication decides which machines hold a write; the storage engine decides what that write costs on each of them. These five decisions are about turning a stream of small random updates into disk work you can afford, and about the reads, compactions and CPU you pay for afterwards.

Decision 10 · fsync every write, or group commit?

A power event takes out a rack. Replica B acknowledged a write for atlas/user42/settings after calling write() on its log file, but the bytes were still in the operating system's page cache. When B came back, the record was not in its log. A write() into the page cache is not durable; fsync, on a storage stack that honours flushes, is what puts it on stable media.

Syncing every record individually is simple and is the safest, but each fsync is a serial, expensive wait, so a node's throughput is capped by how fast it can flush. Group commit gathers the records that arrive within a short window and issues one fsync for all of them, acknowledging everyone together after it completes. With the assumed peak of 6,250 write-applies per node per second and a 1 ms window, a flush covers roughly 6.25 records on average, and the more concurrency there is, the better it amortises. Batched persistence that acknowledges *before* the flush is a third option, and it is a different contract: a crash can lose acknowledged writes.

The reference uses group commit with a short, bounded window and never acknowledges before the flush. The window adds up to that many milliseconds to every write's latency and is paid back in throughput; it should be tuned against measured commit latency, not copied from a blog. Relaxed durability wins only for data you declare disposable, in a different table with a different name. fsync latency deserves a dashboard of its own; a disk with a volatile write cache that ignores flush requests invalidates the whole argument, and the hardware should be qualified for it.

Decision 11 · LSM-tree or B-tree?

Write volume doubles after Atlas launches a bulk import, and the nodes' disks go from comfortable to saturated even though the client request rate rose modestly. A single logical write is being rewritten several times underneath.

A B-tree updates pages in place: reads are predictable (a few page fetches), range scans are natural, and the cost is random writes and page rewrites for small updates. A log-structured merge tree (LSM) appends writes to a log and an in-memory sorted buffer (the memtable), flushes it as sorted immutable files (SSTables) and merges those files in the background (compaction). It turns random writes into sequential ones, and the price is read amplification (a key may be in several files) and write amplification from compaction. A Bloom filter (a compact in-memory structure that says a key is definitely absent or possibly present) at 10 bits per key and 7 hash functions gives about a 0.82% false-positive rate and no false negatives; at 1,953,125 keys per partition replica that is about 2.44 MB, roughly 78 MB per node across 32 replicas. A lookup of an absent key across 5 files then expects about 0.04 needless disk reads.

The reference uses an LSM engine because the workload is write-heavy by count (40,000 writes/s on average, 200,000 at peak) and point-lookup-dominated, which is what Bloom filters help most. The write-amplification factor of 10 used elsewhere is an assumed illustration; the real number depends on compaction strategy and data, and must be measured. A B-tree engine wins for read-heavy, update-in-place workloads with strong range-scan needs and modest write rates. From then on compaction is a permanent background tenant of the disks, and any quoted write throughput has to come with the compaction debt that accompanies it.

Decision 12 · Size-tiered, leveled or time-window compaction?

A month after launch, p99 reads on one hot partition climb even though traffic is flat. A look at the node shows that a point read now consults many overlapping files; compaction has been running behind, and the number of files that might hold a key has grown.

Size-tiered compaction merges files of similar size: it has low write amplification and is friendly to write bursts, but leaves overlapping files behind and can need large temporary space to merge. Leveled compaction keeps files in levels with non-overlapping key ranges, so a read touches roughly one file per level, at the price of rewriting data many times as it moves down. Time-window compaction groups files by time bucket, which is excellent for data with TTL that expires by window because whole files can be dropped, and poor for data that is updated in place. Cassandra documents all three strategies; their behavior in other engines differs and should be checked.

For Meridian, reads outnumber writes about five to one at average load and the SLO is a read latency percentile, so the reference leans leveled for the settings table and accepts the higher write amplification; it is a measured choice, not a rule. Time-window wins for append-only data with expiry, and size-tiered for write-dominated, read-tolerant tables. The metrics that matter here are pending compactions, files per read and disk free space (a 60% ceiling keeps compaction temporary space and repair possible), and strategy changes are slow, disk-heavy migrations to be scheduled.

Decision 13 · Optimize for point lookups or for range scans?

An engineer asks for Scan(atlas/) to export a tenant's settings, and the first implementation fans out to all 1,024 hashed partitions, merges the answers, and takes the cluster's p99 with it for the duration.

Point-lookup design uses hash placement, Bloom filters and small, hot caches of index blocks; it does not care about key order. Range-scan design wants sorted, contiguous data, range partitioning, prefix-aware filters and iterators that stream. Doing both well in one table is possible only up to a point, because the techniques pull in opposite directions: hashing destroys locality, and sorted layouts concentrate load.

The reference optimizes the default table for point lookups, and offers scans on a separate, range-partitioned table class with limits on span and rate; an export is done through a snapshot or the change stream rather than a live scan. Range-first wins for ordered data (time-series, queues, feeds) and for secondary orderings. The API therefore has to state the cost plainly (a scan is not a long Get) and give each tenant a scan budget, because the unbounded scan is the cheapest way for a tenant to hurt others.

Decision 14 · Compress, and at what CPU and compaction cost?

Storage is not the bottleneck in this workload, yet the cluster nodes spend measurable time in a compaction thread reading and writing JSON settings blobs that are mostly repeated field names.

Block compression shrinks files, reduces disk and network bytes for reads and for replication of SSTables, and can help I/O-bound workloads; it costs CPU on write, flush and compaction, plus decompression on every read that misses the block cache. Stronger codecs shrink more and cost more CPU; lighter ones save less and cost little. Settings JSON typically compresses well, but the ratio is a property of your data and should be measured rather than assumed. Compression also interacts with compaction: rewriting data repeatedly means compressing it repeatedly, so high-level (cold) files are the better home for strong compression.

The reference uses a light codec on hot levels and allows a stronger one on the coldest level, since the workload is throughput-bound and CPU is the scarce budget; the disk worksheet (10.752 TB provisioned minimum, a modest figure next to the 96-node throughput need) says space is not the motivation. Heavier compression wins when you are capacity- or network-bound. Record the compression ratio per level and the CPU spent per compaction so the decision can be revisited with data; codec changes apply to new files and take a full compaction cycle to show up.

A replicated commit log guarantees what order writes happen in. It does not say what a *client* is allowed to assume between reading and writing. These three decisions set the boundary of the product: what a write can depend on, how many keys it can touch, and how you look something up without its key.

Decision 15 · Conditional writes with versions, or unconditional last-write-wins?

Two admin sessions open Atlas's settings page showing v7. One disables the beta flag and saves; the other changes the date format and saves a moment later, with the beta flag still on in its form. If the store takes whichever write arrives last, the flag change is silently undone and nobody gets an error.

Unconditional last-write-wins is the simplest API and the highest availability, because any replica may accept any write. It is also data loss by design whenever two writers overlap, and with timestamps it depends on clock agreement, so a skewed clock can make an older write win. Compare-and-set carries expectedVersion with the write; the leader checks it as part of the replicated state machine, and a mismatch is rejected with a 412 Precondition Failed, which is how the second admin learns the page was stale. A third family, version vectors with siblings, keeps both concurrent writes and asks the application to merge.

The reference makes CAS a first-class operation inside the log, so the check and the write are atomic: the sequence read v7, write v8 only if still v7 cannot be interleaved. Client read-then-write is the anti-pattern here, because the gap between the two calls is the race. Last-write-wins is right for data where the newest value is simply the truth (heartbeats, last-seen timestamps). A rising 412 rate is a product signal (editors colliding), clients must be taught to re-read and retry deliberately, and a retried CAS needs an idempotency key so that a timeout does not apply twice.

Decision 16 · Multi-key transactions or single-key atomicity?

Moving a user from tenant Birch to tenant Cedar means deleting birch/user17/settings and creating cedar/user17/settings. If the process dies between the two calls, the user exists in both places, or neither.

Single-key atomicity is cheap to reason about: one key lives in one partition with one leader, and linearizability is local. Multi-key transactions need an atomic commit across partitions (two-phase commit or a similar protocol), locking or timestamp ordering, and recovery for a coordinator that crashes mid-way; throughput and availability pay for it. The middle road is orchestration: model the move as a saga with idempotent steps and explicit compensation. That gives up isolation (other readers can see the in-between state) for independence of partitions. See transactions and concurrency and the saga pattern.

V1 supports no cross-key transactions: the product scope says so, and the right shape for the move is a saga, or a single record that holds both. Transactions win where invariants span keys (balances, inventory) and the store was built for it; FoundationDB, as one example, is described as an ordered transactional key-value store. Teams choosing it accept the extra latency and coordination. A side benefit of single-key atomicity is that one partition's health is the only variable in a write's success, which keeps incident analysis simple.

Decision 17 · Secondary indexes and views, or application-maintained query paths?

Support asks to find every user with locale = de-DE across the tenant. The store only knows keys, so the first answer is a scan of everything.

A built-in secondary index makes the query easy and the write harder: each write touches the index too, either in the same partition (a local index, cheap to keep consistent, but queries fan out to every partition) or in a different one (a global index, which makes a single write a multi-partition operation with its own consistency story). An application-maintained index, written by a consumer of the change stream into a separate table or a search system, is eventually consistent, and the store stays simple. See CQRS for the pattern.

The reference keeps V1 to primary-key access and treats queries as a derived read model fed by the change stream, because indexing inside the commit path would put a second system's availability on the critical path of every write. A built-in index wins when lookups by attribute are on the user-facing path and the extra write cost is acceptable. Index lag then becomes a monitored quantity, and a rebuild-from-snapshot job has to exist, since derived data must always be reconstructible.

A store that accepts data must also give it back, expire it and sometimes erase it. In a replicated LSM store, "delete" is not an act but a process that runs through replicas, compaction and backups, and each of these decisions chooses how long that process takes and what can go wrong while it does.

Decision 18 · Server-side expiration or read-time lazy TTL?

Meridian keeps invitation tokens for 7 days. A reader asks for one at day 7 plus a minute, and the node answers 200 because the background expiry job has not run yet. The token was meant to be dead.

Read-time lazy enforcement compares the expiry time to the clock whenever a record is read, so correctness does not depend on a sweeper; the dead bytes remain on disk until something removes them. Server-side expiration removes the data in the background, through compaction or a scheduled sweep, which reclaims space but leaves a visibility gap between the deadline and the removal. Both depend on time, so clock skew between replicas matters: a replica with a fast clock may hide a record that its peers still serve. The robust combination is to enforce on read *and* to reclaim in the background.

The reference does both: the TTL deadline is stored with the record, reads never return an expired value, and a compaction filter reclaims it. Reclamation is not instant and the product must not claim it is. Lazy only is acceptable when volume is small; server-side only is acceptable when nobody depends on exact expiry. Worth tracking are expired-but-resident bytes and clock-offset alarms, and deadlines should be agreed from a single source such as the leader's commit timestamp where possible.

Decision 19 · Immediate deletion, or tombstone and repair lifecycle?

Cedar's admin deletes cedar/user30/settings. Replica C is down for maintenance and misses the delete. A and B keep the tombstone for a while and then compact it away; when C finally returns after that, it still holds the old record, and with no tombstone left to contradict it, the next repair spreads the record back to A and B. The deleted data is alive again.

In an LSM store, files are immutable, so a delete is a new record, a tombstone, that shadows older versions during reads and is purged by compaction later. If the tombstone is dropped by compaction before every replica has seen it, the old value looks like the only truth and resurrects. Physically removing the data immediately would require every replica, snapshot and backup to cooperate synchronously, which is the opposite of what a fault-tolerant system allows. Two options remain in practice: keep tombstones for a retention period and repair before it expires (the reference), or accept the resurrection risk. In a log-replicated design the common catch-up path is safer, because a returning replica receives the delete as an ordinary log entry or a snapshot taken after it; the danger sits in the other paths, such as a replica rebuilt from an old disk image or backup, or an out-of-band repair of files, once the tombstone has already been compacted away.

The reference replicates the delete as a versioned tombstone through the log, makes the logical delete visible immediately (a read returns 404, or a distinct deleted status if the product chooses to expose one), and treats physical removal as a bounded background process. For regulated erasure, the honest answer is a time window, covering compaction and backup retention (Decision 21), rather than an instant. In practice deletes are cheap, space reclamation is lagging, and a deletion SLA has to be defined against the *slowest* component in the chain.

Decision 20 · Tombstone retention: how long, and at what cost?

The tombstone retention period is the question buried in Decision 19. Set it to a few hours and a replica that was down over a weekend comes back too late: the tombstone is gone, its old data is not, and it returns to life. Set it to a year and the table carries tombstones nobody needs, slowing reads that must skip over them.

The rule is that retention must exceed the longest time any replica may be out of the cluster, or unrepaired, before it is repaired or removed. Cassandra's documented default gc_grace_seconds is 864,000 seconds, ten days, after which tombstones are dropped during compaction; Meridian takes 10 days as a teaching value. A longer retention is safer and costs storage and read-time scanning; a shorter retention is cheaper and demands a tight repair cadence and rapid replacement of dead nodes. Hinted handoff does not substitute for repair here, because hints are best-effort and are only stored for a limited window (recent Cassandra configs show 3 hours; check the version you run).

The reference pairs a 10-day retention with a repair cadence that completes comfortably inside it and a policy that a replica absent for longer is rebuilt from scratch rather than rejoined. A shorter window wins only when repair is demonstrably fast and replicas are never allowed to be away long. The useful dashboard plots *repair age against retention*: the day the oldest unrepaired range exceeds the retention window is a latent data-integrity incident, whether or not any alert has fired.

Decision 21 · Snapshots, full log replay or incremental backups?

A bad deploy writes empty settings for 3 minutes. Replication faithfully copies the damage to all three replicas, and the only way back is a backup: replication is availability, not backup.

Replaying the full log from the beginning is conceptually simple and takes longer the older the system is. A snapshot is a point-in-time image that bounds replay to the log after it; taking it costs I/O and, if sloppy, consistency across partitions. Incremental backups ship only new immutable files or log segments between snapshots, which fits LSM storage naturally and keeps the cost proportional to change. A restore needs a snapshot plus the log up to a chosen point, so the log archive is part of the backup, not a separate concern.

The reference takes periodic snapshots per partition, archives log segments continuously, and restores to a point in time by snapshot plus replay. Retention for backups is a policy (35 days as the example here), and it means physical erasure after a delete can take up to 35 days. Full replay alone wins for tiny datasets. An untested backup is not a backup: schedule restore drills, track restore duration against the recovery objective, and keep the encryption keys for old snapshots as carefully as the snapshots.

Decision 22 · Background repair urgency, or foreground latency?

After replica C returns from a 6-hour outage it is behind by a long stretch of the log. If it catches up at full speed, it saturates the leader's disk and network, and the p99 for every tenant on those nodes rises.

Aggressive repair shortens the window in which a partition has only a bare majority, which lowers risk of a second failure becoming an outage. Throttled repair protects the foreground traffic but extends exposure. Middle options: rate limit by default, prioritize partitions that are under-replicated, raise the rate when the cluster is quiet, and fall back to snapshot transfer for replicas that are very far behind.

The reference gives repair a bandwidth budget that adapts to foreground latency, with a priority order (under-replicated partitions first, then those closest to the tombstone window), and uses a snapshot for large gaps rather than replaying months of log. Aggressive repair wins when a partition is one failure from an outage, and the response then is deliberate: accept a latency hit to restore redundancy. Run repair as visible, rate-limited jobs with progress metrics, so that the question 'are we repaired?' has a number as its answer.

Two regions are not simply twice one region. The speed of light is not tunable, so every cross-region design decides who waits for whom, and what the system admits it might lose when a region disappears.

Decision 23 · Synchronous or asynchronous inter-region replication?

The EU region is lost to a power and network failure. The US replica was 300 ms behind. Meridian's EU share of average writes is assumed to be 30% of 40,000, that is 12,000 writes per second, so up to 12,000 writes/s × 0.3 s = 3,600 acknowledged writes may exist only in the dead region. EU acknowledged v11 on a key; the US holds v10.

Synchronous replication across the WAN would put a majority across regions in every commit, which removes that loss window and adds the inter-region round trip (tens to hundreds of milliseconds depending on geography; measure yours) to every write, plus an availability dependency on the link. Asynchronous replication keeps commit latency regional and makes the loss window equal to the lag at the instant of the disaster. That window is the real RPO (recovery point objective: how much acknowledged data you can lose), which is lag-dependent exposure and never "zero". Managed products also offer multi-region modes with different guarantees; DynamoDB global tables, for example, offer more than one multi-Region mode, so check the vendor's current documentation for what each mode guarantees rather than assuming either extreme.

The reference uses a home-region leader with asynchronous remote replicas: writes and linearizable reads happen in EU, US reads are labeled eventual, and region failover is a deliberate decision with the loss window shown to whoever approves it. Synchronous wins when the business cannot accept any loss and can pay the latency, typically for small, high-value data. Replication lag becomes a headline metric with an alert threshold derived from the RPO you promised, and the failover runbook states the unreplicated window up front. EU-resident records must not be silently promoted in the US, because residency is a constraint on topology, not a preference.

Decision 24 · Active-passive or multi-active regions?

A US-based Atlas administrator edits atlas/user42/settings while the same record is edited from Frankfurt. In an active-passive layout the US write travels to the EU leader and pays the round trip. In a multi-active layout it commits locally in the US and both regions accept updates concurrently.

Active-passive keeps a single ordered history per record and makes conflicts impossible by construction; the cost is that remote writers pay latency and a region failover is a procedure with a loss window. Multi-active gives low local write latency and survives a region loss without a promotion step, but concurrent writes to the same key in two regions must be resolved: last-write-wins by timestamp, per-field merge, or application resolution. Bigtable's replication is a concrete example of the family: replication across clusters is eventually consistent, same-cell conflicts across clusters resolve by server-time last-write-wins, and an app profile can route traffic to a single cluster to get read-your-writes behavior. That is a product with its own design, not a description of the reference here.

The reference stays active-passive for Meridian's settings, because the data is conflict-sensitive and write rates by region are modest; multi-active is presented only as a labeled alternative, never blended with the reference's guarantees. Multi-active wins for collaboratively edited or naturally partitioned-by-region data where conflicts are rare and merges are defined. Multi-active needs conflict metrics, a documented resolution rule that product owners have actually read, and tests that two regions writing the same key give an outcome nobody is surprised by.

The last four decisions concern behavior under stress: a key that gets too popular, a tenant that gets too loud, a cluster that wants to move data, and a quorum that has gone missing. In each, the temptation is a clever shortcut that works on the quiet day.

Decision 25 · Split the hot partition, or salt the keys?

Atlas's checkout fleet reads atlas/feature=checkout_policy at 60,000 reads/s. In the simplified 100-partition illustration, the average partition sees 2,000 reads/s, so this one key is 30× an average partition; it is 6% of the 1,000,000/s peak. At an assumed 25,000 point reads/s per replica, one replica is overrun, and even three replicas at 75,000/s capacity run at 80%.

Splitting a partition helps when the heat is spread across many keys in it, since the halves can live on different nodes. It does nothing when one key is the heat, because one key still lives in exactly one partition. Salting (writing key#0 … key#7 and reading a random one) multiplies read capacity for a read-mostly value and breaks single-key atomicity for any value that changes, since the copies must be updated together. Real remedies for a hot read-only key are follower reads (stale, and labeled), a client or near cache with a TTL, request coalescing so that a burst of identical reads becomes one, or replicating that key's data more widely. Writes to one key stay serialized through one leader whatever you do.

The reference serves it from at least 3 read-capable replicas (callers that accept follower-stale may use the followers), a TTL cache that callers opt into, and coalescing, and it does not salt keys that are written. Salting wins for read-only data, such as published configuration versions that are immutable once written. Per-key top-N telemetry is what tells you whether to split or to cache, and any hot-key mitigation has to state its staleness bound where the product's API does.

Decision 26 · Dedicated tenant partitions or a shared multi-tenant fleet?

Atlas launches a promotion and its request rate triples. Birch and Cedar, on the same nodes, see timeouts. Nobody did anything wrong except share a CPU.

A shared fleet is efficient: small tenants average out and headroom is pooled. Its price is the noisy neighbor, which must be contained with per-tenant quotas, admission control that returns 429 with a retry hint, and fair scheduling in the node. Dedicated partitions or nodes give strong isolation and simple capacity accounting, and cost utilization, because spare capacity belongs to one tenant, and operations, because there are more things to place. See rate limiting and bulkheads.

The reference shares the fleet with enforced per-tenant limits and keeps the option to dedicate partitions to a tenant that is persistently large, like Atlas; it is a placement policy over the same engine rather than a separate product. Dedicated wins for tenants with contractual isolation, regulatory placement or predictably heavy loads. Every throttle needs an owner, tenants need dashboards of their own usage and 429s, and the placement decision should be reversible through the same migration mechanism as any other rebalance.

Decision 27 · Automatic rebalancing or controlled maintenance windows?

A node is added during the afternoon peak, and the balancer begins moving 32 partition replicas. The cluster's p99 rises, two moves stall halfway, and a third fails its cutover because the map epoch moved under it.

Automatic rebalancing keeps the cluster even without anyone watching and reacts to new nodes and failures at machine speed, which is also the risk: a bug or a flapping node can start a storm of movement. A scheduled window gives humans control and predictable load, and leaves the cluster skewed in between and slow to heal after a failure. Both need the same safe cutover protocol: copy, catch up, bump the epoch, reject stale routers, and only then delete the source.

The reference automates with guardrails: a limit on concurrent moves, a rate budget that backs off when foreground latency rises, no movement while under-replicated partitions exist, and a manual pause switch. Pure scheduling wins for small fleets or very sensitive periods. Stuck migrations are first-class alerts, every move is idempotent and resumable, and the balancer's own decisions are logged, because "why did that partition move" will be asked at 3 a.m.

Decision 28 · Availability-first fallback or rejecting writes when there is no safe quorum?

Two of the three replicas of a partition are unreachable. The surviving one is perfectly healthy and willing to accept Put(atlas/user42/settings). If it does, the write exists on one machine, and the two others may elect a leader on their own side with a different history.

An availability-first fallback accepts the write on whatever is reachable and reconciles later, which keeps clients happy and creates the possibility of divergent histories and lost updates. Rejecting returns 503 UNAVAILABLE, which keeps the history single and makes the outage visible. A middle position exists for *reads*: serve a follower-stale read, clearly labeled, when the caller has asked for it. For writes, there is no safe middle: the system either has a majority or it does not.

The reference rejects: never a false success, and a timeout is an unknown outcome that clients retry with the same idempotency key. Availability-first wins for data whose loss is cheap and whose conflicts are mergeable, which is exactly the leaderless family from Decision 5. Because the product's availability is bounded by quorum availability, the investment goes into failure-domain spread, fast replacement of dead replicas, and client behavior (bounded retries with backoff and jitter, circuit breakers) so that a lost quorum does not turn into a retry storm. See retry with backoff.

The 28 decisions are not independent. Pick leaderless replication in Decision 5 and Decision 15's conditional write becomes a different problem; pick multi-active regions and Decision 20's tombstone retention suddenly spans a WAN. The reference is a coherent bundle, and so are its alternatives.

Read the matrix as a list of promises, not of features. The leaderless family promises to accept the write and to converge, and does not promise which of two concurrent writes survives. The leader-based family promises one history and says no when it cannot make one. The tablet family, in its replicated products, promises ordering within a cluster and leaves cross-cluster behavior to configuration: Bigtable's documentation, for example, describes eventual consistency across clusters unless you route traffic to one cluster. None of these is wrong; each is wrong for the other's workload.

• Write down, for every decision, the failure the choice accepts and the metric that shows it is happening.
• Keep the strong default and make every weaker read mode an explicit, labeled opt-in.
• Measure compaction, write amplification, lag and compression on your data; treat the numbers on this page as assumptions.
• Test failover, restore and repair against the stated recovery objectives before you need them.

• Do not equate RF=3 with consensus, or R+W>N with linearizability.
• Do not acknowledge a write before the flush and call it durable.
• Do not salt or fan out keys that are written, or split a partition to cool a single key.
• Do not promote an EU-resident region silently, or promise instant physical erasure.