Distributed Key Value Store System Design

The distributed key-value store is the storage substrate that emerged from the 2007 Dynamo paper (DeCandia et al., SOSP) and proliferated through Apache Cassandra (Lakshman & Malik 2010), Riak, and others. It is a database that maps an opaque key to an opaque value (sometimes a structured value with named columns), partitions keys across many nodes via Consistent Hashing, replicates each key to a configurable number of nodes (replication factor N, conventionally 3), and lets the application tune consistency by choosing how many of the N replicas a read or write must acknowledge (the famous R + W > N quorum trick). It explicitly chooses AP (Availability + Partition tolerance) in the CAP theorem sense — it is willing to return possibly-stale data during network partitions, in exchange for surviving them — and uses background mechanisms (anti-entropy with Bloom-/Merkle-tree-driven repair, hinted handoff, read repair) to converge eventually. Note the naming trap: the 2007 Dynamo paper describes a leaderless, vector-clock, sloppy-quorum ring, but the DynamoDB cloud product (2012 onward, Elhemali et al. ATC 2022) is a different system — leader-based Multi-Paxos replication groups over a B-tree store, which added lock-free serializable multi-item transactions in 2018 (Idziorek et al. ATC 2023). This note describes the Dynamo design lineage — Cassandra and Riak are its truest embodiments; see §7.3 and Leaderless Replication Architecture for where modern DynamoDB departs from it. The original Dynamo paper’s choice to abandon strict consistency in favor of always-writable operation remains one of the most-cited architectural decisions of the 2000s.

1. Functional and Non-Functional Requirements

Functional.

• Key-value get/put/delete. A single keyed operation is the API atom. Keys are typically up to ~1 KB; values typically up to a few MB (DynamoDB’s hard limit is 400 KB; Cassandra has a soft limit of a few MB but supports larger values poorly).
• Structured values (optional). Cassandra and DynamoDB support named columns/attributes within the value, enabling secondary access (e.g., “give me the email field of user 42”). This is the “wide-column” extension to plain KV.
• Range scans within a partition. Many systems support WHERE partition_key = X AND clustering_key BETWEEN A AND B — a scan over a sorted range within one partition. Cross-partition scans are typically discouraged.
• TTL (Time To Live). Each row can have an expiration; expired rows are removed asynchronously by compaction.
• Secondary indexes. Cassandra and DynamoDB both support them, but with strong caveats: secondary indexes against non-partition keys can be expensive (touching every node) or eventually consistent.
• Multi-region. Cassandra natively supports multi-DC replication. DynamoDB’s Global Tables provide multi-region.
• Tunable consistency. Per-request choice of “how many replicas must I hear from?” — the user picks ONE, QUORUM, ALL, or numeric values.
• Conditional writes. Cassandra’s lightweight transactions (LWT, Paxos-backed); DynamoDB’s ConditionExpression. Used for compare-and-swap idioms.

Non-functional.

• Low single-key latency. p99 reads under 10 ms; many production deployments target p99 ~ 5 ms.
• Throughput. Millions of operations per second for large clusters. DynamoDB’s published 2018 numbers were “tens of millions of requests per second” sustained.
• No single point of failure. Peer-to-peer ring; every node is symmetric. Loss of any one node (and often any one rack or AZ) is invisible to the application.
• Horizontal scalability. Doubling the cluster doubles the throughput — adding nodes triggers an online repartitioning.
• Eventually consistent (default). Background convergence to a global state; strong consistency available as an opt-in.
• Partition tolerance. Network partitions between data centers do not cause data loss; on heal, anti-entropy reconciles divergence.

The Dynamo paper’s headline was: “in a 24/7 retail business, an unavailable shopping cart is worse than a stale shopping cart.” That single product-design statement drove every consistency-related choice in the system.

2. Capacity Estimation

Sketch a cluster sized roughly like Cassandra’s at-scale deployments:

