Skip to content

Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: none

TL;DR

Goal: The import reads its large tables only in order or through a sort, and it reads each tag once: after the import, no stage looks up a node or a way by its OSM ID.
Problem: The import finds each node of each way by a binary search in a table sorted by OSM ID, three times for each node reference, and once more for the country of each way. For each road and each profile, the cost code reads the tags, the node list and the country of the way again, and the turn code reads the tags of the junction node for each turn. These are random reads in files of about 18 GB (the node lookups) and 30 GB (the tag lookups) for Europe [est, bake.md finding 2], which a PC with 16 or 32 GB of RAM cannot hold in its page cache.
Decision:

  • The node references are sorted by (node ID, reference position). The second pass over the PBF merges the node stream with them, and one more sort by reference position gives each reference its node data (NodeRef), parallel to the node lists of the ways. The node table goes.
  • The tag work of a node happens in that merge: crossing modes, traffic signal, junction mark, node closures. The tag work of a way happens in one scan of the ways in ID order: country, attributes, closures and doubts of each direction, route ranks (WayFacts).
  • One function osm::split splits a way into roads. Walk 1 calls it to find the road ends and to number the junctions with a sort; walk 2 calls it again to emit the roads. Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 and Routing bake: the partition into nested cells, and the roads in cell order #3300 use the same two walks.
  • The junctions get their numbers in OSM node ID order. No stored byte depends on the junction numbers, so the manifest ID stays. The gate is the same manifest ID.
  • The cost basis of each way, direction and profile comes from one more scan of the ways in ID order (cost::way_bases), into a table with one row for each way. Each road reads its basis from the row of its way (way_row, 4 B for each road). The package dictionary keeps its order of today.
  • After the import, the bake prints the counts and fails at once when a limit of format 9 or a 32-bit count cannot hold.
    Rejected:
  • Keep the junction numbers of today (first use by a road): it needs a third sort, and it changes no byte of the package.
  • A hash map from node ID to position: about 15 GB of RAM for the 610M nodes of Europe.
  • A dense array indexed by node ID: node IDs pass 13 billion, so 52 GB for 4-byte values.
  • The cost basis of each road as a road column, written in the emit walk: 4 B × profiles for each road (12 GB for Europe with 10 profiles) goes through the order of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296, and Routing bake: four cached layers: source, roads, costs, package #3299 must take it out of the roads layer again.
  • A profile-free key of the tags that the cost code reads, so that the costs need no tags: the cost code reads any tag, and a key misses each tag that a later cost change starts to read.
    Systems: routing
    Contracts: none
    Size: M (1 system, no contract change, about 1,200 changed lines with the tests)
    Branch: develop

Facts

  • Pass 2 finds each PBF node in the sorted needed IDs by a binary search (osm.rs#L286). build_graph then resolves each node reference by a binary search three times: junction flag, coordinates, graph point (osm.rs#L396, #L407, #L486), and the country of each way through the nodes (osm.rs#L352, source.rs#L626-L630). Table::get is a binary search (source.rs#L458-L460).
  • The junction marks are set by node ID: tagged nodes with a signal, a crossing limit or a closure, the via nodes of the turn rules, and the first, last and middle node of each routable way (osm.rs#L364-L394). A first or last node that no other reference uses does not change a split: it starts or ends its run anyway (osm.rs#L401-L420).
  • Costing::new reads the way, the tags and the country for each road and each profile (cost.rs#L68-L109), and builds the cycle route map again for each profile with a route bonus (cost.rs#L64). transition reads the tags of the junction node for each turn of the road profiles (cost.rs#L143-L149). The suitability code reads the class, surface, access, difficulties and direction of a road, never its shape or length (suitability.rs#L23-L80).
  • prepare looks up the OSM node of each junction for its closures, and the way of each road for its closures and doubt (lib.rs#L341-L363). Closures::build numbers the sets by first use in road order.
  • The dictionary of cost bases takes its IDs by first insert, profile by profile, each in road order (cost.rs#L108, lib.rs#L368-L393).
  • No stored byte depends on the junction numbers, only on their count, which the manifest warning retained graph nodes holds (osm.rs#L456): the arcs of a road are the departures of its arrival junction in road order (base.rs#L48-L60), the landmarks renumber the junctions by road (landmarks.rs#L22-L38), and the rest reads them only as keys. The spatial order breaks ties by the emit index of a road (layout.rs#L8-L19), so the emit order must stay.
  • The overlay index and the route catalog read the node coordinates by node ID (overlays.rs#L155, catalog/mod.rs#L306-L310).
  • The limits of format 9 fire hours after the import: "Too many roads", "Too many road transitions", the 8 MiB page of the closure sets and the manifest of 128 MiB (lib.rs#L270, base.rs#L57, storage.rs#L5, package.rs#L17).
  • planner/osm/bounds writes one PBF that osmium sorts by type, then ID (planner.rs#L331-L346).

Plan

  1. source.rs: the Nodes table and Data.nodes go. Ways gets points: Lists<NodeRef> (one for each node reference) and facts: Column<WayFacts>; the row Way gets points and facts; Table::filter copies both. Data gets members: Column<i64>, the sorted relation member nodes that a way references and that are present: today's osm.nodes holds only referenced nodes (osm.rs#L286, #L323), so a relation whose only member in the bounds is a node beside the road stays dropped. Data::country goes. Sets (new): the distinct closure sets of the bake, Vec<Set> and a map from set to ID, for way, node and road sets.

    NodeRef field Type Meaning
    lat, lon i32 microdegrees, as Point
    closures u32 Sets ID of osm::node_closures, or u32::MAX
    access u8 crossing modes of osm::crossing, `BIKE
    flags u8 PRESENT (in the PBF and in the bounds), SHARED (more than one reference), MARKED (signal, crossing limit or closure), SIGNALS
    WayFacts field Type Meaning
    routable bool osm::attributes gave attributes
    class, surface, difficulty, hiking_difficulty, structure as Road the attributes
    access [u8; 2] the modes forward and backward, after the via-way exclusions
    country Country of the first present node
    closures [u32; 2] Sets ID of source::closures forward and backward, or u32::MAX
    doubts [u8; 2] Doubts::modes of those sets
    ranks [u8; 2] highest cycle route rank forward and backward, 0 for none
  2. country.rs: Country becomes a Plain value: the row of its DEFAULTS entry (or none) and the side of the road. defaults and left_hand give the same answers.

  3. osm.rs, references: sorts (node ID, reference position) and gives the node stream, with the use count of each node. join_nodes (pass 2) merges it with the PBF nodes and with the sorted node members of the relations; a member enters Data.members only when it has a reference and is present. It fails with "the nodes of the input are not sorted by ID; sort it with osmium sort" when a node ID does not rise. For a present node with tags it calls crossing, the signal test, the mark rule and node_closures, once per node, so each warning count keeps its meaning. It writes one (reference position, NodeRef) record for each reference, also for a missing node (flags without PRESENT). sort::sorted by position gives Ways.points.

  4. osm.rs, facts: one scan of the ways in ID order writes WayFacts. cycle_ranks turns the cycle route relations into a sorted column of (way ID, ranks), which the scan merges; cost::cycle_routes goes. relation_rules changes WayFacts.access through a binary search of the way ID, as it changes RawWay today; RawWay goes. preserve_relations tests node members against Data.members, and ways by a present point. The filter of the ways keeps a way with a present point.

  5. osm.rs, split(way: &Way, vias: &[i64]) -> impl Iterator<Item = Run>: the runs of one routable way, in node order, with the rules of today's run loop and emit_run: a run ends at a missing node and at a junction; a run of fewer than 2 points or under 0.01 m gives no road. A reference is a junction when it is present and SHARED, MARKED, a via node (binary search in the sorted vias), or the middle node of a closed way. Run holds the first and last reference of the run in the way and its length. split yields only runs that give at least one road, one for each direction whose access is not 0, forward first; a way whose access is 0 in both directions after the exclusions yields nothing. So walk 1 numbers only the junctions that a road uses, and the count of the warning stays. The function reads only the way row and vias, so each call gives the same runs.

  6. osm.rs, junctions (walk 1): for each run of each routable way, in ID order, two end records (node ID, end number 2k or 2k + 1, its NodeRef). sort::sorted by (node ID, end number): each distinct node gets the next junction number, and points, node_ids, node_access, signals, node_closures, node_doubts are written in that order. A second sort by end number gives ends: Column<(u32, u32)>, the (from, to) junction of each road in emit order. "Too many graph nodes" fires here.

  7. osm.rs, emit (walk 2): calls split again, takes from and to from ends in order, the attributes from WayFacts, the shape from Way.points, and pushes the road with three new columns of Roads: way_row: u32 (the row of the way), closures: u32 (the Sets ID of the way set of its direction followed by the node set of its arrival junction) and doubt: u8 (WayFacts.doubts of its direction). The turn rules find their via junction by a binary search in node_ids, which walk 1 left sorted; the rest of the rule code stays.

  8. cost.rs: way_bases(osm: &Data, profiles: &[Profile]) -> WayBases scans the ways in ID order. For each routable way, direction with access and profile, it builds the Road of WayFacts with an empty shape and runs today's code of Costing::new before compile: permits, mode, suitability::way or road_bike::way with the way's tags and country, the route bonus from ranks, the doubt factor from doubts. WayBases holds one Column<u32> for each profile, of 2 × ways IDs at index 2 × row + direction, into its own Dictionary (0 for none); this dictionary does not check a basis. One column for each profile keeps the random reads of one profile in 8 B × ways (Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 sizes its profile groups by it). Costing::new takes the basis of road r from entry 2 × way_row[r] + reversed[r] of the column of its profile, compiles it as today, and inserts it into the package dictionary in road order: that insert checks the basis, so the IDs and the errors stay. transition reads signals and node_doubts; Doubts goes.

  9. lib.rs: Graph gets signals, node_closures, node_doubts and sets; Roads gets way_row, closures, doubt (also in push, get, permute). prepare calls cost::way_bases, gives Closures::build the set sets[closures[r]] of each road in road order, and drops the node map.

  10. overlays.rs, overlays/access.rs, catalog/mod.rs: points from Way.points, the country from WayFacts.

  11. lib.rs, check_limits(graph: &Graph, profiles: usize) -> Result<(), String>, called by step::build right after the import. It prints Imported: W ways, N node references, R directed roads, A turns, J junctions, with A = the sum over the junctions of arriving roads × departing roads, from two count columns. It fails when R ≥ 2^32 − 1, A ≥ 2^32, the distinct closure sets of the roads encode to more than MAX_PAGE_BYTES, or the manifest estimate passes MAX_MANIFEST_BYTES: "the package of this region needs a manifest of about N MiB; format 9 allows 128 MiB". With p(n) = ⌈n / 4096⌉, the estimate is 70 B × (p(R + 1) + p(A) + 2 p(R) + profiles × (2 p(R) + p(A) + p(⌈R / 64⌉) + 6 p(J)) + p(⌈R / 128⌉) + 1 + the 1° squares of the bounds) + 64 KiB.

  12. Tests. osm.rs: the fixture builds its graph through join_nodes, facts, junctions and emit; the tests of today keep their checks. New: a_join_gives_each_reference_its_node: references out of ID order, a missing node, a node outside the bounds, a node used twice and a tagged signal node give the expected NodeRef of each reference and the counts. lib.rs: the_manifest_estimate_is_not_below_the_manifest: the fixture package with 2 profiles. cost.rs and tests/routing.rs build Graph values with WayFacts and the new columns.

Files

  • planner/router-build/src/source.rs: change: NodeRef, WayFacts, Sets, no Nodes.
  • planner/router-build/src/osm.rs: change: references, join_nodes, facts, split, junctions, emit.
  • planner/router-build/src/country.rs: change: Plain country.
  • planner/router-build/src/cost.rs: change: way_bases, Costing::new, transition.
  • planner/router-build/src/lib.rs: change: Graph, Roads, prepare, check_limits.
  • planner/router-build/src/column.rs: change: plain! gets NodeRef, WayFacts, Country.
  • planner/router-build/src/step.rs: change: check_limits after the import.
  • planner/router-build/src/overlays.rs, overlays/access.rs, catalog/mod.rs: change: points and country.
  • planner/router-build/tests/routing.rs, planner/service/tests/http.rs: change: the graph fixtures.
  • planner/router-build/README.md: change: the input must be sorted by ID; the import prints its counts.

Done when

  • obc test -p planner-router-build, obc test -p planner-service, and obc exec cargo clippy -p <crate> --all-targets -- -D warnings for these two.
  • A Switzerland bake (the download.openstreetmap.fr extract, bounds 5.95 45.81 10.50 47.81, its 18 GLO-30 tiles, profiles all) gives the SHA-256 of manifest.json, overlays.sqlite and route-catalog.json of develop before the change. The pull request records them, and the printed manifest estimate, which must be at least the size of manifest.json and at most 110 % of it.
  • In a cloud container with 4 cores and 15 GB of RAM, a Germany bake up to the overlay index: the pull request records the counts, the time, the own peak (RssAnon) and the work folder peak of the import and of the preparation.

Out of scope

Built differently

Pull request #3325 built this design with these changes:

  • The junctions keep the first-use numbers of today. The fact "no stored byte depends on the junction numbers" is wrong: the geometry pages store Road.from and Road.to. With numbers in OSM node ID order the geometry part of the manifest changed and the gate failed. Walk 1 gets the first-use numbers with sorts on disk (the "third sort" that this issue rejected). The turn rules find their via junction in a map of the via nodes. Routing bake: the partition into nested cells, and the roads in cell order #3300 changes the road numbers and the package bytes once, so it can number the junctions again.
  • No road column doubt. Nothing reads it: cost::way_bases takes the doubt from WayFacts.doubts.
  • check_limits takes the bounds, because the estimate needs the 1° squares, and returns the estimate.
  • Ways.points is a Column that uses the list ends of nodes, not a second Lists.
  • A public Graph::link_ways sets up the hand-built test graphs.
  • docs/design/routing.md has no body yet, so it did not change.
  • Germany did not run: the cloud container has 30 GB of disk. The pull request records North Rhine-Westphalia in its place. The Germany record of "Done when" is open.
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