Skip to content

Route engine: the data layer on format 10 and the host interface #3302

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3301

TL;DR

Goal: The router asks its data for a search through one trait method, and a data layer on format 10 (Region) gives the request data of an install (candidates, costs at request points, the turns into a road, shapes, closures, profiles) equal to today's data on format 9.
Problem: The router takes the decoded graph of today's engine (Prepared) and runs the search itself, so no other engine can sit behind RoutingData. Today's data layer decodes the road graph and the cost columns of each profile into its own memory: about 40 bytes for each road and 9 to 15 for each profile, so about 16 GB for Europe with one profile. It cannot open format 10, and the engine has no interface to a host that gives bytes.
Decision:

Rejected:

  • A host call for each block or record. The views of Route package format 10: the contract, the writer and the installer #3301 read a part as one slice. A call for each read puts an error path into the hot loop, and no host of today reads less than a part. A map reads only the pages that the engine touches, so a whole part costs nothing more.
  • Map each file at open. A world service opens 35,000 files that most requests never read. Unmap the least used files. A lent slice has no owner that the host can count, and a map that no request touches holds no memory.
  • Region as a RoutingData now, with a search that fails. It is code that Route engine: the road search on format 10, and the test of the old engine against the new one #3303 deletes. The data test calls the functions directly.
  • A port of the memory budget. No data is decoded, so nothing needs an estimate.
  • A second copy of the router for format 10. The leg program is the code that must not differ.

Systems: routing
Contracts: none
Size: M (1 system, about 1,300 changed lines)
Branch: routing-overlay

Facts

The host interface

planner/router/src/host.rs. All workers share one host, so Host: Send + Sync.

