Sunday, February 15, 2009

Concurrent Editing Without Locking

If you write an application that allows a user to edit data, you should consider what happens when multiple users attempt to edit the same data at the same time. If you don't, you are likely to end up with some unhappy users when they unexpectedly lose some of their data.

Contents

Scenario

The approach described here can be applied to other situations, but here we focus on one particular kind of common application: a form-based web app that allows the user to edit a record in a database. In this kind of application, the user typically opens a record for editing, which downloads the data from an app server to his web browser (the client application), which displays it in an editable form. The user edits the data in the form as desired, then presses the Submit button. The web browser sends the form data back to the app server, which saves it to the database.

Now consider this problematic sequence of events, where two users concurrently try to edit the same record:
  1. User A opens record X for editing.
  2. User B opens record X for editing.
    At this point both users see the same data on their screens.
  3. User A submits his changes for record X.
  4. User B submits his changes for record X.
    How do these two submit operations interact?

The Other Ways

There are a number of approaches typically taken to handle concurrent editing.
  • Last in wins: Each user is allowed to open the record for editing and sees the same data. When User A submits his changes, they are saved to the database. When User B submits his changes, they are saved to the database. Whatever data User B submitted will overwrite the values User A submitted for those fields, so User A's changes will be lost.
  • Pessimistic locking: When User A opens a record for editing, the server locks the record. When User B asks to open the same record for editing, the sever denies the request. When User A submits his changes, the server unlocks the record. User B can not edit that record until User A is done.
  • Optimistic locking (first in wins): Each user is allowed to open the record for editing and sees the same data. When User A submits his changes, they are saved to the database. When User B submits his changes, the request is denied because the record changed after User B first opened that record.

Last In Wins

If you don't think about concurrent access, you will most likely end up with a last-in-wins system, although without an explicit review of the code for potential concurrent access problems and depending on the back end, you may also be vulnerable to data corruption as well as data loss.

The big disadvantage of this approach is pretty obvious: User A's changes are lost (referred to as a lost update), and nobody knows until later, when something else goes wrong. User A submitted his data, everything looked good, he might even have gone on to another step that used his changes, and he would have seen them in the database as long as he completed those tasks before User B pushed the Submit button.

Pessimistic Locking

A naive implementation of pessimistic locking is probably the simplest method of doing concurrent access control. You simply don't let two people open the same record for editing at the same time. When the first person opens the record for editing, you lock it. When the second person attempts to edit the same record, he gets an error message and is not allowed to edit. This is a typical solution, but it has some problems, especially for web apps. The problem arises when one person opens a record for editing, then takes a long time editing that record. During that long period, nobody else can update anything in that record. The epitome of this problem is when the user who is editing a record takes a break and walks away from his computer, gets sidetracked, and ends up going home (or out to dinner and a movie) without ever getting out of the editing screen for the locked record.

As an application designer, you have to decide how to handle this situation. Leaving the record locked as long as the user has it open is not a viable option. If the user not only went home but also went on vacation (or got sick), you could be waiting a very long time to unlock that record. So you have to break that lock at some point.

How do you decide how long to wait before breaking the lock? You could hold the lock until someone else wants to edit the record, then let the second person break the lock if it is older than some amount of time, but you still have to decide what that time limit should be. The longer you let the first person hold the lock, the more disruptive it is to other users who want to edit the same record, but if you break the lock too soon, what happens to User A when he finally does submit his changes? User A thinks he has a lock on the record, so should be able to submit, but if the lock has been broken you can't just let him submit his changes, or you are back to last-in-wins.

You have to decide what to do with User A after breaking the lock. The simplest thing to do is to reject the submit request from User A, but this is not a very pleasing solution to User A, especially if the reason it took so long to make the changes was because they were difficult to do.

