Multiple Granularity Locking

Shivani Kumari
Last Updated: May 13, 2022

Introduction

Whenever a transaction T is needed to access the database, a locking protocol locks the entire database. Now, if another transaction S happens simultaneously that requires accessing the data from the same database, it will not perform the transaction due to the locking of the entire database.

Locking the entire database is unnecessary and costs us the loss of concurrency. The concept of multiple granularity talks about resolving this issue. Now let’s first understand granularity.

Granularity

The size of data allowed to lock in is known as granularity.

Multiple Granularity

It means hierarchically breaking up the database into blocks that can be locked. Multiple granularity increases concurrency and reduces the lock overhead. It makes it easy to decide which data should be locked and which is not. A tree can represent the hierarchy of multiple granularity.

For example: Consider a tree that has four levels of nodes.

  • The root level or the top-level represents the entire database.
  • The second level represents a node of the type area. The database consists of precisely these areas.
  • The area has children nodes known as files. Any file cannot be present in more than one area.
  • Each file has child nodes known as records. The file precisely consists of those records that are its child nodes. No records can be present in more than one file. Therefore, levels starting from the highest level are
  1. Database
  2. Area
  3. File 
  4. Record

Explanation

  • Consider the above diagram, each node in the tree can be locked individually. According to the 2-phase locking protocol, it will use shared and exclusive locks.
  • When a transaction locks a node, it is either in shared or exclusive mode. The transaction implicitly locks descendants of that node in the same lock mode.
  • Locks on files and records are made simple, but the lock on the root is still not determined.
  • One way to know about a lock on the root is to search the entire tree. But it nullifies the whole concept of multiple granularity locking schemes. 
  • A more efficient way to achieve this is by using a new type of lock called intention lock mode.

Intention Lock Mode

In addition to shared and exclusive lock modes, other three lock modes are available.

  1. Intention-shared (IS): explicit lock at a lower level of the tree but only with shared locks.
  2. Intention-Exclusive (IX): explicit lock with exclusive or shared locks at a lower level.
  3. Shared & Intention-Exclusive (SIX): In this lock, the node is locked in shared mode, and some nodes are locked in exclusive mode by the same transaction.
     S    X    IS    IX  IX
SYesNoYesNoNo
XNoNoNoNoNo
ISYesNoYesYesNo
SIXNoNoYesNoNo
IXNoNoYesNoYes

 

Intention lock modes are used in multiple-granularity locking protocol uses to ensure serializability. In this protocol, if a transaction T that attempts to lock a node need to follow these protocols: 

  1. Transaction Ti must follow the lock-compatibility matrix.
  2. At first, Transaction Ti must lock the tree’s root in any mode.
  3. Transaction Ti will lock a node in S or IS mode only if Ti has locked that node’s parent in either IS or IX mode.
  4. Transaction Ti will lock a node in IX, SIX, or X mode only if Ti currently has the parent of the locked node in either SIX or IX modes.
  5. Transaction Ti will lock a node only if Ti has not unlocked any node before (i.e., Ti is two-phase).
  6. Transaction Ti will unlock a node only if Ti has not locked its children nodes currently.


Multiple granularity protocol requires that locks are made in a top-down (root-to-leaf) manner, whereas locks must be released in a bottom-up (leaf to-root) manner. 

Consider the given tree in the figure and the transactions:

  • Assume transaction T1 reads record Ra2 from file Fa. Then, T2 will lock the database, area A1, and Fa in IS mode (and in that order), and finally, it will lock Ra2 in S mode.
  • Assume transaction T2 modifies record Ra9 from file Fa. Then, T2 will lock the database, area A1, and file Fa (in that order) in IX mode and lock Ra9 in X mode.
  • Assume transaction T3 reads all the records from file Fa. Then, T3 will lock the database and area A1 (and in that order) in IS mode and lock Fa in S mode.
  • Assume transaction T4 reads the entire database. It can be done after locking the database in S mode.

Transactions T1, T3, and T4 can access the database together. Transaction T2 can execute concurrently with T1 but not with T3 or T4. 

Deadlock is also possible in the multiple-granularity protocol, as it is in the two-phase locking protocol. These can be eliminated by using specific deadlock elimination techniques.

Frequently Asked Questions

Q1. What is granularity?

The size of the data allowed to be locked is called granularity.

Q2. How does the granularity of data affect concurrency performance?

The Multiple Granularity locking protocols enhance concurrency and decrease overhead, especially when a combination of small transactions with a few accesses and transactions that last for a long time accessing many objects, such as audit transactions that access every item in the database.

Q3. What are the disadvantages of multiple granularity locking?

Transaction Ti needs to access the entire database in this technique, and a locking protocol is used. After that, Ti locks each item in the database. Therefore, it is less efficient. It would be simpler if a single lock could lock the entire database.

Key Takeaways

In this article, we learned about granularity and multiple granularity locking. We have also known how multiple granularity locking affects concurrency performances.

We discussed new locking modes to address multiple granularity locking. 

Visit here to learn more about different topics related to database and management systems. Ninjas don’t stop here. Check out the Top 100 SQL Problems to master frequently asked questions in big companies and land your dream job. Also, try  CodeStudio to practice a wide range of DSA questions asked in lots of interviews.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think