How to implement Optimistic Locking
This edition implements Optimistic Locking via some live code
Quick Recap
Optimistic locking and Pessimistic locking are popular concurrency control mechanisms used in computer science. These strategies rely on one simple question: How often do you want to make an update that might be conflicting between two threads? If it’s rare: go for Optimistic Locking which provides less resource contention. If it’s more frequent, then go for Pessimistic Locking which locks the critical section that each thread wants to execute.
You can already take a guess: Optimistic locking allows more throughput from the system and Pessimistic Locking provides less throughput from the system.
If you haven’t read it already, I highly recommend reading this previous article about Optimistic Locking vs Pessimistic Locking:
Database Internals - Optimistic vs Pessimistic
When your application deals with many transactions doing concurrent reads and writes to the database, you need concurrency control mechanisms to ensure that your database is always in a consistent state before and after processing reads and writes requests.
I hope you read the article and know that Optimistic Locking is based on the concept that conflicts between transactions are extremely rare and most transactions can be completed without interference. Let’s take a dig at the implementation.
Optimistic Locking
Well, let’s dig deep into the code now. I am using Golang for coding. But, you can copy-paste the code attached at the end and re-write it in another language with the help of similar libraries.
The main() function
Firstly, I defined a sync WaitGroup to represent a pool of GoRoutines.
Then, I used a for loop to simulate the number of threads working on a database and updating it at the same time. Inside the for loop, I am adding each goroutine to the WaitGroup using the Add() function which is used for managing all the goroutines.
Then, I call the function “incrementCounter” to increment a global variable. The word “go” used before calling the function represents that the function is called asynchronously and fired using a new goroutine (similar to thread in other languages).
Then, after the for loop, I use a function called Wait() to wait until all the goroutines are completed and are reached at this point in the code.
The “incrementCounter” function
Inside the incrementCounter method, I am doing a bunch of things:
defer wg.Done(): The defer keyword ensures that a certain piece of code is always executed just after the current goroutine exits. Thus, irrespective of an error or NullPointerException or any runtime error, wg.Done() will always be executed which decrements the internally maintained goRoutine counter in the WaitGroup. Thus, wg.Wait() will be able to resume the execution in the main method when the goroutine count in waitGroup reaches 0.
Then, I load the old counter value using the “sync/atomic” library and function atomic.LoadInt64() is present in the library.
Then, I increment the old counter value by 1 and store it in the new counter value.
Then, I am using a function called CompareAndSwapInt64(). This function is the secret sauce of optimistic locking. CompareAndSwapInt64 is an atomic operation provided by the sync/atomic package that compares the value of a 64-bit integer with an expected value and, if they match, replaces the integer with a new value.
In the above method, the counter will be updated to newCounterValue if the current value of the counter is oldCounterValue.
When you run the above complete code using the appropriate go command, your computer converts the program into an assembly code. The “CompareAndSwapInt64” will be converted to the “CMPXCHG” CPU instruction in the assembly code.
This CPU instruction “CMPXCHG“ is atomic, meaning it is performed as a single, uninterruptible step. This means when your CPU is performing this CPU instruction “CMPXCHG”, it would not do any context-switching with the other threads.
Thus, you can imagine, that since there is no context switching, there is no way that multiple threads will override their results.
There will be only a boolean result out of this compare and swap function representing whether the values are swapped or not.
In the end, I printed the message “operation failed“ which represents that CPU instruction was unsuccessful. To get an idea of how many times the optimistic locking failed, I have commented on the “operation success” message.
After running the above code, the result was this:
You can see that there are 121 failures for an iteration of 10000 goroutines. An error rate of 1.21%. A similar error rate between 0.5% and 2.5% was observed after running the code multiple times.
Summary
Well, that’s pretty much for this article. Here are a few closing thoughts on this:
Optimistic Locking allows you to get more throughput from your system since there is no explicit resource-locking required. It provides fewer resource contentions and more throughput at the same time compared to pessimistic locking.
Your CPU needs to expose this instruction “CMPXCHG“ so that it can be used for instructing the computer to compare and swap. Today’s computers would have this instruction already present in them but if it’s not there, you would have to use pessimistic locking to implement optimistic locking.
Pessimistic Locking assumes there will be conflicts and thus it locks the resources upfront so that there will be no conflict later. But, there can be conflicts in the optimistic locking. Thus, using the result obtained from the CompareAndSwapInt64() function (or similar function), you can either propagate the error to your client and ask them to retry or implement a retry mechanism in the backend server or fail the request gracefully. Thus, you have a free hand to choose how you want to drive client interactions.
Do It Yourself
I am putting you up for a challenge to implement this in your language of choice and paste the GitHub or online IDE link in the comments. Let’s discuss more in the comments.
Here’s the Go PlayGround link which has the executable code: Optimistic Locking Implementation. Copy this to your IDE and try changing the iteration count to 100. See, what happens next.
Great thanks to
🎉 for creating this awesome video on Optimistic Locking which helped get awesome clarity on this concept. Check it out here.Hope you liked this edition.
Please consider liking 👍 and sharing with your friends as it motivates me to bring you good content. If you think I am doing a decent job, share this article in a nice summary with your network. Connect with me on Linkedin or Twitter for more technical posts in the future!
We have a read heavy resource where we have implemented pessimistic locks. Going optimistic might just unlock some performance.
Interesting read!
I think the failure rate might be higher if
1) op was more computationally intensive than atomic read-write
2) update wasn't on the same computer, which will force us to think of network latencies, packet losses, partitions, between DB client and actual server.
I might need to check if some enterprise or OS DB has done such analysis. Optimistic still is a better fit for use-cases involving simple updates, I have often used DDB's optimistic locking at work: https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/DynamoDBMapper.OptimisticLocking.html