Skip to content

Routing: hierarchical search and disk storage #3227

Open
17 of 20 issues completed
Open

Description

@timohueser

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 the limit error)
    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:

  • develop has 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:

Format and engine:

Serving and phone:

Proof and merge:

What each step keeps true:

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:

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:

Done when

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

  1. 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.
  2. Server disk. fio on 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.
  3. 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.
  4. 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.rs and delete landmarks.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

  1. timohueser commented on Nov 10, 2026

    @timohueser
    OwnerAuthor

    Review of 2026-11-10: the route engine and the service

    One of three review reports on develop 9ec892f (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.md at
    9ec892f9a (origin/develop), issues #3000, #3227, #3053, #3255, and the prototype
    origin/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

    1. Confirmed: develop has no hierarchy. It runs a bidirectional search with 16-bit landmark potentials and decodes the whole graph, the cost columns and the landmark columns into Vecs. Only the bake is bounded-memory.
    2. The engine as built cannot open Europe: the manifest limit stops it at about 47–60M roads, RAM is about 16 GB for one profile and 64 GB for 17 at 300M roads, and the profile cache keeps one profile above about 25–50M roads.
    3. The multi-level overlay of Routing: hierarchical search and disk storage #3227 is the right method. CCH, CH and hub labels all fail on 17 metrics with turn costs and on partial phone selections. Do not polish the current search.
    4. After the overlay, the search is no longer the cost. Unpacking I/O and route geometry are: a cold 2,000 km leg needs about 15–20k disk reads [est] and today's geometry pages cost 0.6–2 s of CPU [est]. Routing: hierarchical search and disk storage #3227 does not design either.
    5. Routing: hierarchical search and disk storage #3227 leaves the stored overlay index, the backward table access, the phone selection unit and the lazy unpack of candidate legs unspecified. Fix these in the design before the build. Measure the disk at small block sizes and queue depth > 1 before the format is final.

    (b) How it works today

    The graph

    • A node is one directed road. Its id is the "arrival state" of that road (search.rs:85). An arc is one legal turn from road u to road v. Its weight is road_cost(v) + turn(u→v) (base.rs:219-227). All-ones in a column means "absent" (base.rs:158-183).
    • Turn restrictions are (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 as u64::MAX turn costs.
    • Road ids follow a Morton curve [EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000]. Arcs of a road are head[first[r]..first[r+1]], ascending (base.rs:119-120).

    What is in RAM (bytes per directed road)

    Data Type, where B/road Shared by
    first Vec<u32>, base.rs:199 4 [code] all workers, all profiles
    head Vec<u32>, base.rs:200 11.4 [code] same
    reverse_first Vec<u32>, base.rs:201 4 [code] same
    reverse_tail Vec<u32>, base.rs:202 11.4 [code] same
    reverse_offsets Numbers, 1 B/arc while the widest row is < 256 arcs, base.rs:203, blocks.rs:263-286 2.8 [code] same
    retained-arc bitmap Vec<u64>, blocks.rs:200 0.4 [code] same
    landmark junction mapping Arc<Vec<u32>>, landmarks.rs:115 4 [code] same
    closure set ids Numbers, 1–2 B, closures.rs:75, data.rs:492 1–2 [code] same
    Topology and shared, sum 39–40
    road costs of one profile Numbers, one width for the whole column (base.rs:76-88): 4 B as soon as one road costs ≥ 65,535 2 or 4 [code] workers
    turn costs Arc<Numbers>, 1 or 2 B/arc; one copy per group of profiles with identical stored tables (data.rs:116-129, :380-386) 2.8 or 5.7 per group [code] workers, profiles of the group
    landmark columns of one profile 6 × Vec<u16> over the junctions (landmarks.rs:148, router-build/src/landmarks.rs:8) 4.8 [code] workers
    One profile, sum 8.8–14.5 [code]; 10.2 average over 17 [#3000: 174 B for all]
    label directory, per worker 2 × Vec<Vec<LabelBlock>>, 24 B per 512 roads per side (search.rs:19-22) 0.094 [code] nobody
    label blocks, per worker 6,656 B per touched 512-road block per side = 13 B per label slot (search.rs:12-16) on demand nobody
    • The memory estimate reserves the full label table for each router: 26.1 B/road (search.rs:72-77, data.rs:259-261). This is accounting, not allocation.
    • A queue entry is (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 is Option<Entry>, which front, top and pop return. One size_of assertion settles it.
    • Per worker besides labels: two radix queues (129 buckets each), a 32 MiB geometry cache with FIFO eviction (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).
    • Shared between workers: the manifest, Ids, the snap map, the Union graph, the junction mapping, the closures, and one cache of prepared profiles behind one mutex (data.rs:76-94). Each profile is loaded once under the loading lock (data.rs:525-533).

    Selections, blocks, unions

    • Selection is the only RoutingData. whole covers a complete package; open/new cover a grid selection from blocks.json (data.rs:147-175).
    • Ids holds sorted source ranges. A local id is the position in their concatenation. local and source are binary searches over the ranges (blocks.rs:78-88).
    • Union::open walks every selected road, reads its row of first and head from 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::costs decodes the full road-cost column and the full turn column of a profile, and then checks every arc (blocks.rs:293-324). Selection::load adds the landmark columns (data.rs:377-403). Junctions::read remaps the junctions (landmarks.rs:121-141).
    • A page read is: digest string → binary search in the mapped 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

    1. HTTP: a semaphore permit within 1 s or 503 busy (http.rs:90-92); spawn_blocking; pop a router from a Mutex<Vec> (LIFO); respond starts the 15 s deadline after the wait (lib.rs:35-38).
    2. routes → primary: returns the cached last route of this router when the request differs only in the alternatives flags (router.rs:171-179).
    3. Snap each point (router.rs:211-258): read the road list of each 0.01° cell in the window, test the allowed bit, 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.
    4. Leg program (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).
    5. 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 the ceiling.
    6. Search (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 exceed 2 × best; cancel check every 1,024 pops. Path: parent arcs; the tail of a forward arc comes from a binary search over first (search.rs:254); the cost is summed again as a witness (search.rs:284-291).
    7. line (router.rs:354-442): for each road of the chosen legs, the geometry page, a cut, pace seconds per segment, totals.
    8. Alternatives (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].
    9. Answer (answer.rs): a serde_json::Value tree, then bytes, then brotli or gzip.

    (c) Findings, ranked by impact

    F1. No hierarchy: work grows with the area, and the landmarks stop helping

    F2. The whole graph and every used cost column are decoded into RAM, at open and per profile

    • Evidence: blocks.rs:203-292, :293-324; data.rs:359-403; landmarks.rs:121-141. Verified by reading.
    • Arithmetic [code, with the ratios above]:
    Directed roads Shared + 1 profile + 17 profiles Label directory, 12 workers
    300M 12 GB 14.6–16.4 GB about 64 GB 0.34 GB
    1B 40 GB 49–55 GB about 214 GB 1.1 GB

    #3000 estimates more for one profile (80–90 GB at 1B). The difference is not in the types; I did not find its source.

    • Open is O(package): about 281k index pages for 300M roads, each with SHA-256, zlib and postcard, plus a random scatter over 852M arcs for the reverse graph. One to two minutes at 300M [est]. Each cold profile repeats this for its columns under the loading lock, and the load is not cancellable, so a request for a cold profile holds a worker past its 15 s deadline.
    • Change: raw memory-mapped columns (Routing: hierarchical search and disk storage #3227). Then Union, Prepared, the profile cache and the whole budget machinery go (about 300 lines of data.rs, blocks.rs; the memory_budget_bytes argument of planner_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

    • Evidence: default_budget = costliest profile + 256 MiB (data.rs:41-50); retain keeps 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.
    • Arithmetic [code]: room for more profiles = 240 MiB + 4 B/road. A second profile costs 8.8–14.5 B/road. So two profiles fit only below 24–52M roads, three only below 10–18M. Germany (60–80M [est]) holds one. Every change of profile then reloads GBs. One alternatives call asks for two more profiles (alternatives.rs:39-46).
    • Change: none in the new design. If the present engine must serve the Germany proof bake as the baseline, give it an explicit budget for N profiles; otherwise the "today" column of the comparison measures cache thrash. Size S.

    F4. Limits in code that fail before Europe

    Limit Where Fails at
    Manifest ≤ 128 MiB package.rs:17, :176; data.rs:156; directory.rs:204 blocks.json: about 47M roads [#3000]. Whole manifest: 129 digests per 4,096 roads × 67 B = 2.1 B/road, so about 60M roads [code]
    Arc ids are u32 table.rs:10, :22; base.rs:199; label parents search.rs:14 4.29B arcs = 1.5B roads [code]. The world (2.8B arcs) fits with 34% left
    Road ids are u32 package.rs:52, :85-86 4.29B roads. Fine
    Landmarks: u16 distance, one scale per package, 6 landmarks in one component landmarks.rs:19-25; router-build/src/landmarks.rs:8, :174 Scale 18 today, about 1,400 at world size, median road cost 123 [#3000]
    Snap: > 100,000 roads in the window → Limit data.rs:464-466 Corridor probes with a 4–5 km radius in a dense city (F9)
    max_geometry = 250,000, used for three things router.rs:125, :303-306, :417, :511 Output vertices: about 3,300 km of route at 75 points/km [est from #3255: 3,200 steps on 42 km]. Witness roads: summed over all candidate searches, so a two-leg 4,000 km request with 6 or more via candidates fails [code + #3227: 19 roads/km]
    Deadline 15 s, started after the queue wait service/src/lib.rs:26, :35 A leg over about 500–900 km on a VPS [est: #3000 gives 80–250 s for 2,000 km, time ∝ distance²]
    MAX_WORKERS = 12 http.rs:31 A constant from a 2 GiB measurement on Central Switzerland [#3053]. It caps a 64 GB server too
    • Change: format 9 removes the first and fourth rows. Keep road ids u32; make arc offsets cell-relative or u64. Split max_geometry into three named limits. Size S each.

    F5. Geometry: 128 roads decoded to use one to three

    • Evidence: package.rs:297-340, geometry.rs:113-140, package.rs:225-235 (digest strings in a block of 4,096 Strings, cache scanned by string compare table.rs:85), SHA-256 on each read package.rs:276-282. Verified by reading.
    • Arithmetic: 320–550 object reads per cold 171 km route, 40–70 ms [EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 measured]. A 2,000 km leg has about 38k roads [Routing: hierarchical search and disk storage #3227 est]. With 128 roads per page that is 10–20k page decodes, 0.6–2 s of CPU [est], inside a 32 MiB FIFO cache per worker. After the overlay this is the largest part of a long request.
    • Change: geometry in cell order, one independently decodable record per road (offset column + delta-varint points + a fixed-width attribute column), memory-mapped. Decode only the roads of the route: about 150k points, 1–3 ms [est]. Verify digests at install only (Selection::verify exists). 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

    • Evidence: router.rs:290-296, :302-311. Verified by reading.
    • Arithmetic: a via point with K candidates (two directions of one road gives 2; a junction gives up to 8) costs K searches and K unpacked paths. Only one path is used.
    • Change: for the overlay engine, a search returns the cost and the packed overlay path. line unpacks 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)

    • Labels are three arrays in one 6,656-byte block (search.rs:12-16). cost, origin and parent are three calls, each through Vec<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.
    • The backward side recomputes first[tail] + offset, then reads turns[arc] and head[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::get reads the mapping and up to 4 columns per push, in i128 (landmarks.rs:191-201, search.rs:125-127).
    • The queue frees the bucket that it redistributes and grows it again from 4 entries (queue.rs:65-66, :44). The key is i128 only because of the potential.
    • Labels::reset walks 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.
    • The forward path uses a binary search over all of first for each arc (search.rs:254): 28 probes at 300M.
    • Change: none of this survives the overlay search. Carry three rules into it: one 16-byte label record, a u64 key 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 busy after 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.
    • limit answers 503 (lib.rs:100, route-api.md:206). A retry cannot succeed. Use 422. Size S, contract change.
    • The primary-route cache is per router (router.rs:146-148). Routers are popped LIFO, so it hits only at low load. With a cheap primary, delete it. Size S.
    • A cold profile load ignores the cancel flag and the deadline (data.rs:512-533). Gone with memory maps.
    • answer builds about 600k Values (about 20 MB) for a 150k-point route before it writes bytes (answer.rs:15-51) [est]. Derive Serialize on a struct. Size S. Low impact.
    • Good: the cancel-on-drop flag, the panic rebuild, LIFO router reuse, one code path for HTTP and the phone.

    F9. Alternatives

    (d) Critique of #3227

    D1. The method is right

    • Tables per profile: 3.3 B/road [Routing: hierarchical search and disk storage #3227 measured]. CCH with turns: 66 B/road per profile [Routing: hierarchical search and disk storage #3227, literature]. CH: about 40–60 B/road per profile [est], hours of preprocessing per profile and cost change. Hub labels: more again. At 17 profiles and 1B roads only the overlay fits a disk, and only its cells are self-contained for a partial selection.
    • Node = directed road makes the overlay clean. A border road is the entry state of the cell of its head and the exit of the cell of its tail. Every arc is a turn at one junction, so every arc and every restriction belongs to exactly one cell at every level. Via-way restrictions do not exist in the graph (osm.rs:204). No hole here.
    • Excluded roads give all-infinite rows and columns. Correct, a little wasteful, not worth a special case.

    D2. Top-level growth: the bytes are no problem, the work must be measured

    • Borders per cell grow ×2 per ×8 cell size (12, 25, 50, 99 [Routing: hierarchical search and disk storage #3227 measured]), exponent 1/3. Table bytes per road halve per level. Levels 4 and up are about 0.4 B/road per profile [est]: 7 GB for 17 profiles at 1B roads. That is the set that must stay in the page cache. It fits 32 GB.
    • The world needs 6–7 levels at ×8 (48 cells of 8.4M junctions, or 6 of 67M) [code arithmetic].
    • Work: each side reads nearly all rows of the sibling cells at each level. On Switzerland, level 4 settles 1,500 labels [Routing: hierarchical search and disk storage #3227 measured]; the full sibling set is 2 × 7 × 99 ≈ 1,390 [code arithmetic]. So values read ≈ 14·b² per level plus the top cells. World: about 5–6M values at exponent 1/3, about 30M at exponent 1/2 [est]. At 10–35 ns per value (prototype: 35 ns with HashMap labels [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

    • The prototype finds the row and the column of a state with two HashMaps per level, and the cell of a junction with one array per level (prototype_mld.rs:259-273, :485-493). It keeps tail and head junction per state. None of this is in the design text.
    • The backward search needs the cell of the departure junction of a state. The road number only gives the cell of the arrival junction.
    • Proposal: number the border roads first inside each level-1 cell. Store per level-1 cell one packed id whose bit fields are its cells at each level, so the level between two cells is one XOR and a leading-zeros count. Store per level and cell the sorted entries and exits; 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 all p (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].
    • Change: store the transposed matrix as well for the levels where a row is longer than a page (levels 4 and up, +0.4 B/road per profile [est]).

    D5. Do not store the reverse graph

    • Base arcs are read only in the level-1 cells that hold a seed and during unpacking. The reverse arcs of one level-1 cell (about 640 roads, 1,800 arcs) are the transpose of its forward rows. Build them at query time.
    • Why it is exact: a road is numbered in the cell of its arrival junction, and every arc into a road v is in the forward row of a road that arrives at the departure junction of v. So the forward rows of a cell hold all predecessors that the backward search needs there.
    • Saves reverse_first, reverse_tail, reverse_offsets: 18.2 of 33.9 B/road [code].

    D6. Unpacking and geometry decide the latency of long routes

    • A 2,000 km leg crosses about 2,900 level-1 cells [Routing: hierarchical search and disk storage #3227 est]. With separate columns per cell (first, head, road cost, turn cost) plus the lower-level tables and geometry, that is 15–20k reads [est]. One thread through page faults is queue depth 1: 1.5–6 s at 100–300 µs per read [est]. EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 reports about 2,800 reads/s on Contabo NVMe plans, which looks like a cap.
    • Europe with 17 profiles is about 35 GB without geometry [est: 15.4 topology + 17 × 5.3 + turn groups, B/road], so a 64 GB server holds most of it warm. The world (about 120–200 GB) does not.
    • Changes: (1) unpack lazily (F6). (2) After the overlay search, the cells of the path are known level by level; ask for all of their ranges at once (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

    • The follower unit has 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.)
    • WebAssembly has no memory map, and iOS limits the address space of an app. The engine must take each column as a byte slice from the host: a map on the server and the phone, a Vec in WebAssembly. Say so in the design; it replaces the Source trait for hot data.
    • A failed read is a SIGBUS (already accepted in directory.rs:55-57).

    D8. The phone selection must consist of whole level-1 cells

    • The text allows "only a part of a cell at its edge". A part of a level-1 cell is a scattered set of road ids, not a range. That brings back per-access id translation and fragmented columns.
    • Change: a download block lists the level-1 cells that it touches, complete. Then a selection is a short list of id ranges (today's 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.
    • Work on the phone: a search across a Switzerland-size selection runs at levels 3–4 near the edge, about 1–2M table values [est]. Fine.
    • Put the compact files and the range table in the design, not sparse files at global offsets.

    D9. Profiles, tables and cost updates

    • Tables cannot be shared between metrics: a shortest-path cost is a minimum over paths, not a linear function of the metric. The partition, the index, the topology and the turn groups are shared.
    • The road-cost columns (2–4 B × 17) are as large as the tables (3.3 B × 17). Use one width per level-1 cell (a width byte in the cell directory), not a per-value exception list. The same for table values: one width per cell matrix. A loop over one width has no branch.
    • The real lever is the count. 10 of the 17 profiles are the shorter and less-climbing variants (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".
    • Cheap extra: store each cell matrix by offset and let two profiles point at the same bytes when they are equal (mtb and mtb/technical, hiking and hiking/alpine away from mountains). The gain is [est] 5–10% and needs a measurement.
    • Cost updates: make "tables of one profile" its own bake step, keyed by the partition and the cost columns. At 1.5 s per million roads per core [Routing: hierarchical search and disk storage #3227 measured], Europe is about 7.5 minutes per profile and core. No customisation code in the engine is needed.
    • Table values are u32 with 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.
    • Drop the "at least 1 per metre" lever. route_bonus and 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

    • Seeds: the prototype tests one source state and one target state without seed costs (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 through Router::route, not state to state.
    • Via points, direction continuity, turnarounds and pins live in the leg program and do not change.
    • Alternatives: variant-profile routes need the variant tables. The geometric probes stay valid and become cheap. The penalty method is impossible with baked tables. A via-state method on the overlay (border states that both sides reach within 1.35 × best) is the clean replacement, later.

    D11. Determinism of the partition

    • The flow and the choice among the four cuts are deterministic. The sort is not safe: f64 keys from cos/sin of the platform library and sort_unstable with ties (prototype_mld.rs:185-189). Use integer direction vectors on integer coordinates and break ties by junction id.
    • The junction graph dedups parallel roads (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

    1. The measurements of (e) on a Germany-size or larger bake. They can still change the level sizes, the layout and the server.
    2. A differential test: old engine against new, through Router::route, with several candidates, via points, pins, turnarounds and all profiles. It is the exactness gate for every later step.
    3. The bake steps partition (deterministic, profile-free) and tables (per profile), and format 9 with the index of D3, whole-cell selections (D8), no reverse graph (D5) and geometry per road (F5).
    4. The engine on byte-slice columns: level-0 search in open cells, overlay search, lazy unpack with prefetch. Delete search.rs labels, queue.rs as it is, landmarks.rs, Union, Prepared, the budgets.
    5. Service classes and the alternatives decision.

    Anything fundamentally wrong beyond this

    • The runtime format is the distribution format. Content-addressed, compressed, hashed pages are right for publishing and wrong for serving. Routing: hierarchical search and disk storage #3227 already separates them. Agree.
    • The hand-written memory budget (about 300 lines, an FFI argument, MAX_WORKERS) exists only because data is decoded into RAM. It goes with F2. Do not port it.
    • Nothing else needs a larger restructure. The leg program, the snapping, the cost curves and the answer are sound and carry over.

    (e) Open measurements

    # Measure Why Kills or changes
    1 Border roads per cell, per level, up to cells of 8M junctions, on Germany or larger; factor ×4 and ×8 D2: the exponent 1/3 is from one mountainous and one flat small country Level count, top-level work
    2 Overlay query time with a real label store and the transposed top tables, 500–2,000 km D2, D4 Whether any goal direction is needed
    3 fio random 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 1 D6: is the cap per request or per byte Column files or one record per cell; the server choice
    4 Cold unpack of the longest route: reads, bytes, time, with and without prefetch D6 The same
    5 Page cache inside the service cgroup: resident bytes under load with the present MemoryMax D7 Unit limits
    6 Share of cell matrices that are byte-equal between profiles D9 Whether dedup is worth one indirection
    7 Which values need 32 bits per cell (road costs, tables levels 1–3) D9; #3227 open question 3 Width per cell
    8 Clean mapped pages and the iOS memory footprint on the oldest target phone; address space for the mapped files D7, D8 Map or read on the phone
    9 size_of::<Entry>() and size_of::<Option<Entry>>() (b): 32 or 48 bytes Nothing; closes a discrepancy with #3000
    10 Requests per second on the present engine for the Germany bake with an explicit budget for all tested profiles F3: otherwise the baseline measures cache thrash The "today" column of the proof

    Generated by Claude Code

  2. timohueser commented on Nov 10, 2026

    @timohueser
    OwnerAuthor

    Review of 2026-11-10: the routing bake

    One of three review reports on develop 9ec892f (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

    Region PBF Highway ways Node refs Unique nodes Directed roads R Arcs A Junctions J
    Switzerland 0.68 GB 2.16M 20.8M 17.9M 7.72M 21.9M 3.09M
    Germany 5.9 GB 16.6M 111M 87.3M about 45M [est] 128M [est] 18M [est]
    Europe 41.2 GB 116M [est] 780M [est] 610M [est] 300M (owner) 850M [est] 120M [est]
    World 80+ GB 390M [est] 2.6B [est] 2.0B [est] 1.0B (owner) 2.84B [est] 400M [est]

    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/OSM1 is a SanDisk SATA SSD (ext4), 234 GB free. There is also a 1.8 TB USB
    HDD and an NVMe root with 55 GB free.

    (a) Verdict

    1. Routing bake 1/4: one compact copy of the OSM source data #3238–Routing bake 4/4: work tables in files, and sorts on disk #3241 did what they promised, with small and correct code: anonymous memory is low on
      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]).
    2. A Europe bake with today's code does not finish. Hard stop: the manifest passes 128 MiB at about
      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.
    3. Anonymous memory is still O(region) in the preparation, the overlays and the block publisher:
      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.
    4. Everything except the catalog runs on one thread. The 17 profiles run one after the other and
      are 77 % of the Germany time without the catalog [measured Routing bake 4/4: work tables in files, and sorts on disk #3251].
    5. The fix is not a rewrite: "one order, then stream". Join nodes to ways by sort, do all tag work
      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.

    # Stage (code) Memory-mapped work files Anonymous RAM Complexity, threads Access pattern
    0 Hash the inputs (step.rs:44-57) none 1 MiB buffer O(PBF bytes), 1 thread; a third full read of the PBF sequential
    1 Import pass 1: ways and all relations (osm.rs:254-268) way builder: 8 B/way id, 8 B/ref + 8 B/way, tags 4 B + key + value per pair + 8 B/way. Europe about 21 GB. Relation builder: every relation of the file, about 3 GB about 0 O(file); reader.iter() is 1 thread and decodes the node blobs too (osm.rs:219-227) sequential append
    2 Sort ways and relations by ID (source.rs:494-502), drop relations without a highway, node or relation member (osm.rs:273-278) order column 16 B/object, sorted in runs; a second full copy of each table merge heap, 1 entry per run O(n log n), 1 thread sequential when the PBF is sorted
    3 Node references (osm.rs:304-312) refs 8 B/ref (6.2 GB), sorted in place in 4 GiB runs; needed 8 B/node (4.9 GB); shared 1 B/node about 0 O(refs log refs), 1 thread sequential
    4 Import pass 2: nodes (osm.rs:280-298) node builder 8 B id + 8 B point per kept node, tags only for tagged nodes; then order 16 B/node (9.8 GB) and a sorted copy (9.8 GB) about 0 each PBF node: binary search in needed (30 probes); 1 thread; decodes way and relation blobs too a forward sweep, because the PBF is sorted
    5 build_graph (osm.rs:339-467): attributes and country per way, restrictions, preserved relations, junction marks, way splitting, turn rules RawWay 16 B/way, twice; a full copy of the ways table (osm.rs:361); point_ids 4 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 each rules Vec 48 B/restriction; crossings HashMap about 32 B per blocking node; kept HashSet per kept relation. Germany whole import: 0.03 GB [measured #3251] O(refs × log nodes), 1 thread. Node IDs resolve by binary search in the sorted node table (source.rs:458-460), three times per way node: coordinates (osm.rs:407), junction flag (osm.rs:396), point id (osm.rs:486) random by OSM ID into nodes.ids, nodes.points, needed, shared, point_ids: 17.7 GB for Europe, 59 GB for the world
    Import total Germany RSS peak 6.33 GB Germany 609 s; Europe ≥ 71 min
    6 Terrain (terrain.rs:6-110, obc-dem planner.rs:215-266) keys 24 B/road, sorted (7.2 GB); new shape list at ≤ 20 m spacing: about 49 GB; the old shapes stay until the end 12 GLO-30 squares × 52 MB + 256 reference tiles × 4 MiB + the seam (32 KB per archive tile); 0.72 GB without reference [measured #3251] O(samples), 1 thread; both directions of a road are sampled; about 0.68 µs per sample all-in [est from #3251] random read of the old shapes (20 GB) and of 13 attribute columns (terrain.rs:47), random write into the new shapes (terrain.rs:105)
    Germany RSS peak 13.36 GB, work folder peak 17.8 GB Germany 392 s; Europe ≥ 46 min
    7 Spatial order (layout.rs:6-34, lib.rs:182-213) keys 16 B/road sorted; order and inverse 4 B/road each; a permuted copy of all 13 columns and of the shapes (62 GB), old and new together column by column about 0 O(R log R), 1 thread random gather; the shape gather reads 49 GB at random (column.rs:214-220)
    8 Preparation, shared part (lib.rs:252-367): checks, topology, snap cells, geometry pages, closures, junctions, reverse arcs first 4 B/road, head 4 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/arc groups about 150 B per non-empty 0.01° cell (lib.rs:324); geometry 88 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) O(R + A), 1 thread sequential, plus random by way ID into the way tags for the closures (lib.rs:357) and by node ID for each junction (lib.rs:343)
    9 Each profile, 17 times in sequence (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) totals 4 B/road, basis ids 4 B/road, turns 4 B/arc, Kosaraju 9 B/road, landmarks 29 B/junction: about 12 GB per profile, created and deleted 17 times DFS stacks 8 B × depth and 4 B × component (connectivity.rs:46,71, landmarks.rs:58,84); sizes 8 B per component; cycle_routes HashMap per way in a cycle route, rebuilt per profile (cost.rs:64); the manifest grows by about 90 B per page; Writer.records about 110 B per distinct object (directory.rs:215) O(R × tags) + O(A) + 8 Dijkstra over J + 2 DFS over R, 1 thread, 17 passes random by way ID into tags, node lists, node table for the country, per road per profile (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 order
    Preparation total Germany RSS peak 13.90 GB 1.26 GB on Germany [measured #3251] Germany 3,853 s (227 s per profile); Europe ≥ 7.5 h
    10 Package writer (directory.rs:213-250) pages.bin sequential, zlib level "fast" + SHA-256 per page; Germany 6.3 GB [measured], Europe about 45 GB records BTreeMap, see 9 1 thread sequential
    11 Overlay index (overlays.rs:100-178) SQLite, one transaction memberships BTreeMap per way in a route; routes JSON per relation; attributes HashMap of distinct property strings. Germany 0.67 GB [measured] O(ways + refs of kept ways), 1 thread. Germany 184 s; Europe ≥ 21 min random by node ID for each node of each feature way (overlays.rs:155) and for the country of every way (overlays.rs:131)
    12 Route catalog (catalog/mod.rs:252-448), the documented exception reads the package decoded graph + 5 profiles; points HashMap per node of a route way; all results. Germany 7.64 GB own, 12.2 GB RSS [measured #3251] 1 worker on Germany: 6,371 s. Not possible for Europe before the disk layout of #3227 random
    13 Blocks and route tiles (blocks.rs:207-314, step.rs:131-143) copies every page into packs (the package a second time) all road ids 4 B/road; all junction ids 4 B/road; objects and consumers about 250 B per object; one clone of the whole manifest per grid cell (blocks.rs:80); the whole catalog as serde_json::Value O(cells × manifest) + O(objects), 1 thread. Not measured random page reads through the package

    Short answers to the questions of point 1:

    • Node IDs to coordinates: a sorted table plus binary search, no hash map and no dense index.
    • Tags: one packed byte string per object, read by linear scan; ways and tagged nodes only.
    • Relations: all are read, then filtered twice; the preserved ones stay for costs, overlays
      and the catalog.
    • Profiles: strictly sequential. Per profile the bake keeps two u32 columns per road and one
      per arc, plus the working arrays of the two graph searches. The cost-basis dictionary is shared.
    • Spatial index: one object per 0.01° cell from a sorted (cell, road) list; the cell directory
      is a BTreeMap in RAM until the last cell.
    • Parallelism: none, except the catalog workers. No rayon in the crate.

    (c) Findings, ranked by impact

    1. Hard limit: the manifest stops a package at about 63M roads with 17 profiles

    • Evidence (verified by reading): every table lists one 64-hex digest per page of 4,096 entries
      in manifest.json (table.rs:5-28); only the geometry is two-level (lib.rs:321). A manifest
      above 128 MiB is refused (package.rs:17,176, directory.rs:204-206). prepare does not check
      the size. The first reader is the catalog (catalog/mod.rs:254), then blocks::publish
      (blocks.rs:216).
    • Arithmetic [est]: digests per 4,096 roads: topology 3.84, closures 1, landmark mapping 1, per
      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.
    • Effect: a Europe bake runs the import, the terrain and all 17 profiles (≥ 9 h), then fails
      with Limit.
    • Change: this belongs to format 9 of Routing: hierarchical search and disk storage #3227 (raw columns in cell order; the manifest names
      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

    • Evidence (verified by reading; the effect is estimated): three patterns.
      1. Lookups by OSM ID. Table::get is a binary search (source.rs:458-460). build_graph
        calls it for the country of each way (osm.rs:352), for the way filter (osm.rs:361), and
        three times for each way node (osm.rs:396,407,486). The ways arrive in way-ID order; their
        node IDs are not in that order. Working set: 17.7 GB for Europe, 59 GB for the world.
      2. Lookups by way ID in road order, 17 times. Costing::new reads the tags and the node list
        of 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.
      3. Gather by road index. The terrain reads the old shapes and writes the new ones in terrain
        order, while the roads are stored in way order (terrain.rs:26-105). spatial_order then
        gathers every column and the 49 GB shape list by a permutation (column.rs:100-103,214-220).
    • Measured hint: on Germany the RSS peak was 13.36 GB in the terrain and 13.90 GB in the
      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.
    • Arithmetic [est]: a cold page fault through mmap is one synchronous read: about 100 IOPS on
      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 SATA
      SSD 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.
    • Change (the main recommendation; size L in total, three independent parts of size M):
      1. Join nodes to ways by sort. references() sorts (node id, ref position) pairs instead
        of bare IDs. Pass 2 merges the node stream with that sorted column and emits
        (ref position, lat, lon, flags). One more sort::sorted by ref position gives a
        way_points column 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_graph then reads
        only sequential columns. Graph point ids come from one sort of the road endpoints.
        sort.rs already does both sorts. Disk: 2 × 12.5 GB for Europe, 2 × 42 GB for the world.
      2. Do all tag work in the way-order scan. The cost basis depends only on the tags, the
        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 and
        direction, 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 the
        import nothing reads graph.osm except the overlays (which then read way_points) and the
        catalog. This also parses the tags once, not 17 times.
      3. Order the roads once, in buckets. Give each road its final key at emit (Morton today, the
        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::permute on one
        bucket 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.
    • Rule to keep: random access only into a column that is at most a quarter of the RAM
      (4 B × R is 1.2 GB for Europe and 4 GB for the world: fine). Everything larger is read in order
      or sorted.
    • Risk: medium. The road and junction numbering changes once, so the manifest ID changes
      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 the
      region:

      Structure Code Size [code] Europe [est] World [est]
      Closure ids Vec<u64>, kept until the last write closures.rs:90, lib.rs:353,395 8 B/road 2.4 GB 8 GB
      Doubts lib.rs:349 1 B/road 0.3 GB 1 GB
      DFS stack and pending list of both Kosaraju runs connectivity.rs:46,71, landmarks.rs:58,84 up to 8 B/road + 4 B/road up to 3.6 GB up to 12 GB
      Manifest in RAM table.rs:9-15 about 90 B per page digest 0.8 GB 2.7 GB
      Writer.records directory.rs:215 about 110 B per distinct object 1.1 GB 3.5 GB
      Snap-cell directory groups lib.rs:324-340 about 150 B per non-empty cell 1 GB 9 GB
      Geometry page keys lib.rs:311 88 B per 128 roads 0.2 GB 0.7 GB
      Overlay memberships, routes, attributes overlays.rs:56-96,129 per route way and per distinct string 4.7 GB 15 GB
      Block publisher: road ids, junction ids, objects, consumers, manifest clones blocks.rs:80,133,218,258 8 B/road + about 250 B/object 7–8 GB 25 GB
      Seam of the reference archive obc-dem planner.rs:446-486 32 KB per archive tile near or in the coverage 1.6 GB at 1.8M km² coverage grows with coverage
    • Calibration: 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 group
      as 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 RssAnon at each
      stage end and fails when it is above the budget. Size S.

    4. One thread, and work that is repeated 17 times

    • Evidence (verified by reading; times [measured Routing bake 4/4: work tables in files, and sorts on disk #3251] and [est]): no thread in the bake
      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.
    • Needless work:
      • Costing::new copies each shape into a Vec and looks up the way and the country per road
        per profile (cost.rs:69,78-79); Country::at runs 17 × R times.
      • transition builds two full Road values, 26 column reads, per arc per profile
        (cost.rs:120, lib.rs:117-138): 850M × 17 × 26 loads for Europe. It needs to, from,
        way and access.
      • cycle_routes walks all relations again for each profile with a route bonus (cost.rs:64).
      • States::tail is a binary search over first for every reverse arc of every profile
        (connectivity.rs:29-31,85): 850M × 17 searches for Europe. A per-road offset inside its
        departure group makes the arc id a sum, and reverse_arcs (4 B/arc) goes.
      • The terrain samples each segment twice, once per direction, and each sample builds a mosaic
        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.
      • The landmarks are 8 Dijkstra runs per profile over all junctions: 136 runs, about 2.3 h for
        Europe [est]. Routing: hierarchical search and disk storage #3227 deletes them; do not tune them.
    • Change: after finding 2 the profile stage is three sequential scans (bases per way, totals
      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).
    • Target [est]: Europe in 3–4 h on the owner PC and the world in 10–13 h on 32 GB, against a
      lower bound of 9.7 h and 33 h today.

    5. No restart and no partial rebake

    • Evidence (verified by reading): the routing layer is one step with three outputs
      (obc-data-steps planner.rs:401-418). Its work files are unnamed scratch that Drop removes
      (work.rs:55-86). The engine removes partial/layer-<key>/, with TMPDIR in it, when the step
      ends, also when it fails (specs/obc-data.md:830-831, process.rs:69-71). So a crash in hour 9
      loses everything, a profile change repeats the import and the terrain, and so does a format
      bump.
    • Change: split the step into layers that the engine already keys, caches and reuses
      (Client::None layers exist). After finding 2 each stage reads and writes whole column files in
      order, so the split is natural:
      1. planner/routing/source: PBF → ways with tags and way_points, tagged nodes, relations.
        Inputs: the OSM cut, the bounds.
      2. planner/routing/roads: way scan → junction graph → partition (Routing: hierarchical search and disk storage #3227) → roads in final
        order → heights. Inputs: layer 1, GLO-30, the reference. No profile.
      3. planner/routing/costs: bases, totals, turns, snap bits, cost tables. Inputs: layers 1 and
        2, 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).
      4. 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.
    • Needs: named, persistent columns (Column::create(path) / open(path)), with a fixed byte
      layout: today a column stores Rust tuples with their padding (column.rs:22-25,68-71), which is
      fine 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.
    • Size: M after finding 2. Risk: medium (engine semantics, store disk use).

    6. Limits that are close or unchecked

    • u32 arc index (verified): first and head are u32 (base.rs:42-57), and the tables use
      u32 lengths (table.rs:10). At 2.84 arcs per road the arc count passes u32 at 1.51 billion
      roads. 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.
    • All closure sets in one object (verified; the size is not known): closures.sets is one
      page 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 distinct
      sets, the bake fails at its end.
    • Late checks: "Too many roads", "Too many road transitions", "A cost exceeds 32 bits" and the
      page budget all fire inside prepare, hours in.
    • Change: page the set table; move every count check to the end of the import. Size S.

    7. Disk: double and triple writes, needless copies, and the free space

    • Evidence (verified by reading):
      • Each growth of a column writes zeros through the page cache, then the values dirty the same
        pages again (column.rs:112-137). A work file is written about twice.
      • Lists::filled pushes 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::filled does the same for the per-profile arrays.
      • Builder::finish sorts 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 nodes
        and 21 GB for the ways of Europe. osm.ways.filter copies the ways again (osm.rs:361), and
        the relations are filtered twice.
      • permuted holds the old and the new shape list together (lib.rs:199-212).
    • Arithmetic [est]: columns created in a Europe bake: import 165 GB, terrain 59 GB, layout
      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.
    • Change: posix_fallocate instead of writing zeros (ext4 reserves the blocks and reports a
      full 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

    • Evidence (verified): sort_run_bytes is min(4 GiB, OBC_DATA_MEMORY_BYTES)
      (work.rs:12-25). The engine takes three quarters of the physical RAM from sysconf
      (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 is
      open. A run is sorted in place inside the mapping, so it needs 4 GiB of page cache to be fast.
    • Effect: in a MemoryMax scope the kernel charges the mapped file pages to the cgroup, so
      the 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.
    • Change: fix obc data: the bake's step limits ignore the cgroup memory cap #3203 in the engine. In the bake, take the run size as the minimum of the
      constant, the variable and a quarter of the memory that is really available (cgroup
      memory.max − memory.current, else MemAvailable). Size S.

    9. blocks::publish does not scale with the package

    • Evidence (verified): prepare clones the whole package manifest for the full selection and
      for every grid cell (blocks.rs:80), then keeps a few pages. With a 630 MB manifest and about
      5,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), and
      decodes each road twice (blocks.rs:45,245). The step then parses the whole catalog into a
      Value (step.rs:133-134).
    • Change: none now. Format 9 makes a cell a contiguous range, and this file is rewritten
      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

    • The seam decodes every archive tile of the bounds at open and keeps 32 KB for each
      (obc-dem planner.rs:446-486): a start-up time and a memory that grow with the national
      coverage [code]. It needs a bound before the reference covers large parts of Europe.
    • Terrain::open hashes every GLO-30 file on each bake (planner.rs:153-157), about 100 GB for
      Europe [est], although the store already knows the hashes of its objects.
    • One height call allocates a mosaic and locks a mutex per square (planner.rs:236-266). A
      "last squares" entry in Recent removes both. Size S.
    • Sampling once per undirected segment halves the terrain time and the 49 GB of shapes. Routing bake 2/4: roads as flat columns #3239
      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

    • Good (verified): every sort uses the full Ord of the record, with the row index where IDs
      repeat; no output depends on a hash-map order; Kosaraju and the landmark choice are fixed.
    • Watch 1: the dictionary takes its ids in road order (cost.rs:108). With parallel profiles or
      ranges the insert order must not decide the ids (finding 4).
    • Watch 2: lengths, piece counts and bridge heights use cos and hypot of the system libm
      (model.rs:18-24, terrain.rs:48-61,114) and are stored as rounded integers or f32. Same
      machine 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.
    • Watch 3: inertial flow (Routing: hierarchical search and disk storage #3227) is deterministic even with threads if each bisection breaks ties
      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

    • Verified: growth is sound (the old mapping drops before the file grows, &mut self excludes
      readers); 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 data the
      engine 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.
    • The terrain keeps a fixed number of squares and tiles; the visit order fits it.
    • The spatial index, the geometry pages and the topology are already sequential.
    • The step checks profiles, countries and the budget variable before the import.

    (d) What #3227 needs from the bake

    1. Partition by inertial flow. Input: junction points (8 B/junction) and one edge per
      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.
      • Alternative if the world must fit 16 GB: contract the junctions into buckets of about 512
        (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.
    2. Renumber the roads in cell order. In today's design this is not a new mechanism: the cell
      key replaces the Morton key in layout.rs, and one Roads::permute does it. But that permute
      is 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.
    3. Cost tables for 17 profiles. Per cell, per profile: a search from each entering border
      road. In cell order the inputs of a cell are contiguous ranges of totals, turns, first
      and 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.
    4. Order of work. The landmarks (136 Dijkstra runs, the 29 B/junction arrays, 41 of the 129
      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

    1. Thrash factor. Bake Germany with the page cache capped at a quarter of its work files, for
      example systemd-run --scope -p MemoryMax=5G in a cloud container, and time the import, the
      terrain and one profile. This predicts Europe on 32 GB and settles the range of finding 2.
    2. Road count of Europe. One ways-only scan of the Europe PBF: highway ways, node refs, tag
      bytes. It decides 300M against 400M and with it every disk figure here.
    3. Time split of one profile on Germany: costs, turns, landmarks, connectivity, page writes.
    4. Depth of the DFS stacks on Germany (the largest anonymous unknown of finding 3).
    5. Distinct closure sets and the raw size of closures.sets on Germany (finding 6).
    6. Manifest bytes of the Germany package (confirms the 2.1 B per road of finding 1).
    7. Peak of the work folder and total bytes written for Germany, per stage (finding 7).
    8. Anonymous peak and time of blocks::publish on Germany; Routing bake 4/4: work tables in files, and sorts on disk #3251 did not record them.
    9. Same manifest ID on the owner PC and in the cloud container for Switzerland with terrain
      (finding 11, watch 2).
    10. Spatial clustering of way IDs: the share of consecutive ways (by ID) that start in the
      same 0.01° cell. It explains how far the present code is from sequential.

    Generated by Claude Code

  3. timohueser commented on Nov 10, 2026

    @timohueser
    OwnerAuthor

    Review of 2026-11-10: the stored format, R2 and the serving path

    One of three review reports on develop 9ec892f (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:

    • code: read from the source, with file:line.
    • measured here: read in this review from the local dir target /media/timo/OSM1/local
      (planner release 04de7174…, routing package 388c436e…, Central Switzerland, the same size as
      production). Two throwaway scripts read the routing step index and the pack indexes. Nothing was
      written there.
    • #N (measured) / #N (estimated): from that issue.
    • estimate: my arithmetic, normally a linear scale of a measured figure. Expect ±40 %.

    Scale used: Europe 275M directed roads (owner: 250–300M), world 1B.

    (a) Verdict

    1. The published format is sound in its bones (immutable, hash-checked, one object pool, start
      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.
    2. As built, nothing above about 47M roads opens (blocks.json is one JSON document with a 128 MiB
      limit; 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.
    3. The Routing: hierarchical search and disk storage #3227 direction (raw memory-mapped columns in partition order) is right. It removes the heap
      graph, the load time and the three-times RAM. Go ahead with it.
    4. Its storage part has five holes: the publish unit is not named, global numbering leaves no
      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.
    5. One change closes most of them: publish one compressed object per partition cell and part,
      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

    Object Encoding Source
    Page zlib (fast) of a Postcard value; stored and decoded size ≤ 8 MiB; name = SHA-256 of the stored bytes code: planner/router/src/storage.rs:5-14
    Column page 4,096 entries of u8/u16/u32/u64, the narrowest width of the whole column; all-ones = absent code: table.rs:5, base.rs:44-56,73-106
    graph.first, graph.head u32 pages; first has roads+1 entries, head one per arc code: base.rs:122-141
    Per profile (17): road_costs, turns, costs (cost-basis IDs), allowed (1 bit per road) Column pages code: package.rs:32-41
    Cost dictionary Vec<CostBasis> pages (2,913 entries today, measured here) code: package.rs:58
    Landmarks: mapping (junction of each road) and 6 distance columns per profile i64 deltas per page code: landmarks.rs:86-111
    Geometry 128 roads per page: road attributes, shape lengths, latitude/longitude deltas, elevation bit XOR. A key table (4,096 hex digests per block) names the pages code: package.rs:18, geometry.rs:80-110
    Closures one object of distinct sets, one column of set IDs code: closures.rs:52-58
    Snap index one road-ID list per 0.01° cell; whole package: one directory object per 1° cell; grid selection: a flat map in blocks.json code: package.rs:19,247-266, router-build/src/blocks.rs:161-180
    Pack packs/<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 cells code: directory.rs:19-21, router-build/src/blocks.rs:192-202,258-296
    routing/blocks.json JSON: the package manifest (every page digest as 64 hex characters), road ranges, arc count, flat snap map, pack list. Its SHA-256 is the package identity code: router/src/blocks.rs:11-22
    offline/routing-cells/<cell>.json The same structure for one zoom 9 cell, with sparse tables (pages + blocks) code: router-build/src/blocks.rs:74-158
    Step index indexes/planner/routing/grid/index.json File entries, cell descriptors (with arc ranges), and a full copy of blocks.json under graph code: tools/planner_grid_pack.py:10-34
    routes/tiles/9-X-Y.json Route catalog records of the cell, whole record in every cell it touches specs/route-catalog.md
    overlays.sqlite, whole package routing/{manifest.json,pages.idx,pages.bin} Bake-internal only. Not client files in a grid release code: 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 under
    releases/<id>/. A routing pack costs two R2 objects.

    Road IDs and grid selections

    • Road ID = rank in a Morton order of the road's last point (code: router-build/src/layout.rs:6-19).
      Dense u32. Arc index is also a dense u32.
    • A cell selection keeps every road whose geometry meets the cell box, as sorted ranges of source
      IDs. Local ID = position in the joined ranges (code: router/src/blocks.rs:39-88).
    • At open, Union::open reads the first and head pages of the ranges, drops arcs to absent
      roads, and builds the reverse graph in heap (code: router/src/blocks.rs:203-292). Costs and
      landmark columns are decoded per profile on first use (data.rs:377-403).
    • A phone area is built by the downloads service: it merges the cell manifests of the requested
      cells in Python (tools/planner_grid.py:51-70, tools/planner_downloads.py:95-104) and writes a
      new routing/blocks.json for 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.

    Part B/road Share
    Geometry pages 53.7 42 %
    Landmark columns, 17 profiles 37.0 29 %
    Road costs, 17 profiles (1.2–1.45 each) 20.4 16 %
    Cost-basis IDs, 17 profiles (11 distinct tables) 6.0 5 %
    Turn penalties, 17 profiles (7 distinct tables; 0.14 each, road 2.4) 4.4 3 %
    graph.first + graph.head 4.2 3 %
    Snap road lists 2.3 2 %
    Geometry key table, landmark mapping, closures, allowed bits, dictionary 0.8 1 %
    All pages 128.8
    pages.idx (48 B per page) 1.7
    blocks.json 2.85

    Without 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)

    Part B/road
    Graph: first 4, head 11.2, reverse_first 4, reverse_tail 11.2, reverse_offsets 2.8 33.2
    Junction mapping 4, retained-arc bits 0.35 4.4
    One profile: road costs 4 (u32; hiking and mtb u16), turns 5.6 (u16 × 2.8), landmarks 4.9 (6 × u16 × 0.41) 14.5
    All 17 profiles: road costs 54, turns 39.2 (7 tables), landmarks 83.3 176.5
    Total, 17 profiles 214

    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

    1. obc data serve prod (the follower) polls R2 every 30 s (cli/serve_cli.rs:226-246). It wants
      up to three releases: serving, rollback, and the one of planner/next.json (serve.rs:52-59).
    2. Fetch: one thread per release downloads the objects one after another over HTTP into a pruned
      store (serve/services.rs:113-133, target.rs:333-346). It parses the step indexes on each of
      three passes (services.rs:127).
    3. Install, on the follower's poll thread (serve.rs:287-290, serve_cli.rs:272-278): each file
      under routing/, search/, offline/ is hard-linked (identity) or gunzipped (gzip) into
      serve/<target>/<planner id>/, then hashed again (services.rs:428-444).
    4. Start: three processes per release: planner-service (Rust), node server.mjs (search),
      python -m tools.planner_downloads (services.rs:86-91,173-204). Nine processes for three
      releases. They must answer within 120 s (serve.rs:26).
    5. planner-service opens blocks.json, maps each pack, builds a digest-to-pack table in heap
      (directory.rs:127-141), then loads touring before 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 a Router on a blocking thread. They share graph and
      profiles; each has its own labels and page caches. 1 s queue wait, then 503 busy.
    6. Unit limits: MemoryMax=9216M, CPUQuota=1800%, TasksMax=576 for the follower and all nine
      processes (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).
    7. Update: the new release starts beside the others; the publisher waits for
      /planner-api/releases/<id>/ready, then switches release.json. Clients move at once. No
      downtime. Memory is the sum of all loaded releases: two in steady state, three during an update.
      Rollback is instant because its processes stay loaded.
    8. Any stopped service fails the whole release: the follower drops its processes, which deletes
      the installed folder (services.rs:272-277), then installs again after a back-off. The work
      folder 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::open and the profile
    load (heap); the parse of blocks.json (heap, one String per page digest); Files::open (36 B
    per page in heap); the follower's parse of the routing step index as serde_json::Value, at least
    three 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), then
    planner_router::open(..).verify() which reads and hashes every page
    (host/obc-data-steps/src/planner/catalog.rs:176-237).

    Phone as built

    • One zoom 9 cell is about 53 km × 53 km at 47° N (2,800 km²).
    • A cell download holds: its routing packs (pages.bin + pages.idx each), two search databases,
      one route catalog file, the map packs of its box, and shared assets. The selection blocks.json
      is made by the downloads service.
    • Measured here, routing only, per cell: 2.1–54 MB, 11–25 packs (22–50 files), 133–425 B/road
      against 129 for the whole package, 56–888 ID ranges, manifest 66 KB–1.3 MB.
    • The app stores decoded objects, links them into releases/<id>/, and opens the router with
      budget 0 = the engine default (companion-ios/PlannerNative/RouteProvider.swift:22). The engine
      then 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

    • Evidence: router/src/blocks.rs:203-292, data.rs:377-403, serve.rs:1-5. Verified by reading.
    • Arithmetic (estimate from the table above): Europe 275M roads: graph 10.3 GB, with touring
      14.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.
    • Also: the default budget is "graph + costliest profile + 256 MiB" (data.rs:41-50). At Europe a
      second 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.
    • Also: load time. About 1.05B u32 values to inflate and a 770M-arc scatter for Europe: 1–1.5
      min (estimate), against the 120 s start limit (serve.rs:26). World does not start. A release
      that misses the limit reinstalls and retries for ever.
    • Change: Routing: hierarchical search and disk storage #3227 (memory maps). Size L, already planned. Risk: medium, see (d).

    2. routing/blocks.json is still one JSON document; #3141 fixed only the release manifests

    • Evidence: package.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 the
      routing grid index, stay with workstream 4". Verified by reading.
    • Arithmetic: 3,426,469 B for 1,201,625 roads = 2.85 B/road (measured here). Limit reached at 47M
      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).
    • The same bytes exist a second time inside the step index (planner_grid_pack.py:34), and
      planner_verify.py:229-230 parses both to compare them. The follower parses that index into
      serde_json::Value (services.rs:381-403): several GB of heap in the follower at Europe size.
      Three Python tools json.loads it.
    • In heap the manifest costs about 90–100 B per page digest (a String each): 0.9 GB for Europe,
      3.3 GB for the world, per service process (estimate).
    • Change: no document that lists pages. See (d): a small JSON header plus one binary cell
      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

    • Evidence: serve_cli.rs:141, services.rs:272-277, serve.rs:287-290,395-399. Verified by
      reading. EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 workstream 7 lists the effect (30 min recovery, estimated).
    • As built at Europe: each follower start (every services deploy) rehashes 35 GB and gunzips most
      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.
    • Change: install into installed/<planner id>/ with a completion marker; never delete it on a
      stop; 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

    • Evidence: layout.rs:6-19 (ID = rank in the sorted order); head pages and snap lists store
      these IDs; column pages are cut every 4,096 ranks. Verified by reading; not measured on two
      bakes.
    • Effect: one added road shifts every ID after it. All later column pages, all head pages and
      all 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).
    • The Routing: hierarchical search and disk storage #3227 numbering (cell order) has the same property.
    • Does it matter? Not for cost: a full Europe upload is 35 GB, about 1 h at the 10 MiB/s that
      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).
    • Change: do not build delta machinery now. Do make IDs cell-relative in the published bytes
      ((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

    • Evidence: router-build/src/blocks.rs:258-296. Measured here.
    • A 4,096-entry page holds roads of several zoom 9 cells, and a cell download takes whole pages.
      One cell costs 1.03–3.3 times its own bytes. The nine cells together download 209 MB for 155 MB
      of pages.
    • Packs are keyed by the exact consumer set. Nine cells give 50 packs: 12 with one consumer, 15
      with two, 13 with three, 10 with four to nine. 30 of 50 are under 1 MB, 9 under 50 KB.
    • publish clones the full manifest for each cell (blocks.rs:80) and keeps every cell
      selection and a map of every page in RAM until the end (blocks.rs:221,258). Estimate for
      Europe (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.
    • Change: the download unit is a partition cell ((d) point 2). Then no page straddles a unit and
      blocks::publish, the packs, the consumer sets and the cell manifests go. Size: part of the
      Routing: hierarchical search and disk storage #3227 format. Risk: low.

    6. Disk: three releases of raw columns do not fit 1 TB at world size

    • As built, per release (estimate from measured): 129 B/road of objects, and a second, decoded
      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).
    • With Routing: hierarchical search and disk storage #3227 as written (estimate): raw columns 177 B/road (graph 33.2, road costs 54, turns
      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.
    • Change: (1) delete transport objects once the install is verified; (2) keep two installed
      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), u16 costs with exceptions, head as cell-local
      u16. Size M. Risk: low.

    7. The systemd memory limit caps the page cache

    • Evidence: tools/vps/obc-data-serve.service:20. Verified by reading. cgroup v2 charges file
      pages to the unit that reads them.
    • Effect: with memory-mapped columns the unit can hold at most 9 GB of page cache, whatever the
      server has. Its comment still derives the figure from the legacy units, and it is larger than
      the RAM of the present VPS.
    • Change: with Routing: hierarchical search and disk storage #3227, set MemoryHigh/MemoryMax near the RAM of the server and put a small
      hard limit only on the anonymous memory of each service (labels, queues). Size S. Risk: low.

    8. Routing packs are gzipped a second time

    • Evidence: tools/planner_offline.py:12,31: the "already compressed" test reads the suffix of
      the source path, and a step receives store object paths without a suffix
      (host/obc-data/src/store.rs:185). Measured here: 36 of 50 pages.bin have gzip transport,
      149.81 MB to 149.05 MB (0.5 %).
    • Effect: the follower cannot hard-link them, so it holds a second copy (services.rs:435) and
      inflates it at each install. The phone inflates them too.
    • Change: test the suffix of the logical name. Size S. Risk: none. Moot once packs go.

    9. Cold reads on a rate-limited disk: per-column files are the wrong layout

    • From Routing: hierarchical search and disk storage #3227 (measured): a long route unpacks 1.4 level-1 cells per km; a 2,000 km leg touches
      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).
    • Estimate: with one file per column, a cold level-1 cell costs one read for each of 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.
    • Change: cluster by level-1 cell. One block per cell for the topology, one per cell and profile
      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 parallel
      pread). Size: a layout decision inside Routing: hierarchical search and disk storage #3227. Risk: low.

    10. The arc index is a u32

    • Evidence: router/src/blocks.rs:19, table.rs:10,22. 2.80 arcs per road (measured here).
    • World: 2.8B arcs at 1B roads; 4.29B is the limit. A world of 1.5B roads does not fit
      (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

    • Evidence: catalog.rs:143-237 (Rust checks object sizes and hashes, runs
      tools.planner_verify, then planner_router::open().verify()), planner_verify.py:221
      (materialize and hash), planner_offline.py:24-44 (two hashes per packed file).
    • Estimate: Europe 35 GB × 5 passes; 20–30 min on the bake disk. Tolerable, but the Python
      verifier re-implements the Rust installer (planner_offline.materialize against
      services.rs:materialize).
    • Change: one Rust verifier for routing that hashes each object once. Size M. Risk: low.

    12. Phone limits as built

    • Heap graph: 37.5 + 14.5 B/road for one profile (code). Switzerland (7.7M roads): 0.4 GB, 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.
    • Budget 0 selects "whatever the data needs" (data.rs:41-44), so a large area ends in an iOS
      kill, not in limit.
    • Junctions::read allocates 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.
    • The selection manifest has the same 128 MiB limit: about 45M roads per area.

    13. Smaller items

    • Route catalog: a region with France and another country has no catalog
      (specs/route-catalog.md), and each record is stored whole in every cell it touches.
    • Files::open holds 36 B per page in heap: 0.36 GB Europe, 1.3 GB world (estimate).
    • specs/planner-release.md:56-58 still says routing/ holds the three package files and
      overlays.sqlite. In a grid release it holds blocks.json and packs.

    Good as it is

    Unused or duplicated

    What Where
    Two layouts of the same pages on the bake machine: routing/pages.bin 155.2 MB and blocks/packs/ 156.9 MB (measured here) router-build/src/step.rs
    The whole-package reader path (Selection::whole, Snap::Directory, 1° snap directories): only bake-internal steps and tests use it data.rs:147-152, package.rs:247-274
    blocks.json twice (file and step index), compared by JSON equality planner_grid_pack.py:34, planner_verify.py:229
    Cell routing metadata in three places: offline/routing-cells/, cells of the step index, routing in offline/cells/ planner_grid_pack.py:21-31, planner_grid_offline.py:39
    Selection logic twice: Rust blocks::prepare and Python planner_grid.routing / merge / ranges / cells tools/planner_grid.py
    Installer twice: Python materialize and Rust materialize planner_offline.py:47, services.rs:428
    Three verifiers finding 11
    Page digest indirection: pages.idx per pack plus a global digest-to-pack table directory.rs:119-158
    At least ten format numbers for one release (manifest 8, OBCRIDX3, blocks 2, grid 3, public grid 4, index 4, offline 3, selection 6, bundle 1, release 2) specs
    Legacy: legacy() treats cell-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 bucket r2.rs:451-454

    (d) The #3227 storage direction

    Judgement against the alternatives.

    • Raw mapped columns, page cache only (chosen). Right for the hot data. No decode, no cache
      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)).
    • Compressed pages with a bounded cache. Half the disk, and per-page integrity. But it needs a
      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).
    • Publish raw, let HTTP compress. R2 stores bytes as given and Cloudflare does not compress
      large binary objects. Raw upload doubles the phone download. No.
    • One big file per column with range reads. Good for the server, bad for the phone: an area is
      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.

    1. The publish unit is not named. "Written at install from the published compressed objects"
      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 --verify scrub re-reads on demand. Per-read
      hashing goes.
    2. Numbering. Make the download unit one overlay level (for example the level near 250k roads:
      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:
      • the phone downloads whole cells and runs the same install code; no partial cell at the
        download level; no straddling pages (finding 5);
      • no global arc index (finding 10);
      • an unchanged cell has unchanged bytes if the partition is kept between refreshes, so deltas
        become possible later without a format change (finding 4);
      • blocks.json, cell manifests, packs, planner_grid.routing and blocks::publish go.
        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.
    3. Layout on disk. Cluster by level-1 cell, not by column (finding 9). Keep parts that are read
      together in one block: topology; costs + turns + level-1 table of one profile group; geometry.
    4. Parts by profile group. Publish static parts (topology, geometry, snap) and each profile
      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.
    5. Disk and install. Finding 6: delete transport objects after a verified install, keep two
      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).
    6. Page cache. Finding 7. Hot set estimate: each overlay level holds about the same table bytes
      (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.
    7. Release switch with one hot copy. With maps, every release process can stay up: only the
      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.json names it as serving).
    8. WebAssembly and iOS address space. Write the engine against "give me bytes [a, b) of part P
      of cell C", with the memory map as one implementation. WebAssembly has no map; an older iPhone
      may refuse a map of many GB.
    9. Failure mode. A read error on a map is SIGBUS for the whole process
      (directory.rs:55-57 already accepts this). With durable installs a restart is cheap; as
      built it would reinstall.

    (e) Open measurements

    1. fio on the candidate server: random 4 KiB and 64 KiB reads at queue depth 1 and 32, and
      sequential 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.
    2. Raw B/road per column on the Germany-size bake: exceptions per arc for turns, share of u16
      costs, geometry points per road and its raw size.
    3. Partition stability: bake two OSM snapshots one week apart with the old partition kept; count
      download cells with identical bytes. It decides whether deltas are ever worth work.
    4. Cold whole-object and range reads of 50–500 MB objects through maps.; the Cloudflare cache
      limit for the plan in use.
    5. iPhone 13: the largest total map the app can hold; memory pressure with several GB mapped;
      install time for a Switzerland-size area.
    6. Cold read count of a 300 km and a 2,000 km route in the prototype, column layout against
      cell-clustered layout.
    7. Real road and arc counts for Europe and the world (the u32 margin, and every figure here).
    8. Follower restart time at Germany size before and after durable installs.
    9. If any interim bake uses today's format: packs per cell on a grid of a few hundred cells.

    Generated by Claude Code

  4. added sub-issues on Nov 11, 2026
  5. timohueser commented on Nov 13, 2026

    @timohueser
    OwnerAuthor

    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-overlay also holds develop up to a4fd2ae34 (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

    Open checks that need the owner's machines

    Archive: the branch claude/overlay-handover (folder handover/) 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 each result.json. Never merge it; delete it when the epic is done.


    Generated by Claude Code

  6. timohueser commented on Nov 13, 2026

    @timohueser
    OwnerAuthor

    State at the end of the second build session

    Merged into routing-overlay in this session: #3303 (pull request #3466), #3305 (#3468), #3309 (#3472), and the tools of #3310 (#3473, a partial step). routing-overlay is at dda6f1a8d. It holds develop up to a4fd2ae34, 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

    1. The owner runs the Germany runs of Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 on his machine. The commands are under "Owner steps" in pull request Route bench for the Germany proof: bands, profiles, new-only, layouts, workers, JSON lines, download-level table (#3310, steps 1 and 2) #3473. One change to them: build from 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.
    2. The same runs give the Germany points of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 (the old engine against the new one, the times of the search and of the unpacking for each band, the cold runs). One more command covers its comparison over all 10 profiles: bin/compare runs/a/output/routing installs/a10 8 1 --max-km 300.
    3. With the figures, Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 Plan steps 4 to 6: the layout, the download level with the owner's answer, data/planner.toml, in a second pull request. In it, compare::grown uses the growth rule of install::area_cells.
    4. Then Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. It deletes the old engine, so it must not merge before the comparison on Germany ran. Then the merge of routing-overlay into develop, with the owner's approval.

    Open decisions (new in this session)

    Open decisions (from the first session, with no change)

    Open checks that need the owner's machines

    Archive: the branch claude/optimistic-gates-p0w0bc holds 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 with claude/overlay-handover when the epic is done.


    Generated by Claude Code

  7. timohueser commented on Nov 15, 2026

    @timohueser
    OwnerAuthor

    Owner decisions of 2026-11-15

    The owner answered the open decisions of the two state comments in the build session.


    Generated by Claude Code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions