Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 79 ยท Concurrency Control

Locks: Shared, Exclusive and Intention

Learn shared and exclusive lock modes, the compatibility matrix, lock granularity, intention locks for multiple-granularity locking and how a lock manager works.

The most common way to get isolation is to make transactions take locks on the data they touch. A lock is a permission slip recorded in memory: "transaction T1 may read this row" or "T1 may change it". Other transactions that want a conflicting permission must wait. If the rules for taking and releasing locks are chosen well (the topic of two-phase locking), the result is a serializable schedule. This lesson covers the building blocks: what kinds of locks exist, which ones can coexist, how big a thing a lock should cover, and how the DBMS keeps track of it all.

You met the problem these locks solve in Isolation Levels and Concurrency Anomalies. Here you will build a small lock manager, so the rules stop being abstract.

Two basic lock modes

Shared (S) Read. Many holders at once.
Exclusive (X) Write. Only one holder, no readers.

Readers share. Writers are alone.

1 / 2

Shared and exclusive locks

A transaction that wants to read an item asks for a shared lock (S, also called a read lock). A transaction that wants to write asks for an exclusive lock (X, a write lock). Two transactions may hold shared locks on the same item at once, because reads do not conflict. An exclusive lock conflicts with everything: while T1 holds X on an item, nobody else can hold any lock on it.

This is the conflict rule turned into a table. Writing the compatibility of a requested mode (rows) against a mode already held by another transaction (columns):

Requested \ Held S X
S yes no
X no no

If the request is incompatible, the transaction is placed in a wait queue for that item and blocked. When the holders release their locks, the manager looks at the head of the queue and grants whatever is now compatible. Most managers serve the queue first-in, first-out. Letting a new reader jump ahead of a waiting writer is tempting, but a steady stream of readers could then starve the writer forever, so a request that arrives while others are queued joins the queue.

A lock manager in miniature

A real lock manager is a hash table keyed by the resource identifier (a table id, or table id plus row id). Each entry holds a list of granted requests and a queue of waiting requests, plus there is a per-transaction list of held locks so everything can be released at commit. Lookups are fast because the table lives in memory and is protected by short-term latches (cheap internal mutexes), not by the locks themselves.

The simulation below implements exactly that. T1 and T2 read item A together, T3 wants to write and must wait, and a later reader T4 queues behind T3 instead of overtaking it.

Python A lock table with a wait queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

T4 asks for a shared lock that would actually be compatible with the two readers holding A, but it waits because T3 is ahead of it in the queue. Only when T1 and T2 are gone does T3 get its exclusive lock, and when T3 releases, T4 finally proceeds.

Lock granularity

What should one lock cover? A whole database, a table, a disk page or a single row? This is the granularity question, and it is a trade-off.

  • Coarse locks (table) are cheap to manage: few entries in the lock table, little memory. But they block more transactions. Two clients updating different rows of the same table would wait for each other.
  • Fine locks (row) allow high concurrency but cost memory and CPU: a query touching a million rows would need a million lock entries.

Real engines mix the two. Many do lock escalation: when one transaction accumulates too many row locks on a table, the engine converts them to a single table lock. Others avoid the problem with different techniques. SQLite, as an embedded database with simple needs, historically locks the whole database file: any number of readers, or one writer. It is simple and correct; it simply does not scale to many concurrent writers.

Multiple-granularity locking and intention locks

If rows, pages and tables can all be locked, the manager must detect conflicts across levels. Suppose T1 holds a lock on one row of the orders table, and T2 now asks for a lock on the entire table. The lock on the table and the lock on the row are different entries in the hash table, so a naive manager would not notice that they overlap. Searching every row for a conflicting lock is far too slow.

The solution is the multiple-granularity protocol with intention locks. Locks are organized along a hierarchy, and before locking a node in mode S or X, a transaction first places an intention lock on every ancestor, from the root down:

flowchart TD
  D["database"] --> T["table orders"]
  T --> P["page 7"]
  P --> R["row 42"]

To write row 42, take IX on the database, IX on the table, IX on the page, then X on the row.

The intention modes are:

  • IS (intention shared): "somewhere below I will take S locks."
  • IX (intention exclusive): "somewhere below I will take X locks."
  • SIX (shared + intention exclusive): "I read this whole subtree, and will also write some parts of it."

An intention lock never conflicts with another intention lock, because the real conflict, if there is one, will be found at a lower level. But it conflicts with a full lock on the same node, which is how the manager notices that a table-level S request clashes with a transaction that is about to write rows underneath. The compatibility matrix for the five modes is:

Requested \ Held IS IX S SIX X
IS yes yes yes yes no
IX yes yes no no no
S yes no yes no no
SIX yes no no no no
X no no no no no