There are things you can do to improve the situation when using pessimistic locking. You could add some code to try to detect when the user navigates away from the page, such as hooks on other pages of your web site that clear locks. You could have a client-side timer that warns the user shortly before his lock is about to expire and gives him the opportunity to reset the timeout, which would include sending a message back to the server with that request. You could notify the user when the lock has been broken, so that he can get annoyed right then rather than editing for another hour and getting even more annoyed when his submit is rejected. But every such change moves you further away from the simplicity that was one of the reasons for choosing pessimistic locking in the first place.

The bottom line is that pessimistic locking ends up being a lot more complicated than it might originally seem once you add everything you need to deal with the lock timeout problem.

Optimistic Locking

"Optmistic Locking" is a bit of a misnomer, since it doesn't necessarily lock. It is more accurately called optimistic concurrency, but calling it optimistic locking helps to draw the functional parallel to pessimistic locking.

With optimistic locking, multiple users are allowed to edit a record at the same time. When the first user edits the record, the server says "OK". When the second user edits the record while the first user is still editing, the server says "OK" again. Whichever user submits first wins; when the other user submits, it will be denied by the server because of the first submitter's changes. With some optimistic systems, the server will at least inform the second user that someone else is already editing the record when he first opens it, so the second user has the option of canceling right away and trying again later. On the other hand, similar to how some people react to a yellow light, the second user might interpret that warning as an exhortation to edit quickly so as to get his changes in before the first user.

Optimistic locking is called that because the application is being optimistic that it can let both users have what they want. This is based on the assumption that at least one of the users will exit the editing screen without making any changes. Assuming that happens, there are no problems caused by allowing both users to edit the same record, because one of them does not actually edit it.

Some systems do not give the user the option to view a record except by opening the record for editing. In such a system, there is a good chance that a user who opens a record for editing will not actually edit the record, so optimistic locking may seem like a reasonable approach. On the other hand, it would not be that difficult to add a View screen that allows the user to see what is in the record without editing it. You could put an Edit button right on the View screen to put the user into the Edit screen, or even automatically switch the user into Edit mode if he changes any fields on the form.

If you have a system in which the user can express an intent to edit rather than view a record, then there is a high probability that a user who opens a record for editing will actually submit some changes. In such a system an optimistic locking strategy is likely to be overly optimistic.

As a user you can ask yourself: Would it be more annoying to try to edit a record and be told right away that you can't because it is locked (pessimistic locking), or to spend time putting in your data, only to be told when you submit that you are not allowed to edit that record and have to start again (optimistic locking)?

Some people use the term "optimistic locking" to refer to a mechanism more like what I describe below, including both the database's rejection of the update request and the following resolving step. My usage of the term above is more typical when applied specifically to transactional database updates, in which only the database request is considered. This is also sometimes called Optimistic Offline Locking.

A Better Way

Let's reexamine our goals:
  1. User changes are never inadvertently lost.
  2. Users are never locked out of editing a record.
  3. Users are never required to throw away their edits.
None of the three methods described above satisfy all of these goals. Here's another approach. It's not Pessimistic Locking, and it's more than simple Optimistic Concurrency - let's call it Optimistic Resolving Concurrency. If you google for phrases like "optimistic concurrency" and "optimistic offline locking" and browse around, you will find a lot of descriptions that discuss in some detail the work of detecting update conflicts, after which they pretty much all punt on how those conflicts should be resolved, simply stating that it is the responsibility of your business logic to handle that. I describe in some detail one approach you can take in your business logic to do that.

If you think about the way many modern source code control systems work, such as Subversion or Git, they satisfy all of the goals listed just above. Their approach is straightforward:
  1. Always allow a user to edit a file.
  2. When a user submits changes, accept them if there are no conflicts with other changes.
  3. If there are conflicts, provide the user with tools to resolve the conflicts and allow the user to resubmit the changes after the conflicts have been resolved.
