Facebook needed a storage system that could handle huge write volumes across commodity machines without depending on a single master or assuming that machines would stay healthy. The immediate problem was Inbox Search, which had to store and index data for more than 100 million users while continuing to operate as machines, disks, and network links failed.
Cassandra was their answer: a decentralized structured storage system designed around high write throughput, low-latency access, incremental scaling, and failure as a normal operating condition. It combines ideas from Dynamo, Bigtable, distributed hash tables, and log-structured storage into one system.
The interesting part isn't any one algorithm. It's how Cassandra connects partitioning, replication, gossip, failure detection, and a write-optimized storage engine so that adding machines or losing machines doesn't require taking the database offline.
The problem: storage that keeps working when machines don't
At Facebook's scale, a storage system cannot treat failure as a rare event. There are always machines being restarted, disks becoming unavailable, networks becoming unreliable, and new machines being added.
Cassandra was designed around a few practical requirements:
High write throughput
Low-latency reads
No single point of failure
Incremental scaling
Automatic distribution and replication of data
Operation on commodity hardware
The original workload was Facebook Inbox Search. The system stored indexes for users and needed to support queries such as finding messages containing a particular term or messages exchanged with a particular person.
This workload favored a storage system that could write enormous amounts of structured data efficiently without requiring the relational features of a traditional database.
Cassandra therefore deliberately chose a simpler model: distribute data across many machines, replicate it, and let the application structure its data around the queries it needs to perform.
A simple data model for a distributed system
Cassandra's data model is inspired by Google's Bigtable. At its core, it is a distributed multidimensional map:
Row Key → Column Family → Columns
A row is identified by a key, and each row contains columns grouped into column families. Cassandra also supports super columns, which provide another level of grouping.
The important part is that Cassandra does not try to behave like a relational database. There are no joins or complex relational transactions in the core model. Instead, the application decides how information should be organized based on how it will be accessed.
For example, Inbox Search can organize a user's row around the terms appearing in their messages, making a query for a particular word a direct lookup rather than an expensive distributed operation.
Columns can also be ordered by name or by time, which is useful for workloads where recent data needs to be retrieved efficiently.
The API is intentionally small: insert(...) || get(...) || delete(...)
That simplicity is deliberate. Cassandra wants the distributed storage layer to do a few things extremely well rather than provide every feature of a traditional database.
Spreading data across the cluster: consistent hashing
Once there are hundreds of machines, the first question is obvious:
which machine should store a particular key?
Cassandra uses consistent hashing to partition the keyspace. Keys and nodes are mapped onto a logical ring, and a key belongs to the node responsible for the corresponding range.
This avoids the problem with a simple hash(key)%N approach. If the number of nodes changes, modulo hashing can move a huge fraction of the data. Consistent hashing limits the amount of data that needs to move when machines join or leave.
But Cassandra goes further.
A real cluster contains machines with different capacities. Giving every machine one arbitrary section of the ring can leave some nodes overloaded while others sit mostly idle.
Cassandra therefore monitors load and can move nodes around the ring to balance the distribution. A new node can also be placed so that it takes over part of an existing range rather than requiring a complete redistribution of the dataset.
This makes scaling incremental: add a machine, move part of the data to it, and continue serving requests while the cluster grows.
Replication: don't let one machine own your data
Partitioning tells Cassandra where a key belongs. Replication determines how many machines should have a copy.
Each key is replicated across multiple nodes. Cassandra supports different replication strategies, including rack-aware and datacenter-aware placement.
Why does that matter?
Suppose three replicas all happen to be in the same rack. A rack-level failure can take all three copies down at once.
By spreading replicas across failure domains, Cassandra can continue serving data even when an entire rack or datacenter becomes unavailable.
The system also allows different consistency levels for reads and writes. A write can be sent to multiple replicas, while a read can query multiple replicas and use the latest response.
This gives applications control over the tradeoff between latency, consistency, and availability instead of forcing one policy on every workload.
Cassandra's replication model is therefore less about "make three copies" and more about put the right copies in the right failure domains and make them available without requiring every replica to be healthy.
Who is alive? Gossip and failure detection
A decentralized database still needs to know what the cluster looks like.
Cassandra uses a gossip protocol for membership information. Nodes periodically exchange information with other nodes, and that information spreads through the cluster without requiring a central membership server.
That solves one problem but creates another:
how do you distinguish a dead node from a slow node?
Cassandra uses an accrual failure detector, based on the Φ failure detector. Instead of returning a simple alive or dead result, it produces a suspicion level based on how unusual the node's communication pattern has become.
A node that has stopped responding for longer than normal becomes increasingly suspicious.
This is useful because distributed systems cannot reliably distinguish every network delay from an actual machine failure. A fixed timeout can be too aggressive in one environment and too slow in another.
The combination of gossip and accrual failure detection gives Cassandra a decentralized way to answer two constantly changing questions:
who is part of the cluster, and which members currently appear unhealthy?
The storage engine: make writes cheap
Cassandra's most important implementation decision is its log-structured storage engine.
A write first goes into a commit log for durability and then updates an in-memory data structure. When enough data accumulates in memory, Cassandra flushes it to disk as an immutable file.
The important word is immutable.
Cassandra does not constantly modify existing disk structures in place. Instead, it creates new files and later merges them through compaction.
That makes the common write path mostly sequential:
Write → Commit Log → Memory → Immutable Disk File → Compaction
Sequential writes are much cheaper than constantly performing random disk updates, particularly for workloads dominated by writes.
But immutable files create an obvious read problem: if the same key can exist in several files, Cassandra needs to know which files are worth checking.
This is where Bloom filters come in.
Each data file maintains a Bloom filter that can quickly tell Cassandra that a key definitely does not exist in that file. If the filter says the key might exist, Cassandra performs the actual lookup.
Cassandra also uses indexes to avoid scanning large rows when a requested column is located deep inside them.
So the storage engine is built around a deliberate tradeoff:
make writes sequential and cheap, then use indexing, Bloom filters, and background compaction to keep reads efficient.
Compaction: keeping immutable files under control
The downside of immutable files is that they accumulate.
If Cassandra keeps flushing memory to disk, a single key might eventually exist in many different files. Searching all of them would make reads progressively worse.
Cassandra solves this through compaction.
Multiple sorted files are merged together into a larger file, similar to a merge-sort operation. During this process, obsolete versions of data can also be discarded.
Compaction runs in the background, so normal reads and writes can continue while storage is reorganized.
This gives Cassandra an important property: the write path doesn't need to wait for expensive disk reorganization. The system can accept new writes quickly and let background work clean up the storage layout later.
The tradeoff is that compaction consumes disk I/O and CPU. A write-optimized storage engine therefore isn't free; it shifts some of the cost into background maintenance.
That pattern shows up in many modern storage engines: optimize the hot path, then perform expensive organization asynchronously.
What happens when a new node joins?
Scaling a distributed database isn't just about updating a membership list. A new node needs actual data.
When a node joins Cassandra, it is assigned a position in the ring and takes responsibility for part of the keyspace. Existing nodes then transfer the relevant data to it.
This process is called bootstrapping.
The important property is that Cassandra can perform this redistribution while the existing cluster continues serving requests. The new machine gradually acquires its share of the data rather than requiring the entire database to be rebuilt.
The same philosophy applies to failures.
If a node temporarily disappears, Cassandra doesn't need to immediately rebuild the entire dataset. Replication allows other nodes to continue serving requests, while the failed node can later recover and catch up.
This makes cluster membership a continuous process rather than a rare migration event:
Node joins → receives a range → streams data
Node fails → replicas continue serving
Node returns → catches up
That is what makes Cassandra suitable for environments where machines are constantly being added, removed, repaired, and replaced.
Why this paper still matters
Cassandra is not based on one revolutionary idea. It is a carefully assembled collection of distributed-systems techniques.
Consistent hashing handles partitioning. Replication handles machine and datacenter failures. Gossip distributes membership information. Accrual failure detection handles uncertainty around node failures. Commit logs provide durability. Immutable files and sequential writes optimize the write path. Bloom filters and indexes keep reads practical. Compaction keeps the storage engine manageable.
The deeper lesson is that a distributed database is a collection of failure-management mechanisms disguised as a database.
Every seemingly simple question becomes harder at scale:
What machine owns this key?
What happens when it disappears?
Where should its replicas live?
How does a new machine get its data?
How do you detect a failed machine without mistaking a slow network for a dead server?
How do you write millions of records without turning the disk into a random-I/O bottleneck?
Cassandra answers these questions by favoring decentralization, incremental scaling, high write throughput, and eventual convergence over the stronger coordination guarantees of a traditional relational database.
The system was originally built for Facebook's Inbox Search, but the architecture became much more broadly influential. Its combination of Dynamo-style distribution and replication with a Bigtable-inspired data model and log-structured storage helped establish the design vocabulary behind modern distributed wide-column databases.
Key takeaways: consistent hashing distributes the keyspace, replication protects against failures, gossip and accrual failure detection keep the cluster aware of its changing state, and a log-structured storage engine turns heavy write workloads into efficient sequential I/O. The bigger idea is that Cassandra scales not by making one machine more powerful, but by making the cluster itself resilient to machines constantly joining, leaving, and failing.
Related reading
Dynamo: Amazon's Highly Available Key-value Store
Bigtable: A Distributed Storage System for Structured Data
The Google File System
Consistent Hashing and Random Trees
The φ Accrual Failure Detector
