Concurrent locking for dummies

Locking is a technique used for concurrent manipulation of shared data. Locking is not only related to databases: for instance you use locking in Java to synchronize multithreaded access to shared objects residing in memory.

Here I am not going to talk specifically about Java locking or database locking, but only how conceptually locking works on concurrent systems.
There are two types of locking: Pessimistic Locking and Optimistic Locking, and I am going to provide some real life examples on those.

Pessimistic Locking

Imagine the case of a book library.

  1. Alex goes to the library ad take the book "Concurrent Programming for Beginners" (lock)
  2. Linda comes to the library the day after and asks for the same book. The the librarian have to reply: "I am sorry Linda, the book that you require is hold by another person, try later...". So Linda waits for the wanted book, maybe asking to be called back by the librarian when the book is returned. (Linda goes in "wait for lock")
  3. Alex is not much respectful of the book he borrowed, so he adds side notes to the books, and underlines paragraphs to ease studying the concepts (modify)
  4. Finally Alex returns the book to the librarian. (unlock)
  5. The librarian then can finally give the book to Linda that was waiting for it (lock)

In summary, Pessimistic Lock from a client perspective involves in following steps:

  1. lock
  2. modify
  3. unlock

Now, there are some corner cases to take in mind, especially in a distributed system.
What happens if Alex dies before returning the book? Or what happens if Alex is a very bad guy and keeps the book for a longer time (lease time) than the acceptable? The librarian should recover the book from Alex's hands and return to the library.
On databases, locks are binded to transactions, and the transactions have expiration time. When the transaction times out the locks kept are freed. A way to implement the pessimistic locking on database could be using the "select for update" statement.
On memory, it can happen that a thread doesn't unlock the shared resource; in this case it's a programming error to be fixed. Or it can also happen that a chain of locks ends up to a circle, freezing the system: A waits for B that waits for C that waits for A; everyone waiting. It's called Dead Lock.
If the resource is shared among several process or several computers, it can happen that one of them crashes abnormally not having the chance to release the lock. Also for this case, the lock could have a lease time that - in case of needing - can be renewed periodically. If the lease is not renewed (because the lock taker is crashed) then the resource can be taken over by another process waiting for the lock.

In Pessimistic Locking the clients could have to wait to access the resource. Take it in mind.

Java synchronization is a good example of pessimistic locking, and it fits perfectly into Lock objects:

1Lock l = ...;
2l.lock(); // waits if the lock is taken by someone else
3try {
4    // access the resource protected by this lock
5} finally {
6    l.unlock();
7}

Pessimistic Locking is also know as "Exclusive Locking", because the access to a shared resource is always exclusive by one client at time.

Optimistic Locking

Imagine the case of two authors working together on writing a book. Albert and Robert are working from home on different sections of the book.

  1. On Monday Robert and Albert take the latest version of the book from their company's server, everything is perfect! (read)
  2. Robert is very quick, on Thursday he finishes his work (modify), so he goes to office to save his updates into the server. Robert checks that nobody updated the book in the meantime (verify), and luckily nobody did, so he just need to replace the old version of the book with his own (save)
  3. Albert is a little bit slower, so he managed to complete his work on Friday (modify), and he diligently goes to office to save his efforts on the server. But, surprise! He notices that Robert has saved his changes the day before (verify) so cannot just replace the existing version with his own: if he does that he will overwrite the changes made by Robert and get in troubles with him. So what Albert needs to do is merging his changes with the Robert's ones (merge), then save the resulting document on the server (save).

In summary, the optimistic locking, from the client perspective involves in:

  1. read
  2. modify
  3. verify
  4. merge (if the verify step fails)
  5. save

If the Verify fails you could have different choices:

  • Merge the changes. Sometime this drives to "merge conflicts", so that operation is not always automatically feasible.
  • Abandon (the first wins). Who arrives late will need to read the updated version, and retry his changes.
  • Overwrite (the last wins). The last who saves overwrites the previous version. You actually don't need to verify then... I would call it "Too Optimistic Locking" or "No Locking": basically users overwrites themselves each others continuously. Not very smart on multi user applications. But, believe it or not, this is how many (most?) systems work! This "solution" doesn't need any effort to be implemented: just always overwrite.

Basically, to implement the Verify in Optimistic Locking, what you do is adding a "version" to your data, and saving you check that you are updating the same version. Saving you also increment the version you read at beginning. If there is a version mismatch during the Verify, it means that somebody updated the document before you, so you have to take a proper action ("merge", "abandon and retry" or "overwrite").

In Optimistic Locking the clients will never need to wait to read or modify shared resources. But it could happen that sometime the save is prevented by a failing verification, needing additional action by the client. Take it in mind.

An example of implementation of Optimistic Lock is how Subversion works by default: every time you commit your source code, the server verifies that you are updating the same revision number you got when you checked out.
Many web application use Optimistic Locking because it does not require the users to wait. But it can happen that if two users modify the same data, the last one gets an error requiring him to redo the change or to merge (or, in some cases, asking to overwrite).

Some persistence tools provide facilities to automatically handle Optimistic Locking. Hibernate for instance can automatically handle the data versioning for you, giving an exception when the version check fails.


One Response to “Concurrent locking for dummies”  

  1. 1 Java synchronization is? | MeInfoBlogger.net


Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>



Calendar

October 2008
M T W T F S S
« Sep   Nov »
 12345
6789101112
13141516171819
20212223242526
2728293031  

Follow me

twitter flickr LinkedIn feed

Subscribe by email

Enter your email address:

Archives


Categories

Tag Cloud


Listening