Skip to content

Route service: request classes, the limit error as status 422, the probe radius #3308

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: none

#3308 Route service: request classes, the limit error as status 422, the worker count

TL;DR

Goal: Heavy requests hold at most max(1, workers / 2) routing workers, a request that a retry cannot help gets status 422, and the worker count has a rule for the engine of today and for the engine of format 10.
Problem:

  • All requests wait for one pool of workers. An alternatives request runs about 15 searches, and EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000 measured that two clients that loop the heaviest request give a normal user 79 % errors.
  • The engine gives Error::Limit for fixed limits of a request and for a lack of memory at that moment. The service answers both with 503, the status of a retry. The phone shows "busy" for both.
  • MAX_WORKERS = 12 cites the 2,048 MiB that the follower unit gives a routing service. Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306 removes that share.
  • Each router keeps its last primary route, which hits only at low load.
  • A corridor probe snaps with a radius of up to 4 km. In a city with more than about 1,200 directed roads per km², the window holds more than 100,000 roads, the snap gives Error::Limit, and the answer has no corridor route with no error.
    Decision:
  • Two request classes. A heavy request is a route request with alternatives or alternatives_only, or a shape request. It needs a heavy permit and a worker; there are max(1, workers / 2) heavy permits. A light request needs only a worker. Both wait at most 1 s in total, then answer 503 busy.
  • The engine splits Error::Limit in two: Error::Limit for a fixed limit that the same request always exceeds, also on an idle service, and Error::Memory for a lack of memory that depends on the other requests. The service answers limit with 422 and Error::Memory with 503 busy. The doc comment of Error states the rule, and Route engine: the data layer on format 10 and the host interface #3302, Route engine: the road search on format 10, and the test of the old engine against the new one #3303 and Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 cite it for their own conditions.
  • The worker count stays min(CPUs, MAX_WORKERS) with MAX_WORKERS = 12, now with its measurement as the reason. With the engine of format 10, Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 deletes MAX_WORKERS, and the count is the CPU count.
  • The cache of the last primary route goes.
  • The probe snaps with 250 m, then 1 km, then its offset when that is larger, and stops at the first radius that finds a road. This fix is in Route service: request classes, the limit error as status 422, the probe radius #3308 because it is the only limit condition that a normal request reaches.
    Rejected:
  • A separate pool of routers for heavy requests. It needs its own router count and memory; a second semaphore over one pool needs neither.
  • A longer queue wait for heavy requests. A client that waits more than 1 s for alternatives gets no better answer.
  • Status 422 for every Error::Limit of today. The queue room and the profile cache depend on the profiles that other routers hold, so a retry can succeed.
  • 503 busy for every queue that fills. A long leg whose queue needs more than the room that its own profile leaves fails each time, also on an idle service, and the phone would say "try again" without end.
  • A new error code for the memory case. Both clients already treat busy as "try again"; an unknown code shows "unavailable" on the phone.
  • Keep the primary cache. It saves the primary search of an alternatives call (91 of 1,145 ms on the 171 km route of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000) only when the same router serves the next request, which is at low load. Under load, where the time counts, it misses, and it makes the answer depend on the worker.
  • The probe fix in its own issue. It is one function, and the list of limit conditions must say what happens to it.
    Systems: routing, companion-ios
    Contracts: specs/route-api.md (errors)
    Size: M (2 systems, a contract change, about 300 changed lines)
    Branch: develop

