by Samuel Hack and Sebastian Wachter.

Most people assume that the data coming from a database is correct. For most applications this is true, but when the databases are used in systems where the database is at its limit, this is no longer always the case. What happens if during a query of a value exactly this value is changed by another user? Which entry was first when two users create different values at the same time. Especially in systems where one database server is not enough it is very important to choose the right rules for Isolation and Consistency, if this is not the case it can lead to data loss or in worst case to incorrect values in the application. 

Most database systems promise virtually nothing by default. Therefore it is important to learn what isolation and consistency level the database promises and then adjust it to fit the application.

In this paper we will give an overview of what isolation and consistency levels are, what different levels are available in databases, and what errors can occur in databases. Afterwards we will give a short introduction to the CAP theorem and discuss the problems that it includes for distributed systems.

Isolation Level

Isolation is the separation of individual transactions with the database so that they can be processed in parallel. This is to prevent the temporary values of one transaction from being used in another transaction.

Perfect Isolation

Perfect isolation means that we can process each transaction in parallel and still consider it as a series of transactions that have happened in sequence. This perfect isolation can be achieved relatively easily with locking, but this will result in a loss of performance.  

In the SQL standard this behavior is known as Serializability.

Anomalies in Concurrent Systems

Various anomalies that can occur in databases where transactions are processed in parallel and do not have serializability as isolation level. 

In these examples you can see that these errors require several transactions to access the same values simultaneously. Therefore, the more often these errors occur, the more the database is busy, because then the probability is higher that fields are accessed simultaneously. In addition, many of these errors can be prevented by clean programming.

As an example application we use a course management where people can register for courses.

lost-update anomaly

In a course there is a field in which it is indicated how many seats are still free. When a person registers for a course, this field is read out and then written back in, reduced by one. In this case the person A registers for the course and reads the value 10 from the database. Now person B comes and also registers for the course and reads the value 10 from the database before the person A writes the new value into the database. Person B also writes the new value 9 into the database. In this case the update of person A is lost, so it is called ‘lost update’.

dirty-write anomaly

As with the Lost Update, person A registers for the course. The value 10 is read and then the value 9 is written into the field ‘free seats’. Now person B registers for the course and reads the value 9 and then writes the value 8 into the field. There is a problem with person A, because the person A does not have the prerequisites for the course, the transaction is reversed. This will reset the ‘free seats’ field to the initial value of person A, which is 10, thus simply overwriting the value of person B and causing a ‘dirty write’.

dirty-read anomaly

Now there is another field in the database for the number of participants in the course. If person A registers now, first the value of free seats will be decreased and then the value of participants will be increased by one. So person A changes the value ‘free seats’ from 10 to 9 and in another transaction the two values are read to calculate the capacity of the course. Only now is the value of the participants set from 0 to 1 by person A. In this case, the calculated capacity of the course is one less than it actually is. This reading of variables that are processed in other transactions is called ‘dirty read’.

non-repeatable read anomaly

That the course takes place the course must have at least five participants. Currently the course has four participants. Now it is checked if the course has < 5 participants. For this purpose the value of the participants is read out, currently 4. As there are less than 5 participants all participants are informed that the course will not take place. In the second step it is checked if the course has >= 5 participants. Since one person has registered for the course at the last second, the second check reads the value 5 for the participants and informs all participants that the course is taking place. This behavior is called ‘non-repeatable read’, because in a transaction a value is read twice and this value has different values.

phantom read anomaly

As additional information we want to record what the maximum age is and the average age of the participants in the course. For this purpose, all participants will be read and compared to find out the maximum age. Afterwards all participants are read out again and the average age is calculated. There are 5 people in the course with an age of 20. So the maximum age is 20. Parallel to this process a person at the age of 50 registers. Now the average age is calculated and the average is 25. In the end the average age is five years higher than the maximum age. If new values are inserted during a transaction and affect the transaction, this is called a ‘phantom read’.

write skew anomaly

The provider of the courses is greedy and makes the price of the course more expensive when only a few seats are available. It is defined that the price of a seats in the course must meet this formula: (10*{seats available}) + {price} >= 100). At the end of an order, this formula is used to check if the price is correct. It is also possible to reduce the current price, but the formula must still be fulfilled with the new price.

If now a person registers the formula is checked and currently there are 5 free seats and the price is 100$, so the formula is fulfilled (10*5)+100 >= 100. Only then the number of free seats will be reduced.

