Byte-for-byte reproducible output: what still differs between multi-threaded runs

[geoneutrino]

We had several aspects of deterministic output / reproducible builds in the last time. In my scenarios i use --threads 1 for testing and comparing but this is a bigger topic e.g. CI job disabled and mentioned in #939 and so on. The following is my current insight discussed with AI and analysed the code. Long story short, i want to collect opinions on this if it would be good to have the reporducible output in all scenarios or not because it would be a bigger task and also needs some decisions how to do it. See below

---

The verify-generated-tiles CI job was disabled in bf237fa because "output is not yet byte-for-byte reproducible between runs". #939 made the clip cache deterministic, and #942 / #889 handle the Lua pairs() order in POI ranking. I wanted to know what else makes two runs differ, so I measured it. Below are four further sources I found, two of them confirmed with prototypes, plus some open questions about how they should be fixed. I'd rather agree on an approach here before opening a PR.

Setup

• master at 4e0f03d, local Test data (~350 MB), 12 threads, 93,930 tiles.
• A custom profile with include_ids: true and combine_polygons_below: 14 on landcover / landuse.
• Lua 5.1, so the pairs() issue from Make POI tag key processing deterministic #942 cannot show up in these numbers.
• Two runs per variant, compared tile by tile. Each tile is classified as: identical bytes, same features in a different order, same feature order but differences inside features (tag order / key-value tables), or different content. Attributes are resolved through each layer's key/value tables, so a different table order alone does not count as a content change.
• With --threads 1 the output is reproducible. Everything below is about multi-threaded runs on a single machine. I have not looked at differences between platforms or compilers, which the CI job also compared.

Results

	master	+ fix 1	+ fixes 1 and 2
tiles with identical bytes	57,014	69,375	57,888
different feature order	25,820 (12 layers)	19,135 (12 layers)	2,493 (water_polygons only)
same order, different inside features	10,475	5,420	33,549
different content	621	0	0

The last column has fewer identical tiles than the middle one, but that is not a regression. Once the feature order matches, tiles that differ in both feature order and tag order get counted under "inside features" instead. How many tiles source 4 hits also varies from one pair of runs to the next. Neither prototype changed any geometry compared with the other variants, and neither made a measurable difference to runtime (59–67 s per run for all three).

The four sources

All four have the same pattern: an internal index that is handed out in insertion order, and is therefore scheduling-dependent, is used as an ordering key.

1. objectID decides the order inside a merge group

sortOutputObjectIDs sorts by layer, z_order, geomType, attributes and finally objectID. Objects with identical attributes are the ones that get merged, so inside such a group objectID alone decides the order.

objectID is not the OSM id. It is (store.first << ...) + offset, where the store is a thread_local LeasedStore taken from a shared list on first use (leased_store.h). Both parts depend on scheduling, so the same way gets a different objectID in each run.

In ProcessObjects that changes two things: the order of union_many (L445), which gives a different ring order and sub-pixel area differences, and which OSM id the merged feature gets, because oo = *jt keeps the last one (L395, L434, L447). This is the only source that changes content. In our run that was 621 tiles in landcover, landuse and poi.

Prototype, which brought content differences from 621 tiles to 0:

 		if (x.oo.attributes > y.oo.attributes) return false;
+		if (x.id < y.id) return true;
+		if (x.id > y.id) return false;
 		if (x.oo.objectID < y.oo.objectID) return true;

This only helps when there is an OSM id. All profiles shipped in resources/ use include_ids: false, and OutputObjectXY doesn't store an id at all.

2. AttributeIndex decides the order between attribute groups

attributes in the same comparator is an AttributeIndex: shard plus the position where the set was first inserted (attribute_store.cpp L447–L451), which again depends on which thread got there first. Merging is not affected, because equal sets still have equal indices. But the order of groups within a layer, and so the feature order in the tile, changes in every layer.

AttributeSet::hash() is not a stable replacement either, because it combines pair indices (attribute_store.h L261), and those are handed out the same way (L265–L270).

Prototype: before sorting, build a content key once per distinct attribute set in the tile (key text, value type, value and minzoom, with pairs sorted by that content), and compare that key instead of the index. This brought the feature-order differences from 12 layers down to water_polygons. To keep the experiment small it reached the AttributeStore through a global pointer set in main() after finalize(), so it is not something I'd propose as it stands.

