Marketplace, Dispatch, and Logistics System Design Questions

Direct answer

Model each driver with a constant-velocity Kalman filter: the hidden state is position and velocity in a local metric frame, each GPS ping is a noisy measurement of position, and every ping runs one predict step (move the state forward by the elapsed time and grow the uncertainty) and one update step (pull the state toward the ping in proportion to how much we trust it). A Kalman filter is the optimal estimator when the motion is roughly linear and the noise roughly Gaussian (bell-shaped), and it costs a few hundred multiply-adds and about 150 bytes of state per driver, so it runs comfortably for a whole fleet. I add a gate that rejects implausible pings (multipath jumps), a reset for genuine manoeuvres, and a backward smoothing pass for completed trips. I would switch to a particle filter when the uncertainty is not one blob: at a fork where the driver is on one of two roads, or when the road network itself should constrain the estimate.

The model

Work in metres, not degrees: convert each latitude and longitude to east and north offsets from a nearby reference point (a local tangent plane). Degrees of longitude shrink toward the poles, so filtering raw degrees would make noise direction-dependent.

State vector (what we estimate):

east and north position in metres, east and north velocity in metres per second.

Motion model (how the state evolves over a gap of Δt seconds): position moves by velocity times time, velocity stays the same apart from random acceleration.

Process noise Q (how much the real motion can deviate from constant velocity): model an unknown acceleration with standard deviation σ_a. For each axis, the position and velocity block is

These powers of Δt come from treating the unmodelled acceleration as a small random push held roughly constant over the gap and integrating it twice: once for its effect on velocity, which scales with Δt (so the variance it contributes scales with Δt²), and again for its effect on position, which scales with Δt² (so the variance it contributes scales with Δt⁴, discounted by 1/4 from the integration). The cross term (Δt³/2) is smaller because it needs only one of the two integrations. The part that matters for using the filter: a longer gap between pings should inflate position uncertainty faster than velocity uncertainty, and this matrix does that automatically. Because Q depends on Δt, irregular pings (3 s, then 11 s, then 4 s) are handled naturally: a long gap simply grows the uncertainty more.

Measurement model: a ping observes position only, so H picks the first two state entries. Measurement noise R comes from the accuracy radius the phone reports with every fix, so a 50 m-accuracy fix is trusted far less than a 5 m one:

Update equations

Predict, then correct. P is the 4 × 4 covariance: the filter's own running estimate of how uncertain the state is, both how large each quantity's uncertainty is and how two quantities' errors move together (for example, a positive entry linking east position and east velocity means: if the position estimate turns out too high, the velocity estimate is probably too high as well). Two notations recur below: $F^{\top}$ is F's transpose (rows and columns swapped) and $S^{-1}$ is S's matrix inverse (the matrix that undoes it, playing the role "divide by S" plays for ordinary numbers); a linear-algebra library computes both directly.

In words: the predict step, $P^{-} = FPF^{\top} + Q$, carries the old uncertainty forward through the motion model and then adds Q, so uncertainty only ever grows on a predict, never shrinks, because every additional second is a second in which the unmodelled acceleration could have pushed the car off the predicted track. y (the innovation) is how far the ping is from where we expected the driver; S is how far we would expect it to be given both uncertainties; K (the Kalman gain) is the blend weight, near 1 when the prediction is vague and near 0 when the prediction is sharp and the ping is noisy. The update step, $P = (I-KH)P^{-}$, then shrinks the uncertainty by removing the part the new measurement has just resolved: a larger K (more trust placed in the ping) removes more, which is why a driver whose recent pings have been consistently trustworthy ends up with a tighter, more confident position estimate.

Outlier gate. Before updating, compute the squared Mahalanobis distance (distance measured in units of expected spread) of the innovation:

For a 2-D Gaussian, d² follows a chi-square distribution with 2 degrees of freedom (the distribution of a sum of two squared, independent standard-normal values, one per axis here), which exceeds 9.21 only 1% of the time, so a larger value marks the ping as suspect. One suspect ping is treated as multipath and dropped (the filter coasts on its prediction). Two suspect pings in a row usually mean the driver genuinely turned or braked, so the filter re-initialises from those two pings rather than rejecting reality forever.

Short-term predictor. To estimate position τ seconds after the last ping, run the predict step alone with Δt = τ; the covariance tells you how wide the uncertainty has become.

Smoother. For a completed window (a finished trip, used for distance, fares or training data) run the Rauch-Tung-Striebel (RTS) backward pass, which revises each past estimate using the pings that came after it.

Worked step, by hand

One predict-then-update cycle with round numbers, so the equations above can be checked without running code. Start from state $\hat{x} = [0, 0, 10, 0]$ (east 0 m, north 0 m, east velocity 10 m/s, north velocity 0), $P = \text{diag}(25, 25, 4, 4)$ (5 m position uncertainty, 2 m/s velocity uncertainty on each axis, no cross-correlation yet), a gap of Δt = 4 s, σ_a = 1.0 m/s², σ_gps = 8 m, and a new ping at $z = [42, 3]$.

