Skip to content

Route package format 10: the contract, the writer and the installer #3301

Closed

Description

@timohueser

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 of directory.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_road of 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_level of data/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 zstd transport 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 as identity files.
  • libzstd in the installer. It is C code that a build script compiles, so cargo check of the engine for iOS fails on Linux. The installer uses the Rust decoder ruzstd; 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:fraction with 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) and length_m (cost.rs#L66). Only the spur check reads way, from and to (alternatives.rs#L131). No engine code reads reversed, structure, ascent_m, descent_m or class. 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::MAX in 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 f32 values, 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 identity file and decodes a gzip file (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 zstd 0.14 (libzstd 1.5.7), which builds C code. ruzstd 0.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 step planner/routing that 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:

  1. 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).
  2. 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 MissingRegion when 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 of snap::cells before 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 no MissingRegion: 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 is MissingRegion too. Phone: an offline area of whole cells, installed with the same installer #3309 chooses the download cells of an area by box of the cell record only, never by long_box; a point nearer to the edge of the area than the snap window can then be MissingRegion.
  3. 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.
  4. Trust. A reader opens only a folder with install.bin whose hash is that of directory.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 is MissingRegion. 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.
  5. 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 box meets it, and each road of the long list whose box meets it, in the installed download cells whose long_box meets it. The snap bit and the distance then decide, as today.
  6. 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

  1. planner/router/src/cells.rs (new): FORMAT, the read views Directory, Topology, Group and Geometry over a byte slice, and encode_road and decode_road for the geometry record. A view checks its header and that each record offset is in the slice. decode_road fills a reused model::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.
  2. planner/router/src/install.rs (new, native only, beside directory.rs):
    • plan(directory, cells, groups) -> Result<Plan>: the objects of an install, each with its record, part, file name, the two hashes, object_bytes and bytes. cells is all cells or a list of download cell IDs; groups is all groups or a list of profile names. It adds each complete upper cell. Plan::missing(target) is the plan without the files that target/cells/ has with their final name. installed_bytes(plan) is the sum of bytes and object_bytes(plan) the sum of object_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>. fetch gives the open file of an object by its SHA-256. The caller sets threads; the follower uses 2 at low priority. In this order:
      1. It takes flock(LOCK_EX | LOCK_NB) on target/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.
      2. It checks info (the bytes of package.json) against the directory. When target has a directory.bin with other bytes, it returns an error, with or without install.bin: a folder holds one package. The same holds for package.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.
      3. It deletes each *.part in cells/. For each file of plan(…).missing(target), a worker reads the object as a stream, decompresses it, hashes the object and the part, writes NAME.part, compares the two hashes and sizes with the directory, syncs, drops the new file and the object from the page cache (posix_fadvise with POSIX_FADV_DONTNEED on 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 the fetch of 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.
      4. It syncs cells/, writes install.bin through a temporary file, a sync and a rename, and syncs target.
      5. It deletes each file in cells/ that the plan does not name. It deletes nothing outside cells/. The follower gives it a folder of its own, route-cells/ of a release (Follower: install format 10, and limits for memory maps #3307).
    • 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.
  3. planner/router-build/src/cells.rs (new): write(input, output) -> Result<Summary, String>, on the rayon pool of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297. input is the columns of the roads layer (the road columns, the shapes, first, head, the closure sets, Cells of Routing bake: the partition into nested cells, and the roads in cell order #3300), of the costs layer (for each profile bases, totals, turns, snap, and the dictionary), download_level and the texts of package.json.
    • Two profiles are one group when their turns columns are equal; the groups are numbered by their first profile.
    • It reads the leaving list of each cell and level from Cells and 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 with border at or above the level. departure is the cell ID of from. 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.json and directory.bin. The bytes do not depend on the thread count.
    • Summary has 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.
  4. planner/router-build/src/step.rs: the step planner/routing gets the option download_level and the output cells, and calls cells::write after the format 9 package. The writer of format 9 does not change. New cells_step: it links each file of cells/ into objects/ under its SHA-256 and writes index.json with kind: "routing-cells" and the files routing/package.json, routing/directory.bin and routing/objects/SHA256, each with identity transport.
  5. host/obc-data-steps/src/functions.rs, planner.rs and data/planner.toml: the setting and the option download_level; the output cells of the step planner/routing; the function ROUTING_CELLS; the step planner/routing/cells/grid (a Rust step with the client paths objects and index.json, as the other grid steps), listed in PARTS under routing; PLANNER_ROUTING.revision goes up by one.
  6. host/obc-data-steps/src/planner/catalog.rs, verify: when a file of planner/routing/cells/grid changed, it calls install::check with the objects of the store.
  7. planner/service/src/main.rs: planner-service INSTALL_DIRECTORY --scrub calls install::scrub and fails when a file differs. No program calls it: tools/vps/README.md tells the operator to run it after a disk fault.
  8. planner/router-build/examples/cells.rs (new): cells write ROADS COSTS OUT [LEVEL] opens the two layers and calls cells::write with zstd level LEVEL; cells install OUT TARGET installs all cells and then runs check. Each prints its Summary or Report, the time and its peak memory. write also 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.
  9. planner/router/Cargo.toml (native targets): ruzstd. planner/router-build/Cargo.toml: zstd.
  10. 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 on develop. specs/planner-release.md: routing/ also holds the three kinds of file above, and an object is an identity file. specs/obc-data.md: the option download_level.
  11. 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: after write and install of 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 whose long_box meets 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 beside cells/ in place; installed_bytes of missing is 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 no install.bin; a folder with the directory.bin of another package and no install.bin gives an error; a second call while the lock is held gives an error; one changed byte in an installed file is found by scrub.
    • the_bytes_do_not_depend_on_the_threads: write in rayon pools of 1 and 4 threads gives the same directory.
  12. planner/router/README.md: the modules cells and install in 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 output cells, 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-service and obc test -p obc-data-steps 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. obc suites check and python3 docs/build_docs.py --check-links pass.
  • 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 write with RAYON_NUM_THREADS=1 and with all threads gives the same directory hash. No second bake is needed.
  • The pull request records, from cells write and cells install on 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 osmium scan of each in a cloud container;
    • the time and the peak memory of install of all cells, with 1 and with 6 workers, and of check, and the decode rate of ruzstd in MB/s for each worker. The frames of level 19 with the window of 8 MiB must decode. Estimate from the README of ruzstd: 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_box tests); or ruzstd decodes below 150 MB/s for each worker.
  • The pull request has the line Requirements: and says that public docs changed.

Out of scope

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 ruzstd 0.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, Object with the object, Io with the path, Invalid.
  • install::plan also takes package.json, which holds the profile names that select the groups. The package step has the option cell_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 an obc data run of the grid step and of verify, 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).
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