Repository navigation
Closed
Description
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::Limitfor 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 = 12cites 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
alternativesoralternatives_only, or a shape request. It needs a heavy permit and a worker; there aremax(1, workers / 2)heavy permits. A light request needs only a worker. Both wait at most 1 s in total, then answer503 busy. - The engine splits
Error::Limitin two:Error::Limitfor a fixed limit that the same request always exceeds, also on an idle service, andError::Memoryfor a lack of memory that depends on the other requests. The service answerslimitwith 422 andError::Memorywith503 busy. The doc comment ofErrorstates 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)withMAX_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 deletesMAX_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
limitcondition 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::Limitof today. The queue room and the profile cache depend on the profiles that other routers hold, so a retry can succeed. 503 busyfor 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
busyas "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
limitconditions 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 ofworkerspermits, then gets503 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::Limitanswers503 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
messageand thecodeof an error answer and reads no status butok(routing.ts#L101-L116). The phone maps the code:busy,limitandcancelledgivePlannerFailure.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 oflimitchange. MAX_WORKERS = 12comes 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.rstakesavailable_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).retainkeeps 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 lessrouter_bytesandshared_bytes([metric])of its own profile (data.rs#L259-L280). Router::primarykeeps the last primary route of each router (router.rs#L152, #L175-L183). The web asks for the route, then foralternatives_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), andoffset_mis 15 % of the route, from 1 to 4 km (alternatives.rs#L61, #L87-L88). A snap window of more than 100,000 roads isError::Limit(data.rs#L464-L466), androutesdrops it (alternatives.rs#L17-L21).snap::candidatessorts by distance, then by road (snap.rs#L38-L41), and the probe uses onlyretained.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
planner/router/src/lib.rs: addError::Memory("A routing worker has no memory for this request now"). The doc comment ofErrorstates the rule:Limitwhen the same request fails again on an idle service with the same data;Memorywhen the cause is memory that other requests hold or an allocation that fails.planner/router/src/: each site of the rows with "yes" in the table returnsError::Memory: eachtry_reserveinqueue.rs,search.rs,blocks.rs,directory.rsandlandmarks.rs. The other sites keepError::Limit. Two sites decide between both:- The queue room.
Querygetsheap_limitbesideheap_bytes: the room on an idle service, the budget lessrouter_bytesandshared_bytes([metric]), also capped byControl::max_heap_bytes.RoutingDatagetsfn idle_bytes(&self, metric: &str) -> Result<usize>for that sum, andleg_batchinrouter.rscomputes both.Queue::push(entry, room, limit)andQueue::front(room, limit)giveError::Limitwhen the bytes would passlimit, elseError::Memorywhen they would passroom. Each side gets both less the heap of the other side, asroomis today (search.rs#L131); else a request that fails the same way at each try would getError::Memory. Selection::preparedindata.rs:Error::Limitwhenidle_bytes(metric)passes the budget, elseError::Memory.
- The queue room.
planner/router/src/alternatives.rs,routes:Error::Memoryalso ends the discovery and keeps the routes found. The probe inalternativessnaps withsnap::Policy::default()(250 m), then withsnap::REACH_M, then withoffset_mwhen it is larger thanREACH_M, and stops at the first that retains a candidate. Remove the.min(5000.0):offset_mis at most 4 km.planner/router/src/shape.rs:Search::routemapsError::Memoryto a newFailure::Memory. It stops the search as a cancel does (stopped), andanswergivesError::Memory.planner/router/src/router.rsandalternatives.rs: delete the fieldprimaryandRouter::primary;routescallsroute_countedfor the primary route.planner/service/src/lib.rs,error_body:Error::Limitgives 422limit, "This route exceeds the limits of the route service. Plan it in shorter parts.";Error::Memorygives 503busywith the message of the queue wait.planner/service/src/http.rs:struct Gate { workers: Arc<Semaphore>, heavy: Arc<Semaphore>, wait: Duration }withasync fn enter(&self, heavy: bool) -> Option<Permits>. A heavy call takes a heavy permit, then a worker permit, both within onewait; a light call takes a worker permit.Permitsholds one or twoOwnedSemaphorePermit.appmakesGatewithworkersandmax(1, workers / 2)heavy permits andQUEUE_WAIT.callreads the class before the wait: a shape call is heavy; for a route call, the body parses intostruct 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 answersinvalid_requestat once.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.companion-ios/Packages/OBCKit/Sources/OBCPlanner/PlannerService.swift: a newPlannerFailure.routeTooLong, "This route is too long to plan. Plan it in shorter parts."sendmapslimitto it;busyandcancelledstay.busy.companion-ios/Packages/OBCKit/Sources/OBCUI/Import/ImportFlowModel.swift,reason:.routeTooLongjoins.lineTooLong.specs/route-api.md, Errors:limitmeans that the request exceeds a fixed limit of the service; the same request fails again.busymeans 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 withalternativesoralternatives_only, and a shape request, can use at mostmax(1, workers / 2)workers; with 1 worker, a light call waits behind a heavy one, as before. The table:limit422;busy503.planner/service/README.md: the same two sentences on the classes, and theROUTE_WORKERSrow.
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 ofError::Memory, the two rooms of the queue,idle_bytes, a test inqueue.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_limitinleg_batch.planner/router/src/shape.rs: change:Failure::Memory.planner/service/src/lib.rs: change: the status oflimitand ofError::Memory, a test.planner/service/src/http.rs: change:Gate, the class of a call, the comment ofMAX_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: aGateof 2 workers and a wait of 50 ms; one heavy call holds its permits; a second heavy call getsNone; 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, forplanner-servicealso with--no-default-features.- The OBCKit tests of the planner and of the import pass, as
companion-ios/README.mdsays. 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: trueof 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 of503 busyof the primary routes before and after.
Out of scope
- The worker count of 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_WORKERSwith the memory budget of the old engine; the count is thenavailable_parallelism(), because a worker of the overlay engine holds only its labels (under 10 MB, the epic), and the engine announces all ranges of a path at once, so more workers than CPUs add no reads in parallel (theannouncecall of the host of Route engine: the data layer on format 10 and the host interface #3302, which Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 uses). The heavy share staysmax(1, workers / 2). 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 classify their own conditions by the rule in the doc comment ofError. - The memory limits of the follower unit: Follower: installs that stay on disk, one fetch at a time, a failure state for each service #3306.
- A new method for alternatives (workstream 5 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000), and the three uses of
max_geometry(engine review F4).
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 answer503 busyat 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 answersMemory, the router now drops the cached profiles that no router holds and tries once. So an idle service answers a route or alimit. - 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.rsmaps the memory error toRouterLimit, andplanner/router/README.mdchanged 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.
Metadata
Metadata
Assignees
Labels
No labels
Activity