At the same time the price will be reduced. From the database is read out that currently there are 5 free seats. Now the formula is checked with the new price. The formula is still fulfilled with the new price of 50$ (10*5)+50 >= 100. The price is reduced to 50$.

Since these two transactions were carried out simultaneously, both have worked with the same values (5 free seats). Therefore both checks of the formula were positive. But after the two transactions the formula is no longer fulfilled (10*4)+50 >= 100. This behavior is called ‘write skew’. If these two transactions would have been executed one after the other, the check would have failed on the price reduction.

SQL Standard

In the standard SQL there are four different isolation levels. These are used by the approvals from the some of the problems described above.

Isolation Level	Dirty Read	Non-repeatable read	Phantom Read
READ UNCOMMITTED	Possible	Possible	Possible
READ COMMITTED	Not Possible	Possible	Possible
REPEATABLE READ	Not Possible	Not Possible	Possible
SERIALIZABLE	Not Possible	Not Possible	Not Possible

The problem is that the levels only refer to three of the above mentioned problems. In addition, serializability is defined further up as perfect isolation. But the table also shows that if the database does not allow dirty read, non-repeatable read and phantom read, but other errors do, serializability is considered to be.

Isolation for distributed Databases

Databases that have isolation level serializable only guarantee that the transactions are performed in some order. This order does not have to be the real order in which the transactions occurred. In the isolation level serializable single server databases prevent the time travel of transactions. With distributed databases systems it is different, it is much more difficult to prevent the time travel of transactions in such systems.

Anomalies under serializability in distributed databases

In distributed database systems running in isolation level serializable, different time travel anomalies can occur.

An online banking system serves as an example of these anomalies.

The immortal write

The user wants to change his username from ‘Hans’ to ‘Peter’. Only when changing the name, the user makes a mistake and specifies ‘Peteeer’ as the username. Then the user corrects the username to ‘Peteeer’. The next time the user logs in to online banking, however, he will see the username ‘Peteeer’ again. Here the database system has decided that the order is as follows: from ‘Hans’ to ‘Peter’ to ‘Peteeer’. This can happen if the two requests to change the username are processed by different database servers and then in the global order the one transaction has travelled back in time. If a write travels back in time this is called an ‘immortal write’.

The stale read

The user has 2000$ in his account. Now he transfers 1000$ to his children. After that it still shows that he has 2000$ in his account. Here is the same as with the ‘immortal write’ which is done in the order of the database system reading the amount of the account before the transfer. A stale read is when a read operation does not return the most recent value. This can happen when the data comes from a database server that is not yet synchronized with the other database servers.

The causal reverse

Now the user wants to transfer 30,000$ from his savings account to his bank account. In his savings account he has exactly the 30,000$ and in his bank account he has 1,000$, but after the transfer he will see a total of $61,000 in his accounts. In the order of the database system, first the 30,000$ was credited to his bank account, then the total value of his accounts are read and finally the $30,000 was deducted from his savings account. The reversal of consecutive writes is called ‘causal reverse’.

Classification of serializable systems

Now a comparing of the system guarantee to the anomalies that are possible under these guarantees.

System Guarantee	Dirty read	Non-repeatable read	Phantom Read	Write Skew	Immortal write	Stale read	Causal reverse
READ UNCOMMITTED	Possible	Possible	Possible	Possible	Possible	Possible	Possible
READ COMMITTED	Not Possible	Possible	Possible	Possible	Possible	Possible	Possible
REPEATABLE READ	Not Possible	Not Possible	Possible	Possible	Possible	Possible	Possible
SNAPSHOT ISOLATION	Not Possible	Not Possible	Not Possible	Possible	Possible	Possible	Possible
SERIALIZABLE / ONE COPY SERIALIZABLE / STRONG SESSION SERIALIZABLE	Not Possible	Not Possible	Not Possible	Not Possible	Possible	Possible	Possible
STRONG WRITE SERIALIZABLE	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible	Possible	Not Possible
STRONG PARTITION SERIALIZABLE	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible	Possible
STRICT SERIALIZABLE	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible	Not Possible

Only ‘STRICT SERIALIZABLE’ protects against all anomalies and prevents any time travel of transactions, but has the worst performance of all guarantee. The performance will be better the less the database guarantees.

Consistency levels

Another important part of data reliability is consistency. Just as with isolation levels a higher consistency level allows a higher reliability on data but comes with the cost of performance and might also add a lot of unnecessary additional complexity to a system.

