Locks
Use locks to guarantee that all schedules are serializable without knowing the entire schedule ahead of time.
Locks isolate user transactions while latches isolate threads.
Lock execution
- Transaction requests lock (or upgrades).
- Lock manager grants or blocks requests.
- Transaction releases lock.
- Lock manage updates the internal lock-table.
Two-phased locking (Pessimistic protocol)
- Growing - Transaction requests all the locks it need. (Cannot unlock during growing phase)
- Shrinking - Transaction is allowed to only release or downgrade locks that it previously acquired. Shrinking phase is entered immediately after the first lock is released.
Subjected to cascading aborts which is a performance issue. For example, an abort of one transaction will cause other transactions to abort too.
To avoid dirty reads (reading uncommitted data), we use strong strict 2PL which only release the exclusive locks at the end of transactions. It can release shared locks during the shrinking phase. (In rigorous 2PL, both shared and exclusive locks are held till commit/abort)
Universe of schedules
Deadlock detection
Background thread that builds waits-for graph to keep track of what locks each transaction is waiting to acquire.
When detected, a "victim" transaction is restarted or aborted (more common) to break the cycle.
Trade-off between frequency of checking for deadlocks and how long transactions wait before deadlocks are broken.
Deadlock prevention: When a transaction acquires a lock, if it is already held, kill one of them.
Wait-Die - If requesting transaction has higher priority, it waits for holding transaction. If it has lower priority, aborts.
Wound-Wait - If requesting transaction has higher priority, holding transaction aborts and releases lock. If it has lower priority, it waits.
Lock granularity
Trade-off between parallelism and overhead. DBMS should hold the fewest locks that a transaction needs.
Every transaction holds all the locks as they go down. For example, if you have a tuple lock, you also have the table lock.
Intention lock
Intention-shared - There is some transaction in shared lock at lower level.
Intention-exclusive - There is some transaction in exclusive lock at lower level.
Shared-intention-exclusive - Node is locked in shared mode and there is some exclusive locking at lower level.
Intention lock protocol
To get S or IS lock on a node, transaction must hold IS on parent node. To get X, IX, SIX on a node, must hold at least IX on parent node.
- T1 - Scan table R and update a few tuples.
- T2 - Read a single tuple.
- T3 - Scan all tuples in table R.
Lock escalation
DBMS can switch to coarser-grained locks when transaction acquires too many low level locks.