FR: Use etags to skip work for unchanged vector tiles

[RivkaMandelbaum]

User Story

As a developer working with maps that contain a lot of vector tile data and are used on underresourced machines, I would like to introduce the ability for the vector tile loading process to respect etag matches such that it will skip parsing and rendering when a tile that was loaded hasn’t changed.

Rationale

• Currently, Maplibre will respect the max-age header and refetch tiles at the given interval via the TileManager (expiry data is set via max-age headers here and here). However, vector tile loading, parsing, and rendering works the same way regardless of whether the tile has changed since we last requested it or not.
• Even when there is a local or remote cache hit (304), such that the tile is exactly the same, all of the work that happens after getting the response from loadVectorTile is repeated. This includes WorkerTile#parse() and firing a data event in TileManager to trigger repaint and rendering.
• If we maintained a mapping of tile ID to etag and compared the existing etag for a given tile with the etag from the tile fetch response, we could skip all of the WorkerTile#parse() work for that tile, and instead immediately set the loaded tile to the cached tile for that ID. This would reduce recomputation when the tile hasn’t changed.
• If we additionally add a way for vector_tile_source#loadTile to communicate to the TileManager that the tile was served from cache, e.g. an optional field on Tile isLastLoadedFromCache?: boolean, we could additionally skip emitting the data event in TileManager#_tileLoaded() for etag matches, reducing the GPU burden.

My proposal would look something like adding the mapping to VectorTileWorkerSource class:

tileETags: {[_: string]: string};

In loadVectorTile, we fetch the tile data. We’d want to modify this to forward the etag header:

const response = await getArrayBuffer(params.request, abortController); 

Then we can use that to check if the etag matches a stored etag and return a new WorkerTileResult type if it does:

        const storedEtag = tileETags[tileUid];
        if (storedEtag && response.etag && storedEtag === response.etag) {
            return {
                type: 'etag_match',
                etag: response.etag,
                cacheControl: response.cacheControl,
                expires: response.expires
            };
        }

If it doesn’t match, we can store it for the future and return the data as usual:

if (response.etag) {
    this.tileETags[tileId] = response.etag;
}

A level higher up in loadTile, if we encounter an etag_match, we can now short-circuit early by setting the loaded tile to the cached one. This skips all of the parsing work.

if (response.type === 'etag_match') {
    this.loaded[tileUid] = workerTile;
    const result: WorkerTileResult = {
        type: 'etag_match',
        ...cacheControl
    };
    return result;
}

const rawTileData = response.rawData;
workerTile.vectorTile = response.vectorTile;
// We only do this if we didn't have an etag_match above!
const parsePromise = workerTile.parse(response.vectorTile, this.layerIndex, this.availableImages, this.actor, params.subdivisionGranularity);
this.loaded[tileUid] = workerTile;
...

We can also add a way to communicate to the TileManager that the tile was loaded from cached and doesn’t need to be rerendered, for example adding an optional boolean flag to the Tile class and updating it in VectorTileSource#_afterTileLoadWorkerResponse:

if (data && data.type === 'processed' && tile.isLastLoadedFromCache) { 
    tile.isLastLoadedFromCache = false;
} else if (data && data.type === 'etag_match' && !tile.isLastLoadedFromCache) { 
    tile.isLastLoadedFromCache = true;
}

The TileManager can now skip unnecessary work in _tileLoaded:

_tileLoaded(tile: Tile, id: string, previousState: TileState) {
        ...
        // Skip backfill DEM, initialize tile state, and firing data event for an unchanged tile
        // This will prevent repainting and rendering a new frame when the tile is the same
        if (tile.isLastLoadedFromCache) { 
            return;
        }
        
        if (this.getSource().type === 'raster-dem' && tile.dem) {
            backfillDEM(tile, this._inViewTiles);
        }
        this._state.initializeTileState(tile, this.map ? this.map.painter : null);

        if (!tile.aborted) {
            this._source.fire(new Event('data', {dataType: 'source', tile, coord: tile.tileID}));
        }
    }

