Yelp and Uber

Both services answer a question about where: which restaurants are within a kilometer of me, which drivers are closest to this rider. The difference is how fast the data changes. Restaurants hardly move, so we can build a careful index and rarely touch it. Drivers move every few seconds, so the index must be cheap to update. The same core idea, divide the map into regions and look only at nearby ones, is applied in two different ways.

Users search for places near a location, optionally filtered by category, and see ratings and reviews. Owners add and edit places, and users post reviews. Search must be fast, and slightly stale data is fine.

Assume 500 million places. At about 500 bytes of details each that is roughly 250 GB, small enough to keep on a few machines. The place locations alone, an id and two coordinates at about 24 bytes, are 500M x 24 B, about 12 GB, which fits in the memory of one server. Assume 50,000 searches per second, and far fewer writes.

The naive query computes the distance from the user to every place and keeps the nearest, which is O(n) over half a billion rows. A database query with a range on latitude and a range on longitude is better, but each range alone matches a huge band around the globe, and intersecting two huge result sets is slow. We need an index that is two dimensional.

Divide the map into a grid of fixed cells, and keep a list of places per cell. To search, find the user's cell and read it and its eight neighbors. This works, but density varies enormously: one cell in the middle of a city may hold a million places while a cell over farmland holds none, so cells are either too crowded or wasted.

A geohash encodes a latitude and longitude into a short string, in such a way that places that are close share a prefix. Longer strings mean smaller cells. Roughly:

• 4 characters: a cell about 39 km by 20 km.
• 5 characters: about 5 km by 5 km.
• 6 characters: about 1.2 km by 0.6 km.
• 7 characters: about 150 m by 150 m.

Store each place under its geohash, and a search for "within a kilometer" becomes a prefix lookup on a normal sorted index. One caution: two points can be very close but lie on either side of a cell boundary, with completely different prefixes. So always search the neighboring cells as well.

A quadtree adapts to density. Start with one node covering the whole map. If a node holds more than a limit of places, say 500, split it into four equal quadrants and push its places down. Repeat. Crowded areas end up deeply subdivided with small leaves, while empty areas stay as a few large leaves.

To search, descend from the root to the leaf containing the user, collect its places, and then add neighboring leaves until you have enough results within the radius. Leaves can be linked to their neighbors to make that cheap.

Size it: 500 million places at 500 per leaf is about 1 million leaves. A quadtree with L leaves has about L/3 internal nodes, so around 333,000. At roughly 100 bytes per node, the tree is only about 130 MB, plus 12 GB for the locations. It fits in memory.

• Static data such as place details and reviews sits in a database sharded by place id, with a cache for popular places.
• Index updates: places change rarely, so rebuild the quadtree periodically from the database, or apply small updates in place and rebuild fully at quiet times. Use two copies and swap.
• Scaling: replicate the index across many servers for throughput. For a worldwide index, partition by region, but balance carefully, since a dense city is far busier than a rural area.
• Ranking: combine distance with rating, popularity, whether a place is open now, and a user's preferences, then return the top results.

Riders request a trip, and the system must quickly find nearby available drivers and offer them the ride. Assume 1 million active drivers, each reporting position every 4 seconds. That is 250,000 location updates per second, around 25 MB per second at 100 bytes each. Rebuilding a quadtree for each of those is out of the question, and writing each to a disk database would be wasteful, since a position is stale after seconds.

Keep current driver positions in memory only. Use a fixed grid or geohash index where each cell holds the set of drivers currently in it. When a driver reports a position:

• Compute their new cell.
• If it is the same as before, just update the stored coordinates.
• If it changed, remove the driver from the old cell's set and add to the new one.

Most updates stay inside a cell, so the index changes only when a driver crosses a boundary. The latest position is also copied to a durable store occasionally, not on every ping, so a crashed server can recover quickly. Driver apps send updates over a persistent connection.

When a rider requests a trip:

1. Find the rider's cell and search outward in rings of cells until enough available drivers are found within a limit.
2. Rank them, not just by straight-line distance but by estimated time of arrival along real roads, using a routing service, plus factors like driver rating.
3. Offer the trip to the best driver, who has a few seconds to accept. If they decline or time out, offer the next.
4. While an offer is out, lock that driver so no other request can offer them the same driver, which prevents double dispatch.

A trip is a small state machine: requested, driver assigned, driver arrived, in progress, completed or cancelled. Persist each transition so a crash cannot lose or duplicate a trip.

Partition the system by city or region: drivers and riders in one city almost never interact with another, so each region can run independently, which keeps data local and failures contained. Large cities may be split further by cells. Keep dispatch services stateless and the in-memory index rebuildable from the recent driver pings, so a failed server is replaced within seconds. Surge pricing is computed by counting supply and demand per cell over a short window and adjusting price multipliers.

• Yelp: data moves slowly, so use a read optimized index (quadtree or geohash), rebuild periodically, and spend effort on ranking.
• Uber: data moves constantly, so use an in-memory cell index with cheap updates, accept approximate positions, and spend effort on matching, locking and state.
• Both rely on the same idea: turn a two dimensional proximity query into a small lookup over nearby cells, and then rank the handful of candidates.