3. Objects without an OSM id are still ordered by objectID

What remains after fixes 1 and 2 is feature order in water_polygons only, which is where the coastline shapefile's polygons go. They have no OSM id, so the tie-break in fix 1 falls through to objectID.

4. Tag order inside a feature

writeAttributesTo writes tags in the order forEachPairUnsafe returns them, which follows the pair indices. Features, their attributes and their order are then all identical, but the tag order and the layer's key/value tables differ. In one pair of runs that was about a third of all tiles. I assume MvtAttributeMemo follows the same order, but I have not checked that separately.

Questions

1. Is byte-for-byte reproducibility the goal, so the CI job can come back, or would reproducible content be enough? Sources 2 and 4 only change the order, not what is rendered.
2. For 1 and 3, what should the stable key be when there is no OSM id? Options I can see: store the id in OutputObjectXY as well (memory), make objectID independent of scheduling (e.g. derived from input position instead of the leased store), or for shapefiles use the record number.
3. For 2, would you rather pass the AttributeStore into sortOutputObjectIDs and compare by content, or renumber AttributeIndex in content order once after finalize()? The second keeps the hot path as it is, but every stored OutputObject would need its index remapped.
4. For 4, sort the pairs by key when writing, or put them into a canonical content order in finalizeSet?

I'm happy to turn whatever approach you prefer into a PR, and to share the comparison script and the two prototype commits.

[dktue]

Thanks for digging into this, @geoneutrino, and for measuring it so carefully. A few data points and thoughts from our side:

What we see. In all our Germany comparisons between two runs of the same build (OpenMapTiles profile, include_ids: false, 32 threads, compared per tile by area/length per layer and tag group), the only layer whose content differs is poi. That matches your source 1 (merge order and the kept id inside groups with identical attributes). For every performance PR we therefore had to compare semantically rather than byte for byte, and we always had to explain the poi noise. Reproducible output would make verifying such changes much simpler.

Q1: that's really for @systemed to decide. From the verification side, reproducible content (your fixes 1 and 3) would already remove the noise we keep explaining; byte-for-byte on top would mainly bring back the CI tile check.

Q2: an idea for objects without an OSM id. Storing the id in OutputObjectXY would add 8 bytes per output object, which adds up to gigabytes on the planet, and objectID is also the geometry's address in the leased store, so making it scheduling-independent means changing how stores are handed out. Since the tie-break only matters inside groups where everything else is equal, a cheaper option might be to break those ties by geometry content (e.g. first point, then point count), if the geometry is at hand there. That needs no extra memory and would also cover the shapefile polygons in water_polygons (your source 3).

Q3: performance shouldn't decide it. From our profiles (Germany, 32 threads), sortOutputObjectIDs is about 0.3% of total CPU and std::sort internals another ~0.3%; finalizeObjects is 0.05%. So even a content comparison that made the per-tile sort several times slower would cost only around 1–2% overall. That makes the simpler option (compare by content in the comparator) look fine, and the remapping pass after finalize() probably isn't worth its complexity.

Q4: sorting the pairs once per set in finalizeSet sounds cheaper than sorting on every write, since each distinct set is stored only once.

One coordination note: #972 (parallel finalizeObjects) and #966 (tile batches handed out on demand) touch the same sorting and finalizing code. Both keep today's order, so they don't conflict in behaviour, but whichever lands second will need a rebase.

Offer: when you have a branch or the two prototype commits, we're happy to benchmark them on our server (full planet and Europe, 32–96 threads) and run our semantic tile comparison, so any cost shows up before a decision.

[geoneutrino]

Thanks, this is very helpful. I built a prototype (co-authored and data tested by Claude) along those lines, on current master: https://github.com/geoneutrino/tilemaker/tree/prototype/deterministic-output

• Attribute sets are compared by a content hash (key names, values, minzoom), with a full content comparison on collisions. The hash is cached per thread.
• No ids added to OutputObjectXY. Ties are broken on the OSM id where it exists, then by geometry, as you suggested. Only stored geometries (relations, shapefiles) need that: OSM ways and nodes carry their OSM id in the objectID, so for them the objectID is already deterministic. Within stored geometries it is first point plus point count, and a hash over all points only if those tie too.
• Tag order: sorted by key name when writing (once per set and layer via the attribute memo), not in finalizeSet, because key indices aren't final yet at that point and the set's storage layout doesn't allow an arbitrary order.

