Repository navigation
Description
Status: done
Part of #3227.
Depends on: #3300
TL;DR
Goal: The bake publishes the routing package as format 10: one compressed object for each part of each cell, and one small binary directory. One library function installs any set of download cells, on the server and on the phone.
Problem: Format 9 lists each page of 4,096 values with a hash in one JSON manifest, so a package above about 47 to 63 million roads does not open. A road ID is a rank in the whole package, a page holds roads of several download areas, and each reader decodes the pages into its own memory. Measured on Central Switzerland (1.2 million roads): 129 bytes for each road in 43,244 page objects and 50 packs, and a phone downloads 1.03 to 3.3 times the bytes of its area.
Decision:
- A package is
package.json(for people and tools),directory.bin(the cell directory) and the objects. The identity of the package is the SHA-256 ofdirectory.bin. - An object is one zstd frame of one part of one cell. The cells with objects are the download cells and each cell of a higher level (an upper cell). The parts are the topology, the geometry, and one for each profile group. No object is without a cell.
- An installed file is one part, with no compression:
cells/LEVEL-ID-PART. The installer decompresses an object into its file and checks it. An install has no offset table. - The ID of a road at run time is
first_roadof its download cell, from the directory, plus its index in the cell. It is the same number on the server and on a phone. No published byte holds it. - In a part, the data lies by level-1 cell. Each column of a level-1 cell has its own width. A turn target is an index in the level-1 cell. A target outside the cell is an index in the list of the leaving border roads of the cell, which the overlay search needs too.
- Each download cell has its own table of cost bases and of closure sets. Snapping reads the box of each level-1 cell; the snap lists go. A road longer than 10 km (a long road) is in no cell box: its download cell lists it with its own box. Nothing replaces the landmark columns.
- Geometry is one record for each road: attributes, points as second differences, heights as bit differences.
- The download level is the setting
download_levelofdata/planner.toml.
Rejected:
- One installed file for each part kind, with all cells. A phone deletes a cell with its last area, which leaves a hole or copies the file. A map of tens of GB is one that a phone can refuse.
- One installed file for each download cell, with its parts in sequence. A change of the installed profile groups writes each file again, and the file needs padding and an offset table.
- A seekable zstd file, or more than one frame. No reader reads a range of an object: the installer reads it whole.
- A
zstdtransport encoding of the release. Each reader of a step index must then know it. Only the installer decodes these objects, so the release carries them asidentityfiles. - libzstd in the installer. It is C code that a build script compiles, so
cargo checkof the engine for iOS fails on Linux. The installer uses the Rust decoderruzstd; only the writer uses libzstd. - One JSON list of the objects. It is the limit of format 9 again. The directory is binary, about 550 bytes for each cell.
- Compact road IDs on the phone. A leg position (
road:fraction) from the server then names another road on the phone. Road IDs of 64 bits: 1.0 to 1.3 billion roads fit 32 bits. - Turn targets as indices in the download cell, with one border table. It needs 4 bytes for each turn (11 bytes for each road, against about 6), and the search still needs the place of the target in the leaving list.
- A list of exceptions for the turn costs. The epic gives each column of a cell one width.
- One column of basis IDs for each profile, or a compressed one. It is 2 bytes for each road and profile. One class index for each road and group holds the same facts. It is not compressed, so a read at a request point needs no cache.
- One table of cost bases and one of closure sets for the package. One new entry gives new IDs to each later cell, so no cell keeps its bytes. A phone downloads the table of the world, and the bake holds it in memory.
- The snap squares of 0.01°. About 8 to 10 bytes for each road when installed, one more object for each cell, and a square directory in the memory of the bake. The boxes give the same candidates.
- A cell box that holds each shape. One ferry of 300 km makes the box of its cell cover a sea. Each snap in that box then reads the cell, and each offline area in it downloads the cell. A list of the long roads in the directory: Scandinavia, Canada, Australia and Siberia can give 100,000 to 1 million of them. The directory then grows by up to 24 MB, which each phone downloads, and each snap tests each record. A long road by the size of its box in degrees: 100,000 microdegrees are 11 km from north to south and 4.7 km from east to west at 65° N. A box in metres needs a cosine, which can differ between machines. The length is an integer that the bake has.
- Geometry in compressed blocks in the installed file. The epic rejects a reader with a page cache. Heights as 4 raw bytes: about 20 bytes more for each road.
- Heights rounded to 1/8 m. With the XOR of bits it saves nothing: it needs integer heights with differences, which is a second geometry encoding, and it changes route costs once. One shape for the two directions of a road: it works only in one level-1 cell, with a twin field, and needs exactly reversed shapes from the terrain step. The two change only the geometry part, so they stay possible later. The installed geometry of Europe is about 25 to 35 GB for each release, which the server disk holds.
Systems: routing, obc-data
Contracts: specs/route-package.md (format 10), specs/planner-release.md (the files under routing/), specs/obc-data.md (the option download_level)
Size: L (2 systems, a new stored format, about 2,500 changed lines)
Branch: routing-overlay
Facts
- A page read hashes the page each time (package.rs#L276). The manifest limit is 128 MiB (package.rs#L17).
- A leg position is
road:fractionwith the run-time road ID (snap.rs#L55). Today that ID is the rank of the road in the selection (blocks.rs#L78), so it differs between the server and a phone area. The labels of today's search have an index over all road IDs (search.rs#L24). - Snapping reads the squares of a window around the point: on each side the radius divided by 0.110 m for each microdegree (for the longitude also by the cosine of the latitude), rounded up, plus 2 microdegrees (snap.rs#L88). It keeps a road only when it has the snap bit of the profile (data.rs#L468) and its projected distance is in the radius (snap.rs#L112). So each index that gives all roads with a point in the window gives the same candidates. A ferry has a cost in each weighted profile (model.rs#L98), so a long ferry can be a candidate.
- The engine reads these fields of a road: the shape,
surface,access, the two difficulty scales (router.rs#L378) andlength_m(cost.rs#L66). Only the spur check readsway,fromandto(alternatives.rs#L131). No engine code readsreversed,structure,ascent_m,descent_morclass. The MTB scale is 0 to 6 or 255 for none; the SAC scale is 0 to 6, 255 for a value that the bake does not know, or none (osm.rs#L81). - The cost basis of a road is read only at request points, and for each road of a route that the router costs again with another profile (data.rs#L501, alternatives.rs#L169). The bake gives the basis IDs in the order of first use (base.rs#L22), and writes all closure sets as one object (lib.rs#L409). A cost that a profile cannot use is
u32::MAXin the bake (base.rs#L97). - The terrain step adds shape points at most 20 m apart on each straight piece (terrain.rs#L114). So the step between two points changes little from one point to the next. The heights are
f32values, and the cost of a part of a road is calculated from them (cost.rs#L66): they must keep each bit. - A turn cost is 0 or 300 for most profiles; the road profiles add bends, signals and ferries (cost.rs#L118).
- A step index gives each file its size, its SHA-256 and its transport; the follower links an
identityfile and decodes agzipfile (services.rs#L428). The release composer accepts only these two encodings (planner_grid_index.py#L30) and reads only the steps whose name ends with/grid(planner.rs#L647). - The workspace has
zstd0.14 (libzstd 1.5.7), which builds C code.ruzstd0.8 is Rust only. It accepts each window size of the zstd format, and its README gives 1.4 to 3.5 times the decode time of libzstd. - Routing bake: the partition into nested cells, and the roads in cell order #3300 gives
Cells: the first road of each level-1 cell, the cell IDs, the first level-1 cell of each higher cell, the border level of each road, and the leaving list of each cell of each level. Routing bake: four cached layers: source, roads, costs, package #3299 gives the columns of the roads layer and of the costs layer as files, and the stepplanner/routingthat writes the package.
Format 10
All integers are little-endian. A width is 1, 2 or 4 bytes. A column of a level-1 cell has the narrowest width whose all-ones value is above each finite value of the column in that cell; a column with no finite value has width 1. In costs and turns, the all-ones value of the width means "cannot use" (the u32::MAX of the bake). A varint is unsigned LEB128; a signed value is zigzag first. Each offset is from the start of the part. Each field with a name that ends in _at is the offset of its section, also when the section is empty. In a part, each section, each block and each list starts at a multiple of 4, and the class table at a multiple of 8; a column of a block starts at a multiple of its width. Only the zero bytes that this needs lie between two items. A reader reads each integer with no alignment need.
Files. routing/package.json: compact JSON with sorted keys: format (10), region, bounds, source_sha256, attribution, warnings as in format 9; profiles, sorted by name, each {"group", "profile"} with the Profile of the engine; levels (the size limit of each level that the package has, level 1 first: the first values of cell_sizes of #3300, one for each level that #3300 made); download_level (that of the package); counts, an object with exactly the keys cells (the cell count of each level, level 1 first), long_roads, roads and turns. routing/directory.bin. routing/objects/SHA256, the objects by the SHA-256 of their bytes, in lower-case hex. A release that has routing/directory.bin holds a package of format 10: the follower of #3307 installs it when it finds that file. The layer format stays 9 until #3311.
Objects. One zstd frame, level 19, window at most 8 MiB, with the content size, no checksum, no dictionary, made on one thread. A part is smaller than 4 GiB; with the default level sizes, a download cell of a large package has 65,536 to 262,144 junctions (each side of a cut of #3300 holds at least a quarter of its part), about 160,000 to 650,000 roads, and its objects have about 0.5 to 45 MB. In the object pool of a target an object is objects/SHA256, as each file of a release. The pull request measures level 12 against 19 on Switzerland: if 19 takes more than 4 times the seconds for less than 5 % fewer bytes, the writer uses 12.
Download level. [routing] download_level in data/planner.toml, beside cell_sizes; the default is 4. It is an option of the step planner/routing, so a change repeats only the package. The step rejects a value outside 1 to 8. The download level of a package is the smaller of the setting and the number of levels that #3300 made.
Directory. The header of 64 bytes, then cells cell records.
| Header field | Type | Meaning |
|---|---|---|
magic |
8 bytes | OBCROUTE |
format |
u32 | 10 |
levels, download_level, groups, zero |
4 × u8 | The number of levels (at most 8), the download level, the number of profile groups (at most 32) |
level_bits |
8 × u8 | The bit count of the ID field of each level, level 1 first (widths of #3300) |
cells, roads |
2 × u32 | The number of cell records; the roads of the package |
info |
32 bytes | SHA-256 of package.json |
A cell record has 48 + 72 × (2 + groups) bytes. The download cells come first, by ID, then the upper cells by level and ID:
| Field | Type | Meaning |
|---|---|---|
level, zero |
u8, 3 bytes | The level of the cell |
id |
u32 | The cell ID of #3300, with zero bits below its level |
first_road, roads |
2 × u32 | The run-time ID of its first road; its road count |
box |
4 × i32 | West, south, east, north in microdegrees: the union of the boxes of its level-1 cells. No long road is in it |
long_box |
4 × i32 | The union of the boxes of the long roads of a download cell. All zero when it has none, and in an upper cell |
parts |
72 bytes each | Part 0 topology, part 1 geometry, part 2 + g profile group g |
A part entry is object (32 bytes, SHA-256 of the object), object_bytes (u32), sha256 (32 bytes, of the part) and bytes (u32). An absent part is all zero: an upper cell has no geometry. The first hash finds and checks the download; the second checks the installed file, also after the object is deleted. The record has no turn, junction or level-1 counts: the headers of the parts have the counts that a reader uses, and package.json has the totals.
A road reference has 8 bytes: cell (u32, a download cell ID) and index (u32). Its run-time ID is first_road of that cell plus index. Each list of road references is in ascending order of that ID. A long road is a road whose length_m is above 10,000.
Topology part. Sections in this order: the header, the level-1 records, the blocks in cell order, the upper records, and for each upper record its entering list and then its leaving list. Header, 24 bytes: cells, roads, turns, upper, upper_at (u32 each), zero. A level-1 record has 28 bytes:
| Field | Type | Meaning |
|---|---|---|
id |
u32 | The ID of the level-1 cell |
first_road, roads, turns |
3 × u32 | Its first road as an index in the download cell; its counts |
block |
u32 | The offset of its block |
entering, leaving |
2 × u16 | Its border roads of level 1. The entering ones are its first roads |
first_width, head_width, zero |
2 × u8, 2 bytes | The widths of its two columns |
The block of a level-1 cell, in this order:
| Column | Entries | Meaning |
|---|---|---|
first |
roads + 1 |
The turns of road i are first[i]..first[i+1], counted from the first turn of the cell |
head |
turns |
The target of a turn. A value below roads is a road of this cell. Other values, less roads, are indices in leaving. The turns of a road are in ascending order of this value |
leaving |
leaving road references |
The roads that depart in this cell and arrive in another |
departure |
entering × u32 |
The level-1 cell ID of the departure junction of each entering border road |
An upper record has 24 bytes: level (u8), zero, id, entering_at, entering, leaving_at, leaving (u32 each). The records are in the order of level and ID. They give the two lists of road references of each cell of level 2 to the download level that lies in this download cell. The topology part of an upper cell has no level-1 cell and one such record. The place of a road in an entering list is its row in the cost tables of the cell; its place in a leaving list is its column. For level 1, the row is the index of the road in its cell.
Profile group part. The profiles of the group are in the order of package.json. Sections in this order: the header, the level-1 records, the blocks, the class table, the slots, the tables. Header, 24 bytes: cells, upper, profiles, classes, classes_at, slots_at (u32 each). A level-1 record is block (u32), turn_width, class_width, one cost_width for each profile (u8 each), and zero bytes to a multiple of 4. The block:
| Column | Entries | Meaning |
|---|---|---|
turns |
turns |
The cost of each turn, in the order of head. All-ones: the profiles of the group cannot use it |
classes |
roads |
The cost class of each road: an index in the class table |
costs, for each profile |
roads |
The total cost of each road. All-ones: the profile excludes it |
allowed, for each profile |
roads bits |
The snap bit: road i is bit i % 8 of byte i / 8. The bits of the last byte above the last road are zero |
The class table has, for each class and each profile, 24 bytes: factor (f64), turn (f64), ferry (u64, 0 or 1). A cost class is the list of the cost bases of a road for the profiles of the group. Factor 0 means that the profile excludes the road. The classes are in ascending order of their bytes. The slots are, for each profile, one slot for each level-1 cell and then for each upper record of the topology part: at and bytes (u32 each). A slot names the cost table of that cell and profile. The tables lie by profile, then level, then cell. #3304 owns the bytes of a table. #3301 writes each slot with 0 bytes. The group part of an upper cell has only the header, the slots and the table of that cell: cells and classes are 0, upper is 1, and classes_at and slots_at are 24. Until #3304 an upper cell has no group part.
Geometry part. Sections in this order: the header, the level-1 records, the blocks, the long list, the set table. Header, 24 bytes: cells, long, long_at, sets, sets_at (u32 each), zero. The long list has one record of 20 bytes for each long road of the download cell, in ascending order of the road: road (u32, its index in the download cell) and the box of its shape (4 × i32). A level-1 record has 32 bytes: box (4 × i32), roads, block, bytes (u32 each), offset_width (u8), zero. The box is the box of the shapes of the roads of the cell that are not long. When each road of the cell is long, it is the last point of the first road. bytes is the size of the records of the block; offset_width is 2 when bytes is below 65,535, else 4. The block is roads + 1 offsets from its first record, then the records. A reader decodes a record with only the box of its cell:
| Field | Type | Meaning |
|---|---|---|
way |
varint | The OSM way ID |
use |
u8 | Bits 0–2 the surface (unknown, paved, compacted, gravel, dirt, rough), bits 3–5 the access (bike 1, foot 2, pushing 4) |
scales |
u8 | Bits 0–3 the MTB scale (0 to 6; 15 is none), bits 4–7 the SAC scale (0 to 6; 14 is the unknown value 255; 15 is none) |
length_m |
varint | The length in metres |
closure |
varint | 0, or 1 plus the index of its closure set |
points |
varint | The number of points, at least 2 |
| positions | signed varints | Point 0: latitude less south, longitude less west. Point 1: its step from point 0. Each later point: its step less the step before. Latitude first |
| heights | varints | For each point, the bits of its f32 height XOR the bits of the point before; zero before point 0. f32::MIN is unknown |
The set table is sets + 1 offsets (u32) from its first set, then the closure sets in the order of their first road. A set is a count (u8) and its entries: modes (u8), kind (u8, the order of closures::Kind), the condition as a varint length and UTF-8.
Installed files. In one folder: directory.bin, package.json, cells/LEVEL-ID-PART (LEVEL and PART decimal, ID as 8 lower-case hex digits), install.lock and install.bin. install.bin is OBCRINST (8 bytes), the SHA-256 of the directory, groups (u32, bit g set when group g is installed), count (u32) and count record numbers of the directory (u32, ascending). Each installed cell has the parts of each installed group. The server has each cell; a phone has fewer cells in the same layout. The engine finds the block of a level-1 cell in two lookups: the directory gives the download cell of a road ID or of a cell ID, and the level-1 records of the part give the block.
Rules that the other sub-issues cite:
- Road ID. Each host uses the run-time ID above. It is the number of the road in the cell order of the bake, so format 9 of the same bake names each road by the same number. A route answer has the identity of the directory as its
package. So a leg position means the same road on the server and on a phone that has the cell. The IDs of a phone area are sparse: no array of the engine has an entry for each road ID of the package (Route engine: the road search on format 10, and the test of the old engine against the new one #3303 keeps its labels in a hash table by road ID). - Missing cell. A turn from or into a download cell that is not installed is not a turn, also in the backward search and in the departures of an end point. A request point is
MissingRegionwhen it is outside the bounds of the package, as today, or when a download cell whose box meets the snap window is not installed. The snap window is the window ofsnap::cellsbefore its rounding to squares, for each radius that the snap tries. A long road of a download cell that is not installed is skipped and gives noMissingRegion: it arrives in the missing cell, so no route of this install can use it. Phone: an offline area of whole cells, installed with the same installer #3309 states this as a known difference from the server. A read of a part that the install does not have isMissingRegiontoo. Phone: an offline area of whole cells, installed with the same installer #3309 chooses the download cells of an area byboxof the cell record only, never bylong_box; a point nearer to the edge of the area than the snap window can then beMissingRegion. - Tables. The search treats a cell as open when its slot has 0 bytes, or when it is an upper cell that is not installed or has no group part. An upper cell is installed when, and only when, each download cell below it is installed. With Routing bake: the cost tables of each profile for each cell #3304, each written slot has a table of at least 16 bytes. A profile of a group that is not installed is not installed: a request with it fails as an unknown profile does today.
- Trust. A reader opens only a folder with
install.binwhose hash is that ofdirectory.bin, and reads both once. It does not hash a part. An installed file never changes under its name: the installer only adds and removes files. A reader keeps the bytes of a file that it mapped before the installer removed it; a first read of a removed file isMissingRegion. So a host opens a new reader after an install that removed cells. A reader closes each file after it maps it: Europe has about 9,000 files and the world about 35,000, against a soft limit of 1,024 open files and 65,530 maps. - Snapping. The roads near a point are the roads of each level-1 cell whose box meets the snap window, in the installed download cells whose
boxmeets it, and each road of the long list whose box meets it, in the installed download cells whoselong_boxmeets it. The snap bit and the distance then decide, as today. - Spur. The record has no junction. The spur check of Route engine: the data layer on format 10 and the host interface #3302 compares the way and the two end points of a road.
Plan
planner/router/src/cells.rs(new):FORMAT, the read viewsDirectory,Topology,GroupandGeometryover a byte slice, andencode_roadanddecode_roadfor the geometry record. A view checks its header and that each record offset is in the slice.decode_roadfills a reusedmodel::Road; the fields that the record does not have keep their default. Route engine: the data layer on format 10 and the host interface #3302 gives the views their bytes through its host interface.planner/router/src/install.rs(new, native only, besidedirectory.rs):plan(directory, cells, groups) -> Result<Plan>: the objects of an install, each with its record, part, file name, the two hashes,object_bytesandbytes.cellsis all cells or a list of download cell IDs;groupsis all groups or a list of profile names. It adds each complete upper cell.Plan::missing(target)is the plan without the files thattarget/cells/has with their final name.installed_bytes(plan)is the sum ofbytesandobject_bytes(plan)the sum ofobject_bytes: the disk check of Follower: install format 10, and limits for memory maps #3307 and the space check of Phone: an offline area of whole cells, installed with the same installer #3309 use them.install(target, directory, info, cells, groups, threads, fetch) -> Result<Report>.fetchgives the open file of an object by its SHA-256. The caller setsthreads; the follower uses 2 at low priority. In this order:- It takes
flock(LOCK_EX | LOCK_NB)ontarget/install.lock(File::try_lock). When another call holds it, in this process or in another, it returns an error at once. The kernel releases the lock when the process ends, so a crash blocks no later call; the file stays. - It checks
info(the bytes ofpackage.json) against the directory. Whentargethas adirectory.binwith other bytes, it returns an error, with or withoutinstall.bin: a folder holds one package. The same holds forpackage.json. A file that is there with the same bytes stays; a missing one is written through a temporary file, a sync and a rename. So no file that a reader has mapped is written again. - It deletes each
*.partincells/. For each file ofplan(…).missing(target), a worker reads the object as a stream, decompresses it, hashes the object and the part, writesNAME.part, compares the two hashes and sizes with the directory, syncs, drops the new file and the object from the page cache (posix_fadvisewithPOSIX_FADV_DONTNEEDon each of the two files, on the targets that have it), and renames. So neither the 100 GB of objects that a world install reads nor the 175 GB that it writes push the files of the serving release out of the page cache. The installer does both, so thefetchof a caller only opens a file. A file with its final name is complete and of this directory, so a second call goes on after a stop. A wrong object stops the install with the name of the object. - It syncs
cells/, writesinstall.binthrough a temporary file, a sync and a rename, and syncstarget. - It deletes each file in
cells/that the plan does not name. It deletes nothing outsidecells/. The follower gives it a folder of its own,route-cells/of a release (Follower: install format 10, and limits for memory maps #3307).
- It takes
check(directory, info, threads, fetch): the same stream with no file; it drops each object from the page cache too.scrub(target): reads each installed file again and returns the files whose SHA-256 differs.- Memory: the directory, and for each worker one zstd window (at most 8 MiB) and two buffers of 256 KiB. A worker holds at most two open files.
planner/router-build/src/cells.rs(new):write(input, output) -> Result<Summary, String>, on therayonpool of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297.inputis the columns of the roads layer (the road columns, the shapes,first,head, the closure sets,Cellsof Routing bake: the partition into nested cells, and the roads in cell order #3300), of the costs layer (for each profilebases,totals,turns,snap, and the dictionary),download_leveland the texts ofpackage.json.- Two profiles are one group when their
turnscolumns are equal; the groups are numbered by their first profile. - It reads the leaving list of each cell and level from
Cellsand does not sort. It makes the entering lists by the prefix rule of Routing bake: the partition into nested cells, and the roads in cell order #3300: in each level-1 cell of the cell, the first roads withborderat or above the level.departureis the cell ID offrom. It fails when the download cell IDs do not ascend with their first road, when a turn target of a level-1 cell is not in the cell and not in its leaving list, when a scale has a value that the record cannot hold, or when a part reaches 4 GiB. - It goes through the download cells in order and builds the parts of one cell in memory: the cost classes of the cell and group from the bases of its roads, the closure sets of the cell, the boxes, the blocks. A worker holds the parts of one cell (up to about 110 MB for 650,000 roads with the tables of Routing bake: the cost tables of each profile for each cell #3304) and one zstd context of level 19 (about 90 MB). It writes each object with its hash as its name, then the upper cells,
package.jsonanddirectory.bin. The bytes do not depend on the thread count. Summaryhas the installed and the published bytes of each part kind and each column, the object count and sizes, the number of long roads, and the largest long list of one download cell.
- Two profiles are one group when their
planner/router-build/src/step.rs: the stepplanner/routinggets the optiondownload_leveland the outputcells, and callscells::writeafter the format 9 package. The writer of format 9 does not change. Newcells_step: it links each file ofcells/intoobjects/under its SHA-256 and writesindex.jsonwithkind: "routing-cells"and the filesrouting/package.json,routing/directory.binandrouting/objects/SHA256, each withidentitytransport.host/obc-data-steps/src/functions.rs,planner.rsanddata/planner.toml: the setting and the optiondownload_level; the outputcellsof the stepplanner/routing; the functionROUTING_CELLS; the stepplanner/routing/cells/grid(a Rust step with the client pathsobjectsandindex.json, as the other grid steps), listed inPARTSunderrouting;PLANNER_ROUTING.revisiongoes up by one.host/obc-data-steps/src/planner/catalog.rs,verify: when a file ofplanner/routing/cells/gridchanged, it callsinstall::checkwith the objects of the store.planner/service/src/main.rs:planner-service INSTALL_DIRECTORY --scrubcallsinstall::scruband fails when a file differs. No program calls it:tools/vps/README.mdtells the operator to run it after a disk fault.planner/router-build/examples/cells.rs(new):cells write ROADS COSTS OUT [LEVEL]opens the two layers and callscells::writewith zstd levelLEVEL;cells install OUT TARGETinstalls all cells and then runscheck. Each prints itsSummaryorReport, the time and its peak memory.writealso prints the largest level-1 box and download cell box, and, for the middle point of each 1,000th road, the median and the largest number of download cells and of level-1 cells whose box meets the snap window of 250 m and of 1 km.planner/router/Cargo.toml(native targets):ruzstd.planner/router-build/Cargo.toml:zstd.specs/route-package.md: written again for format 10, with this outline: version and readers; files and identity; cells, levels and road IDs; objects; the directory; the topology part; the profile group part, with the cost and snap rules of today's text; the geometry part; installed files, the installer and the six rules; limits. Its first paragraph says that the code of format 9 stays until the old engine is deleted, and that its contract is the file ondevelop.specs/planner-release.md:routing/also holds the three kinds of file above, and an object is anidentityfile.specs/obc-data.md: the optiondownload_level.- Tests, in
planner/router-build/tests/cells.rs, on a test graph with a partition of at least three download cells and one upper cell, and one road longer than 10 km:an_install_gives_back_each_road: afterwriteandinstallof all cells, the views give, for each road, the turns as run-time IDs, the cost and the basis of each profile, the turn costs, the snap bit, the closures, the scales (also SAC 255) and each bit of the shape that the bake has. The leaving and entering lists of each cell and level are the border roads that a direct count from the partition gives. Each road with a point in a window is in a level-1 cell whose box meets the window, or in the long list of a download cell whoselong_boxmeets it; no level-1 box holds a point of the long road beyond its other roads.an_install_of_some_cells_holds_those_cells: an install of two of three cells has their files only and no upper cell; a second call with one cell deletes the other and leaves a file besidecells/in place;installed_bytesofmissingis 0 after an install; a turn into the absent cell resolves to a road ID that no installed cell holds.an_install_refuses_what_it_cannot_trust: one changed byte in an object gives an error and noinstall.bin; a folder with thedirectory.binof another package and noinstall.bingives an error; a second call while the lock is held gives an error; one changed byte in an installed file is found byscrub.the_bytes_do_not_depend_on_the_threads:writeinrayonpools of 1 and 4 threads gives the same directory.
planner/router/README.md: the modulescellsandinstallin the reference table.
What stays until #3311: the writer and the reader of format 9, the packs, blocks.json, the landmark columns, the snap lists, and the routing parts of tools/planner_grid*.py, planner_offline.py, planner_downloads.py and planner_verify.py. What format 10 does not have, so that #3311 deletes it with no replacement: the manifest with page hashes, pages.idx, Postcard pages, the junction of a road and the landmark mapping, the snap directories, the package-wide tables of cost bases and closure sets, the stored reverse graph, the cell manifests of offline/routing-cells/, and routing_packs. specs/planner-offline.md loses the routing packs, the routing descriptor and routing_source in #3311, and gains the rule of #3309 for the download cells of an area. routing_package of the release becomes the identity of the directory in #3311.
Files
planner/router/src/cells.rs: create: the views and the road record of format 10.planner/router/src/install.rs: create:plan,install,check,scrub.planner/router/src/lib.rs,planner/router/Cargo.toml: change: the two modules,ruzstd.planner/router-build/src/cells.rs: create: the writer.planner/router-build/src/lib.rs,step.rs,Cargo.toml: change: the module; the option, the outputcells,cells_step;zstd.planner/router-build/examples/cells.rs: create: the measurement tool.planner/router-build/tests/cells.rs: create: the four tests.host/obc-data-steps/src/functions.rs,planner.rs,planner/catalog.rs,data/planner.toml: change: the setting, the step and the check.planner/service/src/main.rs,tools/vps/README.md: change:--scrub.specs/route-package.md,specs/planner-release.md,specs/obc-data.md,planner/router/README.md: change.
Done when
obc test -p planner-router,obc test -p planner-router-build,obc test -p planner-serviceandobc test -p obc-data-stepspass, withobc exec cargo clippy -p <crate> --all-targets -- -D warningsfor each.cargo check -p planner-router --target wasm32-unknown-unknownand--target aarch64-apple-iospass.obc suites checkandpython3 docs/build_docs.py --check-linkspass.- Gate of the epic: a Switzerland bake on the branch gives the same format 9 manifest ID before and after this change. The test of 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.
- On the layers of one Switzerland bake,
cells writewithRAYON_NUM_THREADS=1and with all threads gives the same directory hash. No second bake is needed. - The pull request records, from
cells writeandcells installon the layers of a Switzerland bake with terrain and 10 profiles, on the owner's PC (16 GB, 6 cores):- the published and the installed bytes for each road, by part and column, beside this estimate (installed / published): topology 8 / 4; geometry 75 to 90 / 55 to 65 (53.7 published today); turn costs of all groups 15 to 20 / 2; cost classes 8 / 2; road costs 22 / 13; snap bits 1.3 / 0.3; in total about 135 / 80 without the tables of Routing bake: the cost tables of each profile for each cell #3304;
- the number of objects and their smallest, median and largest size (estimate: 2 plus the number of profile groups for each download cell, 0.5 to 45 MB);
- the bytes and the seconds of zstd level 12 and level 19, and the level that the rule chooses;
- the number of long roads and the largest long list of one download cell (Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 records the two on Germany), the largest level-1 box and download cell box, and the cell counts for the snap windows;
- an upper estimate of the long roads of the world from the lengths of the OSM ways: twice the sum of ⌊length / 10 km⌋ over the highway and ferry ways of the extracts of Norway, Canada, Australia and Russia, from one
osmiumscan of each in a cloud container; - the time and the peak memory of
installof all cells, with 1 and with 6 workers, and ofcheck, and the decode rate ofruzstdin MB/s for each worker. The frames of level 19 with the window of 8 MiB must decode. Estimate from the README ofruzstd: 0.3 to 0.7 GB/s for each worker. On the server, the 2 workers of the follower decode 0.6 to 1.4 GB/s, which is at or above the write rate of a disk of 0.2 to 0.5 GB/s. So the disk sets the install time: about 2 to 5 minutes for Europe (51 GB) and 6 to 15 minutes for the world (175 GB), with no cost from the Rust decoder. A phone area of 8 million roads (1.4 GB) decodes in 2 to 5 s on one core; - the linear estimate for Europe (300 million roads) and the world (1 billion roads): the objects, the installed bytes, the install time.
- The builder reports to the owner and does not change the format when: the installed geometry is above 95 bytes for each road; one download cell has more than 20,000 long roads (a list of 400 KB that each snap in its
long_boxtests); orruzstddecodes below 150 MB/s for each worker. - The pull request has the line
Requirements:and says that public docs changed.
Out of scope
- The host interface, the engine on the views, the spur check and the search: Route engine: the data layer on format 10 and the host interface #3302 and Route engine: the road search on format 10, and the test of the old engine against the new one #3303. The tables in the slots, their width and their value for "no path": Routing bake: the cost tables of each profile for each cell #3304. The overlay search: Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305.
- The follower that calls
installand keeps the installs, and the deletion of transport objects: Follower: install format 10, and limits for memory maps #3307. The phone, its download of the objects and the area rule: Phone: an offline area of whole cells, installed with the same installer #3309. - The deletion of format 9, the layer format 10,
routing_packageandspecs/planner-offline.md: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. - Deltas between two releases.
Built differently
Pull request #3386 built this design, into routing-overlay, with these changes:
- The objects use zstd level 12, not 19. Level 19 took 6.0 times the time for 4.98 % fewer bytes, so the rule of this issue picks 12.
- The decoder is
ruzstd0.9.1. Version 0.8.3 has the advisory RUSTSEC-2026-0344. It decodes 141 to 142 MB/s for each core, under the limit of 150 MB/s of this issue; the owner knows, and the format did not change. - The installer refuses an object before it decodes it when its content size is not the size of the part or its window is above 8 MiB. A part file starts with the first bytes of the part. Its errors have a type:
Locked,Objectwith the object,Iowith the path,Invalid. install::planalso takespackage.json, which holds the profile names that select the groups. The package step has the optioncell_sizes. A level-1 cell with no road has the point of its first junction as its box. The summary gives the published bytes for each part kind.- The views use checked 64-bit sizes, so a damaged field gives an error on each target. The directory index of the download cells is built once.
- Measured on Switzerland (4 cores, 15 GB RAM): identity
bbfb0484a5278cdb4052c49ced217e29a197fdbeb1bcd0762482bf282c286b16; 146 objects and 146 installed files. Installed and published bytes for each road: topology 8.05 and 2.54, geometry 54.07 and 41.06, groups 55.41 and 19.19, 117.5 and 62.8 in all. 64 long roads; the largest long list has 22. An install of all cells takes 10.0 s with 1 worker and 2.6 s with 4. - The 10 profiles give 6 profile groups: {gravel, gravel/less-climbing, touring, touring/less-climbing}, {hiking}, {hiking/alpine}, {mtb}, {mtb/technical}, {road, road/less-climbing}.
- The turn costs take 23.6 installed bytes for each road, above the estimate, because of the group count and not of the widths: a turn is stored as not allowed when the profile excludes one of its two roads, so two profiles with the same turn rules that exclude other roads cannot share a table. A rule that compares the turn columns only where both roads are usable gives 5 groups and about 19.6 bytes. It is not built; the owner decides.
- Open: the Python release steps against an index of kind
routing-cells, and anobc datarun of the grid step and ofverify, did not run in the cloud container. The Python verify reads each object twice. The estimate of the long roads of the world and the Germany figures did not run (30 GB of disk).
Activity