We can apply this approach to our editing web app example. Here are the basic steps:
  1. When a client application (web browser) loads a record for the user to edit, the server sends all of the data for the record, but does not lock the record.
  2. When the user pushes the submit button to save his changes, the client sends back to the server all of the original data along with the user's desired changes.
  3. The server matches the original data sent back by the client against the current contents of the database for the record being edited. If there have been no other changes, then the user's desired changes are saved and the server returns an indication of success to the client.
  4. If the record has been changed, as evidenced by a failure to match all of the original data returned by the client, then a resolving step must be undertaken. This is described in more detail below.
Without the resolving step, you could consider the above to be a description of optimistic concurrency. Personally, I consider the resolving step to be an integral part of the concurrency solution.

The code on the server side is relatively straightforward because we are pushing all of the work of resolving the differences to the client. But there is one interesting detail, and that is concerning how the server determines that the original record has not changed since the data for that record was sent to the client.

App Server Updating

We need to check if the data currently in the database for the row submitted by the client still matches what the client was originally given, and only perform the update with the user's desired changes if there were no other intervening conflicting changes. The obvious way to do this is to use a transaction. Within the transaction, we SELECT all of the fields from the row in question using a FOR UPDATE modifier so that the row is locked for the duration of the transaction. We then compare that data to the original data returned to us by the client requesting an update. If there were no changes we execute a database UPDATE on the row and commit the transaction, otherwise we simply abort the transaction (or commit it, since we only did a read).

In most situations the above approach would be a perfectly satisfactory solution. Our app server, which is presumably a client to the database server, will be locking one row, but the operation should be very fast and there is nothing else it needs to wait on in order to complete the transaction (in particular, we are not waiting for any user actions at this point). But there is a small chance that our app server will, for whatever reason, hang during the transaction, which could leave the row locked for longer than expected. And besides, the title of this article does say "without locking".

There is a simple trick you can use in this situation so that you don't have to separately read the current data from the database in the app server in order to do the comparison against the client's original data. Instead of having the app server do that comparison, we make the database server do it. We do this by having our app server execute a single UPDATE statement for the row to be updated, and we include a WHERE clause that not only includes our row identifier, but also matches each column against the client's original values. If none of the fields in that row have been changed since the client received the original field data, then the WHERE clause in the UPDATE statement will be true and the update will be executed on our row (and only our row, since we include our row identifier in the WHERE clause). If any of the fields have changed, then the WHERE clause will be false for our row (as well as for all others), so no rows will be updated. We can read back the row count of updated rows for the operation and check to see if it is 0 or 1, which tells us whether our row was updated. If 1, then we return a success indicator to our client; if 0, the update failed, in which case we need to do a SELECT on the record to read the current contents of all the fields and return that to the client for use in the resolving process.

With the WHERE clause in our UPDATE statement, we no longer need to lock the record in our app server. How the database server handles the write is its business. Any locking done within the database server would still be better than locking in our app server, and in any case is outside our scope. I think it is fair to say this is an approach without locking.

Rather than using all of the data fields in the WHERE clause of the UPDATE, you could maintain a single extra field which is a version number or an update timestamp. As long as that field is changed to a new value (never used before) every time any field in that row is changed, it works just fine as a check to prevent an UPDATE when someone else has modified the row. But we want to have all of the old field data around anyway so we can use it in our resolve step described below, so we might as well just use that data in our WHERE clause rather than adding a surrogate change field.

Defining Conflicts

If any of the fields of the target row have been changed since the submitting client received his original data, then there is the potential of a conflict between the data written by the previous updater and the data to be written for the submitting client. For each field of the record, we have three values:
  1. The original value of the field as of when the client opened the record for editing.
  2. The current value of the field in the database.
  3. The desired new value of the field as submitted by the client.
If the client does not pass in a desired new value for a field, then we assume the desired value is the same as the original value.

Here are the possible combinations of values for each field:

Original Current Desired Scenario
X X X 1. No change
X X Y 2. We want a change, noone else changed
X Y Y 3. Someone else changed, we want the same change
X Y X 4. Someone else changed, we did not
X Y Z 5. Someone else changed, we want a different change

