In November I read Cassandra: A Decentralized Structured Storage System. The design is easiest to understand as a synthesis: Dynamo contributes decentralised partitioning and availability mechanisms, while Bigtable contributes a structured, sorted column-family data model and storage engine ideas.
The original workload was Facebook Inbox Search: high write volume, geographic distribution and a requirement to remain available without one database master.
Paper: Cassandra: A Decentralized Structured Storage System (PDF)
Any node can coordinate a request
A client may send a read or write to any Cassandra node. That node becomes the coordinator for the operation. It determines which replicas own the key, forwards requests and combines acknowledgements or read results.
There is no permanent per-key primary in the normal request path. This removes one central data-plane role, but every node needs sufficiently current topology and token metadata to route correctly.
Partitioning and the ring
Cassandra places keys in a circular partition space and assigns ranges to nodes. The original paper discusses consistent hashing and an order-preserving partitioner. Modern deployments commonly use token hashing that aims for even distribution.
The partition key determines placement. Rows sharing a partition key are stored together and operations within that partition can be made efficient. A poorly chosen key can create an oversized or hot partition even when the rest of the ring is balanced.
This gives a practical schema rule:
partition key → where data lives and how load spreadsclustering key → how rows are ordered within that partitionThe exact modern terminology has evolved, but placement and local ordering remain the two essential decisions.
Replication across failure domains
For each token range, Cassandra chooses a preference list of replicas. Placement strategies try to distribute copies across racks and data centres.
Replication factor says how many copies exist; consistency level says how many must participate in an operation. These are separate controls.
For replication factor three:
write ONE → return after one replica acknowledgeswrite QUORUM → return after two acknowledgeread ONE → return one replica's valueread QUORUM → compare two replicasAs with Dynamo, R + W > N creates overlap in the normal model. Real guarantees also depend on failure handling, timestamps, repair and topology.
The write path is append-oriented
A replica handling a write follows an LSM-style path:
write → commit log → memtable → immutable SSTableThe commit log provides durability. The memtable keeps sorted in-memory state. When full, it flushes to an SSTable.
This avoids random in-place disk updates and supports high write throughput. The deferred cost appears in reads and compaction, where multiple immutable files must be reconciled.
The read path
A read may consult a memtable and several SSTables. Bloom filters rule out files that definitely do not contain a partition. Index summaries and partition indexes locate likely data positions, and the newest cells are reconciled by timestamp.
Caches can help hot partitions, but they do not eliminate disk and compaction behaviour. A read-heavy workload with many overlapping SSTables can experience amplification even when writes are fast.
This is why storage engines must be evaluated as a cycle, not only by write-path latency.
Compaction and tombstones
Deletes are represented by tombstones because immutable SSTables cannot be edited in place. Compaction merges SSTables, keeps the winning cell versions and eventually removes tombstones after it is safe to assume old replicas will not reintroduce deleted data.
Removing tombstones too early risks resurrection. Keeping them too long increases read cost. Repair frequency, grace periods and failure duration therefore interact.
Compaction strategy should match workload shape: time-series data, frequent updates and mostly immutable partitions produce different file overlap and expiration behaviour.
Gossip membership and failure detection
Cassandra uses gossip to spread cluster state. The paper discusses a Scuttlebutt-style anti-entropy mechanism and a phi accrual failure detector.
Instead of returning a fixed alive/dead boolean, a phi detector produces a suspicion level based on recent heartbeat arrival patterns. The system can choose a threshold appropriate to its environment.
Failure detection remains local. One node may temporarily consider a peer unavailable while another can reach it. Routing can avoid the suspected node without immediately rewriting the authoritative token map.
Hinted handoff and availability
When an intended replica is unavailable, a coordinator can store a hint with another node. The hint is later delivered to the recovered replica.
Hints make short outages inexpensive and keep writes available. They are not a permanent repair system. A long outage can exceed hint retention, and a hinted copy does not replace regular replica synchronization.
Capacity planning must include the recovery burst: an unavailable replica reduces normal capacity while hints and later repair add more work.
Read repair and anti-entropy repair
Replica divergence is expected under partial failure and low consistency levels. Cassandra detects and repairs it through reads and background range repair.
Merkle trees summarize token ranges so replicas can identify differing subranges without exchanging every key. The mechanism is related to Dynamo’s anti-entropy design.
Repair is part of the consistency lifecycle. If it is never completed, replicas can remain stale beyond the period assumed by tombstone collection and operational policy.
Conflict resolution
The early model uses timestamps to select the winning cell. This avoids returning application-visible vector-clock siblings as Dynamo does, but it shifts correctness onto timestamp quality and last-write-wins semantics.
Clock skew can make an older real-world event carry a larger timestamp. Concurrent updates to the same cell can lose information silently. Data models should therefore prefer commutative or append-like updates where possible and avoid using last-write-wins as a substitute for domain conflict handling.
Lightweight transactions and newer features add stronger mechanisms, but they have different latency and availability costs and are outside the core paper design.
Data-model history
The paper describes column families and super columns. Cassandra’s current data model and query language have changed significantly; super columns are historical.
The durable concept is not the old API. It is that storage is organized around partition-local access. Queries that match the partition key and clustering order are efficient; arbitrary relational access is not the design centre.
Failure scenarios I worked through
One replica is down during a write: the selected consistency level may still succeed, with a hint stored for later delivery.
Replicas return different values: the coordinator reconciles versions and repair mechanisms update stale copies.
A node is permanently replaced: token ranges stream to new owners and repair establishes complete replicas.
A network partition splits the cluster: each side can serve operations permitted by its available replicas; conflicting timestamps and later repair decide convergence.
A deleted value returns: an old replica missed the tombstone and rejoined after tombstone garbage collection—showing why repair windows matter.
What I keep from the paper
Cassandra is not merely “a database without a master.” It is a coordinated set of trade-offs:
partitioned ring → incremental scalereplication → failure tolerancetunable consistency → per-operation availability choicegossip + failure signal → decentralized routing knowledgecommit log + SSTables → high write throughputhints + repair → eventual convergenceThe mechanisms create an operational contract. To use the system safely, I need to understand partition size, hotspot risk, consistency levels, repair completion, tombstone lifetime, compaction pressure and recovery bandwidth.
The most reusable lesson is that availability mechanisms do not remove work. They move work from the failed request into reconciliation and operations later.