Match a rider to the nearest driver across millions of moving cars using a geospatial index, absorb a firehose of GPS updates, and dispatch.
Uber answers one question fast, over and over: *which drivers are near this rider, right now?* The hard parts are that there are millions of cars, all moving, each streaming its location, and 'nearest' must be computed in milliseconds. The heart of the design is a geospatial index.
The naive design queries all drivers, computes the distance to each, and picks the closest. That is O(number of drivers) per request — hopeless past one small city. We need to look at only the drivers physically nearby, which means indexing space itself.
The general idea is to tile the map into cells and bucket each driver by cell, so 'nearest' becomes 'read my cell and its neighbours'. There are several schemes in this family: geohash (recursively halve lat/long into a string prefix), quadtree (recursively split a square into 4), and Google's S2 (project the sphere onto cube faces). Uber built and open-sourced its own: H3, which tiles the globe with hexagons.
Every driver streams GPS continuously — Uber cited roughly every 4 seconds, targeting on the order of 1M writes/sec in 2015. Do the math: 1M active drivers pinging every 4s is ~250K updates/sec just to keep the index current, and that data is short-lived (last known position only). A normal disk-backed database cannot keep up; this wants an in-memory, sharded index.
Matching is DISCO (Dispatch Optimization). Rather than just grabbing the nearest idle car, it plans ahead — forward-dispatch — for example a car about to drop off a rider a block away may beat an idle car that is farther. Surge pricing is computed per hexagon, comparing supply against demand in that cell to set a local multiplier. Each concern is its own service so they scale independently.
