Repository navigation
Description
Status: done
Part of #3227.
Depends on: #3296
TL;DR
Goal: The bake computes all profiles on all cores with the same bytes for any thread count, sizes its sorts and passes by the memory that it really has, and stops at once when its own memory passes the budget of 4 GiB that the owner set for the routing bake in #3228; no table in its own memory grows with the region, apart from the stated exceptions.
Problem: The bake runs on one thread, apart from the route catalog. The profiles run one after the other: with 17 profiles they took 77 % of the Germany bake, 227 s each [measured, #3251]. About 28 B for each road stay in the bake's own memory, about 9 GB for Europe [est, bake.md finding 3], and nothing enforces the budget. The sort run ignores the cgroup limit and the free memory, so a capped bake thrashes.
Decision:
rayonover fixed chunks of 65,536 ways or roads. Each chunk writes its own range of each output column, so the bytes do not depend on the thread count. Three parallel passes: the way bases of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 (one dictionary for each chunk, joined in chunk order), the roads (total cost of each road and turn cost of each arc for a group of profiles), and the connectivity with the landmarks (one job for each profile, n jobs at once).- The package dictionary of cost bases gets its IDs in one sequential pass for each profile, in profile order and road order: the IDs of today. The writer of the package stays sequential and in profile order.
- The page budget: the smaller of the cgroup limit less the cgroup's anonymous memory,
MemAvailable, andOBC_DATA_MEMORY_BYTESless the ownRssAnon, read once at the start. The first two already leave out the own memory. It sets the sort run (a quarter of it, at most 4 GiB), the bucket size of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296, the profile group and n. It changes the speed, never the bytes. - The own memory leaves: the closure IDs of each road, the search stacks, the component sizes and snap words, the snap directory and the overlay memberships become work columns or streams. The doubts are columns since Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295. The manifest and the index of the package writer stay until format 10 (Route package format 10: the contract, the writer and the installer #3301).
- A guard samples
RssAnonevery 100 ms and ends the bake at the first sample above 4 GiB (the budget of Routing bake: bake a continent in bounded memory #3228), with the name of the stage. The route catalog and the blocks are exempt until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 and Route package format 10: the contract, the writer and the installer #3301 replace them. The partition gets a budget of its own, which Routing bake: the partition into nested cells, and the roads in cell order #3300 states (Guard::stage_within). The seam of the reference terrain gets its bound in Terrain: the seam of the reference terrain in bounded memory #3298. - Here: the cgroup reader in
obc-dataand its use in the bake. In obc data: the bake's step limits ignore the cgroup memory cap #3203: the engine'sLimits::machine, the CPU limits, and the capped bake without an OOM kill.
Rejected: - Chunks of
total / threads: the chunk dictionaries, and so the bytes before the renumber, would depend on the thread count. - One dictionary under a lock: the insert order, and so the IDs, depends on thread timing.
- Profiles in parallel, each on one core: 10 times the working set of the road pass, and no gain above 10 cores.
- The manifest as a stream: it goes with format 9, and a Europe bake of format 9 fails at the manifest limit anyway (Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295's check).
- A guard that reads the peak only at the end of a stage: a table freed before the end does not show, and a stage over the budget runs on for hours or until an OOM kill.
Systems: routing, data-engine
Contracts: none
Size: M (2 systems, no contract change, about 1,000 changed lines)
Branch:develop
Facts
- The profile loop computes the costs, the landmarks, the turns and the snap bits of one profile after the other (lib.rs#L368-L392). Inside one profile [est, bake.md finding 4]: costs about 70 s, landmarks 65 s, connectivity 30 s, turns 20 s, page writes 15 s on Germany.
- Kosaraju keeps its DFS stack and its pending list in
Vecs, up to 8 B and 4 B for each road, the component sizes in aVec, the snap words in aVec(connectivity.rs#L46, #L70-L71, #L94); the landmarks the same (landmarks.rs#L58, #L84).States::tailis a binary search overfirstfor each reverse arc (connectivity.rs#L29-L31).Junctions::preparewrites its tables while it computes them (landmarks.rs#L178-L189). Closures::buildkeeps oneu64for each road until the closures are written after the last profile (closures.rs#L87-L111, lib.rs#L353, #L395).- The snap directory keeps one map entry for each non-empty 0.01° cell until the last road list, because the pairs are sorted by latitude row first (lib.rs#L324-L340). The manifest lists each directory by key, so the write order of the objects does not change
manifest.json. - The overlay index keeps a map from each way of a route to its relations (overlays.rs#L56-L97); the overlay stage peaked at 0.67 GB of own memory on Germany [measured, Routing bake 4/4: work tables in files, and sorts on disk #3251], about 4.7 GB for Europe [est].
- The budget is read only for the sort run (work.rs#L12-L25). The engine takes three quarters of the RAM from
sysconf(runs.rs#L35-L50) and passes the free part asOBC_DATA_MEMORY_BYTES; obc data: the bake's step limits ignore the cgroup memory cap #3203 is open. - The writer appends objects to one file in call order (directory.rs#L212-L217), so each write must happen in a fixed order for the same bytes.
Plan
Cargo.toml:rayon(inCargo.lockthroughobc-dem).lib.rs:const CHUNK: usize = 65_536, 8 undercfg(test).work.rs:page_budget() -> u64, read once: min(cgroupmemory.max−anonofmemory.stat,MemAvailable,OBC_DATA_MEMORY_BYTES− ownRssAnon), each where it exists.sort_run_bytes= clamp(page budget / 4, 1 MiB, 4 GiB); Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's bucket count reads it. The step prints the budget and its source.host/obc-data/src/engine/cgroup.rs(new):memory() -> Option<Cgroup { max: Option<u64>, anon: u64 }>from/proc/self/cgroupand the cgroup v2 files, with the root as a parameter for tests. obc data: the bake's step limits ignore the cgroup memory cap #3203 reuses it inLimits::machine.cost.rs:way_basesruns over chunks of ways in parallel. Each chunk fills its rows with IDs of its ownDictionary; the chunk dictionaries are joined in chunk order, and each ID adds the offset of its chunk. A basis can then have two IDs; the renumber of step 6 joins them by value.lib.rs, road pass: for a group of g profiles, the roads run in chunks in parallel. A chunk reads each road and its shape once and writes, for each profile of the group,totals[r],bases[r](the way-bases ID) andturns[a]for the arcs of its roads, into columns of known length. g = max(1, ⌊page budget / 4 / (8 B × ways)⌋), at most the profile count: the random reads into the way bases of g profiles fit a quarter of the budget.Costing::transitionbecomes a function of the two roads and the profile, with no state.lib.rs, renumber: for each profile in order, one pass overbasesin road order inserts each basis into the packageDictionaryand writes its ID. These are the IDs of today, and the checks of today.connectivity.rs: the stack, the pending list, the component sizes and the snap words areColumns;Columngetspop. The reverse step reads the roads that arrive at the departure junction of a road, and the arc of each isfirst[that road]plus the place of the road among the departures of the junction (oneu32column for each road).reverse_arcsandtailgo; the snap bits stay the same.landmarks.rs: the stacks becomeColumns;Junctions::preparesplits intocompute(distance columns and scale) andwrite. The landmark choice does not change.lib.rs, profile jobs: one job for each profile runssnappableandJunctions::compute. n = clamp(⌊(page budget − 8 B × R − 4 B × A) / (25 B × R + 4 B × A + 45 B × J)⌋, 1, threads) jobs run at once. Then the writer, in profile order: the landmark tables,metric, then the dictionary and the closures, as today.lib.rs, closures: one pass in road order gives each set ofGraph.setsits final ID at its first use, in aVec<u32>over the distinct sets;write_closureswrites the column through that map withbase::write_column, and the set list in final order. The bake no longer callsClosures::build.lib.rs, snap directory: the cell pairs sort by (1° group, cell, road). Each group writes its road lists and then its directory when the next group starts; theBTreeMapof all groups goes.manifest.jsonstays the same;pages.binholds the objects in another fixed order.overlays.rs: the memberships become a sorted column of (way ID, relation ID) pairs, which the scan of the ways merges. The map of routes (one entry for each route relation) stays.work.rs:const OWN_BYTES: u64 = 4 << 30, the budget of the routing bake's own memory that the owner set in Routing bake: bake a continent in bounded memory #3228.Guard::start(budget)starts a thread that readsRssAnonevery 100 ms and keeps the peak of the stage. At the first sample above the budget, in a stage that is not exempt, the thread writes "stage NAME used N GiB of own memory, above the budget of 4 GiB" as the last line of standard error and ends the process with status 1, as the step contract asks for an error; the engine removes the partial directory, and outsideobc datathe work folder stays, as after a kill.Guard::stage(name)starts the next stage;Guard::exempt(name)starts a stage without the check.step.rsmarks the stages in this order:import(up to the end of walk 1),partition(from Routing bake: the partition into nested cells, and the roads in cell order #3300 on),emit(the keys, the bounds, walk 2, the turn rules andBuckets::finishwith the terrain),way-bases,road-pass,profiles(the profile jobs),writer,overlays;catalogandblocksare exempt. The step prints the peak of each stage.- Tests.
lib.rs:one_and_four_threads_give_the_same_package: the fixture oftests/routing.rswith 3 profiles inrayonpools of 1 and 4 threads gives the same bytes of each object and of the manifest.work.rs:a_sample_above_the_budget_names_the_stage(the check of one sample against a budget of 1 byte, without the exit).cgroup.rs:a_cgroup_limit_is_read_from_a_fake_tree.
Files
planner/router-build/Cargo.toml: change:rayon.planner/router-build/src/lib.rs: change: the passes, the jobs, the closures, the snap directory.planner/router-build/src/cost.rs: change: parallel way bases,transition.planner/router-build/src/connectivity.rs,landmarks.rs,column.rs: change: columns as stacks, the reverse step,computeandwrite,pop.planner/router-build/src/overlays.rs: change: the memberships.planner/router-build/src/work.rs,step.rs: change: the page budget, the guard.host/obc-data/src/engine/cgroup.rs: create.host/obc-data/src/engine.rs: change: the module.planner/router-build/README.md: change: the threads, the budget and the guard.
Done when
obc test -p planner-router-build,obc test -p planner-service,obc test -p obc-data, and clippy on these three with--all-targets -- -D warnings.- The Switzerland bake of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 gives the same SHA-256 of
manifest.json,overlays.sqliteandroute-catalog.jsonas before the change, once withRAYON_NUM_THREADS=1and once with all cores. - In a cloud container with 4 cores and 15 GB of RAM, the uncapped Germany bake of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 again: the pull request records the time and the own peak of each stage against the Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 bake. The way bases, the road pass and the profile jobs together take at most half the time of the profile stage of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296; when they do not, the pull request names the pass that holds it. Each stage that the guard checks has an own peak, less its fixed caches, at most 4 GiB × 45M / 300M = 0.6 GB on Germany (45M and 300M are the road counts of Germany and Europe), so that Europe stays in the budget. The fixed caches do not grow with the region: in the
emitstage 12 GLO-30 squares of 52 MB and 256 archive tiles of 4 MiB (1.6 GiB), and the seam cache of Terrain: the seam of the reference terrain in bounded memory #3298. A stage above it is reported with its largest table.
Out of scope
- The manifest, the index of the writer and the block publisher: Route package format 10: the contract, the writer and the installer #3301. The route catalog: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. The partition, the stated exception: Routing bake: the partition into nested cells, and the roads in cell order #3300.
Limits::machine, the CPU limit and the capped bake test of the engine: obc data: the bake's step limits ignore the cgroup memory cap #3203.- The seam of the reference terrain (32 KiB for each held archive tile of the bounds, about 9 GiB for all of Europe): Terrain: the seam of the reference terrain in bounded memory #3298. The Europe figures of this sub-issue hold only with Terrain: the seam of the reference terrain in bounded memory #3298.
- Landmark tuning: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 deletes them.
Built differently
Pull request #3341 built this design with these changes:
- The disk peak is higher. The work files of all profiles exist together until the writer stage; before, one profile at a time. The work folder peak of "Preparing" rises from 2,757 to 4,613 MiB on Switzerland and from 3,203 to 5,756 MiB on North Rhine-Westphalia. The bake needs about 7 GB of disk for each GB of PBF. Each profile adds 8.125 B for each road, 4 B for each turn and 24 B for each junction (the landmark tables).
- The cgroup reader walks up the tree. It takes the level with the least free memory (
memory.maxless its ownanon), so a limit on a parent slice counts. It reads cgroup v2 only; on cgroup v1 the budget does not use the cgroup. - The thread test uses a ladder graph in
lib.rswhose ways differ from chunk to chunk, with a chunk of 8 roads undercfg(test). A second test compares the costs of the chunks with the costs of each road computed alone. - A parallel pass returns the first error in chunk order, for each thread count.
- All package writes happen in a
writerstage after the passes, in the order of today. - The landmark tables are written by
Distances::write.Costingis a wrapper overroad_passfor one profile, for the tests.Closures::buildofplanner/routeris gone. The profile-job formula uses the point count of the graph as J. - Measured (4 cores, 15 GB RAM): the Switzerland bake takes 367 s (467 s before); the three passes take 27 % of the profile stage before the change, and they are 3.1 times faster on 4 threads than on 1. On North Rhine-Westphalia "Preparing" takes 110 s (265 s before), and 190 s (284 s before) in a memory cgroup of 1.42 GB.
- Germany did not run: the cloud container has 30 GB of disk. The Germany bake of "Done when" is open.
Activity