Published: 2011-11-12
Tagged: acid, isolation, lost update problem, postgresql, transactions

I will introduce the lost update problem in the context of transactions in this post.

The lost Update Problem in the Context of Transactions

The lost Update Problem

Consider the case where two users are about to update the same row/document in some data store. For example, let user A retrieve some row first. After that, assume that user B retrieves the same row; however, B writes his update immediately, and in particular before A writes his update. Then, the changes made by user B are silently overwritten by the update performed by user A. This is known as the lost update problem. It is depicted on the left hand side in the figure given below.

no lost update 01

Transactional Context

The delineated problem has an interesting twist in the light of transactions as implemented in most relational database systems.

Let us consider the same order of events as before, but wrapped inside of transactions, as depicted in the figure above on the right hand side. We might expect, that the write operation performed by user A will trigger an exception and his operations are rolled back. I suggest that you test this in your favorite RDBMs. A demonstration is given as as "Demo 1: The Lost Update Problem" in the screencast included on the very bottom of this page. We witness that the write operation just passes through, again silently overwriting the previous update.

We will discuss the reason of this behavior. However, let us first examine a slightly changed order of commands as depicted in the next figure below.

no lost update 01

Now, let us consider the case where user B reads and writes before user A performs any of his operations. This has, without transactions in place, the desired and expected result. However, things can be different when both users start a transaction before any operation, and commit the transaction after all operations. Then, the update of user B is lost! A demonstration is given in "Demo 2: Bad Transaction" below.

Transactions and Isolation Levels

The letter I in ACID stands for isolation and essentially symbolizes that all transactions should run in complete ignorance of each other. This isolation refers to writes but in particular also to reads of data which might have been changed by other, concurrently ongoing transactions. From this viewpoint, the behavior shown in our second example "Bad Transaction" is absolutely correct. User A should not read the changes made by user B because they are not committed yet. Otherwise, user A would read state that is pending for further overwrites or even possible rollback. Such reads are known as Dirty Reads and are a very undesirable behavior in almost every case.

Our little example demonstrated that isolation is not a trivial property; and, in fact, there are several levels of isolation specified in the ANSI/ISO SQL standard. They are listed below:

  1. Read Uncommitted
  2. Read Committed
  3. Repeatable Read
  4. Serializable

The level Read Committed prevents Dirty Reads. It is the lowest and default level that is implemented in PostgreSQL. The exact behavior of the isolation levels is sometimes not as easily understood as their names suggests, and several anomalies are known to exist (Berenson et al. 1995).

Now, the only level that would prevent lost updates is the highest level Serializable. The last demonstration "Rollback", which uses this level, shows how the update of user A raises an exception and a rollback is forced on the final commit.

The Price of Isolation

The question arises why PostgreSQL, and also SQL Server as well as Oracle® 11g, set Read Committed as default instead of Serializable. The answer is quite simple: complexity of the implementation which imposes a certain amount of overhead and possibly bad performance. The official PostgreSQL 9.1 documentation goes further into detail, but essentially it boils down to real locking, as well as discovering and preventing deadlocks.

Lost Updates in (Web-) Applications

So, imagine we made our analysis and decided, that there are a few updates in our application that we would like to be protected against lost updates. The costs of isolation are acceptable since those writes happen rather rarely. Consequently, we employ the Serializable level, and we are done. Wrong: this approach will not even work in the context of web applications, and it is otherwise most likely a poor design choice. I will discuss this and show a solution in the next post.

Conclusion

The usage of transactions does not conclusively specify the semantics of operations. The level of isolation must be taken into account.

Appendix

Ѕcreencast Demonstration

The following screencasts demonstrate the Lost Update Problem in three examples:

  1. Demo 1: Lost Update (00:04)
  2. Demo 2: Bad Transaction (01:10)
  3. Demo 3: Rollback (02:08)

All demos are preformed within the psql shell of a PostgreSQL 9.1 Database.