Facts

  • A request waits up to QUEUE_WAIT (1 s) for one semaphore of workers permits, then gets 503 busy (http.rs#L24, #L90-L92). The deadline is 15 s for a route and 30 s for a shape request (lib.rs#L26-L27).
  • Error::Limit answers 503 limit (lib.rs#L100, route-api.md#L196-L208). The tokio semaphore is fair, so a light call waits only behind the calls before it in the queue.
  • The web planner throws the message and the code of an error answer and reads no status but ok (routing.ts#L101-L116). The phone maps the code: busy, limit and cancelled give PlannerFailure.busy (PlannerService.swift#L585-L596). The offline planner gives the answers of the native library to the same code, so the same mapping applies offline. So status 422 in place of 503 changes nothing in either client; only the message and the phone's mapping of limit change.
  • MAX_WORKERS = 12 comes from Central Switzerland in format 8: 87 MiB idle, about 80 MiB for each busy worker, 1,181 MiB with 12 busy workers (PR routing: one worker for each CPU of the service, up to a measured 12 #3054). Its comment cites the unit share of 2,048 MiB (http.rs#L27-L31). main.rs takes available_parallelism() up to that limit (main.rs#L21-L24).
  • The heap room of a search is the memory budget less routing_bytes, which counts every profile that any router holds (router.rs#L519, data.rs#L309-L321). retain keeps at least 16 MiB of it (data.rs#L326-L340). The default budget is the larger of 768 MiB and the costliest profile plus 256 MiB (data.rs#L41-L50). On an idle service, the room of a request is the budget less router_bytes and shared_bytes([metric]) of its own profile (data.rs#L259-L280).
  • Router::primary keeps the last primary route of each router (router.rs#L152, #L175-L183). The web asks for the route, then for alternatives_only (routing.ts#L132-L136). Routers leave the pool last in, first out (http.rs#L98-L100).
  • The probe snaps with offset_m.min(5000.0), and offset_m is 15 % of the route, from 1 to 4 km (alternatives.rs#L61, #L87-L88). A snap window of more than 100,000 roads is Error::Limit (data.rs#L464-L466), and routes drops it (alternatives.rs#L17-L21). snap::candidates sorts by distance, then by road (snap.rs#L38-L41), and the probe uses only retained.first() (alternatives.rs#L89), so the nearest road within a small radius gives the same probe as any larger radius.

The conditions that give Error::Limit today, and the result after #3308:

Condition Where A retry helps After
More than max_queries (8,192) searches in one request. A request of 64 points runs at most 497, with alternatives at most about 1,000 router.rs#L303 no 422 limit
The witness roads of all candidate searches pass max_geometry (250,000) router.rs#L308 no 422 limit
The answer passes 250,000 points router.rs#L408 no 422 limit
A path has more roads than max_roads search.rs#L250, #L268 no 422 limit
A cost, a priority or a candidate index overflows search.rs L126–L129, L200, L222, L232, L284, L286; router.rs L478–L502; alternatives.rs L177, L185 no 422 limit
A snap window holds more than 100,000 roads. A request point reads at most 1 km data.rs#L464 no 422 limit
A shape line fails, and one of its legs reached a router limit shape.rs#L314, #L533 no 422 limit
The search queue needs more than the room that its own profile leaves on an idle service queue.rs#L46 no 422 limit
The search queue fills the room that the profiles of the other routers leave queue.rs#L46 yes 503 busy
The profile alone does not fit the budget data.rs#L521 no 422 limit
A profile does not fit next to the profiles that other routers hold data.rs#L521 yes 503 busy
An allocation fails (try_reserve) search.rs L28, L34, L55; queue.rs L50; blocks.rs L112, L173, L209, L211; directory.rs L66, L133; landmarks.rs L54 yes 503 busy
In the data of format 9: a manifest above 128 MiB, a page index or a count above u32, a landmark delta overflow package.rs L177; data.rs L157; directory.rs L206; blocks.rs L57, L225 (at the open); table.rs L46, L60 and landmarks.rs L70 (also during a request, when a page or a profile loads) no 422 limit. A package that opens never reaches them. #3311 deletes them with format 9

Plan

  1. planner/router/src/lib.rs: add Error::Memory ("A routing worker has no memory for this request now"). The doc comment of Error states the rule: Limit when the same request fails again on an idle service with the same data; Memory when the cause is memory that other requests hold or an allocation that fails.
  2. planner/router/src/: each site of the rows with "yes" in the table returns Error::Memory: each try_reserve in queue.rs, search.rs, blocks.rs, directory.rs and landmarks.rs. The other sites keep Error::Limit. Two sites decide between both:
    • The queue room. Query gets heap_limit beside heap_bytes: the room on an idle service, the budget less router_bytes and shared_bytes([metric]), also capped by Control::max_heap_bytes. RoutingData gets fn idle_bytes(&self, metric: &str) -> Result<usize> for that sum, and leg_batch in router.rs computes both. Queue::push(entry, room, limit) and Queue::front(room, limit) give Error::Limit when the bytes would pass limit, else Error::Memory when they would pass room. Each side gets both less the heap of the other side, as room is today (search.rs#L131); else a request that fails the same way at each try would get Error::Memory.
    • Selection::prepared in data.rs: Error::Limit when idle_bytes(metric) passes the budget, else Error::Memory.
  3. planner/router/src/alternatives.rs, routes: Error::Memory also ends the discovery and keeps the routes found. The probe in alternatives snaps with snap::Policy::default() (250 m), then with snap::REACH_M, then with offset_m when it is larger than REACH_M, and stops at the first that retains a candidate. Remove the .min(5000.0): offset_m is at most 4 km.
  4. planner/router/src/shape.rs: Search::route maps Error::Memory to a new Failure::Memory. It stops the search as a cancel does (stopped), and answer gives Error::Memory.
  5. planner/router/src/router.rs and alternatives.rs: delete the field primary and Router::primary; routes calls route_counted for the primary route.
  6. planner/service/src/lib.rs, error_body: Error::Limit gives 422 limit, "This route exceeds the limits of the route service. Plan it in shorter parts."; Error::Memory gives 503 busy with the message of the queue wait.
  7. planner/service/src/http.rs: struct Gate { workers: Arc<Semaphore>, heavy: Arc<Semaphore>, wait: Duration } with async fn enter(&self, heavy: bool) -> Option<Permits>. A heavy call takes a heavy permit, then a worker permit, both within one wait; a light call takes a worker permit. Permits holds one or two OwnedSemaphorePermit. app makes Gate with workers and max(1, workers / 2) heavy permits and QUEUE_WAIT. call reads the class before the wait: a shape call is heavy; for a route call, the body parses into struct Class { #[serde(default)] alternatives: bool, #[serde(default)] alternatives_only: bool } (other fields are ignored), and a body that does not parse is light, because its worker answers invalid_request at once.
  8. http.rs, MAX_WORKERS: the comment says that it is the largest count measured busy on the Central Switzerland package, that router memory grows with the road count, and that a larger package needs a new measurement. It no longer names the unit.
  9. companion-ios/Packages/OBCKit/Sources/OBCPlanner/PlannerService.swift: a new PlannerFailure.routeTooLong, "This route is too long to plan. Plan it in shorter parts." send maps limit to it; busy and cancelled stay .busy. companion-ios/Packages/OBCKit/Sources/OBCUI/Import/ImportFlowModel.swift, reason: .routeTooLong joins .lineTooLong.
  10. specs/route-api.md, Errors: limit means that the request exceeds a fixed limit of the service; the same request fails again. busy means that no worker became free within 1 s, or that a worker had no memory for the request at that moment; send it again later. A route request with alternatives or alternatives_only, and a shape request, can use at most max(1, workers / 2) workers; with 1 worker, a light call waits behind a heavy one, as before. The table: limit 422; busy 503. planner/service/README.md: the same two sentences on the classes, and the ROUTE_WORKERS row.

Files

  • planner/router/src/lib.rs: change: Error::Memory.
  • planner/router/src/queue.rs, data.rs, search.rs, blocks.rs, directory.rs, landmarks.rs: change: the sites of Error::Memory, the two rooms of the queue, idle_bytes, a test in queue.rs.
  • planner/router/src/alternatives.rs: change: the discovery end, the probe radius, no primary cache.
  • planner/router/src/router.rs: change: delete the primary cache; heap_limit in leg_batch.
  • planner/router/src/shape.rs: change: Failure::Memory.
  • planner/service/src/lib.rs: change: the status of limit and of Error::Memory, a test.
  • planner/service/src/http.rs: change: Gate, the class of a call, the comment of MAX_WORKERS, a test.
  • planner/service/README.md: change: the classes and the errors.
  • specs/route-api.md: change: Errors.
  • companion-ios/Packages/OBCKit/Sources/OBCPlanner/PlannerService.swift: change: routeTooLong.
  • companion-ios/Packages/OBCKit/Sources/OBCUI/Import/ImportFlowModel.swift: change: its reason.
  • companion-ios/Packages/OBCKit/Tests/OBCPlannerTests/PlannerServiceTests.swift: change: a row (422, "limit", .routeTooLong).

Done when

  • http.rs: a_heavy_call_waits_for_its_share_and_a_route_gets_a_free_worker: a Gate of 2 workers and a wait of 50 ms; one heavy call holds its permits; a second heavy call gets None; a light call gets a worker.
  • lib.rs: a_fixed_limit_answers_422_and_a_lack_of_memory_answers_busy.
  • obc test -p planner-service, obc test -p planner-router, obc test -p planner-router-build, and clippy on the three crates, for planner-service also with --no-default-features.
  • The OBCKit tests of the planner and of the import pass, as companion-ios/README.md says.
  • queue.rs: a_queue_over_its_idle_room_is_a_limit_and_over_its_room_now_is_memory.
  • The pull request records, on the Central Switzerland package and a release build: for 20 requests with alternatives: true of 30 to 200 km, the route IDs before and after are equal, and the time of the probe snaps before and after. The record proves the speed and the equal routes, not the dense case.
  • The pull request records the load of PR routing: one worker for each CPU of the service, up to a measured 12 #3054 at 4 workers on the owner PC, under nice, with 8 clients that loop alternatives and 8 clients that loop primary routes of 20 to 50 km, for 60 s: the rate of 503 busy of the primary routes before and after.

Out of scope

Built differently

Pull request #3324 built this design with these changes:

  • The router drops unused cached profiles before it answers Memory. With the idle room as this issue defines it, an idle service could answer 503 busy at each retry: the idle room leaves out the cached profiles, but nothing dropped a cached profile while it fitted. Before a queue or a profile load answers Memory, the router now drops the cached profiles that no router holds and tries once. So an idle service answers a route or a limit.
  • The class of a call comes from the route decoder of the worker. The decoder accepts a route request as a JSON array too. A separate small decoder for the two alternatives fields did not, so such a request with alternatives counted as light.
  • planner/router-build/src/catalog/mod.rs maps the memory error to RouterLimit, and planner/router/README.md changed too.
  • Equal route IDs: 19 of 20 alternatives requests gave equal route IDs before and after. One request has 1 route before and 2 after with the same primary route: its old probe snap ended with a limit error. This is the intended effect of the probe radius.
  • Open: the OBCKit Swift tests did not run in the cloud container (no Swift toolchain). The load test ran in the container (4 cores, 15 GB RAM), not on the owner's PC.
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