How Cassandra distributes and replicates data

The Interview Question

Interviewer: "Your team uses Cassandra for a high-write-throughput event store. A developer deletes a batch of records, but a week later those records reappear in query results. Walk me through how Cassandra handles deletes internally and explain why this 'zombie data' problem occurs."

This question tests whether you understand Cassandra beyond the API layer. The interviewer is probing for knowledge of tombstones, gc_grace_seconds, anti-entropy repair, and how the LSM tree storage engine interacts with distributed consistency. Candidates who answer "just delete it again" fail. Candidates who explain the tombstone lifecycle, compaction, and the repair window nail it.

What to Clarify Before Answering

You: "Before I walk through this, let me scope the answer..."

• "What replication factor are we running? RF=3 is standard, but it changes how many nodes need to see the tombstone."
• "Are we running regular anti-entropy repairs? The repair schedule interacts directly with gc_grace_seconds."
• "Which compaction strategy is this table using? Size-Tiered, Leveled, and Time-Window each handle tombstones differently."
• "What consistency level are the reads using? A read at ONE is much more likely to miss a tombstone than a read at QUORUM."
• "How large are the partitions? Wide partitions with thousands of tombstones create performance problems beyond just zombie data."

Why this matters: Cassandra's delete behavior is not a bug. It is a deliberate design tradeoff in a distributed system with no single coordinator. Every clarifying question above demonstrates you understand the interaction between consistency, compaction, and garbage collection.

The 30-Second Answer

Cassandra is a distributed wide-column database that distributes data across a ring of nodes using consistent hashing with virtual nodes. Every node is equal (no leader, no coordinator). Nodes discover each other and share cluster state through a gossip protocol with a phi accrual failure detector. Writes go to a commit log for durability, then to an in-memory memtable, which flushes to immutable SSTables on disk. The storage engine is an LSM tree (Log-Structured Merge tree) with configurable compaction strategies. Reads merge data from memtables and multiple SSTables, using Bloom filters and partition indexes to skip irrelevant files. Consistency is tunable per query: you choose how many replicas must respond (ONE, QUORUM, ALL), trading latency for correctness.

The Architecture Overview

The architecture is peer-to-peer. There is no master node, no leader election, no single point of failure. Any node can coordinate any request. The client driver maintains connections to multiple nodes and picks a coordinator based on load balancing policy (round-robin, token-aware, or datacenter-aware).

I find this design fundamentally different from DynamoDB or MongoDB. There is no metadata service, no routing layer, no managed control plane. Every node knows the full token ring through gossip. This makes Cassandra operationally harder (you manage everything) but architecturally simpler (no hidden dependencies).

Consistent Hashing and Virtual Nodes

Cassandra distributes data using a token ring. Each partition key is hashed (using Murmur3 by default) to produce a token, which is a 64-bit integer. The token ring spans from $-2^63$ to $2^63-1$. Each node owns a set of token ranges.

With virtual nodes (vnodes), each physical node owns many small, non-contiguous token ranges instead of one large range. The default is 256 vnodes per node. This solves two problems:

1. Even distribution: When a node joins or leaves, only its vnodes are redistributed, not a single large chunk. This makes rebalancing faster and less disruptive.

2. Heterogeneous hardware: A node with more capacity can own more vnodes, accepting a proportionally larger share of data.

The replication factor (RF) determines how many copies of each partition exist. RF=3 means the data lives on 3 nodes: the primary owner (determined by the token) and the next 2 nodes clockwise on the ring. For multi-datacenter deployments, Cassandra uses the NetworkTopologyStrategy to ensure replicas are spread across racks and datacenters.

The partition key hash determines the row's position on the ring. Clustering columns determine the sort order within a partition. This is a critical distinction: the partition key controls data distribution (which node), and the clustering columns control data organization (sort order on disk). A well-designed Cassandra schema ensures that all data needed for a query lives in a single partition, sorted by the clustering columns in the query's sort order.

// Pseudocode: Token-based routing
function routeWrite(partitionKey, data, RF):
    token = murmur3Hash(partitionKey)
    primaryNode = findNodeForToken(tokenRing, token)
    replicaNodes = getNextNNodes(tokenRing, primaryNode, RF - 1)
    allTargets = [primaryNode] + replicaNodes

    for node in allTargets:
        node.write(token, data)

    waitForAcks(allTargets, consistencyLevel)

