Skip to content

Routing bake: bake a continent in bounded memory #3228

Closed
4 of 4 issues completed
Closed

Description

@timohueser

Status: done

Part of workstream 4 of #3000. The hierarchical search of #3227 needs continental routing packages: a 2,000 km route must cross a continent inside one graph. Bakes run on the owner's PC: 16 GB of RAM, a 6-core Ryzen from about 2019.

TL;DR

Goal: A continent bakes on a PC with 16 GB of RAM. The routing bake's own memory stays at or below 4 GiB in every stage except the route catalog, the rest of the RAM caches files, and every package keeps the same bytes.
Problem: The bake keeps all OSM data and the whole road graph in RAM, several times over. Switzerland peaks at 9.0 GB for 1.2 GB of road data. Germany needs about 50–60 GB, and Europe about 250–400 GB (estimated).
Decision: The bake keeps each large table once, as a flat array of fixed-width values (a column), in four sub-issues. #3238: the import reads all its files in two passes, keeps one copy of each fact, keeps tags only where they exist, and keeps only the relations that can be used. #3239: the roads become columns. #3240: the preparation keeps cost totals instead of cost curves, and the terrain decodes a bounded number of squares when a height needs them. #3241: the columns move into memory-mapped files, and the large sorts run on disk. Germany and every continent then bake within the budget. A Europe bake of the routing layer takes about 9–12 h on the owner's PC (estimated, accepted by the owner).
Rejected: Tighter tables in RAM only: Europe still needs 45–70 GB. A bake in pieces that a join stage links: every stage needs rules for the piece borders, and routes must stay exact across them. More RAM or a rented machine (owner decision). Another allocator: mimalloc peaks at 8.85 GB against 9.02 GB on Switzerland.
Systems: routing, source-preparation
Contracts: none
Size: L (about 2,600 changed lines over four sub-issues)

Words

  • Manifest ID: the SHA-256 of the package's manifest.json. Two bakes with the same manifest ID wrote the same package bytes.
  • Profile: one of the 17 cost models of the planner, such as touring or mtb/technical. Each profile has its own road costs and turn costs.
  • Cost basis: the factors from which the route engine computes the cost of one road: a distance factor, a bend coefficient and a ferry flag. The package stores each distinct basis once, in a dictionary.
  • Cost curve: the cost of a road along its length, with its climb and bend penalties. The bake needs it only for the total cost of the road.
  • Closures: possible access restrictions of a road, such as private or a seasonal condition. The route reports them.
  • Overlay index (overlays.sqlite) and route catalog (route-catalog.json): two files that the bake writes beside the package from the OSM source data. The catalog routes each signed route on the package to check it.
  • Landmarks: precomputed distance columns that guide today's search. Routing: hierarchical search and disk storage #3227 removes them.
  • Preserved relations: the OSM relations that the import keeps for the catalog, the overlay index and the costs.
  • Crossing modes: the travel modes (bicycle, foot, pushing) that can pass a node, such as a barrier.
  • Disk layout of Routing: hierarchical search and disk storage #3227: a router that reads its package through memory maps, so that it does not decode the whole graph into RAM.

