MyRocks: Range Locking: RCU-based cache for the root node

Problem description

Benchmarks show that Range-Locking mode experiences a lot of contention on the
locktree's root node mutex.

This is because every lock acquisition goes as follows:

• Acquire the locktree's root node mutex.
• Compare the root node's range with the range we intend to lock
• Typically, the ranges do not overlap, so we need to go to the left or right child
• Acquire the mutex of the left(or right) child node
• Possibly do a tree rotation
• Release the root node mutex.

Then the process repeats for the child child node, until we either have found the node whose range overlaps with the range we intend to lock, or we have found the place where we insert the node.

Proposed solution

The idea is that most lock acquisitions do not actually need to modify the
root node. They could use an RCU mechanism to access it.

The tree will have a member variable:

class locktree { 

  bool root_rcu_enabled;

  ...

}

Fast-path reader will do this:

tree_node *get_child_with_rcu(lookup_key) {

  tree_node *res= nullptr;

  rcu_read_lock();

  if (locktree->root_rcu_enabled) {

    cmp = compare(lookup_key, locktree->root->key);

    if (cmp == LESS_THAN) {

      Get the mutex on locktree->root->left_child;

      res= locktree->root->left_child;

    }

    // if (cmp == GREATER_THAN) { same thing with right_child } 

  }

  rcu_read_unlock();

  return res;

}

If this function returns NULL, this means we need to touch the root node and so will retry using the locking.

tree_node *get_root_node() {

  // Stop the new readers from using the RCU

  root_rcu_enabled= false;

  // Wait until all RCU readers are gone

  rcu.synchronize_rcu();

  locktree->root->mutex_lock();

  // Here, can make modifications to the root node

  // When we are done,  release the mutex and enable the RCU

  locktree->root->mutex_unlock();

  root_rcu_enabled= true;

}

Other details

It is not clear if/how this approach could be extended to non-root nodes.