If, for every field, we find ourselves in scenario 1 or 2, then we know no one else has made any changes, so we can save the desired new values without worrying about losing any data. If any field is in scenario 5, we know we have a conflict.

If scenario 3 arises, you might think it is no problem, since both users want the same change. On the other hand, you might want the second user to know that someone else modified the record, even if that modification was to put in the same data. If you choose to accept this scenario as a non-conflict, you can easily implement this in your WHERE-qualified UPDATE statement by modifying the WHERE clause so that each field can match either the original or the desired values.

Scenario 4 is a little bit trickier. It may be the case that two different people have edited the same record, each one changing a different field. If the fields are truly independent, then there should be no conflict. But if the fields are related, you may have a problem. For example, the two fields in question might be two different telephone numbers. Perhaps the data was originally entered incorrectly and the same phone number was put into both fields. Person A edits the record to correct it and updates the phone number in the first field, while person B concurrently edits the record and updates the phone number in the second field. If both changes go in, then both copies of the original phone number are lost. Thus the conservative approach is to treat this scenario as a conflict, the same as scenario 5. However, if you choose to treat this scenario as a non-conflict, you can easily do this by modifying the WHERE clause of the update to include only the fields in which the client submitted a new desired value.

Resolving Conflicts

When the app server determines that there is a conflict, it must tell the client which fields were in conflict and what their current values are. The client can then display that information to the user in a Resolve form that allows the user to determine how to resolve the conflict.

At a high level, the user has three options:
  1. Cancel his change request, discarding all his changes.
  2. Resolve the conflicts and resubmit the request.
  3. Postpone resolving the conflicts but continue editing.
Recall that the client has two pieces of information that it maintains and sends back to the server for each field on a submit request: the original value and the desired value. If the user wants to resolve a field conflict immediately, he needs to select which value should become the new desired value. This is typically either the current value or the previous desired value. The client's original value that it is storing for the field should be updated to be the current value as returned by the app server, so that on the next submit it will match the current value in the database.

If, however, the user would like to postpone resolving the conflict for a field, that can be done by keeping the old original value for the field so that the next time he submits, that field will once again not match the current value in the database, so he will be reminded about that conflict and can take care of it then.

So for each field, the user should be able to specify whether to keep the old original value or update it to the current value, and whether to use the current value as the desired value or keep the previous desired value.

One possible way to display all of this information is to show a table with one row for each data field and five columns: the first three columns are the original, current and desired values at the time of the submit. These are all buttons. The fourth column is a column of check boxes labeled "Resolve Later". By default these boxes are unchecked. For any field with a box which is checked, the client keeps the old original value for that field. For the fields for which the user leaves the box in its default unchecked state, the client updates its original value to the current value. The fifth column is the new desired value. The user can click on one of the buttons in the first three columns to pick which value to use as the new desired value in the fifth column. The value in the fifth column could also be directly editable. The form would have three submit buttons: Cancel, Submit, and Continue Editing (which is the "resolve later" option).

Once the user has filled out all of the fields in the Resolve form, the client now has updated values for both the original and the desired values for each field, ready for either continued editing or submitting to the app server. Submitting the form goes through the same process as before: if there are any conflicts remaining, the user will be put back into the Resolve form to take care of them. If the user has resolved all conflicts, but someone else happens to have made more changes in the mean time, the submit will fail again and the user will have to resolve the conflicts. If the user chooses to continue editing, we just put him back into the regular editing form. In either case, once we leave the Resolve form we are back in the regular code flow, we don't have to remember that we were in the Resolve form.

Theoretically it is possible for the user never to be able to save because there is always someone else making new edits to the record. I suspect this is not a problem for most real-world situations. If it is, then you might have to resort to pessimistic locking. Better still, redesign your system so that you don't have so much contention for that one record.

Subtleties

When defining what constitutes a conflict, the simplest solution is to treat every field as an independent value, so that there is a conflict whenever the same field is changed by two concurrent clients, and there is no conflict if no common fields have been changed. However, as suggested above, a more sophisticated definition may be more appropriate.

