Phase 5: Compaction Strategies & Tombstone Cellular Pathology¶
Audience: Principal Distributed Systems Architect & Storage Engine Specialist
Source References:src/java/org/apache/cassandra/db/compaction/,src/java/org/apache/cassandra/db/rows/Cell.java
1. The LSM Compaction Engine¶
Because SSTables are immutable, updates and deletes accumulate across hundreds of distinct files over time. Without maintenance: - Read queries would have to scan hundreds of files on disk, collapsing read throughput. - Obsolete overwritten data and tombstones would consume 100% of physical storage.
Compaction is the asynchronous process of merging multiple small SSTables into a single new SSTable, resolving duplicate cell versions, and purging tombstones.
2. Compaction Strategies Compared¶
┌────────────────────────────────────────────────────────────────────────┐
│ 1. Size-Tiered Compaction Strategy (STCS) │
├────────────────────────────────────────────────────────────────────────┤
│ - Best For: Write-heavy logging / ingestion pipelines │
│ - Algorithm: Groups SSTables into size tiers (buckets of ~4 tables) │
│ - Flaw: High Space Overhead! Compacting a 500GB SSTable requires │
│ 500GB of FREE disk headroom (Must keep disk usage < 50%!). │
└────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────┐
│ 2. Leveled Compaction Strategy (LCS) │
├────────────────────────────────────────────────────────────────────────┤
│ - Best For: Read-heavy, random update workloads │
│ - Algorithm: Fixed-size 160MB SSTables arranged in levels (L0, L1, L2) │
│ - Invariant: In L1 and higher, SSTables have ZERO overlapping tokens! │
│ - Superpower: 90% of reads hit at most ONE SSTable on disk! │
│ - Space Overhead: Minimal (requires only ~10% free disk headroom). │
└────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────┐
│ 3. Time-Window Compaction Strategy (TWCS) │
├────────────────────────────────────────────────────────────────────────┤
│ - Best For: Time-series, IoT, and TTL-expiring append-only data │
│ - Algorithm: Groups SSTables into discrete time windows (e.g. 1 day) │
│ - Superpower: Once a historical window expires past TTL, Cassandra │
│ drops the entire SSTable file with a single O(1) OS unlink() call, │
│ completely bypassing compaction I/O and tombstone generation! │
└────────────────────────────────────────────────────────────────────────┘
3. Tombstone Cellular Anatomy & Lifecycle¶
In an LSM-Tree database, a delete cannot delete data from existing SSTables because SSTables are strictly immutable.
Instead, a delete is physically written as a new mutation called a Tombstone:
Anatomy of a Row Deletion Tombstone:
┌──────────────────────────────────┬─────────────────────────────────────┐
│ MarkedForDeleteAt (Microseconds) │ LocalDeletionTime (Unix Seconds) │
│ 1716382050000000 (Timestamp) │ 1716382050 (For gc_grace_seconds) │
└──────────────────────────────────┴─────────────────────────────────────┘
3.1 The Retention Window: gc_grace_seconds¶
Configured per table (default: 864,000 seconds = 10 days):
- Tombstones cannot be purged during compaction until LocalDeletionTime + gc_grace_seconds < CurrentTime.
- Why 10 Days? To give administrators time to run nodetool repair across the cluster. If a replica is offline for 3 days, it must receive the tombstone during repair. If the tombstone were purged earlier, the offline node would never know the record was deleted!
4. The Two Catastrophic Tombstone Pathologies¶
4.1 Pathology 1: The Tombstone Avalanche (TombstoneOverwhelmingException)¶
When an application deletes records frequently (e.g. queue pattern where items are inserted, processed, and deleted):
1. A client query executes: SELECT * FROM job_queue WHERE status = 'PENDING' LIMIT 10.
2. Cassandra scans the Memtable and SSTables.
3. It encounters 200,000 tombstones for deleted jobs before finding 10 live jobs.
4. It must load all 200,000 tombstones into JVM heap memory to verify timestamps.
Tombstone Safety Guardrails in cassandra.yaml:
tombstone_warn_threshold: 1000 # Logs WARN message in system.log
tombstone_failure_threshold: 100000 # KILLS QUERY IMMEDIATELY!
tombstone_failure_threshold is exceeded:
org.apache.cassandra.exceptions.TombstoneOverwhelmingException:
Scanned over 100001 tombstones in job_queue; query aborted to prevent JVM heap exhaustion!
4.2 Pathology 2: The Zombie Data Resurrection Disaster¶
Consider a 3-node cluster (\(N = 3\)):
1. Node C goes offline for 12 days (hardware maintenance).
2. On Day 2, a client deletes user_id = "bob". A tombstone is written to Node A and Node B.
3. On Day 11, compaction runs on Nodes A and B. Because gc_grace_seconds (10 days) has passed, the tombstone is purged from disk on Nodes A and B.
4. On Day 12, Node C boots back up!
5. Node C still contains the old live record for "bob" (written before the delete).
6. A read query arrives with QUORUM. The coordinator compares Node A (no data) with Node C (contains "bob" with old timestamp).
7. Because Node A's tombstone is gone, Node C's data appears legitimate.
8. Result: "bob" is resurrected into the database! The deleted data reappears out of thin air!
Zombie Resurrection Disaster Sequence:
[Node A: Tombstone Purged] [Node B: Tombstone Purged] [Node C Revives: Stale Data Alive!]
│ │
└─────────────────────── Read Quorum ──────────────────────┘
│
▼
Stale Data from Node C Resurrected!
The Golden Operational Law:¶
[!CAUTION] If any node has been offline or partitioned longer than
gc_grace_seconds, NEVER start the Cassandra daemon directly. You MUST wipe the node's/var/lib/cassandra/data/directory and perform a clean cluster bootstrap to prevent zombie resurrection!