• Cluster size: 100 nodes (typical “production-medium”).
• Replication factor: N = 3.
• Per-node storage: 4 TB. Total raw: 400 TB. Effective unique storage: 400 TB / 3 ≈ 133 TB.
• Per-node memory: 128 GB. Memtable + cache + Bloom filters use ~1 GB per 10 GB of data; for 4 TB this is ~40 GB of hot RAM per node.
• Per-node IOPS: NVMe SSD, ~500 K IOPS read, ~200 K IOPS write peak.
• Cluster throughput: 100 nodes × ~50 K ops/sec sustained per node ≈ 5M ops/sec cluster total. The factor between peak hardware IOPS and sustained ops/sec accounts for compaction overhead, replication amplification, and tail-latency budget.
• Per-key fanout: each PUT writes to 3 nodes; each GET probes up to 3 nodes (depending on consistency level). Internal traffic is roughly 3× client traffic.
• Network: 25 Gbps NICs per node; ample for 50 K ops × ~1 KB avg ≈ 400 Mbps per node, well within budget.

Latency.

• Quorum read (R = 2 of N = 3): wait for the second response, so latency is the second-fastest of three replicas. With well-balanced replicas, this is dominated by the median replica, plus one network round-trip.
• Single-replica read (R = 1): the fastest response. Stale risk; lowest latency.
• All-replica write (W = 3): wait for the slowest response. Highest tail.

This is the central tunable: lower consistency level → lower latency and higher availability; higher consistency level → stronger guarantees and worse tail.

3. Application Programming Interface

3.1 Cassandra Query Language (CQL) — Structured Layer over Wide-Column KV

CREATE KEYSPACE app
  WITH replication = {'class': 'NetworkTopologyStrategy', 'us-east-1': 3, 'us-west-2': 3};
 
CREATE TABLE app.users (
  user_id   uuid,
  ts        timestamp,
  email     text,
  username  text,
  PRIMARY KEY (user_id, ts)
);
 
INSERT INTO app.users (user_id, ts, email, username)
  VALUES (?, ?, ?, ?)
  USING CONSISTENCY QUORUM;
 
SELECT * FROM app.users
  WHERE user_id = ? AND ts > ?
  USING CONSISTENCY LOCAL_QUORUM;

The PRIMARY KEY (user_id, ts) declaration says: the partition key is user_id (this is what’s hashed onto the ring); the clustering key is ts (sorts rows within the partition for range scans). All rows for a single user_id live on the same set of N replicas; range scans within a user are fast; cross-user queries fan out across the cluster.

3.2 DynamoDB API — Native KV with Items and Attributes

ddb.put_item(
    TableName='users',
    Item={
        'user_id': {'S': '42'},
        'ts': {'N': '1715000000'},
        'email': {'S': 'alice@example.com'}
    },
    ConditionExpression='attribute_not_exists(user_id)'  # CAS
)
 
ddb.get_item(
    TableName='users',
    Key={'user_id': {'S': '42'}, 'ts': {'N': '1715000000'}},
    ConsistentRead=True   # strong; default is eventual
)

DynamoDB’s API has mostly the same primitives but exposes them per-item rather than via a query language (DynamoDB also supports a SQL-like PartiQL interface).

3.3 Riak’s Strict KV API

PUT /buckets/users/keys/42      body=<json>     ?w=quorum
GET /buckets/users/keys/42                       ?r=quorum
DELETE /buckets/users/keys/42                    ?w=all

Pure HTTP REST, with the consistency level as a query parameter. Riak is the closest commercial analog of the original Dynamo paper.

4. Data Model — The Ring, Tokens, and Replicas

4.1 Partitioning by Consistent Hashing

Each node is assigned one or more token ranges on a hash ring (see Consistent Hashing). When an application writes (key, value):

1. Compute hash(key) (e.g., 128-bit MurmurHash3).
2. Walk the ring clockwise from hash(key) to find the first token. The owner of that token is the key’s primary node.
3. The next N-1 nodes clockwise are the secondary replicas. Together, the N nodes are the key’s preference list in Dynamo terminology.