In most databases there are implicit relationships between fields such that you might want to consider changes to any of those fields to be in conflict with changes to any other of those fields. Sets of phone numbers, email addresses or similar lists are a good example of this. Note that these data may not all be stored in one table or shown on one screen, even when submitted by the client in one update request. For example, if you are editing an order with a list of order items, chances are good that each order item is stored in a separate record; but all of the order items are related, and you probably want to treat a change to any order item as potentially conflicting with a change to any other order item, just as with the phone number example above.

Similarly, if your application reads data from one record and is using that data to modify another record or create a new record, you might want to ensure that the first record has not changed before writing the other record, even if you are not changing the first record. In this situation you might not be able to use the UPDATE ... WHERE trick, in which case you can fall back on using a transaction in which you read and validate the old data before updating or inserting the new data.

In the other direction, there may be cases where you want to allow certain changes to one field by two clients to be treated as no conflict. For example, you may be storing a text field, and you may decide that each line in the text field should be treated as an independent entity for the purpose of conflicts. If User A changes line 3 of field X and User B changes line 5 of field X, by this definition those changes do not conflict, so should be allowed. Of course this requires some extra coding: you need to check for this situation in that field, merge the changes if they don't conflict, and provide tools for the user to merge changes that do conflict.

If you are storing and updating blobs in a database that does not allow blobs to be used in comparisons in WHERE clauses, you will not be able to use the UPDATE ... WHERE trick. I mentioned earlier how you can use a version or update timestamp field in the record as a surrogate to know when any data has changed; you can use that technique here, or you can be a bit more precise and add a version or timestamp field associated with the blob field, updating that version or timestamp field only when the corresponding blob field is modified. You can then use that surrogate field in your WHERE clause. Alternatively, you can fall back on the approach of using a transaction within which you read the current database data and compare to the original data in the application.

Summary

On the app server side:
  1. When a client edits a record, send the data and do not lock the record.
  2. When a client requests an update, use an UPDATE with a WHERE clause to make it an atomic update that succeeds only if there were no changes. If the update fails, load the current data from the record and send that back to the client.
On the client side:
  1. Maintain the original value for each field as well as the desired value for changes. Send both to the app server on a submit of an update.
  2. When the app server rejects an update, provide a Resolve form (with Cancel, Submit and Continue Editing buttons) allowing the user to choose, for each field in conflict, whether to accept the previous change or update with his desired value, and whether to keep the old original value for a later resolve or to update to the current value.
Some systems that use the UPDATE ... WHERE trick I describe above, although these references don't mention what the systems do when a conflict is detected:
  • Apple Enterprise Objects Framework Optimistic Locking
  • Apache Cayenne
  • Microsoft's LINQ to SQL detects conflicts and provides some support for how to write the selected values once that decision has been made, but does not include the mechanism to allow the user to resolve conflicts.
Some systems that implement the basic conflict resolving approach I describe above:

4 comments:

hs said...

Your description sounds pretty much like how optimistic landing has been handled in Microsoft Access since at least Access 2000 (I think Access 97 had this too), complete with form to help user resolve conflicts on a record that was changed after the time the user retrieved it.

hs said...

whoops, I meant "optimistic locking" of course. . .

Jim McBeath said...

hs: I am not familiar with Access. I found some web pages that discuss conflict resolution in Access when handling a replicated database, and a form to be used by a sysadmin to resolve those conflicts, but I did not find anything about ordinary users resolving conflicts when they submit their changes. Can you point me to a web page describing that, or better still to one that includes screen shots of the resolving form?

Chris Bouzek said...

Hibernate does "versioning" for its optimistic concurrency control. I believe it is pretty similar to what you've described here, although the manual doesn't describe it as well as Hibernate in Action does: http://www.hibernate.org/hib_docs/reference/en/html/transactions-optimistic.html