Repository navigation
Description
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::splitsplits 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
roadslayer 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_graphthen 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::getis 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::newreads 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).transitionreads 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).preparelooks 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::buildnumbers 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 nodesholds (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/boundswrites one PBF thatosmiumsorts by type, then ID (planner.rs#L331-L346).
Plan
-
source.rs: theNodestable andData.nodesgo.Waysgetspoints: Lists<NodeRef>(one for each node reference) andfacts: Column<WayFacts>; the rowWaygetspointsandfacts;Table::filtercopies both.Datagetsmembers: Column<i64>, the sorted relation member nodes that a way references and that are present: today'sosm.nodesholds 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::countrygoes.Sets(new): the distinct closure sets of the bake,Vec<Set>and a map from set to ID, for way, node and road sets.NodeReffieldType Meaning lat,loni32microdegrees, as Pointclosuresu32SetsID ofosm::node_closures, oru32::MAXaccessu8crossing modes of osm::crossing, `BIKEflagsu8PRESENT(in the PBF and in the bounds),SHARED(more than one reference),MARKED(signal, crossing limit or closure),SIGNALSWayFactsfieldType Meaning routableboolosm::attributesgave attributesclass,surface,difficulty,hiking_difficulty,structureas Roadthe attributes access[u8; 2]the modes forward and backward, after the via-way exclusions countryCountryof the first present node closures[u32; 2]SetsID ofsource::closuresforward and backward, oru32::MAXdoubts[u8; 2]Doubts::modesof those setsranks[u8; 2]highest cycle route rank forward and backward, 0 for none -
country.rs:Countrybecomes aPlainvalue: the row of itsDEFAULTSentry (or none) and the side of the road.defaultsandleft_handgive the same answers. -
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 entersData.membersonly when it has a reference and is present. It fails with "the nodes of the input are not sorted by ID; sort it withosmium sort" when a node ID does not rise. For a present node with tags it callscrossing, the signal test, the mark rule andnode_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 withoutPRESENT).sort::sortedby position givesWays.points. -
osm.rs,facts: one scan of the ways in ID order writesWayFacts.cycle_ranksturns the cycle route relations into a sorted column of (way ID, ranks), which the scan merges;cost::cycle_routesgoes.relation_ruleschangesWayFacts.accessthrough a binary search of the way ID, as it changesRawWaytoday;RawWaygoes.preserve_relationstests node members againstData.members, and ways by a present point. The filter of the ways keeps a way with a present point. -
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 andemit_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 andSHARED,MARKED, a via node (binary search in the sortedvias), or the middle node of a closed way.Runholds the first and last reference of the run in the way and its length.splityields 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 andvias, so each call gives the same runs. -
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, itsNodeRef).sort::sortedby (node ID, end number): each distinct node gets the next junction number, andpoints,node_ids,node_access,signals,node_closures,node_doubtsare written in that order. A second sort by end number givesends: Column<(u32, u32)>, the (from, to) junction of each road in emit order. "Too many graph nodes" fires here. -
osm.rs,emit(walk 2): callssplitagain, takesfromandtofromendsin order, the attributes fromWayFacts, the shape fromWay.points, and pushes the road with three new columns ofRoads:way_row: u32(the row of the way),closures: u32(theSetsID of the way set of its direction followed by the node set of its arrival junction) anddoubt: u8(WayFacts.doubtsof its direction). The turn rules find their via junction by a binary search innode_ids, which walk 1 left sorted; the rest of the rule code stays. -
cost.rs:way_bases(osm: &Data, profiles: &[Profile]) -> WayBasesscans the ways in ID order. For each routable way, direction with access and profile, it builds theRoadofWayFactswith an empty shape and runs today's code ofCosting::newbeforecompile:permits,mode,suitability::wayorroad_bike::waywith the way's tags and country, the route bonus fromranks, the doubt factor fromdoubts.WayBasesholds oneColumn<u32>for each profile, of 2 × ways IDs at index2 × row + direction, into its ownDictionary(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::newtakes the basis of roadrfrom entry2 × 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.transitionreadssignalsandnode_doubts;Doubtsgoes. -
lib.rs:Graphgetssignals,node_closures,node_doubtsandsets;Roadsgetsway_row,closures,doubt(also inpush,get,permute).preparecallscost::way_bases, givesClosures::buildthe setsets[closures[r]]of each road in road order, and drops the node map. -
overlays.rs,overlays/access.rs,catalog/mod.rs: points fromWay.points, the country fromWayFacts. -
lib.rs,check_limits(graph: &Graph, profiles: usize) -> Result<(), String>, called bystep::buildright after the import. It printsImported: 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 thanMAX_PAGE_BYTES, or the manifest estimate passesMAX_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. -
Tests.
osm.rs: the fixture builds its graph throughjoin_nodes,facts,junctionsandemit; 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 expectedNodeRefof each reference and the counts.lib.rs:the_manifest_estimate_is_not_below_the_manifest: the fixture package with 2 profiles.cost.rsandtests/routing.rsbuildGraphvalues withWayFactsand the new columns.
Files
planner/router-build/src/source.rs: change:NodeRef,WayFacts,Sets, noNodes.planner/router-build/src/osm.rs: change:references,join_nodes,facts,split,junctions,emit.planner/router-build/src/country.rs: change:Plaincountry.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!getsNodeRef,WayFacts,Country.planner/router-build/src/step.rs: change:check_limitsafter 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, andobc exec cargo clippy -p <crate> --all-targets -- -D warningsfor 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 ofmanifest.json,overlays.sqliteandroute-catalog.jsonof develop before the change. The pull request records them, and the printed manifest estimate, which must be at least the size ofmanifest.jsonand 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
- The order in buckets and the terrain after the order: Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296. The parallel profile pass, the memory guard and the cgroup limit: Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297. The stored layers: Routing bake: four cached layers: source, roads, costs, package #3299.
- The program
compare: Routing bake: the partition into nested cells, and the roads in cell order #3300, the first gate that needs it. The Europe counts: they print at the first Europe bake. - A sort that is skipped when the PBF is already sorted, and
posix_fallocatein place of the zero writes (bake.md finding 7).
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.fromandRoad.to. With numbers in OSM node ID order thegeometrypart 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_basestakes the doubt fromWayFacts.doubts. check_limitstakes the bounds, because the estimate needs the 1° squares, and returns the estimate.Ways.pointsis aColumnthat uses the list ends ofnodes, not a secondLists.- A public
Graph::link_wayssets up the hand-built test graphs. docs/design/routing.mdhas 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.
Activity