post-mortem · nexus_db · C++17 · 3 pages
The Delete That Did Not Delete
the flush path dropped tombstones it judged redundant, using a definition of redundant that only looked at the memtable. delete a key that already reached disk and the deletion evaporated.
abstract
Under an entirely ordinary sequence of operations, deleted keys came back. The cause was an optimization in the flush path that discarded tombstones it judged redundant, using a definition of redundant that considered only memory and ignored every record already written to disk.
the symptom
Delete a key and read it back immediately and the delete held. Write the key, flush, delete it, flush again, and the old value returned. Reads served from memory were right; reads served after the second flush were wrong, which narrows the fault to the flush path without any further work.
root cause
The flush loop asked whether a tombstone shadowed any live value in the memtable it was currently writing. If not, it dropped the tombstone to save space. That is a correct test of the wrong question: what matters is whether the tombstone shadows anything in the whole tree, and almost all of the tree is on disk, in files the loop never consults.
the fix
Flush unconditionally. Tombstones are still collected, but only during compaction, and only when the merge consuming them also consumes every older record for that key. The rule this generalizes to: the component that deletes information must be the component that can see all of it. Flush sees one memtable and was never entitled to that decision.