# System Design: [Ride-hailing dispatch name]

> Reference design for ride-hailing dispatch: ingesting driver locations,
> indexing them geospatially (geohash or H3), matching riders to drivers,
> estimating arrival times, managing the trip lifecycle and guaranteeing that
> a driver is never assigned to two trips. It includes a note on dynamic
> (surge) pricing. It follows the structure of the System Design Document
> template and is pre-filled with a worked design to adapt. Values marked
> *Example* are assumptions; local transport regulation may constrain
> pricing and data use, so treat those parts as a format, not legal advice.

<!--
Guidance: How to use this template
- Dispatch is local: most state belongs to one city. Fill 3.1 per largest
  city as well as globally, because the busiest city sets the shard size.
- Write the assignment invariant (7.5) first and test it with chaos tests;
  double assignment is the defect riders and drivers notice most.
- Decide what matching optimises (rider wait, driver idle time, total
  distance) with product and operations before choosing the algorithm.
- Location data is personal data. Record retention and access rules in 9.2.
-->

## Document control

<!-- Guidance: A design is a proposal until it is approved; record who decided and when. -->

| Field | Value |
|---|---|
| Document ID | [SDD-DISPATCH-001] |
| System / feature | [Rider-driver matching and trip lifecycle] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Author(s) | [@author] |
| Reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Related | [Marketplace PRD], [Pricing policy], [Privacy impact assessment] |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Tech lead | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Staff / principal engineer | [@name] | [Decision] | YYYY-MM-DD |
| SRE / operations | [@name] | [Decision] | YYYY-MM-DD |
| Marketplace / data science lead | [@name] | [Decision] | YYYY-MM-DD |
| Privacy and legal | [@name] | [Decision] | YYYY-MM-DD |

## Revision history

<!-- Guidance: Note what changed in the design, not the wording. -->

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft for design review |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Batched matching every 2 s instead of greedy nearest driver |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* City-sharded dispatch with single writer per city cell group |
| 1.0 | YYYY-MM-DD | [@name] | *Example:* Approved |

## Contents

<!-- Guidance: Keep aligned with the headings. -->