Facts

  • The import keeps everything it reads. import keeps every relation of the file in relations (osm.rs#L247). Each highway's node list and tags go into preserved.ways and highways (#L262, #L266), and again into RawWay (#L315). Every node that a highway references goes into nodes with its tags (#L282), and a second map, needed, counts the references (#L276).
  • The import copies the source data again. build_graph copies every node and every routable way, with their tags, into source::Data (osm.rs#L390). Its tags are a BTreeMap<String, String> (source.rs#L8), and the cost, closure, overlay and catalog code read them by key.
  • Each direction of a road has its own heap shape. emit_run clones the shape for each direction (osm.rs#L530). Each model::Road takes 64 B, plus 12 B per shape point. The same type is the stored geometry of the package (geometry.rs#L89), and the cost code takes a &Road (Profile::permits, Profile::mode, model.rs#L204).
  • The preparation builds large temporary tables. The spatial index is a BTreeMap<(i32, i32), BTreeSet<u32>> (lib.rs#L119). The closures are one Vec per road (lib.rs#L156). For each profile, Costing keeps the full cost curve of every road (cost.rs#L40), and the road and turn costs are Vec<u64> (lib.rs#L193). connectivity::States and the landmarks build their own copies of the topology (lib.rs#L181, #L183).
  • The terrain decodes every square of the region at once. The routing step calls terrain.load(i32::MIN..=i32::MAX) (step.rs#L60). Terrain::load decodes the GLO-30 squares of a range of latitudes, at all longitudes (obc-dem planner.rs#L174). A decoded square is a grid of f32 heights, at most 3,601 × 3,601 values or 52 MB (geotiff.rs#L133). For Germany, all squares take about 4 GB; for Europe, one row of latitude alone is about 70 squares. The decoded reference tiles are already bounded, at 256 tiles or 1 GiB (planner.rs#L98). terrain::apply sorts the roads by the fine cell of their first point, row by row (terrain.rs#L8), so each row of cells crosses the whole width of the region.
  • The route catalog decodes the package into RAM. catalog::write opens Selection::whole and prepares five profiles (catalog/mod.rs#L257), which decodes the whole graph and its cost columns (Union::open, data.rs#L363). Its routers share 6 GiB (catalog/mod.rs#L27). For a continent, the catalog needs the disk layout of Routing: hierarchical search and disk storage #3227.
  • The overlay index reads the coordinates of every node of every kept way (overlays.rs#L155). The catalog reads the node lists and the coordinates of the ways that belong to routes.
  • obc data already gives each step a temporary folder beside its output, on the disk of the store, because /tmp can be a tmpfs (process.rs#L69).
  • The warning counts are part of the package. graph.warnings, with counts such as "duplicate input ways", goes into the manifest (lib.rs#L111). Today the first copy of a duplicate way, node or relation wins.
  • The bake is deterministic. Two Switzerland bakes gave the same manifest ID (measured), so "same bytes" is a check that works today.

Measured on Switzerland (7.72M directed roads, one profile, no terrain, in a cloud container with 4 cores and 15 GB of RAM):

Step RAM
Peak, at the end of osm::import 9.0 GB
Live after the import, freed memory released 5.1 GB
Of that: source data for the catalog and the overlays 1.6 GB
Of that: road structs and shapes 1.2 GB
Peak while one profile is prepared 7.3 GB

Counted in the extracts:

Extract Size Highway ways Node references Unique nodes Tag pairs
Switzerland 0.68 GB 2.16M 20.8M 17.9M 7.6M
Germany 5.9 GB 16.6M 111M 87.3M 73.0M
North America 21.4 GB
Europe (openstreetmap.fr) 41.2 GB

Estimated from these numbers: Germany needs about 50–60 GB today, and Europe about 250–400 GB. A bake that only packs its tables tighter in RAM still needs about 45–70 GB for Europe.

Targets, estimated from the sizes of the compact tables: about 17 B per node (ID, point, crossing modes), 8 B per node reference, the tag bytes plus 16 B per way, 64 B per road plus 12 B per shape point, and about 140 B per road for the working columns of the preparation (topology, reverse arcs, edges, turn costs, totals, spatial pairs and landmarks).

Stage Switzerland today (measured) Switzerland after #3240 (target) Germany after #3241 (target)
Import peak 9.0 GB about 2–3 GB own memory ≤ 4 GiB
Preparation peak 7.3 GB about 3 GB own memory ≤ 4 GiB
Route catalog not measured not measured about 5–7 GB, until #3227

For Germany, the tables take about 14 GB, so a Germany bake needs #3241. The catalog for Germany decodes the graph and five profiles: about 5–7 GB.

Plan

The sub-issues run in this order. After each one, a Switzerland bake gives the same manifest ID as before, and its pull request records the measured memory.

The work folder is OBC_DATA_WORK when it is set. Else it is the temporary folder that obc data gives the step (TMPDIR), beside its output, on the disk of the store (owner decision). The memory budget is at most 4 GiB, and at most OBC_DATA_MEMORY_BYTES when the run sets it.

Files

Routing bake, planner/router-build/:

Route engine, planner/router/:

Route service, planner/service/:

Terrain, host/obc-dem/ (source-preparation):

New focused tests: a list reads back what the bake pushed, in RAM (#3238) and in a file (#3241); a sort over several runs gives the order of a sort in RAM (#3241); Tags keeps the key order and finds every key (#3238).

Public docs: none change.

Done when

Limits

  • The bake output stays the same, byte for byte: the same input gives the same manifest ID.
  • The memory that the bake allocates for itself stays under a fixed budget, for every region up to a continent. The rest of the RAM caches files. The design counts on 16 GB of RAM; the owner may add 16 GB more.
  • The route catalog, the overlay index and the possible closures get the same source data as today. After Routing bake 4/4: work tables in files, and sorts on disk #3241 that data lives in files, not in RAM.
  • Only the route catalog can go over the budget, until it reads the package through the disk layout of Routing: hierarchical search and disk storage #3227.
  • The bake stays one process step of obc data, with the same inputs and outputs.

Out of scope


Generated by Claude Code

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions