How I once build a real-time location system

Intro

Why I'm writing this?

Every engineer has a few projects they love to talk about. This is one of my favorites. It’s the story of a real-world performance bottleneck that nearly brought our services to a halt, the couple of attempts we made to fix it, and the simple, elegant workaround we eventually found to keep our servers alive. Over the years, this puzzle has become my go-to systems design question when interviewing other engineers. After sketching it on whiteboards dozens of times and watching people wrestle with the exact same constraints I faced, I realized I’d never actually written the whole thing down.

While partial pieces of this puzzle are well-documented in database theory—such as using multi-dimensional indexes like R-trees or mapping coordinates to one-dimensional keys via space-filling curves—I've never actually seen this exact end-to-end problem statement, and real-world operational trade-offs, outlined in a single place.

A small note before we dive in: the system described here is hypothetical. It's inspired by something I built over six years ago, but the details have been changed enough that it carries very little resemblance to what was actually deployed, and that's intentional. Think of it as a hypothetical reconstruction, not a leak.

Section 1

The Problem

A long time ago in a logistics company far, far away, I had the challenge to build a real-time system to track a large fleet of drivers and orders.

Matching happened in real-time (think of it as Uber Eats), and the drivers could opt-in or out of each request.

Matching per se won't be the main topic of this tutorial, and I hope to discuss it in another one. But it does impose some additional requirements on our system: we need to frequently poll "all drivers that are available near this order" or, alternatively, solve for the best match between all unassigned drivers and orders.

In terms of requirements, you can imagine every driver has a smartphone, and they send their accurate location on average 15 times per minute. We had to design the system for a fleet of 100k drivers, totaling 25k position "writes" per second. During peak hours, we had to solve for 3k orders in parallel.

Section 2

The Naive Approach

When I first joined, the company had a very standard, intuitive solution in place: a relational database (think PostgreSQL with PostGIS extensions) doing all the heavy lifting.

The architecture essentially relied on two main tables:

SQL Schema

          CREATE TABLE driver_position (

            driver_id UUID PRIMARY
            KEY,

            location GEOMETRY(Point, 4326),

            last_updated TIMESTAMP,

            status VARCHAR

          );

          CREATE TABLE new_order (

            order_id UUID PRIMARY
            KEY,

            pickup_location GEOMETRY(Point, 4326),

            status VARCHAR

          );

How it worked (in theory)

Every time a driver's app pinged the server (15 times a minute), the backend would run an UPDATE on the driver_position table. Then, when a new order came in, the matching engine would run a spatial query—something like ST_DWithin()—to find all available drivers within a certain radius of the pickup_location.

SQL Query

          -- Find available drivers within 2km of an order's pickup
            point

          SELECT

            dp.driver_id,

            ST_Distance(dp.location, o.pickup_location) AS distance_m

          FROM driver_position dp

          JOIN new_order o ON o.order_id =
          :order_id

          WHERE

            dp.status = 'AVAILABLE'

            AND ST_DWithin(

              dp.location,

              o.pickup_location,

              2000 -- meters

            )

          ORDER BY distance_m ASC

          LIMIT 1;

Why it didn't work

On paper, GIS extensions are built exactly for this. In reality, it was a disaster waiting to happen at our scale. Here's why:

1

Write Contention: A standard relational database is not designed to handle 25,000 UPDATEs per second on a single table. Because the table had a spatial index (like an R-tree or GiST index) to make queries fast, every location update meant the database had to constantly rebalance and rewrite the index tree. This caused massive locking and I/O bottlenecks.

2

Expensive Reads: During peak hours, we had 3,000 orders in parallel constantly polling the database for nearby drivers. Doing thousands of complex spatial radius queries per second over a table that is simultaneously mutating 25k times per second brings the DB to its knees.

3

The Death Spiral: When the database gets slightly behind on writes, queries get slower. When queries get slower, connections pile up. Eventually, the database locks up entirely, requests timeout, and drivers appear "frozen" on the map.

💡

The Takeaway
Relational databases with GIS extensions are fantastic for spatial data that changes occasionally (like zip codes or restaurant locations). They are the wrong tool for high-frequency telemetry.

Section 3

Alternative 1: Redis Geo Features

With the database crashing, the natural next thought is: let's move it to memory! Redis has built-in geospatial commands like GEOADD and GEORADIUS, making it seem like the perfect candidate.

Why it seemed like a good idea

Redis uses Geohashes stored in Sorted Sets under the hood. It's incredibly fast. Handling 25,000 writes per second is a walk in the park for Redis. We could simply use GEOADD to update driver locations and use GEORADIUS to fetch nearby drivers for new orders.

python

          import redis

          from typing import List

          r = redis.Redis(host='localhost', port=6379, db=0)

          def update_driver_location(driver_id: str,
          lat: float, lng: float) -> None:

              # Add/update driver coordinates in
            the spatial index

              r.geoadd("drivers:locations", (lng, lat,
          driver_id))

          def find_nearby_drivers(order_lat:
          float,
          order_lng: float, radius_km: float =
          2.0) -> List[str]:

              # Query all members within a 2km
            radius

              return r.georadius(

                  "drivers:locations",

                  order_lng,

                  order_lat,

                  radius_km,

                  unit="km"

              )

