Scaling Tilemaker to the entire planet, even when it doesn't fit in RAM

[cldellow]

I love Tilemaker's Lua-scripting approach. It's super accessible to a broad class of users.

I also like Tilemaker's internals. There's room for optimization in the implementation, but the overall architecture makes spelunking and tweaking things a joy.

Over the past few weeks, some ideas to improve Tilemaker's performance on large PBFs have been gelling in my mind. Do they fit your vision for the project, or your future code changes in refactor_geometries? That's where I'd need your feedback.

Would you be interested in hearing them?

I'm also mindful that Tilemaker is a passion project, not your job, and I'm just some rando who has shown up and is now generating a flood of work for you in the form of PRs and discussions, and possibly stepping on your toes with your intended code changes. It's totally fine to tell me thanks, but no thanks.

The ideas are in service of achieving these goals:

• Tilemaker scales up and down on PBFs: small PBFs are instantaneous, large PBFs (up to planet size) are fast
• Tilemaker scales up on hardware: more RAM => faster, more CPUs => faster
• Tilemaker scales down on hardware: 16 GB of RAM is enough to generate the planet, albeit slowly
• iterating on a Lua profile is fast, perhaps faster than building an mbtiles from scratch

[systemed]

Absolutely - very happy to hear ideas and get PRs. I'm far from the best C++ programmer in the world so I'm pretty relaxed about contributions. Reducing tilemaker's execution time and memory usage are the two things I'd like to see most, so any PRs or ideas towards that are great.

It might be helpful to have a bit of a braindump on what I see next for tilemaker:

refactor_geometries

The basic idea here is to make it possible to serialise geometries to disk, segmented by area (typically the area of a z6 tile), so that they can be read back in one-by-one. This would have two benefits when not working entirely in-memory:

• RAM: Currently tilemaker keeps the entire object/tile index in memory, which is pretty huge. Working one chunk at a time means we won't need to do this.
• Performance: With --store, tile output is mostly IO-blocked, waiting to retrieve stored geometries from SSD. By writing tiles one z6 area at a time, having loaded the geometries into RAM, all accesses will be much quicker. Typically my 16-core machine is only working at 100%-200% CPU when using --store so there's massive improvement possible here.

So the process becomes:

• Open temporary files for each area.
• In the PBF/SHP reading phase, whenever we output an object (from Lua), append it to the tempfile for each area it crosses. (Often this will just be one area, but a large object may cross two or more areas, and we'll need a special planet-spanning area for features shown at <z6.) Don't write it to the object/tile index.
• In the tile writing phase, proceed one area at a time, reading in the tempfile for that area. When reading it in, populate the object/tile index for that area only.
• Delete tempfiles on exit.

This supersedes mapsplit support so we can remove that. I would suggest we just integrate it into --store rather than adding a new option.

It will require further refactoring to make sure all serialise/deserialise methods are in a sensible place. Perhaps something like

TileDataSource -> MemoryStore -> OsmMemTiles
                              -> ShpMemTiles
               -> OnDiskStore

where, when running with --store, we write to an OnDiskStore singleton; then, when reading the areas back in, we deserialise them into MemoryStore objects. But I've not really thought in great depth about it.

This is all "I'll do it when I have a spare minute" stuff, so don't be worried about stepping on my toes - if you want to implement any of it, or something in a similar but better way, go for it.

I'd like to merge refactor_geometries into master sooner rather than later, to avoid the hassle of repeatedly merging in new features, and because it already has memory improvements and cleaner code. The current blocker to doing that is that include_ids support is broken. Previously we indexed objects by OSM ID | object type bitfield, which was wasteful but preserved the ID. refactor_geometries moves to using sequentially generated IDs, which is much more efficient, but loses the ID. include_ids is a bit of a minority feature but useful for some. It should be possible to reinstate it pretty trivially by having a vector of OSM IDs, which we append to every time we generate a feature; we can then do a lookup by sequential ID every time we write out a feature. (This would only be used if include_ids was enabled, of course.)

Geometry clipping issues

I've done a separate issue about this - #594.

pmtiles support

pmtiles is deservedly getting a lot of traction and we should support it. There's already C++ reference code and the docs are good.

[cldellow]

Thanks, that's really helpful context! I'm out of my depths in the geometry clipping stuff, but I think I can help with the RAM and performance work. (And maybe, later, the pmtiles stuff -- for now, I've been content to convert in a post-build step.)

For performance, my thoughts run along similar lines to yours: use less memory generally & be able to keep the working set in RAM.

My proposed implementation differs a bit. I hope to lean in to the existing mmap approach, vs serializing geometries to disk by z6 tile. I'll do this by making the existing OSM stores much more efficient and lazily generating geometries as needed at write time. Something like:

Step 1 - lay the foundation to read/write in a disk I/O aware manner

• Remove the global TileIndex
• Add uint8_t x, uint8_t y to OutputObject (this is transitional, it can go away eventually; if FAT_TILE_INDEX is present, it'd be uint16_t)
• Add OutputObjects to a z6-specific list
• Cluster writes by z6 tile, generating a z6-specific TileIndex on demand for each z6 tile. For z0-z5 tiles, just scan the entire vector of OutputObjects to determine which apply to a given tile.

This should be straight-forward and can be immediately applied to refactor_geometries. It should give a ~500 MB savings for Great Britain.

Step 2 - be more memory efficient by swapping Boost geometries (16 bytes per point) for lazy geometries created from the OSM stores (~6-8 bytes per point)

• do Alternate node store #590 for ways and relations
  • Alternate node store #590 achieves ~6 bytes/node for NodeStore, I suspect we can achieve something like ~2.5 bytes/member node for ways, or better
• retain the node store and way store into the writing phase
• don't retain geometries in memory, nor write them to disk. Instead, generate geometries on demand from the stores.
  • shp files will have to be treated specially; I haven't thought too much about this yet

There might be a CPU impact here, but I suspect it can be mitigated with enough effort.

Step 3 - avoid thrashing on machines with limited RAM

Conceptually, today's OSM store is a single store covering z0.

This is inefficient for machines with limited RAM--it means a 4,096-byte page of memory might contain data from Singapore cuddled up next to data from San Francisco. If your data fits in RAM, this is fine. If it doesn't, it means you waste I/O reading irrelevant data about Singapore when writing San Francisco.

Instead, be able to subdivide the globe into an optimal number of stores, where each store (a) can fit in memory at read/write time and (b) only contains data about things that are close to each other.

A naive approach: have 16 stores, 1 per z2 tile. This is a bit inefficient, as there's some overhead in the data structures. Maybe good enough, though!

A better approach might be:

• for each z6 tile, compute the # of OSM objects in it, and persist this in the Tilemaker source code
  • the idea is to capture that the z6 tile with Paris has much more info than the z6 tile with, say, the Shetland Islands
• assign some weight to an OSM object, e.g. 1 OSM object = 10 bytes
• given a PBF and an amount of RAM, binpack the set of stores so that the fewest stores are used. For machines with a lot of RAM, you'll end up in today's situation: a single z0 store. For machines with less RAM, you may get 1 store for Europe, 1 for North America, and 1 for South America+Oceania.
• when reading the source PBF, construct the stores serially such that each store is a contiguous block of memory/disk

I'm hand-waving parts of this, but I think the overall approach should work well and fit into the existing mmap stuff, which is attractive. If it ends up not performing well, I think it'd be straight-forward to rejig it to serialize the geometry to disk.

The current blocker to doing that is that include_ids support is broken. Previously we indexed objects by OSM ID | object type bitfield,

Ah, I'll maybe take a stab at a PR that rejigs how TileIndex works and restores support for include_ids.

I think the lazy geometry approach would also get include_ids support for free, as the ID in the OutputObject would then be pointing at an OSM object, not a geometry.

[systemed]

That all sounds worth experimenting with, and yes, very much identifying the same problems just with a slightly different way of solving them.

Ah, I'll maybe take a stab at a PR that rejigs how TileIndex works and restores support for include_ids.

That would be excellent - we can then hopefully merge refactor_geometries and iterate on master instead.

shp files will have to be treated specially; I haven't thought too much about this yet

The Lua methods like FindIntersecting etc. will need some thought here. They're really useful for region-specific processing so I'd like to keep them, but they do require keeping those particular geometries in memory. Generally there won't be too many of them - rough country polygons etc. - so the impact on memory isn't huge.

(In the longer term I'd like to add GeoJSON support as well as shapefiles, and maybe refactor the shapefile Lua interface to be closer to that for OSM data, but that's not a priority.)

[cldellow]

shp files will have to be treated specially; I haven't thought too much about this yet

As I was doing the OutputObjectRef removal, I realized that refactor_geometries already disentangles how geometries work. (Hence the name, one assumes. :)

That's the special treatment I was thinking about -- that OsmMemTiles ought to do something differently than ShpMemTiles.

But I think in fact ShpMemTiles can be left alone. Instead, I can make OsmMemTiles override its buildWayGeometry to generate geometries from the OSM stores, and adjust OsmLuaProcessing to use the OSM IDs as the geometry IDs.

Well, I'm handwaving a bit. There'll be some details, I'm sure.

The Lua methods like FindIntersecting etc. will need some thought here. They're really useful for region-specific processing so I'd like to keep them, but they do require keeping those particular geometries in memory. Generally there won't be too many of them - rough country polygons etc. - so the impact on memory isn't huge.

👍 In the near term, I imagine this will all continue to work, as I won't be touching ShpMemTiles.