Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 30 ยท How Cassandra Works Inside

The read path, bloom filters and compaction

Follow a Cassandra read through the memtable and SSTables, learn how bloom filters skip files, and compare STCS, LCS and TWCS compaction strategies.

The write path made writes cheap by never changing files in place. The bill arrives at read time: the newest version of a row may be in the memtable, in a recent SSTable, or in an old one, and the pieces of one partition can be scattered across several files. A read has to find and merge them. Cassandra keeps this fast with two tools: bloom filters, which let it skip files that cannot contain the key, and compaction, which merges files in the background so that fewer remain.

This lesson walks through a read on a single node, then builds a bloom filter and a compaction in JavaScript. As always, the stand-ins are teaching models: they show the mechanism with toy data, and the numbers they print are not measurements of the real database. Real Cassandra's configuration is shown in read-only blocks.

The read path on one replica

flowchart TD
    R["Read for partition P"] --> M["Check the memtable"]
    R --> S["For each SSTable"]
    S --> BF{"Bloom filter:<br/>maybe contains P?"}
    BF -- "no" --> SKIP["Skip this file"]
    BF -- "maybe" --> IDX["Look up P in the index<br/>(key cache helps)"]
    IDX --> DATA["Read the data from the file"]
    M --> MERGE["Merge all pieces:<br/>newest timestamp wins per cell"]
    DATA --> MERGE
    MERGE --> OUT["Return the result"]

A read collects candidate pieces from the memtable and from every SSTable that might hold the partition, then merges them.

For each SSTable that could hold the partition, Cassandra first asks the bloom filter. If the answer is "no", the file is skipped without any disk I/O. If it is "maybe", Cassandra uses the partition index to find where the partition begins and reads it. The key cache remembers recent index lookups, and the operating system's page cache holds popular file pages. Finally all pieces are merged cell by cell, and for each cell the newest write timestamp wins. This merge-by-timestamp rule is why a newer value (or a tombstone) in a recent SSTable hides older data in an older one.

If a partition has been updated many times over many days, it can appear in a dozen files. More files mean more work per read, and that is the problem compaction solves.

Bloom filters

A bloom filter is a small bit array plus several hash functions. To add a key, hash it several times and set the bits at those positions. To test a key, hash it the same way: if any of those bits is 0 the key was definitely never added; if all are 1 the key is probably there. So a bloom filter has no false negatives, but it can have false positives, which only cost one wasted file lookup.

Each SSTable has its own bloom filter, and the bigger the filter, the fewer false positives. Cassandra lets you tune this per table:

SQL
ALTER TABLE shop.orders WITH bloom_filter_fp_chance = 0.01;

A lower chance means a bigger filter in memory. The default is a small value tuned for typical workloads, and the right setting is a memory-versus-I/O trade-off.

Stand-in 1: build a bloom filter and measure it

This program builds a filter with 100 keys and tests 10,000 keys that were never added, counting how many it wrongly says "maybe" to, for different filter sizes. The hash function is a simple FNV-1a variant, enough for a demonstration.

JS A bloom filter and its false positives

Press Run (or Ctrl + Enter) to see the console output here.

No output.

More bits per key means far fewer false positives, and the number of false negatives is always zero. That asymmetry is what makes the filter safe to use for skipping files.

Tombstones and shadowing during reads

A delete in Cassandra is a write of a tombstone with a timestamp. During a read, if the newest piece for a cell is a tombstone, the cell counts as deleted, even though older SSTables still contain the old value. The tombstone shadows the data beneath it. This is why the old files cannot simply be thrown away: the tombstone has to survive until every older copy has been merged and purged. Deletes, TTL and tombstones covers the consequences in depth.

Compaction

Compaction reads several SSTables and writes one new, merged SSTable, then deletes the inputs. While merging, it keeps only the newest version of each cell, drops values hidden by tombstones, and drops tombstones that are old enough to be safe to remove. The result is fewer files, less wasted space and faster reads. It costs disk and CPU in the background.

Stand-in 2: reads before and after compaction

The next program builds four SSTables with overlapping keys, each with its own bloom filter. It counts how many SSTables a read had to open, with and without bloom filters, shows a tombstone hiding a deleted key, and then compacts everything into one table. Remember that the bloom check is probabilistic, so a few absent keys may still open a file.

JS Opening fewer files: bloom filters and compaction

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Compaction shrank four files and 131 stored cells into one file with 75. Looking up all 80 keys opened 131 files before and only 77 after (one per surviving key, plus a couple of bloom false positives on the five deleted keys). Deleted keys vanished completely because the toy purges tombstones. Real Cassandra only purges a tombstone when it is older than gc_grace_seconds and no other SSTable might still hold data it hides.

Compaction strategies

You pick the strategy per table. The right choice depends on the workload.

SQL
ALTER TABLE iot.readings_by_sensor_day
WITH compaction = {
  'class': 'TimeWindowCompactionStrategy',
  'compaction_window_unit': 'DAYS',
  'compaction_window_size': 1
};
  • STCS (SizeTieredCompactionStrategy) is the default. When several SSTables of similar size accumulate (four by default), it merges them into one bigger file. It is cheap on write I/O and fits write-heavy tables. The downsides are that a partition can still be spread over many files, and a big merge temporarily needs a lot of free disk space.
  • LCS (LeveledCompactionStrategy) organizes SSTables into levels, each about ten times larger than the one before. Within a level the files do not overlap, so a read needs to check only a few files. It suits read-heavy workloads with many updates and costs more write I/O.
  • TWCS (TimeWindowCompactionStrategy) groups files by write-time window and compacts within a window. When every row in an old window has expired through TTL, the whole file is deleted. It is made for time series like the bucketed readings you designed earlier, and it works badly if you update or delete old rows.

Newer Cassandra releases also add a unified strategy (UCS) that can behave like STCS or LCS depending on its settings. Check the documentation of your version before relying on it.

You can watch and trigger the work with nodetool compactionstats and nodetool compact (rarely a good idea on a production table); operations are covered in Drivers, nodetool and production pitfalls.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A bloom filter answers 'no' for a key. What does that guarantee?

    Bloom filters have no false negatives. A 'no' lets Cassandra skip the file without reading it.
  2. 2. When two SSTables hold different values for the same cell, which one does a read return?

    Reads merge all pieces and each cell resolves to the version with the latest timestamp, and a tombstone is just such a version.
  3. 3. Which compaction strategy is designed for TTL'd time-series data written in time order?

    TWCS keeps files per time window and drops a whole file once all its data has expired.
  4. 4. What is the trade-off of lowering bloom_filter_fp_chance?

    A lower false-positive chance needs a bigger bit array per SSTable, which costs memory but saves disk reads.

Summary

  • A read checks the memtable and every SSTable that might hold the partition, then merges the pieces; the newest timestamp wins.
  • Bloom filters skip SSTables that definitely do not contain the key; they can produce false positives but never false negatives.
  • A tombstone shadows older data and must be kept until it is safe to purge.
  • Compaction merges SSTables to reduce files, space and read work. STCS suits write-heavy loads, LCS read-heavy loads, and TWCS expiring time series.
  • The JavaScript stand-ins illustrate the mechanism; real thresholds and file formats are Cassandra's own.

Next: Replication and tunable consistency.