Predict. $\hat{x}^{-} = F\hat{x} = [0+4(10),\ 0+4(0),\ 10,\ 0] = [40, 0, 10, 0]$: the car is predicted 40 m east, still moving at 10 m/s. For Q: Δt⁴/4 = 256/4 = 64, Δt³/2 = 64/2 = 32, Δt² = 16, so $Q_{\text{axis}} = \begin{bmatrix} 64 & 32 \\ 32 & 16 \end{bmatrix}$. Working the east axis alone (position and velocity; the two axes never mix), $F_{\text{axis}} P_{\text{axis}} F_{\text{axis}}^{\top} = \begin{bmatrix} 89 & 16 \\ 16 & 4 \end{bmatrix}$, so $P^{-}_{\text{axis}} = \begin{bmatrix} 89+64 & 16+32 \\ 16+32 & 4+16 \end{bmatrix} = \begin{bmatrix} 153 & 48 \\ 48 & 20 \end{bmatrix}$: position uncertainty grew from 25 to 153, exactly the growth the "uncertainty only grows on predict" rule above predicts; the north axis starts from the same numbers and gets the same block.

Update. Innovation $y = z - H\hat{x}^{-} = [42-40,\ 3-0] = [2, 3]$. Because the axes do not mix, $S = P^{-}_{ee} + \sigma_{\text{gps}}^2 = 153 + 64 = 217$ on each axis (ee meaning the position-position entry). The Kalman gain per axis is $K_{\text{axis}} = [153, 48]^{\top} / 217 = [0.705, 0.221]$: 0.705 says move the position estimate 70.5% of the way to the ping, and 0.221 says nudge the velocity estimate by 22.1% of the same gap. New state: east position $40 + 0.705(2) = 41.41$, east velocity $10 + 0.221(2) = 10.44$; north position $0 + 0.705(3) = 2.12$, north velocity $0 + 0.221(3) = 0.66$, giving $\hat{x} = [41.41,\ 2.12,\ 10.44,\ 0.66]$. New covariance per axis, $(I-K_{\text{axis}}H_{\text{axis}})P^{-}_{\text{axis}}$, works out to $\begin{bmatrix} 45.1 & 14.2 \\ 14.2 & 9.4 \end{bmatrix}$: position uncertainty shrank from 153 to 45.1, well below where it started (25) because this ping was informative, but not to 0, because the ping itself is noisy (σ_gps = 8 m). The Mahalanobis distance is $d^2 = y^{\top}S^{-1}y = (2^2 + 3^2)/217 = 13/217 \approx 0.06$, far under the 9.21 gate, so this ping updates normally. These are exactly the numbers the DriverKF class below produces when it is stepped once with the same inputs.

Runnable implementation

This runs as shipped (Python 3 with numpy). It simulates one driver going east at 10 m/s for 60 s, turning a right angle, then going north, with pings every 3 to 5 s, 8 m GPS noise and one 150 m multipath jump, and it compares two values of σ_a.

import numpy as np

GATE = 9.21  # chi-square with 2 degrees of freedom at 99%: larger innovations are suspect
H = np.array([[1.0, 0, 0, 0],
              [0, 1.0, 0, 0]])          # we observe position only

def motion(dt, sigma_a):
    """Constant-velocity model over dt seconds. Q comes from a random acceleration of std sigma_a."""
    F = np.array([[1.0, 0, dt, 0],
                  [0, 1.0, 0, dt],
                  [0, 0, 1.0, 0],
                  [0, 0, 0, 1.0]])
    block = sigma_a**2 * np.array([[dt**4 / 4, dt**3 / 2],
                                   [dt**3 / 2, dt**2]])
    Q = np.zeros((4, 4))
    Q[np.ix_([0, 2], [0, 2])] = block    # x with vx
    Q[np.ix_([1, 3], [1, 3])] = block    # y with vy
    return F, Q

class DriverKF:
    """State x = [east_m, north_m, v_east, v_north] in a local metric frame."""
    def __init__(self, t0, z0, acc_m, sigma_a):
        self.t, self.sigma_a = t0, sigma_a
        self.x = np.array([z0[0], z0[1], 0.0, 0.0])
        self.P = np.diag([acc_m**2, acc_m**2, 15.0**2, 15.0**2])
        self.history = []            # per ping: (x_pred, P_pred, x_filt, P_filt, F, was_reset)
        self.pending = None          # previous ping, if it was gated out

    def update(self, t, z, acc_m):
        z = np.asarray(z, dtype=float)
        dt = t - self.t
        F, Q = motion(dt, self.sigma_a)
        x_pred = F @ self.x                          # 1. predict
        P_pred = F @ self.P @ F.T + Q
        R = np.eye(2) * acc_m**2                     # 2. measurement noise from the phone's accuracy
        y = z - H @ x_pred                           # 3. innovation
        S = H @ P_pred @ H.T + R
        d2 = float(y @ np.linalg.solve(S, y))        # 4. squared Mahalanobis distance
        reset = False
        if d2 <= GATE:                               # 5a. normal Kalman update
            K = P_pred @ H.T @ np.linalg.inv(S)
            x_new, P_new = x_pred + K @ y, (np.eye(4) - K @ H) @ P_pred
            action = "update"
        elif self.pending is not None:               # 5b. two surprises in a row: a real manoeuvre
            t0, z0 = self.pending
            v = (z - z0) / (t - t0)
            x_new = np.array([z[0], z[1], v[0], v[1]])
            P_new = np.diag([acc_m**2, acc_m**2, 5.0**2, 5.0**2])
            action, reset = "reset", True
        else:                                        # 5c. lone surprise: treat as multipath, coast
            x_new, P_new = x_pred, P_pred
            action = "dropped"
        self.pending = (t, z) if action == "dropped" else None
        self.history.append((x_pred, P_pred, x_new, P_new, F, reset))
        self.t, self.x, self.P = t, x_new, P_new
        return action, d2

    def predict_ahead(self, tau):
        F, Q = motion(tau, self.sigma_a)
        return F @ self.x, F @ self.P @ F.T + Q