1. [Overview](#1-overview)
2. [Requirements](#2-requirements)
3. [Capacity estimation](#3-capacity-estimation)
4. [API design](#4-api-design)
5. [Data model](#5-data-model)
6. [High-level design](#6-high-level-design)
7. [Detailed design](#7-detailed-design)
8. [Scalability and performance](#8-scalability-and-performance)
9. [Reliability, security and operations](#9-reliability-security-and-operations)
10. [Trade-offs and alternatives](#10-trade-offs-and-alternatives)
11. [Delivery plan and risks](#11-delivery-plan-and-risks)
12. [Appendices](#12-appendices)

## 1. Overview

<!-- Guidance: One page that a busy reviewer can read alone: problem, proposed solution in a paragraph, and the decisions that need their attention. -->

### 1.1 Problem statement

[*Example:* Matching queries a relational table of driver positions with a
bounding box. At evening peak in our largest city the query takes 900 ms,
two dispatchers sometimes offer the same driver to two riders, and the
nearest driver by straight line is often across a river, 14 minutes away.]

### 1.2 Proposed solution

[*Example:* Driver apps send locations every 4 seconds to an ingestion
gateway. A location service keeps the latest position and state of every
online driver in memory, indexed by H3 cell, sharded by city. When a rider
requests a trip, the dispatch service for that city finds candidate drivers in
nearby cells, ranks them by road-network ETA from an ETA service, and assigns
in small batches to minimise total pickup time. Assignment is a
compare-and-set on the driver's state, so a driver can hold only one offer.
The trip service drives a trip state machine and notifies both apps.]

### 1.3 Decisions requested from reviewers

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Geohash, S2 or H3? | H3 at resolution 9 for supply, 7 for pricing | 7.2, 10 |
| Q-02 | *Example:* Greedy or batched matching? | Batched every 2 s, greedy fallback under load | 7.3 |
| Q-03 | *Example:* How is double assignment prevented? | Single writer per city shard + CAS on driver state with offer TTL | 7.5 |
| Q-04 | *Example:* Location history retention? | 30 days raw, then aggregated and de-identified | 9.2 |
| [Q-nn] | [Question] | [Option] | [Section] |

## 2. Requirements

<!-- Guidance: Functional requirements describe behaviour; non-functional requirements describe qualities with numbers. Mark what is out of scope so nobody designs for it. -->

### 2.1 Functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* Drivers go online and offline and share location while online | Must |
| FR-02 | *Example:* Riders see nearby drivers and an ETA before requesting | Must |
| FR-03 | *Example:* Request a ride; get a driver offer accepted within 30 s or a clear "no drivers" | Must |
| FR-04 | *Example:* Drivers accept or decline offers within 15 s | Must |
| FR-05 | *Example:* Live trip tracking for rider and driver | Must |
| FR-06 | *Example:* Cancellation by either side with defined fees | Must |
| FR-07 | *Example:* Dynamic pricing per area based on supply and demand | Should |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Matching latency | *Example:* Request to first offer p95 at or below 3 s | Dispatch metrics |
| NFR-02 | Correctness | *Example:* Zero drivers holding two active offers or trips | Invariant checker |
| NFR-03 | Location freshness | *Example:* Driver position used for matching at most 10 s old | Age at match time |
| NFR-04 | Availability | *Example:* 99.99% for ride requests per city | Synthetic requests |
| NFR-05 | ETA accuracy | *Example:* Median absolute error at or below 1 min for pickups under 10 min | Predicted vs. actual |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 2.3 Out of scope

- [*Example:* shared rides (pooling) with multiple pickups]
- [*Example:* scheduled rides booked days ahead]
- [*Example:* payments (handled by the payments platform)]
- [Item deferred, with the release that will take it]

## 3. Capacity estimation

<!-- Guidance: Back-of-the-envelope numbers decide the shape of the design. Show inputs, formulas and results; round generously and say which way you rounded. -->

### 3.1 Assumptions

| Input | Symbol | Value | Source |
|---|---|---|---|
| Online drivers at global peak | $D$ | *Example:* 1 million | Supply data |
| Location update interval | $\Delta$ | *Example:* 4 s | App setting |
| Trips per day | $T$ | *Example:* 20 million | Demand data |
| Peak to average factor | $k$ | *Example:* 3 | Evening peak |
| Candidates scored per request | $c$ | *Example:* 10 | 7.3 |
| Location record (ID, lat, lng, heading, speed, time, state) | $s$ | *Example:* 50 bytes | Schema |
| Largest city share of global peak | $f$ | *Example:* 8% | Market data |

### 3.2 Location ingestion

$$
U = \frac{D}{\Delta} = \frac{10^{6}}{4} = 250\,000 \ \text{updates/s}
$$

$$
B_{in} = U \times s = 250\,000 \times 50 \ \text{B} = 12.5 \ \text{MB/s}
$$

Latest-position state in memory: $10^{6} \times 100$ B (with index overhead)
$= 100$ MB globally, about 8 MB for the largest city. Memory is not the
constraint; update rate and fan-out to rider apps are.

### 3.3 Requests and ETA calls

$$
QPS_{req} = \frac{T}{86\,400} \times k = \frac{2 \times 10^{7}}{86\,400} \times 3 \approx 700 \ \text{requests/s at peak}
$$

$$
QPS_{eta} = QPS_{req} \times c \approx 7\,000 \ \text{ETA computations/s}
$$

plus pre-request ETA previews (*Example:* 5 per request) at about 3 500/s.
In the largest city, $f \times 700 \approx 56$ requests/s.

### 3.4 Location history

$$
S_{day} = 12.5 \ \text{MB/s} \times 86\,400 \ \text{s} \approx 1.08 \ \text{TB/day} \quad (\text{upper bound at constant peak})
$$

Thirty days of raw history is at most about 32 TB, compressed several times
in columnar storage.

### 3.5 Summary

| Quantity | Estimate | Design consequence |
|---|---|---|
| Location updates | 250 000/s | Stateless ingest, partitioned stream, in-memory latest state |
| Requests | ~700/s global peak, ~56/s in largest city | Dispatch per city shard is small and fast |
| ETA | ~10 000/s incl. previews | Dedicated routing service with precomputed graph |
| History | ~1 TB/day | Columnar store with TTL; access controlled |

## 4. API design

<!-- Guidance: Define the contract first: resources, methods, request and response shapes, errors, idempotency, pagination, rate limits and versioning. Use RFC 9457 problem details for errors. -->

### 4.1 Endpoints and channels

| Channel | Operation | Purpose | Idempotent |
|---|---|---|---|
| Driver stream (WebSocket or gRPC stream) | `location` | Position, heading, speed, timestamp | Last-write-wins by timestamp |
| Driver stream | `offer` (server to driver), `accept`, `decline` | Trip offers | Accept deduplicated by `offerId` |
| HTTPS POST | `/v1/trips` | Rider requests a trip | `Idempotency-Key` required |
| HTTPS GET | `/v1/estimates?pickup=&dropoff=` | Price and pickup ETA preview | Yes |
| HTTPS POST | `/v1/trips/{id}:cancel` | Cancel by rider or driver | Yes |
| Rider stream | `trip_update` | Driver position and state during trip | Client keeps latest |

### 4.2 Request and response examples

A ride request carries the price quote the rider saw, so the server can
honour it or ask for confirmation if it expired:

```http
POST /v1/trips HTTP/1.1
Content-Type: application/json
Idempotency-Key: 3b1f6a0e-9a52-4c1e-8f3e-6c4d2a1b7e90

{"pickup": {"lat": 52.52003, "lng": 13.40495}, "dropoff": {"lat": 52.50754, "lng": 13.37603}, "product": "standard", "quoteId": "q_77Z1"}
```

```http
HTTP/1.1 202 Accepted
Content-Type: application/json

{"tripId": "t_5HX9", "state": "matching", "quoteExpiresAt": "2026-03-14T19:05:00Z"}
```

### 4.3 Errors

| Status | Problem type | When |
|---|---|---|
| 409 | `active-trip-exists` | Rider already has an active trip |
| 410 | `quote-expired` | Quote expired; client fetches a new estimate |
| 422 | `outside-service-area` | Pickup outside operating zones |
| 503 | `no-supply` | No drivers available; retry suggested after N seconds |

## 5. Data model

<!-- Guidance: Choose storage by access pattern, not by habit. Show entities, keys, partitioning and the queries each store must answer. -->

### 5.1 Entities

Driver supply state is hot and in memory; trips are durable records with a
strict lifecycle.

```mermaid
erDiagram
  DRIVER {
    string driver_id PK
    string city_id
    string vehicle_class
    float rating
  }
  DRIVER_STATE {
    string driver_id PK
    string status
    string h3_cell
    float lat
    float lng
    datetime updated_at
    string offer_id
    bigint version
  }
  TRIP {
    string trip_id PK
    string city_id
    string rider_id
    string driver_id
    string state
    string quote_id
    datetime requested_at
  }
  OFFER {
    string offer_id PK
    string trip_id FK
    string driver_id FK
    datetime expires_at
    string outcome
  }
  PRICE_CELL {
    string h3_cell PK
    datetime window_start PK
    float multiplier
    int open_requests
    int idle_drivers
  }
  DRIVER ||--|| DRIVER_STATE : "has"
  TRIP ||--o{ OFFER : "offered via"
  DRIVER ||--o{ OFFER : receives
  DRIVER ||--o{ TRIP : drives
```

### 5.2 Storage choices

| Data | Store | Partition key | Main queries | Why |
|---|---|---|---|---|
| Driver state and cell index | In-memory store per city shard (replicated) | `city_id`, then `h3_cell` | Drivers in a set of cells with status available | Microsecond lookups; rebuilt from stream within seconds |
| Trips and offers | Relational database sharded by `city_id` | `trip_id` | Get trip; active trip by rider or driver | Transactions for state changes |
| Location stream | Partitioned log | `driver_id` | Replay to rebuild state; history sink | Durable buffer |
| Location history | Columnar store with 30-day TTL | Day, city | Trip reconstruction, safety investigations | Cheap scans, access-controlled |
| Road graph and traffic | ETA service memory, rebuilt daily with live speeds | Region | Shortest-time paths | Precomputed for speed |

## 6. High-level design

<!-- Guidance: One diagram that shows every component on the request paths and where state lives. Name components by responsibility. -->

Each city (or large metro region) is served by its own dispatch shard; only
ingestion, ETA and storage are shared services.

```mermaid
flowchart LR
  dapp([Driver app]) --> ingest[Location gateway]
  ingest --> stream[[Location stream by driver]]
  stream --> loc[Location service, per city]
  loc --> idx[(Driver state + H3 index)]
  rapp([Rider app]) --> api[Trip API]
  api --> trip[Trip service]
  trip --> tdb[(Trips DB, by city)]
  trip --> disp[Dispatch, per city]
  disp --> idx
  disp --> eta[ETA service]
  eta --> roadgraph[(Road graph + live traffic)]
  disp -->|offer| push[Driver connection gateway]
  push --> dapp
  trip --> rpush[Rider updates]
  rpush --> rapp
  stream --> hist[(Location history)]
  stream --> price[Pricing aggregator]
  price --> pc[(Price cells)]
  api --> pc
```

| Component | Responsibility | Scales by |
|---|---|---|
| Location gateway | Authenticate drivers, validate and timestamp updates, publish | Stateless replicas |
| Location service | Maintain latest state and H3 index per city | City shards |
| Dispatch | Collect requests, find candidates, batch-match, issue offers | City shards (single writer per shard) |
| ETA service | Road-network travel time with live traffic | Replicas per region |
| Trip service | Trip state machine, cancellations, notifications | Stateless, DB sharded by city |
| Pricing aggregator | Supply and demand per cell, multipliers | Stream partitions |
| [Component] | [Responsibility] | [Scaling unit] |

## 7. Detailed design

<!-- Guidance: Go deep on the parts that are new, risky or contested. Show the sequence of calls and the failure behaviour of each step. -->

### 7.1 Location ingestion

Updates carry a device timestamp and a server receive timestamp; the location
service applies an update only if it is newer than the stored one
(last-write-wins by device time, rejected if more than 30 s in the future).
Out-of-order and duplicate updates are therefore harmless. Implausible jumps
(speed above 200 km/h between fixes) are flagged for anti-fraud and not used
for matching.

### 7.2 Geospatial index

| Option | Cell shape | Neighbour search | Notes |
|---|---|---|---|
| Geohash | Rectangles, varying size by latitude | 8 neighbours plus edge cases at cell boundaries | Simple, string prefix friendly |
| S2 | Quadrilaterals on a cube projection | Cell coverings | Good for arbitrary regions |
| H3 | Hexagons (with 12 pentagons globally) | `gridDisk(k)`: all neighbours are equidistant | Uniform neighbour distance suits radius search and pricing |

The design uses H3 resolution 9 (average cell area about 0.1 km², edge about
175 m) for driver lookup and resolution 7 (about 5 km²) for pricing. A
candidate search starts with `gridDisk(origin, 2)` (19 cells, roughly a 0.8 km
radius), widening to $k = 4$ (61 cells) and $k = 8$ (217 cells) if fewer
than 10 available drivers are found. The number of cells in a disk of radius
$k$ is $3k(k+1) + 1$.

### 7.3 Matching algorithm

Greedy "nearest available driver per request" is simple but globally
wasteful when requests cluster. Instead, dispatch collects requests for a
window of $w = 2$ s per shard and solves an assignment problem:

$$
\min \sum_{i \in R} \sum_{j \in D} x_{ij}\, \text{ETA}_{ij} \quad \text{s.t.} \quad \sum_{j} x_{ij} \le 1,\ \ \sum_{i} x_{ij} \le 1,\ \ x_{ij} \in \{0, 1\}
$$

with a penalty for leaving a request unmatched. For a window with tens of
requests and hundreds of candidates, the Hungarian algorithm or a min-cost
flow solves this in milliseconds. Candidate edges are pruned to each
request's 10 nearest drivers by straight-line distance before ETA is computed.
Under overload (window larger than 200 requests) the shard falls back to
greedy matching. Other factors (driver acceptance probability, vehicle class,
fairness of trip distribution among drivers) enter as cost adjustments
agreed with operations.

### 7.4 Request to assignment (critical path)

The rider gets an assigned driver after one batch window and the driver's
acceptance.

```mermaid
sequenceDiagram
  participant R as Rider app
  participant T as Trip service
  participant D as Dispatch (city shard)
  participant L as Driver state index
  participant E as ETA service
  participant G as Driver gateway
  participant V as Driver app
  R->>T: POST /trips (Idempotency-Key)
  T->>T: create trip (matching)
  T->>D: match request
  D->>L: available drivers in gridDisk(pickup, 2)
  L-->>D: 23 candidates
  D->>E: ETA for top 10 per request
  E-->>D: ETAs
  D->>D: solve batch assignment (2 s window)
  D->>L: CAS driver available -> offered (version)
  alt CAS succeeds
    D->>G: offer (expires in 15 s)
    G->>V: offer
    V-->>G: accept
    G-->>D: accept(offerId)
    D->>L: offered -> on_trip
    D->>T: driver assigned
    T-->>R: driver, vehicle, ETA
  else CAS fails or decline or timeout
    D->>D: put request back in next window, exclude driver
  end
```

### 7.5 Consistency of driver assignment

- **Invariant**: a driver is in at most one of `offered` or `on_trip` for at
  most one trip at any time.
- **Single writer**: one dispatch process owns a city shard at a time,
  elected through a lease with a fencing token; it is the only writer of
  driver status in that shard.
- **Compare-and-set**: status changes are conditional on the stored
  `version`, so even a stale former leader (old fencing token) cannot
  overwrite. Offers expire after 15 s; an expiry reverts `offered` to
  `available` unless an accept arrived first.
- **Durable outcome**: the accepted assignment is written to the trips
  database transactionally (trip state and driver ID together); the in-memory
  index is a cache of supply state that can be rebuilt from the stream and
  the trips database after failover.
- **Cross-shard edges**: a driver near a city boundary belongs to the shard
  of their current cell; shards hand a driver over on cell change through the
  location stream, never by both shards writing.

### 7.6 Trip state machine

Trip states are persisted; every transition is validated against this
diagram, and both apps render from it.

```mermaid
stateDiagram-v2
  [*] --> requested
  requested --> matching
  matching --> driver_assigned: driver accepted
  matching --> no_drivers: timeout 60 s
  matching --> cancelled: rider cancels
  driver_assigned --> driver_arrived: within 50 m of pickup
  driver_assigned --> cancelled: rider or driver cancels
  driver_assigned --> matching: driver cancels, rematch
  driver_arrived --> in_progress: trip started
  driver_arrived --> cancelled: no-show after 5 min
  in_progress --> completed: trip ended
  completed --> [*]
  cancelled --> [*]
  no_drivers --> [*]
```

### 7.7 ETA service

Travel times come from a road graph with precomputed shortcuts (for example
contraction hierarchies) and live segment speeds from recent trips, updated
every minute. A learned correction model adjusts the route-based estimate for
pickup-specific delays such as entering a station forecourt. ETAs used for
matching are cached per (driver cell, pickup cell) pair for 30 s.

### 7.8 Surge pricing note

Every minute, the pricing aggregator computes per resolution-7 cell the ratio
of open requests to idle drivers, smooths it over neighbouring cells and time,
and maps it to a multiplier through a capped, monotonic curve. Riders see the
price before confirming (the quote ID in 4.2 locks it for a few minutes).
Pricing rules are subject to local regulation (caps during emergencies,
disclosure requirements) and must be reviewed by legal and policy teams per
market.

## 8. Scalability and performance

<!-- Guidance: Show how the design meets the numbers in section 3 and where it will break first. -->

| Concern | Approach | Limit before redesign |
|---|---|---|
| Location updates | Partitioned stream; per-city consumers | *Example:* ~50 000 updates/s per city shard |
| Large metros | Split a metro into several shards by H3 resolution-5 parent cells | Hand-off overhead at shard boundaries |
| ETA load | Cache by cell pair; precomputed graph | ~20 000 queries/s per region cluster |
| Rider tracking fan-out | Only riders with an active trip subscribe to their driver | [Limit] |
| Batch solver | Window and candidate pruning | Greedy fallback above 200 requests per window |

Latency budget from request to offer sent (target p95 3 s):

| Step | Budget |
|---|---|
| Trip creation | 100 ms |
| Waiting for batch window (average half of 2 s) | 1 000 ms |
| Candidate lookup | 10 ms |
| ETA calls | 150 ms |
| Solve and CAS | 50 ms |
| Offer delivery to driver app | 300 ms |
| Headroom | 1 390 ms |

## 9. Reliability, security and operations

<!-- Guidance: Name the failure modes, the threats and the signals operators watch. Each mitigation should be testable. -->

### 9.1 Failure modes

| Failure | Impact | Detection | Mitigation |
|---|---|---|---|
| Dispatch shard leader dies | Matching pauses in that city | Lease loss | Standby takes over within 5 s; rebuilds state from stream and trips DB |
| Location stream lag | Stale positions, poor matches | Consumer lag, position age at match | Exclude drivers with position older than 10 s; alert |
| ETA service down | Poor ranking | Error rate | Fallback to straight-line distance x city speed factor |
| Driver app offline after accept | Rider waits | Missed heartbeats on trip | After 60 s without heartbeat, offer rematch to rider |
| Trips DB shard down | Requests fail in a city | Error rate | Synchronous standby; requests rejected with clear message, not silently queued |
| [Failure] | [Impact] | [Signal] | [Mitigation] |

### 9.2 Security, privacy and abuse

| Threat | Control |
|---|---|
| GPS spoofing by drivers | Plausibility checks, device attestation, anomaly models |
| Exposure of rider and driver locations | Precise driver location shown only to the matched rider during the trip; nearby-car display uses jittered positions |
| Location history misuse | Role-based access, purpose logging, 30-day raw retention, de-identified aggregates afterwards |
| Fake requests to manipulate surge | Account trust scores; requests without confirmed payment method excluded from demand |
| [Threat] | [Control] |

### 9.3 Observability

| Signal | Metric or log | Alert threshold |
|---|---|---|
| Time to match | Request to accept p95 per city | Above 30 s for 10 min |
| Unmatched rate | `no_drivers` / requests | Above 5% (marketplace alert) |
| Invariant | Drivers with more than one active offer or trip | Any |
| Position age | Age at match time p99 | Above 10 s |
| ETA error | Predicted vs. actual pickup | Median above 1.5 min |

### 9.4 Cost estimate

| Item | Unit cost | Quantity | Monthly cost |
|---|---|---|---|
| Ingestion and stream | [$/node-month] | [n] | [$] |
| Dispatch shards (leader + standby per city) | [$/node-month] | *Example:* 2 x 300 cities, small nodes | [$] |
| ETA service | [$/node-month] | [n] | [$] |
| Location history storage | [$/TB-month] | *Example:* ~32 TB raw, less after compression | [$] |
| Map data licence | [$/month] | [Licence] | [$] |
| **Total** | | | **[$]** |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why you chose one. Reviewers will propose the alternatives anyway; answer them here. -->

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Spatial index | Geohash; S2; H3; database geo index | H3 | Equidistant neighbours, same cells for pricing and supply | Hexagons do not nest exactly; pentagon edge cases |
| Matching | Greedy nearest; batched assignment; driver broadcast (first to accept wins) | Batched assignment | Lower total pickup time, fair to drivers | Up to 2 s added wait |
| Assignment safety | Distributed lock service; single writer per shard + CAS | Single writer + CAS | No extra lock round trip, simple reasoning | Shard failover pause of a few seconds |
| Driver state store | Database; in-memory per shard | In-memory, rebuilt from stream | Speed at 250 000 updates/s | Rebuild needed after failover |
| Distance metric | Straight line; road ETA | Road ETA for top candidates | Avoids "across the river" matches | ETA service cost and dependency |
| [Decision] | [Options] | [Chosen] | [Why] | [Cost] |

## 11. Delivery plan and risks

<!-- Guidance: How the design reaches production safely, and what could stop it. -->

### 11.1 Milestones

| Milestone | Scope | Exit criterion | Target date |
|---|---|---|---|
| M1 | Location pipeline and H3 index in one city (shadow) | Position age p99 under 10 s | YYYY-MM-DD |
| M2 | Greedy dispatch with CAS assignment in one city | Zero invariant violations for 30 days | YYYY-MM-DD |
| M3 | Batched matching | Pickup ETA down 10% in A/B by city | YYYY-MM-DD |
| M4 | All cities, surge v2 | Per-market legal sign-off | YYYY-MM-DD |

### 11.2 Rollout and rollback

[*Example:* Switch city by city during off-peak hours, with the old dispatch
kept warm in shadow mode. Rollback switches the city's request routing back;
active trips continue in the trip service, which both dispatchers share.]

### 11.3 Risks

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Batch window increases perceived wait | Medium | Medium | Adaptive window (0.5-2 s) by demand | [@name] |
| R-02 | *Example:* Shard failover during peak causes matching gap | Low | High | Hot standby consuming the same stream | [@name] |
| R-03 | *Example:* Surge rules breach local regulation | Medium | High | Per-market caps and legal review | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

<!-- Guidance: Supporting detail, glossary and open questions. -->

### 12.1 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Do we let drivers see destination before accepting? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* Airport queues: first-in-first-out or matching? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.2 Glossary

| Term | Meaning |
|---|---|
| H3 | Hierarchical hexagonal geospatial index |
| `gridDisk(k)` | All H3 cells within k steps of a cell |
| CAS | Compare-and-set: update only if the stored version matches |
| Offer | Time-limited proposal of a trip to one driver |
| Surge multiplier | Price factor applied in an area when demand exceeds supply |
| [Term] | [Meaning] |

### 12.3 References

| Reference | Use |
|---|---|
| H3 documentation (h3geo.org) | Cell resolutions and grid functions in 7.2 |
| Kuhn, "The Hungarian Method for the Assignment Problem" (1955) | Assignment algorithm in 7.3 |
| Geisberger et al., "Contraction Hierarchies" (2008) | Routing in 7.7 |
| [Local transport regulations per market] | Pricing constraints in 7.8 |

## Standard and licence note

Based on common industry practice for ride-hailing dispatch design and on the
public references in 12.3. This is a reference design to adapt, with
illustrative numbers; pricing and data-retention sections are a format, not
legal advice. Original text written for this collection. Template licence: MIT.