Gossip Protocol and Failure Detection

Every Cassandra node runs a gossip protocol that shares cluster state. Every second, each node picks a random other node and exchanges state information: which nodes are alive, what tokens they own, their schema version, their load metrics.

Gossip is eventually consistent by design. A new node joining the cluster is known to all nodes within a few gossip rounds (typically 3-5 seconds for a 100-node cluster). This is not a problem for correctness because Cassandra reads and writes tolerate temporary inconsistency through tunable consistency levels.

Failure detection uses the phi accrual failure detector. Instead of a binary "alive/dead" threshold, the phi detector outputs a suspicion level (phi value) based on the inter-arrival times of gossip messages. When phi exceeds a configurable threshold (default: 8), the node is marked as down.

When a node is marked down, the coordinator routes requests to other replicas. Hinted handoff stores writes destined for the dead node on the coordinator, and delivers them when the node comes back. This is a temporary measure: hints expire after 3 hours by default.

The gossip state for each node includes:

• Heartbeat generation: A timestamp of when the node started. Monotonically increasing across restarts.
• Heartbeat version: Incremented with each gossip round. Used to detect stale state.
• Application state: Token ownership, schema version, datacenter/rack placement, load metrics, severity (disk usage), and host ID.
• Status: NORMAL, JOINING, LEAVING, MOVING, or REMOVED.

When a node joins the cluster, it contacts seed nodes first, then rapidly learns the full cluster state through a few gossip rounds. The convergence time for a 100-node cluster is typically under 10 seconds. For a 1,000-node cluster, convergence takes 30-60 seconds.

The Write Path: Memtable to SSTable

Cassandra's write path is optimized for speed. Every write is append-only, which gives sub-millisecond latency on the local node.

The write path has four stages:

1. Commit log: The write is appended to a commit log file on disk. This is sequential I/O, extremely fast. The commit log is the durability guarantee: if the node crashes after this step, the write can be replayed on restart.

2. Memtable: The write is inserted into an in-memory sorted data structure (a skip list or red-black tree). The memtable is organized by partition key and clustering columns. Each table has its own memtable. The memtable is lock-free for concurrent writes using a compare-and-swap (CAS) approach.

3. Flush: When the memtable reaches a size threshold (default ~128 MB), it is flushed to disk as an immutable SSTable (Sorted String Table). The commit log segments that correspond to the flushed data are deleted. Flushing is sequential I/O: the memtable is already sorted, so it writes the SSTable in partition key order without any random seeks.

4. Compaction: Over time, multiple SSTables accumulate. Compaction merges them, removing deleted data (tombstones past gc_grace_seconds) and deduplicating overwrites. Compaction runs in the background and is the primary source of write amplification.

An SSTable consists of several on-disk components:

• Data file (.db): The actual rows, sorted by partition key and clustering columns, compressed in 64 KB blocks.
• Partition index: Maps partition keys to byte offsets in the data file. Enables O(log N) lookups.
• Bloom filter (.bf): Probabilistic membership test per partition key. Answers "is this key in this SSTable?"
• Compression offset map: Maps partition offsets to compressed block offsets.
• Statistics (.stats): Min/max clustering columns, tombstone counts, TTL ranges. Used by compaction to prioritize files.
• Summary (.sum): A sampled index of the partition index. Kept in memory for fast first-level lookup.

Compaction Strategies

The Read Path: Bloom Filters and SSTable Merge

Reads in Cassandra are more complex than writes because data for a single partition may be spread across the memtable and multiple SSTables.

The read path uses multiple optimization layers:

1. Memtable check: The most recent data is in memory. If the partition exists in the memtable, that data is included in the merge.

2. Bloom filters: Each SSTable has a Bloom filter. This probabilistic data structure answers "does this partition key exist in this SSTable?" with either "definitely no" or "probably yes." A Bloom filter configured at 1% false positive rate lets Cassandra skip 99% of SSTables that do not contain the requested partition. No disk I/O needed for skipped SSTables.

3. Partition index: For SSTables that pass the Bloom filter, Cassandra does a binary search on the partition index to find the byte offset of the requested partition.

