A-Z of Database Transactions (Part-3)

Lost write, Write skew are conflicts that can occur in concurrent transactions

In Part-1 of this series, I shared my views on A.C.I.D safety guarantees. Then in Part-2, we dug into various isolation level guarantees and different read issues in the concurrent environment. I have largely untouched issues corresponding to concurrent writes, except for dirty write. In this Part-3, I will examine those issues.

Lost updates

A lost update can occur if an application first reads a value from a database, then modifies it and finally write it back to the database (read-modify-write cycle) If two transaction does this concurrently then write by one of the transaction can be lost, because the second transaction overwrites modifications done by the first transaction.

This issue is fairly trivial in the following scenarios :

• Reading current account balance from a database, calculating a new value from the last read, then update a new value into the database
• Reading JSON document from a database, adding a new field and then updating the whole JSON document in the database
• Multiple user trying to book same meeting room concurrently. First, they check for any unbooked slot, then they send an update request to book this unbooked room concurrently

Figure-1, shows how client-2 update overwrites the update of client-1

Figure 1. Lost update

Preventing Lost updates

There are several techniques employed by databases to prevents lost update. Following are few of those techniques :

Atomic Writes

Read-Modify-Write cycle written in application code was at fault for the lost update. Several RDBMS provide atomic update operations in a database for a safe concurrent write operation.

UPDATE account SET balance=balance+10000 where user_id=123

Similarly, in document databases like MongoDB, present atomic operations to perform local modifications to a part of the JSON document.

Atomic operations are performed by taking an exclusive lock on the object when it is read so that no other transaction can read it until the update is done.

Explicit Locking

If the database doesn’t provide atomic write functionality then an application can explicitly lock objects that it is going to update. Once a lock is taken application can perform a read-modify-write cycle. Any other transaction is forced to wait until the lock is released by the transaction.

BEGIN TRANSACTION;

SELECT * FROM account WHERE user_id=123 FOR UPDATE;

//Check whether balance in account_number=1 > 1000

UPDATE account SET balance=20000–1000 WHERE account_num=2 AND user_id=123;

UPDATE account SET balance=20000+1000 WHERE account_num=1 AND user_id=123;

COMMIT;

FOR UPDATE clause advises database to take locks on all rows returned by this query. This certainly works, but care should be taken by the application to release locks after the commit.

Compare-And-Set

Atomic writes and explicit locks prevent lost updates by forcing read-modify-write cycles to proceed serially. If the database doesn’t provide transactions, then compare-and-set can be used to prevent lost updates.

Compare-And-Set prevents lost updates by allowing a write to happen only if the value (or object) hasn’t changed since the last read. If the value doesn’t match with what previously was read, then the update has no effect and the read-modify-write should be retired.

SELECT balance, last_version FROM account where user_id=123

UPDATE account set balance=20000+10000 , last_version=100+1 where user_id=123 and last_version=100;

Above update first, check whether last_version is 100 or not. This came from the last read(read-modify-write cycle). If last_version is not 100, then the update has no effect else it modifies ‘last_version’ to 101.

Write Skew and Phantoms

In Part-2, I argued about read phantoms that occur in a transaction, when two identical range queries are executed one after another, and the result of these read queries are different. This can happen if a transaction doesn’t take a read lock on all rows that are part of the range query.

A similar, issue can pop up during concurrent writes as well. Like if two different transactions modify some of the data that was part of the last read range query.

We have seen how to avoid dirty writes and lost update. Here we will see techniques to prevent phantom writes or Write skew.

Let’s say we have a meeting room booking application that allows booking a meeting room if there is a room available between in a timeslot with a condition that there should always be a meeting room available (This room is kept in always available mode because CEO can use it to for meeting)

‘Client-1’ first checks how many rooms are available in the time slot between 12:00:00 and 13:00:00. In response he gets two available room. So he knows he can book a single meeting room because he isn’t violating constraint that a meeting room must always be available.

So he proceeds with booking and sends a booking request for room_id=11 and gets a mail after successfully booking room 11.

Concurrently another user, ‘client-2’ tries booking a meeting room and he also gets 2 available rooms in response. Now he immediately sends a booking request for room_id=12 and also gets a mail for successfully booking room 12.

At the end of the transaction, both were able to book meeting rooms but they violated the constraint. This happened because while updating available rooms, none of the transaction took range lock (write).

Figure 2. Phantom write or Write Skew

This phantom write is neither a dirty write nor a lost update as both transaction modified two different objects (room 11 and room 12)

Phantom write is the generalization of a lost update as in lost update different transaction modified the same object but in write skew, they modified different objects.

Preventing Write Skews

Atomic operations cannot prevent write skews though they were able to prevent lost updates.

If the database allows configuring constraints which are enforced by the database (Like unique constraints, foreign key constraints), then this constraint of having at least one room available on database end can prevent phantom writes. However, this approach becomes unmanageable if constraints change dynamically. For example instead of one room being always available, what if you want 3?