def rts_smooth(history):
    """Rauch-Tung-Striebel backward pass. A reset breaks the chain, so we never smooth across one."""
    xs = [h[2].copy() for h in history]
    Ps = [h[3].copy() for h in history]
    for k in range(len(history) - 2, -1, -1):
        x_pred1, P_pred1, _, _, F1, reset1 = history[k + 1]
        if reset1:
            continue
        C = history[k][3] @ F1.T @ np.linalg.inv(P_pred1)
        xs[k] = history[k][2] + C @ (xs[k + 1] - x_pred1)
        Ps[k] = history[k][3] + C @ (Ps[k + 1] - P_pred1) @ C.T
    return xs

# ---- simulated drive: 10 m/s east for 60 s, then a right-angle turn to 10 m/s north ----
rng = np.random.default_rng(7)
def truth(t):
    return np.array([10.0 * t, 0.0]) if t <= 60 else np.array([600.0, 10.0 * (t - 60)])

times = np.cumsum(rng.uniform(3.0, 5.0, size=30))         # irregular pings, 3-5 s apart
SIGMA_GPS = 8.0
pings = [truth(t) + rng.normal(0, SIGMA_GPS, 2) for t in times]
MULTIPATH = 8
pings[MULTIPATH] = pings[MULTIPATH] + np.array([0.0, 150.0])  # one 150 m multipath jump
z_start = truth(0.0) + rng.normal(0, SIGMA_GPS, 2)            # first fix, at t=0

def rmse(estimates, skip=()):
    sq = [np.sum((e[:2] - truth(t))**2) for i, (e, t) in enumerate(zip(estimates, times)) if i not in skip]
    return np.sqrt(np.mean(sq))

print(f"raw GPS RMSE: {rmse(pings):.1f} m, or {rmse(pings, {MULTIPATH}):.1f} m without the multipath ping")
for sigma_a in (1.0, 2.0):
    kf = DriverKF(0.0, z_start, SIGMA_GPS, sigma_a)
    events = []
    for i, (t, z) in enumerate(zip(times, pings)):
        action, d2 = kf.update(t, z, SIGMA_GPS)
        if action != "update":
            events.append(f"ping {i} {action} (d2={d2:.1f})")
    filt = [h[2] for h in kf.history]
    smooth = rts_smooth(kf.history)
    x10, P10 = kf.predict_ahead(10.0)
    print(f"sigma_a={sigma_a}: {'; '.join(events)}")
    print(f"  RMSE filtered {rmse(filt):.1f} m, RTS smoothed {rmse(smooth):.1f} m, "
          f"10 s-ahead error {np.linalg.norm(x10[:2] - truth(times[-1] + 10.0)):.1f} m "
          f"(predicted 1-sigma per axis {np.sqrt(P10[0, 0]):.1f} m)")
    print(f"  filtered RMSE excluding the dropped ping's own timestep: {rmse(filt, {MULTIPATH}):.1f} m")

Output:

raw GPS RMSE: 29.2 m, or 9.7 m without the multipath ping
sigma_a=1.0: ping 8 dropped (d2=53.5); ping 15 dropped (d2=12.5); ping 16 reset (d2=11.4)
  RMSE filtered 17.7 m, RTS smoothed 15.3 m, 10 s-ahead error 36.7 m (predicted 1-sigma per axis 61.6 m)
  filtered RMSE excluding the dropped ping's own timestep: 16.9 m
sigma_a=2.0: ping 8 dropped (d2=26.3)
  RMSE filtered 12.1 m, RTS smoothed 6.4 m, 10 s-ahead error 45.5 m (predicted 1-sigma per axis 112.9 m)
  filtered RMSE excluding the dropped ping's own timestep: 9.2 m

What the run shows:

• Gating works on multipath. The 150 m jump (ping 8) is rejected under both settings. Raw GPS RMSE (root-mean-square error) is 29.2 m including that single point and 9.7 m without it.
• σ_a is the real design decision. With σ_a = 1.0 the filter believes cars barely accelerate, so the right-angle turn looks like an outlier: ping 15 is dropped and ping 16 triggers the reset. Filtered RMSE (17.7 m) is then worse than clean raw GPS, because coasting straight through a turn is badly wrong. With σ_a = 2.0 the turn is accepted, filtered RMSE is 12.1 m and smoothed is 6.4 m. The cost of the looser setting is a wider forecast: the 10 s-ahead 1-sigma grows from 61.6 m to 112.9 m.
• Why filtered RMSE (12.1 m) still looks worse than "raw GPS without the multipath ping" (9.7 m), even though gating worked. The two figures are not measuring the same thing. The clean-GPS benchmark simply deletes ping 8's timestep from the average, as if it never happened. The filter cannot do that: it still owes an estimate at that instant, and with the ping rejected it coasts on its prediction alone, so its error right there is large (the run's added line above shows 9.2 m once that one timestep is excluded from the filtered RMSE too, at σ_a = 2.0), and that one large error is still counted in the 30-point filtered RMSE. Excluded on both sides for a fair comparison, the filter (9.2 m) slightly beats the clean baseline (9.7 m), which is what a working filter should do on ordinary noise. The headline 12.1-vs-9.7 comparison is really "a filter that must answer every 4 seconds, including through one unavoidable coast" against "a benchmark that got to delete its one hard case".
• Filtering helps less than smoothing at sparse pings. At 4 s intervals the motion uncertainty between pings is comparable to GPS noise, so the online filter mostly removes outliers; the RTS pass, which sees future pings, is what halves the error. That is why fare distance should come from the smoothed trail.
• Pure extrapolation degrades fast. A 10 s-ahead error of 36.7 to 45.5 m comes almost entirely from velocity error: a 3 m/s velocity error becomes 30 m after 10 s.