Release goes the other way, from the leaf up to the root, so no node is unlocked while a descendant is still locked. The simulation below uses this matrix. T1 reads one row, T2 updates a different row of the same table, and both proceed. T3 then wants to read the entire table and T4 wants to rewrite it; both must wait because of the intention locks sitting on the table.

Python Multiple-granularity locking with intention locks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the table-level entry for db/orders: T1 holds IS and T2 holds IX, which are compatible, so two row-level transactions coexist. T3's S request conflicts with T2's IX, so it waits, and T4 queues behind it. When T1 and T2 release, T3 receives its table lock. The second queued request (T4's X) must keep waiting, because it conflicts with T3's S lock; the simulation prints only the grant that actually happened.

Notice also what this design costs: every row access takes several lock-table operations. That is the price of letting table-level and row-level lockers exist side by side.

The tree protocol

Two-phase locking is not the only way to get serializable schedules. When the data items are arranged in a tree and every transaction walks from the top down, a simpler and more flexible rule works: the tree (graph-based) protocol. B+ tree indexes, with their root, internal nodes and leaves, are the typical example.

The rules, in the basic version that uses only exclusive locks:

  1. A transaction's first lock can be on any node.
  2. After that, it may lock a node Q only while it currently holds the lock on Q's parent.
  3. It may unlock a node at any time.
  4. Once it has unlocked a node, it may not lock it again.

Rule 3 is what makes the protocol attractive: unlike 2PL, a transaction can release the root as soon as it holds a child, so other transactions can enter the tree behind it. This idea, called lock coupling or crabbing (hold the parent, grab the child, release the parent), is how database engines let many readers and writers traverse a B+ tree at once.

What you get:

  • Conflict serializability. Every schedule allowed by the protocol is conflict serializable, even though transactions release locks early and are not two-phase.
  • Deadlock freedom. All locks are taken parent before child, so a transaction never waits for a lock above one it already holds. A wait-for cycle would need such an upward wait, so none can occur. You never need a detector or an abort for deadlocks.
  • Shorter lock times than 2PL on hot nodes such as the root.

What it costs:

  • A transaction may have to lock nodes it does not need, only because they are on the path to the node it does need.
  • A transaction that unlocks early lets others see its writes before it commits, so the protocol does not guarantee recoverability or cascadeless schedules. A real system adds extra rules, such as holding exclusive locks until commit.
  • There is no tree structure in most application data, so the protocol is rarely used on rows. Its home is inside index structures.

The program below checks the four rules for four transactions on a small tree and replays an interleaving of two legal transactions.

Python Tree protocol: checking the rules and replaying an interleaving

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

T1 walks A -> B -> D and T2 walks A -> C -> F, each unlocking a parent right after locking its child. Bad1 jumps to F without holding C, and Bad2 locks A a second time, which rules 2 and 4 forbid. In the replay, T2 has to wait for the root only until T1 has moved down to B and released A. After that, the two transactions work in different subtrees at the same time. This is the concurrency 2PL cannot give you on a hot root node.

Where locks go wrong

Locks give isolation, but they introduce waiting, and waiting causes two new problems. If two transactions each wait for a lock the other holds, neither will ever proceed: a deadlock, the subject of Deadlocks: Detection, Prevention and Recovery. And a protocol that releases locks too early still allows non-serializable schedules, which is why we need the discipline of two-phase locking. Simply having locks is not enough; when they are taken and released decides correctness.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. T1 holds a shared lock on item A. Which request from another transaction can be granted immediately?

    Shared locks are compatible with each other, because two reads never conflict. An exclusive request must wait.
  2. 2. Why does a lock manager normally put a new shared request into the queue when a writer is already waiting?

    If readers could always jump ahead, a steady stream of them would keep the writer waiting forever. First-in, first-out queuing keeps the waiting time bounded.
  3. 3. What problem do intention locks solve?

    Before locking a row, a transaction places IS or IX on every ancestor. A table-level request then conflicts with those intention locks at the table node itself.
  4. 4. Two transactions hold IX on the same table. What is true?

    Intention modes are compatible with each other. They only announce plans to take finer locks, and conflicts between those finer locks are detected at the row or page level.

Summary

  • Shared locks allow concurrent readers; an exclusive lock admits one writer and nothing else.
  • A compatibility matrix decides whether a requested lock can be granted; incompatible requests wait in a FIFO queue, which also prevents writer starvation.
  • Coarse locks are cheap but limit concurrency; fine locks allow concurrency but cost memory, so engines mix granularities and may escalate.
  • Intention locks (IS, IX, SIX) on ancestors let table-level and row-level locking coexist without scanning all rows.
  • The tree protocol locks a node only while holding its parent and allows early unlocking; it is serializable and deadlock-free, and it is the idea behind lock coupling in B+ tree indexes.
  • A lock manager is an in-memory hash table of granted and waiting requests; correctness also depends on the rule for when locks are taken and released.

Next: Two-Phase Locking.