Impact

Without this feature, there is significant GPU pressure whenever we fetch tiles because a given tile source’s max-age has been reached. This results in noticeable GPU spikes that cause slowdowns and frequent crashes for users.

[HarelM]

Thanks for taking the time to write this down!
I think the following PR is similar to what you would like to achieve from a network perspective, but there's a lot more here from a performance perspective that is not captured in this PR, I believe.

• Performance: Use 'If-Modified-Since' header when re-requesting expired tiles #5799

I also think this should be applied to all the sources, not just vector source, right?

In order to push this forward I would recommend a flow diagram with the proposed changes to better explain where the changes you would like to introduce are in the current flow.
After that we can continue to a PR.
Generally speaking, I think this is a good idea.

We can also consider doing it in two phases - the first one is just to avoid network traffic, and the second one is to avoid unneeded computation.

[RivkaMandelbaum]

Thank you for the thoughts here!

1. I would think of the PR you linked as a separate but related piece of work. That PR deals with the network side - allowing fewer bytes to flow over the network when we can use cached data instead. This PR deals with what happens after that: given that we have a cache hit, don't do computational or rendering work for the tile. The approach used in this PR assumes that the difference between 304s and 200s is opaque (since the response.status field in the ajax util will be a 200 regardless of whether the actual status was a 200 or a 304) and instead tracks the etags directly, which means it doesn't rely on the linked PR to work. Both pieces of work seem valuable here but I don't think they have to depend on each other. Let me know what you think.
2. Re: other sources, I specified vector tile sources because those are the ones in our production use cases that are most likely to have a lot of fast-updating data with a short (<10s) stale time. I don't know if other sources will benefit from this change as much and didn't want to increase the scope too significantly. Do you think it would be reasonable to proceed with a PR that just implements this for vector tile sources to start?

I will try to draw up a flow diagram sometime this week, thank you for the recommendation!

[HarelM]

This is just a hunch at this point in time, but I think that the logic of don't redraw/reload tile if it's the same should be handled in tile manager which should be source agnostic, but I might be wrong.
The bottom line is that I think the logic should be fairly the same for all sources.
If this is not the case then we can discuss the design and understand why it's specific to vector tiles.
But an initial diagram would be a good starting point for this discussion.

[RivkaMandelbaum]

Here's a diagram based on the life of a tile diagram for how this would work in the case of an etag match:

sequenceDiagram
  %%{init: { 'sequence': {'messageAlign': 'left', 'boxTextMargin': 5} }}%%
  participant map
  participant tile_manager
  participant source
  participant ajax
  participant glyph manager
  box rgba(128,128,128,0.1) worker
    participant worker
    participant worker_source
    participant worker_tile
    participant bucket
    participant worker_ajax
  end

  map->>tile_manager: update(transform)
  tile_manager->>tile_manager: compute covering<br> tiles
  tile_manager->>source: loadTile() for each<br>missing tile
  alt raster_tile_source [unchanged]
  else vector_tile_source/geojson_source
    source->>worker: loadTile()
    worker->>worker_source: loadVectorTile()
    alt vector_tile_source
    worker_source->>worker_source: store map with etag keys and tile values
    worker_source->>worker_ajax: getArrayBuffer() **and etags from response header**
    worker_source->>source: return loaded tile with `unchanged` type from tileETags cache
    else geojson_source [unchanged]
    end
      worker_tile-->>source: no callback needed
      source->>source: loadVectorData() no work needed
  end
  tile-->>tile_manager: Tile
  tile_manager->>tile_manager: no _backfillDEM() needed
  source->>source: no event fired
  tile->>tile_manager:<br>
  tile_manager->map:<br>
   map->map: no event fired or repaint needed

Loading

Here's the full flow from life of a tile with a little more detail:

