Guanzhou Hu

Feeling comfortably numb

Find me on GitHub

CV | LinkedIn | Google Scholar (at)
josehu (at)

To all my loved ones and my friends ♥
GitHub Pages — Theme by orderedlist

Understanding Hierarchical Locking in Database Systems

06 Oct 2022 - Guanzhou Hu

Described in this classic paper by Jim Gray et. al, hierarchical locking has been a well-studied idea in database management systems (DBMS). Despite its long history, I found the theoretical notion of lock modes less intuitive and hard to understand upon first encounter. This post tries to distill the core motivations of hierarchical locking, break its design down into three pieces, and describe them progressively, to hopefully clarify this beautiful idea.

Traditional Locking

Consider a database with only one small table (i.e. relation), shared by multiple clients. The clients could issue concurrent transactions that read some tuples (i.e. records) of the table or update them with new values. To protect the database from data races, it is pretty natural to apply a traditional reader-writer lock on the table.

Traditional Locking

In database terminology, we denote acquiring a reader lock on the table as locking it in shared (S) mode, while acquiring a writer lock on the table as locking it in exclusive (X) mode. Multiple clients could hold S locks on the same table at the same time for reads. At most one client could hold an X lock on the table (with no S locks held by anyone else as well).

We call two locking attempts compatible if their lock modes are allowed to be held at the same time on the same thing. S mode is compatible with itself. S and X are not compatible with each other. X is of course also not compatible with itself.

Back to our problem scenario, since the database has only one table with a small number of tuples, a reasonable solution is to put a lock on that table. Read requests must attempt to acquire the lock in S mode and can proceed only after the acquirement is successful. Writes requests must attempt to acquire it in X mode. This is basically how a reader-writer lock works in classic systems. So far, so good.

Problem: what if the database is not in toy scale any more, but is composed of hundreds of tables, each having millions of records? Real-world databases can easily reach this scale. The traditional locking mechanism with uniform granularity puts a dilemma on choosing the granularity of locks:

Both choices are not ideal for overall performance. The solution to this problem is to introduce hierarchical locking on different levels of database resources.

Hierarchical Locking

A database is naturally structured as a tree (or more generally, a DAG) of resources. For example, the following figure represents a database with 3 tables, each having 100 tuples. Tuples could further be decomposed into fields (i.e. attributes or columns); we consider tuples as the finest granularity in this post.

Tree hierarchy

The core idea of hierarchical locking 1 2 is to allow putting locks on nodes of tree (which may be at different granularity levels), instead of only at a uniform granularity.

Version #1: Introduce Implicit Locking

In the first step towards hierarchical locking, we introduce implicit locking: locking an internal node in S mode implicitly locks all its descendant nodes with S mode; X mode behaves similarly.

Implicit Locking

Implicit locking reduces the number of locks dramatically in cases of bulk operations, which nicely solves the performance problem of fine-grained locking. However, this mechanism itself is not enough, because it introduces correctness problems.

Conflict Error

Problem: what about conflicting transactions that end up holding conflicting lock modes at different levels? Transaction B holds X locks on tuple R99 in table 0 and is going to update it. Transaction A comes and acquires a single S lock on table 0 to read all of its tuples. This situation should not be allowed. There are more incorrect scenarios besides this example.

Version #2: Introduce Intention Modes

To solve the correctness problem, we need to let internal nodes remember the locking state of its children. We introduce two intention lock modes: intention shared (IS) mode and intention exclusive (IX) mode.

To lock a node in X mode, the client must traverse the tree from root and lock all ancestor nodes along the path with IX mode, before locking the target node in X. Similarly, to lock a node in S mode, the client must traverse the tree from root and lock all ancestor nodes with IS mode, before locking the target node in S. By doing this, internal nodes now carry necessary information about the locking state of its descendant nodes in the subtree.

By always traversing the tree from root and locking ancestor nodes in intention modes (and releasing them in the reverse order when done), the correctness problem described in the previous section is now solved. Transaction B must have locked table 0 in IX already before it locks its R99 in X, which prevents transaction A from locking the entire table in S. If A and B touch different tables, however, they can proceed concurrently.

Hierarchical Locking

Problem: consider a workload that scans a big table while only attempting to update a few tuples in it. With the current version of hierarchical locking, it must either hold a big X lock on the table, or hold many S locks on tuples it reads. Can we further optimize performance for this situation?

Version #3: Introduce SIX Mode as an Optimization

We introduce a combined mode of S and IX to optimize for the aforementioned situation. The shared and intention exclusive (SIX) mode grants the client with read permission on all children, while optionally allowing it to further acquire X locks on some child nodes. This way, the client can hold a single SIX lock on the table plus a few X locks on tuples it is trying to modify.

SIX Mode

The original paper 1 presents a nice summary of compatibility between modes. Note that NL simply stands for null lock (i.e. not locked).

Compatibility Table

Concurrency control in database systems involve many more interesting issues besides hierarchical locking. To name a few examples:

Some of these things have been covered in my past blog posts. Other techniques and their modern implications may be covered in my future blog posts.


Please comment below anything you wanna say! 😉