Representing Changes as Deltas
Dropbox's Datastore API resolves conflicts automatically for structured data. The core idea is to model every change as an object that can be inspected, serialized, and transmitted between clients and servers — a familiar Command pattern. The server keeps the complete history of changes for each datastore, and any snapshot can be reconstructed by replaying those changes in order from an empty starting point.
These changes are grouped into deltas, each labeled with a revision number. Revision 0 is the empty datastore. Every delta increments the revision by 1 and carries the revision of the state that precedes it — its base revision. Deltas are applied sequentially: delta 0 transforms revision 0 into revision 1, delta 1 transforms revision 1 into revision 2, and so on.
A Simple Walkthrough
Consider a datastore with a single table of records, each record having an ID and named values. Start with the empty snapshot:
Datastore: revision 0
| Table ID | Record ID | Values |
|---|
After applying delta 0, the datastore contains two records:
Datastore: revision 1
| Table ID | Record ID | Values |
|---|---|---|
| T1 | r1 | name="Jack", age=6 |
| T1 | r2 | name="Jill", age=5 |
The deltas themselves look like this:
| Base revision | Changes |
|---|---|
| 0. | insert T1:r1 {name="Jack", age=6}; insert T1:r2 {name="Jill", age=5} |
| 1. | update T1:r2 {age=6} |
| 2. | delete T1:r1; insert T1:r3 {name="Fred", age=42} |
Applying delta 1 changes the contents — in this example, it removes Fred — producing revision 2:
Datastore: revision 2
| Table ID | Record ID | Values |
|---|---|---|
| T1 | r1 | name="Jack", age=6 |
| T1 | r2 | name="Jill", age=6 |
Delta 2 then updates the remaining record, leaving the datastore at revision 3:
Datastore: revision 3
| Table ID | Record ID | Values |
|---|---|---|
| T1 | r2 | name="Jill", age=6 |
| T1 | r3 | name="Fred", age=42 |
Deltas originate on individual devices, though the originating device is not recorded with the delta itself. The server pushes each accepted delta to all other online devices via HTTP long-polling. Offline devices receive the pending deltas when they reconnect:
The same flow works regardless of device count. Every online device except the originator receives a copy of each delta.
When a Delta Is Rejected
Suppose device B goes offline after reaching revision 2, while the server and device A are at revision 3. B misses the delta that moved the datastore from revision 2 to 3. While offline, B's user makes a change — say, updating a character's age. When B reconnects, it tries to send this change as a delta labeled with base revision 2:
| Base revision | Changes |
|---|---|
| 2. | update T1:r2 {age=7} |
The server immediately rejects it: the base revision doesn't match the server's current revision of 3. The server doesn't examine the contents of the delta at all. Along with the rejection, the server sends the list of deltas that would bring B from revision 2 up to revision 3 — in this case, the same delta it earlier received from A:
Notice that B's rejected delta and the delta the server forwards are both labeled with the same base revision but contain different changes. The diagram tracks only revisions, not the specific contents of each delta.
Resolving the Conflict Client-Side
B's rejected delta contains a single change:
update T1:r2 {age=7} [rejected]The delta B missed from A contains these changes:
delete T1:r1; insert T1:r3 {name="Fred", age=42} [accepted]These two deltas commute: the resulting datastore state is identical regardless of the order in which they're applied. Resolving this particular conflict is therefore trivial. B rolls back to revision 2, applies the delta received from the server to reach revision 3, re-applies its own local change, and sends the same update relabeled as delta 3:
Datastore revision: ? (derived from 2)
| Table ID | Record ID | Values |
|---|---|---|
| T1 | r1 | name="Jack", age=6 |
| T1 | r2 | name="Jill", age=7 |
Datastore revision: ? (derived from 3)
| Table ID | Record ID | Values |
|---|---|---|
| T1 | r2 | name="Jill", age=7 |
| T1 | r3 | name="Fred", age=42 |
The server accepts the relabeled delta and advances the datastore to revision 4, with no change to the snapshot contents. B's successful resolution is also broadcast to A.
Why Not Operational Transformation Server-Side?
Readers familiar with Operational Transformation (OT) may wonder why the server doesn't attempt to merge conflicting deltas itself. The answer: Dropbox leaves OT-style resolution to the client, letting the server simply serialize requests. This delegates conflict resolution to your application, which can customize the rules to fit its own needs rather than being locked into fixed server-side policies.
The tradeoff is occasional redundant network traffic when a delta must be retransmitted after relabeling. In practice that's rare, and the flexibility gained is well worth the cost.