Computational cost per update

Counting multiply-adds for the 4-state, 2-measurement filter: F times x is 16, F P Fᵀ is two 4 × 4 products (128), the gain and innovation work on 2 × 2 and 4 × 2 matrices (about 40, including inverting a 2 × 2), and the covariance update is about 96. That is roughly 280, call it 300, multiply-adds per ping, constant time.

Fleet-scale framing. At 1,000,000 online drivers pinging every 4 s, the fleet produces 250,000 updates per second, so 250,000 × 300 = 75 million multiply-adds per second: a small fraction of one core in compiled code. The real costs are elsewhere:

• State: per driver, 4 state values, 10 unique covariance values (P is symmetric), a timestamp, and the pending-ping slot (its time and two coordinates): 4 + 10 + 1 + 3 = 18 doubles of 8 bytes, 144 bytes. For 1,000,000 drivers that is 144 MB, which fits in memory on the location-service shards that already own those drivers.
• Per-call overhead: calling numpy per driver is dominated by interpreter overhead, not arithmetic. In production, either write the filter in a compiled language or batch drivers into arrays and update thousands at once.
• Co-location: run the filter where the latest-location state already lives (sharded by driver ID), so no extra network hop is added per ping.

Using it for pickup ETA

Do not predict pickup ETA (estimated time of arrival) by extrapolating the filter for minutes: velocity error grows linearly into position error, and the car will follow roads, not a straight line. Use the filter for what it is good at: a clean current position, speed and heading (and bridging a missed ping or two for the live map). Then feed that position, snapped to a road segment, into the routing and ETA service, which knows the road network and traffic. The filter's covariance is still useful downstream: when the 1-sigma position radius exceeds a threshold (for example after a long silence), mark the driver's location as low-confidence so dispatch widens its margin or asks the driver's app for a fresh fix.

When to prefer a particle filter

A particle filter represents the belief as many weighted samples ("particles"), each a concrete hypothesis such as "on Main Street at 12 m/s", instead of one Gaussian blob.

Choose a particle filter for map-constrained tracking in dense downtowns, for indoor or garage pickups where fixes are sparse and multimodal, or when the output must be a road position rather than a point. At fleet scale, run it only for drivers where it matters (en route to a pickup in a flagged area), not for all of them.

Pitfalls

• Filtering in degrees rather than metres.
• A fixed Q regardless of Δt, which trusts a 30 s-old prediction as much as a 3 s-old one.
• Gating without a reset rule: the filter locks onto its own prediction after a real turn and rejects every true ping that follows.
• Ignoring out-of-order pings: reject or buffer a ping older than the current state's timestamp instead of predicting backwards.

Direct answer

Do not pick one consistency model for the whole flow. Use strong consistency where a wrong answer costs money or a physical promise: the order's state machine, the payment record, and the "which driver holds this order" record. Use eventual consistency for everything users merely look at: status screens, maps, notifications, analytics. Stitch the steps together as a saga (a sequence of local transactions, each with a compensating action if a later step fails), and make every status update carry a version number so a client never shows an older state after a newer one.

Trade-offs for each choice

Strong consistency means every read sees the latest committed write (for a single record, this is called linearizable). Eventual consistency means replicas may briefly disagree but converge if writes stop.

Doing the whole flow strongly (one distributed transaction across order, payment and dispatch services) couples their availability: if any is down, no one can order. Doing it all eventually gets payments wrong. Hence the hybrid.

Hybrid design

flowchart LR
    A[Create order: CREATED] --> B[Authorize payment: hold funds]
    B -->|approved| C[PAYMENT_AUTHORIZED]
    B -->|declined| X[FAILED, nothing to undo]
    C --> D[Assign driver: CAS on driver record]
    D -->|driver accepts| E[DRIVER_ASSIGNED]
    D -->|no driver in 5 min| V[Void authorization, CANCELLED]
    E --> F[Trip completed: capture payment]

