Optimistic Locking For Retrieving Result Sets

I’m in the middle of updating my Silverlight code to use asynchronous HTTP requests — fortunately, I spent last summer writing a GWT application, where HTTP requests have always been asynchronous, so I’ve got a library of patterns for solving common problems.

For instance, suppose that you’re doing a search, and then you’re displaying the result of the search. The most reliable way to do this is to use Pattern Zero, which is, do a single request to the server that retrieves all the information — in that case you don’t need to worry about what happens if, out of 20 HTTP requests, one fails.

Sometimes you can’t redesign the client-server protocol, or you’d like to take advantage of caching, in which case you might do something like this (in psuedo code):

getAListOfResults(new AsyncCallback {
     ... clearGUI();
         foreach(result as item) {
            fetchItem(item,new AsyncCallback {
               ... addItemToGui()
         }
}

First we retrieve a list of items, then we retrieve information about each item: this is straightforward, but not always reliable. Even if your application runs in a single thread, as it would in GWT or if you did everything in the UI thread in Silverlight, you can still have race conditions: for instance, results can come back in a random order, and getAListOfResults() can be called more than once by multiple callbacks — that’s really the worst of the problems, because it can cause results to appear more than once in the GUI.

There are a number of solutions to this problem, and a number of non-solutions. A simple solution is to make sure that getAListOfResults() never gets called until the result set has come back. I was able to do that for quite a while last summer, but the application finally reached a level of complexity where it was impossible… or would have required a major redesign of the app. Another is to use pessimistic locking: to not let getAListOfResults() run while result sets are coming back — I think this can be made to work, but if you’re not careful, your app can display stale data or permanently lock up.

Fortunately there’s a pattern to retrieve result sets using optimistic locking that displays fresh data and can’t fail catastrophically

class Whatever {
    int transactionId=0;
   public updateGUI() {
      getAListOfResults(new AsyncCallback {
               transactionId++;
               final int currentTransactionId=transactionId;
           ... clearGUI();
              foreach(result as item) {
                 fetchItem(item,new AsyncCallback {
                    if (transactionId != currentTransactionId)
                       return
                    ... addItemToGui()
             }
      }
}

The gist of this is that each result set is assigned a unique transaction id — once the list of items comes back, we clear the GUI, then we ignore fetchItem() callbacks from prior transaction id’s. In a multi-threaded environment, you’ll need to take care that transactionId’s are generated atomically.

Let’s think about how this algorithm holds up in the face of failure: suppose one of the fetchItem() calls fails to return. Perhaps the callback is going to come back with a failure code, but you never know. (It certainly doesn’t in some off-brand browsers with GWT) A pessimistic locking scheme would require some way of knowing when the request is done — it would have to count all the fetchItem() calls that return… If one doesn’t come back, the application could be locked up forever. You could try to fight this by setting a timeout, but getting correct behavior in every strange case could be a lot of work.

The code above might not always do the correct thing, but it always does something sane. If one of the fetchItem() call fails, the item will fail to appear in the list. If the failure is a transient failure, you could say this is a fault of the algorithm: this could be patched over by retrying the failed request. If, on the other hand, the failure is the fault of the server (say the fetchItem() call crashes with a particular argument) this algorithm keeps the client app available.

Note that another detail is missing from this code sample: fetchItem() callbacks can come back in a random order, so that the order that items appear in the GUI is not guaranteed. In some cases you might not care. If you do care, you can associate a sequenceNumber with each fetchItem() request (for instance, using a closure as we do with the currentTransactionId) and then use the sequenceNumber to place each item in the right place in the GUI.

The Optimistic Locking pattern is a simple and provably reliable solution to the problem of retrieving detailed information about items in a result set — in particular, it’s immune to catastrophic failures that can befall pessimistic locking schemes. Many people have proposed solutions to this problem that work sometimes, but not always: you don’t want to waste your time chasing Heisenbugs… Start with reliable patterns and build from there.

kick it on DotNetKicks.com