Snapshot Isolation Level
In my previous post about isolation levels, we read about the Read Committed isolation level. We saw what are dirty reads and dirty writes and how the Read Committed isolation level grants us protection from those issues by aborting the transaction in case of violation.
From the looks of it, one may say that we have solved all the concurrency issues possible. Then why the need for a stronger isolation level?
An Example Scenario
Let us take an example scenario. Suppose you have two user accounts in the same bank. Both accounts have the same amount of INR 40,000. Now, let us say you have to pay an academic fee of INR 50,000. Thus, you decide to transfer INR 10,000 from one account to another, and then transfer INR 50,000 from that account to the academic institution.
Thereafter, you submit the transfer request of INR 10,000 from account 1 to account 2, and now you are observing both your accounts (via read queries). Let us say the read queries submitted by you (as part of a single transaction, say t1) are:
t1.r1 = select balance from account where account_id = 1;
t1.r2 = select balance from account where account_id = 2;
Moreover, at the same time, the bank database has to run 2 write queries corresponding to the transfer request that you placed. Let us say these two queries form part of another transaction t2. The queries corresponding to t2 shall be:
t2.w1 = update account set balance = balance + 10000 where account_id = 1;
t2.w2 = update account set balance = balance — 10000 where account_id = 2;
Suppose the order of execution of these queries is as follows:-
t1.r1 (select balance from account where account_id = 1)
> returns Rs. 40,000 (acc1: Rs. 40000, acc2: Rs. 40000)
t2.w1 (update account set balance = balance + 10000 where account_id = 1)
> (acc1: Rs. 50000, acc2: Rs 40000)
t2.w2 (update account set balance = balance — 10000 where account_id = 2)
> (acc1: Rs. 50000, acc2: Rs. 30000)
t2.commit -> X
t1.r2 (select balance from account where account_id = 2)
> returns Rs. 30,000 (acc1: Rs. 50000, acc2: Rs 30000).
t1.commit -> X
Thus, as a user, you will see that in total, you have 10,000 missing (t1.r1 gave you 40k and t1.r2 gave you 30k). These kinds of anomalies are called non-repeatable reads. Another term used for these concurrency issues is “read skew”. Thus, as we saw, despite avoiding dirty reads, we still got a concurrency issue. It is called non-repeatable because this read is caused by a very specific, temporary read. It might be that this read is not possible again, thus making it non-repeatable.
One might probably contend that this is not a very big issue. You can re-read the non-repeatable read and this would be solved (as you will again see the account balance as 50k and 30k). But consider the case of long running queries, (like database backup or time consuming analytical queries) which might encounter this problem. In those cases, it would be a huge problem. Why? Considering the above case, suppose the database gets backed up with the balance for acc1 and acc2 as 40k and 30k (database backup uses read queries, and while reading, it saw the same values as the user), and after the backup, database crashes and we restore it using the same backup. In that case, INR 10,000 of your user will seem to have vanished into thin air.
Solution to the Above Problem
The above-mentioned problem occurred because while executing a read transaction, we did not take other ongoing write transactions into account. We returned the committed result of t2 to t1 without taking the fact into consideration that t2 occurred after t1. This is an issue with Read Committed isolation level. Had we considered the fact that the transaction t1 (the transaction that read both the accounts) happened before the transaction t2 (the transaction that transferred the balance from one account to another), then we would have known that since t1 occurred earlier, it must be returned the value which is consistent till t1 (that is, the values which are the fact when t1 starts). If those points were considered, then we would not have had the above problem.
This is taken care of in the second isolation level i.e., Snapshot Isolation. Thus, snapshot isolation makes sure that any transaction only reads from a consistent snapshot of the database.
Snapshot Isolation and Repeatable Read
Before starting the discussion, let’s clear the air about the naming confusion surrounding Snapshot Isolation level. Different Databases refer to Snapshot Isolation level by different names. Oracle database refers to Snapshot Isolation as serializable, and PostgreSQL and MySQL calls this level as repeatable read. But for uniformity and simplicity, we shall be calling this level as Snapshot Isolation.
Snapshot Isolation works on the principle that a transaction reads from a consistent snapshot of the database. The difference between Read Committed and Snapshot Isolation is the read transaction. The database usually uses the same way to deal with writes as it did for repeatable read problem, that is, It just locks the object for transaction level, so that no other transaction can write.
The implementation change occurs at read level. We need a consistent snapshot of the database just before the start of any transaction. Now, the database has no idea about a transaction (say t1) at the beginning. It might take a few seconds for t1 to complete and in that time, t1 may read objects which other concurrent transactions (say t2,t3,t4,…) might change. Till now, the database has no mechanism to track these changes.
But, in order to take a consistent snapshot of the database, the database starts to record every change made to any object. In order for t1 to have a consistent snapshot, the database needs to preserve all the values corresponding to all the rows (or object) so that the corresponding old values are available for t1. Thus, the database needs to store all the changes that are corresponding to any row/object. In short, we need to snapshot every object change. We call these changes as versions.
We store all these versions corresponding to any row, and based on the order of transaction, we return the row version which seems appropriate. This approach is called “multi-version concurrency control (MVCC)”. Thus, the database uses MVCC to implement snapshot isolation and subsequently avoid non-repeatable read (or read skew) problems.
It is noteworthy that if instead of taking transaction level snapshot, we can take query level snapshot, we get repeatable read implementation. Thus, databases which implement both the isolation levels (repeatable read and snapshot isolation) use MVCC for both.
Multi-Version Concurrency Control (MVCC)
We can take an example to understand the implementation of MVCC in PGSQL.
Let us take the above example (debit of 10,000, credit of 10,000 into bank account) and see how PGSQL would deal with such a problem in snapshot isolation level:
When any transaction is started, it is given a unique, always-increasing transaction id. Thus, let us give both the transactions (one consisting of 2 reads, and the other consisting of 2 writes) a unique always-increasing id. Since the read query started first, let us say:
Read Transaction (to read both accounts, t1) -> txnId: 132
Write Transaction (to write to both accounts, t2) -> txnId: 133.
Now, another point that MVCC ensures is that each row maintains its changes. For this, what we do is that whenever a row is changed, we create a new row corresponding to that write instead of updating the row. Other than that, we also track the transaction id creating or deleting that row.
Suppose at the beginning of the transactions, the database state is as follows:-
r1.v1 → Account_id:1, balance:Rs. 40000 (created by: 102, deleted by: null)
r2.v1 → Account_id:2, balance: Rs. 40000 (created by 97, deleted by: null)
This nomenclature (r1.v1) means the r1 row’s v1 version was created by a transaction with txnId: 102 and till now, it is not deleted.
Similarly, r2.v2 means that r2 row’s v1 version was created by a transaction with txnId: 97 and till now it is not deleted.
Now, let us consider the same order of transaction:
t132.r1: select balance from account where account_id = 1;
> returns INR 40,000;
t133.w1: update account set balance = balance + 10000 where account_id = 1; (acc1: INR 50,000, acc2: INR 40,000)
The table “account” will be as follows after this step:-
r1.v1 → Account_id:1, balance: INR 40000 (created by: 102, deleted by: 133)
r1.v2 → Account_id:1, balance: INR 50000 (created by 133, deleted by: null)
r2.v1 → Account_id:2, balance: INR 40000 (created by: 97, deleted by: null)
Now, the following query executed:
T133.w2: update account set balance = balance — 10000 where account_id = 2; (acc1: INR 50000, acc2: INR 30000)
The table “account” shall be as follows after this step:-
r1.v1 → Account_id:1, balance: INR 40000 (created by: 102, deleted by: 133)
r1.v2 → Account_id:1, balance: INR 50000 (created by 133, deleted by: null)
r2.v1 → Account_id:2, balance: INR 40000 (created by: 97, deleted by: 133)
r2.v2 → Account_id:2, balance: INR 30000 (created by: 133, deleted by:null)
Then, the transaction t2 commits.
t133.commit -> X
t132.r2 select balance from account where account_id = 2
> returns 40000. **
t132.commit -> X
- *: Returns 40000 because the transaction demanding the read has txnId: 132. We have 2 versions for r2 (v1 and v2). We will return the version which occurred before 132 (for consistency). Thus, we return r2.v1 (created by: 97 (<132)) instead of r2.v2 (created by 133 (>132)).
Note that a read transaction will not be blocked by any write transaction under snapshot isolation.
Conclusion
In the current post, we read about how we can have read-skew issues while using Read Committed isolation level. We then went on to see another weaker transaction isolation level: Snapshot Isolation. We saw how it helps solve the read-skews by introducing ways for the database to keep versions of all changes to an object.
It seems that all concurrency issues must be solved by now. But then why the need of a Serialisable isolation level? We will see it in the next post.
For a deeper understanding of the subject matter, please refer the book mentioned in bibliography. Note that this post is part of the series on Transactions:-
Bibliography
Kleppmann, M., 2017. Designing data-intensive applications: The big ideas behind reliable, scalable, and maintainable systems. O’Reilly Media, Inc.
