mbtiles output not stable/reproducible

[bbilger]

Hello,
I am currently working on #167
And for that I implemented a tool to compare the tiles of two mbtiles https://gist.github.com/bbilger/cbab2aeb9b66ababaffc55ad5ffbef45 (it's still WIP thus it's a gist, it will be part of the PR, then)

For quite some time I thought that I had a bug in my de-duping mechanism but it turns out that the result produced by planetiler is not stable.

$ wget https://github.com/onthegomap/planetiler/releases/latest/download/planetiler.jar
$ java -Xmx10g -jar planetiler.jar --download --area=monaco --mbtiles=monaco1.mbtiles > /dev/null 2>&1
$ md5sum monaco1.mbtiles
d0bde545e5f35cf6ceece120a31f205c monaco1.mbtiles

$ java -Xmx10g -jar planetiler.jar --download --area=monaco --mbtiles=monaco2.mbtiles > /dev/null 2>&1
$ md5sum monaco2.mbtiles
5998bd1005d3bfcb6560705bf15bfc9d monaco2.mbtiles

The produced mbtiles files doesn't contain anything time dependent as far as I can see, so the md5sum should match, but maybe I forget something and something in a sqlite file may be different despite equal content being written identically.

With my tool I can clearly see that the rank attribute changes when I compare monaco1.mbtiles with monaco2.mbtiles - delete line 140 to see that https://gist.github.com/bbilger/cbab2aeb9b66ababaffc55ad5ffbef45/revisions#diff-d887a55f182c151b60946bb3c4e61e449e5deaf3fb08110045277463a227f4e1R140

So that's the first question: is this normal that the rank attribute may differ?

If I go bigger and do the same with Australia, then it's not only the rank attribute that differs but even more things - this doesn't happen on many tiles but just a few:

• some features seam to be picked instead of others for some tiles
• even a few geometries might differ slightly

So that's the second question: are slight geometry and feature differences expected as well?

You can find the result of comparing two australia.mbtiles here: https://gist.github.com/bbilger/1dfd0584e95d0d2566e72f73846d9d95

Thank you!

[nyurik]

@bbilger I don't know as much as @msbarry about Planetiler, but my understanding is that it is possible for two runs to produce different results in two scenarios - one is ok, and one is not.

• tiles are generated with a "merge sort" method - Planetiler generates many slices (slice = a single geometry with tags for one tile, plus some sort key). Later the slices are combined together into a tile using the slice sort key to decide the ordering of geometries. It is quite possible for multiple slices to have the same sort key, so due to multithreading, multiple runs may produce different slice orderings. I don't see this as a big problem. For sort stability, we could use geometry's bytes in case of an identical sort key.
• there could be some bug somewhere, causing different data in tiles. Should be identified and fixed.

[msbarry]

Thanks, that looks like a useful tool @bbilger! Looking forward to the review. I think @nyurik's first bullet is the main culprit - when the sort key of 2 elements is exactly the same it's nondeterministic what order they'll be emitted due splitting work across threads. The ordering determines the rank and also visibility since we limit to the first N points in each cell of a grid which could lead to different points getting included. I opened #215 to track.

even a few geometries might differ slightly

Can you point out a specific example of that?

[bbilger]

Okay, thank you both for the explanation and the ticket. That explains why the rank differs, and here and there some features are chosen instead of others.

In order to avoid any confusion, let me rephrase "even a few geometries might differ slightly" to "even a few locations might differ slightly".
There are a few examples at the end in https://gist.github.com/bbilger/1dfd0584e95d0d2566e72f73846d9d95
For example

<<<
feature diff on coord {x=14505 y=9894 z=14}

additional in db0
---
VectorTileFeatureForCmp[layer=poi, normalizedGeometry=POINT (-19.875 211.5625), attrs={name_int=Stirling Tennis Club, name_de=Stirling Tennis Club, name=Stirling Tennis Club, subclass=tennis, class=pitch, name:latin=Stirling Tennis Club, name_en=Stirling Tennis Club}, group=-9223372036854775808]

additional in db1
---
VectorTileFeatureForCmp[layer=poi, normalizedGeometry=POINT (-18.6875 210.25), attrs={name_int=Stirling Tennis Club, name_de=Stirling Tennis Club, name=Stirling Tennis Club, subclass=tennis, class=pitch, name:latin=Stirling Tennis Club, name_en=Stirling Tennis Club}, group=-9223372036854775808]
>>>

But from your explanation I would assume now that in OSM there are duplicate entries for those POIs and housenumbers, and because of non-deterministic sorting, the single one that gets picked might differ.

[msbarry]

I think that's just another symptom of the same problem. There are 2 features with that same name close to eachother: https://www.openstreetmap.org/search?query=Stirling%20Tennis%20Club#map=19/-35.00901/138.71189

Try applying this change to your branch and see if the results come out consistent?

https://github.com/onthegomap/planetiler/compare/stable-sort

I'm also making it so that fix won't work anymore in #164 but if that patch works, I can figure out another way to achieve the same result.

[bbilger]

