Sync and conflict resolution

01The intuition

The problem it solves

Two friends share a grocery list on their phones. On the bus, with no signal, one adds "milk" and renames "bread" to "brown bread". At home, the other, also offline, deletes "bread" and adds "eggs". Both come online. What should the list be? If the server simply keeps whichever phone synced last, one friend's work vanishes. If it refuses the second sync, that friend has to redo everything. Neither feels right, and both happen in badly designed apps.

Sync is the problem of letting devices work apart and then combining what they did. The core difficulty is that "last" is not well defined when clocks disagree and neither edit knew about the other. A good sync design decides, per kind of data, how to detect that two edits are concurrent and what rule merges them, and it makes that rule run the same way on every device.

Build it one piece at a time

Step 1: a version on every record. The server stores each list item with a version number. A device that downloads an item remembers the version it saw. When it uploads a change, it sends that version along: "I am changing item 7, which I last saw at version 3".

Step 2: detect the conflict. The server compares: if item 7 is still at version 3, apply the change and bump to 4. If it is already at version 4 because the other device changed it first, this upload is based on stale data, and that is a conflict. This is optimistic concurrency, and it is the detection half of sync.

Step 3: pick a merge rule per data type. For a whole-record value like a setting, last-writer-wins by a timestamp is acceptable when losing one is harmless. For a counter, add both increments. For a set like a grocery list, union the additions and apply the deletions, with a rule for "edited by one, deleted by the other" (keep it, since an edit shows intent). For text, use operational transforms or CRDTs, which have their own article. The rule must be deterministic so both phones compute the same result.

Step 4: sync by changes, not by snapshots. Instead of uploading the whole list, each device keeps a log of its operations since the last sync: add milk, rename 7, delete 9. The server applies them in order against its state, and sends back the operations it has from others since the device's last cursor. Operations merge far better than snapshots, because "rename item 7" and "add item 12" obviously do not conflict, while two snapshots of the whole list do.

Step 5: make every operation idempotent and ordered per device. A device may upload the same batch twice after a lost reply. Each operation carries the device ID and a sequence number, so the server skips ones it has seen. Deletes are recorded as tombstones, a marker that says "item 9 was deleted at version 5", so a late add from an offline device does not resurrect it; tombstones are pruned after every known device has synced past them.

Why it works, with the numbers

The invariant is convergence: once all devices have received all operations, every device shows the same list, whatever order the operations arrived in. Version checks give you detection; the merge rule gives you convergence only if it is commutative for concurrent operations, which is why the rules above are chosen the way they are. Costs: one version number per record, a tombstone per deletion for a bounded time, and a cursor per device.

sync payload = operations since the cursor, typically tens of bytes each, rather than the whole document of tens of kilobytes

The failure modes: last-writer-wins applied to data where losing a write hurts, tombstones pruned before a long-offline device returns (its stale add comes back from the dead), and merge rules that differ between the server and a client version, which makes devices disagree forever.

The trade-off you must say out loud

Automatic merging against user control. Say which data types merge silently and which surface a conflict to the user (a document edited in two places may deserve a "keep both" copy). Say how long tombstones live and what happens to a device that was offline longer than that. The follow-up is "what if the server itself is replicated", and the answer is that the same version and merge rules apply between replicas, which is why many sync systems store operations in a log that replicates as a whole.

Where it shows up in the 100 Google problems

• Google Drive: file versions, change logs per client, and "conflicted copy" when two devices edit the same binary file.
• Offline-first client: the question itself; operation logs, version vectors and per-type merge rules are the deep dives.
• Google Docs: text merging by operational transforms, with the server as the ordering authority.
• User preferences across products: settings edited on two devices while offline merge per key with the rules above.

02Used in these problems

• Design Google Drive
• Design Google Docs
• Design an offline-first client that syncs and resolves conflicts