Sled: fully-cooperative, crash-proof tree node merge support

[spacejam]

• [x] detect node mergeable
  
  
  
  • not leftmost child in parent (index 0), detected in Tree::path_for_key
  
  
  • below size threshold or empty
  
  
• [x] install parent cooperative merge intention marker
  
  
  
  • left may split, making intention incorrect, difficult to reconcile, so skip left
  
  
  • Option<NonZeroPageId>
  
  
  • threads race to next step
  
  
• [x] install right child merge
  
  
  
  • cooperative left hint, no specific node necessary
  
  
  • threads race to next step
  
  
• [x] find left child
  
  
  
  • from parent, go to node with intended merge index - 1
  
  
  • from there, that node may have split, so seek forward until either:
    
    
    
    
    
    • find node pointing to right child merge, continue to left merge
    
    
    
    • find node beyond right child's hi key, indicating we lost races, continue to parent merge
    
    
    
  
  
• [x] install left child merge
  
  
  
  • continue to parent merge
  
  
• [x] install parent merge
  
  
  
  • clears intention
  
  
  • only the thread that performs this gets to free the right child afterward
  
  
  • it's ok to leak the orphan page if we crash right after installing parent merge, before freeing merged node
  
  
• [x] free right child

key tests to run continuously while implementing, need to be burned for 48 hours without issue before release:

• while [ $? -ne 1 ]; do cargo test parallel_iter --release -- --nocapture; done
• while [ $? -ne 1 ]; do cargo test crash --release -- --nocapture --ignored; done

[spacejam]

@spacekookie

[spacekookie]

Not sure if you can assign me if I'm not member of the repo? But if you can, feel free to do so.

And I assume that this requires #538 because otherwise we can't properly clean up the abort tags, right?

Or am I misunderstanding the scope of the implementation here? This was the first algorithm we talked about with the aborts and tagging them with db epoch IDs, right?

[spacejam]

@spacekookie no need for #538. Yesterday I worked out the above method which is fully non-blocking. The general principle is that every update does not block other updates, but is merely a signpost for any thread that reads it to try to complete the action.

(I use the term child and sibling interchangeably below)

So, the goal is to chain race conditions to end up in a correct state. The tricky bit is in the "find left child step" because the left sibling of the mergeable node may have split infinite times (and should be assumed to be continuously splitting until the installation of the parent merge (in which case it becomes fully fluid and may merge as well). But it's also possible that another thread was able to already merge the mergeable node into its left sibling, which is why we have to detect if we scan past the node-to-merge's hi key. If we find the left child, install left child merge that moves items from the mergeable node and adopts its hi key using an atomic PageCache::link (works like a CAS).

If at any point one of our CAS's doesn't work out, we should just bail out of the merge process, as we do in the Tree::recursive_split method. Because we leave markers for future threads to read and complete the operation, somebody else will be able to continue if we fail for any reason.

[spacejam]

The nice thing about being non-blocking and cooperative is it retains correctness even when you crash after any of the above operations, without needing any special cleanup of a lock or anything. The only risk is that if we crash after the parent merge, but before freeing the merged child, the child will become an orphan. But this is OK as it should be super rare and doesn't impact correctness.

[spacejam]

@spacekookie to get you started, I just pushed the branch tyler_merge_outline that just includes the fragment enum variants that could be used to complete the above algorithm.

[spacekookie]

Cool! I would suggest we meet in the office on monday afternoon or so, to walk through it on a whiteboard again.

I kinda get how it's supposed to work but I think I have some questions. But super excited to work on this already!

[spacejam]

This is implemented and "first pass" debugged in tyler_avoid_merge_on_page_read