1. Create order in the order database with a client-supplied idempotency key (a unique id per checkout attempt, so a retried request returns the same order instead of creating a second). State CREATED, version 1.
2. Authorize the payment through the PSP (payment service provider, the company that talks to card networks) with the order id as the provider's idempotency key. Authorization places a hold on the rider's funds without moving money; capture happens later. The payment result and the order's state transition are written in one local transaction, and an outbox row (an event stored in the same transaction, published afterwards) announces PAYMENT_AUTHORIZED. This avoids "payment recorded but event lost".
3. Assign a driver only for orders in PAYMENT_AUTHORIZED. Dispatch runs as many independent matchers, each owning one geographic cell and periodically collecting a short batch of nearby requests to assign together rather than one at a time. The assignment is a compare-and-set (CAS) on the driver's record ("set to OFFERED for order o only if AVAILABLE and version v": update the record only if it still matches what was last read), so two matchers cannot both win. The order moves to DRIVER_ASSIGNED only after the driver accepts.
4. Capture the payment on trip completion (for the final fare), or void the authorization (cancel the hold and release the funds back to the rider, without ever moving money) if no driver is found or the rider cancels before pickup. Void and capture are the saga's compensation and completion steps; both are idempotent by order id.
5. Status to users flows from the order's events into a read model (a query-optimised copy, such as a cache or a push channel, a live connection like a WebSocket that pushes updates to the client instead of the client repeatedly asking) that is eventually consistent. Each status carries the order version; the client drops any update with a version lower than what it already shows.

Worked example: an anomaly and how the design handles it

Two matchers in adjacent cells both pick driver d9 for orders o1 and o2 within the same second.

• Matcher 1: CAS d9: AVAILABLE v12 to OFFERED(o1) succeeds, d9 is now v13.
• Matcher 2: CAS d9: AVAILABLE v12 to OFFERED(o2) fails, since the version is 13. Matcher 2 re-queues o2 into its next batch, about 2 seconds later.
• Rider o2 never saw "driver assigned", because the order only moves to DRIVER_ASSIGNED after a successful CAS plus driver accept. The only visible effect is a slightly longer "finding your driver".

Now the status-lag case: o1's status events are version 3 (PAYMENT_AUTHORIZED) and version 4 (DRIVER_ASSIGNED). If the push channel delivers 4 then 3, the client ignores 3, so the screen never flips back from "Driver on the way" to "Finding a driver".

Pitfalls

• Charging before assignment is certain: authorize, do not capture, until the trip happens; otherwise every "no driver found" becomes a refund, which is slower for the rider and costs fees.
• Authorizations expire: a hold does not last forever (the exact window depends on the card network and provider), so long scheduled bookings need re-authorization logic.
• Blocking dispatch on the payment provider: if the PSP is slow, orders queue. For trusted riders, one option is to authorize in parallel with matching and cancel the offer if authorization fails; it trades a small chance of a wasted driver trip for lower wait.
• Showing optimistic status: saying "driver assigned" when the offer was only sent (not accepted) is the most common source of user-visible reversals.

Direct answer

If each matcher instance only searches its own partition, a driver 50 m across the partition line from a rider is invisible, and the rider gets a farther driver or none. There are two fixes: query-time fan-out (search every partition the search circle touches, in parallel, and merge) and write-time halo replication (copy drivers within a strip of width h along each border into the neighbouring partition, so a local search already sees them). With the halo width set equal to the search radius, both cost the same geometric fraction; the halo pays it on every location update, fan-out on every search. Because location updates usually outnumber match searches several times over, I default to fan-out with neighbouring partitions co-located (run on the same host or process, so the fan-out call is a local function call rather than a network hop), and add a halo only on the specific borders where the extra network hop breaks the latency target. The owning partition always makes the final assignment, so a driver seen twice can never be assigned twice.

Terms

• Partition: the area one matcher instance is responsible for. It can be a grid square, a geohash prefix (geohash encodes a location as a short string where each extra character narrows the area, so everyone sharing a prefix falls in one cell), or a region.
• Halo (ghost or overlap region): read-only copies of drivers near a border, kept in the neighbouring partition's index.
• Fan-out / scatter-gather: sending one query to several partitions and merging the answers.
• p99: the 99th-percentile latency, the time 99% of calls finish within.
• Tail latency: how slow the slowest requests are (for example p99), as opposed to the average; a fan-out is only as fast as its slowest partition call.

How big the problem is

The search radius needed to find k candidates at a density of rho idle drivers per km²:

Why: a circle of radius r at density rho drivers per km² holds pi r² rho drivers on average, and r is chosen so that average equals k, giving the formula above.

With k = 8: a dense core at 40 drivers/km² needs r = 0.25 km; a suburb at 2 drivers/km² needs r = 1.13 km.

For square partitions of side L and a rider placed uniformly inside one, the chance the search circle leaves the partition is:

Why: the search circle stays fully inside the partition only when the rider is at least r from every one of the four edges, that is, only when the rider falls inside the smaller (L - 2r) square centred in the partition; P_cross is 1 minus the chance of landing in that inner square.

With L = 2 km and r = 0.25 km: 1 - (1.5/2)² = 0.4375, so 44% of searches touch at least one neighbour. Boundary effects are not an edge case.

Mitigation strategies

Cost analysis with numbers

With the halo width h equal to the search radius r, the expected number of extra partitions touched per search and the expected number of extra copies per driver have the same form (edges plus corners; the corner term is a slight overestimate, since a circle reaches a diagonal neighbour only when it is within r of the corner):

Why: a rider lands within h of one particular edge with probability about h/L, and there are four edges, giving the 4h/L term; the 4h²/L² term is the smaller extra chance of landing near a corner, where two edges' extra-partition contributions overlap.

For L = 2 km, h = 0.25 km: 4(0.125) + 4(0.015625) = 0.5625.

Worked example, one city: 20,000 active drivers sending a location every 4 s is 5,000 updates/s; the city runs 500 match searches/s.