Why it didn't work

While Redis solved the write contention issue, it introduced a new set of problems entirely related to how it processes commands:

1

The Single-Threaded Bottleneck: Redis executes commands sequentially on a single thread. While simple writes are sub-millisecond, a complex GEORADIUS query over a dense city center might take a few milliseconds. If you multiply those few milliseconds by 3,000 parallel queries, you completely exhaust the single thread, blocking all the incoming 25k writes.

2

O(N) Complexity in Dense Areas: Redis Geo queries search within Geohash boxes and then compute exact distances for all points inside those boxes. If it's raining in a dense metropolitan area and thousands of drivers are clustered together, the CPU overhead spikes massively.

3

Clustering is Hard: To solve the single-thread issue, you'd want to use Redis Cluster to shard the load. But how do you shard geographical data? If you shard by driver ID, a spatial query must be broadcast to every node in the cluster. If you shard by geographic region, what happens when a query radius overlaps two regions?

Section 4

The Solution: Redis + Hierarchical H3

The breakthrough came when we decided to stop treating the database as a spatial engine. Instead, we shifted the spatial math into the application layer using Uber's H3 (a hierarchical hexagonal spatial index) and treated Redis as a dumb, hyper-fast key-value store.

⬡

What is H3?
H3 partitions the world into a grid of hexagons at various resolutions. Given a latitude and longitude, the H3 library can instantly give you the ID string of the hexagon that contains it.

The Write Path: O(k)

When a driver pings their location, the backend computes the H3 index for that coordinate across several different resolutions (for example, resolutions 5 through 14). In practice, this means k ≈ 10.

We then simply add the driver's ID to a Redis Set keyed by the H3 index (e.g., SADD h3:892a1072b5bffff driver_123). It's exactly 10 extremely fast, non-blocking string writes to Redis.

python

          import h3

          import redis

          r = redis.Redis(host='localhost', port=6379, db=0)

          def update_driver_location(driver_id: str,
          lat: float, lng: float) -> None:

              # We update across 10 different
            resolutions (k ≈ 10)

              resolutions = range(5, 15)

              pipeline = r.pipeline()

              for res in
          resolutions:

                  # 1. Get the
            H3 hexagon ID for this lat/lng

                  h3_index = h3.latlng_to_cell(lat, lng, res)

                  # 2. Add
            driver to the Redis Set for this hexagon

                  key = f"h3:{res}:{h3_index}"

                  pipeline.sadd(key, driver_id)

              # Execute all writes in a single
            fast network roundtrip

              pipeline.execute()

The Read Path: O(k' * d)

When an order comes in and we need drivers within a certain radius, we don't ask the database to do a radial search. Instead, we:

1

Calculate the appropriate H3 resolution where a hexagon roughly matches our search radius.

2

Find the target hexagon and a few necessary adjacent neighbors. Let's call the number of hexagons we query k' (in practice, k' ≈ 3).

3

Fetch the drivers from those 3 Redis keys using SMEMBERS. Let's call the number of drivers in a hexagon d. Because we picked the right resolution, d << 100.

4

Return the consolidated list of driver_ids that are roughly within the search radius.

python

          import h3

          from typing import Set

          def find_nearby_drivers(order_lat:
          float, order_lng: float, res: int = 8) -> Set[str]:

              """Return a set of driver IDs roughly within the hexagon
            ring at the given resolution.

              Runs O(k' * d): k' hexagons queried, d drivers per
            hexagon.

              """

              # Find target hexagon and a 1-ring
            of neighbors (k' ≈ 7)

              center_h3 = h3.latlng_to_cell(order_lat, order_lng, res)

              hexagons = h3.grid_disk(center_h3, 1)

              potential_drivers: Set[str] = set()

              for h3_index in hexagons:

                  key = f"h3:{res}:{h3_index}"

                  potential_drivers.update(r.smembers(key))

              return potential_drivers

The Magic of the Hierarchy

There is a hidden superpower in this approach: we don't actually have to guess the perfect search radius or number of queries. Because H3 is hierarchical, larger parent hexagons perfectly contain smaller child hexagons.

If our matching engine wants to evaluate at least 50 nearby drivers to find the perfect match, we can start our search at a very high resolution (a tiny hexagon). If that cell only yields 5 drivers, we simply drop a resolution level (zoom out to the parent hexagon) and query again. We keep moving up the hierarchy until our bucket hits our target driver count. Since these are just blazing-fast string lookups in our key-value store, doing 3 or 4 sequential "zoom-out" queries adds practically zero latency.

Storing Exact Locations and Metadata

Notice that so far, we've only used Redis Sets to store a list of driver_ids mapped to an H3 index. But how do we know their exact location or their timestamp? We need this for the final precise distance calculation.

The solution is simple: during the write path, we make one additional write to a separate Redis key where we serialize the driver's metadata (using a python dataclass for instance) to a JSON value.

During the search, once you've retrieved the set of nearby driver_ids from the H3 index queries, you run one single batch query (like MGET) to fetch all their exact locations. You then calculate the precise point-to-point distances entirely in application memory.

python

          import json

          from dataclasses import dataclass,
          asdict

          from typing import Optional

          from geopy.distance import
          geodesic

          @dataclass

          class DriverMeta:

              """Serialisable snapshot of a driver's state at a point
            in time."""

              lat: float

              lng: float

              timestamp: int    # Unix epoch seconds

              status: str       # e.g. 'AVAILABLE', 'BUSY', 'OFFLINE'

          def write_driver_metadata(driver_id:
          str, lat: float, lng: float, timestamp: int, status: str) -> None:

              """Serialize a driver's full metadata to a single Redis
            string key."""

              meta = DriverMeta(lat=lat, lng=lng, timestamp=timestamp, status=status)

              r.set(f"driver:meta:{driver_id}", json.dumps(asdict(meta)))

          def filter_and_find_best_match(

              order_lat: float,

              order_lng: float,

              potential_driver_ids: Set[str],

              max_radius_km: float = 2.0,

          ) -> Optional[str]:

              """Fetch metadata for candidate drivers in a single MGET
            batch, then

              filter by status and distance entirely in application
            memory.

              Returns the driver_id of the closest available driver,
            or None.

              """

              # Batch-fetch all metadata in one
            round-trip

              keys = [f"driver:meta:{d_id}" for d_id in potential_driver_ids]

              meta_results = r.mget(keys)

              best_driver: Optional[str] = None

              min_distance: float = float('inf')

              # Filter by status and exact
            distance in memory

              for d_id, meta_json in zip(potential_driver_ids,
          meta_results):

                  if not meta_json: continue

                  meta = json.loads(meta_json)

                  if meta['status'] != 'AVAILABLE': continue

                  dist: float =
          geodesic((order_lat, order_lng), (meta['lat'], meta['lng'])).km

                  if dist <=
          max_radius_km and dist < min_distance:

                      min_distance = dist

                      best_driver = d_id

              return best_driver

Pre-filtering for High Performance

Filtering by status in memory is usually perfectly fine since we only ever fetch a few dozen drivers from the database. However, if your business logic requires strict, high-performance filtering (e.g., you only ever want to search for AVAILABLE drivers and ignore the rest), fetching metadata for offline drivers is a waste of network I/O.

In this case, you can push the index directly into the Redis key during the write phase. Instead of writing to h3:{res}:{index}, you write to h3:{res}:{index}:{status}.

This adds a slight write overhead if drivers switch statuses frequently, but it guarantees your read path only ever fetches exactly what it needs. This ensures your read stays a true $O(k' \times d)$ where $d$ is strictly the number of available drivers.

How do we expire stale positions?

If you look closely at the write path above, you might notice a missing piece: how do we prevent the Redis Sets from growing indefinitely as drivers go offline? Redis doesn't allow expiring individual elements inside a Set natively.

The elegant solution is time-dependent rolling keys. Instead of just using the H3 index as the key, we append a time bucket to it (e.g., the current minute). When writing, we write to the current minute's bucket and set an expiry on the entire key. When reading, we simply query a fixed number of recent buckets depending on our freshness requirements.

You can choose the time window size to trade off the cost of reads vs. writes. If you need stricter freshness guarantees, you can simply filter the exact timestamps in-memory since you're already calculating precise distances for a very small number of drivers anyway.

python

          import time

          def get_time_bucket() -> int:

              # Bucket by the current
            minute

              return int(time.time() // 60)

          def update_driver_location_with_expiry(driver_id: str, lat: float, lng: float) -> None:

              bucket = get_time_bucket()

              pipeline = r.pipeline()

              for res in
          range(5, 15):

                  h3_index = h3.latlng_to_cell(lat, lng, res)

                  # Append the
            time bucket to the key

                  key = f"h3:{res}:{h3_index}:{bucket}"

                  pipeline.sadd(key, driver_id)

                  # Expire the
            whole bucket after 3 minutes (e.g. current + 2 previous)

                  pipeline.expire(key, 180)

              pipeline.execute()

          def find_recent_drivers_in_hex(h3_index: str, res: int, num_buckets_to_check:
          int = 2) -> Set[str]:

              current_bucket = get_time_bucket()

              potential_drivers = set()

              # Query current minute and the
            previous minute(s)

              for i in
          range(num_buckets_to_check):

                  bucket_to_check = current_bucket - i

                  key = f"h3:{res}:{h3_index}:{bucket_to_check}"

                  drivers_in_bucket = r.smembers(key)

                  potential_drivers.update(drivers_in_bucket)

              return potential_drivers

Why this scales infinitely

By converting a complex 2D spatial problem into simple 1D string lookups, we removed all CPU bottlenecks from the database. Furthermore, because data is accessed strictly by string keys, sharding becomes trivial. You can distribute the keys across a massive cluster without any "cross-boundary" spatial query nightmares.

💡

Storage Agnostic
It's worth noting that in this architecture, Redis is just an implementation detail. Because we're only doing simple string-based set lookups, the design is completely agnostic to the storage layer. You could swap Redis for Memcached, DynamoDB, Cassandra, or any other fast key-value store, and the core logic would remain exactly the same.