Skip to content

Building bigger than memory

The builder reads an extract, turns it into a graph, and lays that graph out as tiles. All three live in memory at once, which is why a 105 MB extract wanted 12 GB and a planet would want terabytes. This page is what we measured, what it costs, and the shape the builder is moving towards.


What a build holds

Measured on Senegal + Gambia, a 105 MB extract that becomes 371 tiles, 906k nodes and 2.4M directed edges. The allocator is counted, so these are bytes handed out and not yet given back rather than resident pages:

flowchart LR
    R["read the extract<br/>0.11 GB"] --> G["build the graph<br/>+0.29 GB"]
    G --> T["lay out the tiles<br/>+0.8 GB at the peak"]

Those are today's numbers. When the counting started they were 0.82, 0.5 and 1.2, for a peak of 12.1 GB resident against 1.8 GB now.

The first number is ways and their nodes. The second is the edges the ways are cut into. The third is everything a tile needs at once: edges grouped by junction, the adjacency, the orderings every mask is written against, the shortcut chains, and the tile bytes themselves, for every tile, before the first one is written.

Three quarters of the first number went away by sharing a way's tags with the edges cut from it and asking the tag rules once per distinct tag set. What is left is structural: the builder holds the whole world because it was written to answer questions about the whole world.

Why it cannot simply be chunked

Tiles are not independent. An edge's endnode is a GraphId into another tile, opp_index is a position in that other tile's edge list, a transition joins a junction to itself on another level, and a bin lists edges from tiles that merely cross it. Two independent builds disagree on all of those numbers wherever they meet.

flowchart LR
    A["tile A<br/>edge 41 → endnode B:17"] -.->|"built separately"| B["tile B<br/>node 17 is a different junction"]

So chunking needs the pieces to agree on numbering before anything is written, which is the same problem as building the lot at once.

How Valhalla fits

Mjolnir keeps everything in sequence<T>: memory-mapped files of fixed-size records, sorted with external sorts, walked in order. Nothing but the current window is resident, which is how a planet build fits on a machine you can rent.

It pays for that twice. Every stage sorts the world, and the planet tile set is written by the graph builder, rewritten by the enhancer, rewritten again when the hierarchy is laid down, and once more when shortcuts go in. Cross-tile reads in the enhancer take a lock on the shared reader.

Where we are going

Same spilling, different shuffle. A tile is a function of a coordinate, so records can be bucketed straight into per-tile files on the pass that produces them: sequential writes, no global sort.

flowchart LR
    W["ways, streamed"] --> C["cut into edges"]
    C --> S["append to the shard of<br/>each end's tile"]
    S --> P["one tile at a time:<br/>read shard, write tile"]

An edge is written to the shard of both of its ends, so a tile's shard holds every edge that touches it and the graph questions asked at a junction can be answered without looking anywhere else.

The questions that reach further than one junction are answered in a second pass over the written tiles, through the reader we already have, the way the enhancer does it: whether a road leads anywhere, what class a slip road deserves, how long a chain a shortcut can cover.

Milestones

What Frees
1 Coordinates in a sorted file on disk done: the extract holds 0.11 GB rather than 0.82
2 Edges bucketed into per-tile shards as they are cut the edges, and the peak they share with the extract
3 Tiles written one at a time from their shard the per-tile machinery
4 Graph walks as a second pass over written tiles what is left of the cross-tile reach
5 Threads, one per tile done: tiles are laid down in parallel

Milestone 5 came early because it turned out to be nearly free: a tile reads what every tile shares and writes only its own file, so handing each one its bins upfront and returning its counts was enough. It is worth remembering what that did and did not buy. The tile loop was about half the wall clock, so going wide took the build from 110 seconds to 90, not to 20. The rest is the serial work before it.

Asking a question once was worth more than any of it. Three passes wanted to know whether a road carries signs, and each one walked the junction to find out; the same went for whether a road is a stub inside a junction. Worst of all was the country lookup, which walks an outline of up to eighteen thousand points: the speed table asked it once per directed edge, which is three times per junction rather than once. Answering each of those once, into a table, took the build from 131 seconds to 69.

What France costs

Senegambia is small enough that everything fits and nothing shows. France is the first extract big enough to argue back: 11.7 million ways, 98 million nodes resolved, 20.2 million junctions, 46.1 million directed edges, 2062 tiles. Two builds of it, on a machine with 128 GB:

Phase Without boundaries With boundaries and speeds
read the extract 2m52s, 21.99 GB at the peak the same
build the graph 2m52s, 25.22 GB 3m56s
read the boundaries not done 4m09s
number the junctions 4m40s 8m48s
lay the tiles 8m58s, 40.44 GB 40 min all told, 39.50 GB

The boundaries cost about four minutes to read and about four more to ask, which is twenty million point in polygon questions against outlines running to seventy thousand points. That is what the latitude bands bought; before them the same questions were an afternoon.

Three things only France could show. The first was a routing bug: a square that roads merely cross still needs a tile, because the bins are how a search turns a point into the edges near it, and 753 of France's tiles are of that kind. Without them a driver standing in one is told there is no road anywhere. The second was that the shortcut chains were the last serial block of any size, at 8m15s. The third was a lesson about the tag memo, which is worth stating plainly because the measurement went the other way from the theory: capping it made the read phase hold five gigabytes more, not less. The memo is not only a cache of what the rules answered, it is what lets every way with the same tags share one answer, and a table that is emptied hands out copies instead.

Measuring it

The build binary counts its own allocations:

cargo run --release -p calculon-build --bin calculon-build-tiles -- \
  --admins <extract.osm.pbf> <out-dir>
# read the extract: holding 0.11 GB, most held so far 0.33 GB
# built the graph:  holding 0.40 GB, most held so far 0.62 GB
# wrote the tiles:  holding 0.47 GB, most held so far 1.46 GB

The gap between what a phase holds and what it held at its peak is where the next saving is: the peak is one tile's bytes times however many are being laid at once, and the held part is the graph and its indexes.

/usr/bin/time -l on the same command gives peak resident, which is the number that decides whether the machine is big enough. Run nothing else while measuring: two builds of this extract came out three times slower than they were because a test suite was running beside them.