Repository navigation
Description
Status: done
Part of #3227.
Depends on: #3297
TL;DR
Goal: The routing bake is four steps of obc data whose layers the store keeps: source, roads, costs and package. A crash repeats only the step that ran, a new profile list or cost model repeats only the costs and the package, and the store keeps only the newest of each cached layer.
Problem: The routing layer is one step with three outputs. Its work files are scratch that the step removes, also after an error, and the engine removes partial/layer-<key>/ when the step ends. So a crash in hour 9 loses all work, and a change of one profile repeats the import and the terrain: 609 s + 392 s on Germany [measured, #3251], at least 2 h for Europe [est]. A column file holds Rust values with their padding, which is right for scratch and wrong for a stored file.
Decision:
- Three new internal layers,
planner/routing-source,planner/routing-roads,planner/routing-costs, each with one step of the same name, no readers and no client files. The layerplanner/routingkeeps its step, which now writes only the package, the overlay index, the route catalog, the blocks and the route tiles. - Each key holds only what changes its layer: the source has the OSM cut and the bounds, the roads add the terrain, the costs add the profile list (and the bounds, which name the region). A new cost model changes the revision of the costs layer. The step list checks the profiles and the countries (
catalog::check) when it is built, so a bad option fails before any bake. - A stored column is one file of little-endian values of one
Storedtype:u8,u16,u32,u64,i32,i64, or a#[repr(C)]record of these with explicit padding. Each layer has alayout.jsonwith the type and the count of each file, which the reader checks. A step saves a work column by a rename into its output; a reader maps a store object read-only. - The costs step scans the ways of the source layer in their own order and calculates the cost basis of each way, direction and profile (
cost::way_basesof Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 and Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297). Each road takes it from the row of its way, throughway_rowof the roads layer (4 B for each road). Layergetscache: bool, which the receipt records. Of all receipts of one step of a cache layer with the same options, only the newest bybuiltcan be reached, and it is reached when its inputs are. So a new OSM cut or cost model deletes the old work layers of that region at the next collection, and the work of other regions stays.
Rejected:- The wording of the layer table of Routing: hierarchical search and disk storage #3227: write the bases "to the final road IDs through a map from the way order to the road order". Its random writes fit the RAM as well as the random reads of the gather. The gather is simpler:
way_rowandreversedare read in road order, no structure of the emit order is stored, the costs step does not split the ways again, and each chunk of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 writes its own range. It needs the column for each profile of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295'sWayBases. - Layers in one step with sub-directories that the step reuses itself: the engine removes the partial directory of a failed step, and the key of one step cannot say that only the costs changed.
serdeorpostcardfiles for the large tables: a decode for each read, and no memory map.- The newest-only rule for every internal layer: the
osmcuts of other targets would go too. - The newest of a step without its options: after a Germany bake, the next collection deletes the work layers of Switzerland.
Systems: routing, obc-data, data-engine
Contracts:specs/obc-data.md(the routing steps, the fieldcacheof a layer, the rule of a collection)
Size: L (3 systems, a contract change, a stored layout of the work layers, about 1,500 changed lines)
Branch:develop
Facts
PLANNER_ROUTINGhas the routerFORMATand revision 3; its one step reads the OSM cut, the GLO-30 tiles and the reference, and has the optionsregion,bounds,profiles,countries,attributionandterrain_attribution(planner.rs#L47-L50, #L401-L419, functions.rs#L19).- The engine builds a step only when the store has no receipt for its key. Code is not in the key; a change of output changes the revision of the layer, and the version of a layer applies to each of its steps (obc-data.md#L723-L728, #L798-L800). A failed step writes no receipt, and the layers that a run built stay (#L829-L834, #L976-L977).
- A collection keeps each layer whose inputs are reached, with no limit on versions (gc.rs#L175-L199). The newest record of a source and the sources of the served releases are reached, so the layers of each older revision on the same inputs stay.
- The work files of the bake are unnamed and removed on drop (work.rs#L55-L86). A column holds any
Plaintype, also tuples,bool,Option<u8>and Rust enums (column.rs#L22-L25). TMPDIRof a step ispartial/layer-<key>/tmp, besideoutput, so on the same file system (obc-data.md#L831-L832).- The step hashes each PBF itself, a third full read, although the request gives the SHA-256 of each input file in
layer_files(step.rs#L44-L57, obc-data.md#L820). - The store names each object by its SHA-256, so two equal turn columns of one profile group are one object.
Plan
-
host/obc-data/src/engine.rs:Layergetscache: bool("the store keeps only the newest layer of each step and options");Receiptgetscache(absent reads as false).store/gc.rs: before the loop ofplan, the newest receipt bybuiltof each group (step, options) of the cache receipts is chosen, whatever is reached; in the loop, a cache receipt is reached only when it is the chosen one of its group and its inputs are reached. So the result does not depend on the order of the receipts. -
planner/router-build/src/column.rs: a sealed traitStoredfor the types of the TL;DR; each record type has a compile-time check that its size is the sum of its fields. Acompile_error!on a big-endian target.Column::save(self, path)truncates the file to its values and renames it (copy and remove when the rename fails across file systems);Column::open(path)maps a file read-only, andpushandvalues_muton it panic.Listssaves and opens two files,<name>.endsand<name>.values.column::Layoutreads and writeslayout.json:{"format": 1, "files": {name: {"type", "len"}}};openfails with the file name when the type or the count differs. -
The road columns of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 become
Storedtypes:reversed,structureandsurfaceasu8,hiking_difficultyasu8with0xFEfor none.Pointgets#[repr(C)](12 B). The records:Record Bytes Fields in order NodeRef16 lat: i32,lon: i32,closures: u32,access: u8,flags: u8, 2 padding bytes (0)WayFacts24 closures: [u32; 2],routable,class,surface,access: [u8; 2],difficulty,hiking_difficulty,structure,defaults(country row or 255),left_hand,doubts: [u8; 2],ranks: [u8; 2], 2 padding bytesRule32 from: i64,to: i64,via: i64,only,u_turn,walking, 5 padding bytesTurn8 from: u32,to: u32 -
step.rsbecomes four functions;host/obc-data-steps/src/functions.rsregistersplanner-router-build/routing-source,routing-roadsandrouting-costsbesiderouting.Step Inputs Options Runs Writes planner/routing-sourceplanner/osm/boundsboundspass 1, the reference sort, the node join, facts, the turn rules of the relations, the relation filterssource/: the ways (IDs, node lists,NodeReflists, tags,WayFacts), the relations, the present member nodes, the rules, the closure sets (sets.postcard),source.json(the counts so far, the SHA-256 of the PBF fromlayer_files)planner/routing-roadsplanner/routing-source, the GLO-30 tiles of the bounds,planner/referencewhen there is onebounds,terrain_attributionwalk 1, the keys and the bucket bounds, walk 2 with the terrain in Buckets::finish, the turn rules, the 32-bit checks ofcheck_limits, the topologyroads/: the junction columns, the road columns withway_row, the shapes,forbiddenandforbidden_foot,firstandhead, the sets with the road sets,roads.json(the manifest warnings in their order, the identities: PBF, then terrain)planner/routing-costsplanner/routing-source,planner/routing-roadsbounds,profilesthe profile check, the manifest estimate of check_limits, the way bases, the road pass, the renumber, the snap bitscosts/: the dictionary (dictionary.postcard), and for each profile<i>.bases,<i>.totals,<i>.turns,<i>.snap;costs.json(the profile IDs in order)planner/routingthe three layers region,bounds,countries,attributionthe package writer with the landmarks ( Junctions::computein Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's n jobs, then the writes in profile order), the overlay index, the route catalog, the blocks, the route tilesas today The per-way table of the bases is a work file of the costs step, not an output.
preparestays for tests as costs plus package in memory.host/obc-data-steps/src/planner.rscallscatalog::checkand checks the profile IDs when it builds the steps; the steps check them again.Routing bake: the partition into nested cells, and the roads in cell order #3300 adds to
planner/routing-roadsthe optioncell_sizes, the partition between walk 1 and walk 2, the junction columns in cell order and the files ofCells. -
host/obc-data-steps/src/planner.rs:PLANNER_ROUTING_SOURCE,PLANNER_ROUTING_ROADS,PLANNER_ROUTING_COSTS(shape whole, format 1, revision 1, no readers,cache: true) and their steps (Client::None).wholesetscache: false. The test of the layer names maps the three steps and counts 20 layers. -
A change of the bytes of a work layer changes its format; a change of its content changes its revision. A change of the cost code changes the revision of
planner/routing-costs; of the import rules, ofplanner/routing-source; of the split, the order or the terrain, ofplanner/routing-roads. -
specs/obc-data.md: the fieldcachein the table of the layer fields; the three layers in the table of layers; the four rows of the routing steps in the step table ofplanner; the cache rule in "Clean", with its known costs: a collection between a failed bake and the next one can delete the last complete set of work layers while the new set is not complete; a region that no target lists any more keeps its work set until its extract request goes, asosmlayers do today; and when the work layers of a target are gone, a later update of that target bakes them again, also when its package is still in the store.planner/router-build/README.md: the layers, what each change repeats, and the disk of a Europe bake. -
Tests.
column.rs:a_saved_column_opens_with_its_values(au32column, aLists<Point>and aWayFactscolumn, throughlayout.json; a wrong type fails).gc.rs:a_collection_keeps_the_newest_cache_layer_of_each_step_and_options(two costs layers on one roads layer, in both receipt orders, and a costs layer of other bounds).planner.rs:only_the_costs_and_the_package_read_the_profiles(the keys of the four steps, the options of each).
What a change repeats:
| Change | Steps that run |
|---|---|
| A crash or a stop in a step | that step and the steps after it |
| The profile list | costs, package |
| The cost model (costs revision) | costs, package |
region, countries, attribution, the package format |
package |
| The GLO-30 tiles or the reference | roads, costs, package |
| The OSM cut or the bounds | all four |
Disk of the stored layers for Europe [est, from bake.md with 300M roads, 116M ways, 780M references, 120M junctions, 850M arcs]:
| Layer | Size |
|---|---|
planner/routing-source |
about 38 GB: references 6 GB, NodeRef 12.5 GB, tags 13 GB, WayFacts 3 GB, IDs, ends and relations 4 GB |
planner/routing-roads |
about 73 GB: shapes 51 GB, road columns 14 GB, topology 5 GB, junctions 3 GB |
planner/routing-costs |
41–58 GB: 2.4 GB for each profile for bases and totals, 3.4 GB for each distinct turn column |
planner/routing |
about 90 GB: the package 45 GB and the blocks 45 GB |
planner/osm/bounds |
about 41 GB |
So a first Europe bake needs about 330 GB: the layers, the cut and about 30 GB of work files while the roads step runs. A bake of a new cut needs about 600–700 GB at its peak: the 330 GB of the new set, the old work layers (152–169 GB) and the old cut (41 GB), which stay the newest until the new set exists, and the packages of the served and the rollback release (about 90 GB each). After the collection, a store holds one set of work layers for each region and profile list, and the package layers of the releases that the targets serve.
Files
host/obc-data/src/engine.rs,host/obc-data/src/store/gc.rs: change:cache, the rule, the test.host/obc-data-steps/src/planner.rs,host/obc-data-steps/src/functions.rs: change: the layers, the steps, the test.planner/router-build/src/column.rs: change:Stored,save,open, the test.planner/router-build/src/step.rs,lib.rs,osm.rs,source.rs,cost.rs: change: the four steps, the stored types, the split ofprepare.planner/router/src/model.rs: change:#[repr(C)]onPoint.- The other layer declarations of
host/: change:cache: false. specs/obc-data.md,planner/router-build/README.md: change.
Done when
obc test -p planner-router-build,obc test -p obc-data,obc test -p planner-service, clippy on them with--all-targets -- -D warnings;obc test -p obc-data-stepsin CI (it needs GEOS);obc suites check;obc prose --check;python3 docs/build_docs.py --check-links.obc data update local --only planner/routingon Switzerland gives the SHA-256 ofmanifest.json,overlays.sqliteandroute-catalog.jsonof the Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 bake. The pull request records the size of each layer, for Switzerland and for a Germany bake in a cloud container, and the Europe sizes scaled from Germany.- On Switzerland:
obc data runs RUN --stopwhile the costs step runs, then a new update: the log shows the source and roads steps unchanged and the costs step baked. With the revision ofplanner/routing-costsraised on a scratch branch,update --dry-runlists only the costs and the package.obc data clean(dry run) after that update shows one costs layer kept.
Out of scope
- The partition and its files in the roads layer: Routing bake: the partition into nested cells, and the roads in cell order #3300. The cost tables in the costs layer: Routing bake: the cost tables of each profile for each cell #3304. Format 10 of the package: Route package format 10: the contract, the writer and the installer #3301.
- A store on two disks, or a move of the work layers to the archive drive. Where the store of a Europe bake lives: workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000, with the figures above.
Built differently
Pull request #3350 built this design with these changes:
- The cache rule keeps the work layers that a run used last. A release names each file of each output, so a work layer that a release recorded would never go. A release now roots only the files that clients read of a cache layer. An update that ends without an error marks the work layers that it built or read (the receipt field
used), and the collection keeps the set marked last. After a failed or stopped update, a collection can delete a set that the update read; the next update makes it again. - The manifest estimate is in the costs step, because it needs the profile count and the key of the roads layer has no profile. The roads step checks the 32-bit counts before the terrain. A region whose manifest passes the limit of format 9 fails in the costs step, after the source and the roads steps.
- The snap bits are computed in the costs step and the landmark distances in the package step.
- A work layer has the format router
FORMAT+ 1, so a change of the router format makes the work layers again. - The profile and country check of a plan runs only when routing is on.
- Measured on Switzerland (4 cores, 15 GB RAM): source 70 s, roads 74 s, costs with 10 profiles 35 s, package 205 s; 384 s in all. The stored layers take 752, 1,243 and 1,434 MiB. After a kill in the costs step and a new profile list, the next bake reuses the source and the roads and takes 207 s. On North Rhine-Westphalia the stored layers take 825, 1,449 and 1,902 MiB; scaled from it, Europe needs about 25, 43 and 56 GB (an estimate).
- Open: the checks of "Done when" with
obc data update local,runs --stop,update --dry-runandcleandid not run, because the cloud container has no local store with the region sources; a script ran the four steps in the request format of the engine. The Germany bake did not run (30 GB of disk).
Activity