Loading...
Each entry stores:
In a single large city with 50k drivers:
50,000 × 40 bytes = 2 MB
Globally with 500k drivers:
500,000 × 40 bytes = 20 MB
Small enough to fully cache all active drivers in Redis or memory.
POST /rides/request
This endpoint allows a user to request a ride. It typically involves several steps.
eg,
{
"user_id": "12345",
"pickup_location": {
"latitude": 37.7749,
"longitude": -122.4194
},
"dropoff_location": {
"latitude": 37.7849,
"longitude": -122.4294
},
"ride_type": "standard"
}
In order to support real time look up of finding nearby drivers we would need something fast like Redis. Redis does not store data permanently, we also save all driver location updates in a reliable database like Cassandra. Cassandra can handle a large number of updates and help us recover data if needed.
Table: driver_location_history
Partition Key: geohash_prefix
Clustering Key: timestamp
Values: driver_id, lat, lon
We will explore sharding and more in depth explanations in the later sections.
The write path begins when the driver app sends a location update to the backend. These updates are processed and stored so the system always knows where each driver is. The read path starts when a rider requests a trip. The system looks up nearby drivers from the latest location data, ranks them based on distance or estimated time of arrival, and returns the best match to the rider. We will omit payment processing to focus on a few critical components.
Driver Mobile App
Sends periodic GPS updates to the backend.
Location Ingestion Service
Processes updates and maps coordinates to some data structure. Stores data in fast in-memory storage like Redis.
Spatial Index / Cache Layer
Stores driver IDs by region key. Updated in real time.
Nearby Search Service
Handles rider requests by determining the rider’s current cell, fetching nearby cells, retrieving drivers, and filtering by distance or ETA.
Geospatial Utilities Library
Wraps logic for converting coordinates to region IDs, finding neighboring regions, and computing distances.
Fallback Persistent Store
Stores historical location data or offline fallback using PostgreSQL with PostGIS.
Matching Engine
Applies ranking logic on top of candidate drivers to choose the best one based on ETA, distance, ratings, etc.
A driver sends a GPS ping.
A rider requests a ride.
Mobile rider and driver apps continuously send GPS location updates to the backend. The frequency and handling of these updates are critical: too slow and the system lags; too fast and it overwhelms networks and drains batteries. Large-scale platforms use adaptive update strategies and filtering to strike a balance.
In practice, drivers do not simply send location every second at all times. The update interval is adjusted based on context (speed, activity, etc.). We can use adaptive intervals such as every ~5 seconds in busy areas or peak hours, and every ~30 seconds in rural or low-activity times. A commonly cited baseline is about 3 seconds per update when a driver is actively moving. If a driver is stationary or moving very slowly, the app can reduce the frequency to save bandwidth and power (since frequent updates would yield almost no change in location). Conversely, if a driver is moving fast (or during a critical period like just before pickup), the app can send more frequent updates to maintain accuracy. This dynamic throttling ensures high fidelity when needed, without incurring the cost of high-frequency updates at all times.
From the rider's client side, early versions of real-time systems often relied on polling to get updates such as driver's location. Uber found that at one point 80% of its backend calls were polling calls, which was not sustainable.
Modern architectures avoid constant polling by using persistent connections and streaming. For instance, Uber migrated from frequent HTTP(S) requests to a gRPC-based bidirectional streaming channel over HTTP/3 for push updates.
Similarly, a WebSocket connection can carry a stream of location updates from driver apps to the server (and updates back to riders) without the overhead of repeated HTTP setup.
These streaming approaches significantly reduce latency and server load, as data flows continuously and only when necessary, rather than through repetitive polling cycles.
To further optimize network usage, location data can be compressed or coalesced. One method is to send only the delta (change) from the last known location when possible. Another is to include additional sensor hints (like heading, speed) so the server can predict motion in between updates. If a connection is temporarily lost, the driver app might batch and send multiple missed location points once reconnected, allowing the server to reconstruct the trajectory. We can use protocols like Google’s Protocol Buffers to encode data in compact binary form instead of verbose JSON.
When drivers send their location, the backend must keep track of where everyone is in real time. That means handling constant updates from thousands or even millions of drivers, while also being able to quickly answer questions like “who is nearby?” To do this efficiently, the system must support both fast writes (location updates) and fast reads (nearby driver queries), and it must scale across many servers around the world. Ride-sharing platforms achieve this by using smart ways to organize and search location data.
Geohash
One common method is Geohash, which turns a latitude and longitude into a short string like 9q8yyzd. This string represents a square area on the map. The more characters in the geohash, the smaller and more precise the area. Drivers in the same area will share the same prefix, such as 9q8yy, which might represent a neighborhood. This makes it easy to group drivers and look them up using prefix matching.
Geohashes are simple and work well in key-value databases like Redis or Cassandra.
For example:
Key: geo:9q8yyzd
Value: [driver_123, driver_456, driver_789]
To find nearby drivers, the rider’s location is also converted to a geohash. The system then checks that geohash and its 8 neighbors to make sure drivers near the edges aren’t missed. After that, it filters the list based on actual distance.
Quadtree
Another method is the Quadtree, a tree structure that splits space into four parts: NW, NE, SW, and SE. If one area gets crowded, it splits again, and so on. The more drivers in a region, the deeper the tree becomes in that spot. Each driver ends up in one of the leaf cells based on their location.
To store a driver, the system calculates a path from the root of the tree to the correct quadrant. This path could look like "NE → SE → NW → NW" or be stored as "1321".
You can save drivers under these path-based keys in memory or a key-value store:
{
"2310": ["driver_123", "driver_456"],
"2311": ["driver_999"]
}
When a rider requests a car, the system finds which quadrant the rider is in and checks that cell plus its neighbors. Quadtrees work well because they adapt to both dense and sparse regions. However, they require more logic to maintain and search, especially in busy areas that need many splits.
Google’s S2 library is based on similar ideas and is used in production by companies like Lyft.
H3 (Uber’s Hexagonal Grid)
Uber created H3, a system similar to Geohash but using hexagons instead of squares. Hexagons are better because they don’t stretch as much across the globe and have six equal neighbors, which makes distance-based queries smoother.
H3 divides the Earth into hexagonal cells at multiple resolutions — from very large to very small. Each cell has a unique ID. When a driver updates their location, the system maps them to a hex cell. To find nearby drivers, the rider’s hex cell and the surrounding cells are checked.
This approach is accurate, efficient, and easy to scale. Uber uses H3 for both real-time driver matching and large-scale analytics like heatmaps and surge pricing. H3 is now open source and widely adopted.
To meet real-time latency requirements, ride-sharing platforms often keep the live location index in memory, and use persistent storage for backup or historical data. A common pattern is Caching + Database.
A fast in-memory data store (like Redis) holds the latest location for each driver and supports quick geospatial queries. Redis, for instance, has built-in geospatial commands: GEOADD to add/update a location in a geospatial index, and GEOSEARCH (or the older GEORADIUS) to query nearby points within a given radius. These operations are optimized and in-memory, giving very low latency.
In fact, using Redis for real-time location was one of the early optimizations Uber and Lyft made. Redis can handle the high volume of writes and perform proximity searches with high throughput, while also allowing you to set a Time-To-Live (TTL) on data to expire old locations (useful if a driver goes offline, their last location can disappear after e.g. a few minutes). Lyft similarly migrated to a Redis-based geolocation system, achieving up to 15 million queries per second on their Redis cluster for location lookups. In Redis, one straightforward schema is to have a single sorted set of all drivers’ geospatial data (which works for moderate sizes). At Uber/Lyft scale, that gets partitioned (sharded) – more on that in a moment.
A durable database (like Cassandra) stores the historical or long-lived data. Uber writes all raw GPS updates to Cassandra for durability, since Cassandra is optimized for fast writes and can scale horizontally. This provides a source of truth and allows offline analysis (e.g., reconstructing past trips, or debugging). However, queries to Cassandra for real-time “who’s nearby” are too slow, which is why the in-memory cache is front and center in handling live requests. In some architectures, the persistent store is also used to seed or recover the in-memory index if needed (e.g., on a service restart, load recent driver locations from DB).
For Uber, incoming raw GPS points are written to a fast in-memory cache (Redis) for quick retrieval and buffering (for map matching context), and also appended to a persistent store (Cassandra) for durability. The in-memory layer can expire old data and serves immediate queries, while the database provides long-term storage and eventual consistency.
One of the trickiest parts of geospatial data management at scale is sharding – dividing the workload across multiple servers or partitions. Two main strategies are used (sometimes in combination):
Sharding by driver (key-based)
For example, hashing the driver’s ID and assigning to one of N shards. This evenly distributes write load (each driver consistently goes to one shard), but complicates read queries because a search for nearby drivers might require checking all shards (since nearby drivers could have any IDs). This was an issue in naive implementations. Lyft’s early approach using a user database had “region” and “driver_mode” indexes to try to limit the search, but it didn’t scale well. A pure ID hash sharding isn’t optimal for spatial queries.
Sharding by space (region-based)
Divide the world or a city into regions and assign each region’s data to a shard. This way, a query for “nearby drivers” only needs to query the shard responsible for that region. The challenge is defining regions – city boundaries or fixed grids can be used, but drivers near the boundary of a region need special handling (e.g. search in adjacent region as well).
Uber’s system uses a variant of this. They leverage H3’s hierarchy or geohash prefixes to shard spatially. For instance, they could assign each high-level cell (or group of cells) to a particular backend server. Uber’s “ringpop” library (a consistent hashing mechanism) is used to partition services such that each server handles a subset of the spatial data. Essentially, they hash some spatial key (like an H3 cell ID or geohash prefix) to a server, ensuring all drivers in that cell range go to the same server. If a driver crosses into a new cell region, their data might migrate to a different server (which is a complexity to manage).
The benefit is huge. Queries for nearby drivers (in a given area) hit only the server(s) responsible for that area, rather than every server. This is how Uber’s system scales horizontally – “they scale writes by adding more servers, and reads by adding replicas”. Each shard’s data can be replicated to a few servers for redundancy and read capacity, using eventual consistency.
Query fan-out
Since the data is sharded across many servers by location, a naive approach would query all servers and combine results (expensive). Instead, as described, we partition space such that only one or a few servers need to be queried for any given rider. This dramatically reduces the query fan-out. Uber’s partitioning via consistent hashing ensures a single responsible server (or replica set) for a given spatial key. This way the matching service can directly query the correct server (often via an RPC call) that holds the local index for that area.
Hybrid
Some systems use a two-level index: e.g. first route the query to a set of shards by region, then within each shard use an in-memory index to narrow down results. Uber’s consistent hash ring (Ringpop) helps route requests to the right shard based on a key (likely something derived from location). This avoids a central coordinator; each service knows the hash ring and can independently compute where to send a request for “location around (lat,lon)”.
Consistency and Replication
Geospatial data is inherently real-time and transient – a slightly stale location is usually not catastrophic (drivers move). Thus, many systems accept eventual consistency in exchange for availability and speed. For example, if a driver’s location update is processed by one data center, it might asynchronously replicate to a backup data center a few hundred milliseconds later. In the interim, a query from the backup DC might not yet see the very latest update. This is generally acceptable as long as the window is small, but the design ensures that typically a rider’s request is served from the same regional cluster that the driver’s updates are going to (locality).
Uber has a primary-active data center per region and a hot standby; if the primary fails, the backup takes over and starts receiving updates. This implies that under normal conditions, cross-datacenter consistency isn’t a big issue – all the action is within one DC, replicated to another for disaster recovery.
When replication is used within a cluster (for scaling reads), the geo-index might be kept in memory on multiple servers. Those servers either subscribe to a stream of updates or use a master-replica system (like Redis replication). With Redis, one could use a primary instance for each shard and have one or more replicas that also serve read queries. If the replication lag is low, read queries (finding drivers) will see nearly up-to-date information. In summary, these systems favor fast, local writes and tolerate a bit of staleness rather than doing expensive distributed transactions for each update.
When a rider requests a trip, the system needs to find nearby drivers very quickly. This happens millions of times every day, so the system must be fast and able to scale. To make this work, driver locations are constantly updated and organized using a spatial grid. This grid could be something like H3, geohash, or a quadtree. These systems divide the map into small regions, and each driver is tagged with the region they are currently in.
When a rider opens the app or requests a ride, the system looks for drivers near their current location. There are two common ways to do this.
The first method is called a radius search. The system finds all drivers within a certain distance from the rider, like three kilometers. Some tools, like Redis, can do this directly using special commands. Databases like PostGIS can also handle these kinds of searches accurately. This method gives precise results but may cost more when used at a very large scale.
The second method is a shortcut called a bounding box. Instead of checking inside a circle, the system draws a square that completely covers that circle. It finds all drivers in the square first, then filters out any drivers that are actually outside the circle. This method is fast and works well with simpler indexes.
In large-scale systems, the search usually happens in two steps. First, the system uses a grid to find drivers in the nearby area. Then it filters and sorts the results more carefully. If the system uses H3, it finds all nearby hexagons around the rider using a built-in function. If it uses geohash, it checks the rider’s current cell and the surrounding ones. If it uses a quadtree, it finds which cell the rider is in, then checks that cell and nearby ones by following the tree structure. The quadtree is special because it can automatically divide the map more finely in crowded areas, which helps when there are many drivers in one place and fewer in others. That makes the search more efficient, especially in cities.
After the nearby regions are selected, the system calculates the exact distance between the rider and each driver. This helps remove drivers that are outside the intended radius. Then the system sorts the results.
To make sure the system can scale, drivers are not stored all in one place. As mentioned, the map is split into regions. Each region might be handled by a different server or cache. When a rider makes a request, the system looks at their region and sometimes the regions around it. This avoids unnecessary work and keeps the system fast.
Once the nearby drivers are found, the next step is choosing the best one. Usually the closest driver is chosen, but distance is not always the best measure. Many systems use estimated time of arrival, which takes into account traffic and road conditions. The system might also consider the driver’s rating, how often they accept rides, or how long they’ve been waiting.
Sorting and Ranking
After obtaining the set of candidate drivers near the rider, the system needs to pick the “best” driver to dispatch. Proximity is a major factor – usually the driver closest (by time or distance) is favored. Uber and others actually sort by ETA (estimated time of arrival), not just distance.
ETA accounts for traffic and road network, whereas straight-line distance does not. The backend can call a service or use a matrix of precomputed travel times to each driver, but that’s beyond our scope. For our purposes, assume the nearest distance drivers correlate to nearest ETA. Other factors like driver ratings, acceptance rate, or how long they’ve been waiting might be considered in the final ranking too, but those are part of the matching logic on top of the location query.
Nearby driver search in large ride-sharing platforms is enabled by fast spatial lookups using indexes (geohash grids, H3 hexagons, etc.) and in-memory stores, combined with smart partitioning to handle load. The result is that when you open the app or hit “Request,” the system can almost instantly say “finding drivers…” and within a second or two assign a driver who was among the closest to your pin on the map.
Each method for indexing location data has its strengths and weaknesses. Grid-based systems like geohash and H3 are fast and scale well, making them ideal for real-time services with many users. However, they work with fixed-size cells, so nearby searches can sometimes include drivers just outside the desired area or miss drivers near cell edges. This is usually fine, since the system can filter results afterward based on exact distance.
Quadtree, on the other hand, uses an adaptive structure that divides space more precisely based on data density. In crowded areas, it can split cells into smaller regions, giving more control over resolution. This makes it more flexible for handling uneven driver distribution. But quadtree queries can be more complex and slower to compute, since you have to walk the tree and manage region boundaries manually.
Recovery
In-memory caches like Redis are very fast and are used to store the latest driver locations. But they don’t keep data forever. If a cache server crashes, the data in it could be lost. That’s why systems also write data to a more permanent database. This way, the data can be recovered if something goes wrong or rebuilt when drivers come back online.
Stateless
The system also needs to be able to handle failures. Uber, for example, uses stateless servers for handling location updates. If one of those servers fails, other servers take over its work. Drivers also reconnect and get assigned to a new server.
Hotspots
Another challenge is dealing with crowded areas. For example, if many drivers are in the same place like an airport parking lot, they might all end up in the same grid cell. This creates a “hot spot.” The system can fix this by zooming in to use smaller cells or by handling that batch of drivers more efficiently.
Eventual Consistency
Because location data changes so quickly, it’s hard to keep everything perfectly in sync. As mentioned, instead of trying to make every copy of the data exactly the same at all times, some systems accept a small delay. It’s more important that the updates for each individual driver arrive in the right order and that old data, like a driver who went offline, is removed so they don’t show up in searches by mistake.
Limiting search radius / result size
The system doesn’t actually want all drivers within 10 km, it usually just needs the closest handful (maybe to dispatch the nearest 5 for a multi-offer, etc.). Many queries therefore have a cutoff: e.g., get me the 50 nearest drivers within 3 km. This can be done by the query itself (Redis allows specifying COUNT or limiting radius) or by simply truncating the sorted results. By keeping the query tight (small radius, limited count), the workload per query is reduced. Urban areas with too many drivers don’t need a large radius; rural areas might increase radius but there are fewer drivers anyway.
Kafka
Kafka helps ride hailing systems handle sudden spikes in traffic by acting as a buffer between services. When a large number of drivers or riders send updates at once, Kafka stores those messages in a queue instead of sending them directly to backend services. This keeps the system from being overloaded. For example, during heavy rain or after a big event, thousands of people might open the app or request rides at the same time. Rather than causing the system to crash, Kafka holds these messages and lets other services process them at their own pace.
Kafka also breaks the data into partitions so that many services can read from different parts of the stream at the same time. This makes it easy to scale. If one service cannot keep up, more worker services can be added and each one will take care of a portion of the data. If a service crashes or slows down, Kafka does not lose any messages. It waits for the service to recover and continue reading where it left off. Since Kafka writes data to disk and copies it across servers, it is safe from data loss even during high traffic or failure.
This setup allows the ride hailing system to handle millions of location updates, ride requests, and trip events per second. Kafka’s ability to store, replay, and spread data across workers makes it a key part of building a fast and reliable real time platform.
Smoothing and Filtering
GPS data is noisy – errors of 5-50 meters are common in urban canyons. To improve real-time accuracy, apps and servers apply filtering algorithms on the stream of raw locations. A popular choice is the Kalman filter, which uses the previous state (position, velocity) to predict the next state and then corrects it with the new GPS observation.
Lyft’s engineering team, for example, used an Unscented Kalman Filter (UKF) to smooth real-time driver location and even estimate vehicle speed.
The Kalman filter assumes noise is near Gaussian; it works well for mild GPS noise. Uber found that in downtown areas with severe signal multipath, a basic Kalman filter was insufficient.
They turned to more advanced techniques like particle filters combined with 3D map data to achieve better accuracy.
A particle filter simulates many possible positions (“particles”) and weights them by how well they match the incoming signals and map constraints, eventually converging on the most likely true location. These filtering techniques significantly reduce jitter (e.g. jumping markers on the map) and prevent spurious large jumps.
Map Matching
Sometimes GPS signals aren’t perfect and may show a driver slightly off the road, like on a sidewalk or even inside a building. To fix this, the system uses a technique called map matching, which adjusts the raw GPS points to the nearest road. This helps make sure drivers are shown where they actually are on the road. The system looks at recent GPS points and uses algorithms to guess which road the driver is on. Uber, for example, keeps a short history of GPS data in memory and uses that to match the driver to the right street in real time. This makes things like route tracking and ETA calculations much more accurate.