Chapter 3 presents two-phase locking (2PL). Remember I told you in Chapter 2: Serializability Theory that the discussion is very scheduler-centric? Well, this is a deeper dive into the scheduler, using 2PL as the concurrency control mechanism. The chapter examines the design trade-offs in scheduler behavior, proves the correctness of basic 2PL, dissects how deadlocks arise and are handled, and discusses many variations and implementation issues.
Here are the section headings in Chapter 3.
- Aggressive and Conservative Schedulers
- Basic Two Phase Locking
- Correctness of Basic Two Phase Locking
- Deadlocks
- Variations of Two Phase Locking
- Implementation Issues
- The Phantom Problem
- Locking Additional Operators
- Multigranularity Locking
- Distributed Two Phase Locking
- Distributed Deadlocks
- Locking Performance
- Tree Locking
Yep, this is a long chapter: 65 pages.
3.1 Aggressive and Conservative Schedulers
The chapter opens by asking: how aggressive or conservative should a scheduler be? An aggressive scheduler tries to schedule operations immediately, risking aborts later. A conservative scheduler delays operations to avoid future conflicts, often needlessly.
This choice affects throughput, latency, and starvation. If conflicts are rare, aggressive wins. If conflicts are frequent or costly, conservative may be preferable.
The book says: "A very conservative version of any type of scheduler can usually be built if transactions predeclare their readsets and writesets. This means that the TM begins processing a transaction by giving the scheduler the transaction’s readset and writeset. Predeclaration is more easily and efficiently done if transactions are analyzed by a preprocessor, such as a compiler, before being submitted to the system, rather than being interpreted on the fly."
This reminded me of Chardonnay, OSDI'23, where Bernstein is an author. (Here is my review/summary of it.) Isn't that an interesting follow-up to the above paragraph 36 years later.
3.2 Basic Two Phase Locking
Three rules define 2PL: don’t grant conflicting locks, don’t release until the data manager (DM) acknowledges, and once you release a lock, you’re done acquiring. These encode the "growing" and "shrinking" phases that give 2PL its name.
Here is the notation the book uses: `rl_i[x]` denotes a read lock by transaction Ti on item x, `wl_i[x]` a write lock, and `wu_i[x]` means Ti releases the write lock. These are distinct from the operations themselves (like `r_i[x]` or `w_i[x]`), and the system must track both.
The figure below shows an example of what would go wrong if rule 3 is violated.
3.3 Correctness of Basic Two Phase Locking
In this section, the authors prove that histories produced by 2PL schedulers are serializable. The proof hinges on showing that the serialization graph (SG) is acyclic. They derive this from the locking orderings induced by the scheduler's behavior. The key idea is that if T1 precedes T2 in SG, then T1 must have released a lock before T2 acquired a conflicting one. Since T1 does not acquire any locks after releasing that one, this precludes cycles in the SG.
3.4 Deadlocks
2PL enables serializability, but at the cost of deadlocks. The section opens with classic 2PL-induced deadlocks: mutual lock upgrades. Then it dives into detection via Waits-For Graphs (WFGs), where the idea is to add an edge when one transaction waits on another, and detect deadlocks by finding cycles.
Timeouts versus explicit detection gets compared. Timeouts are crude but simple (deadlocks don’t vanish on their own, so detection can be delayed safely). WFG cycle detection is precise but expensive. The section discusses how often to detect, how to tune timeouts, and how to pick a victim.
3.5 Variations of Two Phase Locking
Conservative 2PL requires that a transaction predeclare all the data it may access and acquire all locks up front before execution begins. If even one lock is unavailable, it waits for all. This avoids deadlocks entirely but sacrifices concurrency and assumes predictability in data access.
Strict 2PL, used in nearly all real systems, releases locks only at commit time. This is more strict than the basic 2PL we discussind in 3.2, where the shrinking could happen gradually. But in return, this guarantees strictness and recoverability. To avoid cascading aborts, write locks are held until after commit; read locks can be released a bit earlier.
3.6 Implementation Issues
This section gives some guidelines (as of 1987) for implementing a lock manager, handling blocking and aborting transactions, and ensuring atomicity of reads and writes.
3.7 The Phantom Problem
The phantom problem is set up nicely. Most real databases can dynamically grow and shrink. In addition to Read and Write, they usually support Insert and Delete. Index locking is introduced as a way to lock ranges instead of records. This helps detect conflicts for inserts into a scanned range.
Two locks conflict if there could be a record that satisfies both predicates, i.e., the predicates are mutually satisfiable. This is predicate locking. While more general than index locking, it's more expensive, as it requires the lock manager (LM) to reason about predicates. Predicate locking is rare in practice.
We had discussed index locking and predicate locking in Chapter 7 of the Gray/Reuters book, so I defer to that discussion.
3.8 Locking Additional Operators
Similar to how Chapter 2 extended serializability theory beyond read/write to include increment/decrement, Chapter 3 does the same for locking. I really like this treatment and generalization opportunity!
To add new operation types, follow these rules:
- Make each new operation atomic w.r.t. all others.
- Define a lock type for each operation.
- Build a compatibility matrix where two lock types conflict iff their corresponding operations don’t commute.
3.9 Multigranularity Locking
Multi-granularity locking (MGL) allows each transaction to use granule sizes most appropriate to its behavior. Long transactions can lock coarser items like files; short transactions can lock individual records. In this way, long transactions don’t waste time setting too many locks, and short transactions don’t block others by locking large portions of the database that they don’t access. This balances overhead and concurrency.
We assume the lock instance graph is a tree. A lock on a coarse granule x implicitly locks all its descendants. For instance, a read lock on an area implicitly read-locks its files and records.
To make fine-grained locks compatible with this, we use intention locks. Before locking a record x, the scheduler sets intention locks (`ir`, `iw`) on x’s ancestors (database, area, file). This prevents conflicting coarse-grain locks from being acquired concurrently.
3.10 Distributed Two Phase Locking
Section 3.10 explains how Strict 2PL makes distributed concurrency control simpler. With Basic 2PL, one site might release locks while another is still acquiring them, which breaks the two-phase rule unless schedulers coordinate. But with Strict 2PL, locks are only released after commit, so once a scheduler sees the commit, it knows the transaction is done acquiring locks. No need to talk to other sites. The TM only sends commit after all operations are done, so this setup guarantees that each site’s local two-phase rule lines up with the global one. Strict 2PL gives you correctness without extra coordination.
3.11 Distributed Deadlocks
Distributed deadlocks arise when the global Waits-For Graph (WFG), formed by uniting local WFGs, contains a cycle even if each local WFG is acyclic. Detecting global cycles requires message exchanges among sites. A site may initiate detection when it sees a potential cycle, collecting dependency information and detecting loops.
A deadlock prevention method is to use timestamps. When a transaction T1 is about to wait for T2, the system checks their timestamps. If the wait would lead to a possible deadlock, it aborts one of them.
- In wait-die, older transactions wait for younger ones; younger ones abort if they encounter older ones.
- In wound-wait, older transactions preempt younger ones by aborting them; younger transactions are allowed to wait for older ones.
Wait-die favors younger transactions but can cause repeated aborts; wound-wait favors older transactions and avoids starvation.
3.13 Tree Locking
Suppose data items are structured as nodes in a tree, and transactions always follow tree paths. The scheduler can exploit this predictability using Tree Locking (TL), rather than requiring the grow/shrink discipline of 2PL. That is, a transaction can release a lock and later acquire another, so long as it follows the tree order (root to leaf).
TL resembles resource ordering schemes in OSes for deadlock avoidance. It ensures deadlock freedom. Once a transaction locks all children of a node it needs, it can safely release the lock on the parent. This can improve performance by holding locks for shorter durations. But it only makes sense if transactions follow predictable root-to-leaf access patterns. Otherwise, TL can reduce concurrency among transactions.
TL must also be extended if we want recoverability, strictness, or to avoid cascading aborts. For example, writes should be held until commit. In practice, most updates are on leaf nodes, making this workable.
This is a niche idea, but when applicable, it's elegant. I like it! The section closes by discussing locking in B-trees as an application.
by Murat (noreply@blogger.com)
