Repository navigation
Description
Status: done
Part of #3227.
Depends on: #3295, #3296, #3297, #3299
TL;DR
Goal: The bake divides the junctions into nested cells and numbers the junctions and the roads in cell order. Each cell of each level is then one range of junction IDs and one range of road IDs, and the bake holds the cell data that #3301, #3302, #3303 and #3304 read.
Problem: After #3296 the bake orders the roads by a Morton key of their arrival point, and after #3295 the junctions are in OSM node ID order. It has no cells. The prototype partition copies the graph of each part with a reverse arc array, keeps one junction array per thread, and sorts by floating-point keys: about 3 times the memory of the graph, and a result that can differ between machines.
Decision:
- A new module
partition.rscuts the junction graph by recursive bisection with inertial flow: four integer directions, a quarter of the part as sources and a quarter as sinks, Dinic's maximum flow, the smallest of the four cuts. The cells of a level are the largest parts of the bisection tree within the size limit of that level. - The partition holds one graph in RAM in import order and never moves an arc. A part is a range of a position array; an arc to a junction outside the part is skipped. About 48 bytes for each junction. The partition is not under Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's limit of 4 GiB: it has a budget of its own and its own check (
Guard::stage_within). - Parts run in parallel with
rayon::join. A part depends only on its own junctions, so the result is the same for each thread count. - The partition runs between Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295's two walks, on
ends. Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's order key function becomes the cell key; Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's scan ofends, buckets, emit and terrain pass stay. The roads are still ordered once. - In a level-1 cell the roads go by border level, highest first, then by arrival junction. So the entering border roads of each level are a prefix of the cell.
- A cell ID has at most 32 bits; the partition has at most 8 levels. The level sizes are the option
cell_sizesof the layerplanner/routing-roads(Routing bake: four cached layers: source, roads, costs, package #3299), indata/planner.toml. planner/router/examples/compare.rsroutes one request set on two packages and reports each different cost: the gate of this change.
Rejected:- The bucket contraction of the review (bake.md (d)1): the top cuts follow bucket borders and get 10–30 % more border roads [est], and the top level does the most query work. The exact method fits 32 GB for the world.
- A graph copy for each part (the prototype), or arcs compacted at each split: a split then needs scratch for the arcs of the part, about 16 B for each junction at the top.
- Projections with
cosof the latitude: the system libm can differ in the last bit. The keys only choose sources and sinks; the flow finds the cut. - The four directions in parallel: four times the working memory at the top split.
- Emit the roads in way order, partition, then copy them into cell order: a second copy of all roads and shapes, which the epic excludes.
- A column for the cell of each road, a list of entering border roads, a departure cell column: the ranges,
borderandfromgive them. - A library partitioner (KaHIP, METIS): a C++ dependency of the bake, and its results depend on its version.
Systems: routing, obc-data
Contracts:specs/obc-data.md(the optioncell_sizesof the routing step)
Size: M (2 systems, a compatible option, about 800 changed lines)
Branch:routing-overlay
Facts
- Before Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295, a junction gets its ID at its first use by a road (osm.rs#L485-L497). The cost code reads junction columns by junction ID (cost.rs#L127, #L143).
- Format 9 does not depend on the junction IDs: the arcs of a road are the departures of its arrival junction in road order (base.rs#L48-L60), and the landmark junctions are renumbered by arrival (landmarks.rs#L22-L38).
- Format 9 accepts any road order. The snap lists come from the geometry (lib.rs#L288-L340). A geometry page holds 128 consecutive roads with coordinate deltas across roads (lib.rs#L311-L321, geometry.rs#L139-L148), so its size depends on locality. A grid selection takes the roads that meet the tile and keeps their pages (blocks.rs#L34-L50); the phone reads it as ranges of road IDs (blocks.rs#L41-L60).
- Snapping sorts the candidates by distance, then by road ID, and keeps at most 8 (snap.rs#L38-L43). So a point where more than 8 roads have the same distance can get other candidates when the road IDs change; the answer then has
snap_truncated. - The prototype deduplicates parallel roads, sorts
f64keys withsort_unstable_by, takes max(1, ⌊n/4⌋) junctions as sources and as sinks, copies each part with a reverse arc array, and takes as the cells of a level the largest tree nodes within its size (prototype_mld.rs#L28-L38, #L57-L85, #L179-L198, #L714-L733). It measured 52 s for 3.09M junctions on 4 cores.
Plan
#3295 gives osm::split, walk 1 (osm::junctions: the junctions in OSM node ID order with points, node_ids, node_access, signals, node_closures, node_doubts, and ends, the (from, to) junction of each road in emit order), and walk 2 (osm::emit). #3296 gives the order key of each road, written in a scan of ends after walk 1 by one key function, layout::bounds (equal-count quantiles of the sorted keys), Buckets, the turn rules after the emit, and layout::order for test graphs. #3297 gives rayon, work::page_budget and work::Guard. #3299 gives the layer planner/routing-roads, which holds the partition. #3300 changes only what follows.
-
Option.
data/planner.tomlgets[routing] cell_sizes;host/obc-data-steps/src/planner.rs(Routing) passes it as the optioncell_sizesof the layerplanner/routing-roads, so it is in that layer's key: a change of the sizes makes the roads layer and the layers after it again.step::Buildgetscell_sizes: Vec<u32>: the largest number of junctions in a cell of level 1, 2, …. Until Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310:[512, 4096, 32768, 262144, 2097152, 16777216, 134217728](factor 8, level 1 of about 250 to 500 junctions, as the prototype).step::buildrejects before the import: 0 or more than 8 values, values that do not increase, a first value below 2 or at or above 2^24. The sizes are settings: a region whose IDs need more than 32 bits (step 5) removes a level. -
Junction graph.
partition::partition(points: &Column<Point>, ends: &Column<(u32, u32)>, sizes: &[u32]) -> Result<Partition, String>, called bystep::buildright after walk 1. For each road with from ≠ to, the pair (min, max) goes throughsort::sorted(…).counted(). Each distinct pair is one edge with capacity min(count, 127): the count is the number of directed roads between the two junctions in both directions, and the cap keeps the residual, at most twice the capacity, in au8. A road from a junction to itself gives no edge. The edges go to a work columnColumn<((u32, u32), u8)>. The need is 32 B × J + 6 B × A (J junctions, A = 2 × edges); when it passeswork::page_budget(), the bake fails with "The partition needs N bytes; the page budget is M". Then two passes over the edge column fill the CSR in RAM: degrees, then a scatter. Each list is sorted by neighbour.Array Index Type Bytes per junction (A ≈ 2.6 J) Meaning point,firstjunction [i32; 2],u3212 lon, lat in microdegrees; start of its arcs adj,capacity,residualarc u32,u8,AtomicU815.6 neighbour; capacity in each direction; residual of the flow at,posposition, junction u32,AtomicU328 junction at each position; position of each junction workposition in the part u32× 312 in a bisection: BFS level with two flag bits, current arc, BFS queue and the selection Sum about 48 The arrays never move. A part is a range [lo, hi) of positions; an arc whose neighbour has its
posoutside the range is skipped. Parts that run at the same time touch disjoint entries ofresidualandpos, so relaxed atomic access is enough. A read ofpos[nb]for a junction of a part that another thread works on gives a position inside that other part, before or after its split, so it is outside [lo, hi) and the skip is correct. The memory does not depend on the thread count. Estimate with J of 18M (Germany), 120–166M (Europe) and 400M (the world) from bake.md: 0.9 GB, 5.7–7.9 GB and 19 GB of RAM, and about 1 GB, 7–9 GB and 22 GB of work files (the pair sort, the edge column). Time: the epic estimates 1–2 h on 4 cores for 650M roads. -
Bisection (
partition::bisect, one part of n >sizes[0]junctions), with k = max(1, ⌊n/4⌋):- For each direction of
lon,lat,lon + lat,lon − lat(i64), the order is (key, junction ID).select_nth_unstablegives the first k junctions as sources, the last k as sinks, and the median. The set does not depend on the selection algorithm, because the order is strict. - Dinic's algorithm: a BFS from all sources over arcs with residual > 0 gives levels; an iterative DFS with the current-arc array pushes a blocking flow; the twin of an arc is a binary search in the list of its neighbour. A direction stops when its flow exceeds the smallest cut of the directions before it.
- The source side is the set that the final BFS reaches from the sources: it is the same for each maximum flow. A component of the part without a source and without a sink (an island, a junction with only a loop road) goes whole to the source side when its lowest junction ID has a key at or below the median, else to the sink side. Each side holds at least k junctions, so a part of 2 or more junctions always has a cut; a cut of 0 is valid.
- The choice: the smallest cut, then the larger smaller side, then the lower direction.
- The split: a stable partition of
at[lo..hi)(source side first) through the space ofwork, which is freed before the recursion, then the newposof each junction of the part.
- For each direction of
-
Tree and levels.
partitionsplits the whole graph, then each side withrayon::join, until a part has at mostsizes[0]junctions: a level-1 cell. The tree is a list of (lo, hi) positions; a subtree returns its list, and the parent puts the source side first. The cells of level ℓ are the largest tree nodes with at mostsizes[ℓ−1]junctions. A level above 1 exists only when it has at least 2 cells. The final junction ID is the position, so a level-1 cell has its junctions in ascending OSM node ID.Partition { order: Column<u32>(final → walk-1 ID, fromat),rank: Column<u32>(walk-1 → final, frompos),cells: Cells }; the RAM arrays are freed. One scan ofendscounts the roads of each level-1 cell (the cell ofrank[to]). -
Cell ID. The field of level ℓ has wℓ bits: the bits of (the largest number of level-ℓ cells in one level-(ℓ+1) cell − 1), and at the top level the bits of (its cell count − 1). The ID of a level-1 cell (
u32) holds, from the top field down, the place of each of its cells among its siblings, in tree order: so ascending ID is the cell order and the road order. Each side of a cut holds at least a quarter of its part, so a parent has at most 32 children. Right after the partition, the bake fails when Σ wℓ > 32, with "The cell IDs need N bits (level 1: w1, …); at most 32. Remove a level fromcell_sizes". The bits are about log2(J /sizes[0]) plus a balance slack of up to 2 bits at each level, so a larger factor removes no bits while all levels stay; one level less removes one slack. Estimate for the default sizes: Europe 25 to 31 bits, the world 26 to 34 bits. So the default sizes may not fit the world: a world bake uses[512, 4096, 32768, 262144, 16777216, 134217728](without 2097152), at most 32 bits by the same estimate. -
Key and junctions.
layout::partition_key(from, to, &Partition) -> u64, with the walk-1 IDs ofends[i], is the key function that Routing bake: the partition into nested cells, and the roads in cell order #3300 passes to Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296'slayout::keysin place oflayout::spatial_keyand its Morton range check. For each road:cell << 32 | (255 − border) << 24 | (to − first junction of the cell), withto=rank[ends[i].1],cellthe level-1 cell number ofto, andborder=Cells::border(rank[from], to): 0 in one level-1 cell, else the level whose field holds the highest set bit of the XOR of the two cell IDs (the road is a border road of levels 1 to that level). Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296'slayout::keyscalls this function in place of the spatial key; its quantilebounds,Bucketsand the tie by emit index do not change. The first key of level-1 cellcisc << 32.osm::emitpushesfromandtothroughrank; each read of a junction column beforepermute_junctions(for example Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295's node set of the arrival junction inclosures) uses the walk-1 IDends[i]. The turn rules find a via junction by Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295's binary search innode_ids, still in walk-1 order, and take it throughrank. After the rules,Graph::permute_junctions(order)permutes every junction column ofGraph(the six of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 and any that Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 adds) and checks that each has J entries.layout::orderfor test graphs takessizesand runs the same steps. -
Cell data.
Cells(partition.rs) holds these columns; they are files of the layerplanner/routing-roads(Routing bake: four cached layers: source, roads, costs, package #3299).Cells::finish(&mut self, roads: &Roads)fillsborderand the leaving lists after the order: one scan offromandto, one sort of (cell number over all levels, road). It checks that each road lies in the cell of its arrival junction.Column Type Entries Meaning level1(u32, u32)level-1 cells + 1 first junction and first road of each level-1 cell; the last entry holds the counts idsu32level-1 cells the cell ID of step 5 upperu32cells of levels 2..L, + 1 each level first level-1 cell of each cell widths,countsVec<u8>,Vec<u32>L field width and cell count of each level borderu8roads the border level of each road leaving_firstu32cells of all levels + 1 start of the leaving list of each cell, level by level leavingu32leaving roads the roads that depart in the cell and arrive outside it at its level, ascending Rules that Route package format 10: the contract, the writer and the installer #3301, Route engine: the data layer on format 10 and the host interface #3302, Route engine: the road search on format 10, and the test of the old engine against the new one #3303 and Routing bake: the cost tables of each profile for each cell #3304 cite:
- Ranges. Each cell of each level is one range of junction IDs and one range of road IDs. A road is in the cell of its arrival junction. The cell of a road or a junction is a binary search in
level1. - Entering prefix. In each level-1 cell the roads are in descending
border. The entering border roads of a level-ℓ cell are, in each of its level-1 cells in order, the first roads withborder≥ ℓ; so the list is ascending. Route package format 10: the contract, the writer and the installer #3301 derives the entering lists by this rule. - Leaving lists. Routing bake: the partition into nested cells, and the roads in cell order #3300 builds the leaving list of each cell of each level; Route package format 10: the contract, the writer and the installer #3301 reads them and does not sort again.
- Departure cell. The departure cell of an entering border road is the cell of its
from. - Cell order. The cells of each level are numbered in tree order, so ascending ID is the order of the roads. The children of a cell of level ℓ are one contiguous range of cells of level ℓ−1, found from
upper.
- Ranges. Each cell of each level is one range of junction IDs and one range of road IDs. A road is in the cell of its arrival junction. The cell of a road or a junction is a binary search in
-
Stages and statistics. Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's stage "import" ends after walk 1; then the stage "partition"; then the stage "emit" (walk 2, the turn rules,
permute_junctions,finish); then Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's later stages. The step marks the partition as a stage of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's guard with its own budget, the need of step 2 plus 256 MiB (Guard::stage_within(name, bytes), new), and prints its peakRssAnon. It prints J, A, the need, the time, a SHA-256 oforderand theCellscolumns, and for each level the number of cells, the roads per cell (median, largest), and the entering and the leaving border roads per cell (median, largest). -
Format 9 on this branch. No change to the writer or the reader; junction IDs do not reach format 9. The builder records, against the package of the branch base: the bytes of
pages.bin, of the geometry pages and of all packs, and for 5 zoom-9 tiles of Switzerland the downloaded bytes against the bytes of the tile's own pages and the number of road ranges in its selection. Production keeps the format 9 ofdevelop, so a growth only goes into the report; Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 times the old engine on this order. -
Comparison.
planner/router/examples/compare.rs:compare OLD NEW COUNT SEED. It opens both packages withplanner_router::openand fails with exit 2 when their profile names differ. A xorshift64 from SEED takes COUNT pairs of road IDs of OLD; a request point is the point at half the length of its road's shape; a pair more than 75 km apart is drawn again. For each profile, one at a time, it routes each request on both packages (Router::routes, default budget). A request withsnap_truncatedin either answer is skipped and counted: more than 8 candidates at one distance are cut by road ID, which this change renumbers. For each other request whoseRoute::costor error kind differs, it printsprofile, points, old cost or error kind, new cost or error kind. It ends withN requests, S skipped, D differencesand exits with 1 when D > 0. -
Tests.
partition.rs:a_grid_is_cut_at_its_minimum_into_nested_ranges: a 40 × 40 grid with two roads on each edge, and an island of 3 junctions at column 12.5 and row 20.5 with no road to the grid (it holds no source and no sink); sizes [16, 64, 256]; the top cut is 80 roads, its source side is columns 0 to 9 and the island (theloncut wins on balance), and each cell of each level is one range and within its size.one_and_four_threads_give_the_same_cells: the same input plus parallel roads and a junction of degree 60, inrayonpools of 1 and 4 threads;orderand everyCellscolumn are equal.a_part_of_three_junctions_splits: sizes [2].tests/routing.rs:prepared_coordinate_routes_match_independent_arrival_road_searchcallslayout::orderwith sizes [4, 8], and also checks against a direct scan the cell of each road, the entering prefix, the leaving lists, and that each turn rule joins the same two roads as before the order. -
Docs.
planner/router-build/README.md, "Work files and memory": the partition holds about 48 bytes for each junction in RAM, outside the 4 GiB guard, and fails when its need passes the page budget.specs/obc-data.md: the optioncell_sizes.
Files
planner/router-build/src/partition.rs: create: junction graph, bisection, tree, levels, IDs,Cells, tests.planner/router-build/src/layout.rs: change:partition_key, whichkeystakes in place ofspatial_key;ordertakessizes.planner/router-build/src/osm.rs: change:rankin the emit and the turn rules.planner/router-build/src/lib.rs: change:Graph.cells,Graph::permute_junctions.planner/router-build/src/step.rs,work.rs: change:cell_sizes, the partition stage,Guard::stage_within, statistics.planner/router-build/tests/routing.rs,planner/service/tests/http.rs: change:orderwith sizes.planner/router/examples/compare.rs: create: the cost comparison of two packages; request points at half the length of a road; a request withsnap_truncatedon either side is skipped and counted.host/obc-data-steps/src/planner.rs,data/planner.toml: change: the option ofplanner/routing-roads.planner/router-build/README.md,specs/obc-data.md: change.
Done when
obc test -p planner-router-build,obc test -p planner-service,obc test -p obc-data-steps, clippy on these three with--all-targets -- -D warnings,cargo fmt --all,obc suites check.- In a cloud container: one Switzerland bake (Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295's input, profiles
all) with all cores. A second run of the step withRAYON_NUM_THREADS=1, stopped after the partition line, prints the same partition SHA-256. compare OLD NEW 200 1on the Switzerland package of the branch base and the new one reports 0 differences. The pull request records the number of skipped requests.- The pull request records the statistics of step 8 for Switzerland, and for Germany in a cloud container with 4 cores and 15 GB of RAM (the bake up to the order), and the checks of step 9 for Switzerland. When the Germany partition takes more than 1 hour, or its peak passes 60 bytes for each junction, the builder reports to the owner before the merge.
Out of scope
- The bytes of the cell directory and the stored index, and the download level: Route package format 10: the contract, the writer and the installer #3301. The cost tables: Routing bake: the cost tables of each profile for each cell #3304. The final level sizes and the factor: Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310.
- The walks,
splitandends: Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295. The scan of the keys, the buckets and the terrain pass: Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296. The layers and their files: Routing bake: four cached layers: source, roads, costs, package #3299.
Built differently
Pull request #3366 built this design, into routing-overlay, with these changes:
- Walk 1 numbers the junctions in OSM node ID order, which removes two sorts on disk. Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 kept the first-use numbers only because the package bytes had to stay; this issue changes them once.
- There is no
step::Build: the roads step reads and checkscell_sizesbefore the import.level1is stored as[u32; 2]. The stagepartitionstarts after the sort of the junction pairs. The partition SHA-256 covers the columns that exist right after the partition. The three work layers share the formatFORMAT + 2. - The RAM graph of the partition is numbered in Morton order of the points, for speed. Each tie still goes by the junction ID of the bake, so the cells do not depend on it. The partition holds 36 B for each junction and 6 B for each arc, about 52 B for each junction.
comparecompares each request. A request whose 8th and 9th snap candidate are at exactly the same distance can differ, because the road numbers choose between them; it is counted apart. On Switzerland: 2,000 requests, 0 differences; 420 with more than 8 candidates, 14 differences, each at such a tie.- Measured (4 cores, 15 GB RAM): the partition takes 73.8 s for the 3.09 million junctions of Switzerland (160.9 s on 1 thread) and 116.1 s for the 3.99 million of North Rhine-Westphalia. Both regions have 5 levels. The package of Switzerland is 4.9 % larger than in the spatial order.
- The time of the partition grows about as n^1.8. Routing bake: the time of the partition grows about as n log n #3381 makes it faster with the same cells, before Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 measures Germany.
- Germany did not run (30 GB of disk): its partition figures and the mark of 1 hour are open, with Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310.
Activity