Cassandra — Wide-Column Store Meets Dynamo

What you'll learn

• The Cassandra Origin Story

  Cassandra was designed at Facebook in 2008 to solve the inbox search problem: millions of users, billions of messages, need low-latency search across message metadata (sender, subject, timestamp), with writes distributed globally and no…

• Data Model — CQL Today vs Original Wide-Column

• Original Model (Thrift API)

  The original Cassandra data model was wide-column, inherited from BigTable: - Keyspace = database namespace - Column Family = analogous to a table, but schema-free - Row key = partition key (determines placement on ring) - Columns = name…

• Modern Model (CQL)

  CQL introduced a more familiar table abstraction. Today, you define a schema: The PRIMARY KEY has two parts: 1. Partition key (userid) — determines which nodes store this row. Hash of the partition key maps to a token on the ring. 2. Clu…

• Why This Matters

  Efficient queries are those that: 1. Specify the full partition key (so Cassandra knows which nodes to hit). 2. Optionally filter/sort by clustering columns (since they're already sorted on disk). Inefficient queries: - Scan multiple par…

• Peer-to-Peer, Masterless

  Unlike BigTable, which has a master server (the metadata server coordinated via Chubby/GFS) that assigns tablets to tablet servers, every Cassandra node is identical. There is no leader election, no master, no metadata server. When a cli…

• Partitioning — Consistent Hashing with Vnodes

  Cassandra uses consistent hashing (same as Dynamo) to distribute data across the cluster. The key space is a ring of tokens (64-bit integers), and each partition key is hashed to a token on the ring.

• Original Design (Single Token per Node)

  In early Cassandra, each node was assigned a single token on the ring. When you added a new node, it would split the token range of an existing node. Problem: uneven load distribution. If one node owned a huge range, it would be a hot sp…

• Modern Design (Vnodes)

  Since Cassandra 1.2 (2012), each physical node is assigned multiple virtual nodes (vnodes). Default: 256 vnodes per node. How it works: - Each physical node owns 256 random tokens on the ring. - A partition key hashes to a token, which m…

• Partitioners

  The hash function is pluggable via partitioners: - Murmur3Partitioner (default): hashes partition keys with MurmurHash3, distributes tokens uniformly. - RandomPartitioner (legacy): hashes with MD5, but slower than Murmur3. - ByteOrderedP…

• Replication — RF + Strategy

  Replication in Cassandra is configured at the keyspace level (not per table). When you create a keyspace, you specify: 1. Replication factor (RF): how many copies of each partition. 2. Replication strategy: how those copies are placed.

• SimpleStrategy (Single Datacenter)

  The simplest strategy: once the hash determines a primary replica (the first node clockwise on the ring from the token), the next RF - 1 replicas are placed on the next RF - 1 clockwise nodes on the ring. Example: RF = 3, and the token m…

• NetworkTopologyStrategy (Multi-Datacenter)

  For production multi-DC deployments, use NetworkTopologyStrategy (NTS). You specify RF per datacenter: This places 3 replicas in dc1 and 3 in dc2, ensuring that each DC can serve requests independently if the other DC is down. Within a D…

• Consistency Levels — Tunable, per Query

  One of Cassandra's defining features is tunable consistency: each read or write specifies a consistency level (CL), which determines how many replicas must respond before the operation succeeds.

• Write Consistency Levels

  - ANY: Write to at least one node (or hinted handoff). Fastest, but least durable (if the only node that got it crashes before flushing to disk, data is lost). - ONE: Write to at least one replica (commit log + memtable). Fast, but no re…

• Read Consistency Levels

  - ONE: Read from the fastest replica (per dynamic snitch). Fast, but might return stale data if that replica is behind. - TWO, THREE: Read from 2 or 3 replicas, wait for both/all to respond, reconcile. Higher latency than ONE, but more l…

• Strong Consistency Formula

  If R + W > RF, you get strong consistency (per partition key): any read will see the latest write. Example: RF = 3, write at QUORUM (W = 2), read at QUORUM (R = 2). R + W = 4 > 3, so read and write quorums overlap, guaranteeing the read…

• The Storage Engine — LSM Straight from BigTable

  Cassandra's storage engine is a log-structured merge tree (LSM), the same architecture as BigTable and LevelDB.

• Write Path (Storage)

  When a write arrives at a replica: 1. Append to commit log: sequential disk write to a durable log file (commitlog/ directory). This ensures durability before memory updates. 2. Insert into memtable: in-memory sorted map (one memtable pe…

• Read Path (Storage)

  To read a partition: 1. Check memtable: is the partition in memory? If so, read it. 2. Check key cache: is the partition's SSTable location cached? If so, skip the Bloom filters and go directly to the SSTable. 3. Check Bloom filters: for…

• Compaction Strategies

  Because SSTables are immutable, old/deleted data accumulates. Compaction merges SSTables, discarding tombstones (after gcgraceseconds), and consolidating versions. Cassandra has three main compaction strategies:

• Read Path in Detail

  When a read request arrives (e.g., SELECT FROM messages WHERE userid = ?), here's the full coordinator read path:

• 1. Coordinator Selection

  The client sends the query to any node (round-robin, or token-aware if the driver knows the ring topology). That node becomes the coordinator for this read.

• 2. Replica Determination

  The coordinator hashes the partition key (userid) to a token, looks up which nodes own that token (per the replication strategy and current ring state), and determines the replicas (e.g., for RF = 3, three nodes).

• 3. Dynamic Snitch (Latency Tracking)

  The coordinator tracks recent latency to each replica (via gossip and probe requests). It picks the fastest replica to send a full data request (read the partition). The other replicas (based on the consistency level) get digest requests…

• 4. Wait for Consistency Level Responses

  The coordinator waits for R responses (per the CL). For QUORUM with RF = 3, it waits for 2 responses.

• 5. Digest Reconciliation

  If the digest from replica B matches the digest of A's data, and C's digest also matches, we're done — return A's data to the client. If the digests don't match (replicas are out of sync), the coordinator must read-repair: - Request full…

• 6. Background Read Repair (Optional)

  Cassandra can optionally do background read repair with a configured probability (e.g., 10% of reads). Even if the consistency level is satisfied, the coordinator sends digest requests to all replicas, and if any are out of sync, repairs…

• Write Path in Detail

  Here's the full coordinator write path for an INSERT/UPDATE/DELETE:

• Pseudo-Code

• Key Points

  1. Parallel writes: the coordinator sends the mutation to all replicas at once (not sequential). This minimizes latency. 2. Timestamp: the write includes a microsecond timestamp (either client-provided or coordinator-generated). This is…

• On-Replica Write

  When a replica receives the mutation: 1. Append to commit log: sequential write to disk (durability). 2. Insert into memtable: in-memory update (fast). 3. ACK to coordinator: immediately respond (don't wait for flush to SSTable). The com…

• Conflict Resolution — Last-Write-Wins with Timestamps

  One of the biggest departures from Dynamo: Cassandra dropped vector clocks in favor of last-write-wins (LWW) based on timestamps.

• Why Vector Clocks Were Dropped

  Vector clocks track causality: if write A happened-before write B, the vector clock knows. If A and B are concurrent (neither happened-before), the vector clock says "conflict" and punts to the application to resolve it (Dynamo's sibling…

• Last-Write-Wins (LWW)

  Every write includes a microsecond timestamp (64-bit integer). When replicas are out of sync and must reconcile: - The write with the highest timestamp wins. - If timestamps are equal (rare but possible), the write with the lexicographic…

• Clock Skew Hazard

  If node A's clock is 1 second ahead of node B's clock: 1. Client writes to node A → timestamp = now + 1 second. 2. Client writes to node B (updating the same key) → timestamp = now. 3. Reconciliation: A's write wins (higher timestamp), e…

• Deletes and Tombstones

  Deletes in Cassandra are implemented as tombstones: a special marker with a timestamp. When you delete a column or row, Cassandra writes a tombstone to the memtable and SSTables. Why tombstones? - Because SSTables are immutable, you can'…

• Anti-Entropy — Merkle Trees + Repair

  Even with read repair, replicas can diverge (e.g., if a write succeeded on 2/3 replicas and the third was down). Cassandra uses anti-entropy repair to keep replicas consistent in the background.

• Merkle Trees

  Cassandra builds a Merkle tree over each SSTable (same concept as Dynamo): - Partition keys are grouped into ranges (leaf nodes). - Each leaf node hashes its range of keys → hash H. - Parent nodes hash their children's hashes → tree up t…

• Repair Operations

  Cassandra has several repair modes:

• When to Repair

  - Pre-4.0: you must run full repair on every node within gcgraceseconds (10 days) to prevent tombstone resurrection. This was a major operational burden. - 4.0+: incremental repair is more reliable, and read repair (foreground + backgrou…

• Snitch Types & Topology Discovery

  The snitch is Cassandra's mechanism for understanding datacenter and rack topology. It's critical for replica placement and read routing. Several snitch implementations exist:

• SimpleSnitch

  The default snitch for single-datacenter deployments. Treats all nodes as being in the same datacenter and rack. Cassandra simply walks the ring clockwise to place replicas. - Use case: Development, single-DC deployments. - Limitation: C…

• PropertyFileSnitch

  Reads topology information from a configuration file (cassandra-topology.properties). You manually map IP addresses to datacenters and racks: - Use case: Static deployments where IPs don't change often. - Limitation: Manual configuration…

• GossipingPropertyFileSnitch

  Each node declares its own datacenter and rack in cassandra-rackdc.properties. Gossip automatically propagates this topology to the entire cluster: - Use case: Production deployments with static topology. Each node knows its own location…

• Ec2Snitch

  Auto-detects AWS region and availability zone from EC2 instance metadata. Region becomes the datacenter name; AZ becomes the rack name. - Use case: AWS deployments where you want automatic topology discovery. - Advantage: Zero configurat…

• Ec2MultiRegionSnitch

  Similar to Ec2Snitch but designed for cross-region AWS deployments. Uses private IPs within a region and public IPs for cross-region communication. - Use case: Multi-region AWS deployments with VPC peering or public endpoints. - Advantag…

• GoogleCloudSnitch

  Auto-detects Google Cloud region and zone from GCE instance metadata. - Use case: GCP deployments with automatic topology. - Advantage: Like Ec2Snitch, zero config.

• CloudstackSnitch

  For Apache CloudStack deployments. Reads zone and rack from CloudStack metadata. Choosing a snitch: If you're on AWS, use Ec2Snitch (single region) or Ec2MultiRegionSnitch (multi-region). If you're on GCP, use GoogleCloudSnitch. For on-p…

• Membership & Gossip

  Cassandra uses a gossip protocol (Scuttlebutt-style, same as Dynamo) for cluster membership and failure detection.

• How Gossip Works

  1. Every second, each node picks 1-3 random peers (from its known cluster) and gossips its state: - My token ranges (vnodes). - Other nodes I know about (and their states). - Heartbeat counters (version numbers). 2. When node A receives…

• Failure Detection

  Each node maintains a heartbeat counter for every other node (incremented each gossip round). If node A hasn't heard from node B in phiconvictthreshold rounds (default: ~10 seconds), A marks B as down. This is a phi accrual failure detec…

• Seeds

  Seeds are a small set of nodes (e.g., 3 in a 100-node cluster) that new nodes contact to learn the ring topology. Seeds don't elect a leader or coordinate anything — they're just well-known addresses for bootstrapping. - When a new node…

• Split-Brain Avoidance

  Because Cassandra is masterless and has no quorum-based leader election, it's vulnerable to split-brain in network partitions. If a cluster is partitioned into two halves: - Each half can serve reads/writes independently. - If you use CL…

• Lightweight Transactions (LWT) with Paxos

  Most Cassandra operations are eventually consistent (with tunable consistency levels). But some operations require linearizability (stronger than strong consistency): only one client can succeed, no concurrent updates allowed. Example: u…

• How LWT Works (Paxos)

  Paxos is a consensus protocol that ensures a value is agreed upon by a quorum of replicas. Cassandra uses per-partition Paxos: each partition key runs its own Paxos instance (there's no global Paxos across the cluster). The Paxos flow (s…

• LWT Consistency Levels

  - SERIAL: full Paxos quorum across all replicas (global consensus). - LOCALSERIAL: Paxos quorum in the local DC only (doesn't wait for other DCs). Reads with IF conditions must use CL = SERIAL or LOCALSERIAL to ensure linearizability.

• Cost of LWT

  LWT is expensive: - 4× latency of a normal write (two round-trips: prepare + propose). - High contention cost: if multiple clients try to update the same partition key, Paxos conflicts, and clients must retry (exponential backoff). - Pax…

• Materialized Views & Secondary Indexes

• Secondary Indexes

  Cassandra supports secondary indexes on non-partition-key columns: Under the hood: - Cassandra creates a hidden table mapping sender → partitionkeys. - When you query sender = 'alice', Cassandra: 1. Queries the secondary index table to f…

• Interview Takeaways

  When discussing Cassandra in interviews, hit these points: 1. Partition keys determine performance Cassandra is a distributed hash table. Efficient queries target a single partition (specify the full partition key). Scatter-gather querie…

• Further Reading

  - Original paper: Lakshman & Malik, "Cassandra: A Decentralized Structured Storage System" (2010) — the Facebook design doc. - Dynamo paper: DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (2007) — Cassandra's availa…