In a ride-hailing app that shards its in-memory driver location index by region, what problems do shard boundaries cause and how are they handled?

## Why shard the live index by region A **ride-hailing app** keeps driver positions in an **in-memory geo index**. One index for a whole country would need to fit in one server's memory and absorb every update. So the index is **sharded by region**: each shard owns an area - a metro region, or a contiguous group of cells - and holds only the drivers inside it. A **router** maps any coordinate to its owning shard. This works well because nearly every query is local: a pickup only cares about drivers within a few kilometres. The trouble is concentrated at the **edges**. (Splitting an overloaded shard is a general sharding topic and is not covered here.) ## Problem 1: handoff when a driver crosses A driver in shard A drives across the border. The next update is routed to shard B, which inserts the driver. Shard A still holds the previous entry. - For up to one time-to-live, the driver exists **twice**: a stale copy in A and a live copy in B. - A search near the border may return both copies. - A search deep inside A may return a **ghost** that is really somewhere else. Handling: 1. The router remembers each driver's **current shard** (in the session for a persistent connection, or in a small lookup). 2. When the computed shard changes, it writes to the new shard **first**, then sends a delete to the old shard. Writing first means the driver is never missing, only briefly duplicated. 3. If the delete is lost, the old entry's **time-to-live** removes it anyway. 4. Anything that merges results **dedupes by driver id** and keeps the entry with the newest timestamp. ## Problem 2: searches that straddle an edge A pickup sits 300 m inside shard A, and the dispatcher searches 2 km around it. Almost half of that circle lies in shard B. Querying only A misses every driver across the border, even ones 400 m away. Handling: - compute the **set of shards whose area intersects the search area** (a bounding box or circle against each shard's area); - **fan out** the query to each of them in parallel; - **merge**, dedupe by driver id, and keep the best K; - set a per-shard timeout so one slow neighbour degrades the result instead of blocking it. Most searches touch one shard; only the ones near an edge pay the fan-out cost. ## Problem 3: flapping on the border A driver on a road that follows the border may be computed into A, then B, then A on successive pings. Each flip causes a handoff: a write, a delete and a brief duplicate. Handling: **hysteresis**. A driver stays in the current shard until they are more than some margin, say 200 m, past the border. The cost is that a shard can hold drivers slightly outside its area, so edge detection for fan-out must use each shard's area **expanded by that margin**. ## Summary | Problem | Symptom | Mitigation | |---|---|---| | Handoff | Duplicate or ghost driver after a crossing | Write new shard, then delete old; time-to-live backstop; dedupe by id | | Edge search | Missed drivers just across the border | Fan out to all overlapping shards and merge | | Flapping | Constant handoffs on a border road | Hysteresis margin; expand areas by it for fan-out | ## Choosing where borders sit Borders are cheapest where little happens: - follow **natural gaps** - rivers, parks, sparsely populated land - rather than cutting through a dense downtown; - keep a **metro area in one shard** when it fits, since most trips start and end inside it; - be careful with places that draw traffic from two regions, such as an airport between two cities, because every search there fans out. ## What must not depend on the shard Dispatch state - offers and assignments - should live in its authoritative store, **not** in the regional index. Then a handoff can only duplicate or briefly misplace a **position**, which the next ping repairs; it can never lose or duplicate an **assignment**. Keeping the index purely rebuildable is what makes these simple, eventually consistent boundary fixes acceptable.