Apache Cassandra — the vnode pioneer

It is 2007. Facebook has 50 million users. Their Inbox Search feature — the thing that lets you search your own message history — is running on MySQL. It works, barely. Every year the data set doubles. Every quarter the query latency doubles. Sharding by user works for reads but the writes for a viral thread (one post, millions of comments) all pile onto one shard. Two Facebook engineers — Avinash Lakshman and Prashant Malik — decide to build a purpose-built store. Lakshman had already co-authored Amazon's Dynamo paper earlier that year. He knew what worked.

The result was Cassandra — open-sourced in 2008, Apache top-level project in 2010, and today the backing store for Facebook Messenger, Netflix's viewing history, Discord's message store, Apple's iCloud, Instagram, and roughly the entire top-100 of Fortune 500 companies who need to store more than 1 TB per shard. Every one of those clusters is a ring built on consistent hashing.

Cassandra took the Dynamo blueprint and made three big improvements: (1) Murmur3 instead of MD5 — because MD5 was overkill and slow. (2) Default 256 vnodes per host instead of ~100 — because more vnodes means finer-grained load balancing. (3) Gossip protocol that scales to 1000+ nodes — because Dynamo's original cluster-membership design didn't. Everything else it kept.

The ring — but denser

Cassandra uses a 64-bit hash space — 2⁶⁴ positions, which is ~1.8 × 10¹⁹. Smaller than Dynamo's 128-bit space, but 64 bits is plenty when your ring holds a few hundred nodes with 256 vnodes each. The trade-off is deliberate: smaller hashes = smaller network overhead when replicas gossip token assignments, smaller state to keep in memory.

The hash function is Murmur3 — the "Murmur3Partitioner" became the default in Cassandra 1.2 (2013), replacing the older RandomPartitioner (which used MD5). Murmur3 is 3-5× faster than MD5, distributes keys almost as uniformly, and (crucially) is non-cryptographic — which is fine because Cassandra is trusting its own operators, not defending against adversarial input.

The vnode revolution — 256 tokens per host

Before Cassandra 1.2, every node owned exactly one token — one point on the ring. Adding a node meant carefully picking its token position so the load stayed balanced. Rebalancing was manual, painful, and slow. In 2012 Cassandra 1.2 introduced vnodes — every node owns 256 random tokens by default, controlled by num_tokens. This made two things trivial:

• Adding a node — pick 256 random positions, take ownership of the ~1/N of the ring nearest to each. No manual rebalancing.
• Removing a node — the 256 arcs that node owned are absorbed by the next-clockwise neighbors, ~256 different neighbors so no single node gets overwhelmed.

Gossip — how the ring stays coherent

Cassandra is decentralized — there is no coordinator, no leader, no metadata service. Every node knows the full ring topology (which node owns which token ranges), and every node keeps that knowledge up-to-date via the gossip protocol.

