Show nearby cabs for riders inside a city

Questions I would ask: is the map a browsing view only, or does it also feed booking and driver matching? How fresh must a cab marker be, and is smooth movement on the map required? How many cabs should be shown, and does the rider choose a vehicle type? Which zones matter: airports, no-pickup areas, city service limits, surge areas? How often do zones change?

Assumed scope: drivers report location and status; riders see up to 10 available cabs nearby; a zone check answers "is this point inside zone X". In scope: location ingest, the proximity query, caching, the polygon check. Out of scope: matching and dispatch, routing, pricing, and the trip itself.

Planning figures for the exercise, not facts about any company.

• Writes: 100,000 drivers ÷ 4 s = 25,000 location updates a second. That is five times the 5,000 committed writes a second a relational primary can be planned for.
• State size: 100,000 drivers × 100 B = 10 MB. The whole city's live positions fit in memory on one box. The problem is the update rate and availability, not size.
• Reads: 150,000 riders ÷ 5 s refresh = 30,000 reads a second, past the 20,000 simple reads a second one box does.
• Grid: a city of about 1,000 km² cut into cells of about 1 km² is 1,000 cells, so about 100 drivers per cell on average; a dense downtown cell might hold 1,000. A query reads a cell plus its 8 neighbours: about 900 candidates on average, a few thousand in the worst case. Distance maths on that is cheap.
• Cache effect: if each cell's driver list is rebuilt every 2 s, that is 1,000 ÷ 2 = 500 rebuilds a second however many riders ask.
• Trail logging: storing every ping is 25,000 × 100 B = 2.5 MB a second, about 216 GB a day. Sampling one in five gives about 43 GB.

The numbers force an in-memory, partitioned index, a cell-level cache for reads, and a separate, sampled path for history.

Components. A gateway that accepts driver pings; a location service holding the live index in memory; a read API for riders; a cell-snapshot cache; a log for history; and a zone service.

Data model (in memory).

• drivers: driver_id -> {lat, lng, cell, status, vehicle_type, seq, updated_at}.
• cells: cell_id -> set of driver_id, where cell_id is a geohash or similar grid code at roughly 1 km precision. Keep one set per vehicle type if filters are common.

The index is partitioned by region: the city is divided into a few coarse regions, each owned by one shard with a hot replica. A shard owns every cell inside its region, so a rider's 9-cell query normally hits one shard (two near a region edge).

Write path.

1. A ping arrives with driver id, position, timestamp and a per-driver sequence number.
2. The gateway routes it to the owning shard by its cell. The shard ignores the ping if the sequence is older than what it holds, which handles out-of-order delivery.
3. It updates the record. If the cell changed, it removes the driver from the old cell set and adds it to the new one. If the new cell belongs to another shard, send the update there and let the old entry expire; a driver on a boundary can appear in both shards for up to 12 s, so the API de-duplicates by driver id.
4. Entries expire after 12 s without a ping (three missed pings), so crashed phones disappear without anyone telling us.
5. Every fifth ping is also appended to a log for trip history and analytics. That log is not on the serving path.

The index is rebuilt from incoming pings within one interval, so it needs no durable database. A replica takes over if a shard dies, and the first pings after a restart refill the rest.

Read path. The rider app sends its position. The API computes the rider's cell and its 8 neighbours, takes each cell's cached snapshot (a list of driver ids and positions, rebuilt every 2 s), filters to available drivers of the requested type, sorts by straight-line distance, and returns 10. The app interpolates markers between refreshes, so movement looks smooth without a faster poll. If fewer than 10 are found, widen to the next ring of cells up to a maximum radius.

Consistency. The map is a hint. A marker can be several seconds old (up to about 6 s when the API reads it: 4 s between pings plus up to 2 s of snapshot age, then the rider's 5 s poll on top), and a driver shown as available may have just taken a trip. The authoritative state lives in the trip service, and dispatch makes a conditional update from available to offered, so two riders cannot get the same driver. This is the line between eventual and strong consistency: browsing tolerates staleness, assignment does not.

Dense and sparse areas. A fixed grid wastes work in a crowded cell and finds nothing in a thin one. Cap candidates per cell by taking the freshest N, and use ring expansion for sparse areas.

Zone check. Polygons (airport, service area, restricted pickup) are loaded into memory on every instance of the zone service, versioned, with a bounding box for each. At load time, record for each grid cell which polygons touch it and whether the cell is fully inside one. A lookup finds the point's cell: if no polygon touches it, answer outside; if the cell is fully inside one, answer inside; otherwise run a ray-casting point-in-polygon test on the few candidate polygons. With 10 candidates of 500 vertices that is 5,000 edge tests, microseconds of work. Define boundary points consistently and support polygons with holes.

• In-memory sharded index vs Redis geo sets. A geo set is quick to adopt and good enough for the first version, but members cannot expire one by one, so you sweep stale drivers yourself and the cell filter options are limited. A custom in-memory index gives per-driver expiry and vehicle-type sets. Start with the managed structure; flip to custom when expiry and filtering get awkward.
• Fixed grid vs adaptive tree. A fixed grid is trivial and cache-friendly. A quadtree adapts to density but is harder to cache and move between shards. Pick the grid with a cap per cell; flip to a tree if downtown cells routinely exceed a few thousand drivers.
• Polling vs push for the map. Polling every 5 s is simple and caches by cell. Push gives smoother markers but needs one subscription per rider. Poll for browsing; switch to a push stream only after booking, for one tracked driver.
• Straight-line vs road ETA. Straight-line distance is fast and good for ranking a list; road time is what the rider cares about but costs a routing call. Use straight-line for the 10 on screen and road time only for the top 3. Flip to road-first where rivers and one-way grids make the two differ widely.

• Writing every ping to a relational table and indexing latitude and longitude. At 25,000 writes a second, the primary cannot keep up.
• Searching a single cell and missing a cab 50 m away across the cell edge. Always query the neighbours.
• Treating the map as the booking truth, so two riders are given the same driver.
• No expiry, so drivers who went offline stay visible as ghost cars.
• Running the point-in-polygon test against every polygon in the country on each request instead of narrowing by bounding box or cell first.
• Using straight-line distance as the promised pickup time.