SLIDE 58: Section Intro, Geospatial Systems
Section 6: Geospatial Systems
Recognition signal: “When the interviewer asks about finding nearby entities, location-based queries, or real-time position tracking, this is the section you reach for.”
Geospatial systems solve a specific class of problem: given a point on Earth, find other points near it, and do so at extreme throughput with data that changes every few seconds. In a ride-sharing platform, this translates to “which drivers are near this rider?” answered 250+ times per second against a spatial index receiving 1.25 million position updates per second.
This is the section that separates a strong interview answer from a generic one. Most candidates describe matching as “find the closest driver.” This section gives you the vocabulary and depth to explain how that lookup actually works at scale.
What We’ll Cover
- Why geospatial is the architectural family that defines ride-sharing
- The naive approach and why it fails
- Three spatial indexing strategies: Geohashing, Quadtrees, S2/H3 Cells
- The moving objects problem: indexing data that changes every 4 seconds
- The boundary problem and its solution
- Location Service architecture with Redis
- Geofence service for zone-based rules
- Decision framework for choosing a spatial index
- How these patterns transfer to other systems
Where This Section Fits
SLIDE 59: Why Geospatial Is the Core Differentiator
If you have designed an Instagram-style content platform, you have solved problems like feed generation, content delivery, and follower graphs. None of those problems appear in a ride-sharing system. And the core problem that does appear in ride-sharing, finding nearby moving entities at extreme write throughput, does not appear in content platforms.
This is the architectural family that makes ride-sharing a distinct system design problem.
What Makes This Different
Instagram, Twitter, and YouTube serve static or slowly-changing content. The data is written once and read many times. Caching is straightforward because content does not move.
In a ride-sharing system, the most queried data (driver positions) changes every 3-4 seconds. There are 5 million active drivers, each sending GPS coordinates continuously. Every ride request triggers a spatial query against this constantly-changing dataset. Traditional database indexing (B-trees on latitude/longitude columns) cannot handle 1.25 million updates per second while simultaneously serving sub-200ms read queries.
The entire matching system depends on answering one question efficiently:
“Which drivers are within 5 kilometers of this rider, right now?”
That question sounds simple. The next two slides show why it is not.
SLIDE 60: The Naive Approach: Scan Every Driver
The most intuitive solution: for each ride request, calculate the distance to every active driver, sort by distance, and pick the closest.
def find_nearby_drivers(rider_lat, rider_lng, all_drivers, radius_km):
candidates = []
for driver in all_drivers:
dist = haversine(rider_lat, rider_lng, driver.lat, driver.lng)
if dist <= radius_km:
candidates.append((driver, dist))
return sorted(candidates, key=lambda x: x[1])[:10]
This is O(N) per query where N is the total number of active drivers. For a single city with 50,000 active drivers, every ride request performs 50,000 distance calculations.
The haversine formula (computing great-circle distance on a sphere) involves trigonometric operations: two sine calculations, two cosine calculations, an arctangent, and a square root. Each call costs roughly 100-200 nanoseconds on modern hardware.
Per query: 50,000 drivers x 200 ns = 10 ms
10 milliseconds per query does not sound terrible. But this is one city. And it gets worse at scale.
SLIDE 60B: The Naive Approach: Why It Fails at Scale
Worked Calculation: City Scale
Active drivers in city: 50,000
Ride requests per second: 250 (city level, not global)
Distance calculations/sec: 50,000 x 250 = 12,500,000
At 200 ns per haversine: 12.5M x 200 ns = 2.5 seconds of CPU time per second
A single CPU core is already saturated at 250 requests/sec for one city. And this ignores the sorting step, memory access patterns, and the fact that peak demand is 4x average.
Fundamental Problem: No Pruning
The deeper issue is not CPU cost per calculation. It is that 99% of the calculations are wasted. A rider in downtown Mumbai does not need distance calculations to drivers 40 kilometers away in the suburbs. But the naive approach checks every single driver regardless of location.
What we need is a data structure that eliminates irrelevant drivers before we start calculating distances. Instead of checking 50,000 drivers, we want to check only the 50-200 drivers that are plausibly nearby.
This is exactly what a spatial index does.
SLIDE 61: Spatial Indexing: The Key Idea
A spatial index divides geographic space into regions (cells) and assigns each driver to the cell that contains their current position. When a ride request arrives, instead of scanning all drivers, the system identifies which cell the rider is in, then checks only the drivers in that cell and its neighboring cells.
Before spatial indexing: check all 50,000 drivers per query.
After spatial indexing: check 50-200 drivers per query.
That is a 250-1,000x reduction in work per query.
Three main approaches exist for dividing space into searchable cells. Each makes different trade-offs between simplicity, adaptiveness, and scalability:
- Geohashing: fixed-grid string-based encoding. Simple to implement, works in any database.
- Quadtrees: recursive subdivision that adapts to density. Dense areas get smaller cells.
- S2/H3 Cells: hierarchical spherical geometry used in production at Google and Uber.
All three solve the same fundamental problem. The differences are in how they handle non-uniform density, how they distribute across servers, and how complex they are to implement.
Interview Tip:
In an interview, name all three approaches, then pick one and justify your choice. Saying “I would use geohashing because it is simple to implement with Redis and handles our scale” is a strong answer. Saying only “I would use a spatial index” without naming a specific approach is too vague.
SLIDE 62: Geohashing: Encoding Location as a String
Geohashing converts a latitude/longitude pair into a short alphanumeric string by recursively subdividing the world into grid cells. Each subdivision adds one character to the string. Longer strings mean smaller cells and higher precision.
How It Works
The algorithm alternates between longitude and latitude, splitting each dimension in half at every step. The binary choices (left/right, top/bottom) are concatenated into a binary string, then encoded as Base32.
The critical property: nearby locations share string prefixes. Two points in the same neighborhood will have geohashes starting with the same characters (e.g., dr5ru7 and dr5ru6). This makes spatial queries reducible to string prefix matching, which every database can index efficiently.
This prefix property is what makes geohashing practical. You can store geohashes in Redis, PostgreSQL, DynamoDB, or any system that supports string indexes. No specialized geospatial database is required.
SLIDE 62B: Geohashing: Precision Levels and Nearby Queries
Precision Level Reference
For ride-sharing, precision 6 (~1.2 km cells) is the typical choice. It is granular enough that each cell contains a manageable number of drivers (10-100 in urban areas) but coarse enough that you do not create billions of nearly-empty cells.
How a Nearby Query Works
When a rider requests a ride, the system:
- Computes the rider’s geohash at precision 6 (e.g., dr5ru7)
- Computes the 8 neighboring geohash cells (the surrounding ring)
- Queries all 9 cells for active drivers
- Calculates actual distances to the returned drivers (post-filtering)
- Returns the nearest candidates
Querying 9 cells instead of 1 solves most boundary cases. A driver sitting just across a cell boundary will still be found because neighboring cells are always included.
Rider geohash: dr5ru7
Query cells: dr5ru7, dr5ru6, dr5ru5, dr5rud, dr5ruh,
dr5ruk, dr5rum, dr5run, dr5rup
Total cells: 9
SLIDE 63: Geohashing: Pros, Cons, and Edge Cases
Strengths
Geohashing is the simplest spatial indexing approach to implement. The geohash is a plain string, so it works with any database that supports string indexing: Redis, PostgreSQL, DynamoDB, Cassandra. No specialized libraries or in-memory data structures are needed.
It distributes naturally: you can shard by geohash prefix. All drivers in the “dr5” region go to one shard, all drivers in “9q8” go to another. This aligns well with geographic partitioning.
Weaknesses
The fixed grid is the main limitation. Every cell at a given precision level is the same size, regardless of how many drivers are in it. A geohash cell covering downtown Manhattan and a cell covering rural Kansas have the same dimensions. Downtown might have 500 drivers in one cell. Rural Kansas might have zero.
This means:
- Dense areas return too many candidates per cell (over-fetching)
- Sparse areas waste cells on empty space
- No automatic adaptation to demand patterns
The Boundary Problem
Two drivers 10 meters apart can end up in different geohash cells if they straddle a cell boundary. The 9-cell query (target + 8 neighbors) mitigates this, but it does not eliminate all edge cases. Near the edges of geohash regions, prefix-based adjacency can break: cells that are geographically adjacent may not share a string prefix.
This edge case is rare and manageable, but it is worth mentioning in an interview to show depth.
SLIDE 64: Quadtrees: Recursive Spatial Decomposition
A quadtree starts with a single cell covering the entire service area. When a cell contains more drivers than a threshold (e.g., 100 drivers), it splits into four equal sub-cells. Each sub-cell can split further if it also exceeds the threshold.
The result: dense areas (downtown, airports) get many small cells. Sparse areas (suburbs, highways) keep large cells. The data structure automatically adapts to the distribution of drivers.
The Splitting Rule
MAX_DRIVERS_PER_CELL = 100
When a cell has > 100 drivers:
Split into 4 equal sub-cells (NW, NE, SW, SE)
Redistribute drivers into the appropriate sub-cells
Each sub-cell can split further if needed
When a cell has < 25 drivers (after drivers leave):
Merge back into parent cell (optional, prevents thrashing)
Downtown Manhattan might reach depth 8 (cells of ~50 meters). A rural highway might stay at depth 2 (cells of ~10 kilometers). The tree depth varies across the service area based entirely on where drivers actually are.
SLIDE 64B: Quadtrees: Tree Structure, Splitting, and Querying
Tree Structure
Each node in the quadtree is either a leaf (contains driver positions) or an internal node (has exactly four children). The tree is not balanced. Its shape is determined by the spatial distribution of drivers, not by insertion order.
Nearby Query
- Start at the root. Traverse down to the leaf cell containing the rider’s position.
- Check all drivers in that leaf cell.
- Check neighboring leaf cells (may require traversing back up the tree and into adjacent branches).
- Calculate actual distances and return the nearest candidates.
The traversal is O(log N) to find the rider’s cell, where N is the total number of cells. Checking neighbors requires walking the tree, which is more complex than geohash’s simple “8 adjacent strings” but handles non-uniform density correctly.
Update Cost
Every time a driver moves, the quadtree must check whether the driver has crossed a cell boundary. If yes, the driver is removed from the old leaf and inserted into the new leaf. If the old leaf drops below the merge threshold, it may merge with its siblings. If the new leaf exceeds the split threshold, it splits.
At 1.25 million updates per second, this means 1.25 million potential tree modifications per second. This is why production quadtrees are kept in memory on a single server (per city), not distributed across a cluster.
SLIDE 65: Quadtrees: Pros, Cons, and Trade-Offs
Strengths
Adaptive density is the primary advantage. The quadtree naturally allocates more cells to areas with more drivers, which means nearby queries return a consistent number of candidates regardless of whether the rider is downtown or in the suburbs. This produces more consistent query performance than a fixed grid.
Nearest-neighbor queries are efficient because the tree structure allows pruning entire branches that are too far away. You do not check cells that cannot possibly contain a closer driver than your current best candidate.
Weaknesses
The quadtree is an in-memory data structure that is difficult to distribute across multiple servers. Unlike geohash strings that can be stored in any distributed database, a quadtree’s tree structure relies on pointer-based traversal. Splitting it across machines introduces cross-machine traversals during neighbor searches.
Every driver movement triggers a tree update. At 1.25 million updates per second globally, the tree is being modified continuously. This requires careful concurrency control: reader-writer locks, or a copy-on-write strategy where reads see a consistent snapshot while writes build a new version.
Practical Constraint
Quadtrees work best when partitioned by city. Each city has its own quadtree on a dedicated server (or pair of servers for redundancy). This keeps the tree small enough to fit in memory and avoids cross-server traversals. It also aligns with the geographic partitioning strategy from Section 11 (Scaling): ride-sharing operations are city-local by nature.
SLIDE 66: S2 Cells: Spherical Geometry at Production Scale
Google’s S2 Geometry Library takes a fundamentally different approach. Instead of projecting the Earth’s surface onto a flat grid (like geohashing), S2 projects it onto the six faces of a cube, then recursively subdivides each face into cells using a Hilbert curve.
Why Spherical Geometry Matters
Flat grids distort near the poles. A geohash cell at the equator covers a different real-world area than a cell at 60 degrees latitude, even at the same precision level. S2 cells have approximately equal area everywhere on Earth because they account for the sphere’s curvature.
S2 Cell Hierarchy
S2 cells have 31 levels of precision. Each cell has a 64-bit cell ID that encodes its position in the hierarchy. Parent-child relationships are embedded in the ID structure, making it fast to determine whether one cell contains another or to find a cell’s neighbors.
Level 0: ~85,000 km per side (whole face)
Level 12: ~5 km per side (comparable to geohash precision 5)
Level 14: ~1.2 km per side (comparable to geohash precision 6)
Level 16: ~300 m per side (urban block)
Level 20: ~20 m per side (building-level)
S2 is used by Google Maps, Google Earth, and many of Google’s internal spatial systems. The library is open source and available in C++, Java, Go, and Python.
SLIDE 66B: S2 and H3: How Production Systems Use Hierarchical Cells
Uber’s H3: Hexagonal Hierarchical Grid
Uber developed H3 as an alternative to S2 that uses hexagonal cells instead of square cells. The key advantage: every hexagonal cell has exactly 6 equidistant neighbors, while a square cell has 8 neighbors at two different distances (4 edge-adjacent, 4 corner-adjacent).
Square grid neighbors:
Edge neighbors: 4 cells at distance d
Corner neighbors: 4 cells at distance d x sqrt(2)
Total: 8 neighbors, two different distances
Hexagonal grid neighbors:
All neighbors: 6 cells at distance d
Total: 6 neighbors, all equidistant
Equidistant neighbors simplify nearby queries because every neighbor cell is the same “distance” from the center cell. There is no ambiguity about whether to include corner neighbors, and the search radius maps cleanly to “rings” of hexagons.
H3 Resolution Levels
H3 is open source, available in C, Python, Java, and JavaScript. It is used in production at Uber for surge pricing zones, supply-demand analysis, and driver positioning.
Interview Tip:
You do not need to know the implementation details of S2 or H3 to use them effectively in an interview. Mentioning “Uber uses H3 with hexagonal cells because equidistant neighbors simplify nearby queries” demonstrates awareness of production approaches without requiring you to explain the Hilbert curve projection.
SLIDE 67: Geohash vs Quadtree vs S2/H3: Comparison Table
Decision Framework
Choose Geohash when: you want simplicity, you are using Redis GEOADD (which uses geohash internally), or you need to store spatial data in a general-purpose database. This is the right default for most interview answers.
Choose Quadtree when: driver density is highly non-uniform, you can afford an in-memory solution per city, and you need adaptive cell sizes without manual tuning.
Choose S2/H3 when: you are building a production system at global scale, you need hierarchical precision (coarse for regional queries, fine for local), or you want to match what Uber and Google actually use.
SLIDE 68: The Harder Problem: Indexing Moving Objects
Everything discussed so far assumes objects are stationary. A traditional spatial index (like a PostGIS index on restaurant locations) is built once and queried many times. The data changes rarely, perhaps when a restaurant opens or closes.
Drivers are not stationary. They move continuously, sending a new GPS position every 3-4 seconds. At 5 million active drivers globally, that is 1.25 million spatial index updates per second.
What Each Update Requires
For geohash: recompute the geohash string from new coordinates. If the string changed, delete the old entry and insert a new one. If the string is the same (driver moved within the same cell), update in place.
For quadtree: check if the new position is still within the current leaf cell. If yes, update coordinates. If no, remove from old leaf (possibly triggering a merge), insert into new leaf (possibly triggering a split).
For S2/H3: recompute the cell ID. If changed, update the index entry.
The Optimization
Most GPS updates do not cross a cell boundary. At geohash precision 6 (~1.2 km cells), a driver traveling at 50 km/h moves about 55 meters in 4 seconds. They will stay in the same cell for roughly 20+ consecutive updates before crossing a boundary.
This means the cell boundary check (comparing old and new geohash/cell ID) is cheap, and the expensive index modification (remove + insert) happens infrequently. The system processes 1.25 million position updates per second, but only a fraction of those require actual index restructuring.
SLIDE 68B: Update Strategies for Moving Drivers
Strategy 1: Update on Every GPS Tick
Write the new position to the spatial index on every incoming GPS update, regardless of whether the cell changed.
Pros: Simplest implementation. Position always fresh.
Cons: 1.25M writes/sec to the spatial index. Unnecessary if cell unchanged.
Redis handles this well because GEOADD is an upsert (update-or-insert) operation. The old position is overwritten in place. There is no separate “delete then insert” step.
Strategy 2: Update Only on Cell Boundary Crossing
Compare the new geohash/cell ID to the old one. Only modify the index if the cell changed.
Pros: Reduces index writes by ~80-95%. Lower write amplification.
Cons: Requires storing the previous cell ID per driver. Slightly stale within-cell position.
This is an optimization for quadtrees and custom spatial indexes where writes are expensive. For Redis GEOADD, the overhead of the boundary check may exceed the cost of the write itself, making Strategy 1 simpler and fast enough.
Strategy 3: Batch Position Updates
Collect GPS updates into micro-batches (every 1-2 seconds), then apply all updates to the spatial index at once.
Pros: Amortizes write overhead. Smoother write throughput.
Cons: Adds 1-2 seconds of latency to position freshness.
In practice, Strategy 1 with Redis GEOADD is the most common approach. Redis handles 500K+ GEOADD operations per second per instance, so 3 instances cover the global load without needing write optimization.
SLIDE 69: Stale Position Tolerance and Write Amplification
How Stale Is Too Stale?
Not all position consumers need the same freshness. Different parts of the system tolerate different levels of staleness.
Write Amplification
Each GPS update touches multiple storage layers:
TTL on Position Records
Drivers can go offline without notification (phone dies, app crashes, network loss). The spatial index must not retain stale positions indefinitely. Solution: set a TTL on every position record.
Redis supports per-key TTL natively. For a quadtree, this requires a background sweeper that removes entries older than the threshold.
SLIDE 70: The Boundary Problem: Deep Dive
The boundary problem is the most commonly discussed edge case in geospatial indexing interviews. Understanding it and its solution demonstrates depth.
The Problem
A rider and a driver are 10 meters apart, but they sit on opposite sides of a cell boundary. If the system queries only the rider’s cell, it misses the driver entirely.
The Solution: Always Query Adjacent Cells
For geohash (square cells): query the target cell plus all 8 surrounding cells. Total: 9 cells per query.
For H3 (hexagonal cells): query the target cell plus all 6 surrounding cells. Total: 7 cells per query. Fewer cells because hexagons tile more efficiently.
Why 9 Cells Is Acceptable
Each cell at precision 6 contains roughly 10-100 drivers in an urban area. Querying 9 cells returns 90-900 drivers. Post-filtering by actual distance (haversine calculation on 90-900 candidates instead of 50,000) is trivially fast.
Without spatial index: 50,000 distance calculations per query
With spatial index: 90-900 distance calculations per query
Reduction: 55-555x fewer calculations
The boundary problem does not eliminate the benefit of spatial indexing. It adds a constant factor (query 9 cells instead of 1), which is negligible compared to the orders-of-magnitude reduction from not scanning all drivers.
Interview Tip:
If you mention the boundary problem proactively (“one edge case with geohashing is the boundary problem, which we solve by always querying adjacent cells”), it signals to the interviewer that you understand the approach deeply, not just at the surface level. This is one of the clearest ways to demonstrate depth in a system design discussion.
SLIDE 71: Location Service Architecture
The Location Service is the central component that connects GPS ingestion, spatial indexing, nearby queries, and location history. It sits in the Real-Time Services group from Section 4 (Architecture).
Write Path (GPS Updates)
- Driver sends GPS coordinates via WebSocket connection to the WebSocket Gateway
- Gateway forwards to Location Service
- Location Service validates the update (reasonable coordinates, driver is active)
- Location Service writes to Redis spatial index (GEOADD)
- Location Service publishes to Kafka for async processing (location history, analytics)
The write path is the hot path: 1.25 million operations per second. Every component on this path must be optimized for throughput. Validation is lightweight (coordinate range check, driver status check against cache). The Redis write is sub-millisecond. The Kafka publish is fire-and-forget from the write path’s perspective.
Read Path (Nearby Queries)
- Ride request arrives at Trip Service
- Trip Service calls Location Service with rider’s coordinates and a search radius
- Location Service queries Redis spatial index (GEOSEARCH within radius)
- Redis returns matching driver positions
- Location Service filters (active drivers only, correct vehicle type) and returns candidates
The read path is bursty: it spikes with ride request volume (250/sec average, 700/sec peak). Redis GEOSEARCH returns results in sub-millisecond time for datasets of 50K-500K entries. The read and write paths do not contend because Redis processes commands sequentially and both operations are sub-millisecond.
SLIDE 72: Redis for Real-Time Driver Positions
Redis is the most common technology choice for real-time driver positions in ride-sharing systems. Its built-in geospatial commands (GEOADD, GEOSEARCH, GEODIST) are purpose-built for this exact use case.
Why Redis
Redis stores all data in memory, which eliminates disk I/O latency. A single Redis instance handles 500,000+ GEOADD operations per second. The geospatial commands use a sorted set internally, with geohash-encoded scores, so all spatial operations are O(log N + M) where N is total entries and M is returned results.
Redis positions are ephemeral by design. They are overwritten on every GPS update and expire via TTL if updates stop. There is no durability concern because the spatial index is a real-time view, not a permanent record. Location history goes to a separate time-series database (Section 8).
Core Commands
GEOADD drivers -73.9857 40.7484 "driver_123"
Add or update a driver’s position. If driver_123 already exists, the position is overwritten.
GEOSEARCH drivers FROMLONLAT -73.9851 40.7489 BYRADIUS 5 km ASC COUNT 20
Find up to 20 drivers within 5 km of the given point, sorted by distance ascending.
GEODIST drivers "driver_123" "driver_456" km
Calculate the distance between two drivers in kilometers.
GEOPOS drivers "driver_123"
Return the current stored position of a specific driver.
SLIDE 72B: Redis Geospatial: Worked Commands
Scenario: Driver Comes Online in Manhattan
> GEOADD nyc_drivers -73.9857 40.7484 "driver_A1"
(integer) 1
> GEOADD nyc_drivers -73.9812 40.7527 "driver_A2"
(integer) 1
> GEOADD nyc_drivers -73.9903 40.7411 "driver_A3"
(integer) 1
Three drivers are now indexed in the nyc_drivers sorted set.
Scenario: Rider Requests a Ride
> GEOSEARCH nyc_drivers FROMLONLAT -73.9851 40.7489 BYRADIUS 2 km ASC COUNT 10 WITHCOORD WITHDIST
1) "driver_A1" 0.07 km -73.9857 40.7484
2) "driver_A2" 0.48 km -73.9812 40.7527
3) "driver_A3" 0.95 km -73.9903 40.7411
Three drivers found within 2 km. driver_A1 is closest at 70 meters. These candidates are passed to the Matching Service (Section 7) for scoring.
Performance Characteristics
GEOADD: O(log N) per operation. ~500K ops/sec per instance.
GEOSEARCH: O(N + log M) where N = results, M = total entries. Sub-millisecond for 50K entries.
Memory: ~100 bytes per driver (sorted set entry with geohash score).
50K drivers = ~5 MB. 500K drivers = ~50 MB.
At these numbers, a single Redis instance handles an entire large city. For a mega-city (1M+ active drivers), use Redis Cluster or partition by geographic sub-region within the city.
SLIDE 73: Geofence Service: Zones with Special Rules
Not all geographic areas follow the same rules. Airports have pickup queues. City centers have congestion surcharges. Certain neighborhoods have restricted pickup/dropoff zones. The Geofence Service manages these zone-specific rules.
What a Geofence Is
A geofence is a polygon defined by a set of coordinates that outlines a geographic boundary. When a rider’s pickup location or a driver’s current position falls within a geofence, special rules apply.
Zone Types
Implementation
Geofences are stored as polygons (lists of lat/lng vertices). When a ride request arrives, the system performs a point-in-polygon test: is the pickup location inside any defined geofence?
Geofences change infrequently (airport zones are stable, event zones are created hours in advance), so they are cached in memory and refreshed periodically. This is not a high-throughput problem like driver positions. It is a low-volume lookup that applies rules to specific ride requests.
SLIDE 74: Worked Example: Design Location Service for 50K Active Drivers
This worked example sizes the Location Service for a single large city and shows how the estimates translate into concrete infrastructure choices.
Given Values
City: Mumbai
Active drivers: 50,000
GPS update interval: every 4 seconds
Nearby query latency: sub-200ms target
Ride volume: 500,000 rides/day
Step 1: Write Throughput
GPS writes: 50,000 / 4 = 12,500 writes/sec
Redis GEOADD capacity: ~500,000 ops/sec per instance
Utilization: 12,500 / 500,000 = 2.5%
Verdict: single Redis instance, well within capacity.
Step 2: Memory Footprint
Per driver: ~100 bytes (sorted set entry)
50,000 drivers x 100 bytes = 5 MB in-memory
Redis available memory: typically 1-16 GB
Utilization: 5 MB / 1 GB = 0.5%
Verdict: memory is not a concern at this scale.
Step 3: Read Throughput
Ride requests: 500K/day / 86,400 ≈ 6/sec average, ~24/sec peak
Each triggers GEOSEARCH: sub-millisecond at 50K entries
Redis can handle 100K+ GEOSEARCH/sec
Verdict: read load is trivial.
Step 4: Location History Volume
12,500 writes/sec x 100 bytes = 1.25 MB/sec
1.25 MB/sec x 86,400 = 108 GB/day = ~39 TB/year
Verdict: time-series DB (TimescaleDB or Cassandra) for history.
Architecture Decision
For a city of 50K drivers, the Location Service is a single Redis instance for live positions and a TimescaleDB instance for history. The bottleneck is not memory (0.5% utilization), not query latency (sub-millisecond), and not write throughput (2.5% utilization). At this scale, the bottleneck is operational: network reliability for the WebSocket connections and monitoring for position freshness.
For a mega-city (500K active drivers), multiply everything by 10x. Write throughput reaches 125K/sec (25% of a single Redis instance), memory reaches 50 MB (still trivial), and history reaches 1 TB/day. Still manageable with a single Redis instance, but you are now closer to capacity and should plan for Redis Cluster or sub-city partitioning.
Interview Tip:
Walking through this calculation takes about 90 seconds. It shows the interviewer that you can take a global estimate (1.25M GPS/sec from Section 3) and narrow it to a deployable unit. Finish by stating: “A single Redis instance per city handles this comfortably, which makes geographic partitioning straightforward: one instance per city, independent scaling.”
SLIDE 75: Decision Flowchart: Choosing a Spatial Index
Expanded Decision Criteria
Start with Geohash if:
- You are using Redis (GEOADD uses geohash internally)
- You need simplicity and fast implementation
- Driver distribution is roughly uniform across the service area
- You want the spatial index to work in any database (PostgreSQL, DynamoDB, Cassandra)
- This is the strongest default for an interview answer
Consider Quadtree if:
- Driver density varies dramatically (10x difference between downtown and suburbs)
- You can afford in-memory storage per city (which you almost always can)
- You need consistent query performance regardless of local density
- You want adaptive cell sizing without manual precision tuning
Consider S2/H3 if:
- You are designing for global scale with hierarchical precision needs
- You need both coarse regional queries and fine local queries in the same system
- You want to match production approaches at Uber (H3) or Google (S2)
- You need hexagonal cells for equidistant neighbor queries (H3)
For Most Interview Answers
Geohash via Redis is the strongest default. It is simple, proven, and demonstrates that you understand spatial indexing without over-engineering. If the interviewer pushes on non-uniform density, pivot to quadtree. If they ask what Uber actually uses, mention H3.
SLIDE 76: Geospatial Patterns Applied to Other Systems
Everything in this section transfers to any system that needs to answer “find nearby X” queries. The specific algorithms, trade-offs, and implementation patterns apply directly.
The Transferable Principles
- Never scan all entities. Use a spatial index.
- Match the update frequency to the data lifecycle. Static data (restaurants) needs a different approach than moving data (drivers).
- Always query adjacent cells to handle the boundary problem.
- Choose your index based on density uniformity, distribution needs, and implementation budget.
- Separate the real-time spatial index (in-memory, ephemeral) from the historical record (persistent, time-series).
If you understand the geospatial design in this course, you can apply it to any of these systems by adjusting the update frequency, staleness tolerance, and query patterns.
SLIDE 77: Wrong vs Right: Geospatial Design Mistakes
Mistake 1: Scanning All Drivers
Wrong: “For each ride request, I would calculate the distance to every active driver and pick the closest one.”
Better: “I would use a spatial index, specifically Redis GEOADD with geohash-based lookup, so each nearby query checks only the drivers in the relevant cells rather than scanning all 50,000 drivers in the city.”
Why it matters: The naive O(N) scan is the most common mistake in ride-sharing interviews. It shows the candidate has not thought about the scale of the problem.
Mistake 2: Naming a Spatial Index Without Justifying the Choice
Wrong: “I would use a quadtree.” (then moves on)
Better: “I would use geohashing via Redis because it is simple to implement, handles our write throughput with GEOADD at 500K ops/sec, and distributes naturally by partitioning cities. If the interviewer asks about non-uniform density, I would discuss quadtrees as an alternative that adapts cell sizes to driver concentration.”
Why it matters: Naming the approach is not enough. The interviewer wants to see that you compared options and chose based on specific criteria.
Mistake 3: Ignoring Moving Objects
Wrong: “I would build a spatial index for driver positions.” (treats it as a static dataset)
Better: “Driver positions change every 3-4 seconds, so the spatial index receives 1.25 million updates per second globally. I would use Redis GEOADD which handles this as an upsert operation, and set a TTL of 15-20 seconds on each position so drivers who stop sending updates are automatically removed from the index.”
Why it matters: The moving objects problem is what makes ride-sharing geospatial design harder than a restaurant finder or store locator. Addressing it proactively shows depth.
SLIDE 78: Interview Practice: Geospatial Systems
Time Budget: 3-5 Minutes in a 45-Minute Interview
Geospatial is typically the deep-dive section. When the interviewer asks “how do you find nearby drivers?” or “tell me more about the location system,” this is your opportunity to demonstrate depth.
Recommended Flow
Minute 1: State the problem and why naive scanning fails
"Finding nearby drivers at 1.25 million position updates per
second requires a spatial index. Scanning all drivers per
query is O(N) and breaks at city scale."
Minute 2: Describe your chosen approach
"I would use Redis with GEOADD and GEOSEARCH. Geohashing
encodes lat/lng into string-based cells. Nearby queries check
the rider's cell plus 8 adjacent cells, reducing candidates
from 50,000 to roughly 100."
Minute 3: Address the moving objects problem
"Drivers send GPS every 4 seconds. Redis GEOADD handles this
as an upsert. I set a 15-second TTL so offline drivers expire
automatically. The boundary problem is solved by always
querying adjacent cells."
Minutes 4-5 (if interviewer asks to go deeper):
Compare geohash vs quadtree vs H3. Discuss write path vs read
path separation. Walk through the city-scale worked example.
Transition to Matching
“Now that we have a list of nearby drivers from the spatial index, the next step is scoring and ranking these candidates. That is the Matching Service, which I will cover next.”
This connects directly to Section 7 (Matching and Dispatch), which consumes the candidate list produced by the geospatial system.
SLIDE 79: Section Cheat Sheet
Key Numbers
GPS update frequency: every 3-4 seconds per driver
GPS updates globally: 1.25M/sec
Geohash precision 6: ~1.2 km x 0.6 km per cell
Geohash precision 7: ~150 m x 150 m per cell
Nearby query cells: 9 (target + 8 neighbors) for geohash
7 (target + 6 neighbors) for H3
Redis GEOADD throughput: ~500K ops/sec per instance
Redis GEOSEARCH latency: sub-millisecond for 50K entries
Position staleness tolerance: 3-5 seconds for matching
TTL on position records: 15-20 seconds
Naive scan (50K drivers): 50,000 distance calcs per query
Spatial index (50K drivers): 50-200 distance calcs per query
Reduction factor: 250-1,000x
Approach Comparison Summary
Common Interview Mistakes
How This Connects to Other Sections
Section 3 (Capacity Estimation) provided the 1.25M GPS/sec number that motivates everything in this section. Section 5 (Data Flow) defined the write path (GPS ingestion) and read path (nearby query) that the Location Service implements. Section 7 (Matching) consumes the candidate driver list produced by the spatial index. Section 8 (Database Design) covers Redis configuration and time-series database selection for location history. Section 12 (Caching) discusses TTL strategies for position data. Every section that touches driver positions depends on the geospatial architecture designed here.