The theoretical models defined in 15 - Concurrency control theory assume we know upfront all read and writes in transactions to construct a schedule, but this is not true. We need to construct a serializable schedule on the fly.
Database locks are used to generate such a schedule, and a centralized lock manager decide whether a transaction can acquire a specific lock or must be stalled. There are two basic types of lock:
- Shared locks (S-LOCK): Multiple transactions can read the same object at the same time, so they can all acquire the same shared lock
- Exclusive Lock (X-Lock): An exclusive lock allows a transaction to modify an object: therefore it can be held by a single transaction at the time and stops other transaction from taking any other lock on the object.
Important
The lock manager maintains a lock table to track which transaction are holding locks and which transactions are waiting for them. The lock table can be lost on crash since any transaction that is still running should be considered non committed, and automatically aborted upon rn restart
2 Phase Locking
Two phase locking is a pessimistic concurrency control that uses locks to determine whether a transaction is allowed to access an object in the database on the fly:
- In the growing phase each transactions require the locks it needs from the lock manager
- In the shrinking phase each transactions can only release locks. Transactions enter the shrinking phase after they release their first lock.
Cascading abort
2PL guarantees conflict serializability but when a transaction abort, another might be rolled back, resulting in wasted work. It can also lead to dirty reads and deadlocks
Strong 2 Phase Locking
A schedule is strict if any value written by a transaction is never read by another transaction until the first transaction commits: this can be achieved by releasing locks at commit time. This prevents cascading aborts but has a lower concurrency.
Deadlock handling
A deadlock is a cycle of transactions waiting for locks to be released by each other. A classic example of a deadlock occurs when Transaction 1 holds a lock on resource A and needs resource B, while Transaction 2 holds resource B and needs resource A. There are two approaches to handling deadlocks in 2PL:
- detection
- prevention.
Detection is typically done checking periodically the wait-for graph to identify cycle. When a cycle is detected, a victim transaction is selected and restarted or aborted depending on how the application had invoked it.
Prevention is done at lock acquire time: when a transaction try to acquire a lock acquired by another transaction, that DBMS can kill one transaction based on assign priorities(i.e. start time). The idea is that only one of type of direction (i.e. lower priority transaction waiting on higher priority): if a transaction tries to acquire a lock owned by a lower priority transaction, the lower priority transaction gets killed (wound-wait) while if the holding transaction has higher priority, the current transaction waits (wait-die)
Lock granularity
If a transaction wants to update one billion tuple, does it ask the DBMS lock manager for billion locks?. Does a transaction that needs to update a single tuple lock the entire table?
DBMS uses a lock hierarchy with different granularity levels: when a transaction acquires a lock at a certain level, it implicitly acquires the locks for all its children (i.e. acquiring a lock on a table implicitly acquires a lock on each tuple). A typical lock hierarchy is the following:
- Database level (rare)
- Table level (very common)
- Page level (common)
- Tuple plevel (very common)
- Attribute level (rare)
Intention locks
If a transaction is using tuple-level locks, it needs to communicate that no other transaction can crab a page-level lock or anything higher. Intention locks are implicit locks that indicates an explicit lock at a lower level:
- IS (Intention Shared): Indicates a transaction intends to acquire shared locks at a lower level.
- IX (Intention Exclusive): Indicates a transaction intends to acquire exclusive locks at a lower level.
- SIX (Shared and Intention Exclusive): Indicates a transaction holds a shared lock at the current level and intends to acquire exclusive locks at a lower level
For example, when a transaction tries to modify a record, the lock manager acquires first an IX lock on the table and an X lock on the tuple. Since this is all done transparently from the developer, this is called implicit