Cassandra introduced virtual nodes (vnodes — multiple tokens per physical node, default 256) to smooth load distribution. Without vnodes, adding a new node only relieves load from one neighbor; with vnodes, the new node’s 256 tokens fragment the ring and pull load from many existing nodes proportionally.

4.2 Replication Strategies

• SimpleStrategy. N successor nodes on the ring, ignoring topology. Useful for single-DC test clusters.
• NetworkTopologyStrategy (Cassandra’s production strategy). Aware of racks and datacenters; places replicas to ensure cross-rack redundancy and configurable per-DC replication factors.

For a key with RF = 3 in us-east-1 and RF = 3 in us-west-2, a write reaches 6 replicas total. The LOCAL_QUORUM consistency level acknowledges as soon as quorum within the local DC has acknowledged, with cross-DC replication continuing asynchronously — a common pattern for low-latency writes with multi-region durability.

4.3 Versioning — Vector Clocks vs Last-Write-Wins

Dynamo (and original Riak) uses Vector Clocks. Every write to a key carries a vector clock: a map {node_id → counter}. When concurrent writes happen, their vector clocks are concurrent (neither is a prefix of the other), and the system returns both versions to the client on subsequent reads, expecting the application to merge.

Vector clocks are conceptually clean but operationally awkward — applications must implement a merge function for every type, and clocks can grow unboundedly under churn (mitigation: pruning by oldest entries).

Cassandra uses last-write-wins by client-supplied timestamp. Every column has a per-column timestamp; on read, the column with the highest timestamp wins. Simpler but pushes the conflict-resolution problem to the client (which must produce monotonic timestamps; clock skew between client machines can cause data loss).

DynamoDB uses last-write-wins by server-assigned sequence number for non-conditional writes; conditional writes use compare-and-swap to detect concurrent updates.

The choice has been the subject of heated debate. Riak has experimented with both CRDT-based merging and last-write-wins. The Dynamo paper itself argues for vector clocks but acknowledges they’re a niche choice for shopping-cart-like workloads where the merge is “concatenate items.”

5. High-Level Architecture

flowchart TB
    subgraph Clients
        A1[App Server 1]
        A2[App Server 2]
    end

    subgraph Ring["Ring of N nodes (peer-to-peer; no master)"]
        N1[(Node 1<br/>tokens [t1,t2,...])]
        N2[(Node 2)]
        N3[(Node 3)]
        N4[(Node 4)]
        N5[(Node 5)]
    end

    subgraph Storage["Per-node Storage Engine (LSM tree)"]
        ME[MemTable]
        WAL[(Write-Ahead Log)]
        SS[(SSTables on disk)]
    end

    A1 -->|coordinator-style RPC| N3
    A2 -->|coordinator-style RPC| N1
    N3 -->|replicate to 3 successors| N4
    N3 --> N5
    N3 --> N1
    N1 -->|gossip membership| N2
    N2 -->|gossip| N3
    N3 -->|gossip| N4
    N1 --> ME
    ME --> WAL
    ME -->|flush| SS

    BG[Background:<br/>compaction, anti-entropy with Merkle trees,<br/>hinted handoff replay] -.-> N1
    BG -.-> N2

What this diagram shows. A Cassandra-style cluster is a peer-to-peer ring — every node is functionally identical and can serve as a coordinator for any request. When App Server 1 sends a PUT key=K, it picks any node (e.g., N3) as the coordinator, often the closest topologically. The coordinator hashes K, walks the ring to find the preference list (say N4, N5, N1), and forwards the write to all three in parallel. Each node persists locally to its LSM-backed storage engine: write to the MemTable, append to the Write-Ahead Log for durability, and acknowledge. The coordinator waits for W of the N replicas to acknowledge, then replies to the client. Cluster membership and ring topology are propagated by gossip — every second or so, each node picks a random peer and exchanges state digests. There is no central master; if any node disappears, the cluster keeps operating with the remaining nodes. Background processes — compaction (LSM tree merging), anti-entropy (periodic Merkle-tree-based reconciliation between replicas), and hinted handoff replay (re-delivery of writes that landed on a substitute when the primary was down) — keep the system converging even under sustained churn.

