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.

What Tombstone Staleness Actually Means in Cassandra

Tombstone staleness is the accumulation of deletion markers (tombstones) that outlive their usefulness, degrading read performance and causing latency spikes. In Cassandra, a delete doesn't remove data immediately — it writes a tombstone with a timestamp. During compaction, tombstones older than gc_grace_seconds (default 10 days) are purged. Until then, every read must scan past these tombstones, increasing I/O and CPU. The core mechanic: tombstones are not garbage collected until compaction, and if compaction falls behind, stale tombstones accumulate linearly with write volume.

In practice, tombstone staleness manifests as steadily rising read latencies and timeouts, especially on range queries. Cassandra's read path must merge all SSTables for a partition — tombstones add overhead proportional to their count. A single partition with 100,000 tombstones can cause multi-second reads. The key property: tombstones are not free; they consume disk space and memory in the memtable and row cache. The compaction strategy (SizeTiered, Leveled, or TimeWindow) determines how aggressively tombstones are reclaimed — Leveled Compaction is most efficient for tombstone cleanup.

Use tombstone staleness awareness when designing systems with high delete rates — time-series data with TTLs, session stores, or queue-like patterns. It matters because ignoring tombstone accumulation leads to cascading failures: slow reads cause client retries, which increase load, which further delays compaction. The rule of thumb: keep tombstones per partition under 1,000 for predictable latency. Monitor 'org.apache.cassandra.metrics.Table.TombstoneScannedHistogram' in production.

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();
    }
}

The 100-Millisecond Rule: Why WebSockets Beat Polling for Driver Location

Every Uber backend engineer knows that latency kills the rider experience. When you open the app and watch your driver approach, that blue car icon updates because of WebSocket push, not HTTP polling. Polling adds 300ms-1s of overhead per request. At Uber’s scale, that’s millions of wasted requests per minute. Instead, the driver’s mobile app sends GPS coordinates every 3-5 seconds via a persistent WebSocket connection. The server validates, updates Redis (for fast reads), and pushes to subscribed riders. That means 100ms end-to-end. If you use polling, your system collapses under load. WebSockets also reduce bandwidth by 80% compared to REST polling. The trade-off: connection management. You need a load balancer that supports sticky sessions or a distributed pub/sub like Kafka to fan out updates. Uber uses WebSockets with long-lived connections and fallback to Server-Sent Events for firewall-busted clients. Never poll when you can push. Your users’ thumbs will thank you.

import asyncio
import websockets
import json

DRIVER_LOCATIONS = {}
RIDER_SUBSCRIPTIONS = {}

async def handle_driver(websocket, driver_id):
    async for message in websocket:
        data = json.loads(message)
        DRIVER_LOCATIONS[driver_id] = data['lat'], data['lng']
        # Fan out to subscribed riders
        for rider_ws in RIDER_SUBSCRIPTIONS.get(driver_id, []):
            await rider_ws.send(json.dumps({
                'driver_id': driver_id,
                'lat': data['lat'],
                'lng': data['lng']
            }))

async def main():
    async with websockets.serve(handle_driver, "0.0.0.0", 8765):
        await asyncio.Future()

asyncio.run(main())

H3 Hexagons: How Uber Discretizes the Earth for Geofencing and Dispatch

Uber doesn’t use lat/lng pairs for geofencing. That’s amateur hour. They use Uber H3, a hexagon-based spatial index. Why hexagons? They tessellate better than squares (no jagged corners) and have uniform distance properties—each edge of a hexagon is roughly the same length. That’s critical for surge pricing zones and driver dispatch. The H3 grid resolves queries like “find all drivers within 500 meters” in O(log n) by indexing hexagon IDs. Resolution 10 means each hexagon is about 0.2 square kilometers—perfect for city-level matching. Uber pre-computes hexagon neighbors, so dispatch only checks 7 hexes (center + 6 neighbors) rather than scanning all drivers. That’s a 100x speedup. They also use H3 for pricing: surge zones snap to hexagon clusters, not arbitrary lat/lng polygons. If you’re building geospatial systems, stop reinventing the wheel. Use H3. It’s open-source. It’s battle-tested. It’s the reason your Uber knows exactly how many drivers are on the next block.

import h3

# Riders location to hexagon
rider_lat, rider_lng = 40.7580, -73.9855  # Times Square
hex_id = h3.latlng_to_cell(rider_lat, rider_lng, resolution=10)

# Get neighboring hexagons (for dispatch radius)
neighbors = h3.grid_disk(hex_id, k=1)

print(f"Rider Hex: {hex_id}")
print(f"Dispatch Area (7 hexes): {neighbors}")

# Simulate query: drivers indexed by hex
drivers_by_hex = {
    '8c089ec8b4dffff': ["driver_1", "driver_2"],
    '8c089ec8b4f9999': ["driver_3"],
}

nearby_drivers = []
for hex in neighbors:
    nearby_drivers.extend(drivers_by_hex.get(hex, []))

print(f"Available drivers in zone: {nearby_drivers}")

The Two-Phase Commit Trap: Why Uber Uses Saga Pattern for Payments

Do not use distributed transactions for ride payments. That’s a recipe for deadlocks and downtime. Uber processes millions of payments per hour across drivers, riders, promotions, and surge adjustments. A two-phase commit across database shards would block for seconds, and any coordinator failure leaves locks forever. Instead, Uber uses the Saga pattern: a sequence of local transactions with compensating actions on failure. When a ride ends, the saga orchestrates: (1) charge rider card, (2) credit driver wallet, (3) apply promo discount. Each step writes to its own shard. If step 2 fails, step 1 is reversed via a refund transaction. No global locks. No two-phase commit. Uber’s payment saga runs on Apache Kafka for durability and ordering. Each event is idempotent—if a message is retried, the system ignores duplicates via a unique ride_id. This is how Uber processes $14 billion in payments annually without locking a single database row. Sagas are hard to debug, but they are the only way to scale payments. If you try two-phase commit at Uber’s volume, you will learn what production paging looks like at 3 AM.

import json

class PaymentSaga:
    def __init__(self):
        self.steps = []
        self.compensations = []

    def add_step(self, step_func, compensate_func):
        self.steps.append(step_func)
        self.compensations.append(compensate_func)

    def execute(self, ride_id, amount):
        executed = []
        for i, step in enumerate(self.steps):
            try:
                step(ride_id, amount)
                executed.append(i)
            except Exception as e:
                print(f"Step {i} failed: {e}")
                for j in reversed(executed):
                    self.compensations[j](ride_id, amount)
                raise

# Example: charge rider, credit driver
def charge_rider(ride_id, amount):
    print(f"Charged rider ${amount} for ride {ride_id}")

def refund_rider(ride_id, amount):
    print(f"Refunded rider ${amount} for ride {ride_id}")

def credit_driver(ride_id, amount):
    print(f"Credited driver ${amount} (after Uber cut)")
    # Simulate failure
    raise Exception("Driver wallet service down")

def clawback_driver(ride_id, amount):
    print(f"Clawed back driver credit for ride {ride_id}")

# Build saga
saga = PaymentSaga()
saga.add_step(charge_rider, refund_rider)
saga.add_step(credit_driver, clawback_driver)

try:
    saga.execute("ride_12345", 25.00)
except:
    print("Saga completed with compensation: rider refunded, driver not credited")