Test data results: two runs with all threads and a single-threaded run are byte-identical, with include_ids true and false, and with the OpenMapTiles profile (on master 28,050 of 94,709 tiles differ between two runs). Compared to master, merged geometry is unchanged; only which id survives a merge differs. I couldn't measure a runtime or memory difference on Bangladesh (12 threads); a planet run at 32–96 threads would tell much more, if your offer still stands (Bangladesh is my test du to very complex water polygons, can test with other extracts locally too)

Can turn this into a PR, rebased onto #972 / #966, whichever lands first.

[dktue]

Thanks for the prototype, @geoneutrino. We ran it on the planet and on Germany. Short version: it costs nothing measurable, and together with #942 every tile is reproducible, byte for byte.

Planet

master d0ab14b vs. your prototype on top of it. Planet .pmtiles with --store --fast and the OpenMapTiles profile, on a 96-thread server.

	wall	user CPU	heap peak
master, 32 threads	1997 s	41,950 s	24.8 GB
prototype, 32 threads (2 runs)	1917 s / 1923 s	41,549 s / 41,885 s	25.5 GB / 25.6 GB
master, 96 threads (2 runs)	1807 s / 1552 s	76,335 s / 59,727 s	27.7 GB / 28.4 GB
prototype, 96 threads (2 runs)	1561 s / 1611 s	59,560 s / 59,892 s	29.2 GB / 29.4 GB

• 32 threads: same speed or slightly faster (wall −4%, CPU −0.2% to −1%). Heap +0.7 GB (+3%).
• 96 threads: the runs vary too much to resolve a few percent either way: master's two runs are 255 s apart. CPU is the same as master's second run, and heap is about +1 GB.
• Output size: +0.1% (76.68 GB vs. 76.59 GB at 32 threads), which fits merges keeping a different id.

Reproducibility (Germany, .pmtiles)

Compared tile by tile; "content" means the same features, attributes and geometry, in any order.

	tiles with different content
master, 2 runs at 32 threads	44,317
prototype, 2 runs at 32 threads	41,624
prototype + #942, 2 runs at 32 threads	0 of 273,199
prototype + #942, 32 vs. 8 threads	0 of 273,199

With the prototype alone, the remaining differences were all in poi. That's the pairs() order in GetPOIRank() that #942 fixes, which your Lua 5.1 setup can't show. We also tried the prototype with LuaJIT, and poi still differed there, so #942 is needed regardless of the Lua version.

With #942 applied, we also compared the stored tile bytes (compressed, as written) of two 32-thread runs: all 273,199 tiles are byte-identical. The .pmtiles files as a whole still differ (by 1.5 KB here), but only in where each tile sits in the file and in the directory that points to it. The PMTiles writer appends tiles in the order the threads finish them. Writing in a fixed order would make the whole file byte-identical; that's a separate change in the writer.

So from our side: the prototype plus #942 gives reproducible tiles at no measurable cost, and that would let us drop the poi caveat from all our comparisons. We'd be glad to see it as a PR.

One follow-up on the last step to byte-identical files: making the PMTiles writer write tiles in a fixed order (and therefore a fixed directory). Would you like to include that in your PR, or should we take it as a separate PR on top? Either is fine with us. We just don't want to both work on it.

[geoneutrino]

Thanks a lot for the planet benchmark! The PR is up: #981

On the PMTiles writer: please take it as a separate PR on top, it fits better with your #966 work and we won't both be working on it. Two notes from looking at it:

• saveTile appends tiles in thread completion order, and the tiny-tile dedup cache (tinyCache) depends on that order too. With ordered appends the directory offsets, and so the compressed directories, should become identical as well (probably your 1.5 KB).
• mbtiles has the same issue at file level: tile content is identical, but the SQLite insert order (and so the page layout) follows thread completion.

Two changes in the PR compared to the prototype you measured: the hashes are now platform-independent (boost::hash changed between Boost versions, which would break the cross-runner comparison in CI), and the thread_local sort buffers are gone. They stayed allocated per thread for the whole run, which may be part of the +0.7–1 GB heap. If you get the chance to re-run the heap peak, I'd be curious whether it moved.

While verifying, I also found that --store read relations several times on extracts that span more than one shard (#980). The planet isn't affected.