Replaying a Queue Against State That Has Moved On

An outbox guarantees that an operation will be attempted until it succeeds. It does not guarantee that the operation still means what it meant when it was created. A device that has been offline for six hours holds writes composed against a version of the data that no longer exists, and when the queue finally drains, the server must decide for each write whether it is still applicable, already reflected, or in conflict with what happened in the meantime.

This is the part of offline support that cannot be delegated to the queue. The queue’s job is delivery; the merge policy’s job is meaning. Getting delivery right and meaning wrong produces data that is consistent in transit and corrupt in fact.

Three shapes of divergence

The conflicts that arise are not one problem but three, distinguished by what the write depends on. The queue that delivers them is described in The durable outbox; what follows concerns only the moment after delivery.

A write can be independent. It touches an entity the client alone modified, or a field no one else touched. It applies cleanly and the merge is trivial.

A write can be superseded. Someone else changed the same field after the client’s last read, and the client’s queued value was computed from the old one. An example is a counter that the client read as 5 and set to 6, while the server had already moved it to 8. Applying the write blindly loses the other update; rejecting it loses the client’s intent.

A write can be invalidated. The entity it refers to has been deleted, or the user’s permission to modify it has been revoked, or a state machine has moved the entity past the point where the operation is legal. Here there is no merge to perform; the operation is simply not applicable, and the client must be told.

Only the second shape is a genuine conflict requiring a policy. The first is the common case and should be cheap. The third is an error case and should be distinguishable from a conflict, because the correct response differs: a conflict needs resolution, an invalidated operation needs withdrawal and an explanation. The classification of the failure that produced the retry is a separate question, treated in Retry classification when the failure arrives as a timeout.

Detecting what changed

To know which shape applies, the server must be able to tell what the client’s write was based on. That requires the client to send a basis along with the operation.

The simplest basis is a version number on the entity, incremented on every write. The client sends the version it read, and the server accepts the write only if the current version matches. This is optimistic concurrency, and it is exact: any change at all, even to an unrelated field, causes the write to be rejected. That strictness is a virtue when the entity is small and a nuisance when it is a large document edited by many people.

A finer basis is a per-field version or a per-field timestamp of last modification. The client sends, for each field it is writing, the version it observed. The server accepts a field’s write if that field’s version is unchanged, and rejects it otherwise. Unrelated fields then merge without conflict, which is what a form that edits one attribute of a large record needs. The cost is a version per field, which multiplies the metadata and the bookkeeping on both sides.

The finest basis is a vector of counters, one per replica, that records how many updates each replica has contributed. A client compares its vector with the server’s to determine whether either has seen the other’s changes, and the comparison distinguishes three cases: the server has seen everything the client saw, the client has seen everything the server has, or neither has seen the other’s. The third case is a genuine concurrent update, and it is the only one where a merge policy must choose. Vector clocks make that determination without a central authority, which is what allows peer-to-peer and multi-device editing, at the cost of a vector whose size grows with the number of replicas.

Merge rules that do not need a human

Where the operations commute, the merge can be automatic, and the choice of representation determines whether they commute.

A last-write-wins register resolves a conflict by a total order on writes: a timestamp, a sequence number, or a Lamport clock. The rule is simple, requires no user interaction, and discards one of the two writes. That discard is the cost, and it is acceptable for data where losing an update is a minor annoyance (a display preference) and unacceptable for data where it is not (a medical record, a bank balance).

A multi-value register keeps every concurrent write and lets the reader resolve. It loses nothing and defers the decision, which pushes the problem to the interface. This is what a source control system does for a merge conflict, and it works because the resolution is presented at the moment the user is looking at the data.

A counter that supports increments and decrements can be represented as a pair of per-replica counts, so that concurrent increments sum rather than overwrite. The representation makes the operations commutative by construction, which is the general trick: rather than detecting a conflict and resolving it, choose a data structure in which the conflict does not exist.

A set with add and remove operations is the classic hard case, because a concurrent add and remove of the same element is genuinely ambiguous: the remove may have been intended to remove the element that existed before the add, or to prevent it from ever appearing. The observed-remove variant resolves this by tagging each add with a unique identifier and having a remove name the identifiers it observed, so an add that the remover did not see survives. The result is a set where the outcome depends on causality rather than on arrival order, which is what makes it converge.

The pattern behind all of these is that convergence requires the merge to be independent of the order in which updates arrive, and the way to guarantee that is to make the state a join-semilattice: a set of states with a merge operation that is commutative, associative, and idempotent. Idempotence is what makes a replayed duplicate harmless, which ties the merge policy back to the delivery layer: an outbox that resends an entry after a crash must not corrupt a counter, and a merge that is idempotent makes that true by construction.

Field-level granularity and the patch format

The wire format determines how much of the client’s intent survives, and the two standard JSON patch formats illustrate the trade.

A merge patch, defined in RFC 7386, describes a set of changes to apply to a target document: a field set to a value replaces it, a field set to null removes it, and fields absent from the patch are untouched. It is compact and it composes naturally with field-level versioning, because the patch names exactly the fields the client intended to change.

A JSON Patch, defined in RFC 6902, is a sequence of operations with explicit paths, including array indices, test operations, and move and copy. It is precise and it can express changes that a merge patch cannot, such as inserting into the middle of an array. It is also fragile: an operation that indexes into an array by position breaks when the array has changed, and the failure is silent unless a test operation guards it.

For a queue of writes composed offline, the merge patch is usually the better fit, because it names fields rather than positions and therefore survives reordering by other writers. The array case remains a problem in either format, which is why arrays of records in offline-capable systems are often modelled as maps keyed by identifier rather than as lists — a change to one element then addresses it by key and is independent of every other element’s position.

What the user must be told

Automatic merging is correct only where losing an update is acceptable, and the decision of where that is true belongs to the product, not to the storage layer.

The signals available to the interface are the ones the merge policy can produce: a write applied, a write applied with fields discarded, a write rejected as invalid, and a write held for resolution. Each needs a different presentation.

A write applied with discarded fields is the dangerous case, because the user’s intent was partially honoured and nothing in the normal flow reveals it. Surfacing it as a conflict is often the right call even though the system could have resolved it silently, because the user is the only party who knows whether the discarded value mattered.

A write rejected as invalid needs an explanation and a path forward: the item was deleted, so the edit cannot apply; the state has moved on, so the action is no longer available. Silently dropping it leaves the user believing a change was saved.

A write held for resolution needs the competing values presented together, with enough context to choose. Presenting one value and asking whether to keep it is not a resolution, because the user cannot see what they are choosing against.

The general principle is that the merge policy should be as automatic as the data allows and no more, and that the boundary is a product decision expressed as a per-field policy. A single application typically needs several: last-write-wins for preferences, additive for counters, held-for-resolution for text that people wrote, and rejected-with-explanation for anything referring to an entity that no longer exists.

The cost of getting this wrong is deferred

A system with an outbox and no merge policy works perfectly until two devices are used, or until a second user touches the same record, and then it fails in a way that is hard to attribute because the failure is in the data rather than in the code path. The queue delivered everything it was given. The server applied everything it received. The corruption is in the composition.

The alternative to a merge policy is to prevent the situation, by refusing to accept offline writes to shared data at all. That is a legitimate design, because it makes the offline experience read-only for anything contested, and it is much simpler. What is not legitimate is accepting offline writes and hoping the conflicts do not arise, because on a mobile device they arise on the ordinary schedule of a commute, a flight, or a tunnel, and the data that arrives afterwards is the data the user will see.