6. Request Flow

6.1 Quorum Write

sequenceDiagram
    actor Client
    participant Coord as Coordinator (any node)
    participant N1 as Replica 1
    participant N2 as Replica 2
    participant N3 as Replica 3

    Client->>Coord: put(key, value, W=2)
    Coord->>Coord: hash(key) -> preference list [N1, N2, N3]
    par
      Coord->>N1: write
      Coord->>N2: write
      Coord->>N3: write
    end
    N1-->>Coord: ack
    N2-->>Coord: ack
    Note over Coord: 2 of 3 acks received; W met
    Coord-->>Client: success
    N3-->>Coord: ack (lazy; coordinator already responded)

If a replica fails to ack (network partition, slow GC, or restart), the coordinator may write a hinted handoff — a stand-in record on a different node saying “when N3 comes back, replay this write to it.” Hints are kept for hours; if the down node returns, hints replay; if not, the missed write is reconciled later by anti-entropy.

6.2 Quorum Read with Read-Repair

sequenceDiagram
    actor Client
    participant Coord
    participant N1
    participant N2
    participant N3

    Client->>Coord: get(key, R=2)
    par
      Coord->>N1: read
      Coord->>N2: read
      Coord->>N3: read (digest only)
    end
    N1-->>Coord: value (timestamp T1, hash H1)
    N2-->>Coord: value (timestamp T2, hash H2)
    Note over Coord: 2 of 3 received; R met
    Note over Coord: H1 != H2 -> divergence detected
    alt T1 > T2
      Coord-->>Client: N1's value
      Coord->>N2: read-repair: install N1's value
    else T2 > T1
      Coord-->>Client: N2's value
      Coord->>N1: read-repair: install N2's value
    end
    N3-->>Coord: digest (for completeness)

Read-repair is the cheap repair channel: every read that observes divergent replicas pushes the freshest value back to the lagging ones. Combined with anti-entropy (the expensive deep-scan repair), this keeps replicas converged on hot keys without operator intervention.

6.3 Anti-Entropy via Merkle Trees

Periodically (Cassandra: weekly by default; tunable), each pair of replicas runs:

1. Each replica computes a Merkle tree over its data — a binary tree where leaves are hashes of small key ranges and each internal node is the hash of its children.
2. The two replicas exchange root hashes. Match? Done — replicas agree.
3. Mismatch? Recurse down to find subtrees that differ.
4. Stream over only the differing keys.

The cost of the comparison is logarithmic in the data size (the tree has log2(N_keys) levels), but the cost of streaming differs is linear in the number of differences. For a healthy cluster, differences are tiny, so anti-entropy is cheap. After a long partition or a node restoration, differences are large and anti-entropy becomes expensive — operators throttle it.

Merkle trees were invented by Ralph Merkle (1987) for cryptographic signatures; their use here is purely as an efficient set-difference primitive over hashed content.

6.4 Hinted Handoff

When a coordinator detects a replica is unreachable during a write, it stores the write locally as a hint (annotated with the intended target). The hint is written to a special directory with a TTL (Cassandra default: 3 hours). When the missing replica’s gossip traffic returns, the coordinator drains its hint queue to that replica.

If hints exceed their TTL (the replica was down for too long), they’re discarded; the missed writes will eventually be reconciled by anti-entropy. This is the bounded-staleness guarantee: in the worst case, missed writes are at most one anti-entropy cycle stale.

7. Deep Dive — Selected Topics

7.1 The R + W > N Quorum Rule

The Dynamo paper’s central theorem: if R + W > N, then every read overlaps every write in at least one node, so the read can observe the write.

Concretely: suppose N = 3, W = 2, R = 2. A write reaches 2 of 3 replicas; a read queries 2 of 3 replicas. The write set and the read set must share at least (W + R) - N = 1 node, by the pigeonhole principle. That shared node has the latest write, and the read sees it.

Common configurations:

• R = 1, W = 1: lowest latency, eventual consistency. Suitable for “always-writable” caches.
• R = 2, W = 2 (quorum): consistent if no failures during the write/read window. The default for most production deployments.
• R = 1, W = 3: cheap reads, strong writes — useful when reads dominate.
• R = 3, W = 1: strong reads, cheap writes — useful when writes dominate.
• R = N, W = 1 or R = 1, W = N: still satisfies R + W > N but makes one side painfully slow.

The rule is a necessary condition for “read sees write” — but not sufficient under network partitions. If a partition splits the ring, both sides can satisfy the local R + W rule and yet diverge. The system’s job after the partition heals is to reconcile.

7.2 Sloppy Quorum

Strict quorum says: a write must be acknowledged by W of the preference-list nodes. If the preference list is {N3, N4, N5} and N5 is down, a strict quorum write with W=2 must wait for N3 and N4 — but a partition could leave only N3 reachable.

Sloppy quorum relaxes this: if a preference-list node is down, write to any live node (e.g., N6) as a substitute. The substitute records the write with a “hint” annotation pointing at the intended target. This lets the system make progress under partial failure, at the cost of weaker consistency: a read of the same key from the still-strict preference list will not see the substitute’s write until hinted handoff replays.

The Dynamo paper described sloppy quorum as the right trade for “always-writable” workloads (Amazon’s shopping cart). Cassandra by default uses strict quorum and relies on hinted handoff and read repair as backup.

7.3 Tunable Consistency in DynamoDB and Beyond

Original Dynamo: AP with eventual consistency, no opt-in to strong.

DynamoDB (cloud product, 2012): added ConsistentRead=True for read-after-write consistency on a single item. It is worth being precise about what the modern cloud DynamoDB actually is, because it is routinely conflated with the 2007 Dynamo paper. The Elhemali et al. ATC 2022 paper describes the production architecture: a table is split into partitions, each partition’s replicas form a replication group, and that group uses Multi-Paxos for leader election and consensus — “only the leader replica can serve write and strongly consistent read requests” (§ of the paper on replication). The leader generates a write-ahead-log record and ships it to its peers; any replica can serve eventually consistent reads. The group can also include log replicas (“akin to acceptors in Paxos”) that store only recent WAL entries for availability. The on-disk store is a B-tree, not an LSM tree. So modern DynamoDB is not a leaderless Dynamo-style ring with sloppy quorum and vector clocks — it is a leader-based, Paxos-replicated, B-tree-backed system that kept the Dynamo name and the operational philosophy (predictable latency, horizontal scale) but replaced the replication core. (This is exactly the point the Leaderless Replication Architecture note makes.)

Transactions came next. The Idziorek et al. ATC 2023 paper, “Distributed Transactions at Scale in Amazon DynamoDB,” documents TransactWriteItems / TransactGetItems. The protocol is timestamp-ordering (TSO) with one-shot optimistic concurrency control, and it acquires no locks — “Transactions do not acquire locks. While two-phase locking … [the design uses] an optimistic concurrency control scheme that avoids” lock-holding. A dedicated transaction coordinator fleet drives a two-phase protocol (Two-Phase Commit): the coordinator assigns the transaction a timestamp from a clock sourced from the AWS time-sync service (synchronized to within microseconds), then prepares every item’s primary storage node (phase 1) and, if all accept, commits (phase 2); any single rejection cancels. Non-transactional singleton reads/writes bypass the coordinator entirely and go straight to the storage node, preserving single-key latency. Crucially, the isolation guarantee is serializable but not strict serializable — “transactions can appear to happen in any order” — and there is no MVCC; items are updated in place. So DynamoDB’s transactions are weaker than Spanner-class strict-serializable transactions and are implemented quite differently (no locks, no MVCC, no commit-wait), even though both use a two-phase protocol.

Cassandra added Lightweight Transactions (LWT) — single-key compare-and-swap implemented via Paxos — in version 2.0. The cost is dramatic: LWT writes are an order of magnitude slower than non-LWT. They are reserved for the few operations that genuinely need linearizability (idempotent token reservation, leader election rows).

7.4 The CAP Theorem in Practice

