Transactions: Two-phase Locking – Distributed Computing Musings

Two-phase locking(2PL for short) is one of the most well-known algorithm for serializability. Note that it is totally different concept from two-phase commit even though both these concepts sound confusingly similar.

Two phase locking makes use of lock in a much stricter manner. It allows multiple transactions to read a resource as long as nobody is updating the resource. As soon as an update operation is detected on a resource, it is locked for other transactions. In other words, for any form of modification of a resource an exclusive access is required. So if a transaction is reading the object and another transaction tries to modify it then it is blocked until the first transaction is finished and vice versa.

We saw in snapshot isolation that readers don’t block writers and writers don’t block readers. In the case of 2PL, we do the exact opposite. A read will block a write and a write will block a read. 2PL is used by MySQL(InnoDB) for providing serializable isolation levels.

Implementation of Two-phase commit

Before diving into the implementation of 2PL on database level, let’s try to understand 2PL with a real life example. Consider an example of a children’s park which contains a lot of swings.

Children can come in and play on the swings. Note that they are just playing with the swings but not changing the shape or functionality of any of the swings.
With time these swings will require maintenance or even new swings need to be installed or defected swings need to be removed. This requires a maintenance worker to come in and perform the updates on the swings so that they remain functioning in the long term.
Now a maintenance worker cannot perform their work if there are children already playing in the park.
At the same time if a worker has started with maintenance work then children cannot enter the park to play until the maintenance is finished.
So the worker has to wait for all children to finish playing and at the same time all children have to wait until the maintenance is finished to resume playing.

Now let’s see how the above example translate to implementation of 2PL on databases.

On a database level, for 2PL we have a lock on each object in the data store.
Lock can be in two modes.
- Shared mode (Children playing)
- Exclusive mode (Worker performing maintenance)
For read operation, a transaction has to first acquire lock in shared mode. Multiple transactions can acquire lock in shared mode but no one can acquire the lock in shared mode if another transaction has acquired the lock in exclusive mode.
Vice-versa for acquiring locks in exclusive mode. If a transaction has already acquired lock in shared mode then the transaction trying to acquire lock in exclusive mode needs to wait.

With above criteria we can easily end up in a deadlock scenario where:

Transaction T1 acquires lock in exclusive mode for objectA and tries to acquire lock in shared mode for objectB
Transaction T2 acquires lock in exclusive mode for objectB and tries to to acquire lock in shared mode for objectA
Both transactions are stuck waiting for each other to release the lock and hence we end up in a deadlock.

In such situations, databases automatically detect the deadlock and aborts one of the transactions. This decision is based on various criteria such as priority, timeout etc. The aborted transaction is retried by the client. One such example is deadlock handling in InnoDB

Variations of Two-phase lock

There are some other flavors of lock used by 2PL such as:

Predicate Lock: Instead of locking a single record, lock all records that match the predicate condition. Example meeting rooms available between 1:00-2:00PM.
Index Range Lock: Finding all records that match the predicate can become time consuming. Instead we can fall back on the database index to lock all records using the index. So for above example we can book all slots for a particular room if we have an index on room_id

Performance issues with Two-phase locking

2PL has not been so favorable when we look at the performance side of things. Even though it ensures that we don’t face the issues due to concurrency which we have discussed so far, it doesn’t fare well for a performance sensitive application. A lot of latency is induced by the process of acquiring and releasing locks.

In addition to this, 2PL doesn’t allow concurrent transactions to update the same resource simultaneously. So if two clients are concurrently trying to update the same resource then one of the transaction is blocked until the other transaction is finished. Also if a long running transaction is aborted due to being in deadlock then it needs to be restarted and all the previous computation is lost. If such deadlocks are frequent due to access patterns of the application then it will result in increasing the latency of endpoints by multi-fold.

So we have seen that 2PL solves all our problems that arise due to concurrent transactions but if our system requires scalability then it might not be the best choice. Do we really need to choose between being correct & being fast? Probably not. There is a middle ground i.e. Serialized snapshot isolation. Let’s see how it performs in terms of correctness compared to weaker isolation levels and how well it scales when compared to the 2PL algorithm in the next post.