Capturing Lineage for Tile Generation Pipelines

Part of: Streaming and Incremental Lineage Capture

A tile pyramid is the worst case for naive lineage capture. One vector source at zoom fourteen expands into millions of output artefacts, each technically a derived entity, and a system that emits one lineage record per tile will generate more provenance than data. This how-to captures tiles at the granularity that answers real questions — which source version is behind the tile a user is looking at — without producing a record per artefact.

The reframing that makes it tractable: a tile is not an entity, a tile generation run over a region is. Individual tiles are addressable positions within an output, the way pixels are addressable positions within a raster, and nobody records provenance per pixel.

Prerequisites

  • A tile pipeline with an identifiable run boundary — a full rebuild, a region refresh, or a dirty-tile pass.
  • Source dataset versions resolvable at run time, per Streaming and Incremental Lineage Capture.
  • A way to express which tiles a run touched compactly — a bounding extent, a quadkey prefix set, or a dirty list.
  • Somewhere to write run records that the tile server can later query cheaply.

Record Runs and Coverage, Not Tiles

The unit of the lineage record is the run; the tiles it produced are described by a coverage expression stored on that run.

Granularity choices for tile lineage Per-tile records are unaffordable, per-pyramid records are too coarse to answer regional questions, per-run with a coverage expression sits between. GRANULARITY RECORDS / MONTH ANSWERS one record per tile the obvious implementation ~400 000 000 everything, at a cost nobody will pay one per run + coverage quadkey prefixes or extent ~2 000 which sources built the tile at any address one per pyramid version whole-set granularity ~30 nothing regional — partial refreshes become invisible

The middle row is the working choice, and the reason is the bottom row’s failure mode rather than the top row’s cost. Tile pyramids are almost never rebuilt whole; they are refreshed regionally when a source changes over some area. A per-pyramid record cannot express that, so it reports the whole pyramid as being at the newest version when most of it is months old.

Express coverage in whatever form the pipeline already computes. If it works from a dirty-tile list, store the list compressed or as a quadkey prefix roll-up. If it works from a bounding box, store the box and the zoom range. The coverage expression only needs to support one query: given a tile address, which runs touched it.

The Query That Justifies the Whole Scheme

Everything above is in service of answering one question at tile-serving time, and designing backwards from it keeps the scheme small.

The question is: a user is looking at this tile and says it is wrong — what produced it? The answer needs the most recent run whose coverage contains the tile address, and from that run, the source versions and the pipeline version. Nothing else is needed at that moment.

Index for it directly. A run table with a coverage geometry indexed spatially, or a quadkey-prefix table indexed on the prefix, answers this in a single indexed lookup. Ordering by run time descending and taking the first row gives the answer, because a later run over the same tile supersedes an earlier one.

A second question arrives soon after and is worth designing for: which tiles are stale with respect to their sources? That one runs the other way — from a source version to the tiles built before it landed — and it is answered by the same table with the ordering reversed, provided the source versions were recorded rather than merely named.

Resist adding fields the question does not need. Every optional field on a run record is one more thing to populate correctly at three in the morning, and the ones nobody queries are the ones that silently rot. Add fields when a second real question arrives, not in anticipation of one.

Sources Are Versions, Not Names

The single highest-value field on the run record is the resolved source version, and it is the one most often stored as a name instead.

Recording that a run consumed buildings tells you nothing six months later, because buildings has changed. Recording that it consumed buildings@2026-05-14T03:11Z or buildings#a91f3c makes the run reproducible and makes the “what changed?” comparison between two runs mechanical.

Resolve the version at read time, not at configuration time. A pipeline configured against “latest” must record what latest actually resolved to during that run — otherwise the record documents an intent rather than an event, and the two diverge exactly when it matters.

Record every source, including the ones that feel like infrastructure. A basemap style file, a label-placement ruleset and a font set all affect what the tile looks like, and a rendering change attributed to a data change wastes a day of investigation. If it can change the output, it is a source.