Brewer’s CAP theorem (2000 PODC keynote, “Towards Robust Distributed Systems”) says: in the presence of a network Partition, you must choose between Consistency and Availability. Gilbert & Lynch (2002) gave a formal proof for the asynchronous network model. See the dedicated CAP Theorem note for the full statement and its common misreadings.

The original Dynamo paper is the canonical AP-system example: availability is non-negotiable; we accept reading stale data during partitions and reconcile later. Spanner is the canonical CP-system: under partition, the side without quorum becomes unavailable to preserve linearizability.

But CAP is a two-out-of-three at the moment of partition, not a long-term identity. Most real systems are AP under partition + strong eventually; the PACELC extension (Daniel Abadi, 2010) — “if Partition, choose A vs C; Else, choose Latency vs Consistency” — is closer to how systems are tuned in practice.

7.5 Anti-Entropy Engineering — Not as Cheap as It Sounds

A common interview misstatement: “anti-entropy is cheap because Merkle trees are logarithmic.” False — the comparison is logarithmic, but streaming the differences is linear. After a long outage or a major topology change (adding nodes, decommissioning), anti-entropy can saturate the cluster’s IO. Cassandra operators schedule incremental repair (only the recently-changed data) and reserve full repair for off-peak windows.

7.6 Tombstones — The Quiet Killer

A delete in an LSM-backed KV store does not erase the data; it writes a tombstone (see LSM Tree). The tombstone shadows older versions on read. After a grace period (Cassandra: gc_grace_seconds, default 10 days) and a compaction cycle, the tombstone and the old data are reclaimed.

Tombstones interact badly with sloppy quorum and hinted handoff: if a replica was down when the delete happened and stayed down past the grace period, the resurrected node’s un-tombstoned old version can come back to life (“zombie” data). The 10-day grace period is a safety margin against this; aggressive deletion patterns combined with slow recoveries can resurrect data, which is why Cassandra docs warn loudly against shortening the grace period.

8. Scaling Considerations

• Adding nodes (online). New node joins the gossip ring with its tokens; the cluster rebalances by streaming the relevant token ranges’ data from existing replicas to the new node. Reads and writes continue throughout.
• Decommissioning. Node announces departure; tokens are reassigned to remaining nodes; data is streamed off before the node leaves.
• Per-key hot spots. A single key in the ring sees all its traffic on N nodes (the preference list) regardless of cluster size. Mitigations: client-side caching, “cold” rows in a single-row partition, splitting hot keys into sub-keys (user_42_part_0, user_42_part_1, etc.) to spread across more replicas.
• Per-partition hot spots. A wide partition (many rows under one partition key) all hits the same N replicas. Cassandra docs warn against partitions exceeding 100 MB; large partitions cause read amplification and GC pressure.
• Multi-DC. NetworkTopologyStrategy lets you replicate to multiple DCs at controlled factors. LOCAL_QUORUM makes writes ack as soon as the local DC’s quorum has it; cross-DC replication continues async.
• Read load scaling. Linearly with cluster size for non-hot keys.
• Write load scaling. Linearly with cluster size up to the point where compaction saturates (LSM compaction is the typical write-throughput ceiling).

9. Real-World Examples

