Resumable Backfills: Watermarks, Chunk Boundaries, and Gap-Free Progress

A backfill reads every record in a dataset and rewrites it in a new form. It is not a transaction and it cannot be one: the dataset is too large to fit in a single atomic unit, the work takes hours or days, and processes restart during it. Everything about the design follows from that: the job must be divisible into pieces small enough to commit individually, and it must record its position well enough that a restart resumes rather than repeats or skips.

Why the position must be a value, not a count

The obvious progress record is a counter: “processed 4,120,000 rows of 9,300,000”. It is also the least useful one, because a counter cannot be turned back into a query. On restart the job knows how far it got but not where, and re-deriving the position from a count requires either the same scan order and the same snapshot, which a concurrent workload does not provide, or an offset-based paging scheme, which is where the trouble starts.

Offset paging over a mutating table is incorrect even when nothing fails. SELECT ... LIMIT 1000 OFFSET 4120000 reads rows in whatever order the plan produces; deleting or inserting a row before the offset shifts every subsequent row, so the next page both repeats one record and misses one. With a stable sort key the shifting is at least deterministic, but the cost is not: the database must still walk and discard OFFSET rows for every page, so the total work of a full scan by paging is quadratic in the number of pages. The later pages of a 9-million-row backfill read nine million index entries to return a thousand rows.

A keyset position avoids both problems. The job records the sort key of the last row it processed and resumes with WHERE key > last_key ORDER BY key LIMIT n. The query uses the index, the cost per page is proportional to the page size, and the position is a value that remains meaningful across restarts. The requirement is that the key be unique and totally ordered: a primary key, or a composite of (created_at, id) where the second component breaks ties.

-- Keyset paging: cost per batch is O(batch), not O(offset).
SELECT id, payload FROM records
WHERE (created_at, id) > ($1, $2)
ORDER BY created_at, id
LIMIT 1000;

The composite form is what makes this usable on append-heavy tables. Ordering by created_at alone fails when many rows share a timestamp, because > last_created_at skips all the rows with the same timestamp that had not yet been read. Ordering by id alone works but scatters reads across the table. The pair gives an index-friendly order with a unique tiebreak, and the watermark is then the pair, not a single scalar.

Watermarks that can move backwards

The watermark is only trustworthy if the set of records below it is closed: no record below the watermark can appear later. On an append-only log with monotonically increasing offsets, this holds by construction: offset 5,000 has been written, and nothing will ever be inserted at offset 4,999. On a table with an auto-incrementing identifier it holds only approximately, because transactions can commit out of order: a transaction that started earlier and received a lower identifier may commit after the backfill has passed that point, and its row is then invisible to the scan and permanently missing from the backfill.

This is the read-snapshot question, and it has two honest answers. The first is to backfill from a snapshot taken at a known point, so that the visible set is fixed for the duration; the position then refers to the snapshot rather than to the live table. The second is to run a second pass over a recent window after the main pass completes, sized to cover the maximum transaction duration, which catches the late arrivals. The window is not a guess: it must exceed the longest interval between a transaction receiving its identifier and committing, which is bounded by lock waits and statement timeouts rather than by the job.

For a log-structured source the equivalent concern is consumer position versus committed position. A consumer that records its offset before processing the batch loses records on a crash between the two; one that records it after may reprocess the batch, which is harmless only if the processing is idempotent. The standard resolution is to make the write and the position update atomic: the same transaction writes the output and advances the stored offset, so that the pair cannot diverge. When the output lives somewhere that cannot join the transaction, the offset update must come after and the processing must tolerate replay.

Idempotent chunks and the cost of replay

If the backfill can be restarted at any point, the last chunk before a crash is processed twice. That is not an edge case; it is the normal behaviour of any job that crashes, and jobs crash routinely under memory pressure, deploys, and node failures. The design must therefore assume at-least-once execution of each chunk and make the effect of a second execution identical to the first.

Three mechanisms achieve that, with different costs.

A conditional write makes the operation naturally idempotent: UPDATE ... WHERE id = $1 AND version = $2 writes only if the row is still in the state the backfill observed, and a replay finds the version already advanced and does nothing. The cost is a version column on every row and an extra predicate in every write.

A derived write is idempotent when the output is a pure function of the input: computing a normalised field from the payload gives the same result whenever it runs, so a replay overwrites with the same value. This is the cheapest option and the one to prefer, but it excludes anything that accumulates: counters, append-only logs of the change, notifications.

A deduplication key handles the accumulating case: each chunk carries an identifier, the output records which identifiers have been applied, and a replay of a known identifier is skipped. This is the most general and the most expensive, since it adds a lookup and a record per chunk, and the record must itself be durable and garbage-collected.

The choice interacts with chunk size. Larger chunks amortise the fixed costs of a transaction and reduce the number of position updates, but they increase the amount of work a crash discards. A chunk that takes ten seconds to process means at most ten seconds of repeat work per failure; a chunk that takes ten minutes means ten minutes, and on a job that fails every few hours the repeated work becomes a visible fraction of the total. The tuning axis is the ratio of per-chunk overhead to per-chunk work, and the constraint is that the chunk must fit in one transaction or one atomic unit of output.

Running alongside live traffic

A backfill that reads and writes every row of a live table competes with the traffic the table exists to serve. Three effects compound.

The first is lock contention. Row-level writes take row locks; a backfill touching a contiguous key range will contend with foreground writes to the same rows, and on a hot range the contention produces wait queues that show up as latency in the serving path. Batching by key range makes this worse rather than better, because it concentrates the backfill’s writes in a narrow region; interleaving the ranges, or randomising the order within a pass, spreads the pressure.

The second is cache and buffer pressure. A full scan evicts the working set the serving path depends on. On a system with a buffer pool sized to hold the hot set, a scan over the cold remainder pushes hot pages out and the serving path begins missing to disk. Sequential scans that use a small ring buffer, rather than the whole pool, exist in the relational engines specifically for this; the effect is that the scan does not displace the hot pages, at the cost of re-reading pages it has already seen if the scan restarts.

The third is write amplification at the storage layer. On a log-structured engine, a backfill that rewrites most of the dataset generates compaction work proportional to the data it touches, and the compaction competes with foreground writes for the same I/O. The backfill’s throughput then declines as it progresses, which is a common and confusing shape: the job appears to slow down for no reason visible in its own metrics.

All three are rate problems with a shared resource, and the control mechanism is a rate limit that responds to the resource rather than a fixed sleep between batches. A fixed sleep degrades as the chunk’s work grows and does nothing when the resource is idle. The design of that controller, meaning how to shape background work against foreground latency, is the subject of admission control for background work.

Knowing when it is done

Completion is not “the scan returned no rows”. It is the conjunction of three conditions: every record below the final watermark has been transformed, the catch-up pass over the late-commit window has run, and a verification pass has found no record where the old and new representations disagree. The first two are progress; the third is correctness, and it is the only one that catches a transformation that ran on every row but produced the wrong value.

Verification by full comparison doubles the read cost. Cheaper schemes compare aggregates per range: counts, sums, or hashes over canonicalised values, which localise a discrepancy to a range without reading every row, and the comparison of those aggregates is the mechanism described in verifying a backfill with range checksums. Whatever the scheme, the job is not finished until something has compared the two sides, because a backfill that silently skips a range and reports completion is worse than one that fails loudly.