Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-21574

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

    XMLWordPrintable

Details

    Description

      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.

      Attachments

        1. range-lock-counters1.diff
          2 kB
        2. range-lock-counters1-b.diff
          6 kB
        3. rcu4a.diff
          5 kB
        4. rcu4b.diff
          17 kB
        5. results-feb3.tgz
          41 kB
        6. screenshot-1.png
          screenshot-1.png
          76 kB
        7. screenshot-2.png
          screenshot-2.png
          92 kB
        8. screenshot-3.png
          screenshot-3.png
          30 kB
        9. screenshot-4.png
          screenshot-4.png
          45 kB

        Issue Links

          Activity

            People

              psergei Sergei Petrunia
              psergei Sergei Petrunia
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.