Details
-
Task
-
Status: Open (View Workflow)
-
Major
-
Resolution: Unresolved
-
None
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
Issue Links
- relates to
-
-
- Stalled
-
-
-
- Open
-
Activity
This shows RCU now is much more commonly used, but the %age of the operations that use the RCU is still too low.
Questions:
- Is this a fundamental limitation or there's a way to increase the number of lock acquisitions/releases that do not use the RCU?
Could it be that my idea about how often the root node needs to be modified is wrong?
Added counters to check how often this happens: range-lock-counters1-b.diff
range-lock-counters1.diff
and ran the benchmark.
no surprises so far...
Improved patch, run in c5.9xlarge (two runs with the patch, one without perf counters and one with):
threads orig range-locking range-locking-rcu range-locking-rcu-cntr
|
1 21916.79 22166.78 21960.01 21347.42
|
5 98125.35 90756.97 63205.76 61617.9
|
10 165994.26 143740.83 94505.42 93738.68
|
20 189590.09 154530.26 114082.09 113270.92
|
40 209484.58 145180.66 130328.97 129862.27
|
60 213205.54 140677.04 133218.07 132456.41
|
80 216881.11 138068.66 132357.3 131860.98
|
100 210547.05 137074.94 131686.54 130884.23
|
It is not as bad as before, but still it's worse than regular range locking 
.
Counters for the new patch:
https://docs.google.com/spreadsheets/d/1aApVWcYp9CogAUfho9wvH55-h4a0SkdKFAqJFNXQku0/edit#gid=0
At high number of threads, the number of operations that use the RCU read path (and don't acquire mutex on the root node) is about 90%. With previous patch, it was 50-70%.
If an operation (lock acquisition/release) couldn't use the RCU read path, it will get the root node's mutex. Then, it will examine the root node and arrive at one of these outcomes:
- 1. It doesn't need to modify the root node. It will release the mutex and move to the child. Note that this path doesn't prevent others from using RCU read path
- 2. It needs to modify (e.g. delete) the root node itself (or one of its direct children). This is counted in RCU_DISABLE_ROOT_HIT.
- 3. It needs to modify the root node due to doing re-balance operation on the child. This is counted in RCU_DISABLE_DUE_TO_REBALANCE.
One can see that RCU_DISABLE_DUE_TO_REBALANCE is relatively rare.
RCU_DISABLE_ROOT_HIT is also quite infrequent.
c5.2xlarge:
ubuntu@ip-172-31-17-220:~/range-locking-benchmark$ ./summarize-result.sh 105-origSERVER_DIR=mysql-5.6-origSYSBENCH_TEST=oltp_write_only.luaThreads, QPS1 17531.275 58527.5010 94065.1120 101323.1640 101602.4760 100858.5480 100453.83100 99408.72ubuntu@ip-172-31-17-220:~/range-locking-benchmark$ ./summarize-result.sh 105-range-locking-baseSERVER_DIR=mysql-5.6-range-lockingSYSBENCH_TEST=oltp_write_only.luaThreads, QPS1 17777.905 54689.0610 76271.5620 81926.3340 84046.3060 83086.2580 80931.29100 78644.12ubuntu@ip-172-31-17-220:~/range-locking-benchmark$ ./summarize-result.sh 104-rcu-relSERVER_DIR=mysql-5.6-range-locking-rcuSYSBENCH_TEST=oltp_write_only.luaThreads, QPS1 16099.385 33605.9110 29440.7720 29464.2340 28729.2160 28841.0980 29461.01100 30389.78