The pipeline’s own version belongs in the same list. A tile that changed because the renderer was upgraded is indistinguishable, from the output alone, from one that changed because the data moved — and the second is the one worth investigating. Recording the renderer version and the style hash lets a comparison between two runs immediately separate the two cases, which is usually the first question anyone asks and the one that a source-only record cannot answer.

Sizing the Coverage Expression

Coverage expressions grow badly if left unconstrained, and the growth is what turns a tidy scheme into a slow one.

Rolling a dirty-tile list up to prefixes Raw list is exact but large, bounding box is small but grossly over-covers, prefix roll-up sits between with a tunable over-coverage budget. raw dirty list 180 000 entries over-coverage 0% too big to index well prefix roll-up 1 400 quadkey prefixes over-coverage 6% the working choice bounding box 1 extent over-coverage 840% answers are wrong Over-coverage is a false positive: the run is reported as having touched a tile it did not. Set a budget, roll up until it is reached, and record the achieved figure on the run.

Recording the achieved over-coverage on the run turns an approximation into a stated one. A reader who knows the coverage is six percent generous can weigh an answer accordingly; a reader who assumes exactness will chase a phantom.

Bound the roll-up by over-coverage rather than by prefix count. A run touching one contiguous region rolls up beautifully and a run touching scattered edits does not, and a fixed prefix budget forces the second case into a wildly inaccurate expression to meet a number that was chosen for the first.

Tying the Served Artefact Back to Its Run

The lineage record describes what the pipeline produced. What the user complained about is what the CDN served, and those are the same thing only if you can demonstrate it.

Cache layers between the run and the user Two cache layers can each hold an artefact from an earlier run; a run stamp in the response header is what identifies which one the user actually received. tile build run 4471 origin cache may hold run 4468 CDN edge may hold run 4455 user Without a stamp, the lineage answers for run 4471 and the user is looking at 4455. X-Tile-Run: 4455 — set at build, travels with the bytes through every cache The user pastes the header; the lineage lookup becomes exact instead of probable.

Stamp the run identifier into the tile response at build time so it travels with the bytes. A header is the cheapest carrier for raster tiles; for vector tiles a metadata layer or a tag in the tile’s own header works and survives more transformations.

This turns the diagnostic conversation from an inference into a lookup. Without it, the honest answer to “what produced this tile?” is “run 4471, unless a cache is serving something older, which it probably is” — and that qualification makes the whole capture scheme less useful than it should be.

Verification

Round-trip a known dirty-tile list through the roll-up and assert that every tile in the list is contained by some emitted prefix. Containment must be total — a roll-up that drops tiles produces silently wrong answers rather than merely imprecise ones.

Assert the over-coverage figure independently by counting tiles covered by the prefixes and comparing against the input list length. Compute it in the test rather than trusting the roll-up’s own reported number, since a bug in the roll-up is likely to be a bug in its accounting too.

Assert the serving query returns the latest run for a tile covered by three runs at different times. Ordering bugs here are invisible in normal operation because the newest run is usually also the only one in a recent window.

Gotchas & edge cases

  • Zoom levels are not independent. A source change usually dirties a tile at every zoom that shows it, and a run that refreshes only zoom fourteen leaves twelve and thirteen stale. Record the zoom range in the coverage expression or the answers will be right for one level and wrong for the rest.
  • Cached tiles outlive their runs. A CDN serving a tile generated three runs ago makes the lineage answer disagree with what the user sees. Record the cache key or the generation timestamp in the tile’s own headers so the served artefact can be tied to a run directly.
  • Failed partial runs still changed tiles. A run that died halfway wrote real tiles. Record the coverage actually completed rather than the coverage attempted, or the record claims a refresh that did not happen.
  • Prefix roll-up assumes a quadtree scheme. Tiling schemes that are not power-of-two quadtrees have no prefix containment property, and the roll-up must be replaced with an interval or geometry union.
  • Over-coverage compounds across runs. Three overlapping generous runs make almost every tile look recently refreshed. Keep the budget tight where the answer feeds anything automated.