Uber System Design — Cassandra Tombstone Staleness

Uber processes roughly 20 million trips per day across 70+ countries. At peak hours in a city like New York, the system is simultaneously tracking hundreds of thousands of driver GPS pings per second, matching riders to drivers in under 2 seconds, calculating surge multipliers in real-time, and processing payments across dozens of currencies. Getting any one of those wrong at scale doesn't just cause a bug — it causes someone standing in the rain at 2am. That's the real pressure behind this design.

The core problem Uber solves isn't 'connecting riders to drivers' — that's too simple. The real problem is: how do you maintain a globally consistent, real-time view of moving objects (drivers), efficiently query that view by proximity, run a two-sided marketplace matching algorithm under millisecond constraints, handle partial failures gracefully, and do all of this across data centers on multiple continents while remaining cheap enough to be profitable? Each of those sub-problems alone is a PhD thesis. Together, they're one of the most instructive system design challenges you'll encounter.

By the end of this article you'll be able to walk into any senior engineering interview and articulate the full Uber architecture — from the geospatial indexing strategy that makes proximity search fast, to the matching algorithm trade-offs, to why Uber moved away from a monolith to a domain-oriented microservices architecture, and the exact database and messaging choices that make all of it work in production. More importantly, you'll understand why each decision was made, not just what it was.

High-Level Architecture Overview

Uber operates a domain-oriented microservices architecture. Each domain — location, matching, payment, pricing, trip management — owns its data and exposes APIs via an API gateway (Envoy). Services communicate asynchronously through Kafka topics for event-driven flows, and synchronously through gRPC for low-latency queries.

The architecture is regionally isolated: each city or metro area runs its own stack. Data centers are replicated across multiple regions, with Cassandra providing multi-master replication for location data and PostgreSQL shards for transactional trip/ payment data.

package io.thecodeforge.geo;

import java.time.Instant;
import java.util.UUID;

public class LocationUpdater {
    private final CassandraSession session;
    private final H3Index h3;

    public LocationUpdater(CassandraSession session) {
        this.session = session;
        this.h3 = new H3Index();
    }

    public void updateDriverLocation(DriverPing ping) {
        long h3Index = h3.latLngToCell(ping.lat(), ping.lng(), 9);
        PreparedStatement stmt = session.prepare(
            "INSERT INTO driver_location (driver_id, epoch_min, h3_cell, lat, lng, ts) " +
            "VALUES (?, ?, ?, ?, ?, ?) USING TTL 600");
        session.execute(stmt.bind(
            ping.driverId(),
            ping.epochMinute(),
            h3Index,
            ping.lat(),
            ping.lng(),
            Instant.now().getEpochSecond()));
    }
}

Geospatial Indexing & Location Tracking

Every driver sends a GPS ping every 4 seconds. At 20 million trips per day, that's roughly 2.5 million pings per second at peak. Storing and querying these points in real time requires a geospatial indexing system that can answer "Who is within 500 meters of (lat, lng)?" in under 10 milliseconds.

Uber originally used Google S2 but later developed H3, a hexagonal hierarchical grid. Each driver's location is assigned an H3 cell at resolution 9 (hexagons ~0.1 km²). The matching service then queries all drivers in the same cell and adjacent cells (hex ring), then calculates ETA via OSRM (Open Source Routing Machine).

Storage: The location table in Cassandra uses driver_id as partition key and epoch_minute as clustering key, with a TTL of 10 minutes. A secondary table by h3_cell allows fast proximity searches: SELECT driver_id, lat, lng, ts FROM driver_location WHERE h3_cell = ? AND epoch_min = ?.

package io.thecodeforge.geo;

import com.uber.h3core.H3Core;
import java.util.List;

public class DriverNearbyQuery {
    private final CassandraSession session;
    private final H3Core h3;