Every second, each node picks 1-3 random peers and exchanges its current view of the cluster. The exchange is small — mostly node heartbeats and version numbers. Any new information (a node just joined, a node's status changed, a schema version bumped) propagates across the entire cluster in O(log N) rounds — for 100 nodes that's ~7 seconds, for 1000 nodes ~10 seconds.

Two subtle properties matter. First, gossip is eventually consistent — if you added a node 500ms ago, some peers still don't know. This is fine because writes pick their coordinator by looking at their own gossip state and replicas that were mid-gossip-lag see "hinted" writes when they catch up (below). Second, gossip is anti-entropy — it converges toward the true state, so a network partition's stale nodes recover automatically when the partition heals.

Replication — the next N clockwise, with rack awareness

Cassandra's replication is nearly identical to Dynamo's: for each key, walk the ring clockwise from the key's hash and take the first replication_factor (RF) nodes as its replicas. RF=3 is the industry-standard default. But Cassandra adds a critical enhancement: NetworkTopologyStrategy.

In production, servers live in racks (physical or logical failure domains), and racks live in data centers. If your ring's first-3-clockwise happens to put all 3 replicas of a key in the same rack, a single rack-power-failure loses all 3. So Cassandra walks the ring clockwise skipping nodes whose rack is already represented. RF=3 with NetworkTopologyStrategy = "3 different racks, best effort."

The rack-awareness comes from each node's snitch —GossipingPropertyFileSnitch is standard. The snitch tells other nodes which DC and rack each node lives in, via gossip. So the topology-aware placement is automatic: the operator just labels the racks in cassandra-rackdc.properties and Cassandra does the rest.

Tunable consistency — per-query, not per-cluster

This is where Cassandra shines and where it diverges most from DynamoDB. Every query — read or write — carries a consistency level that the client picks. The server does whatever the client asked. RF=3 is fixed at table creation, but CL is negotiated on every request.

• ONE — wait for exactly 1 replica. Lowest latency. Weakest consistency.
• QUORUM — wait for ⌈RF/2⌉+1 replicas. With RF=3 that's 2 of 3. If you read-QUORUM and write-QUORUM, you get read-your-writes consistency because your read quorum overlaps your write quorum by at least 1 replica.
• ALL — wait for all RF replicas. Highest consistency. Highest latency. Any replica down = query fails.
• LOCAL_QUORUM — quorum within one data center only, for multi-DC deployments. The industry-standard default. Meets quorum locally, replicates async cross-DC.

The subtle brilliance is that a single Cassandra cluster can serve both low-latency (CL=ONE) analytics reads and read-your-writes (CL=QUORUM) transactional reads — on the same table. DynamoDB has this too since 2018 (strong vs eventual consistency flag on GetItem), but Cassandra had it since 2010.

When a replica is down — hinted handoff

Imagine you write with CL=QUORUM (2 of 3 must ACK). Two replicas respond quickly. The third is down. The write already succeeded — so what happens to that third replica when it comes back? It must somehow learn about the write.

The coordinator stores a hint — literally a small record: "when replica X comes back, deliver this row to it." Hints are held in a hints keyspace with a TTL (3 hours by default). When gossip detects the replica is back up, the coordinator drains its hints for that replica one-by-one until caught up. If a replica is down for more than 3 hours, hinted handoff gives up and read repair + anti-entropy (below) takes over.

Read repair — fix inconsistency on the read path

Every read with CL > ONE compares the responses from replicas. If they disagree, the coordinator picks the latest (by write-timestamp, which every Cassandra column carries) and writes the correct value back to the stale replicas synchronously before returning to the client. This is "foreground read repair." There's alsoread_repair_chance (default 10%): even CL=ONE reads occasionally check other replicas in the background.

Anti-entropy — Merkle tree repair for long divergence

If a replica has been down for days, hinted handoff has given up and read repair only fixes the rows people happen to read. To find every stale row on that replica, Cassandra runs nodetool repair — a Merkle-tree-based anti-entropy protocol identical to Dynamo's. Each replica computes a hash tree of its data partitions, the trees are exchanged, and diverging subtrees are streamed row-by-row from the healthy replica.

Cassandra vs Dynamo vs DynamoDB — the family tree

Where Cassandra runs in production

The mental model — Cassandra in one paragraph

Key takeaways

• 256 vnodes per host made adding and removing nodes trivial — no manual token assignment. This is the single biggest ops improvement Cassandra shipped over Dynamo.
• Gossip in O(log N) rounds is how you get a decentralized cluster of 1000+ nodes with no coordinator and still have every node know the ring within seconds.
• NetworkTopologyStrategy makes the ring rack-aware — replicas are placed in different racks and data centers automatically, so one rack failure never loses a key.
• Tunable consistency per query (CL=ONE, QUORUM, ALL, LOCAL_QUORUM) means one cluster can serve both analytics and transactional workloads. RF is per-table, CL is per-query.
• Hinted handoff + read repair + Merkle anti-entropy together make Cassandra converge no matter how long a replica has been down — 3 hours (hints), on-read (repair), or manual (nodetool repair).
• Cassandra is Dynamo + BigTable: this page covers the Dynamo half (ring, gossip, replication). The BigTable half — SSTables, MemTable, WAL, compaction — is a storage-engine topic covered in the LSM-tree concept page.

References

• Lakshman & Malik (2010) — "Cassandra: A Decentralized Structured Storage System." SIGOPS OSR, 2010.
• DeCandia et al. (2007) — "Dynamo: Amazon's Highly Available Key-value Store." SOSP 2007 — Cassandra's intellectual parent.
• Chang et al. (2006) — "Bigtable: A Distributed Storage System for Structured Data." OSDI 2006 — Cassandra's storage-engine parent.
• Cassandra 1.2 release notes (2013) — the release that introduced vnodes and Murmur3Partitioner as defaults.
• Discord Engineering — "How Discord Stores Trillions of Messages" (2022) — real-world scaling story.
• Netflix TechBlog — many posts on operating Cassandra at extreme scale (Priam, Astyanax, EVCache).