• Amazon Dynamo (SOSP 2007) — internal Amazon. Underpinned the Amazon shopping cart, S3 metadata, and other “always-writable” services. The paper is THE foundational citation for everything in this note.
• Apache Cassandra (2010 paper) — open-sourced from Facebook. Production at Apple (per public Apple TechTalks: tens of thousands of Cassandra nodes), Netflix (chronicled in their tech blog), Instagram. Wide-column model, NetworkTopologyStrategy, gossip-based membership.
• Riak — closer to literal Dynamo, written in Erlang. Used to be a popular alt-database; commercial vendor (Basho) shut down 2017; project continued as Riak KV / Riak Cloud Storage.
• Amazon DynamoDB — managed cloud product since 2012, and architecturally distinct from the 2007 Dynamo paper despite the shared name. Per Elhemali et al. ATC 2022, each partition’s replica group uses Multi-Paxos with a single leader (only the leader serves writes and strong reads), backed by a B-tree storage engine — not a leaderless ring, not vector clocks, not sloppy quorum. Multi-item ACID transactions (Idziorek et al. ATC 2023) layer a lock-free, timestamp-ordered, two-phase protocol on top. It kept Dynamo’s philosophy (predictable latency at any scale, multi-AZ durability, Global Tables for multi-region) while replacing the replication core.
• ScyllaDB — Cassandra-compatible C++ rewrite using shard-per-core design (seastar). Same data model and protocol; better tail latency.
• Voldemort (LinkedIn) — open-source Dynamo-style KV store; LinkedIn’s pre-Espresso datastore.
• etcd / Consul — Raft-backed KV stores; not Dynamo-style, but conceptually related (KV API). They choose CP, not AP.

10. Tradeoffs

Decision	Choice	Alternative	Why
CAP corner	AP with eventual consistency	CP (Spanner)	Always-writable is the product requirement
Partitioning	Consistent hashing	Hash mod N	Survive node add/remove without mass reshuffle
Replication topology	Successor list (ring)	Master-slave	No SPOF; symmetric peer-to-peer
Conflict resolution	Vector clocks (Dynamo) / LWW (Cassandra)	Strong consistency only	Trade simplicity for availability
Membership	Gossip	Centralized membership service	No SPOF
Storage engine	LSM tree	B+ tree	Write-optimized for typical workload
Default consistency	Quorum (R+W>N)	Strong only	Tunable per request
Repair	Anti-entropy + read repair + hinted handoff	Synchronous chain	Asynchronous; preserves availability
Schema	Wide-column with primary key	Document-store	Range scans within partition; predictable I/O

11. Pitfalls

1. The quorum rule is conditional. R + W > N gives consistency if no partition splits the system during the read/write window. Under partition, both sides may locally satisfy R + W > N and still diverge; anti-entropy reconciles, but reads in the meantime can be stale. Interview answer: “quorum gives single-item linearizability in the absence of partitions and concurrent writers.”

2. Last-write-wins by client clock loses data on clock skew. If client A’s clock is ahead of client B’s, A’s later wall-clock-time write wins even if it temporally happened first. Mitigation: use a logical clock or server-assigned timestamps.

3. Tombstone resurrection. Deletes that are not seen by all replicas before gc_grace_seconds can resurrect. See §7.6.

4. Wide partitions melt down. A partition with many millions of rows or many GB of data hits the same N replicas; reads of the whole partition are slow; compaction takes hours; GC pauses get long. Cassandra docs cap partitions at 100 MB / a few hundred K rows.

5. Secondary indexes are weak. A non-partition-key index distributes the index across all nodes; queries against it fan out cluster-wide. For most workloads, dual-write (denormalize an inverted table) is faster.

6. Read amplification on LSM with many SSTables. Cassandra reads check Bloom filters per SSTable, but if compaction can’t keep up under heavy write load, reads visit many SSTables. The metric to watch: SSTables per read.

7. Hot keys are unsolvable in pure consistent hashing. A single key’s traffic is bounded by the N replicas. Mitigations are application-level (bucketing, caching).

8. Repair operations are expensive. A full repair on a multi-TB cluster can take days. Schedule carefully; throttle.

9. Multi-DC consistency is operational hazard. LOCAL_QUORUM is fast but eventually consistent across DCs. EACH_QUORUM is consistent but slow. Choosing wrong is a common mistake.

10. Sloppy quorum + hinted handoff is not a substitute for replication. If hints expire before the down node returns, writes are lost from that replica. The data is still on N-1 replicas, but the cluster is briefly under-replicated.

11. Vector-clock pruning corner cases. Pruning the oldest entries of a vector clock can mask concurrent writes as ordered. Riak’s documentation has a long list of “do not do this” patterns.

12. DynamoDB’s “hot partition” surcharge. Pre-2018, exceeding a partition’s provisioned capacity throttled. Post-2018, “adaptive capacity” auto-balances, but burst behavior still varies.

