Change Logs and Tombstones for Offline-First Sync

A phone is offline often enough that the local database is the primary copy for stretches of time, and a sync mechanism has to answer one question when connectivity returns: what is different? Answering it by comparing every row against the server is O(n) in the data and requires the server to cooperate in a full-table read. Answering it by recording changes as they happen is O(k) in the changes, and it requires the recording to be exact.

The exactness is the hard part. An update that touches a row twice must produce one change, or two that collapse; a delete must be distinguishable from a row that was never created; and a change that has been sent but not yet acknowledged must be distinguishable from one that has been sent and lost.

The log is a separate table, not a column

The simplest design adds a timestamp column to every synced table and indexes it. It fails for three reasons. A row updated twice has one timestamp, so the server receives the final state without knowing that an intermediate state existed, which is usually fine and sometimes not. A deleted row has no row, so its timestamp is gone and the server never learns of the delete. And a timestamp requires a clock, which on a phone can jump when the user changes the timezone or when the network supplies a corrected time.

A separate change-log table avoids all three. Each entry records the entity type, the entity identifier, the kind of change (insert, update, delete), a sequence number local to the device, and optionally the changed fields. The sequence number is assigned from a monotonically increasing counter stored in the same database, inside the same transaction as the data change, so a change and its log entry are atomic together.

Atomicity here is the property that matters. If the data change commits and the log entry does not, the change is invisible to sync and will never be sent. If the log entry commits and the data change does not, sync sends a change that the local database does not contain, and the server’s copy diverges from the local one. Both failures are avoided by one transaction, and neither is avoided by an approach that writes the log after the transaction commits.

The log entry’s sequence number must be allocated inside the transaction too. Allocating it beforehand means a rolled-back transaction leaves a gap; gaps are harmless if the reader tolerates them, and a reader that assumes contiguity will stall at the first one.

CREATE TABLE change_log (
  seq         INTEGER PRIMARY KEY,        -- local monotonic counter
  entity      TEXT    NOT NULL,
  entity_id   TEXT    NOT NULL,
  op          TEXT    NOT NULL CHECK (op IN ('ins','upd','del')),
  fields      TEXT,                        -- JSON of changed columns, nullable
  synced_seq  INTEGER                      -- NULL until acknowledged
);

CREATE INDEX change_log_pending ON change_log(synced_seq) WHERE synced_seq IS NULL;

The partial index is the one that matters at read time. The sync path asks only for rows where synced_seq IS NULL, and a partial index on that predicate stays small even when the table holds a long history, because acknowledged entries leave the index as soon as they are updated.

Deletes need a row of their own

A tombstone is a row that exists to say something does not. Without one, a delete is indistinguishable from a row that was never inserted on this device, and the server cannot tell whether to delete its copy or to leave it alone.

The tombstone must survive until the delete has been acknowledged by every party that needs to know. In a two-party sync that means until the server confirms. In a multi-device sync it means until every device has pulled past the tombstone’s sequence, which the device cannot know locally and must be told.

The storage consequence is that the local database never shrinks from deletes alone. Deleting a thousand rows adds a thousand tombstones, and the tombstone table grows monotonically until some process collects the ones that are no longer needed. That collection is only safe when the server can prove no client will ask about them again, which is the same reasoning that governs reclaiming space from a page-oriented store: deletion marks, reclamation requires a separate decision about when the marks are unnecessary.

A common compromise is to keep tombstones in a separate table with only an identifier and a deletion sequence, no payload, and to drop them after a retention period that exceeds the maximum plausible offline duration. The period is a policy, not a guarantee, and a device offline longer than the period will resurrect deleted rows when it next syncs. Making the retention long enough to be implausible is the practical answer; making resurrection detectable is the correct one.

The cursor is a position, not a timestamp

Pulling changes from the server uses a cursor that records how far the client has read. The cursor must be assigned by the server, monotonically, and stable: a server sequence number, not a wall-clock time, because two changes committed in the same millisecond must still have a defined order.

The cursor is stored in the local database in the same transaction that applies the pulled changes. If the cursor advances but the changes are not applied, the client skips them forever. If the changes are applied but the cursor does not advance, the client re-applies them, which is safe only if applying is idempotent.

Idempotence is worth designing for explicitly rather than assuming. Applying an insert twice fails on a primary key conflict; applying an update twice is harmless if the update sets absolute values and harmful if it increments. A pull path that uses upsert semantics, insert or replace by identifier, is idempotent for both inserts and updates, and a tombstone application that deletes by identifier is idempotent as well. That combination makes a repeated pull a no-op, which in turn makes the cursor update a performance optimisation rather than a correctness requirement.

Pushing changes uses the opposite kind of cursor: the highest sequence number that the server has acknowledged. A push that sends entries 40 through 60 and receives an acknowledgement for 55 must mark 40 through 55 as synced and leave 56 through 60 pending. An acknowledgement for the whole batch is only valid if the server applies the batch atomically; if it applies entries individually and fails partway, the acknowledgement must be per entry.

Conflict is a data model question

Two devices editing the same row while offline produce two changes that cannot both be applied as written. The sync layer can detect this (the server knows the row’s version when it received each change), but it cannot resolve it without a policy.

Last-writer-wins by server receipt time is the simplest policy and the one that discards the most information: the losing edit is gone, and the user is not told. Last-writer-wins by a client-supplied timestamp is worse, because the timestamps come from clocks that can be wrong.

Field-level merge preserves more. If the change log records which fields changed rather than only that the row changed, then two edits to different fields of the same row can both be applied. This is why the fields column above exists; it costs space proportional to the number of changed columns and turns a whole-row conflict into a per-field decision.

For counters and sets, the merge must be commutative or the result depends on the order in which changes arrive. A counter that is stored as a total cannot be merged by addition without a record of what was added; storing it as a base plus a set of deltas, or using a counter that carries per-device components, makes the merge order-independent. The general theory is the same one behind version vectors and hybrid logical clocks, applied to the value rather than to the row.

Triggers versus application writes

Recording changes with database triggers has the appeal of completeness: any write, from any code path, is logged. It has the cost of opacity: the trigger fires for bulk operations too, so a migration that rewrites a table produces one log entry per row, and a cascading delete produces entries the application did not intend to sync.

Application-level logging has the opposite profile. It records exactly what the application means to sync, and it misses any write that bypasses the logging path, including writes from a migration, from a debugging tool, or from a second module that was added later.

The hybrid that works is to log in the data-access layer and to treat direct writes as a bug, with the database opened in a mode that makes them visible. A trigger that records a row count per transaction, compared against the number of entries the application logged, catches the mismatch without producing a full log of its own.

Triggers also interact badly with write-ahead logging thresholds. A single logical change that fires three triggers produces three log inserts, three index updates, and a correspondingly larger set of dirty pages, which means the checkpoint copies more frames per user action. On a phone, where the number of barriers is the dominant cost, that difference is measurable in the user’s perception of responsiveness rather than in a benchmark.

What the log costs when it works

A change log that is never pruned becomes the largest table in the database. Every insert adds a row plus an index entry; a table of a million rows has a log of at least a million rows until the acknowledged entries are removed. Removing them is a delete, which on a page-oriented store creates free pages rather than shrinking the file, so the file grows to the high-water mark of the log and stays there.

The mitigation is to prune in bounded batches and to accept that the file’s size reflects the peak rather than the current content. Pruning aggressively during a sync session competes with the sync for the same write bandwidth; pruning on a background pass after the sync has the same total cost but keeps the latency out of the interactive path.