4. Compression offset map: SSTables are stored in compressed blocks (default: 64 KB). The compression offset map translates the partition's byte offset to the correct compressed block.

5. Disk read: The compressed block is read from disk, decompressed, and the requested rows are extracted.

6. Merge: Results from the memtable and all matching SSTables are merged by timestamp. For columns that exist in multiple SSTables, the newest timestamp wins. Tombstones (delete markers) suppress older data.

// Pseudocode: Cassandra read merge
function readPartition(partitionKey):
    results = []

    // Check memtable first (newest data)
    if memtable.contains(partitionKey):
        results.add(memtable.get(partitionKey))

    // Check each SSTable, newest first
    for sstable in sortByAge(allSSTables, newest_first):
        if sstable.bloomFilter.mightContain(partitionKey):
            offset = sstable.partitionIndex.lookup(partitionKey)
            if offset != null:
                block = decompress(sstable.data[offset])
                results.add(block.getRows(partitionKey))

    // Merge all results by timestamp
    merged = mergeByTimestamp(results)

    // Apply tombstones: suppress any row/column
    // where a tombstone has a newer timestamp
    return applyTombstones(merged)

The merge process is where Cassandra pays the price for its fast writes. Every write creates a new version of the data, and reads must reconcile all versions. This is why the number of SSTables per read directly impacts latency.

Tunable Consistency: ONE, QUORUM, ALL

Cassandra does not have a fixed consistency model. You choose the consistency level per query. This is the key tradeoff mechanism.

The consistency formula is: if W + R > RF, you get strong consistency. With RF=3:

• QUORUM write (W=2) + QUORUM read (R=2): 2+2=4 > 3. Strong consistency. At least one node in the read set saw the latest write.
• ONE write (W=1) + ONE read (R=1): 1+1=2 < 3. Eventually consistent. The read might hit a replica that missed the write.
• ALL write (W=3) + ONE read (R=1): 3+1=4 > 3. Strong consistency, but writes block on the slowest replica.

Read repair happens automatically when a coordinator detects stale data during a read. If two replicas return different versions, the coordinator sends the latest version to the stale replica. This is a background consistency healing mechanism, not a replacement for repair.

Anti-entropy repair uses Merkle trees to compare data between replicas. Each node builds a hash tree over its data. Replicas exchange tree roots and drill down to find differing ranges, then stream only the mismatched data. This is much more efficient than comparing every row.

The repair process works in stages:

1. Build Merkle trees: Each replica computes a hash tree for the token ranges being repaired. This is CPU and I/O intensive on large datasets.
2. Exchange and compare: Replicas exchange tree roots. If roots match, the data is identical (no repair needed). If roots differ, they recursively compare subtrees to narrow down the divergent ranges.
3. Stream data: Only the mismatched ranges are streamed between replicas. This minimizes network bandwidth.
4. Apply: The receiving replica merges the streamed data, keeping the newest timestamp for each column.

Repair can be full (compares all data) or incremental (compares only data that changed since the last repair). Incremental repair is faster but requires that anti-compaction correctly separates repaired and unrepaired SSTables. In older Cassandra versions (pre-4.0), incremental repair had bugs that caused data inconsistency. I recommend full repair for clusters on versions below 4.0.

Tombstones, gc_grace_seconds, and Zombie Data

Deletes in Cassandra are the most misunderstood feature. Cassandra does not remove data immediately. It writes a tombstone: a marker that says "this data is deleted as of timestamp T."

Why? Because Cassandra is distributed. If you delete a row and immediately remove it from one replica, the other replicas still have it. On the next read repair or anti-entropy repair, the "live" replicas would re-propagate the row back to the replica that deleted it. The row comes back from the dead.

Tombstones prevent this by persisting the delete marker. During reads, tombstones suppress older data. During compaction, tombstones eventually trigger actual data removal, but only after gc_grace_seconds (default: 10 days).

There are several types of tombstones in Cassandra:

• Cell tombstone: Deletes a single column in a row.
• Row tombstone: Deletes an entire row (all columns).
• Range tombstone: Deletes a range of rows within a partition (by clustering key range). Efficient for DELETE FROM table WHERE pk='x' AND ck > 100.
• Partition tombstone: Deletes an entire partition. Rare but used by DELETE FROM table WHERE pk='x'.

