Cassandra 3.11.4 corrects the order of tombstone collection

Deleting data in Cassandra creates work that a later maintenance operation must finish. A tombstone has to suppress older values before compaction can discard the deletion itself. That makes the order in which maintenance visits files significant. In Cassandra 3.11, a comparator used by garbage collection put SSTables in the opposite order from the one the operation needed. Rewriting the files could therefore leave the tombstones in place.

The 3.11.4 release metadata dates the release to 11 February 2019. Its most instructive correction is CASSANDRA-14870, which connects ineffective garbage collection with timestamp ordering in leveled compaction. The report describes a maintenance operation that could run without achieving its intended reclamation. That is a useful distinction when interpreting a successful administrative command.

I find Cassandra compelling when an application needs active-active operation at scale. The storage machinery behind that capability deserves close attention. This patch is interesting because it exposes a dependency between a small implementation detail and an operator's expectation that deleted data will eventually stop occupying storage.

Why the oldest file has to come first

The issue describes nodetool garbagecollect as an operation intended to work from the oldest SSTable toward the newest. An older file may contain a value that a tombstone in a newer file deletes. Removing that obsolete value first makes it possible for a subsequent pass over the newer file to discard the tombstone, subject to the remaining safety conditions.

The comparator named SSTableReader.maxTimestampComparator sorted files in the other direction. The report traces that ordering through earlier changes, CASSANDRA-13776 and CASSANDRA-14010. A caller that needed oldest-first processing could no longer obtain the required sequence simply by using the shared comparator. The bug report states that this prevented garbage collection from purging tombstones.

Consider an old value and a newer deletion stored in different SSTables. Visiting the deletion first leaves the older value present elsewhere. Retaining the deletion is then necessary to keep that value from becoming visible. Visiting the old file afterward can remove the shadowed value, but the pass over the deletion's file has already happened. This example explains the dependency described in the report without assuming that every retained tombstone has the same cause.

The patch also incorporates the leveled-compaction ordering correction from CASSANDRA-14099. In the issue's November discussion, Branimir Lambov explains that both changes require the same order adjustment. The connection matters because a comparator is shared implementation policy. Its name alone does not establish whether a particular caller needs ascending or descending timestamps.

Tombstone age is only one condition

The compaction documentation shipped with 3.11.4 explains why elapsed time cannot determine reclamation on its own. Cassandra retains tombstones so that replicas which missed a deletion can learn about it during repair. Removing the deletion record while an older value remains on a replica can allow that value to return.

The table setting gc_grace_seconds establishes a retention interval. The documented default is 864000 seconds, or ten days. Expiry of that interval makes a tombstone eligible for removal. It does not schedule its immediate deletion, and it does not prove that all older data has disappeared. Compaction still needs enough information about overlapping data to establish that removal is safe.

The same documentation describes the relationship between SSTables containing a partition and older data covered by its tombstone. Files containing relevant older values must participate in the necessary compaction work. Data known to be newer than a tombstone does not create the same dependency, because that tombstone cannot delete it. Timestamp ordering therefore affects which reclamation opportunities a maintenance pass can reach.

This is why reducing the grace interval does not repair the comparator bug. Changing a retention setting cannot reverse the sequence in which an operation processes files. I prefer to keep those explanations separate when assessing disk usage. A retention policy and an implementation defect can produce similar visible symptoms while requiring different remedies.

Compaction has several independent divisions

The release's versioned changelog also lists severe concurrency issues in size-tiered, date-tiered and time-window compaction. It includes a correction to synchronizing access to LifecycleTransaction during streaming. These entries broaden the significance of the maintenance release beyond a single administrative operation, although they do not establish that every compaction strategy suffered the same failure.

The versioned documentation explains that incremental repair separates repaired and unrepaired SSTables into different compaction strategy instances. It also describes separate instances for data directories. Consequently, compaction does not see a node's entire collection of files as one freely mergeable set. Older data in another relevant group can affect the ability to discard deletion records.

Leveled compaction introduces another ordering problem. Its levels limit overlap above level zero, and selecting files for compaction must account for overlapping files in the destination level. Timestamp selection and token overlap answer different questions. The first helps choose work in a useful sequence, while the second preserves the layout that limits the files a read must inspect.

The practical value of 3.11.4 is that it corrects maintenance behavior within these existing rules. It does not change the meaning of deletion or remove the need for repair. A garbage-collection pass still operates within the retention and overlap constraints documented for the release. Correct oldest-first processing lets that pass remove obsolete values before reconsidering the newer tombstones that suppressed them.