• Call TileManager#update(transform) on each map data source. This computes the ideal tiles that cover the current viewport and requests missing ones. When a tile is missing, searches child/parent tiles to find the best alternative to show while the ideal tile is loading.
• Call Source#loadTile(tile, callback) on each source to load the missing tile. Each source implements this differently:
  • RasterTileSource#loadTile just kicks off a getImage request using src/util/image_request which keeps a queue of pending requests and limits the number of in-progress requests.
  • RasterDEMTileSource#loadTile starts off the same to fetch the image, but then it sends the bytes in a loadDEMTile message to a worker to process before returning the results. Getting pixels from the image response requires drawing it to a canvas and reading the pixels back. This can be expensive, so when the browser supports OffscreenCanvas, do that in a worker, otherwise do it here before sending.
    • [in web worker] RasterDEMTileWorkerSource#loadTile loads raw rgb data into a DEMData instance. This copies edge pixels out to a 1px border to avoid edge artifacts and passes that back to the main thread.
  • VectorTileSource#loadTile sends a loadTile or reloadTile message to a worker:
    • [in web worker] Worker#loadTile handles the message and passes it to VectorTileWorkerSource#loadTile
      • Calls VectorTileWorkerSource#loadVectorTile which stores etag to loaded tile in a map and uses
        • ajax#getArrayBuffer() to fetch raw bytes and etag header
        • if the etag header matches an existing cached result:
          • put the cached result into a new WorkerTile instance. It doesn't need to be parsed again, so pass the tile back to the main thread here with type: unchanged.
        • if it's not a match, use:
          • pbf to decode the protobuf, then
          • @mapbox/vector-tile#VectorTile to parse the vector tile.
          • The result goes into a new WorkerTile instance with type processed.
      • If it's not a match for a cached tile: Calls WorkerTile#parse() and caches the result in the worker by tile ID:
        • For each vector tile source layer, for each style layer that depends on the source layer that is currently visible ("layer family"):
          • Calculate layout properties (recalculateLayers)
          • Call style.createBucket, which delegates to a bucket type in src/data/bucket/*, which are subclasses of src/data/bucket
          • Call Bucket#populate() with the features from this source layer in the vector tile. This precomputes all the data that the main thread needs to load into the GPU to render each frame (ie. buffers containing vertices of all the triangles that compose the shape)
        • Most layer types just store triangulated features on that first pass, but some layers have data dependencies, so ask the main thread for:
          • Font PBFs (getGlyphs)
            • Handled by GlyphManager on the main thread which serves as a global cache for glyphs we’ve retrieved. When one is missing it either uses tinysdf to render the character on a canvas, or makes a network request to load the font PBF file for the range that contains the missing glyphs.
          • Icons and patterns (getImages({type: 'icon' | 'pattern' }))
            • Handled by ImageManager on the main thread which caches images we’ve already fetched and fetches them if missing
      • When all data dependencies are available WorkerTile#maybePrepare(), create a new GlyphAtlas and ImageAtlas that store the used font glyph symbols and icon/pattern images into a square matrix that can be loaded into the GPU using potpack. Then call StyleLayer#recalculate() on each layer that was waiting for a data dependency and:
        • Call addFeatures on each bucket waiting for a pattern
        • Call src/symbol/symbol_layout#performSymbolLayout() for each bucket waiting for symbols, which computes text layout properties for the zoom level and places each individual symbol based on character shapes and font layout parameters, and stores the triangulated symbol geometries. Also computes collision boxes that will be used to determine which labels to show to avoid collisions
      • Pass the buckets, featureIndex, collision boxes, glyphAtlasImage, and imageAtlas back to the main thread
  • GeojsonSource#loadTile() also sends a loadTile or reloadTile message to a worker. The handling is almost exactly the same as a vector tile, except GeojsonWorkerSource extends VectorTileWorkerSource and overrides loadVectorTile so that instead of making a network request and parsing the PBF, it loads the initial geojson data into geojson-vt and calls the getTile method to get vector tile data from the geojson for each tile the main thread needs.
  • ImageSource#loadTile() computes the most-zoomed-in tile that contains the entire bounds of the image being rendered and only returns success if the main thread is requesting that tile (the image was already requested when layer was added to the map)
• When the vector sources (geojson/vector tile) responses get back to the main thread, it calls Tile#loadVectorData with the result. If the type is unchanged, set a field on the tile to indicate this like isLastLoadedFromCache: true and return here. If not, deserializes and stores the buckets for each style layer, image/glyph atlases, and lazy-loads the RTL text plugin if this is the first tile to contain RTL text.
• Back up in TileManager, now that it has the loaded tile:
  • If the tile.isLastLoadedFromCache is true, short-circuit here and skip firing a data event, therefore skipping repaint.
  • TileManager#_backfillDEM copies the edge pixels to and from all neighboring tiles so that there are no rendering artifacts when each tile computes the slope up to the very edge of the tile.
  • Fire a data {dataType: 'source'} event on the source, which bubbles up to TileManager, Style, and Map, which translates it to a sourcedata event and also calls Map#_update() which calls Map#triggerRepaint() then Map#_render() which renders a new frame just like when user interaction triggers transform change.

Let me know if another format would be useful for the flow diagram!

Regarding the difference between source types:

I think that the logic of don't redraw/reload tile if it's the same should be handled in tile manager which should be source agnostic

The logic of not redrawing and reloading in tile manager is fairly similar, but the difference would be (1) how to determine that the tile is the same and (2) how to communicate that to the tile manager.

[HarelM]

Thanks for the thorough write up! I hope researching all this flow allowed you to better understand what happens where.
We could consider adding to the source API a hasTileChanged or something similar to avoid the need to call all the reload/load logic I suppose - this can (maybe) call the header http to see if there's a change, or something else, and finally store the etag in the tile, similar to what we do for the cache control response.
There's already a (very) complicated cache logic in the main thread which is memory aware, so I'd like to avoid adding a cache in the workers if possible.
I'm guessing the solution need to involve the Tile class somehow as it currently store most of the state and data.
There's also a need to look into what happens when the tile expires but the data is the same - there's some timer logic involved in that as well.
Bottom line, from the diagram above and my personal knowledge, I still think most of the controlling logic should happen in the tile manager and the source and not in the worker.
I hope that helps, do let me know if I missed anything.

[RivkaMandelbaum]

Thank you for the thoughts here! That's an interesting idea - let me make sure I’m understanding the suggestion. I'm thinking this would mean something like:

1. In the Source API, add a method:

hasTileChanged?: (tileId: string, etag: string, _<any other params needed to fetch>_) => Promise<boolean>;

2. In VectorTileSource, implement the method:

async hasTileChanged(id: string, etag: string, _etc_): Promise<boolean> {
        const etagResponse = await /** ajax util which makes a HEAD request for the tile ID **/;
        return etagResponse === etag;
}

3. In TileManager:

Add _etagCache: { [tileId: string]: string}; (do not re-cache the tile itself)

In _loadTile conditionally call source.loadTile:

const tileEtag = this._etagCache[id];
const hasTileChanged = await this._source.hasTileChanged(id, tileEtag);
const existingTile = /** get the existing loaded tile from the tile_manager's cache **/
if (hasTileChanged || existingTile == null) {
     await this._source.loadTile(tile);
} else {
     tile = existingTile;
}
this._tileLoaded(tile, id, state, hasTileChanged);

In _tileLoaded, deal with the timer updates, and make later steps (backfillDEM, initializetileState, fire event) conditional on hasTileChanged.

Does that general outline look like a reasonable approach to you?

[HarelM]

Yes, maybe the etag can be stored in the Tile class so that there won't be a need for another cache?
But generally speaking this sounds like the right approach.