Repository navigation
Description
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:
- Host. A trait
Hostwith two calls.rangelends the bytes of a range of one installed part.announcenames ranges that the engine reads next.Maps(server, phone) maps a file read-only and shared at its first use, closes the file, and keeps the map until the host is dropped.Memory(WebAssembly, tests) holds parts in its own memory. - Data layer.
Region<H>reads the views of Route package format 10: the contract, the writer and the installer #3301 through the host. It has no cache and decodes nothing at open. No array has an entry for each road ID or each cell of the package (rule 1 of 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 gives it the data functions with the signatures ofRoutingData; Route engine: the road search on format 10, and the test of the old engine against the new one #3303 adds the search and the trait. - Trait seam.
RoutingDatagetssearch,closingandannounce, and losesclosures,preparedandrouting_bytes.Selectionruns today's search behindsearch. The leg program, the line, the alternatives and the line following stay one code for both engines. - Shared code. The spur check compares end points (rule 6 of Route package format 10: the contract, the writer and the installer #3301). A probe whose snap gives
MissingRegionis skipped.Router::costbecomes exact, so the gate of Route engine: the road search on format 10, and the test of the old engine against the new one #3303 can cost a route on the old data. - Gate. One test on a fixture graph: each data function of
Regiongives whatSelectiongives, for each road and each profile. Today's tests check the edits of the shared code, because both engines run it.
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.
Regionas aRoutingDatanow, 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
Selectionis the one implementation ofRoutingData(data.rs#L17-L45). The router uses the search only inleg_batch: it takesPrepared(graph, costs, landmarks) and callsWorkspace::run_with_potential(router.rs#L518-L533).linecallsclosuresandwith_road(router.rs#L365-L394).- Snapping reads the road lists of each square of 0.01° in a window into one sorted set, then the snap bit and the geometry page of each road, and stops with
Error::Limitabove 100,000 roads (data.rs#L448-L476, snap.rs#L88-L95).snap::candidatessorts by distance, then by road ID, and keeps at most 8 (snap.rs#L38-L43);projectdrops a road beyond the radius (snap.rs#L112). endpointcompiles the cost curve of a road from its cost basis and its shape, and lists the roads from which a turn enters it, with the turn cost (data.rs#L415-L423, #L501-L510).- The spur check reads
way,fromandto(alternatives.rs#L126-L139). An error of the probe snap ends the request (alternatives.rs#L88). Router::costsums the pieces of a route and the turns between them (alternatives.rs#L163-L189).leg_batchdrops a piece of no length (router.rs#L538-L542): the start road of a candidate at fraction 1, the end road of a candidate at fraction 0. The route cost holds the turn out of that start road and into that end road;costdoes not, so it can be lower than the route cost by these two turn costs.- The budget:
default_budgetis the costliest profile plus 256 MiB (data.rs#L41-L50). The queues get the budget lessrouting_bytes(router.rs#L519-L520); Route service: request classes, the limit error as status 422, the probe radius #3308 adds a second room (heap_limit,idle_bytes) to tell a fixed limit from a shortage. - A failed read of a memory map ends the process (directory.rs#L55-L57).
memmap2is a native dependency only (Cargo.toml#L17-L18); itsMmap::mapis read-only and shared. - Route package format 10: the contract, the writer and the installer #3301: an install has one file for each part of each cell, about 9,000 files for Europe and 35,000 for the world, against 65,530 memory maps for a process (
vm.max_map_count) and a soft limit of 1,024 open files. Follower: install format 10, and limits for memory maps #3307 sets the limit of the server, and Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 chooses the download level so that the world has at most 250,000 files. The run-time road ID is the same number in format 9 and in format 10 of one bake, and sparse on a phone (rule 1). A long road is a record of its level-1 block and an entry of the long list of its download cell. - Follower: install format 10, and limits for memory maps #3307 limits the anonymous memory of the route service (
RLIMIT_DATA); a map that is read-only and shared does not count. Route service: request classes, the limit error as status 422, the probe radius #3308:Error::Limitis a fixed limit, which the same request passes again on an idle service;Error::Memoryis a shortage that a retry can end.
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 |
- The engine asks for a whole part: the span from 0 to the
bytesof its directory entry. The views of Route package format 10: the contract, the writer and the installer #3301 then give each block. Maps::new(folder, directory)(native): one slot (OnceLock<Mmap>) for each part of each record. At the first use of a part,rangeopenscells/LEVEL-ID-PART, maps it withMmap::map(read-only, shared), closes the file, and compares the length with the directory. The map stays until the host is dropped, also when the installer removes the file. A later call is an index and one atomic load. A file that does not exist isMissingRegion; a wrong length isInvalidData; a map that the system refuses isError::Memory(another process state can change it), and the next call tries again. A read that fails on a mapped file ends the process, as today.announcemaps the file and callsmadvise(WILLNEED)for the span.Maps::silent(self)makesannouncedo nothing; only a measurement uses it.- Map limit. On Linux
Maps::newreads/proc/sys/vm/max_map_count. When the installed files plus 4,096 (the maps of the process itself are a few hundred) are more than the limit, it fails withInvalidData: "The install has N files and a process can hold M memory maps: set vm.max_map_count to at least N + 4096". The service then does not start, and no request finds the limit. Follower: install format 10, and limits for memory maps #3307 sets the limit of the server (vm.max_map_count = 1048576), and Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 chooses the download level so that the world has at most 250,000 files. Maps::evict(folder)(targets withposix_fadvise, the call of Route package format 10: the contract, the writer and the installer #3301's installer): drops each file ofcells/from the page cache, for the cold measurements of Route engine: the road search on format 10, and the test of the old engine against the new one #3303, Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 and Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. The system keeps a page that a process has mapped, so the caller drops each host of the folder first.Memory(each target):insert(part, bytes)before the open;rangelends a slice of its own bytes; an absent part isMissingRegion;announcedoes nothing. A host that reads files and fails givesInvalidDatawith the cause.
Plan
Error::Memory of #3308 must be on the branch: merge develop first.
planner/router/src/host.rs(new): the table above,Mapsundercfg(not(target_arch = "wasm32")),Memory.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 intocheck(bytes) -> Result<()>and a constructor that does no work.checkreads 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 isInvalidDataat the read that finds it.Directory::meeting(window)gives the download cell records whoseboxmeets a window; the snap andinstall::area_cellsof Phone: an offline area of whole cells, installed with the same installer #3309 call it.planner/router/src/region.rs(new),Region<H: Host>: the handle of one worker. It holdsArc<Shared<H>>and one reusedmodel::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 ofinstall.bin, its hash against the SHA-256 ofdirectory, and theinfohash of the directory header againstinfo. A failure isInvalidData. It parsespackage.json.Sharedholds the host, the directory, the profiles of the installed groups, the installed download cells in ascendingfirst_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.forkshares it. A host opens a newRegionafter 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 thefirst_roadof the records of the topology part; the part bytes byHost::range. The first read of a part runscheckand 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 isfirst_roadof the cell plusindex; a cell that is not installed gives none.
region.rs, the data functions, with the signatures ofRoutingData:identity: the SHA-256 ofdirectory.binas hex.region,bounds,attribution,warnings: frompackage.json.profilesandprofile: the profiles whose groupinstall.binnames; another name isInvalidRequest("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 insnap.rs) is the box ofsnap::cellsbefore its rounding to squares;cellscalls it. Rule 2: when a download cell ofDirectory::meeting(window)is not installed, the result isMissingRegion. The router callssnapwith 250 m and then withREACH_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 whoseboxmeets it, and each road of the long list whose own box meets the window, in each installed download cell whoselong_boxmeets it. A long road of a cell that is not installed is skipped with no error. More than 100,000 roads in the set isError::Limit. A road with its snap bit (allowedof the profile) is decoded and goes throughsnap::project.snap::candidatesthen sorts and cuts as today. Each road with a segment that meets the window is in the set, andprojectdrops 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_roadinto the reusedRoad, thenf. No cache.closing(road, mode): the closure set of the road from the geometry part, with the filter ofClosures::closing.endpoint(metric, road): the cost class of the road givesfactor,turnandferryof the profile. Factor 0 givescost: Noneand no departures. ElseCostBasis::compilewith the decoded road, as today. The departures: letCbe the level-1 cell of the departure junction of the road (its own cell when its index is at or afterentering; else the cell thatdeparturenames), andtits target number inC(its index, orroadsplus its place inleaving). Each turn ofCwith targettand a turn cost that is not all-ones givesDeparture { state, penalty }, in ascendingstate. ACthat 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.
planner/router/src/data.rs,RoutingData: addfn search(&mut self, metric: &str, query: Query<'_>) -> Result<Option<Found>>,fn closing(&self, road: u32, mode: u8) -> Result<Option<Vec<Closure>>>andfn announce(&self, _roads: &[u32]) {}. Removeclosures,prepared,routing_bytesand Route service: request classes, the limit error as status 422, the probe radius #3308'sidle_bytesfrom the trait;default_budgetloses its default body.Selectionkeeps them as its own functions, and gets the fieldworkspace: search::Workspace.Selection::searchholds the lines thatleg_batchhas today:prepared, the two rooms of Route service: request classes, the limit error as status 422, the probe radius #3308 (each at mostquery.heap_bytes), the potential,run_with_potential, andclear_heapswhen the profile changes.Query::heap_bytesis the cap ofControl::max_heap_bytes; the engine applies its own budget below it.planner/router/src/router.rs:Routerlosesworkspace;leg_batchcallsself.package.search(&self.metric, query)withheap_bytes: control.max_heap_bytes;linecallsannouncewith the roads of all paths, then reads them, and callsclosing.planner/router/src/alternatives.rs:spurcompares the way and the lesser and the greater of the first and the last shape point, for both engines.- A probe snap that gives
MissingRegionskips the probe. Router::costbecomespub(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. Thencost(route, the profile of the route)isSome(route.cost)for each route.
- Tests:
planner/router-build/tests/engines.rs(new) holds the fixturetown(): 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'slayout::orderwith sizes [8, 32, 128] and download level 2, then format 9 byprepareand format 10 bycells::writeandinstall, as Route package format 10: the contract, the writer and the installer #3301'stests/cells.rs.Selectionreads the pages from memory;Regionreads aMemoryhost 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:endpointgives the same cost curve and the same departures;with_roadgives the same shape (each bit), surface, access, scales, way and length;closinggives the same closures for each mode.snapgives the same candidates (position, projected point, distance,truncated) with 250 m,REACH_Mand 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 givesMissingRegion; 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 oftown(), with a via point,Router::costwith 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.rsandplanner/service/tests/http.rspass with their assertions as they are: they checksearch,closing,announce, the spur check and the probe skip in the shared code.
planner/router/README.md: the moduleshostandregion.
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.rsand the unit tests ofdata.rs: change: only where they callprepared,routing_bytesorclosuresthrough the trait.planner/router/README.md: change.
Done when
obc test -p planner-router,obc test -p planner-router-buildandobc test -p planner-servicepass, withobc exec cargo clippy -p <crate> --all-targets -- -D warningsfor each.cargo check -p planner-router --target wasm32-unknown-unknownand--target aarch64-apple-iospass.cargo fmt --allandobc suites checkpass.- 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
acceptfor 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 withalternatives: trueof 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
- The search on format 10,
Regionas aRoutingData, the search limit,open, the service and the comparison of the two engines: Route engine: the road search on format 10, and the test of the old engine against the new one #3303. - The tables and the closed-cell step: Routing bake: the cost tables of each profile for each cell #3304, Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305. The follower and its limits: Follower: install format 10, and limits for memory maps #3307. The phone area and its FFI: Phone: an offline area of whole cells, installed with the same installer #3309. The catalog on format 10: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
Built differently
Pull request #3401 built this design, into routing-overlay, with these changes:
- No
checksplit 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.releaseleft the trait.Router::costispub, because the test that this issue names is inplanner-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
headcolumn of the departure cell with a walk of thefirstcolumn in step (region::entering). The package stores no reverse turns. A level-1 cell with no road gives no departures. cells::encode_markeris besidecells::marker, so a host without the installer (WebAssembly) can open a region.Mapstakes its file count from the install marker and the file names frominstall::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::Memorycarries 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 checkfor iOS and wasm32 ran.
Activity
handover: the state after #3302 and #3304