• Halo: 0.5625 x 5,000 = about 2,812 extra index writes/s, and every partition also subscribes to its neighbours' border traffic.
• Fan-out: 0.5625 x 500 = about 281 extra partition reads/s.

The geometric factor cancels; the comparison is the ratio of update rate to search rate, here 10 to 1 in favour of fan-out. Memory is not the deciding cost (an index entry is on the order of a hundred bytes); write throughput and stream subscriptions are.

What fan-out costs instead is tail latency. If each partition call independently finishes within its p99 99% of the time, a query waiting on n calls finishes within that bound with probability 0.99ⁿ: 0.99 for one call, 0.9606 for four. So a four-way fan-out sees a slow partition about 4% of the time instead of 1%. Mitigations: place adjacent partitions on the same host where possible (fan-out becomes an in-process call), give neighbour calls a tight timeout and accept a partial result (the home partition's answer plus whatever returned), and hedge (send a duplicate request to a replica, a second copy of that partition's service holding the same data, if the first is slow).

Correctness with duplicated state

Halo copies are read-only and lag the owner by the stream delay. Correctness must not depend on them: an offer is made by a compare-and-set (CAS) on the driver's status record ("AVAILABLE, version 17" becomes "OFFERED, version 18" only if still at version 17). If two partitions pick the same driver (one via a ghost), exactly one CAS succeeds and the loser moves to its next candidate. The halo and the fan-out only affect match quality, never the single-assignment guarantee.

Tuning the overlap to density and latency

1. Derive h from density, per partition. Set h to the radius needed for k candidates at the current idle density, with a floor and a cap, recomputed every few minutes. At peak, density rises and r shrinks, so the halo gets cheaper exactly when load is highest.
2. Size partitions so r/L stays small. If r approaches L, a search touches all 8 neighbours. Suburbs should use larger partitions (a coarser level) so the ratio stays roughly constant across the city.
3. Choose per border, not globally. Default to fan-out. Measure p99 retrieval latency per border; where a cross-host hop pushes it over the budget, turn on a halo for that border only.
4. Validate by replay. Replay a day of searches with and without the mitigation and count "missed better driver" events (a driver across the line closer than the chosen one). That metric, not intuition, says whether the overlap is wide enough.

Pitfalls

• Treating boundary misses as rare: at typical radii nearly half of searches cross.
• A halo narrower than the search radius, which still misses drivers, just fewer.
• Letting a ghost copy make an assignment directly.
• One global halo width: too wide downtown (wasted writes), too narrow in suburbs (misses).

Direct answer

Surge can be gamed from both sides: riders or bots can inflate demand (fake accounts, emulator farms, software that simulates many phones on one machine so one attacker can run hundreds of fake app instances, opening the app and requesting then cancelling), and drivers can deflate supply (a group going offline together near an airport so the area surges, then logging back on to take the surged trips). The core defence is to compute surge from trusted signals rather than raw counts: demand is counted per verified rider and device, not per tap, and supply that disappears in a statistically implausible burst is held in the supply count for a short time. Detection feeds the price calculation, not a ban hammer: suspicious signals are down-weighted in the surge computation, while the people behind them still get normal service. Enforcement against accounts is a separate, slower, human-reviewed path, which is how the system avoids false positives harming real users.

Threat model

Layer 1: Data validation (trust the signal before counting it)

• Count riders, not taps. One demand unit per rider per area per 10-minute window, however many times they open the app.
• Collapse by device. Accounts sharing a device fingerprint (a hash of hardware and software characteristics that identifies a physical device, even across different app accounts on it) or payment instrument count as one rider.
• Trust weighting. Accounts under 72 hours old with no completed trip count as 0.25 of a rider. Established riders count as 1.
• Device attestation. Platform attestation APIs (Android Play Integrity, Apple App Attest) indicate whether a request came from a genuine app on a real device; unattested requests carry lower weight.
• Location plausibility. Reject driver locations that jump faster than a vehicle can travel, or that disagree with network-derived location.

Layer 2: Anomaly detection

Coordinated logoff. For each area and hour, learn the normal rate of drivers going offline per 2-minute window. A burst far above that, especially when the drivers are physically close together, is suspicious. A Poisson distribution (the standard model for counts of independent events at a known average rate) gives the chance of seeing at least k logoffs by accident.

Demand spikes without corroboration. Real demand spikes come with correlated signals: a concert ending, many different established riders, trips actually completed. A spike of requests with a high cancel rate and few completed trips is suspect.

Graph signals (slower, for enforcement). Drivers who repeatedly log off together, or rider accounts sharing devices and payment methods, form clusters. These feed investigations, not live pricing.

Layer 3: Rate limiting

• Per device and per account: at most a few ride requests per 10 minutes before further requests stop counting toward demand. The requests still work; they just stop moving the price.
• Per area: cap how much a single account or device can contribute to that area's demand count.
• API-level limits for unauthenticated or unattested clients.

Layer 4: Incentive design (remove the payoff)

• Pay surge on the dispatch-time price, and only to drivers who were online in or near the area before the surge started. A driver who logs off to cause the surge and logs back on gets the base fare during a short cooldown.
• Hold flagged supply: drivers who went offline in a flagged burst stay in the supply count for 15 minutes, so the surge they tried to trigger never appears.
• Quest bonuses require completed trips with a real rider, with delayed payout, so fraud reviews can claw back (reverse an approved-but-not-yet-paid payout once it is found to be fraudulent) before money leaves.