12. Common Interview Variants

• “Design Cassandra” — full system. Hit consistent hashing, gossip, replication, R+W>N, hinted handoff, anti-entropy, LSM storage.
• “Design DynamoDB” — same plus the cloud-product layer (provisioned capacity, autoscaling, global tables).
• “Design a session store / cache” — KV with TTL; lower replication factor (RF=2 or even 1) often acceptable; pure AP is fine.
• “Why does Cassandra use last-write-wins?” — operational simplicity vs vector clocks; pushes complexity to clients; works if clients have synchronized clocks.
• “What’s the difference between strict quorum and sloppy quorum?” — see §7.2.
• “How do replicas converge after a partition?” — read repair (cheap), anti-entropy (expensive), hinted handoff (bounded).
• “How would you handle a hot key?” — sub-key splitting; client-side caching; replication factor increase.
• “Why does Cassandra have a 100-MB partition limit?” — wide partitions concentrate read load on N replicas; LSM read amplification compounds; GC pressure.
• “What is the relationship between Bigtable’s wide-column model and Cassandra’s?” — Cassandra inherited wide-column from Bigtable but pairs it with Dynamo-style replication.
• “Why is Dynamo’s choice ‘AP’ rather than ‘CP’?” — Amazon’s shopping-cart product requirement: always-writable is more important than always-consistent.

13. Open Questions / Uncertain

The DynamoDB storage-layer and transaction-protocol questions previously here are now resolved against the ATC 2022 and ATC 2023 papers (Multi-Paxos replication groups, B-tree store, lock-free timestamp-ordering two-phase transactions, serializable-not-strict) and folded into §7.3 and §9. What remains open:

• How DynamoDB’s transactions perform under real adversarial customer workloads — the ATC 2023 paper gives controlled benchmarks, but contended-key abort rates in production are not publicly characterized.
• Production benchmarks comparing Cassandra vs ScyllaDB at scale; ScyllaDB claims dramatic improvements but the workloads matter.

Uncertain

Verify: the Accord protocol’s status as Cassandra’s general-purpose transaction mechanism. Reason: as of early 2025, secondary sources (Instaclustr; The New Stack) report Accord (CEP-15) did not land in Cassandra 5.0; it slipped past the originally-planned 5.1 and is associated with Cassandra 6 (alpha as of 2025), gated on the Cluster Metadata Service (CEP-21). Exact GA version and date are not yet pinned to a primary release announcement. To resolve: the official Apache Cassandra 6.0 release notes once published. (Lightweight Transactions via Paxos remain the shipping single-key CAS mechanism in the meantime.)

Uncertain

Verify: real-world deployment scale numbers (e.g., “Apple has tens of thousands of Cassandra nodes”). Reason: these come from conference talks (Apple/Netflix TechTalks), not formal publications, and are point-in-time. Treat as historical, approximate claims. To resolve: a dated primary engineering disclosure. #uncertain

14. See Also

• Leaderless Replication Architecture — the replication topology this design rests on; also explains why modern DynamoDB is not leaderless
• Consistent Hashing — the partitioning primitive
• LSM Tree — the per-node storage engine
• Bloom Filter — used by SSTables for negative-cache; also conceptually similar to Merkle trees for repair
• Vector Clocks — Dynamo’s conflict-detection mechanism
• Gossip Protocol — cluster membership
• CAP Theorem — why this design picks the AP corner
• PACELC Theorem — the Else-Latency-vs-Consistency refinement of CAP
• Distributed SQL Database System Design — the CP cousin (Spanner, Cockroach) — strong consistency + transactions
• Distributed Log System Design — Kafka; conceptually similar partitioning / replication ideas
• Two-Phase Commit — how DynamoDB’s multi-item transactions work
• Raft / Paxos High-Level — what Cassandra’s LWT and DynamoDB’s transactions are built on
• Amazon S3 Object Storage System Design — the metadata layer behind S3 is also a sharded KV store of this shape
• Major System Designs MOC
• SWE Interview Preparation MOC