Databases - 2 Phase Locking Concurrency Control

Conflict serializable verifies using either "swapping" method or dependency graphs. View serializable have no efficient way to verify. An example is counting all the number of accounts that got a positive balance.  So, how do we do this stuff in real time? For example, This is not conflict serializable since it's an unrepeatable read. 

So we need a way to do this on a fly. When clients connect to a database, we don't know originally what the queries are going to do, and we can't predict serializability. So we need to be able to have parallelism as well as guaranteeing isolation. This is because we're going to have to ask for permission from the system before every operation. Before we read or write on a tuple, we're going to have a lock. 

Here, before we read on a, then we have to enforce the lock protocol on a system. T1 is going to request a lock, gets a lock, T2 then begin , then lock on A because eventually will do a read and write, T1 proceeds, does write, does read, get lock then T2 do what it needs to do, then releases a lock. 

Today, we'll go through 2 basic lock types, go through two-phase locking, figure out how to reason about deadlocks, and introduce the notion of hierarchical locking. 

Locks are NOT the same thing as Latches. Latches protects threads, Locks protect logical constructs of the databases, preventing transactions from conflicting each other. We can reason about what operations were doing with latches so we know what order things are going to go. Locks we can't do this because we don't know what order the transactions are going to run, since it's pretty easy to put the system into a deadlock. 

Shared locks are used for reads, and exclusive locks are used for writes. Transactions request locks and the lock manager grants or block requests and the lock manager updates its internal lock table. Probably uses a hash table and a queue. 

Here, the locks are first of all give then released sequentially. 

Two-phase locking is a concurrency control protocol that determines whether a transaction can access object in the database, and we don't need to know if transactions can run in order to figure out if it is conflict serializable or not. Turns out it's a pretty good idea, and most systems use it to this day. 

The growing phase of a transaction has each transaction requests the lock that it needs and has a lock manager that grants/denies requests. 

Shrinking is the concept which transaction is allowed to only release locks previously acquired, and that it cannot acquire new locks. The transaction cannot acquire/upgrade locks after the growing phase finishes, the second it releases a lock for example. Lock manager will stall the process until the lock is finally available. The great thing about 2-phase locking is it guarantees conflict serializable schedules, but the problem is it is subject to cascading aborts. 

Let's say in this scenario that is aborted. If one thread with a lock will abort, this means that the other thread needs to abort as well, and this is a major problem because it is wasting a lot of work. Here, any information from T1 cannot be "leaked" from the outside world. 

There are schedules that are serializable that 2-Phase locking won't allow, since it is a bit conservative. We might still have dirty reads or deadlocks, and we need a stronger 2-phrase locking/prevention, acquiring the locks in a specific way to guarantee that we never get into a deadlock. 

In Strong strict 2 phase locking, the transaction is not allowed to acquire/upgrade locks after phase finishes. It allows only "strong" conflict serializable schedules. Here, we release everything at the end of the transaction. A schedule is "strict" if a value written by a transaction is not read or overwritten by any other transaction until that transaction finishes. The advantages is that it doesn't incur cascading aborts, since aborted transactions only need to put back their value. 

In 2-phase locking before unlocking lock A here, the thread acquires the lock at B.

In strong 2-phase locking, T2 has to wait the entire time and forcing a serial ordering. 

Here's the universe of Serializability: 

2-Phase locking generate conflict serializable schedules, but it's going to be suspected for cascading aborts. What we can do is build a waits-for graph where nodes are transactions. The system periodically checks for cycles in wait-for graph, then decides how to break it. 

Here T1 gets an edge point to T2, T2 goes to T3, and T3 goes to T1, and here we will have a deadlock. So, deadlock handling is simple: 

Pick a victim, then kill it. First choose a transaction, then roll back. The victim transactions will either restart or abort depending on how it was invoked. There is a tradeoff between frequency of checking for deadlocks and how long transactions have to wait before deadlocks are broken. Selecting a proper victim depends on lots of variables. 

One thing we can try is by age (lowest timestamp), by progress (most/least queries executed), how many locks hold, how many transactions we have to rollback (in cascading aborts). We will later talk about which transaction gets killed.  After selecting a victim transaction to abort, the Database can also decide on how far to roll back, ether partially or completely. 

For demo

SET GLOBAL innodb_lock_wait_timeout = 10; 

BEGIN; 

SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE; 

BEGIN

UPDATE txn SET val = val + 1 WHERE id = 1 (set lock on id 1);

UPDATE txn_demo SET val = val + 1 WHERE id = 2; (b set lock on id 2, we have to wait here)  

Other Terminal: 

UPDATE txn_demo SET val = val + 1 WHERE id = 2; (a, set lock on id 2) 

UPDATE txn_demo SET val = val + 1 WHERE id = 1; (c, set lock on id 1 but we have deadlock on here as the first transaction not complete). 

T2 is never written tot he table since it didn't commit, and as a result, T1 is never going to make full progress. Strong strict 2-phase locking is what we need to do if we don't get any dirty reads. 

Postgres tells us what process something is taking up the particular lock. The alternative to doing detection is ever preventing deadlocks in the first place. You can have old die(old waits for young) or wound wait (young waits for old) transaction priority system. Wait-die is if the requesting transaction has higher priority than holding transaction, then it waits for holding transaction, otherwise, this transaction aborts. 

In wound-wait, if requesting transaction has higher priority than holding transaction then the holding transaction aborts and releases lock. Otherwise the requesting transaction will wait. 

When a transaction restarts, what would its new priority be? it's got to be the original timestamp.This is due to starvation, its original timestamp. So far, this doesn't seem very efficient. How do we update 1 billion tuples? Going through a lock manager 1 billion times isn't cheap at all. What we are going to try is to change the granularity of the system. If there are a billion updates, then you might have to use a single lock!

Conceptually, you can now take locks at many different locations inside of the system. Here if T1 takes lock at Table 1 it will take the locks that are children of it. It's sort of a conceptual hierarch of the system. In intention locks, you give hints to other transactions into what you're doing at lower levels, increase the parallelism with the system.

An intention lock allows a higher level node to be locked in shared or exclusive mode without having to check all of the descendant nodes. This means explicit locking is done at a lower level of the tree. 

A shared intention exclusive lock is an explicit shared lock. The subtree rooted by node is locked explicitly in shared mode and explicit locking is being done at a lower level in exclusive-mode locks. In order to get a shared lock, you have to hint at least to the parent node that you have intention for a shared lock. Here's an example;

Here, andy wants to do a read  at Tuple 1 but we need to take an intention shared on Table R and explicit share. Then in T2, then we want an explicit exclusive lock on T2, so we're going to try to get intention exclusive lock on the parent node and exclusive lock on the individual tuple. 

Shared intention exclusive is taking a shared lock on the entire table and updating at least one of those tuples. 

So in practice, it's pretty helpful because you can reduce the number of lock requests dramatically, and there's a concept of lock escalation. This is designed to reduce the number of trips to the lock manager. In practice, you're not sitting there telling which tuples to lock. Maybe you can give hints for concurrency: LOCK TABLE <table> IN <mode> MODE; The most widely deployed commercial system is 2PL and gives us our serializable schedule. We just have to be disciplined in whether to detect deadlocks or prevent them in the first place.