Cassandra

Cassandra takes the distribution model of Dynamo, a ring of equal nodes with no master and tunable consistency, and joins it to the data model and storage engine of Google's Bigtable, wide column tables stored as sorted, immutable files. The result is a database built for very high write throughput, linear scalability and no single point of failure. Understanding Cassandra means understanding two halves: how data is spread, and how each node stores it.

Data lives in tables inside keyspaces. A row is identified by a primary key, which has two parts with different jobs.

• The partition key decides which nodes hold the row. It is hashed to a position on the ring.
• The clustering columns decide the order of rows inside a partition on disk.

All rows with the same partition key form one partition and are stored together, sorted by the clustering columns. That makes reading a range inside one partition, such as "the latest 50 messages of this conversation", a fast sequential read from one place.

CREATE TABLE messages (
  conversation_id uuid,
  sent_at timeuuid,
  body text,
  PRIMARY KEY ((conversation_id), sent_at)
) WITH CLUSTERING ORDER BY (sent_at DESC);

Here conversation_id is the partition key and sent_at orders messages within it.

Unlike relational design, you design tables around the queries you will run, not around the entities. There are no joins, so related data is denormalized: the same facts may be stored in several tables, each shaped for one query. Every query should name the partition key, so it is served by a small set of nodes. Avoid unbounded partitions, because one very large partition becomes a hot spot and slow to compact, and split such data by adding a time bucket to the key, for example conversation and month.

Every node runs the same software. A hash function, the partitioner, maps each partition key to a token on the ring, and each node owns token ranges, with virtual nodes to even out load. Any node can accept any request and then acts as the coordinator for it, finding the replicas that own the data and forwarding the operation.

Replicas are chosen by a replication strategy and a replication factor (RF), the number of copies. A typical RF is 3. A topology-aware strategy spreads copies across racks and data centers, so losing a rack or a whole data center does not lose data. A component called the snitch tells Cassandra which rack and data center each node belongs to.

Nodes learn about each other through gossip: every second each node exchanges state with a few random peers, so membership and health spread through the cluster without a central registry.

Each read and write chooses a consistency level, the number of replicas that must respond.

• ONE: one replica. Fastest, weakest.
• QUORUM: a majority, which is RF/2 + 1, so 2 of 3.
• ALL: every replica. Strongest, least available.
• LOCAL_QUORUM: a majority within the local data center, avoiding slow cross-region trips.

As in Dynamo, if reads and writes together overlap, R + W > RF, then a read sees the latest write. Writing and reading at QUORUM with RF 3 gives 2 + 2 > 3. The choice is made per request, so a rarely changing profile may be read at ONE while a payment record is written at QUORUM.

A write is designed to be as cheap as possible. On each replica it goes through four steps.

1. Commit log: the write is appended to a sequential log on disk. Appending is fast, and the log guarantees durability: if the node crashes, it replays the log to recover.
2. Memtable: the write is applied to an in-memory sorted structure. Now it is readable.
3. The node acknowledges the write.
4. When the memtable grows too large, it is flushed to disk as an SSTable (sorted string table), an immutable, sorted file, and the matching part of the commit log is discarded.

There are no in-place updates and no random disk writes. All disk writes are sequential, which is why Cassandra can absorb enormous write rates, even on modest disks.

Because data for one key may be spread over the memtable and several SSTables, a read must check them all, then combine the results.

1. Check the memtable for recent data.
2. For each SSTable, consult its Bloom filter, a small in-memory structure that says "definitely not here" or "maybe here". Most SSTables are ruled out cheaply.
3. For candidate SSTables, use the partition index and caches to find the exact location on disk.
4. Read the matching data from each, and merge the pieces, with the value having the newest timestamp winning for each column.

This is why reads cost more than writes in Cassandra, and why keeping the number of SSTables small matters.

Over time flushes create many SSTables, which slows reads and wastes space with overwritten and deleted data. Compaction is a background process that merges several SSTables into one, keeping only the newest value of each cell and dropping data that has been overwritten or expired. Strategies trade off write and read cost.

• Size-tiered: merge SSTables of similar size. Cheap on writes, but can need a lot of temporary space.
• Leveled: organize SSTables into levels with non-overlapping key ranges, so a read touches few files. Better for read-heavy loads, at the cost of more write work.
• Time-window: group by time, ideal for time series data that is written once and expires.

A delete cannot remove data immediately, because the data sits in immutable files on possibly several replicas. Instead Cassandra writes a tombstone, a marker that says "this was deleted at time T". Reads see the tombstone and treat the data as gone. Compaction eventually removes both the data and the tombstone.

There is a subtle danger. If a replica was down during the delete and returns later, it may still hold the old data and could spread it back, resurrecting deleted data. To prevent this, tombstones are kept for a grace period, by default ten days, during which repair must reach every replica. Heavy use of deletes or of expiring data can create many tombstones that slow reads, so model data to avoid wide delete patterns.

Three mechanisms repair differences, the same ones as in Dynamo.

• Hinted handoff: when a replica is down, the coordinator stores a hint and delivers it when the node returns, for a limited time.
• Read repair: if a read finds replicas with different versions, the newest is written back to the stale ones.
• Anti-entropy repair: a scheduled process compares replicas using Merkle trees and streams only the differing ranges. It should run regularly, at least within the tombstone grace period.

Cassandra resolves conflicting writes to the same cell by last write wins, using timestamps. That is simple and fast, but depends on reasonably synchronized clocks and can lose one of two concurrent updates. For the rare case needing a compare-and-set, such as claiming a unique username, Cassandra offers lightweight transactions based on a consensus protocol, which are several times slower and should be used sparingly. There are no general multi-row transactions or joins.

• Good fit: huge write volumes, time series, messaging, sensor data, activity feeds, anywhere you know your queries in advance, need linear scaling, and must survive losing nodes or data centers.
• Poor fit: ad hoc queries and joins, heavy updates and deletes of the same data, strict multi-row transactions, or small data that fits one relational database comfortably.

The core lesson is a design principle worth remembering: by making writes append-only and sequential and pushing the cleanup work into the background, Cassandra turns the slow part of a disk, random writes, into something it never has to do.