Sync engines
Building a sync engine, part two: ordering
Vector clocks for the offline reality. Why they pay off, and the simpler model that does not.
Part ofsync-engineLoading essay…
Vector clocks for the offline reality. Why they pay off, and the simpler model that does not.
Part ofsync-engineLoading essay…
Two devices, one row, two different edits, both made offline. When they both reconnect, what does the row look like? This is the question every sync engine has to answer, and the wrong answer will cost you a customer. This is part two of five on the engine. Part one covered the queue; here we deal with ordering.
If you read the literature, the answer is vector clocks. Each node keeps a per-other-node counter; every write increments the local counter and includes the full vector; conflicts are detected by comparing vectors; either side may resolve them.
Vector clocks are correct. They are also expensive in two ways: every write carries a vector roughly the size of the active client population, and the conflict-resolution UI you have to build for the user gets complicated fast. For an accounting app where 99 % of writes never conflict, paying that cost on every row is wasteful.
For the dominant case (one row, one editor, no concurrency) we use a
single column on the server: version as a monotonically increasing
integer scoped to that row. Every update sends version along with the
diff. The server only accepts the write if the version matches; otherwise
it rejects with 409 Conflict and returns the current row.
// PATCH /invoices/:id
{
"version": 7,
"patch": { "amount": 1450 }
}
// 409 response
{
"error": "version_mismatch",
"current": {
"version": 8,
"row": { /* full server-side row */ }
}
}That covers 99 % of writes. The remaining 1 % is where this gets interesting.
When the client gets a 409, it has the user's local edit and the server's current row. There are three honest paths:
amount and the server's
newer version changed notes, both edits can land. We compute the
intersection of changed fields; if disjoint, we re-issue the patch
targeting the new version.We pick the path per entity type, not globally:
const RESOLUTION: Record<string, ResolutionStrategy> = {
contact: 'field-merge',
invoice: 'show-user',
invoice_item: 'last-write-wins',
user_profile: 'field-merge',
payment: 'show-user',
};Some engines try to be clever and infer the strategy from the diff. We tried. It produced surprises. A flat per-entity table is dumber, easier to debug, and easier to change when a customer reports something weird.
The clever engine that infers a resolution strategy from the diff is correct in 95 % of cases and wrong in the 5 % that produces a phone call. The dumb table is correct in 100 % of the cases it covers and silent on the rest. Silent on the rest is a feature.
Three reasons, in order of how much they matter:
Vector-clock conflicts have to be presented to the user as "your edit" and "their edit" and the user picks. The user does not understand "their edit" unless we attach a name and a timestamp. We do not always have a name. The screen the engineering team sketches at the whiteboard never ends up looking like the screen we have to ship.
Each write would carry a vector keyed by every active editor of that row in the last N days. For an accounting app where one tenant has 80 employees who all touch the same general ledger, that is 80 entries on every push. Not the worst thing in the world. Also not free.
Real-world data: in our app, 94 % of conflicts that exist at all are the same user editing on two devices (phone and desktop, both online). The remaining 6 % are sharing-mode edits. Vector clocks treat the 94 % case the same as the 6 %, when in fact it can be detected with a single device-id field and resolved with "merge by field, fall back to most recent device."
Three columns per syncable entity on the server:
ALTER TABLE invoices ADD COLUMN version INTEGER NOT NULL DEFAULT 1;
ALTER TABLE invoices ADD COLUMN updated_by_device VARCHAR(64);
ALTER TABLE invoices ADD COLUMN updated_at_server TIMESTAMP NOT NULL;version does the optimistic-concurrency-control work. updated_by_device
lets us implement the "same user on two devices" path. updated_at_server
is the source of truth for ordering across devices, because client clocks
lie.
The push protocol from part one carries a single version per item; the
server validates and returns either the new version or a 409 with the
current row. The client, on receiving a 409, runs the resolution table:
async function resolve(item: QueueItem, current: ServerRow): Promise<Action> {
const strategy = RESOLUTION[item.entityType] ?? 'show-user';
const localChanges = computeDiff(item.payload, current);
switch (strategy) {
case 'field-merge':
if (disjointFields(item.payload, current.recentChangedFields)) {
return { type: 'rebase', toVersion: current.version };
}
return { type: 'show-user', current, local: localChanges };
case 'last-write-wins':
return { type: 'discard', notice: 'serverWonNotice' };
case 'show-user':
return { type: 'show-user', current, local: localChanges };
}
}rebase is the simplest of the three: rewrite the queue item's payload
to target the new version and put it back at the head of the queue. The
next push attempt sends it through.
The textbook is right that you need a way to detect concurrent edits.
Optimistic concurrency on a version column does that. The textbook is
also right that conflicts must be resolved before the data lands; we do
that with the resolution table. What we dropped was the assumption that
every conflict is structurally interesting. Most are not.
The next part is about reconnect storms: what happens when a thousand devices come back online at the same moment, and how we kept the server up.
Series page tracks the rest.