Repository navigation
Description
Status: done
Part of #3227.
Depends on: #3305
TL;DR
Goal: On Germany, measurements show that the bake fits 16 GB, that its stages that read work files slow by at most 2 times when the page cache holds a quarter of the work files, and that the new engine gives the route costs of the old engine, answers each long leg across Germany in less than 1 s with warm files, and holds less than 1 GB of its own memory for each worker. The level sizes and the download level come from these measurements; the owner sees the tables before the values go into data/planner.toml.
Problem: The figures of the overlay come from a prototype on Switzerland and Belgium (7.7 and 5.4 million roads, one start state, no seed costs). The level sizes of #3300 (factor 8 from 512 junctions) and the download level (#3301's default 4) have no measurement on a graph of Germany's size, and the growth of the border roads with the cell size comes from two small countries (engine review D2). Europe has work files several times the RAM of the bake machine.
Decision:
- One cloud container with 4 cores, 15 GB of RAM and at least 150 GB of disk, as the Germany runs of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 to Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 and Routing bake: the partition into nested cells, and the roads in cell order #3300, so that their stage times compare. One Germany PBF for all runs, the 94 GLO-30 tiles of its bounds, no reference archive, all 10 profiles. The owner PC does not take a Germany bake.
- Two layouts, both of factor 8, so that each reaches the world within the 8 levels of Routing bake: the partition into nested cells, and the roads in cell order #3300 and Route package format 10: the contract, the writer and the installer #3301: A from 512 junctions (Routing bake: the partition into nested cells, and the roads in cell order #3300's default), B from 256 (the "smaller level 1" of the prototype, which makes the unpacking cheaper).
- Four runs: bake A; bake B (the roads, costs and package layers again); the routes; bake C, the chosen layout in a memory cgroup of its own peak plus a quarter of its work files. The gate of C covers the stages that read work files.
- The bench is the example
compareof Route engine: the road search on format 10, and the test of the old engine against the new one #3303. Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 adds distance bands, a profile list, a mode with the new engine alone, a check of two layouts, a warm repeat of the new engine, workers, JSON lines and the table for the download level. It is not a test in CI. - Choice rules: the layout with the least time of long legs; the lowest download level whose world file count is at most 250,000.
- A failed gate names its lever. The result goes into a comment on Routing: hierarchical search and disk storage #3227 and the pull request, not into a notes file.
Rejected: - Factor 4 from 512: on Germany it has 3 top cells of 8.4 million junctions, and with the cap of 8 levels Europe would have 15 to 57 top cells and the world 50 to 190, with no level above them. So it tests no layout that the world can use.
- A bench program of its own:
comparealready does the requests and the check. A CI test: a Germany bake takes hours. - The owner PC: 16 GB and other work on it (owner rule). A 32 GB container, as Routing bake: the cost tables of each profile for each cell #3304: the gate of the epic is a machine with 16 GB.
- All 10 profiles in the engine runs: the old engine holds its graph (37.5 B for each road, about 1.8 GB on Germany's about 49 million roads [est from
pages.bin]) and each tested profile (14.5 B for each road, about 0.7 GB) in its own memory, plus up to 4 GiB of labels: about 13 GB with 10 profiles, about 9 GB with 5. The 5 profiles without a variant name (one for each activity) cover each kind of turn cost. - The old engine on layout B, or more than once on a request: its costs do not depend on the layout, and a request of 600 to 900 km takes it up to a minute. B is checked against A, new engine against new engine.
- The gate of C on the whole bake: bake A in 15 GB already has a page cache of only about 0.4 to 0.5 of its work files, and the route catalog is bound by the CPU (6,371 s on one core, PR Routing bake 4/4: work tables in files, and sorts on disk #3251), so the ratio of the whole bake says little.
- A download level bound to the default
vm.max_map_count(65,530): the server sets that limit from the file count of its installs (Follower: install format 10, and limits for memory maps #3307), so it must not set the download size of a phone area.
Systems: routing, data-registry
Contracts: none
Size: M (2 systems, about 300 changed lines, about 11 to 13 h of measurements)
Branch:routing-overlay
Facts
- The earlier Germany bake: download.openstreetmap.fr, 5.9 GB PBF, bounds 5.86 47.27 15.04 55.06, 94 GLO-30 tiles, 17 profiles, 4 cores and 15 GB: import 609 s, terrain 392 s, order and preparation 3,853 s, overlay index 184 s; work folder peak 17.8 GB;
pages.bin6.3 GB; the route catalog 6,371 s on one core at 9 to 12 GB RSS (PR Routing bake 4/4: work tables in files, and sorts on disk #3251). - Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 defines the capped run: a memory cgroup of the largest own peak plus W / 4 (W the work folder peak of the uncapped bake). Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's guard prints the own peak of each stage of the bake, and exempts only
catalogandblocks. - Route engine: the road search on format 10, and the test of the old engine against the new one #3303's
compare OLD NEW COUNT SEED [--max-km K] [--cold] [--no-announce]opens both folders withopenand a budget ofusize::MAX, goes profile by profile with COUNT requests for each, drawscompare::requests(8 kinds: 0 two points, 1 junction ends, 2 a via junction, 3 a turnaround, 4 pinned positions, 5 and 6 two points on one road, 7 alternatives up to 40 km), and checks each withcompare::check.--colddrops the new engine, callsMaps::evict(Route engine: the data layer on format 10 and the host interface #3302) and opens it again before each request.opengives format 10 for a folder withdirectory.bin, so both sides can be installs.checkcompares the positions (road:fraction) and the pieces, because two formats of one bake have the same road IDs; two layouts do not, andsnap::candidatesbreaks distance ties by road ID, so a cut at 8 candidates can keep other roads. The old search callscancelledevery 1,024 settled labels (search.rs#L177). Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305'sStatsholds the times of the last search and unpacking, not of each leg. - Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305's
Statsgives the settled labels of each level, the table values read, the roads and settled labels of the unpacking, and the times of the search and of the unpacking;compareprints them. - Routing bake: the partition into nested cells, and the roads in cell order #3300 prints the cells, the roads per cell and the border roads per cell of each level; Routing bake: the partition into nested cells, and the roads in cell order #3300 and Route package format 10: the contract, the writer and the installer #3301 allow at most 8 levels;
cell_sizesanddownload_levelare settings ofdata/planner.toml. Route package format 10: the contract, the writer and the installer #3301'scells writeprints the number of long roads and the largest long list of one download cell, and asks Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 to record both on Germany. Routing bake: the cost tables of each profile for each cell #3304 prints the table bytes of each level; its threshold of the column copy isCOLUMNS_FROM, thecolumns_fromoftables::build. - Route engine: the data layer on format 10 and the host interface #3302 refuses an install with more files than
vm.max_map_countless 4,096. Follower: install format 10, and limits for memory maps #3307 leaves the cold start of the route service on Germany to Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. - The route catalog of the bake runs on format 9 and the old engine until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 (Route engine: the road search on format 10, and the test of the old engine against the new one #3303).
Plan
-
planner/router/src/compare.rsandexamples/compare.rs(Route engine: the road search on format 10, and the test of the old engine against the new one #3303 owns them; Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 adds):requestsgetsmin_m: each later spot is at leastmin_mfromA. Withmin_mabove 0 the kinds 5, 6 and 7 are left out (one road, or at most 40 km).- Options:
--min-km K;--profiles a,b,…(else all);--new-only(NEW alone and no check, for--cold,--workersand the cold start; OLD is then not opened);--repeat-new N(NEW runs each request N times and the last run counts; OLD runs once);--layouts(OLD and NEW are installs of two layouts of one bake: the check compares, route by route, the reason, the cost and the error kind, and each position by its projected coordinate, not by road ID or pieces; a request withsnap_truncatedon either side is skipped and counted, because the cut at 8 candidates breaks ties by road ID);--workers N(with--new-only: N threads, each with its own router over one opened install, which take the requests in turn);--json FILE(one line for each request);--areas(step 2). - A line holds the profile, the kind, the points, the straight km of each leg, and for each side the outcome, the cost, the error kind, the time of
routesplusanswer::answerand the settled labels (OLD: 1,024 × the calls ofcancelled, as the prototype counted them; NEW: Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305'sStatsof the last search); with--coldalso the open time, the major faults (/proc/self/stat) andread_bytes(/proc/self/io). A thread samplesRssAnonof/proc/self/statusevery 10 ms; the summary gives the value after the open and the peak, the median, P90 and largest time for each side, and leaves out the first OLD request of each profile (it loads the profile). The Linux reads are undercfg(target_os = "linux").
-
compare --areas INSTALL, the table for the download level. For each level ℓ from 2 to the top of the install: the cells; the roads per cell (median, largest); the objects of a whole package at that level (2 + groups for each cell, plus the upper cells) and their median and largest size, from the bytes per road of each part of the download cells; the world file count (that count scaled by 10^9 / the roads of Germany) and the bytes of the worlddirectory.bin(Route package format 10: the contract, the writer and the installer #3301: 48 + 72 × (2 + groups) bytes for each record; at 250,000 files about 19.5 MB, which each phone area downloads, Phone: an offline area of whole cells, installed with the same installer #3309); and the area overhead: the installed routing bytes of an area divided by those of its own roads (the roads whose arrival junction lies in it). An area takes the level-ℓ cells whose box meets it, grown as Phone: an offline area of whole cells, installed with the same installer #3309 grows it; the box of a level-ℓ cell is the union of the boxes of its level-1 cells; long roads do not count (Route package format 10: the contract, the writer and the installer #3301 rule 2). Two kinds of area: each zoom-9 tile, and each 3 × 3 block of them, that lies wholly inside the Germany bounds and has no tile at their edge. The median and P90 of each kind. -
The runs, all under
nice, in this order. Before run 1 the builder reports the cost to the owner: about 11 to 13 h in the container (bake A about 3 h with the catalog, bake B about 2.5 h, the routes about 3.5 h, of which the old engine takes about 3 h on the long bands, the cold start a few minutes, bake C 2.5 to 4 h). Nothing that is timed runs beside another run in one container. A second container of the same size can bake B while the first bakes A, which saves about 2.5 h; the owner chooses.- Bake A.
obc data updateof a folder target with the regioneurope/germanyand--only planner/routing(Routing bake: four cached layers: source, roads, costs, package #3299),cell_sizes=[512, 4096, 32768, 262144, 2097152, 16777216, 134217728],download_level4. Records: for each layer and stage the time, the own peak (RssAnon), the RSS peak, and the page cache that the container leaves (15 GB less the RSS peak) against W; W as Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 measures it; the bytes of each layer, of format 9, of the format 10 objects and of the install; the time ofcells install(Route package format 10: the contract, the writer and the installer #3301) on 4 workers; Routing bake: the partition into nested cells, and the roads in cell order #3300's level statistics; Routing bake: the cost tables of each profile for each cell #3304's table bytes of each level; Route package format 10: the contract, the writer and the installer #3301's count of long roads and the largest long list of one download cell. - Bake B. The same with
cell_sizes=[256, 2048, 16384, 131072, 1048576, 8388608, 67108864, 536870912]. The source layer is cached. The same records. - Routes. For each band (km) 0–25, 25–75, 75–150, 150–300, 300–600, 600–900:
compare A9 A10 C 1 --min-km … --max-km … --profiles road,touring,mtb,hiking,gravel --repeat-new 2 --json …, with C = 20 for the bands up to 300 km and 10 above (A9 the format 9 package of bake A, A10 its install). Thencompare A10 B10 --layoutswith the same bands and--repeat-new 2: new engine against new engine, which checks B and gives B's warm times. Then--new-only --coldon A10 and on B10 over the bands 300–900, and--new-only --workers 1and--workers 4on A10 over the same bands. - Cold start, on the chosen install:
Maps::evict, thenplanner-service INSTALLwithROUTE_WORKERS=4: the time to/health200, then the first 20 requests of the band 300–600 one after another, each with its time, major faults andread_bytes. - Bake C. After the choice of step 4, the chosen layout again from an empty store, in a memory cgroup of the largest own peak of its uncapped bake plus W / 4, with
OBC_DATA_MEMORY_BYTESas Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's capped run sets it unless Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 makes the sort run read the cgroup. The time of each stage against the uncapped bake (for B, its source stages against bake A).
- Bake A.
-
The layout. For each layout: the sum over the bands 300–600 and 600–900 of the median warm time of the new engine over the 5 profiles. The layout with the lower sum wins when it is at least 10 % lower; else the one with fewer table bytes for each road. A layout that fails a gate loses. Reason: the epic's goal is the time of long legs, and the tables are about 33 of about 170 installed bytes for each road (3.3 for each profile). The pull request also records, for each layout, the fit of log(median border roads) against log(median junctions) over the levels 2 to the second highest.
-
The download level. From the table of step 2 for the chosen layout: the lowest level whose world file count is at most 250,000. A lower level gives a smaller area overhead on the phone (Phone: an offline area of whole cells, installed with the same installer #3309), and Follower: install format 10, and limits for memory maps #3307 sets
vm.max_map_countof the server from the file count of its installs. The builder writes nothing intodata/planner.tomlbefore the owner has seen the tables of steps 2 and 4 and agreed, or chosen other values. -
data/planner.toml,[routing]:cell_sizesanddownload_levelget the values, each with a one-line comment: chosen on a Germany bake withcompare; the layout by the time of long legs, the download level by the area bytes on the phone. With the new values, a Switzerland bake on the owner PC underniceandcompare OLD NEW 48 1 --max-km 40(Route engine: the road search on format 10, and the test of the old engine against the new one #3303's gate) report no difference. -
When a gate fails. The pull request does not merge before the owner decides. The builder writes the gate, the numbers and the lever of this table as a comment on Routing: hierarchical search and disk storage #3227; the owner names the sub-issue that takes it.
Files
planner/router/src/compare.rs,planner/router/examples/compare.rs: change:min_m, the options, the check of--layouts, the JSON lines, the memory samples,--areas.data/planner.toml: change:cell_sizes,download_level.
Done when
obc test -p planner-router,obc test -p planner-router-build(Route engine: the road search on format 10, and the test of the old engine against the new one #3303's testenginesusescompare.rs), andobc exec cargo clippy -p <crate> --all-targets -- -D warningsfor both.cargo fmt --all.- Gates of the epic, in the container of the Decision:
- Bake A finishes, with an own peak below 15 GB.
- In bake C, each stage that the guard of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 prints, except
catalogandblocks, takes at most 2 times its uncapped time; among them Route package format 10: the contract, the writer and the installer #3301'scells::write, which reads both work layers and stays after Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. The pull request records the page cache of bake A against W for each of them. - On each request and profile,
compare A9 A10reports no difference, andcompare A10 B10 --layoutsnone beside the skipped requests, whose count the pull request records. - With the chosen layout, each warm request of the kinds 0, 1 and 4 (one leg each) in the band 600–900 takes less than 1 s. The kinds 2 and 3 have two or three legs; their times are recorded. The pull request records the cold times and the cold start.
- With 4 workers, (peak − idle
RssAnon) / 4 is less than 1 GB.
- The pull request records the PBF (source, date, SHA-256), the records of step 3, the tables of steps 2 and 4 with the chosen values and the owner's answer, and the linear estimate for Europe (300 million roads): the bake time, W, the installed bytes and the file count.
- The comment on Routing: hierarchical search and disk storage #3227 holds the same tables and the result of each gate.
- The pull request has
Requirements:(the route requirements for speed and exact costs thatobc reqlists) and says that public docs did not change.
Out of scope
- A change that a failed gate calls for: the sub-issue of the table in step 7.
- The route catalog on format 10: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. The Europe bake and the server test: workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000. The install of the follower and its map limit: Follower: install format 10, and limits for memory maps #3307.
- The deletion of the old engine: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
Progress
Pull request #3473 merged the tools of Plan steps 1 and 2 into routing-overlay. It is a partial step: this issue stays open.
- Done: the options of
compare(--min-km,--profiles,--new-only,--repeat-new,--layouts,--workers,--json,--areas), with two tests inplanner-router-build. - Built differently:
--layoutsmoves each pin to the candidate at the same coordinate (compare::repin), and each side costs the roads of its own route on its own data. The settled labels of OLD are the exact count.--profilesreplaces--profile. With--cold, the NEW columns are those of the warm route. In the--areastable each road has the same installed bytes, and a cell above the level has 1 + groups objects. - Proof on Switzerland (4 cores, 15 GB RAM): old against new gives 0 differences on 150 requests of two bands. Layout A against layout B (from 256 junctions) gives 0 differences and 0 skipped requests. Each of 4 workers holds 10.1 MB of own memory.
--areason layout A: 162,066 world files at level 3 and 20,452 at level 4; the median overhead of a zoom-9 tile is 3.48 at level 3 and 12.81 at level 4. - Next: the Germany runs of Plan step 3, on the owner's 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 branchclaude/3310-germany-benchis merged. The bakes run withhandover/tools/bake_layers.pyof the archive branchclaude/overlay-handover, not withobc data update, becausecompareneeds the packages as plain folders. - Then: 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::grownuses the growth rule ofinstall::area_cells(Phone: an offline area of whole cells, installed with the same installer #3309) in place of its own copy.
Built differently
Pull requests #3473 (the tools, see "Progress") and #3490 (the values) built this design, into routing-overlay, with these changes:
-
The Germany runs did not run. The owner deferred them on 2026-11-15: no machine for them. Plan step 3, the capped bake and each Germany gate of "Done when" move to the first bake of that size, with workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000. Not proven: the bake in 16 GB at the size of Germany, the gate of the capped page cache, a sixth level, legs above 273 km, the cold start on a real disk.
-
The choice rests on Switzerland (the bake of
routing-overlayat67320e4, 4 cores, 15 GB RAM). The layout stays A (cell_sizesfrom 512): layout B (from 256) has a median of 46.0 ms against 51.5 ms on legs of 150 to 229 km, which is not clearly 10 % lower, and it has twice the files. -
download_levelis 3 (it was 4). The owner's rule: a large offline area must not grow against today's format; a very small area may grow. The routing bytes of a phone area, download and installed, in MB:Area Format 9 Level 2 Level 3 Level 4 Uri tile, 0.15 M own roads 30.1 / 30.6 29.4 / 45.9 57.0 / 92.8 166.0 / 275.7 Valais tile, 0.09 M own roads 18.4 / 18.7 16.3 / 24.4 34.3 / 52.9 150.7 / 247.9 Zurich tile, 1.34 M own roads 130.3 / 131.9 127.0 / 222.7 173.7 / 305.4 296.9 / 527.6 3 × 3 tiles in the Alps, 1.74 M own roads 222.1 / 224.8 180.0 / 293.4 225.8 / 377.1 334.6 / 581.3 Whole bounds 740.7 / 748.9 608.7 / 1,043.3 598.7 / 1,035.5 593.1 / 1,055.1 Format 9 is measured with the selection code of
developon theblocksoutput of the same bake. At level 3 the package has 1,169 objects and adirectory.binof 99,280 B; the world estimate is 162,066 files and a directory of 12.8 MB. Level 2 gives the download of format 9, but its world estimate is 1,345,325 files and a directory of 106.5 MB, above the limit of 250,000 files. -
The installed bytes grow at each level, 1.4 to 1.7 times for a large area: the installed files are not compressed. The owner's answer on this is open.
-
The gates on the level 3 install:
compare OLD NEW 48 1 --max-km 40gives 480 requests, 0 differences, 42 ties;compare OLD NEW 24 1 --max-km 300gives 240 requests, 0 differences, 49 ties. -
What a tie is, measured on the 49 ties: the roads that only one of the two routes uses have a median of 197 m and at most 4.0 km; the two lines are a median of 21 m apart; the total length differs by a median of 9 m and at most 666 m. No tie lies within 1 km of a leg end.
-
A phone area against the full install (the 3 × 3 block at level 3, 102 requests inside it, 3 profiles): 98 give the same route, 3 find no path on both, 1 has a higher cost on the phone because the route of the full install leaves the area. No tie, and no lower cost on the phone.
-
install::grownis the one rule that grows an area by the snap window;install::area_cellsand the table ofcompare --areascall it. -
Open: the
Requirements:line of both pull requests is not checked (the verification token was absent).
Activity
Route bench: the box of an area in one line (#3310 plan step 2)
Route bench: --layouts pins the candidate at the coordinate of the pi…
Route bench: --layouts costs the unpacked roads of each side; the TOD…
Route bench: a cold line counts the warm route only; a panic ends the…
Route bench: tests of two layouts and of the table for the download l…
Route bench: the layouts test counts the compared requests and checks…
Merge pull request #3473 from timohueser/claude/3310-germany-bench
refactor(router): one rule grows an area by the snap window (#3310 Pl…
fix(planner): the real reason for the layout, `install::grown` crate-…