Range tombstones are particularly dangerous for performance. A single range tombstone can suppress thousands of rows, and the read path must evaluate the tombstone against every row in the range. If your workload generates many range tombstones (e.g., deleting old time-series data by range), compaction must process them efficiently or reads degrade severely.

This is the zombie data problem. It occurs when:

1. A delete happens, creating a tombstone.
2. One replica misses the tombstone (it was down).
3. gc_grace_seconds passes and compaction removes the tombstone from the replicas that had it.
4. The lagging replica comes back and its stale data propagates back via read repair or anti-entropy repair.

Lightweight Transactions (Compare-and-Set)

Cassandra's tunable consistency does not give you linearizable operations by itself. QUORUM reads and writes give you strong consistency (latest value guaranteed), but they do not prevent two clients from doing a read-modify-write cycle that overwrites each other's changes.

For this, Cassandra provides lightweight transactions (LWT) using a Paxos-based protocol. The syntax uses IF clauses:

-- Only insert if the row does not exist
INSERT INTO users (id, name, email)
VALUES ('u42', 'Alice', 'alice@example.com')
IF NOT EXISTS;

-- Only update if the current value matches
UPDATE accounts SET balance = 900
WHERE id = 'acc1'
IF balance = 1000;

Internally, an LWT goes through four phases: Prepare, Promise, Propose, Commit. This is a full Paxos round, which means 4 round trips between replicas instead of 1 for a normal write. As a result, LWT latency is 4-10x higher than a regular write (20-50ms vs 3-5ms).

What Happens When Things Break

Performance Characteristics

The JVM garbage collection characteristics of Cassandra deserve special attention. Cassandra runs on the JVM (Java), and large heaps (>8 GB) can cause GC pauses that stall all operations on a node. This is why modern Cassandra deployments:

• Use off-heap memory for Bloom filters, partition indexes, and compression offset maps (reducing GC pressure).
• Limit JVM heap to 8-16 GB and rely on the OS page cache for data caching.
• Use G1GC or ZGC garbage collectors to minimize stop-the-world pauses.
• Monitor GC pause duration closely (>500ms pauses cause gossip failures and false node-down detection).

ScyllaDB, a Cassandra-compatible database written in C++, eliminates the JVM entirely. This gives it 2-5x better latency at the p99 level because there are no GC pauses. If JVM tuning is your primary operational headache, evaluating ScyllaDB is worthwhile.

How This Compares to Alternatives

I reach for Cassandra when I need massive write throughput on hardware I control, especially for time-series, event stores, or IoT data. I switch to DynamoDB when I want zero operations overhead and can model simple key-value patterns. I would evaluate ScyllaDB as a drop-in Cassandra replacement when JVM GC pauses are causing latency spikes. I use MongoDB when I need flexible querying and aggregation pipelines.

Interview Cheat Sheet

• When asked about data distribution: "Cassandra uses consistent hashing with virtual nodes. Each partition key is hashed to a token. The token determines which node owns the data. With RF=3, data replicates to the next 2 nodes clockwise on the ring."

• When asked about writes: "Writes are append-only: commit log for durability, then memtable in memory, then flush to immutable SSTables on disk. This is why writes are sub-millisecond. No random I/O on the write path."

• When asked about reads: "Reads merge data from the memtable plus multiple SSTables. Bloom filters eliminate 90%+ of unnecessary SSTable checks. The remaining SSTables are read via partition index and decompressed."

• When asked about consistency: "Consistency is tunable per query. QUORUM writes (W=2) plus QUORUM reads (R=2) with RF=3 gives strong consistency because W+R > RF. Any weaker combination gives eventual consistency."

• When asked about deletes: "Deletes write tombstones, not actual deletions. Tombstones are garbage collected after gc_grace_seconds (default 10 days). If a replica misses a tombstone and gc_grace passes, zombie data can appear. Regular repair prevents this."

• When asked about compaction: "Compaction merges SSTables to reduce read amplification and reclaim tombstoned data. Size-Tiered for write-heavy, Leveled for read-heavy, Time-Window for time-series. Wrong compaction strategy is the number one performance killer."

• When asked about failure handling: "There is no leader, so no leader election. Any node can coordinate. A dead node is detected by the phi accrual failure detector in seconds. Hinted handoff stores writes for it (up to 3 hours). Repair syncs it when it returns."

• When asked about gossip: "Every node runs gossip every second, exchanging cluster state with random peers. The phi accrual failure detector learns normal heartbeat patterns and adapts its threshold. This is much more reliable than fixed timeout heartbeats."

• When asked vs DynamoDB: "Cassandra gives you tunable consistency, open-source control, and sub-millisecond writes on your own hardware. DynamoDB gives you zero-ops, predictable pricing, and tight AWS integration. Choose Cassandra for write throughput and control, DynamoDB for simplicity and serverless."

• When asked about data modeling: "Cassandra requires you to model your tables around your queries. Each query pattern gets its own table with the right partition key and clustering columns. Denormalization is expected. If you need JOINs, ad-hoc queries, or flexible schema changes, Cassandra is the wrong choice."

• When asked about operational complexity: "Cassandra demands active management: compaction tuning, repair scheduling, JVM GC tuning, token rebalancing on cluster changes, and tombstone monitoring. Budget at least one engineer focused on Cassandra operations for every 20 nodes. If you cannot afford that, use a managed alternative like DataStax Astra or switch to DynamoDB."

Test Your Understanding

Quick Recap

These are the 8 facts that matter most for interviews and production debugging. If you can explain each of these clearly, you have a strong grasp on Cassandra internals.

1. Cassandra distributes data across a ring using consistent hashing with virtual nodes, where each partition key is hashed to a token that determines which nodes store it.

2. The gossip protocol runs on every node every second, sharing cluster state, and the phi accrual failure detector adapts to network conditions rather than using fixed timeouts.

3. Writes are append-only (commit log then memtable), giving sub-millisecond latency because there is no random I/O on the write path.

4. Memtables flush to immutable SSTables, which are merged by compaction: Size-Tiered for writes, Leveled for reads, Time-Window for time-series.

5. Reads merge data from the memtable and multiple SSTables, using Bloom filters to skip 90%+ of irrelevant files.

6. Consistency is tunable per query: QUORUM reads + QUORUM writes with RF=3 gives strong consistency (W+R > RF).

7. Deletes write tombstones that are garbage collected after gc_grace_seconds; failing to repair within that window causes zombie data.

8. There is no leader, no master, no single point of failure: any node can coordinate any request, making Cassandra highly available but operationally demanding.

9. Lightweight transactions (LWT) provide compare-and-set semantics using Paxos but cost 4-10x more latency than regular writes, so use them sparingly.

10. JVM garbage collection is the most common source of latency spikes in Cassandra. Keep heap under 16 GB, monitor GC pauses, and consider ScyllaDB if GC is your primary pain point.

Related Concepts

These topics are directly connected to Cassandra's architecture. Understanding them gives you a deeper foundation for distributed systems interviews.

• LSM Trees: The storage engine architecture Cassandra uses, trading write performance for read complexity. Understanding LSM trees is essential for tuning compaction strategies.
• Consistent Hashing: The partitioning mechanism Cassandra uses to distribute data across nodes. Also used by DynamoDB, Riak, Redis Cluster, and most distributed key-value stores.
• Bloom Filters: The probabilistic data structure that makes Cassandra reads efficient by eliminating unnecessary SSTable lookups. Worth understanding the math behind false positive rates.
• CAP Theorem: Cassandra is an AP system by default (available and partition-tolerant), but achieves CP behavior when using QUORUM consistency. This is the most common interview question linked to Cassandra.
• Vector Clocks and Conflict Resolution: Understanding why Cassandra uses last-write-wins (timestamps) instead of vector clocks helps explain its simplicity and limitations compared to systems like Riak.
• Gossip Protocols: The peer-to-peer protocol Cassandra uses for cluster membership and failure detection. Understanding gossip helps you debug network partition scenarios and node join/leave behavior.
• Tombstones and Deletion in Distributed Systems: How distributed databases handle deletes without a central coordinator. Cassandra's approach with tombstones and gc_grace_seconds is a textbook example of the tradeoffs involved in distributed deletion.