In this introduction the consistency levels are explained in the context of shared-memory multi-processor or distributed system operating on a single data item at a time.

Database systems nowadays are able to group read and write operations together in atomic transactions which makes it hard to apply these levels to them. After the introduction of the consistency levels a possible solution to said issue will be discussed.

The general goal of consistency is to achieve a state in which all members (threads) agree on the value of the last write on data items.

In the following sub chapters some well-known consistency levels will be discussed.

Eventual consistency

Eventual consistency is the weakest level of consistency in this article. The only constraint it gives is that all members will eventually agree on the value of the last write after a long time without any writes. The definition of  long is system dependant.

Initial values of X and Y are 0:

In this type of diagram the threads of execution P1, P2, P3 and P4 perform read (R) and write (W) operations on the variables X and Y with different values. Time progresses to the right.

This diagram is only valid in terms of eventual consistency because P4 breaks causal consistency (the next higher level of consistency which will be discussed in the next chapter) when it reads Y as 10 while still reading X as 0. 

Only after a long period of time without any writes all threads agree on a consistent state of Y as 10 and X as 5.

Causal consistency

The already above mentioned causal consistency is a higher consistency level than the eventual consistency. 

When a read operation on a variable (call it A) is followed by a write of another (call it B) it assumes that these a connected and places a causal constraint on them. Therefore A has to happen before B which also means that it is impossible to read the write of B without reading the write of A beforehand.

Example (initial values of X and Y are 0):

The difference between this diagram and the one of the eventual consistency (before the long time period without writes) is that P4 now reads X as 5 after reading Y as 10. P2 places a causal constraint with its write to Y after reading X. P3 is able to read X as 5 while still reading Y as 0 because the constraint only links Y to X (X has to happen before Y) and does not work vice versa.

Sequential consistency

Sequential consistency is an even higher level of consistency. Here all writes are globally ordered. It doesn’t matter which thread made the write or which data item got written to. That means if one thread saw some variable (call it A) being written to and then later saw another variable (call it B) being written as well all other threads have to see the write on A happen before the write on B.

If any thread sees the new value of B but also the old value of A the sequential constraint is violated.

Example (initial values of X and Y are 0):

This diagram is sequential consistent because all reads on Y are followed by an read on X with the value of 5. The write on the data item Y happened after the write on X therefore P3 is able to read X as 5 but Y as 0 but P4 can’t because it reads Y first which requires the write of X as 5 earlier.

In sequential consistency it is still possible to see results that differ from what happened in real time. As long as every thread agrees to see the write on B happening before the write to A it is sequential consistent which allows the following diagram to be sequential consistent as well (initial values of X and Y are 0):

Atomic consistency

Atomic consistency is the highest possible consistency level in a distributed system. In contrast to the sequential consistency it imposes real time constraints on writes. That means a reordering of history (possible in a sequential consistent system) is not possible anymore. 

Atomic consistency also acknowledges that it takes time to actually write a data item. A period of time has to pass between the submission of an operation and the response with the completion acknowledgement from the system. In distributed systems this time period may also include the time it takes to replicate data to different locations.

The atomic consistency does not place any ordering constraints upon actions happening with overlapping start and end times. It only places them on operations that do not overlap in time.

Example (initial values of X and Y are 0):

In this diagram P3 is able to read X as 0 because the read operation starts during the write operation on X of P1. Later P4 and P3 are only able to read the values written by P1 and P2 in the correct order as happened in real time.

Strict consistency

Strict consistency is not achievable by any distributed system and therefore mostly of theoretical interest.

In a strict consistent system every thread has to agree on the precise current time (with zero error). The order of the writes must correspond to the real time the commands were issued. A read operation always has to read the value of the most recent write in real time. In distributed systems the global agreement on precise current time is impossible to achieve.

Example (initial values of X and Y are 0):

In this diagram P3 is not able to read Y as 0 anymore (see the diagram of sequential consistency) because it always has to read the value of the most recent write in real time which is 10.

Transactions and consistency levels

Database systems are able to group reads and write of data in atomic transactions. Therefore it is hard to apply the different consistency levels on database systems because they always see read and write operations as singular actions. Neither in literature nor in documentation of DBMS a uniform approach to apply consistency levels in database system can be found.

Daniel Abadi’s approach to incorporate transactions into these consistency models is by adding a boundary with a identifier to each read/write request that initiated that request:

