Repository navigation
Description
Status: approved
Workstream 4 of #3000.
TL;DR
Goal: One routing package covers a continent, and later the world. The bake runs on a PC with at most 32 GB of RAM. The route service runs on a server with at most 64 GB of RAM and answers a leg of 2,000 km in a few seconds. The phone routes offline on a downloaded area with the same engine.
Problem: Three things stop this today.
- The search has no hierarchy. Its work grows with the square of the distance, and its landmarks stop to help when the package grows.
- The route engine decodes the whole road graph and the cost columns into RAM. The package lists each page of 4,096 values with a hash in one JSON manifest, which has a limit of 128 MiB. So a package above about 47 to 63 million directed roads does not open, and Europe has about 290 to 415 million (an estimate from the counts of Switzerland and Germany; Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 measures it).
- The bake keeps its own memory low since Routing bake: bake a continent in bounded memory #3228, but it reads its work files at random through memory maps, on one thread, and it cannot continue after a crash. Germany passed because its 17.8 GB of work files fit the RAM of the test machine. Europe has about 125 to 150 GB of work files.
Decision: The bake divides the road graph into nested cells (the partition of the overlay search). A cell becomes the unit of everything: the road numbers, the files on disk, the published objects, the area that a phone downloads, and the cost tables. - Search: a multi-level overlay, as the prototype below shows. In the cells that hold the start or the end, the search uses the roads. In every other cell it crosses the cell in one step with a cost table that the bake calculated. The landmarks go.
- Package format 10: the roads are numbered in cell order. The package is published as one compressed object for each cell and part. The installer decompresses each object into a file of its own and checks it. The engine reads the installed files as byte ranges (memory maps on the server and on the phone). The manifest with a hash for each page,
blocks.json, the packs and the page caches go. - Bake: each stage reads and writes its tables in order ("one order, then stream"). The bake joins the nodes to the ways with a sort, reads the tags only while it scans the ways in their own order, and puts the roads into cell order once. It calculates all profiles in one parallel pass. Four cached layers replace the single step, so a crash or a new cost model repeats only a part.
- Serving: the follower keeps an installed release on disk across its own restarts. It runs the services of two releases, not three. Whether the files of a third release stay on disk during an update depends on the disk: without them there is no rollback while an update installs. Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306 decides it: the files of the rollback stay while a disk check before each install passes. The systemd unit lets the page cache use the RAM of the server.
Rejected: See Directions. New in this design: a manifest that lists pages (the cause of the limit), one file for each column (too many reads from a cold disk), cost tables computed at install, and a phone area that holds parts of cells.
Systems: routing, obc-data, data-engine, source-preparation, planner-map-baking, route-planning, data-registry, companion-ios
Contracts:specs/route-package.md(format 10),specs/planner-offline.md,specs/planner-release.md,specs/obc-data.md(the routing layers),specs/route-api.md(the status of thelimiterror)
Size: L (4 systems, a new stored format, more than 1,500 changed lines)
Words
- Directed road: one direction of a piece of a way between two junctions. It is the node of the search graph. A turn from one directed road to the next is an arc of that graph.
- Seed: a directed road where a search starts or ends, with the cost of the part of the road that the route uses. A request point gives up to 8 candidate roads near it, and each gives seeds.
- Leg: the route between two request points. The leg program of the router chooses, for all legs together, which candidate road each request point uses.
- Cell, level: in this issue a cell is a cell of the partition, not a map tile. The offline downloads of today use tiles of zoom 9 (
9-X-Y), which this issue calls zoom-9 tiles. The partition puts each junction into one cell of level 1 (the lowest, about 250 to 500 junctions). A cell of level 2 is a group of cells of level 1, and so on. A border road of a level has its two junctions in different cells of that level. - Cost table: for one cell and one profile, the cost from each border road that enters the cell to each border road that leaves it.
- Download cell: a cell of one middle level, 160,000 to 650,000 roads at the default level. It is the unit that the bake publishes and that a phone downloads. The level is a number that the bake records in the package.
- Part: one kind of data of a cell, published as one object: the topology, the geometry, or the data of one profile group (costs, turn costs and cost tables).
- Profile group: profiles whose turn costs are equal byte for byte. They share one stored turn table, as today.
- Release, follower: a release is one published set of data with its ID. The follower is the program on the server that downloads a release, installs it and runs its route, search and download services (
obc data serve). - Closures: possible access restrictions of a road, which the route reports.
- Inertial flow: a way to cut a road network in two: sort the junctions along a direction, take the first and the last part as the two sides, and find the smallest set of roads that separates them.
Facts
The review of 2026-11-10 is in three comments on this issue (route engine, bake, stored format and serving). Each fact below has its file and line there. Figures for Europe (about 300 million directed roads) and the world (about 1 billion) are estimates from the code and from measured smaller packages.
Search and engine:
develophas a bidirectional search with landmark bounds of 16 bits (search.rs, landmarks.rs). A node of the search is one directed road, and an arc is one legal turn. So each arc and each turn restriction belongs to one junction, and a partition of the junctions puts each of them into exactly one cell.- In RAM the graph takes about 40 bytes for each road, and each profile 9 to 15 bytes: about 16 GB for Europe with one profile, for each release that the follower runs.
- The prototype measured cost tables of 2.6 to 3.3 bytes for each road and profile, and about 1,000 times fewer settled labels on long routes. It tested one start state and one end state for each route, with no seed costs, no cost ceiling and no tie-break between candidates. So the request features of Limits are not proven on the overlay yet.
- The figures of the prototype section and of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 are for the 17 profiles of that time. With 10 profiles the published package is about 100 bytes for each road (129 today with 17 profiles, less 37 for the landmark columns, less about 10 for the costs of 7 profiles, plus about 14 for the tables of 10 profiles): a download gets smaller. The installed files are not compressed, apart from the geometry. An estimate for 10 profiles is 150 to 175 bytes for each road: about 15 for the topology, 30 for the road costs, 15 to 30 for the turn costs, 33 for the tables, 55 for the geometry and about 10 for the rest. That is 45 to 73 GB for Europe and 150 to 175 GB for the world, for each installed release. Route package format 10: the contract, the writer and the installer #3301 measures it.
- After the overlay search, a long route costs most in the unpacking and in the geometry. A leg of 2,000 km crosses about 2,900 cells of the lowest level. Today's geometry pages hold 128 roads and are decoded whole, with a hash check at each read.
- Each inner leg of a request runs one search for each candidate road of its end point, and each search builds its full path (router.rs#L290). Only one path is used.
Stored format and serving:
- Measured on Central Switzerland (1.2 million roads): the package takes 129 bytes for each road. The geometry is 54, the landmark columns 37, the road costs 20.
- A road ID is the rank in a spatial order of the whole package. One new road moves each later ID, so two releases share almost no page.
- A page of 4,096 values holds roads of several download cells. A phone downloads 1.03 to 3.3 times the bytes of its cell, in 11 to 25 packs.
- The follower deletes its installed files at each start and when one service of a release stops, and then installs again (services.rs).
- The unit of the follower has
MemoryMax=9216M(obc-data-serve.service). The kernel counts the pages of a memory map for the unit, so the page cache of the route service cannot pass 9 GB.
Bake:
- The import finds each node of each way with a binary search in a table sorted by OSM ID, three times (osm.rs). For each road and each profile, the cost code reads the tags and the country of the way again (cost.rs#L78). The terrain step and the spatial order copy the shape list by index. These are random reads in files of 20 to 60 GB.
- About 28 bytes for each road stay in the bake's own memory (closure IDs, search stacks, the manifest, the writer index, the snap directory): about 9 GB for Europe.
- The bake runs on one thread, apart from the route catalog. The profiles run one after the other; with the 17 profiles of that time they took 77 % of the Germany bake.
- The routing layer is one step with scratch files, so a crash loses all work.
- The partition of the prototype sorts by floating-point keys with an unstable sort, so its result can differ between machines.
Plan
Each line is one sub-issue with its own design, and one pull request. Each design had an adversarial review. Where a sub-issue says something else than this issue, the sub-issue is right: it was written later, with the code open.
#3295 to #3299, #3306 and #3308 merge into develop: they do not change the package format. The other sub-issues merge into one integration branch, routing-overlay, which starts after #3299. On that branch the old engine and the writer of format 9 stay beside the new code until #3311, because the proof compares them. Production keeps format 9 and the old engine until the branch merges, so it never serves an engine without landmarks and without tables.
Bake:
- Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways
- Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket (depends on Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295)
- Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory (depends on Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296)
- Terrain: the seam of the reference terrain in bounded memory #3298 Terrain: the seam of the reference terrain in bounded memory
- Routing bake: four cached layers: source, roads, costs, package #3299 Routing bake: four cached layers: source, roads, costs, package (depends on Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297)
- Routing bake: the partition into nested cells, and the roads in cell order #3300 Routing bake: the partition into nested cells, and the roads in cell order (depends on Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295, Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296, Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297, Routing bake: four cached layers: source, roads, costs, package #3299). The partition is the one stated exception to the memory limit of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297: it holds about 48 bytes for each junction, about 6 to 8 GB for Europe and 19 GB for the world
- Routing bake: the time of the partition grows about as n log n #3381 Routing bake: the time of the partition grows about as n log n (depends on Routing bake: the partition into nested cells, and the roads in cell order #3300)
Format and engine:
- Route package format 10: the contract, the writer and the installer #3301 Route package format 10: the contract, the writer and the installer (depends on Routing bake: the partition into nested cells, and the roads in cell order #3300)
- Route engine: the data layer on format 10 and the host interface #3302 Route engine: the data layer on format 10 and the host interface (depends on Route package format 10: the contract, the writer and the installer #3301)
- Route engine: the road search on format 10, and the test of the old engine against the new one #3303 Route engine: the road search on format 10, and the test of the old engine against the new one (depends on Route engine: the data layer on format 10 and the host interface #3302)
- Routing bake: the cost tables of each profile for each cell #3304 Routing bake: the cost tables of each profile for each cell (depends on Routing bake: four cached layers: source, roads, costs, package #3299, Routing bake: the partition into nested cells, and the roads in cell order #3300, Route package format 10: the contract, the writer and the installer #3301)
- Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only (depends on Route engine: the road search on format 10, and the test of the old engine against the new one #3303, Routing bake: the cost tables of each profile for each cell #3304)
Serving and phone:
- Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306 Follower: installs that stay on disk, one fetch at a time, a failure state for each service
- Follower: install format 10, and limits for memory maps #3307 Follower: install format 10, and limits for memory maps (depends on Route package format 10: the contract, the writer and the installer #3301, Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306)
- Route service: request classes, the limit error as status 422, the probe radius #3308 Route service: request classes, the
limiterror as status 422, the probe radius - Phone: an offline area of whole cells, installed with the same installer #3309 Phone: an offline area of whole cells, installed with the same installer (depends on Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305)
Proof and merge:
- Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one (depends on Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305, Routing bake: the time of the partition grows about as n log n #3381)
- Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 Format 10 becomes the only format: delete the old engine and format 9, merge
routing-overlayintodevelop(depends on Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306, Follower: install format 10, and limits for memory maps #3307, Phone: an offline area of whole cells, installed with the same installer #3309, Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310)
What each step keeps true:
- Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 to Routing bake: four cached layers: source, roads, costs, package #3299 do not change the package: a Switzerland bake gives the same manifest ID before and after each of them. No stored byte depends on the junction numbers, so Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 can number the junctions by OSM node ID. Each pull request records the memory and the time of the bake.
- In Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 the order key is the spatial key of today. In Routing bake: the partition into nested cells, and the roads in cell order #3300 the key becomes the cell: the partition runs on the junction graph before the roads are ordered. The buckets and the emit do not change, so the roads are still ordered once.
- Routing bake: the partition into nested cells, and the roads in cell order #3300 changes the road numbers and so the package bytes once. Route package format 10: the contract, the writer and the installer #3301 adds format 10 beside format 9.
- Route engine: the data layer on format 10 and the host interface #3302 and Route engine: the road search on format 10, and the test of the old engine against the new one #3303 give a complete engine on the new format without cost tables. The final search uses the roads in each cell that is open (see Directions) and a table in each other cell. Without tables each cell is open: the code path is the road search of the final engine. Its routes are exact and slow on long distances. Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 then adds the tables and the unpacking. So the new engine needs no code that a later step deletes; only Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 deletes the old engine.
- From Route engine: the road search on format 10, and the test of the old engine against the new one #3303 on, a program routes the same requests through the old engine on a package of format 9 and through the new engine on a package of format 10 of the same input, with several candidates for each point, via points, pins, turnarounds, a cost ceiling and all profiles. The route costs and the chosen candidates must be equal. When a path differs at equal cost, the old engine prices the new route again.
The four layers of #3299:
| Layer | Holds | Made again when |
|---|---|---|
| source | The ways with their tags and the position of each of their nodes, the tagged nodes, the relations. Also what the tags give with no profile: the country, the closures and the access of each way, and the signals at the nodes | The OSM cut or the bounds change |
| roads | The junction graph, the partition, the roads in their final order, their heights | The source or the terrain changes. No profile is in its key |
| costs | For each profile: the cost basis of each way and direction, the road costs, the turn costs, the snap bits, and from #3304 the cost tables. Each road reads the basis of its way through a column that names the row of its way | The roads, the profile list or the cost model change |
| package | The published objects, the database of route networks that the map shows (overlays.sqlite), the route catalog |
A layer before it changes |
Decisions that the sub-issues made, where this issue left them open or said something else:
- One installed file for each object (Route package format 10: the contract, the writer and the installer #3301). The first text of this issue said that an install appends to large files. A phone adds and removes areas, which would leave holes. Europe has about 9,000 files and the world about 35,000 at the default download level; the server raises its limit of memory maps (Follower: install format 10, and limits for memory maps #3307).
- No snap lists. Snapping reads the boxes of the level-1 cells and gives the same candidates as today (Route package format 10: the contract, the writer and the installer #3301, Route engine: the data layer on format 10 and the host interface #3302). A road longer than 10 km is listed with its own box, so that it does not stretch the box of its cell.
- The identity of a package is the hash of the cell directory. An install is complete when the installer has checked each object and written its marker last; a reader opens only a marked install (Route package format 10: the contract, the writer and the installer #3301).
- A cost table is also stored by column when it is larger than 16 KiB (Routing bake: the cost tables of each profile for each cell #3304), not by level: the proof changes the level sizes.
- The download level is a setting. The proof chooses the lowest level whose estimated world file count is at most 250,000, and the owner sees the measured table of phone download sizes before the value is written (Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310).
- Cell numbers have at most 32 bits and the partition at most 8 levels (Routing bake: the partition into nested cells, and the roads in cell order #3300). The bake checks it right after the partition.
- The search labels are records of 24 bytes in a hash table by road ID, so the memory of a search does not grow with the package (Route engine: the road search on format 10, and the test of the old engine against the new one #3303).
- The interface to the host gives the bytes of one part of one cell and takes a list of parts that the engine will read (Route engine: the data layer on format 10 and the host interface #3302). The server and the phone map each file read-only at its first use.
- The capped Germany bake gates each stage that reads work files, and runs once on the chosen level layout (Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310).
- Not in format 10, possible later without a change to the rest: heights rounded to 1/8 m, and one stored shape for the two directions of a road. Each changes only the geometry part.
- The follower keeps the files of the rollback while a disk check before each install passes; else it deletes the rollback first and says so (Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306).
Measurements that belong to a step: the road count of the Europe extract (#3295 prints the counts right after the import; the first Europe bake shows them), the Germany bake with a capped page cache (#3296, then the gate of #3310), the border roads of each level and the level sizes (#3300 and #3310), and fio on the candidate server with reads of 4, 16 and 64 KiB at queue depth 1 and 32 and one sequential write (the owner, before the server is ordered; a record on this issue, not a gate; #3307 says what each result changes).
Files
The sub-issues list their files. By area:
planner/router-build/src/: the import, the columns, the order, the profiles, the partition, the cost tables, the package writer (Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 to Route package format 10: the contract, the writer and the installer #3301, Routing bake: the cost tables of each profile for each cell #3304).planner/router/src/:package.rs,directory.rs,blocks.rs,data.rs,table.rs,storage.rs,geometry.rs(the data layer, Route package format 10: the contract, the writer and the installer #3301 and Route engine: the data layer on format 10 and the host interface #3302);search.rs,queue.rs,router.rs,landmarks.rs(Route engine: the road search on format 10, and the test of the old engine against the new one #3303 and Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305).host/obc-data-steps/src/planner.rsandhost/obc-data/src/serve/: the layers and the follower (Routing bake: four cached layers: source, roads, costs, package #3299, Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306, Follower: install format 10, and limits for memory maps #3307).tools/vps/obc-data-serve.service(Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306).tools/planner_grid*.py,tools/planner_offline.py,tools/planner_downloads.py,tools/planner_verify.py: the routing parts go with the packs (Route package format 10: the contract, the writer and the installer #3301, Phone: an offline area of whole cells, installed with the same installer #3309).planner/service/src/(Route service: request classes, the limit error as status 422, the probe radius #3308).companion-ios/(Phone: an offline area of whole cells, installed with the same installer #3309).specs/route-package.md,specs/planner-offline.md,specs/planner-release.md,specs/obc-data.md,specs/route-api.md.
Done when
- Each sub-issue meets its own "Done when".
- Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310: a Germany bake with terrain and all profiles finishes on a machine with 16 GB of RAM. In a second bake with the page cache held at a quarter of the size of the work files, each stage that reads work files takes at most twice as long: that is the condition of Europe, whose work files are several times the RAM. The new engine gives the route cost of the old engine on each test request; the old engine gets a memory budget that holds all profiles of the test, so that it does not reload them. A leg across Germany answers in less than 1 s with warm files, and the pull request records the time with cold files. The route service holds less than 1 GB of its own memory for each worker.
- The Europe bake and the server test are workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000.
Limits
- Exact costs. For every request, the route cost is the same as the cost from today's search. When two paths have the same cost, the router can return the other path.
- All request features stay: several road candidates per point, direction continuity at via points, turnarounds, pinned start and end positions, a route on one road, the tie-break between candidates, cancellation, and the limits on queries, geometry and queues (route API).
- 10 profiles since Routing: 10 profiles, two for each activity #3275, two for each activity. Each profile has its own road costs and turn costs, and gets the hierarchy. Turn restrictions are per mode. A profile can exclude roads.
- The phone creates long routes offline (owner decision).
- One engine for the route service, the phone library (iOS) and WebAssembly. WebAssembly has no memory map, and a phone can refuse a map of many GB. So the engine asks its host for a byte range of a part of a cell, and a memory map is one way to give it.
- The bake machine has at most 32 GB of RAM (owner decision of 2026-11-10; the PC of today has 16 GB and 6 cores). The same input gives the same bytes.
- The server has 32 GB, at most 64 GB of RAM, and about 1 TB of SSD. Nobody has measured the disk of the candidate yet.
- No compatibility. The routing package format can change. Format 9 is the package of Routing: 10 profiles, two for each activity #3275; this design is format 10.
Out of scope
- A new method for alternatives (workstream 5 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000). The overlay makes each of their searches cheap.
- Search (workstream 6). Follower work that the disk layout does not need (workstream 7).
- Deltas between two releases. Format 10 only makes them possible later: the road IDs inside a published cell are relative to the cell, so a cell that did not change can keep its bytes when a later bake keeps the partition.
- The cost weights of the profiles.
- A patent check (owner decision).
Directions
- Chosen: a multi-level overlay over today's road graph, with the cell as the unit of the package. This is the method of "Customizable Route Planning in Road Networks" (Delling, Goldberg, Pajor, Werneck), which OSRM calls multi-level Dijkstra.
- Once per bake, for all profiles, the bake divides the junctions into cells by recursive bisection. Each cut is a minimum cut between the two ends of the area, along one of four directions ("inertial flow"). Two junctions with several directed roads between them count that many roads in a cut, because the cost of a cut is its border roads. The sort keys are integers and ties go by junction ID, so the result is the same on each machine. The cells nest in levels.
- A border road of a level is a directed road whose two junctions are in different cells of that level. A road has the cell of its arrival junction.
- For each profile, the bake computes one cost table per cell: the exact cost from each border road that enters the cell to each border road that leaves it, on roads inside the cell. Level 1 uses the roads. Each higher level uses the tables of the level below. The bake publishes the tables (owner decision). A table larger than 16 KiB is stored a second time by column, because the backward search reads columns.
- The search is today's bidirectional search on the same road states and with the same seeds. A cell of any level is open when it holds the arrival junction of a start seed or the departure junction of an end seed. This is the rule that the prototype proved exact. The search never uses the table of an open cell: it goes into its child cells. A child that is not open is crossed in one step, from an entering border road to all leaving border roads, with its table. In an open cell of level 1 the search uses the roads. So the search uses the table of the highest level whose cell is not open.
- The backward search needs the turns that lead into a road. Each turn into a road of a cell starts at a road that arrives at the same junction, so the forward turns of a level-1 cell hold all of them. The search turns the forward list of an open level-1 cell around when it enters the cell (about 640 roads and 1,800 turns). So the package stores no reverse graph. In today's engine the reverse graph is 18 of the 34 bytes that the topology takes in RAM for each road.
- The search keeps today's rules at the end: it goes on at equal cost until the tie-break between candidates is decided, and it obeys the cost ceiling of a request.
- A search returns the cost and the path over cells. The router unpacks only the legs that its leg program chooses. Before it unpacks, it asks the host to read the byte ranges of all cells of the path at once.
- The roads are numbered in cell order, with the border roads of each lowest cell first. So each cell of each level is one range of road IDs.
- The stored index of the overlay: each level-1 cell has one number whose bit fields are its cells at each level, so the level that separates two cells is one comparison of two numbers. Each cell of each level has the sorted lists of its entering and its leaving border roads; the place of a road in such a list is its row or column in the cost table. The road number gives the cell of the arrival junction. The backward search also needs the cell of the departure junction, so each entering border road stores it.
- A published object holds one part of one download cell, or of a cell of a higher level: the topology, the geometry, or the costs, turn costs and tables of one profile group. It installs as one file; inside a part the data lies by lowest cell. A small binary directory lists the cells with their box and the hashes and sizes of their parts. The installer checks each object while it writes; a reader does not hash again.
- Each column of a cell has one value width, chosen for that cell. Geometry is one record for each road, which the reader decodes alone.
- A phone area is a set of whole download cells. A cell of a higher level that the area holds only in part counts as open at that level: the search goes into its child cells and uses the tables of the complete children. It reaches the roads only in the level-1 cells that are open by the seed rule. So the phone routes exactly on the roads that it has, with no computation at install.
- Rejected: customizable contraction hierarchies (CCH). In the literature, their queries are about 5 times faster than the overlay. But with turn costs, the data of each profile is about 20 times larger: on the Europe test graph with turns, 331M shortcut arcs for 40M road states, about 66 B per road state per profile. The overlay measured 2.6–3.3 B. A phone selection that holds a part of the graph cannot use the shortcuts.
- Rejected: one contraction hierarchy per profile (GraphHopper, OSRM CH). Preprocessing one profile with turn costs takes about 23 minutes for the Europe car graph. It repeats for each of the 17 profiles and for each cost change. A partial selection cannot use it.
- Rejected: better landmarks (more landmarks, wider values, one set per continent). Guidance only makes the searched area narrower. EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 projects 0.7–1.0 s for a cold 300 km leg with working landmarks, and the area still grows with the square of the distance.
- Rejected: a road-class hierarchy or a heuristic search (Valhalla, BRouter). The result is not exact, and bicycle profiles prefer small roads.
- Rejected: cost tables computed at install, on the server and on the phone. It saves only about $0.24 per month of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 at the target coverage (16 GB per release). The phone needs about 2–3 minutes for a Switzerland-size area, which is not good for the rider (owner decision). With tables from the bake, the routing download of an area gets smaller, because the tables replace the landmark columns (see Facts).
- Rejected: goal direction on the top levels with a straight-line bound. Profile weights go down to 0.01 and signed routes get a bonus, so no single lower bound per metre holds for every profile. The estimate of the review gives 0.05 to 1 s for the search of a world route without it.
- Rejected: compressed pages with a bounded cache as the format of the reader. It needs a shared cache with locks, pays a decode at each miss, and its cache is memory that the phone counts for the app. Compression stays in the published objects.
- Rejected: a bake in pieces that a join stage links (from Routing bake: bake a continent in bounded memory #3228): each stage needs rules for the piece borders, and routes must stay exact across them.
Open questions
- Level sizes. The prototype used a factor of 8 between levels. Routing bake: the partition into nested cells, and the roads in cell order #3300 and Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 measure the border roads of each level on Germany and choose the sizes and the factor.
- Server disk.
fioon the candidate server (see Plan). If the disk limits the number of reads, not the bytes, the order of the parts on disk matters more. - Profile groups. How many groups the 10 profiles give (before Routing: 10 profiles, two for each activity #3275, 7 turn tables served 17 profiles). Route package format 10: the contract, the writer and the installer #3301 puts two profiles into one group when their turn costs are equal.
- The download cell. Which level a phone downloads. Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 measures the bytes of an area against the bytes of its roads and applies the rule above.
Prototype: does a multi-level overlay give exact routes and large speed-ups on our bicycle road graph, and what does it cost?
Answer: Yes. On 695 random routes in Switzerland and Belgium, for 9 profiles, the overlay gives exactly the cost of today's search. Each unpacked path is a valid road path with that cost. On long routes, the overlay settles about 1,000 times fewer labels and is 100–300 times faster, in an unoptimized prototype. The cost tables of one profile take 2.6–3.3 B per directed road. Today's landmark columns take 4.9 B per road per profile in RAM.
Evidence:
Packages, built from OpenStreetMap extracts with planner-router-build without terrain (no heights, so no climb costs):
| Package | Directed roads | Junctions | Turns | Profiles |
|---|---|---|---|---|
| Switzerland | 7.72M | 3.09M | 21.9M | 17 |
| Belgium (flat and dense) | 5.44M | 2.10M | 15.8M | touring |
| Lucerne area (debugging) | 0.48M | 0.20M | 1.4M | touring |
Partition and cost tables, on 4 cores. The levels give the largest number of junctions in a cell.
| Package, levels | Partition | Border roads per cell, median per level | Tables per profile | Tables, one profile |
|---|---|---|---|---|
| Switzerland, 512 / 4k / 32k / 262k | 52 s | 15, 31, 62, 127 | 20.0 MB (2.6 B/road), 11.0 MB zlib | 4.2–8.0 s (9 profiles) |
| Switzerland, 256 / 2k / 16k / 131k / 1M | 49 s | 12, 25, 50, 99, 118 | 25.1 MB (3.3 B/road) | 3.9 s |
| Belgium, 256 / 2k / 16k / 131k / 1M | 43 s | 12, 25, 53, 120, 145 | 18.1 MB (3.3 B/road) | 3.4 s |
With 5 levels on Switzerland, the tables of one profile take 11.8 s on one core and 6.2–7.2 s on two cores (touring, mtb). That is 1.5 s per million roads per profile on one core.
In levels 1 and 2, 99% of the table values fit 16 bits. At the top level, only 27–67% fit.
Queries, touring, 5 levels, medians by straight-line distance. One thread, all data in RAM. "Today" is the package's own search with its landmarks, as in production. Its label count is rounded up to 1,024, because the prototype counts the calls of the cancel callback.
| Distance | Routes | Overlay labels | Overlay ms | Unpack ms | Today labels | Today ms |
|---|---|---|---|---|---|---|
| Switzerland 0–25 km | 5 | 1,293 | 1.3 | 0.7 | 115k | 33 |
| Switzerland 25–75 km | 17 | 2,340 | 3.7 | 3.3 | 539k | 191 |
| Switzerland 75–150 km | 23 | 3,656 | 7.4 | 6.3 | 1.92M | 791 |
| Switzerland 150–250 km | 26 | 3,876 | 9.2 | 13.7 | 3.10M | 1,291 |
| Switzerland 250–298 km | 4 | 3,652 | 8.0 | 20.1 | 4.28M | 1,930 |
| Belgium 0–25 km | 12 | 1,673 | 1.3 | 0.7 | 30k | 8 |
| Belgium 75–150 km | 20 | 3,249 | 6.0 | 4.4 | 1.37M | 512 |
| Belgium 150–250 km | 3 | 3,359 | 5.3 | 10.6 | 3.66M | 1,559 |
- The other 8 profiles on Switzerland, 4 levels, 150–250 km: 4,970–5,140 overlay labels and 10–14 ms. Today: 1.2–4.1M labels and 585–2,053 ms. Plain bidirectional Dijkstra settles 4.9–6.1M labels on routes of this length.
- On long Swiss routes, level 4 does the most work: 1,500 of 3,900 settled labels, and 178k of the 263k arcs and table values that the search reads.
- Unpacking reads 1.4 level-1 cells and 19 road states per km of straight-line distance. On long routes, it takes as long as the search.
- The partition is deterministic: two runs gave the same cells.
Estimates for 650M directed roads (84 times Switzerland, linear, ±50%):
| Item | Estimate |
|---|---|
| Cost tables, one profile | 2.0–2.3 GB raw (u32), about 1 GB compressed |
| Cost tables, 17 profiles | 33–40 GB raw, or about 22 GB with 16-bit values in levels 1 and 2 |
| Landmark columns removed | 54 GB of RAM for 17 profiles |
| Partition | 1–2 h on 4 cores |
| Cost tables, 17 profiles | 2–3 h on 4 cores |
| Search labels per worker | under 10 MB (today: 1.3–4 GiB for a 2,000 km leg) |
| Unpacking a 2,000 km leg | about 2,900 level-1 cells and 38k road states |
For the design:
- Keep today's road-state graph, seeds, candidate choice and leg program. Replace the search loop in
search.rsand deletelandmarks.rs. - Give each directed road the cell of its arrival junction.
- The forward search takes the level of a road from its arrival junction. The backward search takes it from its departure junction. A cell is open when it holds the arrival junction of a start seed or the departure junction of an end seed. With these rules the search is exact. The prototype checks this on every route.
- Number the roads in partition order, so that each cell is one contiguous range of every column. This replaces the Morton order. The level-1 search and the unpacking read whole level-1 cells.
- Unpacking costs as much as the search on long routes. Make it faster, for example with a smaller first level or a search from both ends.
- Choose the level sizes on a Germany-size bake. The upper middle levels set the query time.
- The prototype keeps labels in a standard hash map. Its times are an upper bound.
Branch: prototype/mld-routing: planner/router/examples/prototype_mld.rs and planner/router-build/examples/prototype_mld_package.rs.
Activity
timohueser commentedon Nov 10, 2026
Review of 2026-11-10: the route engine and the service
One of three review reports on
develop9ec892f (engine, bake, storage). An agent wrote it from the code, the issues and the pull requests. Nothing was built or run, so each scale figure is an estimate unless it names a measurement. The summary and the owner decisions are in #3000.Scope:
planner/router/src,planner/service/src,specs/route-api.md,specs/route-package.mdat9ec892f9a(origin/develop), issues #3000, #3227, #3053, #3255, and the prototypeorigin/prototype/mld-routing:planner/router/examples/prototype_mld.rs. Read only. Nothing was built or run.Number labels: [code] = derived from the types or constants in the source. [#N] = taken from issue #N,
which marks it measured or estimated. [est] = my estimate. Ratios used throughout: 2.84 arcs per directed
road and 0.40 junctions per directed road (21.9M turns, 3.09M junctions, 7.72M roads, Switzerland, [#3227 measured]).
(a) Verdict
Vecs. Only the bake is bounded-memory.(b) How it works today
The graph
search.rs:85). An arc is one legal turn from roaduto roadv. Its weight isroad_cost(v) + turn(u→v)(base.rs:219-227). All-ones in a column means "absent" (base.rs:158-183).(before, after)road pairs at one junction. Via-way restrictions are excluded by the bake (router-build/src/osm.rs:204,:461). The engine sees them only asu64::MAXturn costs.head[first[r]..first[r+1]], ascending (base.rs:119-120).What is in RAM (bytes per directed road)
firstVec<u32>,base.rs:199headVec<u32>,base.rs:200reverse_firstVec<u32>,base.rs:201reverse_tailVec<u32>,base.rs:202reverse_offsetsNumbers, 1 B/arc while the widest row is < 256 arcs,base.rs:203,blocks.rs:263-286Vec<u64>,blocks.rs:200Arc<Vec<u32>>,landmarks.rs:115Numbers, 1–2 B,closures.rs:75,data.rs:492Numbers, one width for the whole column (base.rs:76-88): 4 B as soon as one road costs ≥ 65,535Arc<Numbers>, 1 or 2 B/arc; one copy per group of profiles with identical stored tables (data.rs:116-129,:380-386)Vec<u16>over the junctions (landmarks.rs:148,router-build/src/landmarks.rs:8)Vec<Vec<LabelBlock>>, 24 B per 512 roads per side (search.rs:19-22)search.rs:12-16)search.rs:72-77,data.rs:259-261). This is accounting, not allocation.(i128, u64, u8, u32)(queue.rs:5): 29 bytes of fields, so 32 bytes at alignment 16 [code, derived from the layout rules, not compiled]. The 48 bytes in EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 isOption<Entry>, whichfront,topandpopreturn. Onesize_ofassertion settles it.package.rs:141,:330-336), four index caches of 8 blocks each (table.rs:94), two snap directories (package.rs:262), 32 snap results and the last primary route (router.rs:146-150).Ids, the snap map, theUniongraph, the junction mapping, the closures, and one cache of prepared profiles behind one mutex (data.rs:76-94). Each profile is loaded once under theloadinglock (data.rs:525-533).Selections, blocks, unions
Selectionis the onlyRoutingData.wholecovers a complete package;open/newcover a grid selection fromblocks.json(data.rs:147-175).Idsholds sorted source ranges. A local id is the position in their concatenation.localandsourceare binary searches over the ranges (blocks.rs:78-88).Union::openwalks every selected road, reads its row offirstandheadfrom compressed pages, drops arcs to absent roads, and then builds the reverse graph with a counting sort (blocks.rs:203-292). The stored reverse tables are not read.Union::costsdecodes the full road-cost column and the full turn column of a profile, and then checks every arc (blocks.rs:293-324).Selection::loadadds the landmark columns (data.rs:377-403).Junctions::readremaps the junctions (landmarks.rs:121-141).pages.idx→ copy out of the map → SHA-256 of the bytes → zlib → postcard (directory.rs:82-112,package.rs:276-286,storage.rs:17-24). The SHA-256 runs on every read, not only at install.One query, step by step
503 busy(http.rs:90-92);spawn_blocking; pop a router from aMutex<Vec>(LIFO);respondstarts the 15 s deadline after the wait (lib.rs:35-38).routes→primary: returns the cached last route of this router when the request differs only in the alternatives flags (router.rs:171-179).router.rs:211-258): read the road list of each 0.01° cell in the window, test theallowedbit, decode the geometry page of each road, project the point on every segment, keep candidates within 3 m of the nearest, at most 8 (data.rs:448-476,snap.rs:14-45). Radius 250 m, then 1,000 m.router.rs:259-330): a dynamic program over the candidates of consecutive points. The last leg is one search to all end candidates. Each inner leg runs one search per end candidate (router.rs:290-296).leg_batch(router.rs:444-533): start seeds are the candidate roads with the cost of their rest. End seeds are the predecessor states of each end candidate, with prefix cost plus turn penalty. A same-road hit sets theceiling.search.rs:140-293): reset both label directories; pick 4 of 6 landmarks (landmarks.rs:160-187); alternate sides by smaller queue top; stop when the two tops exceed2 × best; cancel check every 1,024 pops. Path: parent arcs; the tail of a forward arc comes from a binary search overfirst(search.rs:254); the cost is summed again as a witness (search.rs:284-291).line(router.rs:354-442): for each road of the chosen legs, the geometry page, a cut, pace seconds per segment, totals.alternatives.rs:30-128): one route in each of the two variant profiles, then up to four corridor probes, each a 3-point route. 15 searches on a 10 km route [EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 measured].answer.rs): aserde_json::Valuetree, then bytes, then brotli or gzip.(c) Findings, ranked by impact
F1. No hierarchy: work grows with the area, and the landmarks stop helping
search.rs:176-242;landmarks.rs:144-201; oneu16scale per package (landmarks.rs:19-25,router-build/src/landmarks.rs:174). Verified by reading.F2. The whole graph and every used cost column are decoded into RAM, at open and per profile
blocks.rs:203-292,:293-324;data.rs:359-403;landmarks.rs:121-141. Verified by reading.#3000 estimates more for one profile (80–90 GB at 1B). The difference is not in the types; I did not find its source.
loadinglock, and the load is not cancellable, so a request for a cold profile holds a worker past its 15 s deadline.Union,Prepared, the profile cache and the whole budget machinery go (about 300 lines ofdata.rs,blocks.rs; thememory_budget_bytesargument ofplanner_router_open). Size L. Risk: low for the engine, operational for the server (see D7).F3. The profile cache keeps one profile once the package is large
default_budget= costliest profile + 256 MiB (data.rs:41-50);retainkeeps shared data + one router + 16 MiB inside the largest budget (data.rs:326-340); the linking scratch of 4 B/road is in the budget and is free after the first load (data.rs:279-283). Verified by reading.alternatives.rs:39-46).F4. Limits in code that fail before Europe
package.rs:17,:176;data.rs:156;directory.rs:204blocks.json: about 47M roads [#3000]. Whole manifest: 129 digests per 4,096 roads × 67 B = 2.1 B/road, so about 60M roads [code]u32table.rs:10,:22;base.rs:199; label parentssearch.rs:14u32package.rs:52,:85-86u16distance, one scale per package, 6 landmarks in one componentlandmarks.rs:19-25;router-build/src/landmarks.rs:8,:174Limitdata.rs:464-466max_geometry= 250,000, used for three thingsrouter.rs:125,:303-306,:417,:511service/src/lib.rs:26,:35MAX_WORKERS= 12http.rs:31u32; make arc offsets cell-relative oru64. Splitmax_geometryinto three named limits. Size S each.F5. Geometry: 128 roads decoded to use one to three
package.rs:297-340,geometry.rs:113-140,package.rs:225-235(digest strings in a block of 4,096Strings, cache scanned by string comparetable.rs:85), SHA-256 on each readpackage.rs:276-282. Verified by reading.Selection::verifyexists). Size M. Risk: low. Put it in the Routing: hierarchical search and disk storage #3227 format; it is not there today.F6. Inner legs: one full search per end candidate, each with a full path
router.rs:290-296,:302-311. Verified by reading.lineunpacks only the legs that the dynamic program selects. Count witness roads only for the selected legs. Size S–M inside the rewrite. Without this, unpacking (as long as the search, [Routing: hierarchical search and disk storage #3227 measured]) multiplies by K.F7. The search hot loop (matters only if the present search lives on)
search.rs:12-16).cost,originandparentare three calls, each throughVec<Vec<_>>(search.rs:38-46). One relaxation touches 2 lines to read, 3 to write, and 1–3 for the opposite side: 5–8 cache lines [code]. A 16-byte record{cost: u64, parent: u32, origin: u8}is one line.first[tail] + offset, then readsturns[arc]andhead[arc]at random places (base.rs:206-208,:219-227);head[arc]is the node itself. Three random reads where the forward side has one.Potential::getreads the mapping and up to 4 columns per push, ini128(landmarks.rs:191-201,search.rs:125-127).queue.rs:65-66,:44). The key isi128only because of the potential.Labels::resetwalks the whole directory for each search (search.rs:24-37): 28 MB at 300M roads, 94 MB at 1B [code], 4.5 ms per search at 1B [EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 computed]. Blocks over the 1,024-block pool are freed and allocated again each search.firstfor each arc (search.rs:254): 28 probes at 300M.u64key with 16-byte queue entries, and no per-search work that depends on the package size. Verified by reading; the gains are [est] and unmeasured.F8. Service
503 busyafter 1 s and no request classes (http.rs:24,:90-92). One alternatives or shape call holds a worker for up to 15 or 30 s. Two looping clients give 79% errors [EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 measured]. After the overlay, a primary route takes 10–100 ms, so the queue rule is fine for primaries. Change: a second semaphore that keeps alternatives and shape calls from more than about half of the workers. Size S.limitanswers 503 (lib.rs:100,route-api.md:206). A retry cannot succeed. Use 422. Size S, contract change.router.rs:146-148). Routers are popped LIFO, so it hits only at low load. With a cheap primary, delete it. Size S.data.rs:512-533). Gone with memory maps.answerbuilds about 600kValues (about 20 MB) for a 150k-point route before it writes bytes (answer.rs:15-51) [est]. DeriveSerializeon a struct. Size S. Low impact.F9. Alternatives
alternatives.rs:67,:93), for routes from 27 km. The window is then about 100 snap cells, 84 km² [code]. Over 100,000 roads it returnsLimit(data.rs:464), whichroutesswallows (alternatives.rs:17-21). So a dense city centre (over about 1,200 directed roads per km²; the Swiss average is 188 [Routing: hierarchical search and disk storage #3227]) silently gets no corridor alternative. Elsewhere each probe projects every road of the window: about 16,000 roads and 125 geometry pages at the Swiss average [est]. This is the "probe snap, line and checks: 222 ms" row of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000. Verified by reading; the city case is [est], not run.(d) Critique of #3227
D1. The method is right
osm.rs:204). No hole here.D2. Top-level growth: the bytes are no problem, the work must be measured
HashMaplabels [Routing: hierarchical search and disk storage #3227 measured]) that is 0.05–0.2 s, worst case 0.3–1 s. The goal holds in both cases. A factor of ×4 between levels halves the work for about 1 B/road more [est]; measure it on the Germany bake.D3. The stored overlay index is not designed
HashMaps per level, and the cell of a junction with one array per level (prototype_mld.rs:259-273,:485-493). It keepstailandheadjunction per state. None of this is in the design text.entriesandexits; find a position by binary search when a state is settled, not per relaxation. Store the tail cell beside each entry road. Write this into the issue.D4. The backward search reads table columns with a stride
cliques[offset + p*nx + q]for allp(prototype_mld.rs:587-588). For a top cell with 800 borders that is 800 reads 3.2 KB apart: one page per value, and cold it faults in the whole matrix [est].D5. Do not store the reverse graph
vis in the forward row of a road that arrives at the departure junction ofv. So the forward rows of a cell hold all predecessors that the backward search needs there.reverse_first,reverse_tail,reverse_offsets: 18.2 of 33.9 B/road [code].D6. Unpacking and geometry decide the latency of long routes
madvise(WILLNEED)) before the unpack. (3) Keep "one contiguous record per level-1 cell" as a lever if the disk is capped by request count. (4) Geometry as in F5.D7. "The page cache is the only cache" has three conditions
MemoryMax=9216M(tools/vps/obc-data-serve.service:20). Mapped file pages are charged to the unit, so the kernel reclaims them at 9 GB. The limit must change with this design. (The install reviewer owns this; the engine latency depends on it.)Vecin WebAssembly. Say so in the design; it replaces theSourcetrait for hot data.directory.rs:55-57).D8. The phone selection must consist of whole level-1 cells
Ids), only cells of level 2 and up can be incomplete, and the range test is exact. Cost: at most one cell width (1–2 km) of extra roads at the edge.D9. Profiles, tables and cost updates
shorterandless-climbingvariants (model.rs:150-177), used for alternatives. 7 metrics instead of 17 saves about 53 GB at 1B roads and 59% of the table bake [est]. This is an owner decision; Routing: hierarchical search and disk storage #3227 already expects "probably fewer".mtbandmtb/technical,hikingandhiking/alpineaway from mountains). The gain is [est] 5–10% and needs a measurement.u32with an assertion (prototype_mld.rs:433). Weights up to 1,000 are valid (model.rs:190), so a 5,000 km top cell can overflow. Fail the bake with a clear message.route_bonusand weights down to 0.01 (model.rs:190-199) make the bound profile-specific, and D2 shows it is not needed.D10. Request features on the overlay
prototype_mld.rs:483-505,:769-773). Production has up to 8 start seeds with costs, the predecessor states of up to 8 end candidates, a ceiling, and a tie-break on the candidate (search.rs:164-170,:192-207). The open set must be the union over all seeds. The prototype stops at>= best; production continues at equal cost to apply the tie-break. This path is unproven. Test it throughRouter::route, not state to state.D11. Determinism of the partition
f64keys fromcos/sinof the platform library andsort_unstablewith ties (prototype_mld.rs:185-189). Use integer direction vectors on integer coordinates and break ties by junction id.prototype_mld.rs:37-38). Give each junction pair a capacity of its number of directed roads, because the cost of a cut is its border roads.What I would build first
Router::route, with several candidates, via points, pins, turnarounds and all profiles. It is the exactness gate for every later step.partition(deterministic, profile-free) andtables(per profile), and format 9 with the index of D3, whole-cell selections (D8), no reverse graph (D5) and geometry per road (F5).search.rslabels,queue.rsas it is,landmarks.rs,Union,Prepared, the budgets.Anything fundamentally wrong beyond this
MAX_WORKERS) exists only because data is decoded into RAM. It goes with F2. Do not port it.(e) Open measurements
fiorandom reads at 4, 16 and 64 KiB, queue depth 1 and 32, on the candidate server, at several hours. #3227 plans only 64 KiB at depth 1MemoryMaxsize_of::<Entry>()andsize_of::<Option<Entry>>()Generated by Claude Code
timohueser commentedon Nov 10, 2026
Review of 2026-11-10: the routing bake
One of three review reports on
develop9ec892f (engine, bake, storage). An agent wrote it from the code, the issues and the pull requests. Nothing was built or run, so each scale figure is an estimate unless it names a measurement. The summary and the owner decisions are in #3000.Read-only review. Nothing was built or run. Every number has a source tag:
[code] = derived from the types and the code, [measured #N] = recorded in that PR or issue,
[est] = my estimate.
Scale used in this report
Switzerland and the Germany counts are [measured #3228, #3227]. Ratios from Switzerland
[measured #3227]: 2.84 arcs per road, 0.40 junctions per road, 3.57 roads per highway way, 0.37
roads per node ref. Europe = Germany × 7.0 (PBF bytes). Note: the measured ratios give 290M (by
refs) to 415M (by ways) roads for Europe. The owner figure of 250–300M can be low by a third; every
Europe figure below then grows by the same factor.
Owner PC, read now: 16 GB RAM, no swap, 2 GB available (the terrain job holds 13 GB), 6 cores / 12
threads.
/media/timo/OSM1is a SanDisk SATA SSD (ext4), 234 GB free. There is also a 1.8 TB USBHDD and an NVMe root with 55 GB free.
(a) Verdict
Germany and the bytes stay the same. But they bound anonymous memory, not the working set.
Germany passed because its 17.8 GB of work files fit the 15 GB page cache (RSS peak 13.9 GB
[measured Routing bake 4/4: work tables in files, and sorts on disk #3251]).
63M roads with 17 profiles, so the bake fails when the catalog opens the package, after all the
profile work. Soft stop: three stages do random lookups through mmap into files that are 2–10
times the RAM.
about 28 B per road, so about 8–9 GB for Europe and 28 GB for the world [est]. Nothing enforces
the 4 GiB budget, and nothing reads the cgroup cap.
are 77 % of the Germany time without the catalog [measured Routing bake 4/4: work tables in files, and sorts on disk #3251].
in the way-order scan, put the roads into their final (cell) order once, in buckets, and make
every later stage a sequential scan. This also gives restartable stages and carries Routing: hierarchical search and disk storage #3227.
(b) Stage table
Sizes per unit are [code]. Europe sizes are [est] for R = 300M; the world is × 3.3. Times are the
Germany times [measured #3251] × 7, which assumes that every page is in the page cache: a lower
bound, not a forecast.
step.rs:44-57)osm.rs:254-268)reader.iter()is 1 thread and decodes the node blobs too (osm.rs:219-227)source.rs:494-502), drop relations without a highway, node or relation member (osm.rs:273-278)osm.rs:304-312)needed8 B/node (4.9 GB);shared1 B/nodeosm.rs:280-298)needed(30 probes); 1 thread; decodes way and relation blobs toobuild_graph(osm.rs:339-467): attributes and country per way, restrictions, preserved relations, junction marks, way splitting, turn rulesRawWay16 B/way, twice; a full copy of the ways table (osm.rs:361);point_ids4 B/node (2.4 GB); roads 36 B + 8 B + 12 B/shape point (33 GB); graph points 21 B/junction;group×2: 8 B/junction + 4 B/road each; forbidden turns 8 B eachrulesVec 48 B/restriction;crossingsHashMap about 32 B per blocking node;keptHashSet per kept relation. Germany whole import: 0.03 GB [measured #3251]source.rs:458-460), three times per way node: coordinates (osm.rs:407), junction flag (osm.rs:396), point id (osm.rs:486)nodes.ids,nodes.points,needed,shared,point_ids: 17.7 GB for Europe, 59 GB for the worldterrain.rs:6-110,obc-dem planner.rs:215-266)terrain.rs:47), random write into the new shapes (terrain.rs:105)layout.rs:6-34,lib.rs:182-213)column.rs:214-220)lib.rs:252-367): checks, topology, snap cells, geometry pages, closures, junctions, reverse arcsfirst4 B/road,head4 B/arc; cells 12 B per (cell, road) pair, sorted (5.4 GB); junction columns about 6.8 GB; reverse arcs 4 B/road + 4 B/arcgroupsabout 150 B per non-empty 0.01° cell (lib.rs:324);geometry88 B per 128 roads; node closures HashMap (lib.rs:341); closure ids 8 B/road (closures.rs:90); doubts 1 B/road (lib.rs:349)lib.rs:357) and by node ID for each junction (lib.rs:343)lib.rs:368-392): costs (cost.rs:54-110), landmarks (landmarks.rs:140-191), turn costs (cost.rs:118-157), connectivity (connectivity.rs:35-101)connectivity.rs:46,71,landmarks.rs:58,84);sizes8 B per component;cycle_routesHashMap per way in a cycle route, rebuilt per profile (cost.rs:64); the manifest grows by about 90 B per page;Writer.recordsabout 110 B per distinct object (directory.rs:215)cost.rs:78-79): 30 GB working set for Europe; by node ID per arc for the three road profiles (cost.rs:143); the graph searches are local, thanks to the Morton orderdirectory.rs:213-250)pages.binsequential, zlib level "fast" + SHA-256 per page; Germany 6.3 GB [measured], Europe about 45 GBrecordsBTreeMap, see 9overlays.rs:100-178)membershipsBTreeMap per way in a route;routesJSON per relation;attributesHashMap of distinct property strings. Germany 0.67 GB [measured]overlays.rs:155) and for the country of every way (overlays.rs:131)catalog/mod.rs:252-448), the documented exceptionpointsHashMap per node of a route way; all results. Germany 7.64 GB own, 12.2 GB RSS [measured #3251]blocks.rs:207-314,step.rs:131-143)objectsandconsumersabout 250 B per object; one clone of the whole manifest per grid cell (blocks.rs:80); the whole catalog asserde_json::ValueShort answers to the questions of point 1:
and the catalog.
per arc, plus the working arrays of the two graph searches. The cost-basis dictionary is shared.
is a
BTreeMapin RAM until the last cell.rayonin the crate.(c) Findings, ranked by impact
1. Hard limit: the manifest stops a package at about 63M roads with 17 profiles
in
manifest.json(table.rs:5-28); only the geometry is two-level (lib.rs:321). A manifestabove 128 MiB is refused (
package.rs:17,176,directory.rs:204-206).preparedoes not checkthe size. The first reader is the catalog (
catalog/mod.rs:254), thenblocks::publish(
blocks.rs:216).profile 4.86 (road costs, basis ids, turns, snap bits) + 6 landmark columns × 0.40 = 7.26.
Total 3.84 + 2 + 17 × 7.26 = 129 digests × 67 B = 2.1 B per road. 128 MiB / 2.1 B = 63M roads.
Germany (about 45M) gives about 95 MB and passed [measured: the bake ended]. Europe gives about
630 MB, the world 2.1 GB.
with
Limit.files, not pages). Until then: do not start a Europe bake. Add one check after the import that
compares the road count with the limit and fails early. Size S for the check. Risk low.
2. Random access through mmap: the bake needs its work files in RAM
Table::getis a binary search (source.rs:458-460).build_graphcalls it for the country of each way (
osm.rs:352), for the way filter (osm.rs:361), andthree times for each way node (
osm.rs:396,407,486). The ways arrive in way-ID order; theirnode IDs are not in that order. Working set: 17.7 GB for Europe, 59 GB for the world.
Costing::newreads the tags and the node listof the way of each road and resolves its first node for the country (
cost.rs:78-79,source.rs:627-629), for each profile. The roads are in Morton order by then. Working set:way tags about 12 GB, node lists 6 GB, node table 10 GB, ends and IDs 3 GB: about 30 GB for
Europe, 100 GB for the world. The closures (
lib.rs:357), the node closures (lib.rs:343),the signal check of the road profiles per arc (
cost.rs:143) and the overlays(
overlays.rs:131,155) do the same.order, while the roads are stored in way order (
terrain.rs:26-105).spatial_orderthengathers every column and the 49 GB shape list by a permutation (
column.rs:100-103,214-220).preparation, in a container of 15 GB [measured Routing bake 4/4: work tables in files, and sorts on disk #3251]. The work folder peaked at 17.8 GB. The
mapped files were in RAM. Europe has 125–150 GB of work files [est] for 16 or 32 GB of RAM.
the USB HDD, about 8k on the SATA SSD, 20–40k on NVMe, on one thread. The costs alone touch
116M ways × 17 profiles × about 5 cold pages = 10 billion faults in the worst case on 16 GB:
weeks on the SATA SSD. With 32 GB the 30 GB set almost fits; at a 15 % miss rate it is still
about 1.5 billion faults, 2 days.
build_graph: 0.15–1.5 billion faults, 5–50 h on the SATASSD at 16 GB; it fits at 32 GB for Europe and never for the world. Terrain and layout: 0.1–0.6
billion faults, 3–20 h. The spread is how well way IDs cluster in space, which nobody measured.
On a spinning disk none of this ends.
references()sorts(node id, ref position)pairs insteadof bare IDs. Pass 2 merges the node stream with that sorted column and emits
(ref position, lat, lon, flags). One moresort::sortedby ref position gives away_pointscolumn parallel to the node lists. The junction flag (uses > 1, a tagged node,a restriction via from a small sorted Vec) is set in the merge.
build_graphthen readsonly sequential columns. Graph point ids come from one sort of the road endpoints.
sort.rsalready does both sorts. Disk: 2 × 12.5 GB for Europe, 2 × 42 GB for the world.country, the direction and the profile, not on the shape (
suitability.rs:23-80,road_bike.rs:14). Compute the country once per way, the basis id of each profile anddirection, the closure set and the doubt byte while the way is at hand, and carry them as
road columns. Per junction keep a signal bit and a doubt byte beside
node_access. After theimport nothing reads
graph.osmexcept the overlays (which then readway_points) and thecatalog. This also parses the tags once, not 17 times.
cell of Routing: hierarchical search and disk storage #3227 later). Append it to one of K bucket files chosen by the top bits of the key
(K so that a bucket is about 1 GB: 64 for Europe). Then run today's
Roads::permuteon onebucket at a time and append to the final columns. The terrain then runs after the order, as
one sequential pass that writes the new shapes in order; a separate terrain order is not
needed, because the final order is spatial and the terrain keeps 12 squares.
(4 B × R is 1.2 GB for Europe and 4 GB for the world: fine). Everything larger is read in order
or sorted.
once. The cost and access code and its tests stay.
3. Anonymous memory is O(region) and nothing enforces the budget
Evidence (verified by reading): the budget is used in one place, the sort run
(
work.rs:12-25); Routing bake 4/4: work tables in files, and sorts on disk #3251 says so. These structures live in anonymous memory and grow with theregion:
Vec<u64>, kept until the last writeclosures.rs:90,lib.rs:353,395lib.rs:349connectivity.rs:46,71,landmarks.rs:58,84table.rs:9-15Writer.recordsdirectory.rs:215groupslib.rs:324-340lib.rs:311memberships,routes,attributesoverlays.rs:56-96,129objects,consumers, manifest clonesblocks.rs:80,133,218,258obc-dem planner.rs:446-486Calibration: these terms give about 1.3 GB for Germany; the measured peak of the preparation
is 1.26 GB [measured Routing bake 4/4: work tables in files, and sorts on disk #3251]. Linear to Europe: about 8.8 GB. World: about 29 GB.
Change: closure ids and doubts become columns computed at emit (finding 2.2). Write the
closures before the profile loop. Replace the recursion stacks by a column (the stack is a
plain array;
Column<(u32, u32)>works as it is). Write the snap directory per one-degree groupas the sorted cell list crosses a group border; the list is already sorted by latitude first.
The manifest and the writer index go with format 9. Size M. Risk low.
Enforcement: one cheap guard instead of hope: the step samples its own
RssAnonat eachstage end and fails when it is above the budget. Size S.
4. One thread, and work that is repeated 17 times
outside the catalog. Germany: import 609 s, terrain 392 s, preparation 3,853 s, overlays 184 s.
The preparation is 77 % of that. Inside one profile (227 s) [est]: costs about 70 s, landmarks
about 65 s, connectivity about 30 s, turns about 20 s, page compression and hashing about 15 s.
Costing::newcopies each shape into aVecand looks up the way and the country per roadper profile (
cost.rs:69,78-79);Country::atruns 17 × R times.transitionbuilds two fullRoadvalues, 26 column reads, per arc per profile(
cost.rs:120,lib.rs:117-138): 850M × 17 × 26 loads for Europe. It needsto,from,wayandaccess.cycle_routeswalks all relations again for each profile with a route bonus (cost.rs:64).States::tailis a binary search overfirstfor every reverse arc of every profile(
connectivity.rs:29-31,85): 850M × 17 searches for Europe. A per-road offset inside itsdeparture group makes the arc id a sum, and
reverse_arcs(4 B/arc) goes.and takes a mutex up to four times (
obc-dem planner.rs:236-266).reader.iter()decodes on one thread, and each pass decodes the blobs it then drops(
osm.rs:219-227).par_iter()of the same crate keeps the order (par-map guarantees it):a one-line change.
Europe [est]. Routing: hierarchical search and disk storage #3227 deletes them; do not tune them.
per road, turns per arc) that compute all 17 profiles in one pass and split by road range over
the cores. Connectivity runs 2–3 profiles at a time (about 6 GB of mapped working set each for
Europe). Keep one dictionary per profile and merge them in profile order, so that the bytes do
not depend on thread timing. Size M. Risk low to medium (determinism needs a test with 1 and
N threads).
lower bound of 9.7 h and 33 h today.
5. No restart and no partial rebake
(
obc-data-steps planner.rs:401-418). Its work files are unnamed scratch thatDropremoves(
work.rs:55-86). The engine removespartial/layer-<key>/, withTMPDIRin it, when the stepends, also when it fails (
specs/obc-data.md:830-831,process.rs:69-71). So a crash in hour 9loses everything, a profile change repeats the import and the terrain, and so does a format
bump.
(
Client::Nonelayers exist). After finding 2 each stage reads and writes whole column files inorder, so the split is natural:
planner/routing/source: PBF → ways with tags andway_points, tagged nodes, relations.Inputs: the OSM cut, the bounds.
planner/routing/roads: way scan → junction graph → partition (Routing: hierarchical search and disk storage #3227) → roads in finalorder → heights. Inputs: layer 1, GLO-30, the reference. No profile.
planner/routing/costs: bases, totals, turns, snap bits, cost tables. Inputs: layers 1 and2, the profiles, a cost-model version. To keep layer 2 free of profiles, layer 3 scans the
ways once and writes each basis id through the "emit index → final id" map of layer 2
(4 B × R, a scatter that fits the RAM).
planner/routing: the package, the overlays, the catalog, the blocks.A crash repeats one layer. A cost-model change repeats layers 3 and 4, about a third of the time
[est]. An OSM refresh repeats all layers: the import has no diff input, and at 3–4 h that is
acceptable; I would not build an incremental import.
Column::create(path)/open(path)), with a fixed bytelayout: today a column stores Rust tuples with their padding (
column.rs:22-25,68-71), which isfine for scratch and wrong for a stored file. Disk: layers 1 and 2 are about 30 GB and 75 GB for
Europe [est] and stay in the store.
6. Limits that are close or unchecked
firstandheadare u32 (base.rs:42-57), and the tables useu32 lengths (
table.rs:10). At 2.84 arcs per road the arc count passes u32 at 1.51 billionroads. A world of 1.0–1.3 billion roads uses 66–86 % of the range [est]. The road index itself
is fine. Decide in format 9: cell-relative offsets or a 64-bit
first.closures.setsis onepage of at most 8 MiB raw (
lib.rs:409,storage.rs:5-9), written after the last profile(
lib.rs:395). The conditions are free text. At about 50 B per set [est], if a continent has more than about 150k distinctsets, the bake fails at its end.
page budget all fire inside
prepare, hours in.7. Disk: double and triple writes, needless copies, and the free space
pages again (
column.rs:112-137). A work file is written about twice.Lists::filledpushes a default value into every slot before the terrain overwrites it(
column.rs:185-195,terrain.rs:24): the 49 GB shape list is written three times.Column::filleddoes the same for the per-profile arrays.Builder::finishsorts and copies every table although a PBF is sorted by ID(
source.rs:494-502): 16 B per object of order column plus a full copy, 20 GB for the nodesand 21 GB for the ways of Europe.
osm.ways.filtercopies the ways again (osm.rs:361), andthe relations are filtered twice.
permutedholds the old and the new shape list together (lib.rs:199-212).70 GB, preparation 28 GB + 17 × 12 GB: about 525 GB, so about 1 TB of writes with the zero
fill. Peak space: about 150 GB of work files + 45 GB package + 45 GB blocks + 4 GB overlays =
about 245 GB. OSM1 has 234 GB free. The world needs about 800 GB.
posix_fallocateinstead of writing zeros (ext4 reserves the blocks and reports afull disk at growth; keep the zero write as the fallback for other platforms); skip the sort and
the copy when the IDs arrive in order; a bitmap instead of the filter copies. Findings 2 and 4
remove the rest. Size S. Risk low.
8. The budget does not see the cgroup or the free memory
sort_run_bytesis min(4 GiB,OBC_DATA_MEMORY_BYTES)(
work.rs:12-25). The engine takes three quarters of the physical RAM fromsysconf(
runs.rs:31-47) and passes what the running steps do not reserve (runs.rs:653). obc data: the bake's step limits ignore the cgroup memory cap #3203 isopen. A run is sorted in place inside the mapping, so it needs 4 GiB of page cache to be fast.
MemoryMaxscope the kernel charges the mapped file pages to the cgroup, sothe page cache of the bake is the cap minus its anonymous memory. The bake does not die; it
thrashes (finding 2) at a much smaller region. Today the PC has 2 GB available: a 4 GiB sort
run does not fit.
constant, the variable and a quarter of the memory that is really available (cgroup
memory.max−memory.current, elseMemAvailable). Size S.9.
blocks::publishdoes not scale with the packageprepareclones the whole package manifest for the full selection andfor every grid cell (
blocks.rs:80), then keeps a few pages. With a 630 MB manifest and about5,000 land cells at zoom 9 for Europe that is hours of string copies [est]. It also holds every
road id, every junction id and two maps over all objects in RAM (
blocks.rs:133,218,258), anddecodes each road twice (
blocks.rs:45,245). The step then parses the whole catalog into aValue(step.rs:133-134).with it. Name it in Routing: hierarchical search and disk storage #3227 so that it is not carried over. Size M inside Routing: hierarchical search and disk storage #3227.
10. Terrain details
(
obc-dem planner.rs:446-486): a start-up time and a memory that grow with the nationalcoverage [code]. It needs a bound before the reference covers large parts of Europe.
Terrain::openhashes every GLO-30 file on each bake (planner.rs:153-157), about 100 GB forEurope [est], although the store already knows the hashes of its objects.
planner.rs:236-266). A"last squares" entry in
Recentremoves both. Size S.rejected it as "little gain on disk"; at 49 GB (Europe) and 160 GB (world) it is not little.
Decide it with format 9, which stores the geometry.
11. Determinism: good today, three things to watch
Ordof the record, with the row index where IDsrepeat; no output depends on a hash-map order; Kosaraju and the landmark choice are fixed.
cost.rs:108). With parallel profiles orranges the insert order must not decide the ids (finding 4).
cosandhypotof the system libm(
model.rs:18-24,terrain.rs:48-61,114) and are stored as rounded integers or f32. Samemachine and same binary: same bytes [measured Routing bake 4/4: work tables in files, and sorts on disk #3251]. Another libc can differ in the last bit;
with about 100M bridge samples a flipped f32 is plausible [est]. Only matters if bakes move
between machines.
by junction id and takes the source side of the residual graph, which is the same for every
maximum flow.
12. Crash behaviour of the work files
&mut selfexcludesreaders); alignment is page alignment; a full disk is an error, not a fault. An I/O error of
the drive is a SIGBUS without a message. A killed bake leaves its folder; under
obc datatheengine removes it with the partial directory. Outputs are published by the engine only after
success. No change needed.
Good, in one line each
column.rs,sort.rs,work.rs: 420 lines, clear invariants, one unsafe idea, tested.(d) What #3227 needs from the bake
undirected segment (8 B). Both are small and sequential after finding 2.1. Exact inertial
flow in RAM needs about 40 B per junction [est]: order by projection, CSR, flow bits, BFS
levels. Europe: about 5 GB. World: about 16 GB. That is O(region) anonymous memory: fine for
Europe on 16 GB if the terrain job is not running, fine for the world on 32 GB, and a second
documented exception to the 4 GiB budget. Time: 52 s for 3.09M junctions on 4 cores
[measured Routing: hierarchical search and disk storage #3227], so about 35–50 min for Europe and 2–3 h for the world [est], with the log
factor of the deeper recursion. Below the top levels each part fits a core and the parts run
in parallel.
(Morton prefix), cut the bucket graph with capacities until a part has under about 4M
junctions, then run the exact method inside each part. Memory: megabytes for the top, 160 MB
per part. Cost: the top cuts follow bucket borders, so the top cells get more border roads
(perhaps 10–30 % [est]), and Routing: hierarchical search and disk storage #3227 measured that the top level does the most query work. Use
it only if the exact method does not fit.
key replaces the Morton key in
layout.rs, and oneRoads::permutedoes it. But that permuteis the 49 GB random gather of finding 2.3, so it does not work at Europe scale. With bucketed
ordering the cell order is the one and only order: the partition runs on the junction graph
before the roads are ordered, the top-level cell is the bucket, and each cell of each level is
a contiguous range by construction. Junctions should take their ids in the same order. The
present column and sort design carries this after finding 2, not before.
road. In cell order the inputs of a cell are contiguous ranges of
totals,turns,firstand
head, so the stage streams, needs megabytes per worker and runs in parallel over cells.Time: 1.5 s per million roads per profile per core [measured Routing: hierarchical search and disk storage #3227]: Europe 2.1 core-hours,
about 25 min on 6 cores; world 7 core-hours, about 1.3 h [est]. Output: 2.6–3.3 B per road per
profile [measured Routing: hierarchical search and disk storage #3227]: about 15 GB raw for Europe, 51 GB for the world. Write the tables in
cell order from per-chunk buffers, so the bytes do not depend on the threads.
manifest digests) go with Routing: hierarchical search and disk storage #3227, and so do the manifest limit, the writer index and the block
publisher. So: finding 2 first, then the bake part of Routing: hierarchical search and disk storage #3227, then the first Europe bake. A
Europe bake before that needs the manifest fix and still cannot run the catalog.
(e) Open measurements
example
systemd-run --scope -p MemoryMax=5Gin a cloud container, and time the import, theterrain and one profile. This predicts Europe on 32 GB and settles the range of finding 2.
bytes. It decides 300M against 400M and with it every disk figure here.
closures.setson Germany (finding 6).blocks::publishon Germany; Routing bake 4/4: work tables in files, and sorts on disk #3251 did not record them.(finding 11, watch 2).
same 0.01° cell. It explains how far the present code is from sequential.
Generated by Claude Code
timohueser commentedon Nov 10, 2026
Review of 2026-11-10: the stored format, R2 and the serving path
One of three review reports on
develop9ec892f (engine, bake, storage). An agent wrote it from the code, the issues and the pull requests. Nothing was built or run, so each scale figure is an estimate unless it names a measurement. The summary and the owner decisions are in #3000.Review of origin/develop
9ec892f9a, read in/media/timo/OSM1/tmp/routing-review/wt. Read-only.Sources of numbers:
/media/timo/OSM1/local(planner release
04de7174…, routing package388c436e…, Central Switzerland, the same size asproduction). Two throwaway scripts read the routing step index and the pack indexes. Nothing was
written there.
Scale used: Europe 275M directed roads (owner: 250–300M), world 1B.
(a) Verdict
beside and switch), but its unit is wrong: 4,096-entry pages in global road order, each with its
own SHA-256, grouped into packs by "the same set of cells". Every size and count below follows
from that unit.
blocks.jsonis one JSON document with a 128 MiBlimit; Manifests: small release manifests, per-cell offline catalogs and file lists as objects #3141 did not touch it), and the service decodes the whole graph into heap: 14 GB for
Europe with one profile, 59 GB with 17, per release, for up to three releases.
graph, the load time and the three-times RAM. Go ahead with it.
object stable between releases, per-column files multiply cold reads on a rate-limited disk, raw
columns for three releases do not fit 1 TB at world size, and the follower as built deletes and
reinstalls every release at each start.
whose bytes are a slice of the installed file, with cell-relative road IDs. Install is
"decompress and append" on the server and on the phone. Then delete
blocks.json, the packs,the per-page hashes and the Python selection merge.
(b) The format and the serving path as built
Objects of a routing package
planner/router/src/storage.rs:5-14u8/u16/u32/u64, the narrowest width of the whole column; all-ones = absenttable.rs:5,base.rs:44-56,73-106graph.first,graph.headu32pages;firsthas roads+1 entries,headone per arcbase.rs:122-141road_costs,turns,costs(cost-basis IDs),allowed(1 bit per road)package.rs:32-41Vec<CostBasis>pages (2,913 entries today, measured here)package.rs:58mapping(junction of each road) and 6 distance columns per profilei64deltas per pagelandmarks.rs:86-111package.rs:18,geometry.rs:80-110closures.rs:52-58blocks.jsonpackage.rs:19,247-266,router-build/src/blocks.rs:161-180packs/<id>/pages.bin(pages, no separators) +pages.idx(OBCRIDX3, 48-byte records: digest, offset, length, sorted).<id>= SHA-256 of the joined page digests. ≤ 16 MiB. One pack per distinct set of consumer cellsdirectory.rs:19-21,router-build/src/blocks.rs:192-202,258-296routing/blocks.jsonrouter/src/blocks.rs:11-22offline/routing-cells/<cell>.jsonpages+blocks)router-build/src/blocks.rs:74-158indexes/planner/routing/grid/index.jsonblocks.jsonundergraphtools/planner_grid_pack.py:10-34routes/tiles/9-X-Y.jsonspecs/route-catalog.mdoverlays.sqlite, whole packagerouting/{manifest.json,pages.idx,pages.bin}host/obc-data-steps/src/planner.rs:529; measured here:"client":"none"On R2: every file is
objects/<sha256 of transport bytes>; named metadata is underreleases/<id>/. A routing pack costs two R2 objects.Road IDs and grid selections
router-build/src/layout.rs:6-19).Dense
u32. Arc index is also a denseu32.IDs. Local ID = position in the joined ranges (code:
router/src/blocks.rs:39-88).Union::openreads thefirstandheadpages of the ranges, drops arcs to absentroads, and builds the reverse graph in heap (code:
router/src/blocks.rs:203-292). Costs andlandmark columns are decoded per profile on first use (
data.rs:377-403).cells in Python (
tools/planner_grid.py:51-70,tools/planner_downloads.py:95-104) and writes anew
routing/blocks.jsonfor the selection.Bytes per directed road, stored (measured here)
1,201,625 roads, 3,359,430 arcs (2.80 per road), 490,764 junctions (0.41 per road), 17 profiles.
43,244 page objects (0.036 per road), median 3.5 KB, in 50 packs.
road2.4)graph.first+graph.headpages.idx(48 B per page)blocks.jsonWithout landmarks: 91.8 B/road. With the overlay tables of #3227 (11.0 MB zlib for 7.72M roads and
one profile = 1.4 B/road, #3227 measured), 17 profiles: about 116 B/road (estimate).
Bytes per directed road, decoded in the service heap (code widths × measured counts)
first4,head11.2,reverse_first4,reverse_tail11.2,reverse_offsets2.8u32; hiking and mtbu16), turns 5.6 (u16× 2.8), landmarks 4.9 (6 ×u16× 0.41)This matches #3000 (37 + 174). Raw fixed-width turn columns are 40 times their zlib size
(5.6 against 0.14 B/road): they are almost all one value.
Serving path as built
obc data serve prod(the follower) polls R2 every 30 s (cli/serve_cli.rs:226-246). It wantsup to three releases: serving, rollback, and the one of
planner/next.json(serve.rs:52-59).store (
serve/services.rs:113-133,target.rs:333-346). It parses the step indexes on each ofthree passes (
services.rs:127).serve.rs:287-290,serve_cli.rs:272-278): each fileunder
routing/,search/,offline/is hard-linked (identity) or gunzipped (gzip) intoserve/<target>/<planner id>/, then hashed again (services.rs:428-444).planner-service(Rust),node server.mjs(search),python -m tools.planner_downloads(services.rs:86-91,173-204). Nine processes for threereleases. They must answer within 120 s (
serve.rs:26).planner-serviceopensblocks.json, maps each pack, builds a digest-to-pack table in heap(
directory.rs:127-141), then loadstouringbefore it listens (service/src/http.rs:26,50-52):the whole graph and that profile, decoded. Workers = CPUs of the unit, at most 12
(
http.rs:31,main.rs:21-24); each is aRouteron a blocking thread. They share graph andprofiles; each has its own labels and page caches. 1 s queue wait, then
503 busy.MemoryMax=9216M,CPUQuota=1800%,TasksMax=576for the follower and all nineprocesses (
tools/vps/obc-data-serve.service:20-22). The present VPS has 4 cores and 7 GB(obc data: publish Trail View to prod (central Switzerland now, the Alps box after the Rust port) #2845).
/planner-api/releases/<id>/ready, then switchesrelease.json. Clients move at once. Nodowntime. Memory is the sum of all loaded releases: two in steady state, three during an update.
Rollback is instant because its processes stay loaded.
the installed folder (
services.rs:272-277), then installs again after a back-off. The workfolder is also deleted at every follower start and stop (
serve_cli.rs:141,206).Steps that are O(package) in RAM or read every object in series:
Union::openand the profileload (heap); the parse of
blocks.json(heap, oneStringper page digest);Files::open(36 Bper page in heap); the follower's parse of the routing step index as
serde_json::Value, at leastthree times per fetch and again for prune and install; the serial download; the serial hash of
every installed file; before publish,
planner_verify.py(materialize and hash), thenplanner_router::open(..).verify()which reads and hashes every page(
host/obc-data-steps/src/planner/catalog.rs:176-237).Phone as built
pages.bin+pages.idxeach), two search databases,one route catalog file, the map packs of its box, and shared assets. The selection
blocks.jsonis made by the downloads service.
against 129 for the whole package, 56–888 ID ranges, manifest 66 KB–1.3 MB.
releases/<id>/, and opens the router withbudget 0 = the engine default (
companion-ios/PlannerNative/RouteProvider.swift:22). The enginethen builds the union graph in heap at each open.
(c) Findings, ranked by impact
1. The service holds the graph in heap; three releases multiply it
router/src/blocks.rs:203-292,data.rs:377-403,serve.rs:1-5. Verified by reading.touring14.3 GB, with 17 profiles 58.9 GB, per release. World: 37.5 / 52 / 214 GB. Three releases with
one profile each at Europe: 43 GB before search, labels and page cache. Not compatible with
32 GB; not usable in 64 GB.
data.rs:41-50). At Europe asecond profile (2.4–4 GB) does not fit that room, so each profile change evicts and decodes
several GB under one lock (
data.rs:326-340,525). With 17 profiles the service thrashes.u32values to inflate and a 770M-arc scatter for Europe: 1–1.5min (estimate), against the 120 s start limit (
serve.rs:26). World does not start. A releasethat misses the limit reinstalls and retries for ever.
2.
routing/blocks.jsonis still one JSON document; #3141 fixed only the release manifestspackage.rs:17(MAX_MANIFEST_BYTES= 128 MiB),directory.rs:195-207,data.rs:155-161. Manifests: small release manifests, per-cell offline catalogs and file lists as objects #3141 decision 6: "routing/blocks.json, and the copy of its graph in therouting grid index, stay with workstream 4". Verified by reading.
roads. Europe 0.78 GB, world 2.85 GB (estimate; EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 estimates 5.7 GB at 650M roads because
the flat snap map grows with area).
planner_grid_pack.py:34), andplanner_verify.py:229-230parses both to compare them. The follower parses that index intoserde_json::Value(services.rs:381-403): several GB of heap in the follower at Europe size.Three Python tools
json.loadsit.Stringeach): 0.9 GB for Europe,3.3 GB for the world, per service process (estimate).
directory. Size M inside the Routing: hierarchical search and disk storage #3227 format work. Risk: low.
3. The follower's installs are not durable, and one service failure reinstalls everything
serve_cli.rs:141,services.rs:272-277,serve.rs:287-290,395-399. Verified byreading. EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 workstream 7 lists the effect (30 min recovery, estimated).
of it, per release, in series, on the poll thread, then loads three graphs. With raw columns
written at install (Routing: hierarchical search and disk storage #3227) the same code would rewrite 66 GB (Europe) or 239 GB (world) per
release at every start.
installed/<planner id>/with a completion marker; never delete it on astop; delete only when no wanted release names it. Run install on the fetch thread. Give each
service its own failure state, so a search fault does not stop routing. Download with 8–16
parallel requests. Size M. Risk: low.
4. Global dense numbering makes every page new at every OSM refresh
layout.rs:6-19(ID = rank in the sorted order);headpages and snap lists storethese IDs; column pages are cut every 4,096 ranks. Verified by reading; not measured on two
bakes.
headpages andall snap lists change. So releases share almost no routing objects. The per-page SHA-256 buys
no reuse between releases. It costs 0.036 objects per road, 48 B on disk and 36 B of heap per
page (
directory.rs:124), 64 hex characters per page in JSON, and a SHA-256 on every page read(
package.rs:276-282).obc data: publish Trail View to prod (central Switzerland now, the Alps box after the Rust port) #2845 measured, and a few cents of Class A. It matters for disk on the follower (finding 6) and
for phone updates (a refresh downloads every cell again).
((d) point 2). That costs little, and a stable partition later makes unchanged cells
byte-identical. Size M. Risk: medium (engine addressing).
5. Pages and grid cells do not line up; packs fragment
router-build/src/blocks.rs:258-296. Measured here.One cell costs 1.03–3.3 times its own bytes. The nine cells together download 209 MB for 155 MB
of pages.
with two, 13 with three, 10 with four to nine. 30 of 50 are under 1 MB, 9 under 50 KB.
publishclones the full manifest for each cell (blocks.rs:80) and keeps every cellselection and a map of every page in RAM until the end (
blocks.rs:221,258). Estimate forEurope (3,800 cells, 1 GB manifest in heap): about an hour of copying and 5–10 GB of RAM. It
does not finish at world size on the 16 GB bake machine.
blocks::publish, the packs, the consumer sets and the cell manifests go. Size: part of theRouting: hierarchical search and disk storage #3227 format. Risk: low.
6. Disk: three releases of raw columns do not fit 1 TB at world size
copy of 97 % of the pack bytes (finding 8). Europe 69 GB, world 258 GB. Three releases: 207 GB
and 774 GB, routing only. Search adds 51–56 GB plus gzip copies per release (EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000, estimated).
39.2, overlay tables about 50) plus the parts that stay compressed 62 B/road (geometry, cost
IDs, snap) = 239 B/road. Routing: hierarchical search and disk storage #3227's own target is 185 B/road. World: 185–239 GB per release
installed, plus about 110 GB of transport objects if the follower keeps them. Three releases:
0.9–1.05 TB. Europe: 51–66 GB per release; no problem.
releases: before an install, remove the rollback; after the switch the old serving release is
the rollback; (3) narrow the columns where the measurement says so: turns as a default plus an
exception list (40 times redundant today),
u16costs with exceptions,headas cell-localu16. Size M. Risk: low.7. The systemd memory limit caps the page cache
tools/vps/obc-data-serve.service:20. Verified by reading. cgroup v2 charges filepages to the unit that reads them.
server has. Its comment still derives the figure from the legacy units, and it is larger than
the RAM of the present VPS.
MemoryHigh/MemoryMaxnear the RAM of the server and put a smallhard limit only on the anonymous memory of each service (labels, queues). Size S. Risk: low.
8. Routing packs are gzipped a second time
tools/planner_offline.py:12,31: the "already compressed" test reads the suffix ofthe source path, and a step receives store object paths without a suffix
(
host/obc-data/src/store.rs:185). Measured here: 36 of 50pages.binhave gzip transport,149.81 MB to 149.05 MB (0.5 %).
services.rs:435) andinflates it at each install. The phone inflates them too.
9. Cold reads on a rate-limited disk: per-column files are the wrong layout
about 2,900 level-1 cells and 38k road states. EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000: Contabo NVMe plans show about 2,800 reads
per second at 64 KiB (public benchmarks, not measured by us).
first,head, road costs, turns, plus the geometry pages of its path roads: 6 or more. 2,900 cells →17k+ reads → 6 s or more at 2,800 reads/s. Page faults on a map are also serial per worker.
group for costs and turns, one per cell for geometry (about 67 KB compressed at 1,250 roads).
That is about 3 reads per cell: about 3 s cold for 2,000 km, 0.4 s for 300 km (estimate). After
the search, give the kernel the whole list of cells at once (
madvise(WILLNEED)or parallelpread). Size: a layout decision inside Routing: hierarchical search and disk storage #3227. Risk: low.10. The arc index is a
u32router/src/blocks.rs:19,table.rs:10,22. 2.80 arcs per road (measured here).(estimate). Cell-relative layout removes the global arc index. Size: none if (d) point 2 is
taken. Risk if ignored: a late format change.
11. Three verifiers and five hash passes before a publish
catalog.rs:143-237(Rust checks object sizes and hashes, runstools.planner_verify, thenplanner_router::open().verify()),planner_verify.py:221(materialize and hash),
planner_offline.py:24-44(two hashes per packed file).verifier re-implements the Rust installer (
planner_offline.materializeagainstservices.rs:materialize).12. Phone limits as built
at each open in 1–3 s (estimate). About 25–30M roads is the ceiling on a 4 GB iPhone
(estimate); Germany does not open. Heap is dirty memory, which iOS counts; clean mapped pages it
does not. This is a strong reason for Routing: hierarchical search and disk storage #3227 on the phone.
data.rs:41-44), so a large area ends in an iOSkill, not in
limit.Junctions::readallocates a bit set over all source junctions and loops over all of them(
landmarks.rs:123-128): 51 MB and about 1 s at world size for any area. Goes with landmarks.13. Smaller items
(
specs/route-catalog.md), and each record is stored whole in every cell it touches.Files::openholds 36 B per page in heap: 0.36 GB Europe, 1.3 GB world (estimate).specs/planner-release.md:56-58still saysrouting/holds the three package files andoverlays.sqlite. In a grid release it holdsblocks.jsonand packs.Good as it is
objects per publish, under $1 of Class A (estimate).
client: none(measured here).Unused or duplicated
routing/pages.bin155.2 MB andblocks/packs/156.9 MB (measured here)router-build/src/step.rsSelection::whole,Snap::Directory, 1° snap directories): only bake-internal steps and tests use itdata.rs:147-152,package.rs:247-274blocks.jsontwice (file and step index), compared by JSON equalityplanner_grid_pack.py:34,planner_verify.py:229offline/routing-cells/,cellsof the step index,routinginoffline/cells/planner_grid_pack.py:21-31,planner_grid_offline.py:39blocks::prepareand Pythonplanner_grid.routing/merge/ranges/cellstools/planner_grid.pymaterializeand Rustmaterializeplanner_offline.py:47,services.rs:428pages.idxper pack plus a global digest-to-pack tabledirectory.rs:119-158OBCRIDX3, blocks 2, grid 3, public grid 4, index 4, offline 3, selection 6, bundle 1, release 2)legacy()treatscell-catalog/,planner/,reference/as legacy prefixes, yet the live pointers are under the first two; #2656 (open) still lists legacy R2 keys and VPS units to remove. Not checked on the bucketr2.rs:451-454(d) The #3227 storage direction
Judgement against the alternatives.
code, workers and releases share memory for free, an idle release costs nothing, a restart is
instant, and on iOS mapped pages are not counted as app memory. Cost: 3–4 times the disk of
today's zlib pages for the same columns (126 B/road raw against 33 B/road compressed for graph,
costs and turns, from the tables in (b)).
shared cache with locks, pays decode on every miss, and its cache is dirty memory on the phone.
Keep it only for cold bulk data: geometry, snap lists, cost-basis IDs. Routing: hierarchical search and disk storage #3227 says this for the
cost IDs; say it for geometry and snap too (56 B/road compressed).
large binary objects. Raw upload doubles the phone download. No.
many ranges in many files, with no simple resume or per-object hash, and Cloudflare does not
cache objects over 512 MB (my knowledge; check). Many small objects (today) are bad for
everyone. The middle is right: one object per partition cell and part, 5–60 MB.
Holes, and the change for each.
allows a second logical encoding (pages) and an install-time transform. Change: a published
object is a zstd frame of a byte slice of the installed file. Install = decompress and append,
in cell order, plus one offset table. No Postcard, no page table, no renumbering. The manifest
carries the SHA-256 of each transport object and of each decoded slice; the installer hashes
while it writes, so there is no second pass. A
--verifyscrub re-reads on demand. Per-readhashing goes.
about 1,100 cells for Europe, 4,000 for the world; with 6 parts each, 7k and 24k objects).
Inside an object, a road is a local index; an arc that leaves the cell names (neighbour slot,
local index) through a small border table. The engine adds a per-cell base from a table made
at install: on the server the bases are the global cell-order numbers, on the phone they are
compact. Results:
download level; no straddling pages (finding 5);
become possible later without a format change (finding 4);
blocks.json, cell manifests, packs,planner_grid.routingandblocks::publishgo.The directory of cells (ID, box, counts, object hashes) is one binary file: about 300 B per
cell, 1.2 MB for the world. Area selection = cells whose box meets the rectangle.
together in one block: topology; costs + turns + level-1 table of one profile group; geometry.
group as separate objects. The server takes all. The phone can skip profiles. Today 7 turn
tables and 11 cost-ID tables serve 17 profiles (measured here), so groups are real.
installed releases, narrow columns. Finding 3: durable installs. Install time at world size:
110 GB down, about 200 GB written; 30–60 min if downloads run in parallel (estimate; the disk
write rate is unmeasured).
(cells × border², with border ∝ √size), about 0.6 B/road per profile and level. The upper three
levels of 17 profiles: 30 GB at world size, 8 GB for Europe. 64 GB holds it; 32 GB holds it
for Europe, and for the world only for the popular profiles.
release that gets requests fills the page cache. Keep serving + one other installed. Until
Routing: hierarchical search and disk storage #3227 lands, the cheap interim rule is: load the rollback only on demand (files stay
installed, process starts when
release.jsonnames it as serving).of cell C", with the memory map as one implementation. WebAssembly has no map; an older iPhone
may refuse a map of many GB.
(
directory.rs:55-57already accepts this). With durable installs a restart is cheap; asbuilt it would reinstall.
(e) Open measurements
fioon the candidate server: random 4 KiB and 64 KiB reads at queue depth 1 and 32, andsequential write. Pending since EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000. It decides finding 9 and the install time.
u16costs, geometry points per road and its raw size.
download cells with identical bytes. It decides whether deltas are ever worth work.
maps.; the Cloudflare cachelimit for the plan in use.
install time for a Switzerland-size area.
cell-clustered layout.
u32margin, and every figure here).Generated by Claude Code
timohueser commentedon Nov 13, 2026
State at the end of the first build session
Merged into
develop: #3295, #3296, #3297, #3299, #3306, #3308.Merged into
routing-overlay: #3300, #3301, #3302, #3304, #3307, and a partial step of #3381 (pull request #3387).routing-overlayalso holdsdevelopup toa4fd2ae34(pull request #3444), because the clippy of Rust 1.100 failed each pull request into it.Open pull request: #3326 (#3298, into
develop). Its review is clean and CI is green. It waits for the check on the real reference archive, or for the word to merge without it.Not started: #3303 (it can start now), #3305 (after #3303; #3304 is in), #3309, #3310, #3311, and the next step of #3381.
Each finished sub-issue has a "Built differently" section. The later issue texts do not know those changes, so read the sections before a build.
Open decisions
dirtarget?Open checks that need the owner's machines
journalctl,vm.max_map_count, the data limit,fio).obc data update local. Route package format 10: the contract, the writer and the installer #3301: the Python release steps against the index kindrouting-cells.Requirements:line checked: the agent token of the verification console was absent.Archive: the branch
claude/overlay-handover(folderhandover/) holds the notes of the session: the rules that each agent read, the container setup, the bake commands and baselines, two gate programs that are not committed tests, and eachresult.json. Never merge it; delete it when the epic is done.Generated by Claude Code
timohueser commentedon Nov 13, 2026
State at the end of the second build session
Merged into
routing-overlayin this session: #3303 (pull request #3466), #3305 (#3468), #3309 (#3472), and the tools of #3310 (#3473, a partial step).routing-overlayis atdda6f1a8d. It holdsdevelopup toa4fd2ae34, as before.Open pull request: #3326 (#3298, into
develop), with no change: its review is clean and CI is green. It waits for the check on the real reference archive, or for the word to merge without it.Open issues: #3310 (Plan steps 3 to 6), #3311 (not started), #3381 (the next step), #3471 (new,
Status: explored).The order from here
origin/routing-overlay, because the branch of Route bench for the Germany proof: bands, profiles, new-only, layouts, workers, JSON lines, download-level table (#3310, steps 1 and 2) #3473 is merged. They need at least 150 GB of disk.bin/compare runs/a/output/routing installs/a10 8 1 --max-km 300.data/planner.toml, in a second pull request. In it,compare::grownuses the growth rule ofinstall::area_cells.routing-overlayintodevelop, with the owner's approval.Open decisions (new in this session)
touring).Region::snapof Route engine: the data layer on format 10 and the host interface #3302 decodes each road of the snap window on each request. Long routes are 25 to 40 times faster. Does the snap need work before the merge intodevelop?routing/package.jsonandrouting/directory.binon any network, before the user allows mobile data: about 3 to 19.5 MB for a world package. The issue asks for this, and the contract now states it. Should it wait for the consent?handover/tools/bake_layers.pyof the archive branch, notobc data update, becausecompareneeds the packages as plain folders.Open decisions (from the first session, with no change)
dirtarget?Open checks that need the owner's machines
obc data update localandobc data serve localwith the web planner, and the phone against the local follower. Phone: an offline area of whole cells, installed with the same installer #3309: the comparison with format 9 on the Central Switzerland target, and the four iPhone steps. Each list is under "Owner steps" in its pull request.Requirements:line checked: the agent token of the verification console was absent.Archive: the branch
claude/optimistic-gates-p0w0bcholds the archive of the first session (handover/) and the notes of this one (handover/session-2/): the container setup, the new Switzerland baseline with its hashes, the scripts. Never merge it; delete it withclaude/overlay-handoverwhen the epic is done.Generated by Claude Code
timohueser commentedon Nov 15, 2026
Owner decisions of 2026-11-15
The owner answered the open decisions of the two state comments in the build session.
developfirst; it merges when CI is green.developis not decided.Generated by Claude Code