Skip to content

B-Tree merge frees the emptied page outside the transaction: rolling back deletes leaves the committed tree pointing at a freed page #233

Closed

Description

@mrdevrobot

Summary

When a delete makes two B-Tree nodes merge, BTreeIndex.MergeWithSibling frees the emptied page with _storage.FreePage(rightNodeId), which takes effect on disk immediately, outside the transaction. If that transaction is then rolled back, the committed tree still points at the freed page. Once the page is reused, or after a reopen, the index is corrupt.

Repro

Found by an independent review of #232 with a randomized probe, and confirmed on the code in main (BTreeIndex.cs ~1707 on main, ~1883 on the #232 branch).

  • Setup: page sizes 4/8/16 KB and four key mixes (12 combinations).
  • Steps: build a tree, run a transaction that deletes enough entries to merge nodes, roll that transaction back, then reopen the database.
  • Result: every combination failed. After the reopen, the committed tree had a child pointer to page 0.
  • Controls: the same probe with no rollback, or with a rolled-back transaction that only inserts, passed every seed.

Expected

A rolled-back transaction leaves the index exactly as it was. Freeing a page that a transaction stops using must take effect only when that transaction commits; on rollback, the page stays in use.

Notes

  • Free page queue: pages freed inside a transaction should go through the transaction, like page writes, for example by queuing the free until commit. Compare the deferred free of pages with a WAL image (fix(storage): don't reuse freed pages that still have a WAL image (#168) #169) and CollectionIndexManager.DropIndex.
  • Other free paths: check the other FreePage calls on B-Tree delete paths (root collapse, internal merges) and in the vector and spatial indexes.
  • Allocation leak: pages allocated by a rolled-back split are not reclaimed either. That is a leak, not a corruption, and is related but separate.

Activity

  1. added this to the 5.3.0 milestone on Oct 15, 2026
  2. added
    bugSomething isn't working
    severity/criticalData loss, corruption, or silently wrong results in common use
    priority/P0Fix before anything else; blocks the next release
    area/indexingB-Tree and secondary indexes, index lifecycle
    on Oct 15, 2026
  3. moved this from Todo to In Progress in BLiteon Oct 16, 2026
  4. moved this from In Progress to Done in BLiteon Oct 16, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    area/indexingB-Tree and secondary indexes, index lifecyclebugSomething isn't workingpackage/coreAffects BLite.Corepriority/P0Fix before anything else; blocks the next releaseseverity/criticalData loss, corruption, or silently wrong results in common usetriage

    Type

    No type

    Projects

    • Status
      Done

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions