[CASSANDRA-19617] Paxos may re-distribute stale commits that predate a collectable tombstone

• Type: Bug
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 4.1.6, 5.0-rc1, 5.0, 5.1-alpha1
• Component/s: Consistency/Coordination
• Bug Category: Correctness - Recoverable Corruption / Loss
• Severity: Critical
• Complexity: Byzantine
• Discovered By: Diff Testing
• Platform: All
• Since Version: 4.1.0

Source Control Link

https://github.com/apache/cassandra/commit/53b06453b7dea147ef6369765e0b7ac7fb0990fd

Test and Documentation Plan

Patch includes tests

• Assignee: Benedict Elliott Smith
• Reporter: Benedict Elliott Smith

Authors

Benedict Elliott Smith

Reviewers

Blake Eggleston

• Created: 03/May/24 17:13
• Updated: 18/Jul/24 21:11
• Resolved: 11/Jun/24 13:37

Description

Note: this bug only affects {{paxos_state_purging:

{gc_grace, repaired}

}}, i.e. those introduced alongside Paxos v2.

There are two problems:
1) Purging is applied only on compaction, not on load, which can lead to very old commits being resurfaced in certain circumstances
2) PaxosPrepare does not filter commits based on paxos repair low bound

This permits surprising situations to arise, where some replicas purge a stale commit and all newer commits, but due to compaction peculiarities some other replica may purge only the newer commits, leaving a stale commit in some compaction "purgatory"[1] to be returned to reads indefinitely.

So long as there are no newer commits, the paxos coordinator will see this commit is not universally known and redistribute it - no matter how old it is. This can permit an insert to be reapplied after GC grace has elapsed and the tombstone has been collected.

For proposals this is not a problem, as we correctly filter proposals based on the last paxos repair time. This also does not affect clusters with the legacy (and default) paxos state purging using TTL. Problem (1) only applies also to the new gc_grace compatibility mode for purging.

[1] Compaction purgatory can arise for instance because paxos purging allows whole sstables to be erased quite effectively, and if this is able to ordinarily prevent sstables being promoted to L1, then if for some abnormal reason sstables reach L1 (e.g. repairs being disabled for some time), those that collect may remain uncompacted for an extended period without purging being applied.

Issue Links

• links to: GitHub Pull Request #3289