NumLock: Towards optimal multi-granularity locking in hierarchies

We study multi-granularity locking in hierarchies. Existing popular mechanisms for multi-granularity locking work on two extremes: fine-grained locking which maximizes concurrency, and coarse-grained locking which minimizes the locking cost. Between the two extremes, there exist several pareto-optimal options which provide a trade-off between the concurrency cost and the locking cost. These options are captured under multi-granularity locking (MGL) protocol, but there exists no methodical way to choose a good MGL option. In this work, we present a locking technique, NumLock, which chooses optimal locking combination to serve MGL requests. NumLock works in two phases: first, it generates few pareto-optimal MGL options and second, it quickly analyzes these options to report the optimal one. We propose a greedy algorithm to generate a subset of the pareto-optimal options. We further improve the concurrency by abstracting the non-planar hierarchy as logical planar sub-hierarchies using multiple intervals. Our study reveals that the lock manager must explore various MGL options for achieving the best parallel performance, and that the extreme options often used in practice are suboptimal. We validate our claim quantitatively using an XML database as well as STMBench7, and show that the intermediate MGL options perform better compared to the existing state-of-the-art methods. In particular, NumLock achieves 65% reduction in execution time for the XML database, and 25% throughput improvement on STMBench7.