Serializable is the best solution to prevent such anomalies. However, it comes at a penalty of performance and not many applications or database vendors can allow such performance degradation.

If Serializable isn’t available then the second best option is to explicitly lock the rows on which transaction depends on. In meeting room booking example it could be the following :

BEING TRANSACTION;

//Take lock on all rows return by following query

SELECT count(*) FROM room WHERE is_available=true and time>12:00:00 AND time<13:00:00 FOR UPDATE;

UPDATE room SET is_available=false WHERE room_id=12 and time>12:00:00 and time<13:00:00;

COMMIT;

FOR UPDATE clause locks all rows returned by the select query

SERIALIZABILITY

Serializability isolation is strongest isolation level. It guarantees that parallel execution of transactions behaves as if they get executed serially. Most databases employ one of these following techniques to impart Serialization

1. Actually executing a transaction in serial order
2. Two Phase Locking
3. Optimistic Concurrency control techniques like Serializable Snapshot Isolation(SSI)

Actual Serial Execution

In this technique, the database executes only one transaction at a time, in serial order, on a single thread. This way no two concurrent transaction side step on one’s work as they are forced to move serially.

VoltDB, H-Store, Redis, and Datomic execute transactions serially. A system with single-threaded execution sometimes works better than a system supporting concurrency as it can avoid coordination overhead of locking. However, it can only use a single CPU core so it’s throughput gets limited.

Such a system usually keep their data in memory for fast executions so as to avoid I/O and thus can achieve quite a good throughput

Two-Phase Locking (2 PL)

This is the most widely used technique for serializability. In two-phase locking, several transactions are allowed to concurrently read the same object as long as nobody is writing to it. As soon as anyone wants to write an object, exclusive access is required.

If transaction-1 has read an object and transaction-2 want to write to that same object, then transaction-2 must wait until transaction-1 commits or aborts (This ensures transaction-2 cannot change the object unexpectedly behind transaction-1’s back)

If transaction-1 has written to an object and transaction-2 wants to read that object, then transaction-2 must wait until transaction-1 commits or aborts(Reading an old version of an object is not acceptable in 2PL)

In 2PL, a writer not only blocks another writer they also block other readers as well. 2PL is employed by SQL Server, MySQL (InnoDB) and DB2. Since 2PL blocks, all reads and writes they don’t perform well in practice

Serializable Snapshot Isolation (SSI)

Weak isolation levels have good performance but are prone to various abnormalities and inconsistencies (Lost updates, write skew, phantoms etc), whereas serial execution doesn’t scale well and 2PL doesn’t perform well.

2PL works is a pessimistic concurrency control mechanism which works on the philosophy that if anything might possibly go wrong, then it’s better to wait until the situation is safe again before taking any step forward. It is like mutual exclusion used by data structures in a multi-threaded environment.

Serial execution takes pessimism to an extreme, by executing everything in a single thread and not even allowing concurrent execution to take place.

Serializable snapshot isolation is an optimistic concurrency control mechanism. Even If something is potentially dangerous with a transaction, it still allows that transaction to proceed, in hope that eventually everything will end correctly.

When a transaction wants to commit, database checks whether anything bad happened (whether isolation was violated), if so the transaction is aborted and has to be retried. Only transactions that executed serially are allowed to commit.

Optimistic concurrency has its fair share of issues. They perform badly if there is high contention (Transactions trying to access the same object), as this lead to a large number of aborts. If the system is already close to maximum capacity then retrying makes system performance much worse.

However, if capacity is high enough and there is low contention among transactions, then this algorithms shines as compared to pessimistic algorithms.

Summary

• Lost Update : When one transaction overwrites the update of another one, data is lost. This usually occurs in a concurrent environment when transaction follows the read-modify-write cycle. Atomic operations, Compare-And-Set and manual lock to an object can prevent this data loss. Serializability isolation also arrests this divergence
• Write Skew and Phantom writes: If a read query in a transaction spans multiple rows (over a range) and another transaction modifies some of these rows, then by the time transaction writes to the database, based on the premise of the last read, then this decision might not turn out to be true. Serializable isolation prevent this anomaly
• Actual Serial Execution: If all transactions are run by a single thread then all concurrent transactions will run serially. Though this hamper performance because of reduced throughput
• Two Phase Locking (2PL) : A transaction blocks all reads and writes to an object it is modifying. This is a huge penalty on performance
• Serializable Snapshot Isolation: A fairly new algorithm which works on optimistic principle. It allows transactions to proceed without blocking and only abort them, in the end, if they are found to be not in serial order.

That’s all folks from Part-3 of this series.
To know more about A.C.I.D safety guarantees, read Part-1 and to enrich your knowledge on database Isolation safety guarantees, read Part-2

Don’t forget to clap if you liked this article!