Skip to content

Routing bake: the partition into nested cells, and the roads in cell order #3300

Closed

Description

@timohueser

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.rs cuts 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 of ends, 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_sizes of the layer planner/routing-roads (Routing bake: four cached layers: source, roads, costs, package #3299), in data/planner.toml.
  • planner/router/examples/compare.rs routes 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 cos of 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, border and from give 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 option cell_sizes of the routing step)
    Size: M (2 systems, a compatible option, about 800 changed lines)
    Branch: routing-overlay

Facts

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.

  1. Option. data/planner.toml gets [routing] cell_sizes; host/obc-data-steps/src/planner.rs (Routing) passes it as the option cell_sizes of the layer planner/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::Build gets cell_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::build rejects 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.

  2. Junction graph. partition::partition(points: &Column<Point>, ends: &Column<(u32, u32)>, sizes: &[u32]) -> Result<Partition, String>, called by step::build right after walk 1. For each road with from ≠ to, the pair (min, max) goes through sort::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 a u8. A road from a junction to itself gives no edge. The edges go to a work column Column<((u32, u32), u8)>. The need is 32 B × J + 6 B × A (J junctions, A = 2 × edges); when it passes work::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, first junction [i32; 2], u32 12 lon, lat in microdegrees; start of its arcs
    adj, capacity, residual arc u32, u8, AtomicU8 15.6 neighbour; capacity in each direction; residual of the flow
    at, pos position, junction u32, AtomicU32 8 junction at each position; position of each junction
    work position in the part u32 × 3 12 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 pos outside the range is skipped. Parts that run at the same time touch disjoint entries of residual and pos, so relaxed atomic access is enough. A read of pos[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.

  3. 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_unstable gives 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 of work, which is freed before the recursion, then the new pos of each junction of the part.
  4. Tree and levels. partition splits the whole graph, then each side with rayon::join, until a part has at most sizes[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 most sizes[ℓ−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, from at), rank: Column<u32> (walk-1 → final, from pos), cells: Cells }; the RAM arrays are freed. One scan of ends counts the roads of each level-1 cell (the cell of rank[to]).

  5. 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 from cell_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.

  6. Key and junctions. layout::partition_key(from, to, &Partition) -> u64, with the walk-1 IDs of ends[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's layout::keys in place of layout::spatial_key and its Morton range check. For each road: cell << 32 | (255 − border) << 24 | (to − first junction of the cell), with to = rank[ends[i].1], cell the level-1 cell number of to, and border = 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's layout::keys calls this function in place of the spatial key; its quantile bounds, Buckets and the tie by emit index do not change. The first key of level-1 cell c is c << 32. osm::emit pushes from and to through rank; each read of a junction column before permute_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 in closures) uses the walk-1 ID ends[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 in node_ids, still in walk-1 order, and take it through rank. After the rules, Graph::permute_junctions(order) permutes every junction column of Graph (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::order for test graphs takes sizes and runs the same steps.

  7. Cell data. Cells (partition.rs) holds these columns; they are files of the layer planner/routing-roads (Routing bake: four cached layers: source, roads, costs, package #3299). Cells::finish(&mut self, roads: &Roads) fills border and the leaving lists after the order: one scan of from and to, 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
    ids u32 level-1 cells the cell ID of step 5
    upper u32 cells of levels 2..L, + 1 each level first level-1 cell of each cell
    widths, counts Vec<u8>, Vec<u32> L field width and cell count of each level
    border u8 roads the border level of each road
    leaving_first u32 cells of all levels + 1 start of the leaving list of each cell, level by level
    leaving u32 leaving 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:

    1. 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.
    2. 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 with border ≥ ℓ; so the list is ascending. Route package format 10: the contract, the writer and the installer #3301 derives the entering lists by this rule.
    3. 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.
    4. Departure cell. The departure cell of an entering border road is the cell of its from.
    5. 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.
  8. 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 peak RssAnon. It prints J, A, the need, the time, a SHA-256 of order and the Cells columns, 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).

  9. 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 of develop, 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.

  10. Comparison. planner/router/examples/compare.rs: compare OLD NEW COUNT SEED. It opens both packages with planner_router::open and 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 with snap_truncated in 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 whose Route::cost or error kind differs, it prints profile, points, old cost or error kind, new cost or error kind. It ends with N requests, S skipped, D differences and exits with 1 when D > 0.

  11. 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 (the lon cut 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, in rayon pools of 1 and 4 threads; order and every Cells column are equal. a_part_of_three_junctions_splits: sizes [2]. tests/routing.rs: prepared_coordinate_routes_match_independent_arrival_road_search calls layout::order with 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.

  12. 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 option cell_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, which keys takes in place of spatial_key; order takes sizes.
  • planner/router-build/src/osm.rs: change: rank in 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: order with sizes.
  • planner/router/examples/compare.rs: create: the cost comparison of two packages; request points at half the length of a road; a request with snap_truncated on either side is skipped and counted.
  • host/obc-data-steps/src/planner.rs, data/planner.toml: change: the option of planner/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 with RAYON_NUM_THREADS=1, stopped after the partition line, prints the same partition SHA-256.
  • compare OLD NEW 200 1 on 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

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 checks cell_sizes before the import. level1 is stored as [u32; 2]. The stage partition starts 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 format FORMAT + 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.
  • compare compares 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.
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