Multiple granularities of database locks
Shreyansh Gupta
Multiple granularity locking
To understand this concept, first let us take a look at the structure of a database. It can be represented by the following hierarchy.
Now, whenever we explicitly apply a lock at any level, all the children nodes are implicitly locked by the same lock. e.g. If a transaction T1 obtains an S lock on a page P1, all the rows, Ri, on P1 will be implicitly locked using the S lock. If another transaction T2 tries to obtain an X lock on the row R1 (R1 in on P1), it will be denied that request since R1 is implicitly locked with an S lock and S and X locks are not compatible.
Why lock at multiple granularities?
Let us consider a case where we only have locks at the database level. Whenever a transaction, T1, needs to update a row, it obtains an X lock at the database level even if it needs to update only 1 row. If another transaction, T2, needs to read a row in a different table, it cannot do that since T1 has a lock on the entire database. This has an adverse affect on concurrency.
Let us consider a case where we only have locks at the row level. If a transaction wants to update a table, TAB1, it obtains X locks on all the rows in TAB1. If TAB1 has 1 million rows, the overhead of adding locks to all the rows and storing these locks is too much.
As we saw, there a merits and demerits to both, higher level and lower level, locks.
Multi-granularity locking using Intent Locks
Let us consider another case.
- A transaction, T1, obtains an X lock on the row, R1. R1 belongs to the table, TAB1. TAB1 has a lot of rows, say 1 million. Now, another transaction, T2, wants to obtain an X lock on TAB1. Since X lock is not compatible with itself, T2 will need to scan all the rows in TAB1 to ensure that no row has an incompatible lock. This adds a lot of processing overhead for every lock that needs to be added. We can solve this problem with the help of Intent locks. (You can read here to know more about different types of locks.)
When T1 obtains the X Lock on R1, the database adds IX (Intent Exclusive) lock on the parent nodes (page, table TAB1, database). When T2 attempts to obtain an X Lock on TAB1, the request can be rejected by simply inspecting the locks on TAB1. The IX Lock on TAB1 signifies that there is an X Lock at the lower level. Since we know -
When we apply a lock at a node, all the children nodes are also implicitly locked by the same lock.
An X lock is not compatible with itself.
Hence, T2’s request to obtain an X Lock on TAB1 can be rejected. As we read later in this article, this process can be summarized by understanding the relation between IX and X lock. IX and X locks are not compatible. So, an X lock on TAB1 cannot be obtained while TAB1 is locked with an IX lock.
Similarly we also have a SIX Lock. A SIX Lock on a node indicates that there is an S Lock at lower level and an X Lock at an even lower level.
Rules for obtaining a lock
When a transaction, T1, wants to obtain a lock on the node, N, it needs to follow these rules -
Before T1 can be granted a lock on N, the database lock management system must ensure lock compatibility.
Before granting a lock on N, the root of the tree must be locked first. It can be locked in any mode. So, we apply a lock from top-to-bottom.
A node, N, can be locked by T1 in S or IS mode only if the parent of N is currently locked by T1 in IS or IX mode. (Note that this means that the parent must have at least an IS or an IX lock active. But the parent can also have other compatible locks active.)
A node, N, can be locked by T1 in X, SIX or IX mode only if the parent of N is currently locked by T1 in either IX or SIX mode. (Note that this means that at least an IX or a SIX lock must be present on the parent. But the parent can also have other compatible locks active.)
T1 can lock any node only if it has not unlocked any node so far. i.e. once T1 starts unlocking nodes, it cannot lock any more nodes.
T1 can unlock a node, N, only if none of the children of N are currently locked by T1. This means that the unlocking is done from bottom-to-top.
Lock compatibility matrix
Following matrix shows the compatibility between different locks. Compatibility between 2 locks means that at any given point, both the locks can be concurrently active on the same node. They may be obtained by the same transaction or by different transactions.
References
Subscribe to my newsletter
Read articles from Shreyansh Gupta directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by