CodeBrief

Client Sync for the REST of Us

It is no surprise that streaming technologies such as meteor have taken the spotlight over the last year. They present a compelling real-time way of keeping the client in sync with the server. One interesting result of thinking in real-time is that things like conflicts become top of mind: what is supposed to happen when two separate users modify the same data at the same time?

When dealing with traditional websites and basic REST API's, however, less thought is given to these concurrency scenarios. Real-time aside, in an age where client-heavy applications are becoming commonplace, this behavior can be problematic. In this post, I explore this inadequacy and also explore a possible solution.

Most Applications Today

From my experience, many applications adhere to something similar to the following diagram:

Naive sync

The client sends data to the server and the server sends new data back to the client. This seems simple enough and works in many cases– especially in an environment where conflicts are unlikely. These environments are generally reflective of traditional webpages where the user modifies data in a form and then waits for a new page to load. If there is an error or conflict, the server can either clobber the data or display an error when the page loads. Despite being less than ideal, this works most of the time.

Unfortunately, when dealing with rich client applications (such as those built with a client-side javascript MVC framework), developers are given no such luxuries. With a more responsive UI and better user experience comes more complexity to develop against. An application that has a non-blocking Asynchronous UI can not afford to wait around to see what the server thinks of the user's actions. Without additional logic to handle a myriad of edge cases, the client can quickly diverge from the server.

Specifically, the following are some cases where this simple model breaks down:

  • The client sends updates to the server, the user simultaneously updates the same data locally on the client, and then the server responds with a new version.
  • The client sends updates to the server, the server sends an error back saying that the client was operating on stale data (based on something like an ETag).
  • The client is modifying some local data, meanwhile updates to the same data are being streamed/polled in.

This begs the question: is a REST API even a suitable backend for a rich client application? My answer to this is a resounding yes. In order to properly handle real-time conflicts, algorithms such as operational transformation should be used1. Most applications are not real-time and/or collaborative and this is way overboard. Moreover, aside from allowing for a much simpler and client-agnostic backend implementation, applications which are more transactional in nature can benefit from more coarsely-grained requests.

We Can Do Better

In order to properly use a REST API with a rich client application, it is clear that something better than the naive request/response cycle represented in the above diagram is required. Fortunately, situations like this where there are infrequent updates to the same data that potentially conflict are well-tread. Technologies such as GIT have provided an adequate solutions for some time and merging algorithms such as 3-way merging have been around for ages. The main difference is that, in our case, the client does not have access to the version history to perform this type of resolution.

One of the virtues of having a rich client, is that it maintains state. This can be leveraged to maintain the version history required to perform GIT-like resolution. This is how Ember.js Persistence Foundation (EPF) works.

Below is a diagram of how EPF handles a successful client write:

Epf sync with 200 response
  1. The client computes a diff between its latest version (the Client Model) and the last known version from the server (the Client Shadow).
  2. A list of edits is computed.
  3. A backup of the last known version from the server (Shadow Backup) is stored.
  4. The Client Shadow is optimistically updated to reflect the client's changes.
  5. An HTTP PATCH/PUT request is sent to the server containing the client's updates.
  6. The server indicates success and returns its latest version of the data.
  7. This data is loaded by the client (Server Model).
  8. A merge operation is performed between the Client Model and the Server Model using the Client Shadow as a common ancestor.
  9. The Client Model is updated to reflect the result of the merge.

The main difference betweem this algorithm and the naive diagram at the beginning of the post relates to the ability to reconcile changes that have taken place on the client while the request is in transit. If the user changes the model before the server has sent its version back, the client is able to merge the user's edits against the lastest from the server.

You might be wondering what the purpose of the Shadow Backup is. This becomes apparent in the event of an error. In this case it is assumed that the server did not apply the client's edits and that the common ancestor to merge against is the original shadow. The below diagram represents what would happen in the even of a 412 response (which might be the case if the server rejects the client's request based on an ETag):

Epf sync with 200 response
  1. The client computes a diff between its latest version (the Client Model) and the last known version from the server (the Client Shadow).
  2. A list of edits is computed.
  3. A backup of the last known version from the server (Shadow Backup) is stored.
  4. The Client Shadow is optimistically updated to reflect the client's changes.
  5. An HTTP PATCH/PUT request is sent to the server containing the client's updates.
  6. The server indicates that the client's request is operating on old data and returns an error along with the latest version of the data.
  7. This data is loaded by the client (Server Model).
  8. The Client Shadow is reset to the Shadow Backup. This is necessary since the Client Shadow was optimistically updated in step 4.
  9. A merge operation is performed between the Client Model and the Server Model using the Client Shadow as a common ancestor.
  10. The Client Model is updated to reflect the result of the merge.

Although far from perfect, in my opinion, the above algorithm is a large improvement over clobbering/reloading. There is now well-defined behavior for conflicts and errors. A solid merging strategy can be provided out of the box and can also be customized for an individual application's needs.

The Future

A source of inspiration for this is differential synchronization, an alternative to operational transformation. The diagrams above also bear a striking resemblance to those in Neil Fraser's post. At this point I would like to wave my hands and say that perhaps something like that could ultimately be used to improve this type of resolution and provide a more incremental transition from async to real-time.

1. Interestingly enough, and a general misconception, Meteor does not use Operational Transformation out of the box. If two users are editing text at the same time, the last write wins.

comments powered by Disqus