How it fits into the pricing pipeline, and the numbers

The defences sit between the raw event stream and the surge calculator, as a "trusted signal" stage. The calculator never sees raw counts. The script below (Python 3, standard library only, no randomness) shows both halves on a concrete area: 50 genuine riders each requesting once, plus 8 fake accounts on 2 emulator devices each requesting 15 times, against 40 idle drivers; then a burst of 14 driver logoffs where the historical average is 1.5 per 2 minutes.

import math

# ---- 1. Demand side: turn raw request events into "trusted demand" ----
# (account_id, device_id, account_age_hours, completed_trips, requests_in_window)
legit = [(f"r{i}", f"dev{i}", 2000, 12, 1) for i in range(50)]
farm = [(f"f{i}", f"emu{i % 2}", 6, 0, 15) for i in range(8)]   # 8 accounts on 2 devices
events = legit + farm

raw_demand = sum(e[4] for e in events)                 # every tap counts
per_account = len(events)                              # 1 request per account per window

def trust(age_h, trips):
    return 1.0 if (age_h >= 72 or trips >= 1) else 0.25   # new, never-ridden accounts count a quarter

by_device = {}
for acct, dev, age, trips, _ in events:
    by_device[dev] = max(by_device.get(dev, 0.0), trust(age, trips))   # one device = at most one rider
trusted_demand = sum(by_device.values())

supply = 40
print(f"raw requests      = {raw_demand:>6}   ratio = {raw_demand / supply:.2f}")
print(f"dedup per account = {per_account:>6}   ratio = {per_account / supply:.2f}")
print(f"trusted demand    = {trusted_demand:>6.2f}   ratio = {trusted_demand / supply:.2f}")

# ---- 2. Supply side: is a burst of drivers going offline plausible by chance? ----
def poisson_tail(k, lam):
    """P(X >= k) for X ~ Poisson(lam)."""
    return 1.0 - sum(math.exp(-lam) * lam ** i / math.factorial(i) for i in range(k))

baseline = 1.5          # historical mean logoffs per 2-minute window, this cell and hour
for observed in (3, 5, 14):
    print(f"logoffs in 2 min = {observed:>2}   P(X >= k | lam={baseline}) = {poisson_tail(observed, baseline):.2e}")

# ---- 3. Effect on the price if flagged logoffs are held in supply for 15 minutes ----
flagged_burst = 14
naive_supply = supply - flagged_burst
print(f"surge ratio with naive supply {naive_supply}: {trusted_demand / naive_supply:.2f}")
print(f"surge ratio with held supply  {supply}: {trusted_demand / supply:.2f}")

Output:

raw requests      =    170   ratio = 4.25
dedup per account =     58   ratio = 1.45
trusted demand    =  50.50   ratio = 1.26
logoffs in 2 min =  3   P(X >= k | lam=1.5) = 1.91e-01
logoffs in 2 min =  5   P(X >= k | lam=1.5) = 1.86e-02
logoffs in 2 min = 14   P(X >= k | lam=1.5) = 8.30e-10
surge ratio with naive supply 26: 1.94
surge ratio with held supply  40: 1.26

What the numbers say:

• The ratio above is not itself the price; the surge calculator looks it up on that area's surge curve to get the multiplier a rider is actually charged. Illustrative curve for this example: multiplier = 1.0 for ratio ≤ 1.0, then 1.0 + 0.5 × (ratio − 1.0), capped at a regional maximum of x2.5. On that curve the trusted-demand ratio of 1.26 gives 1.0 + 0.5 × 0.26 = x1.13; the naive, undefended ratio of 1.94 gives 1.0 + 0.5 × 0.94 = x1.47. The gap, x0.34, is roughly 3.40 USD extra on a 10 USD base fare, charged to every rider in the area for as long as the fake burst lasted, which is the revenue and trust cost the defenses below prevent.
• Raw taps give a ratio of 4.25, a maximum surge. Counting one request per account already drops it to 1.45; collapsing devices and trust-weighting new accounts gives 1.26, which is the genuine riders' demand (50) plus half a rider from the two emulator devices (2 × 0.25).
• Three logoffs in 2 minutes happen by chance 19% of the time and five about 1.9% of the time; both are normal. Fourteen has a probability of about 8 in 10 billion under the baseline.
• If those 14 drivers were subtracted from supply, the ratio would jump to 1.94 (about x1.47 on the surge curve above); holding them in supply keeps it at 1.26 (about x1.13). The attack gains nothing.

Avoiding false positives that harm real users

1. Down-weight, don't block. A misclassified genuine rider still gets a ride at a fair price; only their contribution to the surge signal is reduced. The worst case of a false positive in the pricing path is slightly lower surge, which costs the platform a little revenue rather than hurting a customer.
2. Set thresholds for the number of tests you run. With 5,000 areas and 720 two-minute windows a day, that is 3.6 million tests daily; a threshold of one in a million still produces about 3.6 false alarms per day. So require corroboration (drivers physically clustered, logoff followed by logon within 20 minutes) before holding supply, and use the probability threshold only as a first filter.
3. Real events look like attacks. A shift change at 6 p.m. produces many logoffs; a stadium emptying produces a genuine demand spike from many new accounts (tourists). Use a baseline per area and hour, and an events calendar, so these are expected.
4. Separate pricing defences from account enforcement. Pricing reacts in seconds and automatically, with low stakes. Suspending a driver or rider requires a human reviewer and an appeal path.
5. Measure the defences. Track how often trust-weighting changes the served multiplier, and audit a weekly sample of held-supply decisions. If defences change prices in a large share of areas, they are probably over-triggering.

