Repository navigation
[lsm] Compaction permanently loses a re-inserted entry (put -> remove -> re-put of the same key/RID)Â #4942
Description
Severity: CRITICAL (delayed silent corruption after background compaction)
Location: index/lsm/LSMTreeIndexCompactor.java:163 and :218:
final Set<RID> rids = new LinkedHashSet<>();
...
rids.add(rid); // ADD ALSO REMOVED RIDS...The merge relies on the temporal order of the value stream (readers decide liveness by "last operation wins", LSMTreeIndexCursor.java:392-413). But LinkedHashSet.add() of an already-present element does not move it to the tail. The op stream ADD R, TOMBSTONE(-R), ADD R (an indexed property changed away and back across three commits, or any delete + re-insert of the same record/key) collapses to [R, TOMBSTONE(-R)]: the second ADD R keeps its oldest position. The compacted leaf is written in that order, so every subsequent read replays "insert then delete" and treats the key as deleted for R. The record silently disappears from the index while remaining in the bucket. Live (non-compacted) reads are correct, so this appears only after compaction runs.
Fix: preserve last-write order, e.g. if (!rids.add(rid)) { rids.remove(rid); rids.add(rid); }, or better fold per-RID state in temporal order and emit only the final state (also enables dropping resolved tombstones). Regression test: insert, delete, re-insert same key/record across commits, force compact(), then get() and full scan must return the record.
Filed from an internal engine deep-audit (2026-07). Traced to source; verify against current main before fixing and add a regression test.
Activity
fix(#4942,#4944): LSM compaction lost re-inserted keys; range scans t…
fix(#4945): thread deletedRIDs across pages so non-unique get() canno… (
lvca commentedon Jul 5, 2026
Fixed in #4968 (merged). Confirmed real and reproduced deterministically: with auto-compaction disabled and one controlled compaction merging ADD + tombstone + re-ADD of the same key/RID, the re-inserted entry vanished from the index (query by key returned nothing while the record existed).
Root cause exactly as traced: the compactor merges pages oldest to newest into an insertion-ordered set, while the reader treats the LAST position of an entry as the newest operation. A re-added RID kept its pre-tombstone position, so the tombstone ended up "newest" and won. Duplicates (re-added RIDs and repeated tombstones alike) now move to the end of the set, preserving last-write-wins.
Note for posterity: this was initially mis-triaged as not reproducible because the test harness's explicit
compactAll()was a silent no-op - a background auto-compaction held the COMPACTION_SCHEDULED status, soscheduleCompaction()/compact()returned false. The committed tests now disable auto-compaction on the database's own context configuration and assert both calls return true.fix(#4945): thread deletedRIDs across pages so non-unique get() canno… (