Unfortunately applying https://github.com/onthegomap/planetiler/compare/stable-sort does not make the output consistent. The rank attributes still differ.
It's okay, I just wanted to check why this is happening and if it's expected. If there were an easy way to make it stable then it were good, but if not then that's fine as well.

[bbilger]

@msbarry

One more thing I just noticed is that there are a few tiles with missing features and actually a different feature count. Is that still the same "problem" or a different one?

for i in {0..10}; do java -Xmx1g -jar planetiler.jar --download --area="australia" --mbtiles="data/australia-$i.mbtiles" --minzoom=8 --maxzoom=8; done

When I compare the generated mbtiles files then I see the following diffs on the following tiles.

<<<
feature diff on coord {x=227 y=154 z=8} - 608 vs 609 features

additional in db0
---
VectorTileFeatureForCmp[layer=place, normalizedGeometry=POINT (71.5625 9.8125), attrs={name_int=Blanchetown, name_de=Blanchetown, name=Blanchetown, class=town, name:latin=Blanchetown, name_en=Blanchetown}, group=-9223372036854775808]

additional in db1
---
VectorTileFeatureForCmp[layer=place, normalizedGeometry=POINT (61.1875 101.375), attrs={name_int=Walker Flat, name_de=Walker Flat, name=Walker Flat, class=town, name:latin=Walker Flat, name_en=Walker Flat}, group=-9223372036854775808]
VectorTileFeatureForCmp[layer=mountain_peak, normalizedGeometry=POINT (-33.8125 95.4375), attrs={name_int=Mount Pleasant, ele_ft=1781, name_de=Mount Pleasant, name=Mount Pleasant, class=peak, ele=543, name:latin=Mount Pleasant, name_en=Mount Pleasant}, group=-9223372036854775808]
>>>

<<<
feature diff on coord {x=234 y=143 z=8} - 2014 vs 2015 features

additional in db0
---


additional in db1
---
VectorTileFeatureForCmp[layer=mountain_peak, normalizedGeometry=POINT (-36.8125 125.375), attrs={name_int=Ben Mohr, ele_ft=2297, name_de=Ben Mohr, name=Ben Mohr, class=peak, ele=700, name:latin=Ben Mohr, name_en=Ben Mohr}, group=-9223372036854775808]
>>>

[msbarry]

Yes, I think that's a symptom of the same problem since they both use the the same sorting/filtering logic.

[phanecak-maptiler]

One example from Slovakia, which might not be ordering issue:

• Putyrovci: https://www.openstreetmap.org/node/2029218414
• Na Črchli: https://www.openstreetmap.org/node/2045121722

When generating Slovakia twice and then running compare on those two results:

feature diff on coord {x=1130 y=700 z=11} - featureCountMatches: true (412 vs 412)

additional in db0
---
VectorTileFeatureForCmp[layer=place, normalizedGeometry=POINT (322.0625 -246.6875), attrs={name_int=Putyrovci, name_de=Putyrovci, name=Putyrovci, class=hamlet, name:latin=Putyrovci, name_en=Putyrovci}, group=-9223372036854775808]

additional in db1
---
VectorTileFeatureForCmp[layer=place, normalizedGeometry=POINT (281.8125 -224.875), attrs={name_int=Na Črchli, name_de=Na Črchli, name=Na Črchli, class=hamlet, name:latin=Na Črchli, name_en=Na Črchli}, group=-9223372036854775808]
>>>

[phanecak-maptiler]

follow-up on previous:

1. sorting of SortableFeatures is the main point: If they get sorted differently between two runs, then different features may make it past certain layer limits, hence difference in output even if input is same: one feature present in result from run 1, but missing (replaced with other feature) in result from run 2
2. one problem with sorting are features, which are different (SortableFeature.value()) but their key (SortableFearture.key()) is same: Here it helps that if same key is detected, also values are evaluated while sorting:
   • same feature sorted consistently on same position -> consistently passing/not passing through layer limits -> consistent result
3. another problem is use of idGenerator.incrementAndGet() in stages which are multi-threaded: In such cases, based on slight scheduling variations, same feature will get different ID between two runs, hence affecting sorting of features thus also causing some differences in output even if input is same.
   • Stable ID assignment gets that fixed.
   • So far I've experimented with removal of idGenerator.incrementAndGet() and using sourceId instead (i.e. ID from OSM or Nat. Earth).

Pull request (PR) which should be fixing this: #382

• The diff of .mbtiles from two runs is still not yet empty, but is much smaller. And remaining differences seems to be caused by something other than sorting hence I would like to target that with different PR.

Feedback welcome. Typically if you can check with your maps/use-cases.

[phanecak-maptiler]

I forgot to include some results from my testing: I was using Slovakia as a testing area and:

• diffs before (i.e. current main branch), three runs, diff between 1st and 2nd and then 2nd and 3rd:

...
INF - totalTiles=30811 tilesWithDiffs=35
...
INF - totalTiles=30811 tilesWithDiffs=30

• diffs after (i.e. with changes from this PR applied), again three runs ...:

...
INF - totalTiles=30811 tilesWithDiffs=1
...
INF - totalTiles=30811 tilesWithDiffs=2