整理自CSE 444 Database Internals, Spring 2019 的课程Lectures，课程地址：https://courses.cs.washington.edu/courses/cse444/19sp/

Lectures 14 Transactions: Locking

---

Scheduler

The scheduler:

  Module that schedules the transaction’s actions, ensuring serializability

  Two main approaches

•   Pessimistic: locks  
•   Optimistic: timestamps, multi-version, validation

Pessimistic Scheduler

Simple idea:

• Each element has a unique lock
• Each transaction must first acquire the lock before reading/writing that element
• If the lock is taken by another transaction, then wait
• The transaction must release the lock(s)

Notation

 

Two Phase Locking (2PL)

The 2PL rule:

• In every transaction, all lock requests must precede all unlock requests
• This ensures conflict serializability ! (will prove this shortly)

Example with Multiple Transactions

Theorem: 2PL ensures conflict serializability

 

Strict 2PL

Strict 2PL: All locks held by a transaction are released when the transaction is completed; release happens at the time of COMMIT or ROLLBACK

Schedule is recoverable

Schedule avoids cascading aborts

Summary of Strict 2PL

• Ensures serializability, recoverability, and avoids cascading aborts
• Issues: implementation, lock modes, granularity, deadlocks, performance

 

The Locking Scheduler

Task 1: -- act on behalf of the transaction

Add lock/unlock requests to transactions

• Examine all READ(A) or WRITE(A) actions
• Add appropriate lock requests
• On COMMIT/ROLLBACK release all locks
• Ensures Strict 2PL !

Task 2: -- act on behalf of the system

  Execute the locks accordingly

• Lock table: a big, critical data structure in a DBMS !
• When a lock is requested, check the lock table  – Grant, or add the transaction to the element’s wait list
• When a lock is released, re-activate a transaction from its wait list
• When a transaction aborts, release all its locks
• Check for deadlocks occasionally

Lock Modes

Lock Granularity

Fine granularity locking (e.g., tuples)

• High concurrency
• High overhead in managing locks

Coarse grain locking (e.g., tables, predicate locks)

• Many false conflicts
• Less overhead in managing locks

Deadlocks

Cycle in the wait-for graph:

• – T1 waits for T2
• – T2 waits for T3
• – T3 waits for T1

Deadlock detection

• – Timeouts
• – Wait-for graph

Deadlock avoidance

• – Acquire locks in pre-defined order
• – Acquire all locks at once before starting

Phantom Problem

• So far we have assumed the database to be a static collection of elements (=tuples)
• If tuples are inserted/deleted then the phantom problem appears

 

A “phantom” is a tuple that is invisible during part of a transaction execution but not invisible during the entire execution

In our example:

• – T1: reads list of products
• – T2: inserts a new product
• – T1: re-reads: a new product appears !