    public List<DriverPing> findNearbyDrivers(double riderLat, double riderLng, int radiusMeters) {
        // Convert rider location to H3 cell at resolution 9
        long originCell = h3.latLngToCell(riderLat, riderLng, 9);
        // Get hexagonal ring around origin (k=1 includes origin + 6 neighbors)
        List<Long> ringCells = h3.gridRingUnsafe(originCell, 1);
        // Query Cassandra for each cell
        List<DriverPing> result = new ArrayList<>();
        for (long cell : ringCells) {
            PreparedStatement stmt = session.prepare(
                "SELECT driver_id, lat, lng, ts FROM driver_location WHERE h3_cell = ? AND epoch_min = ?");
            ResultSet rs = session.execute(stmt.bind(cell, currentEpochMinute()));
            for (Row row : rs) {
                result.add(new DriverPing(row.getUUID(0), row.getDouble(1), row.getDouble(2), row.getLong(3)));
            }
        }
        return result;
    }
}

Matching Algorithm (Ride Dispatch)

When a rider requests a ride, the matching service must find the best driver within 2 seconds. The process is:

1. Filter eligible drivers — those whose acceptance rate > 80%, not on a trip, within surge zone.
2. Proximity query — find drivers in the same H3 hex ring (radius ~1 km). If too few, expand to ring 2.
3. Cost computation — for each candidate, compute ETA (via OSRM routing service) and surge multiplier.
4. Auction — Uber uses a second-price auction (Vickrey): the rider pays the lowest winning bid, the driver gets their bid price. This incentivizes truthful bidding.
5. Dispatch — send the rider's request to the top 3 drivers simultaneously (but avoid over-dispatching by reserving the driver for 15 seconds).

The algorithm is optimized for throughput: most cities can dispatch in under 1 second at p99.

package io.thecodeforge.matching;

import io.thecodeforge.geo.DriverNearbyQuery;
import io.thecodeforge.pricing.SurgeCalculator;

public class DispatchEngine {
    private final DriverNearbyQuery nearby;
    private final SurgeCalculator surge;
    private final OSRMClient routing;

    public DispatchResult dispatch(RideRequest request) {
        // 1. Find nearby drivers
        List<DriverPing> candidates = nearby.findNearbyDrivers(
            request.riderLat(), request.riderLng(), 1000);
        if (candidates.isEmpty()) {
            candidates = nearby.findNearbyDrivers(
                request.riderLat(), request.riderLng(), 2000);
        }
        // 2. Compute ETA and filter accepted
        List<DriverBid> bids = candidates.stream()
            .map(d -> new DriverBid(d.driverId(),
                routing.estimatePickupTime(request.riderLat(), request.riderLng(), d.lat(), d.lng(),
                surge.getMultiplier(d.driverId(), request.zoneId()))))
            .filter(b -> b.eta() < 300) // only drivers within 5 minutes
            .collect(Collectors.toList());
        // 3. Second-price auction: pick the highest bidding driver, rider pays second-highest bid
        bids.sort(Comparator.comparingInt(DriverBid::bidAmount).reversed());
        return new DispatchResult(bids.get(0).driverId(), bids.get(1).bidAmount());
    }
}

Surge Pricing Engine

Surge pricing adjusts fares based on real-time supply (available drivers) and demand (ride requests). The calculation runs every 5 minutes per geographic zone (a set of H3 cells).

Algorithm: - Compute surge_multiplier = max(1.0, demand / (supply * target_coverage)) - Where target_coverage is the desired driver-to-rider ratio (e.g., 0.5 for 1 driver per 2 riders). - The multiplier is smoothed using an exponential moving average to avoid sudden spikes. - If supply drops below a threshold, the zone is marked "surge".

Implementation: A separate Kafka stream processor consumes ride_request and driver_online events per zone, aggregates, then broadcasts the multiplier to a Redis cache. The matching service reads the multiplier from Redis, and the rider app displays the surge notification before confirming.

Uber also uses heatmaps to proactively send drivers notifications about potential surge areas.

package io.thecodeforge.pricing;

import org.apache.kafka.streams.KStream;

public class SurgeCalculator {
    private final double TARGET_COVERAGE = 0.5;

