Re: Race condition in b-tree page deletion

On 10.11.2013 01:47, Robert Haas wrote:
> I think we've tried pretty hard to avoid algorithms where the maximum
> number of lwlocks that must be held at one time is not a constant, and
> I think we're in for a bad time of it if we start to deviate from that
> principal. I'm not sure what to do about this problem, but I think
> locking N levels of the tree at once, where N can be as large as the
> tree is deep, is probably a bad plan, whether the number of locks
> required is N or 3N.

I think I found a solution that accomplishes that. It's actually not
that complicated:

Like we currently do, first climb up the tree to check that it's safe to
delete, ie. the downlink in the first non-empty parent is not the
rightmost entry. But when we reach the level where the parent is
non-empty - I'll call that the "topmost" parent - we keep that page
locked. The leaf page is kept locked while we climb.

This is enough to plug the race condition. As long as we hold a lock on
the topmost parent containing the downlink to the branch of pages we're
about to delete, it cannot become the rightmost entry. And as long as we
hold a lock on the leaf page, no new insertions can happen on any of the
internal pages in the branch, as insertions to internal pages only
happen when a child is split. However, the rest of the algorithm needs
to be slightly modified, as we cannot re-lock the lower-level pages
until we release the lock on the topmost page, to avoid deadlock.

So at this point, we hold two locks: the leaf page, and the topmost
parent containing the downlink to the branch we're deleting. Next, we
remove the downlink from the topmost parent, and mark the leaf page as
half-dead in one atomic operation. Also, a pointer to the highest
internal page in the branch we're deleting - the one the removed
downlink pointed to - is put on the leaf page. We can now release the locks.

At this point, searches and inserts work fine. The leaf page has been
marked as half-dead, so any insertions to the deleted page's keyspace
will go to its right sibling. The downlink is to the top of the branch
is gone, so even if the right sibling is split many times, any keys in
the transferred keyspace that propagate to the higher levels won't be
out-of-order.

All that is left is to unlink the all the lingering pages in the branch
we're deleting from their left and right siblings. This can be done at
any later time, and if we error out or crash for some reason, next
vacuum that comes along can finish the job. This is done one level at a
time. Lock the leaf page, and the internal page the leaf page points to,
and the internal page's left and right siblings (in the right order, not
this order). Change the left and right sibling's right- and left-links,
mark the internal page as deleted, and update the pointer in the leaf
page to point to the child of the deleted internal page. Then recurse to
the child, until we reach the leaf level.

This has the nice extra property that we don't need the
incomplete-action tracking in WAL recovery. I'd like to get rid of that
anyway.

I'm not sure what to do about stable branches. This could be
back-patched, with the caveat that this introduces new WAL record types
so standbys need to be upgraded before the master. But given the lack of
field reports in the ten years this race condition has existed, I'm not
sure it's worth the hassle.

- Heikki