Uber Driver Location and Dispatch Architecture
Uber replaced relational databases for real-time driver geospatial state with a purpose-built geospatial indexing system using Google S2 cell hierarchies, reducing proximity query latency from seconds to sub-100ms across millions of concurrent active driver locations.
Uber's dispatch system must match riders to nearby drivers within seconds across cities with hundreds of thousands of active drivers simultaneously. The initial architecture used PostgreSQL with PostGIS for geospatial queries, but at scale, a "find all drivers within 2km of this point" query becomes a full-table scan or requires R-tree index traversal that does not scale to millions of active entities updating their position every 4 seconds. Uber developed Schemaless (a custom column-store on MySQL) for durable trip records, and moved real-time driver location state to an in-memory geospatial system using Google's S2 cell hierarchy: a hierarchical decomposition of the globe into cells at multiple zoom levels that enables O(log n) proximity queries. Driver location updates flow through a dispatch gateway at approximately 1-4 updates per second per active driver; S2 cell lookups find candidates in microseconds for the matching algorithm to rank.
Scale at Decision Point
Users
~1 million active drivers globally by 2016; 75 million monthly active users by 2017
Data Volume
~1 million driver location updates per second at peak globally; ~200 bytes per update; trip records in Schemaless growing at billions of rows per year
Request Rate
~150,000 dispatch matching operations per minute globally at 2016 scale; ~4 driver location updates per driver per second
Schemaless (custom column-store on MySQL) for durable trip/driver records; dispatch service with in-memory S2 cell geospatial index; Kafka for location event streaming to downstream analytics
Architecture Evolution
Initial Architecture
PostgreSQL with PostGIS for all location data including real-time driver positions, trip records, and geospatial queries. Driver location updates were written to PostgreSQL on each heartbeat; dispatch queries used PostGIS ST_DWithin() for radius search. As the active driver count exceeded tens of thousands per city, PostGIS radius queries required 200-800ms per lookup: too slow for the sub-second dispatch matching SLA. A separate MySQL database handled user and payment records. Uber ran separate database instances per city, which provided geographic isolation but created operational complexity as city count grew past 100.
- PostGIS radius queries at 100,000+ concurrent active drivers exceed 200ms latency: unacceptable for real-time dispatch
- Per-city database instances multiply operational burden: 100 cities = 100 separate PostgreSQL deployments
- Real-time driver location writes compete with trip record reads on the same PostgreSQL instance
- No efficient path for multi-city driver queries (cross-city trips, airport pickups)
Evolved Architecture
Multi-tier storage model with data classified by access pattern and durability requirement. Schemaless (Uber's custom column-store built on MySQL) stores durable trip records, driver profiles, and historical location traces: it provides flexible schema-per-row semantics suitable for evolving data models while preserving MySQL's ACID guarantees for trip state transitions. Real-time driver location state is maintained in a dispatch service with an in-memory geospatial index partitioned by S2 cells at zoom level 12 (approximately 3km per cell at the equator). Driver location updates update the in-memory S2 cell index directly; dispatch proximity queries look up the target cell and adjacent cells to find driver candidates within the search radius. Kafka carries driver location events to downstream consumers (surge pricing computation, ETA calculation, analytics). Redis stores rider session state and rate limiting for the rider-facing API.
- In-memory S2 cell index is not durable: dispatch service restart requires rebuilding the index from Kafka replay or a snapshot
- S2 cell boundaries create edge artifacts: a driver 10 meters across a cell boundary is in a different cell than a rider 10 meters on the other side
- Schemaless on MySQL still has single-primary write limits per shard: sharding by driver_uuid distributes this but requires consistent hash routing
- Location stream at 1M+ updates per second requires careful Kafka partition management to prevent consumer lag accumulation
Key Transitions
Trigger
Trip data models evolved rapidly as Uber added products (UberPool, UberEATS, freight). Traditional MySQL schema migrations required ALTER TABLE locks, creating downtime risk during feature launches. Additionally, different trip types required different data structures that were awkward to represent in a fixed schema. The team designed Schemaless to provide per-row schema flexibility while keeping MySQL as the durable storage engine.
Before
Fixed-schema MySQL for trip records; ALTER TABLE required for each new trip type
After
Schemaless column-store on MySQL; per-row JSON cells alongside indexed columns
Outcome
Trip data model evolution decoupled from database schema migrations. New trip types (Pool, Express Pool) launched without ALTER TABLE downtime. Schemaless became the primary data store for Uber's core trip data and was described in a public engineering blog post in 2016 that influenced other high-growth startups' database design.
Lessons
- Schema flexibility and ACID guarantees are not mutually exclusive: a JSON-cell-per-row model on MySQL provides both
- Column-store semantics on a row-store database trades storage efficiency for schema agility: acceptable for trip records where correctness outweighs storage cost
- ALTER TABLE locks are a product velocity constraint for fast-iteration startups; addressing this early is worth the architectural investment
Trigger
PostGIS radius queries for driver dispatch exceeded 300ms latency as active driver count in major markets (San Francisco, New York, Beijing) exceeded 50,000 simultaneously. Dispatch matching requires proximity results within 100ms to maintain sub-second rider experience. The team evaluated Elasticsearch geospatial, Geohash indexing, and S2 cell hierarchies: S2 was selected for its hierarchical properties that enable efficient neighbor-cell queries without post-filtering.
Before
PostGIS radius queries on PostgreSQL; 300ms+ dispatch latency at scale
After
In-memory S2 cell geospatial index at zoom level 12; sub-10ms proximity queries
Outcome
Driver proximity query latency reduced from 300ms to under 10ms. Dispatch matching throughput increased 30x on equivalent hardware. S2 cell neighbor queries (needed for radius search across cell boundaries) execute in microseconds due to the hierarchical bit manipulation properties of S2 cell IDs.
Lessons
- Purpose-built geospatial indexing outperforms general-purpose databases for real-time proximity queries by 10-100x at millions of active entities
- S2 cell hierarchy enables O(log n) proximity queries through hierarchical cell enumeration: the key property is that nearby points share common cell ID prefixes
- Geospatial data and durable record data have different access patterns and should live in different stores
Trigger
S2 cells have irregular shapes and sizes at different zoom levels, which creates complications for surge pricing zone definition: zone boundaries that look uniform on a map correspond to irregular cell shapes in S2. Uber developed H3, a hexagonal hierarchical indexing system, as an alternative with more uniform cell shapes for zone-based analytics.
Before
S2 cell dispatch index; PostGIS polygon queries for surge pricing zones
After
H3 hexagonal index for surge pricing and analytics; S2 retained for real-time dispatch
Outcome
H3 hexagonal cells provided more uniform geographic coverage for surge pricing zones. Uber open-sourced H3 in 2018; it has since become an industry standard for geospatial analytics. S2 remained for real-time dispatch due to its superior neighbor query performance.
Lessons
- Different geospatial workloads favor different indexing schemes: dispatch (point proximity) and analytics (zone aggregation) have different optimal index structures
- Open-sourcing H3 created a positive feedback loop: external contributors improved the library, benefiting Uber's internal use cases
Key Lessons
Geospatial proximity at millions of entities requires purpose-built hierarchical indexing: PostGIS cannot serve sub-100ms dispatch queries at this scale
PostGIS ST_DWithin() on 1 million driver locations requires either a full R-tree scan or careful index tuning. At 50,000 active drivers per city with updates every 4 seconds, the index is continuously rewritten while being queried. S2 cell hierarchies avoid this by partitioning the problem: a proximity query touches only the target cell and its immediate neighbors (typically 8-9 cells), regardless of the total driver count. Query cost is O(1) with respect to total driver count.
Applicable when: You are building a location-based matching system with more than ~10,000 concurrently tracked entities requiring sub-100ms proximity queries
Classify data by access pattern and durability requirement before choosing a storage engine
Uber's evolved architecture uses different stores for different access patterns: Schemaless for durable trip records (ACID, schema-flexible), in-memory S2 index for real-time dispatch (fast, ephemeral), Redis for session state (fast, moderately durable), Kafka for location event streaming (ordered, replayable). Each store is chosen for its access pattern fit. Using a single store for all data was the root cause of the original PostGIS performance problems.
Applicable when: You are designing a multi-workload system and selecting databases; classify each data type independently before selecting stores
Location update frequency creates unexpected write amplification: 1M drivers updating every 4 seconds is 250,000 writes per second
At Uber's scale, driver location updates alone generate 250,000 writes per second globally. A relational database receiving this write load while also serving dispatch reads is guaranteed to reach its write saturation point. Routing location updates to an append-only log (Kafka) and maintaining derived state in an in-memory index separates the write path from the read path, allowing each to scale independently.
Applicable when: You are tracking high-frequency position updates for a large number of entities and need to serve both real-time queries and historical analysis
Technologies
Patterns
Failure Modes Encountered
Related Scenarios
Sources
- Engineering BlogThe Architecture of Schemaless, Uber Engineering's Trip Datastore Using MySQL (Uber Engineering Blog) (2016)
- Engineering BlogDesigning Schemaless, Uber Engineering's Scalable Datastore Using MySQL (Uber Engineering Blog) (2016)
1 source is pending verification and has been hidden until a followable citation is available.