Trade-offs and pitfalls

• Overdispersion: real logoff counts vary more than a Poisson model assumes (weather, shift patterns), so the Poisson tail overstates how unusual a burst is. Fit the baseline per area and hour, and treat the probability as a ranking score, not a literal false-positive rate.
• Attackers adapt: once new accounts are down-weighted, farms age accounts. Trust weights need refreshing from observed fraud, and the incentive changes (paying only pre-surge drivers) matter more than any detector because they remove the payoff.
• Driver trust: drivers who see fares reduced by an opaque cooldown will complain; publish the rule ("surge applies to drivers online before it started") so honest drivers understand it.

Direct answer

The system is a pipeline of seven services, and the key design decision is which of them hold state. Location ingestion, candidate generation, ML scoring and the API layer are stateless and scale horizontally; the proximity index and the assignment service are stateful, partitioned by geography, and the assignment service is the single place where "this driver belongs to this ride" is decided with an atomic write; the ETA and feature cache sits between candidate generation and ML scoring, stateful but disposable, since a cache miss just falls back to computing the value fresh. The first thing I would do is sanity-check the numbers: 200k matching requests per second is far more than 10M users can generate as ride requests, so I read it as 200k proximity and scoring queries per second (price quotes, ETA previews, re-matches, pool evaluations, meaning checking whether a new rider can share an already-assigned car in a shared-ride pool), while committed assignments are a small fraction of that. I would design for that split, with a per-request latency target of under 100 ms at the 95th percentile and regional failover.

Checking the numbers first

No user requests 1,700 rides a day, so most of those "matching requests" must be previews and re-evaluations. That matters: previews need a fast, approximate answer and no commit, while real ride requests need a commit. Designing both paths as one would put the expensive exclusive write on 200k requests/s for no reason.

Consequences: the index fits in memory many times over; ML scoring at 10 million rows/s is the dominant compute cost, so the model must be cheap and batched, and candidate lists must be pruned before scoring.

Components and data flow

flowchart LR
  DRV[Driver apps] --> LI[Location ingestion]
  LI --> PI[Proximity index]
  RID[Rider apps] --> API[Matching API]
  API --> CG[Candidate generation]
  CG --> PI
  CG --> CACHE[ETA and feature cache]
  CG --> ML[ML scoring]
  ML --> ASN[Assignment service]
  ASN --> DS[Driver state store]
  ASN --> NOTIF[Offer push]

Stateless services can be killed and replaced at will. The stateful ones need a recovery story: the index rebuilds itself within one ping interval (4 s) because every driver re-reports; the driver state store is a replicated database and is the only component whose loss would be a correctness problem.

Two request paths

• Preview path (quotes, ETA display, pool evaluation): candidate generation, scoring, answer. No write. Most of the 200k/s.
• Commit path (real request): the same, then the assignment service does "claim driver D for ride R if D's version is still v", tries the next candidate on conflict, then pushes the offer. The design target is 10,000 commits/s at peak across all regions, roughly 24x the ~417/s real commit rate estimated above, which is the headroom the target buys for uneven load across regions and demand spikes. Spread over the 1,000,000 online drivers, 10,000 commits/s is 36,000,000 commits/hour / 1,000,000 drivers, about 36 writes per driver-hour, one every 100 seconds per driver: easily handled by a partitioned store.

SLOs per component

An SLO (service-level objective) is the internal target each team is held to. They must add up to the end-to-end target of under 100 ms at the 95th percentile (P95: 95% of requests are faster):

15 + 20 + 25 + 20 + 20 = 100 ms. Summing P95s is conservative (not every step is slow on the same request), so this budget leaves real headroom. The components that have fallbacks can have lower availability targets than the end-to-end one, because their failure degrades quality rather than causing errors.

Region failover

• Each metro is served from a home region; drivers and riders in that metro connect there. A second region holds a warm standby for each metro (a standing but idle copy, kept ready to take over quickly, that does not serve live traffic day to day).
• The proximity index is not replicated across regions: on failover, driver apps reconnect to the standby region and their pings rebuild the index in about 4 s.
• The driver state store replicates to the standby region. On failover, rides in flight whose assignment was committed but not yet replicated are the risk; the driver app, which knows its current ride, re-registers it with the new region, and the assignment service accepts the driver's own record as authoritative for that ride.
• Failover is triggered by health checks with a manual confirmation for whole-region moves, because automatic region failover on a flaky signal causes more incidents than it prevents. DNS or gateway routing moves the metro's traffic.

Trade-offs and pitfalls

• Scoring every nearby driver: at 10 million rows/s even a cheap model is expensive; pruning by cheap ETA first is where most of the cost savings come from.
• Putting the exclusive claim on the preview path: turns 10k TPS of writes into 200k.
• Strongly consistent location data: unnecessary; a location a few seconds old is fine, and the commit path protects correctness.
• Global single index: simple, but one bad deploy or overload takes out every city; geo shards limit the blast radius (how much one failure can break).