Since transactions are atomic they add additional constraints to the diagram because they either fail or succeed together and are isolated (depending on the isolation level) from other concurrently running transactions. Committed transactions are also durable meaning that all writes will outlive all kind of system failure.

Difference between Isolation levels vs. Consistency levels

Since consistency levels were only designed for single operation actions (read or write not a transaction which might combine both atomically) only having consistency without any form of isolation can cause bugs. Consistency levels do not protect against temporary writes which get rolled back when a transaction aborts or against reads that become stale because of a concurrent write by a different thread. 

Isolation grants that kind of necessary protection. It defines what kind of operations by other threads are allowed (or not allowed) during the time period between the first and last operation of said transaction. Serializable isolation states that only changes that will not cause a visible change in the database’s state are allowed during concurrent transactions.

So once concurrent transactions are possible on a system it might be necessary to think about isolation levels to protect it.

On the other hand having isolation guarantees without any forms of consistency levels might cause bugs as well.

For example a system starts with an empty database that grows over time. In theory it would be possible to return an empty set of data every time when no consistency level is applied. Isolation only guarantees that operations will happen in some serial order. But without any form of consistency guarantee it is completely possible to go back in time in a serializable way.

Isolation only defines what happens during concurrent transactions. If two transactions do not happen concurrently they are already perfectly isolated and no isolation level will specify how they should be processed. This is what consistency guarantees are for.

Higher level consistency levels make real-time guarantees for non-concurrent operations. Even lower consistency  levels make real-time guarantees as long as the operations happen within the same thread.

Therefore you need to think about both isolation and consistency levels when designing your system: Once you have concurrent transactions you need isolation guarantees. If you need guarantees for any non-concurrent transaction you need to think about consistency levels.

CAP Theorem

In the year 2000 Professor Eric A. Brewer formulated the CAP theorem during a Keynote on the ACM Symposium. Seth Gilbert and Nancy Lynch of MIT proved it to be correct two years later.

The acronym CAP stands for the words Consistency, Availability and Partition Tolerance. 

Consistency means that every client sees the same data at every time. Consistency is measured in the time it is achieved. In strict consistency this would be instantly (and therefore considered high consistency) while eventual consistency would happen after a long time without any writes (therefore considered low consistency).

Availability means that all clients are able to perform read and write operation at any time. It is considered as being high when the system is responding fast and low when it is responding slow.

Partition Tolerance means that the system still works when some nodes might become unavailable. Partition Tolerance should always be given in any distributed system.

It is only possible to serve two of these three properties. The resulting possibilities therefore are: CA, PC or AP. These possibilities can easily be remembered with the following image:

Also it is important to notice that systems aren’t entitled to serve two out of three. There are many systems that serve zero or just one of these properties.

In any actual system you should always be interested in high availability. Therefore only CA and AP are the remaining combinations. In distributed systems P should also always be given since you don’t want to rely on centralized services but want globally horizontally scaled distributed independent replications of your services. That’s why the AP combination is the only one that is of practical use in distributed systems – high availability and highly partition tolerant.

For example the DNS (Domain Name System) is such a AP service: it is technically always available (its availability is so high that some people might even forget that it exists) and it is very tolerant towards server failure of singular DNS servers. But it might take days for DNS to generate consistency between all of DNS’ nodes (low consistency).

Conclusion

As you can see the discussion of isolation and consistency levels can get very tedious and theoretical. To make it even harder to specify which level your system needs systems in the real world do not separate between consistency and isolation levels and combine them under the name of isolation level. Also in these systems you mostly aren’t able to mix consistency and isolation levels arbitrarily but are limited to a set of predefined mixtures.

CAP also limits you to only one combination of Availability, Consistency and Partition Tolerance that actually makes sense in terms of a running service: Availability and Partition Tolerance.

Everything discussed here is important to evaluate which technology you should use for your project and how you should configure it to match your guarantee requirements in terms of isolation and consistency levels.

References

https://dbmsmusings.blogspot.com/2019/07/overview-of-consistency-levels-in.html

https://dbmsmusings.blogspot.com/2019/08/an-explanation-of-difference-between.html

https://dbmsmusings.blogspot.com/2019/05/introduction-to-transaction-isolation.html

https://dbmsmusings.blogspot.com/2019/06/correctness-anomalies-under.html

https://www.ibm.com/cloud/learn/cap-theorem