You open Blinkit, tap order, and within a second or two a rider is assigned. The obvious framing is "find the closest rider," which makes it sound like a geometry problem. It is mostly a write-throughput problem: tens of thousands of riders are each reporting a new position every few seconds, and the index you query must be that fresh.
What the problem really is
Two coupled subsystems, with opposite characteristics:
| Subsystem | Shape | Hard part |
|---|---|---|
| Location ingestion | Very high write rate, tiny payloads, overwrite-heavy, no history needed on the hot path | Sustaining writes without touching the primary database |
| Nearest-rider query | Moderate read rate, latency-critical, spatially bounded | Not scanning; correctness under staleness |
| Assignment | Low rate, must be exactly-once per rider | Races — two orders must not get the same rider |
Recognising that these are three systems with three storage choices is most of the answer.
The numbers that shape the design
Riders online (city, peak) ≈ 20,000 Location update interval = 4 s → 5,000 location writes/sec per city → 20 cities ≈ 100,000 writes/sec Payload: rider_id 8B + lat/lng 16B + ts 8B + status 1B ≈ 40B → ~4 MB/s of raw updates; trivial bandwidth, brutal write rate Orders at peak (city) ≈ 40/sec → matching reads are 100x rarer than location writes Latency budget for assignment < 500 ms Freshness requirement < 10 s stale positions Search radius 1–5 km, expanding
The 100:1 write-to-read ratio is the design constraint. Optimise the write path for cheap overwrite, and accept doing a bit more work per (rare) read.
Why scanning does not work
SELECT rider_id,
ST_Distance(location, ST_MakePoint($lng, $lat)::geography) AS d
FROM riders
WHERE status = 'available'
ORDER BY d
LIMIT 10;Without a spatial index this computes a distance for every available rider — 20,000 haversines per order, and it grows with fleet size. Worse, it runs against a table receiving 5,000 updates per second, so it competes with the write load for the same rows and indexes. Even with PostGIS and a GiST index (which does work well up to moderate scale), you are hammering your primary database with high-frequency updates that have no business being there. That is exactly how you end up at 100% CPU.
The fix is to make "near me" a key lookup instead of a computation.
Grid indexing: geohash, S2, H3
Divide the world into cells, each with a short identifier, and store riders under their cell ID. "Near me" becomes: compute my cell, read that cell and its neighbours, and you have a small candidate set to compute exact distances on.
| Scheme | Cell shape | Strength | Weakness |
|---|---|---|---|
| Geohash | Rectangles from interleaved bits | Dead simple; prefix = larger cell; works in any key-value store | Distortion near poles; awkward neighbour maths; boundary artefacts |
| S2 (Google) | Squares projected on a sphere | Very uniform areas; excellent region-covering | More complex library and mental model |
| H3 (Uber) | Hexagons | Uniform neighbour distance (6 equidistant neighbours); ideal for ring searches | Hexagons do not nest perfectly across resolutions |
precision 5 ≈ 4.9 km × 4.9 km "tdr1y" precision 6 ≈ 1.2 km × 0.6 km "tdr1yb" precision 7 ≈ 153 m × 153 m "tdr1yb2" A shared prefix means spatial proximity, so widening the search is just truncating the key: tdr1yb2 -> tdr1yb -> tdr1y Critical detail: two points 10 m apart can sit in different cells with completely different prefixes. You MUST search neighbouring cells, never the single cell alone.
Pick resolution so a cell holds a useful number of riders — typically a few dozen. Too coarse and you scan thousands; too fine and you fetch dozens of cells to find anyone.
Where live locations live
Not in your relational database. Live positions are ephemeral, overwritten constantly, and only need to be correct for a few seconds — the ideal fit for an in-memory store.
# ingest: a single command per update, O(log N) GEOADD riders:blr:available <lng> <lat> rider:8817 # query: radius search, sorted, bounded GEOSEARCH riders:blr:available FROMLONLAT <lng> <lat> BYRADIUS 3 km ASC COUNT 20 WITHCOORD WITHDIST # rider goes offline / gets assigned ZREM riders:blr:available rider:8817 # staleness: a separate sorted set of last-seen timestamps ZADD riders:blr:heartbeat <now_ms> rider:8817 ZRANGEBYSCORE riders:blr:heartbeat -inf <now_ms - 15000> # → sweep these out
Design notes that matter more than the command syntax:
- Shard by city or region. One key per city gives natural partitioning, bounded set sizes, and independent failure domains. Nobody searches across cities.
- Overwrite, do not append. The hot path stores only the current position. The location history — needed for ETAs, disputes and analytics — goes to a stream and then to columnar storage, entirely off the critical path.
- Expire aggressively. A rider whose phone died must vanish from the index within seconds, or you assign orders to ghosts. Heartbeat timestamps plus a sweeper.
- Sample the writes if needed. A stationary rider does not need a write every four seconds; the client can suppress updates when movement is below a threshold, cutting write volume substantially for free.
- Persistence is optional. Losing the index is survivable: within four seconds every rider re-reports and it rebuilds itself. That is a rare and pleasant property — use it, and do not pay for durability you do not need.
The matching query end to end
1. Resolve the customer's location to a city shard and cell ID.
2. Candidate fetch: cell + neighbouring ring, or GEOSEARCH BYRADIUS 2 km.
Expand the radius (2 km → 4 km → 7 km) only if too few candidates.
3. Filter hard constraints:
- heartbeat fresh (< 10 s)
- status = available
- vehicle/capacity suitable, order value within limits
- not already reserved by another in-flight assignment
4. Score the survivors (this is where the product lives — see below).
5. Reserve the winner atomically:
Lua script / SETNX on lock:rider:8817 with a short TTL,
then ZREM from the available set.
If reservation fails, take the next candidate.
6. Offer the order to the rider. On decline or timeout, release the
reservation and re-run scoring with that rider excluded.Step 5 is the correctness crux. Reservation must be atomic, or two concurrent orders both read the same rider as available and both assign them. A Lua script — check, remove, mark — executes as one unit in Redis and gives you that. The same "unique claim" reasoning underlies duplicate-payment prevention.
Distance is the wrong ranking
Straight-line distance ignores rivers, one-ways, flyovers and traffic. A rider 800 m away across a highway may be twelve minutes out while one 2 km away on a clear road is five. Rank by predicted time, not metres.
score = w1 · predicted_pickup_eta // routing/ML, not haversine
+ w2 · predicted_dropoff_eta
+ w3 · batching_bonus // already heading that way
- w4 · rider_idle_time // fairness: longest-waiting first
- w5 · rider_acceptance_rate // reliability
+ w6 · store_prep_time_alignment // arrive when the order is ready
Straight-line distance is only the candidate FILTER.
ETA and business objectives are the RANKING.Two consequences: ETA prediction must be fast (precomputed road-network travel times per cell pair, or a cached routing service — you cannot call a routing API for 50 candidates inside a 500ms budget), and store preparation time matters, because a rider who arrives eight minutes early is capacity you wasted.
Assignment, races and batching
- Greedy per order is not optimal. Assigning each order to its best rider as it arrives can leave a cluster of orders unservable. Batching orders into short windows (2–10 seconds) and solving a small assignment problem across them measurably improves overall delivery times — at the cost of a few seconds of latency, which users never see because the rider still has to reach the store.
- Order batching (multi-drop). One rider carrying two nearby orders is the single biggest efficiency lever in the model, so the scorer must reason about routes, not just riders.
- Declines are normal. Model assignment as an offer with a timeout, and keep a ranked fallback list so a decline costs milliseconds rather than a full re-run.
- Fairness is a requirement, not a nicety. Pure ETA optimisation systematically starves riders in low-density areas. Idle time in the score is what keeps the supply side viable.
Edge cases that break naive designs
| Edge case | Why it breaks things | Handling |
|---|---|---|
| Cell boundaries | The nearest rider sits in an adjacent cell | Always search the neighbour ring, never one cell |
| Dense city centre | One cell holds 2,000 riders | Finer resolution in dense areas, or cap and sample |
| Sparse outskirts | No riders within radius | Progressive radius expansion with a hard ceiling, then queue the order |
| Stale GPS / tunnels | Rider appears somewhere they are not | Heartbeat freshness, plausibility checks against last known speed |
| Ghost riders | App killed, position frozen | TTL sweep on heartbeats |
| Rider moving fast | Position is already wrong when you assign | Dead reckoning from last known heading; keep freshness tight |
| Thundering herd on one store | A promo drops and 500 orders hit one location | Batch assignment windows; queue with expected-wait feedback |
How to answer this in an interview
"The headline is 'nearest rider', but the numbers say otherwise: 20,000 riders reporting every 4 seconds is 5,000 writes/sec per city, while orders are only ~40/sec. It's a write-throughput problem with a rare, latency-critical read. So live positions don't go in the primary database — they go in an in-memory geospatial index sharded per city, overwritten in place, with heartbeat TTLs so dead riders disappear. History goes to a stream for ETAs and analytics, off the hot path. For the query, I index on a grid — H3 or geohash — so 'near me' is a lookup of my cell plus the neighbour ring rather than a distance per rider. Always the ring: the nearest rider is often just across a boundary. Then I filter on freshness and availability, and rank by predicted ETA plus batching and fairness, not straight-line distance — distance is only the filter. Correctness crux: reserving a rider must be atomic, or two orders assign the same person, so a Lua script that checks and removes in one step. And I'd batch assignment over a few seconds because greedy per-order matching is measurably worse for overall delivery time. Trade-off: positions can be up to ~10 seconds stale, which is fine because the rider is moving anyway and the offer can be declined. The index is derived — if it's lost, it rebuilds in four seconds."
Summary
- The hard part is 5,000 location writes/sec per city, not the nearest-neighbour query.
- Keep live positions in an in-memory, city-sharded geospatial index — never in the primary database.
- Grid indexing (geohash/S2/H3) turns "near me" into a handful of key lookups.
- Always search neighbouring cells; boundaries otherwise hide the closest rider.
- Filter by distance, rank by ETA plus batching and fairness.
- Reserve riders atomically or you will double-assign.
- Heartbeat TTLs remove ghosts; the index is derived state and heals itself.