Skip to content

S11.md

Latest commit

 

History

History
103 lines (65 loc) · 7.14 KB

S11.md

File metadata and controls

103 lines (65 loc) · 7.14 KB
Raw

Now, we are Deconstructing Uber.

For a Engineer, Uber is the ultimate boss fight. It requires massive data ingestion, real-time spatial indexing, complex state management, and algorithmic matching—all happening in under 100 milliseconds.

1. EASY: The "Firehose" (High-Throughput Location Ingestion)

Scenario: You have 5 million active drivers globally. The Uber driver app sends a GPS ping (Latitude, Longitude, Driver ID, Status) every 4 seconds. Volume: ~1.25 million writes per second. Task: Ingest this firehose of data reliably without crashing your backend servers. You don't need to process it yet; just get it into the system.

Solution: MQTT / WebSockets into Apache Kafka

We do not use standard HTTP (REST) for this. The overhead of establishing a new TCP connection and SSL handshake every 4 seconds for 5 million drivers would melt our edge load balancers.

The Workflow:

  1. Persistent Connection: The driver app establishes a persistent WebSocket or MQTT (Message Queuing Telemetry Transport) connection to our Edge Gateway.
  2. The Ping: The app sends a tiny binary payload containing the GPS data.
  3. The Buffer: The Edge Gateway instantly drops this payload into an Apache Kafka topic called driver_locations.
  4. Partitioning: The data is partitioned by driver_id. This guarantees that all GPS updates for Driver Mike are processed in the exact chronological order they were sent.

Production Grade Architecture

Handling Network Drops (The "Tunnel" Problem): What happens when a driver goes through a tunnel? They lose connection for 2 minutes. When they exit, the app suddenly sends 30 buffered GPS pings at once.

The Fix: * Client-Side Timestamps: We never rely on the server's timestamp (when the message was received). We always use the timestamp generated by the driver's phone.

  • Idempotent Ingestion: If the phone retries sending a batch of pings because of a flaky 4G connection, Kafka must be configured with enable.idempotence=true so it drops exact duplicate packets.
  • Loss Tolerance: If a single ping is permanently lost, we don't care. We don't use heavy database transactions here. Another ping is coming in 4 seconds anyway. We optimize for throughput, not 100% durability of every single coordinate.

2. MEDIUM: The "Radar" (Hexagonal Spatial Indexing)

Scenario: A rider in downtown Manhattan opens the app. Task: You must show the 5 nearest available cars on their screen instantly. The Problem: You cannot run a SQL query scanning 5 million drivers calculating the Haversine distance formula for each one. We touched on Redis GEO on Day 3, but Uber outgrew that. They invented something better.

Solution: Uber's H3 (Hexagonal Hierarchical Spatial Index)

Uber divides the entire surface of the Earth into a grid of hexagons.

Why Hexagons? If you use squares (like a checkerboard), the distance from the center of a square to its top neighbor is shorter than the distance to its diagonal neighbor. With hexagons, the distance from the center to all neighboring centers is exactly the same. This makes radius math incredibly fast and accurate.

The Workflow:

  1. Resolution: H3 has 15 levels of resolution. Level 1 is the size of a country. Level 15 is the size of a coffee table. Uber typically uses Level 9 (hexagons about the size of a city block).
  2. Ingestion Update: When Driver Mike sends his GPS ping, a microservice runs the H3 algorithm: lat/long -> Hexagon ID (e.g., 8928308280fffff).
  3. In-Memory Store: The service updates a Redis cluster: "Add Driver Mike to the set of drivers in Hexagon 8928308280fffff."

Production Grade Architecture

The Proximity Query: When the rider opens the app:

  1. The app converts the rider's lat/long into their current Hexagon ID.
  2. The Backend queries Redis for all drivers currently in that specific hexagon.
  3. If it finds 5 drivers, it returns them.
  4. The Ring Expansion: If it finds only 2 drivers, it mathematically calculates the IDs of the 6 neighboring hexagons (the "first ring") and queries them. It expands outward in rings until it finds enough drivers. This is an $O(1)$ lookup rather than an expensive database table scan.

3. HARD: The "Dispatch" (Stateful Event-Driven Matching)

Scenario: The rider clicks "Confirm UberX". You found 5 nearby drivers. The Problem: You send a request to Driver A. Driver A has 10 seconds to accept. During those 10 seconds, Driver A's app crashes, the Rider cancels the trip, and Driver B drives into a different hexagon. Task: Design the Dispatch Engine. It must handle massive concurrency, race conditions, and distributed state transitions (Rider: Looking -> Matched -> In Trip) without double-booking a driver.

Solution: The Dispatch Saga (Kafka + Flink + Redis Locks)

This cannot be done with simple REST APIs calling each other. It requires an Event-Driven Choreography using the Saga Pattern.

The Architecture:

  • State Machine Store: Cassandra (stores the truth of the Trip: Requested, Dispatched, Accepted, Cancelled).
  • Event Bus: Kafka.
  • Matchmaker Service: Node.js or Go (Asynchronous worker).

The Workflow:

  1. Trip Created: Rider clicks "Confirm". A TripRequested event goes to Kafka.
  2. Candidate Selection: Matchmaker reads the event, uses the H3 index (from the Medium question) to find 5 candidates, and ranks them by ETA (using a routing engine).
  3. The Offer: Matchmaker places a Distributed Lock on Driver A in Redis (SET driver_lock:A "trip_123" NX PX 15000). It sends an "Offer" push notification to Driver A.
  4. The Timer: Matchmaker schedules a delayed message in RabbitMQ/SQS for 10 seconds.
  5. The Race Condition Outcomes:
  • Outcome 1 (Happy Path): Driver A clicks "Accept". An OfferAccepted event fires. Matchmaker commits the match to Cassandra and releases the lock.
  • Outcome 2 (Timeout): Driver A ignores it. The 10-second timer pops. Matchmaker checks Cassandra. The trip is still "Requested". It voids the offer to Driver A, locks Driver B, and sends the offer to B.
  • Outcome 3 (Rider Cancels): Rider cancels after 5 seconds. TripCancelled event fires. Matchmaker updates Cassandra. When Driver A clicks "Accept" at second 8, the app checks Cassandra, sees "Cancelled", and returns a "Trip no longer available" UI to the driver.

Production Grade Architecture

Handling "Zombie" State (Data Consistency): In a distributed system, an event will eventually fail to deliver. What if the Matchmaker locks Driver A in Redis, but the push notification fails to reach Driver A's phone? Driver A is now a "zombie"—locked in the system so they get no other rides, but staring at an empty screen.

The Fix:

  • TTL (Time to Live): Every lock in Redis must have an absolute expiration (e.g., 15 seconds).
  • Reconciliation Workers: A background cron job (or Apache Flink stream) constantly joins the Active_Locks stream with the Active_Trips database. If it finds a driver who has been locked for 30 seconds but has no active trip assigned in Cassandra, it forcefully evicts the lock, returning the driver to the available pool.