Archive for August 30, 2013

Friday, August 30, 2013

How the Dropbox Datastore API Handles Conflicts

Guido van Rossum:

The Dropbox server stores the full list of changes for each datastore, and the state (a.k.a. snapshot) of a datastore can be obtained by executing the entire list of changes, in sequence, starting with an empty datastore.

[…]

When the server rejects a delta, it also sends the list of deltas that will take a datastore from the device's current revision to the latest revision seen by the server. In this example that's just the same delta that the server received earlier from device A. It is then up to device B to resolve the conflict and send the server an updated delta representing its resolution of the conflict.

[…]

If you’re familiar with the theory of Operational Transformation (OT), you might be surprised that the server doesn’t even attempt to resolve conflicts. We use OT-style conflict resolution on the client, but leave the server to simply serialize requests. This allows conflict resolution to be defined by the client — your app — giving you more freedom than traditional approaches (which usually require that the rules for conflict resolution be fixed).

Part 2:

For field collisions we look at the type of the modifications and the resolution rule set for the field. We also distinguish between local and the remote changes. When resolving a conflict between two changes, one is always designated the local change: this is the one that hasn’t been accepted by the server yet (in the first example above, this is “x:=1”). The change that was received from the server is called the remote change (in the example, “x:=2”). The difference is important because remote changes may already have been observed by other devices. This is also the reason why “remote” is the default rule (see below).