    public void process(SupplyDemandEvent event) {
        double ratio = (double) event.demand() / (event.supply() * TARGET_COVERAGE);
        double rawSurge = Math.max(1.0, ratio);
        // Exponential moving average
        double previousSurge = redis.get("surge:" + event.zoneId());
        double newSurge = 0.3 * rawSurge + 0.7 * previousSurge;
        redis.set("surge:" + event.zoneId(), newSurge);
        // Broadcast to riders via push notification
        notificationService.broadcastSurge(event.zoneId(), newSurge);
    }
}

Payment & Trip Execution

Uber's payment system processes tens of millions of transactions daily across 50+ currencies. The core challenge is exactly-once payment capture — you never want to charge a rider twice or miss a driver payout.

The solution: idempotency keys. Before initiating any payment, the client generates a UUID (the idempotency key) and sends it along with the request. The payment service stores this key in a Redis set with a short TTL. If the same key appears again, the service returns the previous response without re-executing.

For cross-region payments (e.g., rider in New York pays for a trip in Paris), the system uses a saga pattern with compensating actions. The steps: 1. Capture rider payment (source account) 2. Payout to driver (destination account) 3. Apply Uber commission 4. If any step fails, compensate: reverse capture, refund driver percentage.

The trip execution state machine runs on a Kafka-backed stream: states go from REQUESTED → MATCHED → EN_ROUTE → ON_TRIP → COMPLETED → SETTLED.

package io.thecodeforge.payment;

import java.util.UUID;

public class PaymentCapture {
    private final RedisClient idempotencyStore;
    private final PaymentGateway gateway;

    public CaptureResult capture(UUID idempotencyKey, double amount, String currency) {
        // Check if already processed
        if (idempotencyStore.exists("capture:" + idempotencyKey)) {
            return CacheResult.ALREADY_PROCESSED;
        }
        // Execute payment
        try {
            CaptureResult result = gateway.capture(amount, currency);
            idempotencyStore.setex("capture:" + idempotencyKey, 86400, result.id());
            return result;
        } catch (NetworkException e) {
            // Retry logic: the caller will retry with same key
            throw new RetryableException(e);
        }
    }
}

Scaling, Fault Tolerance & Real-World Incidents

Uber's system must survive: single data center failure, sudden demand spikes (New Year's Eve), driver app disconnections, network partitions, and rogue deployments. Key strategies:

1. Regional isolation: each city runs independent stacks. If one region fails, others are unaffected.
2. Graceful degradation: if the matching service cannot compute ETAs, it falls back to linear distance matching. If payment fails, riders can still complete the trip and pay later.
3. Auto-scaling: all stateless services (matching, pricing, ETA) scale based on CPU and request queue depth. Cassandra and Redis clusters are sharded and replicated.
4. Chaos engineering: Uber runs regular failure drills: kill random pods, inject latency into Kafka, throttle Cassandra nodes.
5. Circuit breakers: every synchronous call (gRPC) has a circuit breaker. When error rate exceeds 50%, the circuit opens and the caller uses a fallback (e.g., cached data).

A real incident from 2020: A bug in the H3 library caused all new driver pings to be placed in the same hex cell. Suddenly, all riders in a city saw drivers at a single point. The fix required a hotpatch rolled out via the driver app's feature switch system.

package io.thecodeforge.infra;

import com.netflix.hystrix.HystrixCommand;

public class MatchingServiceClient {
    private final HystrixCommand.Setter config;

    public MatchingServiceClient() {
        this.config = HystrixCommand.Setter
            .withGroupKey(HystrixCommandGroupKey.Factory.asKey("MatchingService"))
            .andCommandPropertiesDefaults(
                HystrixCommandProperties.Setter()
                    .withCircuitBreakerErrorThresholdPercentage(50)
                    .withCircuitBreakerSleepWindowInMilliseconds(10_000)
                    .withExecutionTimeoutInMilliseconds(500)
            );
    }

    public List<Driver> getNearbyDrivers(double lat, double lng) {
        return new HystrixCommand<List<Driver>>(config) {
            @Override
            protected List<Driver> run() throws Exception {
                return grpcClient.findNearby(lat, lng);
            }
            @Override
            protected List<Driver> getFallback() {
                // Fallback to cached driver list for this area
                return cache.getDrivers(lat, lng);
            }
        }.execute();
    }
}