Saturday, October 25, 2008

Optimistic locking vs. pessimistic locking

If you have an education in computer science you typically learned about locking in databases. I was taught that the only safe way to update a database in a multi-user environment is to use a transaction:


  1. acquire a lock on the record

  2. read the current value from the record

  3. calculate the new value

  4. write the new value to the record

  5. release the lock


Simple. Reliable. Safe.

And horribly slow...

Imagine thousands of users concurrently hammering your database. Most of these users will be working on different records. So for most of them, the lock is completely useless. But you're still paying the price for acquiring this lock on every database update. That is why this type of locking is called a pessimistic lock. You assume that multiple people will want to update that same record and prevent them from doing so.

I thought this was the only way to do locking, until I encountered something completely different about 10 years ago. At my company at the time we used an internally built software application to track stock levels of our products. And that application used the pessimistic lock pattern described above. The application worked fine for some time, but as it got more users it started to have more and more performance problems. I was brought in as part of a team to solve those problems. I immediately went to work on some of the heaviest operations and was able to bring startup performance back to acceptable levels in a few days. But the updates to the database were still going as slow as ever.

That's when the technical lead of my team came with an interesting suggestion. "Why don't we remove the database locks?" Of course the entire team was in shock. You couldn't remove the locks from the updates. That meant that the data could become corrupt. That is what we told the tech lead: you need locks to keep your data from becoming corrupt. "So why don't we ensure that the data won't become corrupt when we update it?"

Nobody understood what he meant. Keep in mind that all of us were brought up with the concept of pessimistic locking. So the lead asked us to show him the queries that were being fired against the database:

  1. SELECT ID, StockCount FROM tblProducts WHERE ID=?

  2. application code calculates the new stock for the product

  3. UPDATE tblProducts SET StockCount=? WHERE ID=?


He thought about it for a while and then said "How about this?":

  1. SELECT ID, StockCount FROM tblProducts WHERE ID=?

  2. application code calculates the new stock for the product

  3. UPDATE tblProducts SET StockCount=? WHERE ID=? AND StockCount=?


"So we pass in both the new value for StockCount and the value that we expect to be there. That way the update will only be performed when the StockCount has not been modified by anyone else."

I can still remember the shock going through my mind. Does this mean that I don't need to lock the record before reading it? What will we do when the StockCount did actually change between our SELECT and our UPDATE?

All these questions were answered in the next few hours. If some other user had performed a conflicting UPDATE while our code was busy figuring out the new stock vale, we'd have to reperform the entire sequence above. So the process turned more into a loop:

  • while the stock value has not been updated:


    1. SELECT ID, StockCount FROM tblProducts WHERE ID=?

    2. application code calculates the new stock for the product

    3. UPDATE tblProducts SET StockCount=? WHERE ID=? AND StockCount=?



And sure the code got a bit more complex. And definitely in the worst case, this code will send a lot more queries to the database than the one with pessimistic locking. After all, it will fire multiple SELECT and UPDATE statements. Potentially an unlimited number of them, because of the loop.

But that is exactly why people call this the optimistic locking pattern. As I said earlier, most concurrent updates to a database are to different records. So most updates don't have a conflict. But with pessimistic locking all updates pay the price of acquiring a lock. So all updates pay get a penalty for a small fraction of them that do require the locking.

Optimistic locking is built on the assumption that most updates are without conflicts. When there is no conflict, there is no penalty. And only when there has been a conflicting update, do we go into the loop of retrying and pay the penalty. The penalty will be much higher than with pessimistic locking, but it will only be paid for the cases where it is needed.

So there you have it, the difference between optimistic and pessimistic locking and how I learned about them. Pick whichever one you think will work best for your project. Both of them are perfectly suitable for keeping your data safe. It all depends on the ratio of "updates with conflicts" vs. "updates without conflicts" for your application.

7 comments:

Adam Conrad said...

You should look into Transactional Memory. I'm writing a paper on it for my CS grad classes right now...all the security and data integrity of lock-based programming, without...well, the locking aspect.

