Distributed key-value store: tunable consistency without false guarantees

This is a leaderless, Dynamo-inspired design with a Cassandra-like coordinator-local hinted-handoff policy. Those are related families, not identical products: original Dynamo used sloppy quorum and vector clocks, while Cassandra's current conflict and repair behavior differs. The animation states the policy it actually models instead of combining incompatible details.

Data placement and durability

Keys map to token ranges. For the illustrated key, the replication factor is RF=3; coordinators send each accepted write to all three natural replicas and return after the selected consistency level has enough durable acknowledgements. W=2 changes acknowledgement latency and failure tolerance, not the total replica work eventually required.

Every replica box includes its own durable local engine. Acknowledgement means the configured local durability boundary has completed; an in-memory receipt is not silently treated as durable. Membership gossip distributes liveness and token-map observations, but it is not consensus and does not serialize writes.

What quorum arithmetic proves

If reads and writes use the same replica set and W + R > RF, their acknowledgement sets must intersect at at least one replica. With RF=3, W=2, and R=2, the intersection is at least one.

That arithmetic alone does not prove linearizability, eliminate concurrent siblings, repair stale replicas, or make a last-write-wins clock trustworthy. A leaderless system can accept concurrent writes through different coordinators. The application must choose and document one of these policies:

• return causally concurrent siblings for deterministic application merge;
• use a domain-specific convergent data type;
• use last-write-wins and accept its clock/skew/data-loss trade-off;
• route operations requiring a single global order through a consensus-backed subsystem.

Vector-clock or dotted-version metadata is not a fixed 40-byte field. It can grow with participants and concurrency, so pruning and sibling limits are explicit loss/complexity trade-offs.

Failure semantics

• An unavailable natural replica causes this design's coordinator to save a bounded, expiring local hint. Hints are best-effort delivery acceleration, not the correctness mechanism. Scheduled anti-entropy repair is still required.
• A successful quorum can be followed by a lost response. The client then sees an ambiguous timeout: retrying a non-idempotent effect under a new identity can apply it twice. Mutating APIs carry a stable request id and persist the outcome in a dedupe window sized to the retry horizon. The operation id is stored with the replicated mutation; the dedupe record is a durable pending/committed state machine, not an isolated cache flag. If a coordinator dies between quorum and outcome recording, retry reconciles the operation id from replicas before deciding whether to apply it.
• Deletes are tombstones. A replica that missed the tombstone can resurrect old data if the marker is garbage-collected before repair reaches it. Repair age must remain below the configured tombstone grace period, including after long outages.
• With insufficient reachable replicas, the selected consistency level fails rather than pretending that a local write met quorum. Lowering consistency can increase availability but changes the stale/conflict envelope.

Merkle trees identify differing ranges efficiently when the trees are comparable. They do not guarantee a universal O(log N) network bill: tree construction, range mismatch, streaming, compaction, and repair concurrency can be expensive.

Capacity and rebalance math

Suppose four storage nodes each hold 30 decimal TB of physical replicated data. The cluster holds 4 * 30 = 120 TB. After a balanced fifth node joins, each holds 120 / 5 = 24 TB.

Each old node therefore sends about 30 - 24 = 6 TB, but the new node receives about 4 * 6 = 24 TB in total. At a new-node ingress limit of 200 MB/s, the transfer-only lower bound is 24,000,000 MB / 200 MB/s = 120,000 s, or 33.3 hours. At 800 MB/s aggregate ingress it is 8.3 hours. Checksums, retries, compaction, foreground load, throttling, and post-stream repair make wall time longer.

Logical throughput is also replication-adjusted. If five nodes each sustain 10,000 replica writes/s and every logical write is sent to three replicas, an ideal uniform ceiling is 5 * 10,000 / 3 = 16,667 logical writes/s, not 50,000. Coordinator work, skew, repair, compaction, and network headroom reduce it. For an R=2 read workload the analogous replica-work ceiling is 5 * 10,000 / 2 = 25,000 logical reads/s before those reductions.

Operational invariants

Track p99 coordination latency, unavailable errors by consistency level, sibling counts, hint age/expiry, repair age, tombstone grace margin, dropped mutations, compaction debt, hot partitions, stream backlog, and per-node disk/network saturation. Admission control protects repair bandwidth; permanently postponing repair is a data-loss decision.

Related material

[CONCEPT]consistency-models [CONCEPT]quorum-reads-writes [CONCEPT]replication [CONCEPT]partitioning-strategies [CONCEPT]gossip-protocol [CONCEPT]merkle-trees [CONCEPT]vector-clocks [CONCEPT]pacelc-theorem [CONCEPT]sharding-strategies

Capacity planning is an explore diagram and is therefore linked with a normal viewer URL.

[CASE]object-storage-s3

Primary sources

• Dynamo: Amazon's Highly Available Key-value Store — original Dynamo partitioning, sloppy quorum, hinted handoff, vector clocks, and anti-entropy design.
• Apache Cassandra: Dynamo architecture — tunable consistency, replication, current Cassandra conflict semantics, hints, and repair distinctions.
• Apache Cassandra repair documentation — why repair is mandatory, resource cost, and tombstone resurrection risk.
• Apache Cassandra hints documentation — coordinator-local best-effort hints and replay behavior.
• Amazon DynamoDB read consistency — current managed DynamoDB consistency options, included to avoid conflating the service with the original Dynamo paper.

Interactive scenarios

▶Walkthrough: quorum-write-read (not found) ▶Walkthrough: concurrent-writes (not found) ▶Walkthrough: partition-and-hints (not found) ▶Walkthrough: ambiguous-timeout (not found) ▶Walkthrough: delete-and-repair (not found) ▶Walkthrough: rebalance-math (not found)