In the previous chapters we learned how to check whether a schedule is serializable (using precedence graphs) and whether it is recoverable or cascadeless. But a real database cannot first let transactions run and then check the result afterwards. It needs a set of rules that makes sure only good schedules can happen in the first place.
Such a set of rules is called a concurrency control protocol. The most widely used family of protocols is based on locks.
In simple words:
Before a transaction touches a data item, it must get a lock on it. The lock tells other transactions what they are allowed to do with that item at the same time.
In this chapter we will learn shared and exclusive locks, why simple locking is not enough, the Two-Phase Locking (2PL) protocol and its variants, and we will watch real locks inside MySQL.
Why Do We Need Locks?
Recall the lost update problem. Two transactions read the same balance and both write back their own new value:
Balance A = 1000
T1 T2
read(A) → 1000
read(A) → 1000
A = A - 100
A = A + 500
write(A) → 900
write(A) → 1500
Final A = 1500 (T1's withdrawal of 100 is lost!)
The problem is that T2 was allowed to read A while T1 was in the middle of changing it. If T1 could say "nobody else may touch A until I am done", the problem disappears. That is exactly what a lock does.
Shared and Exclusive Locks
Most lock-based protocols use two lock modes:
Lock Mode | Written as | Allows the holder to | Others can still |
|---|---|---|---|
Shared lock | S(A) or lock-S(A) | Read A | Read A (take their own S lock) |
Exclusive lock | X(A) or lock-X(A) | Read and write A | Nothing — they must wait |
The idea is very natural: many people can read the same notice board at once, but if someone is rewriting the notice, nobody else should read or write it at that moment.
Lock Compatibility Matrix
A requested lock is granted only if it is compatible with all locks already held on that item by other transactions. Otherwise the requesting transaction waits.
Requested ↓ / Held → | S | X |
|---|---|---|
S | ✔ Compatible | ✘ Wait |
X | ✘ Wait | ✘ Wait |
Only S with S is compatible. Any combination involving X conflicts. Notice that this matches the definition of conflicting operations from the Conflict & View Serializability chapter: two operations conflict if at least one of them is a write.
Lock Upgrade and Downgrade
Upgrade (S → X): a transaction that holds a shared lock asks to convert it to exclusive, for example after reading a value it now wants to change it.
Downgrade (X → S): a transaction holding an exclusive lock converts it to shared because it no longer needs to write.
We will see shortly that in 2PL, upgrades are allowed only in the growing phase and downgrades only in the shrinking phase.
Locking Alone Is Not Enough
A common beginner assumption is: "If every transaction locks items before using them, the schedule must be serializable." This is false. The problem is when locks are released.
Consider T1 transferring 100 from A to B, and T2 displaying A + B. Initially A = 1000, B = 2000, so the correct total is always 3000.
T1 T2
X(A)
read(A) → 1000
A = A - 100
write(A) → 900
unlock(A)
S(A)
read(A) → 900
unlock(A)
S(B)
read(B) → 2000
unlock(B)
display A + B → 2900 ✘ wrong!
X(B)
read(B) → 2000
B = B + 100
write(B) → 2100
unlock(B)
Every access was protected by a correct lock, yet T2 saw an inconsistent state (2900 instead of 3000). The schedule is not serializable: T2 sees T1's write of A (T1 → T2) but reads B before T1 writes it (T2 → T1), giving a cycle.
The fix is not more locks. The fix is a rule about when a transaction may release locks. That rule is Two-Phase Locking.
Two-Phase Locking (2PL)
Two-Phase Locking protocol: each transaction acquires and releases its locks in two phases. In the growing phase it may obtain locks but may not release any. In the shrinking phase it may release locks but may not obtain any new lock.
In one line: once a transaction releases any lock, it can never acquire another lock.
Number of
locks held
│ lock point
│ ●
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
└────────────────────────────────▶ time
growing phase shrinking phase
(only acquire) (only release)
The moment when a transaction gets its last lock is called its lock point.
Fixing Our Example with 2PL
T1 T2
X(A)
read(A) → 1000
write(A) → 900
X(B) ← T1 takes ALL locks before releasing any
unlock(A) ← lock point passed, shrinking begins
S(A)
read(A) → 900
S(B) ← must WAIT, T1 still holds X(B)
read(B) → 2000
write(B) → 2100
unlock(B)
S(B) granted
read(B) → 2100
unlock(A), unlock(B)
display A + B → 3000 ✔
Because T1 could not release A until it had also locked B, T2 can never "slip in between" T1's two updates. The result is equivalent to the serial order T1 → T2.
Why Does 2PL Guarantee Serializability?
Here is the intuition behind the proof.
Suppose the precedence graph has an edge Ti → Tj. That means Ti and Tj performed conflicting operations on some item Q, and Ti went first.
Because the operations conflict, at least one lock was X. So Tj could only get its lock on Q after Ti released its lock on Q.
Ti released a lock, so Ti was already past its lock point. Tj then acquired a lock, so Tj had not yet reached its lock point. Therefore lock point(Ti) < lock point(Tj).
A cycle Ti → Tj → … → Ti would mean lock point(Ti) < lock point(Ti), which is impossible.
Every schedule allowed by 2PL is conflict serializable, and an equivalent serial order is the order of the transactions' lock points.
Important: the opposite is not true. Some conflict-serializable schedules cannot be produced by 2PL. 2PL is a sufficient condition, not a necessary one.
Problems with Basic 2PL
Basic 2PL solves serializability but leaves two problems open.
Problem 1: Cascading Rollbacks
Basic 2PL allows a transaction to release an X lock in the shrinking phase before it commits. Another transaction can then read the uncommitted value:
T1 T2 T3
X(A)
read(A)
write(A)
X(B)
unlock(A)
X(A)
read(A) ← dirty read of T1's value
write(A)
unlock(A)
S(A)
read(A) ← dirty read
read(B) ...
ABORT ✘
→ T2 must roll back → T3 must roll back
This is the cascading rollback we studied in the Recoverable & Cascadeless Schedules chapter. Worse, if T2 had already committed, the schedule would not even be recoverable.
Problem 2: Deadlocks
T1 T2
X(A)
X(B)
X(B) → waits for T2
X(A) → waits for T1
Both wait forever.
2PL does not prevent deadlocks. A transaction in its growing phase may hold some locks and wait for others, and two such transactions can wait for each other. Detecting and handling this is the topic of the next-but-one chapter, Deadlocks in DBMS.
Variants of 2PL
Strict 2PL
Strict 2PL: basic 2PL, plus a transaction holds all its exclusive (X) locks until it commits or aborts.
Since no one can read or overwrite an item that an uncommitted transaction has written, there are no dirty reads. Strict 2PL schedules are therefore cascadeless (and so also recoverable). Shared locks may still be released early in the shrinking phase.
Rigorous 2PL (Strong Strict 2PL)
Rigorous 2PL: a transaction holds all its locks, shared and exclusive, until it commits or aborts.
Here the serialization order is simply the commit order, which makes reasoning very easy. Most commercial systems, including MySQL's InnoDB, behave like rigorous 2PL for the locks they take: row locks are released at COMMIT or ROLLBACK. (One caveat: an ordinary InnoDB SELECT without FOR SHARE / FOR UPDATE takes no row locks at all; it reads a consistent snapshot instead. Only locking reads and writes follow the locking rules described here.)
Conservative 2PL (Static 2PL)
Conservative 2PL: a transaction must acquire all the locks it will ever need before it starts executing. If any lock is unavailable, it takes none and waits.
Because a transaction never holds some locks while waiting for others, conservative 2PL is deadlock-free. The downside: the transaction must know its full read/write set in advance, which is rarely possible (think of a query whose rows depend on data it reads), and it can hold locks for longer than needed.
Comparison Table
Variant | Conflict serializable? | Cascadeless? | Deadlock-free? | Key rule |
|---|---|---|---|---|
Basic 2PL | Yes | No | No | No lock after first unlock |
Strict 2PL | Yes | Yes | No | Hold X locks till commit/abort |
Rigorous 2PL | Yes (order = commit order) | Yes | No | Hold all locks till commit/abort |
Conservative 2PL | Yes | Not necessarily | Yes | Take all locks before starting |
A popular GATE trap: conservative 2PL is deadlock-free but it is not automatically cascadeless, because it may release an X lock before commit. Strict 2PL is cascadeless but not deadlock-free.
Lock Granularity and Intention Locks
So far we locked "data items" without saying how big an item is. It could be a whole database, a table, a page, or a single row.
Coarse locks (a whole table): little lock-management overhead, but low concurrency.
Fine locks (single rows): high concurrency, but many locks to manage.
Multiple granularity locking lets a transaction lock at the level that suits it. The challenge: if T1 holds an X lock on one row, and T2 wants an S lock on the whole table, how does the system find the row lock quickly without scanning every row? The answer is intention locks placed on the ancestors (table, database) first.
Mode | Meaning |
|---|---|
IS (intention shared) | I intend to take S locks at a finer level below this node |
IX (intention exclusive) | I intend to take X (or S) locks at a finer level below |
SIX | S on this whole node, plus IX: I read everything and will update some parts |
Compatibility (✔ = compatible):
Requested ↓ / Held → | IS | IX | S | SIX | X |
|---|---|---|---|---|---|
IS | ✔ | ✔ | ✔ | ✔ | ✘ |
IX | ✔ | ✔ | ✘ | ✘ | ✘ |
S | ✔ | ✘ | ✔ | ✘ | ✘ |
SIX | ✔ | ✘ | ✘ | ✘ | ✘ |
X | ✘ | ✘ | ✘ | ✘ | ✘ |
Rules: locks are taken from the root downwards (to lock a row in S you first need IS or IX on the table) and released from the bottom upwards. Now when T2 asks for S on the table, the system sees T1's IX on the table and makes T2 wait, without looking at any row.
Seeing Real Locks in MySQL
InnoDB, MySQL's default storage engine, uses exactly these ideas: S and X row locks, IS and IX table-level intention locks, and locks held until the transaction ends. You can take locks explicitly with SELECT ... FOR SHARE (S) and SELECT ... FOR UPDATE (X); UPDATE and DELETE take X locks automatically.
We ran two sessions against a copy of the tutorial's company_db sample database. Session 1 (T1):
START TRANSACTION;
SELECT emp_id, name, salary FROM employees WHERE emp_id = 1 FOR SHARE;
UPDATE employees SET salary = salary + 5000 WHERE emp_id = 2;
-- ... T1 stays open for a few seconds, then COMMIT
While T1 was still open, Session 2 (T2) ran:
START TRANSACTION;
SELECT emp_id, name FROM employees WHERE emp_id = 1 FOR SHARE; -- S lock on row 1
UPDATE employees SET salary = salary + 1 WHERE emp_id = 2; -- needs X lock on row 2
COMMIT;
A third session looked at the lock table performance_schema.data_locks while T2 was stuck:
SELECT engine_transaction_id AS trx, lock_type, lock_mode, lock_status, lock_data
FROM performance_schema.data_locks
WHERE object_schema = 'lk30_db'
ORDER BY engine_transaction_id, lock_type DESC, lock_data;
+------+-----------+---------------+-------------+-----------+
| trx | lock_type | lock_mode | lock_status | lock_data |
+------+-----------+---------------+-------------+-----------+
| 3210 | TABLE | IS | GRANTED | NULL |
| 3210 | TABLE | IX | GRANTED | NULL |
| 3210 | RECORD | S,REC_NOT_GAP | GRANTED | 1 |
| 3210 | RECORD | X,REC_NOT_GAP | GRANTED | 2 |
| 3211 | TABLE | IS | GRANTED | NULL |
| 3211 | TABLE | IX | GRANTED | NULL |
| 3211 | RECORD | S,REC_NOT_GAP | GRANTED | 1 |
| 3211 | RECORD | X,REC_NOT_GAP | WAITING | 2 |
+------+-----------+---------------+-------------+-----------+
(The transaction ids will be different on your machine.) Everything we learned is visible here:
Both transactions hold IS and IX on the table — intention locks are compatible with each other.
Both hold an S lock on row 1 at the same time — S is compatible with S.
T2's request for an X lock on row 2 is WAITING, because T1 holds X on row 2.
REC_NOT_GAPmeans a lock on the row itself only. InnoDB also has gap and next-key locks that lock the space between index entries to stop phantom rows; you will meet them when studying isolation levels.
As soon as T1 committed, its locks were released and T2's update went through. If T1 had stayed open longer than innodb_lock_wait_timeout (50 seconds by default), T2 would have received ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction.
Starvation
Locking can also cause starvation: a transaction waits indefinitely even though there is no deadlock. Example: T1 wants an X lock on A, but a continuous stream of transactions keep taking S locks on A, and each new S request is compatible with the S locks already held. T1 never gets its turn.
The lock manager prevents this by granting requests in order: a new request is granted only if it is compatible with held locks and there is no earlier request still waiting for that item.
Common Mistakes
"2PL means locking in two steps." No — the two phases are growing and shrinking. The number of locks does not matter.
"2PL prevents deadlock." Only conservative 2PL does. Basic, strict and rigorous 2PL can all deadlock.
"Every serializable schedule is a 2PL schedule." No. 2PL produces only conflict-serializable schedules, but not all of them.
Upgrading a lock in the shrinking phase. An upgrade is acquiring a stronger lock, so it is allowed only in the growing phase.
Confusing strict and rigorous. Strict holds exclusive locks till the end; rigorous holds all locks till the end.
Interview Questions
What is the lock point of a transaction?
The point in time at which the transaction acquires its last lock, i.e. the end of the growing phase. Under 2PL, ordering transactions by their lock points gives an equivalent serial schedule.
Does 2PL guarantee recoverability?
No. Basic 2PL allows reading data written by an uncommitted transaction, so cascading rollbacks and even non-recoverable schedules are possible. Strict 2PL fixes this by holding X locks until commit.
Which 2PL variant is deadlock-free?
Conservative (static) 2PL, because a transaction takes all its locks before it starts and never waits while holding a lock.
Why are intention locks needed?
To make multiple-granularity locking efficient. A transaction that wants to lock a whole table can check the table's intention locks instead of inspecting every row lock below it.
Is S compatible with IX?
No. IX on a table means someone will write some rows; an S lock on the whole table means "nobody may write any row", so they conflict.
Which variant does a typical commercial DBMS use?
Strict or rigorous 2PL. InnoDB, for example, keeps the row locks it takes until COMMIT or ROLLBACK, so for locking reads and writes the conflict order matches the commit order. (Plain SELECTs in InnoDB read a snapshot and take no locks.)
Summary
Shared (S) locks allow reading and are compatible with each other; exclusive (X) locks allow writing and conflict with everything.
Locking alone does not guarantee serializability; releasing locks too early can expose inconsistent data.
2PL: a growing phase (only acquire) followed by a shrinking phase (only release). It guarantees conflict serializability in lock-point order.
Basic 2PL can cause cascading rollbacks and deadlocks.
Strict 2PL (hold X till end) → cascadeless. Rigorous 2PL (hold all till end) → serial order = commit order. Conservative 2PL (lock everything first) → deadlock-free.
Intention locks (IS, IX, SIX) make locking at multiple granularities efficient; MySQL InnoDB uses them together with row-level S/X locks.
Locks make transactions wait. In the next chapter, Timestamp Ordering Protocol, we will see a completely different approach that never makes a transaction wait for a lock — it decides the order in advance using timestamps.