No deadlocks. Improved performance. Bliss.

Anonymous said...

or add a new column called lock_version starts at zero when the record is inserted. Select the lock_version when you read from the table then compare lock_version with the value selected when you update the table, in the update also increment lock_version by 1.

SELECT lock_version, stock_level WHERE id = ?

UPDATE lock_version = lock_version + 1, stock_level = ? WHERE id = ? and lock_version = lock_version

Some databases (Sybase and MS-SQL for example) have a timestamp data type that is updated automatically and have a special function (tsequal?) that will throw an error which you can recognize as an optimistic update problem. Now you can update any column on the table without getting into trouble.

SELECT timestamp, stock_level WHERE id = ?

UPDATE stock_level = stock_level WHERE id = ? AND tsequal(timestamp, old_timestamp)

Frank said...

The question of whether to use of a version column is actually the main reason I wrote this post. I noticed the use of a version column in some code I was reading and wondered why the author introduced such a column.

Although a version column is a simple way to ensure that no conflicting updates occur, it is (just like pessimistic locking) also a sub-optimal one. Essentially it ensures that no concurrent updates occur, whether they are conflicting or not.

Depending on the database schema there are many types of concurrent updates that can happen without losing data integrity. They could be updating different columns that don't have dependencies on each other.

I started writing a post about exactly the use of version number columns vs. the use of field values in optimistic locking applications, but somehow ended up with this post instead. Your feedback shows that I really should finish the other post as well.

Anonymous said...

@Frank Although a version column is a simple way to ensure that no conflicting updates occur, it is (just like pessimistic locking) also a sub-optimal one. Essentially it ensures that no concurrent updates occur, whether they are conflicting or not.

I'm not sure I understood why the version column-based solution is sub-optimal. Would you please elaborate...? as I think (1) that the version-column-based solution would be just as efficient as checking the old value of stock_level or comparing timestamps, and (2) that some tables may not have even one 'efficient' column type (and thus value) to use for comparisons (let's say, all columns in a table are all string type)... forcing you to either use timestamp column approach or the version number approach.

I'm assuming that when implementing a version-column-based solution, one would use an auto-incrementing integer type column... so that it too, just like the timestamp column, does not require 'user code' to manually increment the current version and thus start being inefficient relative to timestamp approach where the timestamp update would happen inside the more efficient 'system code'.

/Harry

Frank said...

Hi Harry,

Imagine a table with four columns: ID, version, count, day. Let's also assume there is no relation whatsoever between these columns. We have a row with these values:

42,1,100,Monday

And we have two updates that we want to execute:

subtract 50 from count
set day to Saturday

If we write these with version based locking, we end up with:

UPDATE table
SET count = 50
WHERE id=42 AND version=1

UPDATE table
SET day = "Saturday"
WHERE id=42 AND version=1

There is no way these two updates could ever execute in parallel. One of them will fail and the application logic will have to read back the new version number, resolve potential conflicts (none in this case) and retry.

When using value-based locking, you'll end up with queries like these:

UPDATE table
SET count = 50
WHERE id=42 AND count=100

UPDATE table
SET day = "Saturday"
WHERE id=42 AND day="Monday"

These two queries can execute in parallel.

This is a very simplistic and contrived example and there are many cases where this simply will not work. In those cases locking on multiple columns or introducing a version column to lock the entire row are totally fine.

But in cases where a value-based lock can suffice, you'll end up decreasing (potential) throughput if you use a version-based lock.

Thanks for your feedback.

Frank

Anonymous said...

Hi Frank, I follow you and agree with you now. Thanks for replying promptly. And btw, did I forget to mention that I found this post of yours overall quite a lucid read?!

Regards,
/Harry

Unknown said...


Nice Article !

Really this will really help to people of Database Community.
I have also prepared small note on this, What is Optimistic locking and Pessimistic locking.

http://www.dbrnd.com/2016/04/database-theory-what-is-optimistic-locking-and-pessimistic-locking/