Item Signature Rule
Part { record: u32, part: u8 } One installed file: the record number of its cell in directory.bin, and the part number of #3301
Span { part: Part, at: u32, bytes: u32 } A byte range of a part
Host::range fn range(&self, span: Span) -> Result<&[u8]> Lends the bytes. The slice stays valid and does not change while the host lives (rule 4 of #3301). A part that the install does not have: Error::MissingRegion (rule 2). A span that ends after the part: Error::InvalidData
Host::announce fn announce(&self, spans: &[Span]) The engine reads these spans next. The call returns at once, gives no error and changes no result

Plan

Error::Memory of #3308 must be on the branch: merge develop first.

  1. planner/router/src/host.rs (new): the table above, Maps under cfg(not(target_arch = "wasm32")), Memory.
  2. planner/router/src/cells.rs (Route package format 10: the contract, the writer and the installer #3301): each part is checked once and read many times. Where a view of Route package format 10: the contract, the writer and the installer #3301 checks in its constructor, split it into check(bytes) -> Result<()> and a constructor that does no work. check reads the header and the record tables only, a few KB, so the first read of a cold part of 45 MB reads a few pages. A block, a list or a record that does not lie in the part is InvalidData at the read that finds it. Directory::meeting(window) gives the download cell records whose box meets a window; the snap and install::area_cells of Phone: an offline area of whole cells, installed with the same installer #3309 call it.
  3. planner/router/src/region.rs (new), Region<H: Host>: the handle of one worker. It holds Arc<Shared<H>> and one reused model::Road.
    • Region::open(host, directory: Vec<u8>, info: Vec<u8>, install: &[u8]) -> Result<Self> checks rule 4 of Route package format 10: the contract, the writer and the installer #3301: the magic of install.bin, its hash against the SHA-256 of directory, and the info hash of the directory header against info. A failure is InvalidData. It parses package.json. Shared holds the host, the directory, the profiles of the installed groups, the installed download cells in ascending first_road (record, ID, first_road, roads), the bits of each level, and one flag for each part ("checked"). This is about 600 bytes for each cell, for all workers together. fork shares it. A host opens a new Region after an install that removed cells (rule 4).
    • Lookups: the download cell of a road ID by a binary search on first_road (the last cell is remembered); the level-1 record by a binary search on the first_road of the records of the topology part; the part bytes by Host::range. The first read of a part runs check and sets its flag. The download cell of a road reference by a binary search on the cell ID (the last cell is remembered); its run-time ID is first_road of the cell plus index; a cell that is not installed gives none.
  4. region.rs, the data functions, with the signatures of RoutingData:
    • identity: the SHA-256 of directory.bin as hex. region, bounds, attribution, warnings: from package.json. profiles and profile: the profiles whose group install.bin names; another name is InvalidRequest("Profile NAME is not installed"), as today (rule 3 of Route package format 10: the contract, the writer and the installer #3301).
    • snap(point, metric, policy). snap::window(point, radius) (new in snap.rs) is the box of snap::cells before its rounding to squares; cells calls it. Rule 2: when a download cell of Directory::meeting(window) is not installed, the result is MissingRegion. The router calls snap with 250 m and then with REACH_M, so each radius has its test. Rule 5: the road IDs go into one sorted set, as today, so a long road counts once: the roads of each level-1 cell whose geometry box meets the window, in each installed download cell whose box meets it, and each road of the long list whose own box meets the window, in each installed download cell whose long_box meets it. A long road of a cell that is not installed is skipped with no error. More than 100,000 roads in the set is Error::Limit. A road with its snap bit (allowed of the profile) is decoded and goes through snap::project. snap::candidates then sorts and cuts as today. Each road with a segment that meets the window is in the set, and project drops a road beyond the radius, so the candidates are those of today. Only the count for the limit differs; a request point reads at most 1 km.
    • with_road(road, f): decode_road into the reused Road, then f. No cache.
    • closing(road, mode): the closure set of the road from the geometry part, with the filter of Closures::closing.
    • endpoint(metric, road): the cost class of the road gives factor, turn and ferry of the profile. Factor 0 gives cost: None and no departures. Else CostBasis::compile with the decoded road, as today. The departures: let C be the level-1 cell of the departure junction of the road (its own cell when its index is at or after entering; else the cell that departure names), and t its target number in C (its index, or roads plus its place in leaving). Each turn of C with target t and a turn cost that is not all-ones gives Departure { state, penalty }, in ascending state. A C that is not installed gives none (rule 2).
    • announce(roads): one span for the geometry block of each level-1 cell of the roads, sorted, each once.
  5. planner/router/src/data.rs, RoutingData: add fn search(&mut self, metric: &str, query: Query<'_>) -> Result<Option<Found>>, fn closing(&self, road: u32, mode: u8) -> Result<Option<Vec<Closure>>> and fn announce(&self, _roads: &[u32]) {}. Remove closures, prepared, routing_bytes and Route service: request classes, the limit error as status 422, the probe radius #3308's idle_bytes from the trait; default_budget loses its default body. Selection keeps them as its own functions, and gets the field workspace: search::Workspace. Selection::search holds the lines that leg_batch has today: prepared, the two rooms of Route service: request classes, the limit error as status 422, the probe radius #3308 (each at most query.heap_bytes), the potential, run_with_potential, and clear_heaps when the profile changes. Query::heap_bytes is the cap of Control::max_heap_bytes; the engine applies its own budget below it.
  6. planner/router/src/router.rs: Router loses workspace; leg_batch calls self.package.search(&self.metric, query) with heap_bytes: control.max_heap_bytes; line calls announce with the roads of all paths, then reads them, and calls closing. planner/router/src/alternatives.rs:
    • spur compares the way and the lesser and the greater of the first and the last shape point, for both engines.
    • A probe snap that gives MissingRegion skips the probe.
    • Router::cost becomes pub(crate) and exact. The cost of the pieces stays as today. For the turns of a leg, it takes the roads in this order: the start road (Leg::start), the road of each piece, the end road (Leg::end). It drops each road that is the same as the road before it, and adds the turn cost between each two neighbours that remain. A turn that the data does not have gives none, as today. So a start at fraction 1 or an end at fraction 0, which has no piece, still gives its turn; a leg with no piece between two roads gives one turn; and a leg that starts and ends at one place of one road gives none. Then cost(route, the profile of the route) is Some(route.cost) for each route.
  7. Tests:
    • planner/router-build/tests/engines.rs (new) holds the fixture town(): a graph of 20 × 20 junctions about 350 m apart, each moved by a fixed xorshift so that few costs are equal; two-way and one-way roads, some gaps and diagonals, three surfaces, heights from a smooth function, forbidden turns for each mode, some foot-only roads, two closures, and one paved two-way road of about 10.5 km between two far junctions of the grid (a long road of Route package format 10: the contract, the writer and the installer #3301, and for some profiles the cheapest way between its ends). Routing bake: the partition into nested cells, and the roads in cell order #3300's layout::order with sizes [8, 32, 128] and download level 2, then format 9 by prepare and format 10 by cells::write and install, as Route package format 10: the contract, the writer and the installer #3301's tests/cells.rs. Selection reads the pages from memory; Region reads a Memory host filled from the install.
    • the_data_of_format_10_is_the_data_of_format_9: region, bounds and the profile list are equal. For each of the 10 profiles and each road: endpoint gives the same cost curve and the same departures; with_road gives the same shape (each bit), surface, access, scales, way and length; closing gives the same closures for each mode. snap gives the same candidates (position, projected point, distance, truncated) with 250 m, REACH_M and 4 km, at the middle and at the last point of each 5th road and at 50 points off the roads; among them a window that meets the level-1 box of the long road and its long box.
    • a_missing_cell_is_a_missing_region_and_gives_no_turn: an install of half of the download cells. A point whose window meets a cell that is not installed gives MissingRegion; another point gives the candidates of the full install that are installed; a road whose departure junction lies in a missing cell has no departures.
    • a_route_costs_what_its_pieces_and_turns_cost, on today's engine: for requests between junction points and road points of town(), with a via point, Router::cost with the profile of the route gives its cost. Among them: a leg from the end of one road to the start of the road directly after it (no piece, one turn), and a leg whose two points are one place of one road (no piece, no turn).
    • host.rs, maps_and_memory_lend_the_same_bytes: both hosts over two files; a range, a span beyond the part, an absent part.
    • Today's tests in planner/router-build/tests/routing.rs and planner/service/tests/http.rs pass with their assertions as they are: they check search, closing, announce, the spur check and the probe skip in the shared code.
  8. planner/router/README.md: the modules host and region.

Files

  • planner/router/src/host.rs, region.rs: create.
  • planner/router/src/cells.rs: change: the check of a part apart from its views; Directory::meeting.
  • planner/router/src/data.rs, snap.rs: change: the trait; Selection::search; snap::window.
  • planner/router/src/router.rs, alternatives.rs: change: search, closing, announce, the spur check, the probe snap, Router::cost.
  • planner/router/src/lib.rs: change: the modules.
  • planner/router-build/tests/engines.rs: create: the fixture and three tests.
  • planner/router-build/tests/routing.rs and the unit tests of data.rs: change: only where they call prepared, routing_bytes or closures through the trait.
  • planner/router/README.md: change.

Done when

  • obc test -p planner-router, obc test -p planner-router-build and obc test -p planner-service pass, with obc exec cargo clippy -p <crate> --all-targets -- -D warnings for each. cargo check -p planner-router --target wasm32-unknown-unknown and --target aarch64-apple-ios pass. cargo fmt --all and obc suites check pass.
  • Gate: the data test above. The old engine against the new one starts with Route engine: the road search on format 10, and the test of the old engine against the new one #3303.
  • The effect on today's answers: only accept for a route of another profile (the less-climbing route) changes. Its cost goes up by at most 600 for each leg (two turn costs), against a threshold of 1.35 times the primary cost on routes of 30 km or more, so only a route at the threshold can change. The spur check reads end points, which differ from junctions only for two nodes at one place. The pull request records, on the owner's PC, for 20 requests with alternatives: true of 30 to 200 km on one format 9 package of Switzerland, that the route IDs before and after this change are equal. A difference goes to the owner before the merge.
  • The pull request has the line Requirements: and says that public docs did not change.

Out of scope

Built differently

Pull request #3401 built this design, into routing-overlay, with these changes:

  • No check split and no "checked" flag for each part: the view constructors of Route package format 10: the contract, the writer and the installer #3301 read only the header and check each read. release left the trait. Router::cost is pub, because the test that this issue names is in planner-router-build. There is no "last cell remembered": the layer keeps 16 bytes for each installed download cell.
  • The turns into a road come from one pass over the head column of the departure cell with a walk of the first column in step (region::entering). The package stores no reverse turns. A level-1 cell with no road gives no departures.
  • cells::encode_marker is beside cells::marker, so a host without the installer (WebAssembly) can open a region. Maps takes its file count from the install marker and the file names from install::name.
  • A refusal by the system on an open or a map (no descriptors, no memory) is Error::Memory, which a retry can end. Error::Memory carries no text, so the cause is not in the message.
  • Measured on Switzerland (4 cores, 15 GB RAM), against the format-9 data layer on the package of the same input: all 7,719,364 roads equal; 11,027,670 endpoint calls for the 10 profiles equal, in 89.3 s against 88.3 s; 40,000 snaps equal (1,218 with more than 8 candidates), in 239.0 s against 387.0 s; the route IDs of 20 requests with alternatives equal. Opening the layer adds 36 KiB of own memory. The program that made this comparison is not a committed test.
  • Not measured: the first read with cold files (the disk of the cloud container is virtual; cold and warm gave about 7 ms). The Germany figures are with Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. A phone build on a Mac is an owner step: only cargo check for iOS and wasm32 ran.
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