How do databases guarantee that two transactions with different isolation levels run concurrently correctly

Question

I wonder how databases guarantee that two transactions with different isolation levels run concurrently correctly. That is, different sessions are allowed to use different isolation levels. For example, one session may use "serializable" and the other may use "read committed". How do databases guarantee that two transactions with different isolation levels run concurrently correctly? I tried to google this topic but could not find any material explaining this topic in detail.

Answer 1

Many algorithms have been developed for this. They fall into two basic categories - optimistic and pessimistic.

I'm going to use slightly different wording to your question. A session is a transport-level connection between the client and the server. A transaction is an atomic unit of work within the DBMS which either fully commits or is fully rolled back. It is a transaction which has an isolation level, so I'll use that term.

Optimistic approaches assume that two transactions will not cause problems for each other. As each transaction reads and writes the system tracks which rows it touched. When the transaction comes to commit, the system checks there is no conflict with other transactions' reads and writes. If all is OK the commit happens. If there is a problem one transaction is rolled back and (probably automatically) re-queued to run again.

Pessimistic approaches assume there will be conflicts and take action in advance, in the form of locks, to prevent them. As a transaction tries to read or write it asks for the corresponding lock. If a previous transaction already holds a lock on that object the new requester waits in a queue. When the current lock holder commits (or rolls back) its locks are released and the next transaction in the queue is granted the lock. In this way each transaction's isolation preference can be respected. This approach is subject to deadlocks, which the system has to detect and break. The various isolation level differ on what locks are taken.

Read Committed need lock only those rows specifically touched by the query e.g. "only row number 5." Serializable, to prevent phantoms, will lock a range of key values e.g. "all rows from 1 to 9 inclusive." You can see that these are incompatible because row 5 is included in both. So whichever transaction started second will have to wait for the other to commit and release its locks.

This is not the whole story, of course. There are a great many nuances and performance and throughput optimisations which have been developed. The Introduction and Advanced courses from Carnegie Mellon on Youtube cover this topic in some detail. I enjoyed them for their pace and visualisations.

It should be noted that there is a whole hierarchy of isolation levels and "stronger" levels imply all the guarantees of "weaker" levels below them. Specifically for this question Serializable includes all the guarantees of Read Committed.