Skip to content

S50.md

Latest commit

 

History

History
85 lines (49 loc) · 4.74 KB

S50.md

File metadata and controls

85 lines (49 loc) · 4.74 KB
Raw

We are going to stress-test your entire technology stack—Kafka, Flink, Cassandra, Spark, and AWS—in a single, brutal real-world system design interview.

Now, we are architecting Uber's Real-Time Surge Pricing Engine.

We must ingest millions of geospatial coordinates, calculate local supply and demand, and update prices on drivers' phones with sub-second latency. Let’s tear it down.

Step 1: The Scope & The Math (Minutes 0-5)

The Problem: We cannot calculate surge pricing for the entire planet at once. We must calculate it for highly specific neighborhoods, and we must do it fast.

  • Scale: Assume 5 million active drivers and 20 million active riders globally.
  • Velocity: The mobile apps ping our servers with their GPS coordinates every 4 seconds.
  • Ingestion Rate: $\sim 6.25 \text{ million}$ events per second.

The Spatial Resolution (Uber H3): Instead of using messy, overlapping zip codes, we map the world into a grid of perfect hexagons using Uber's open-source H3 Index. Every GPS coordinate is instantly mathematically hashed into a specific Hexagon ID.

Step 2: The Ingestion Firehose (Minutes 5-15)

If 6.25 million pings hit our database every second, the database will instantly melt. We need a massive shock absorber.

The Architecture:

  1. The Edge: The mobile apps hit our AWS API Gateway (via WebSockets or standard HTTPS).
  2. The Hashing: A lightweight microservice takes the raw (latitude, longitude) and converts it to an h3_hexagon_id.
  3. The Buffer: The microservice drops the payload into Apache Kafka.

Kafka Partitioning Strategy (Crucial): If we partition the Kafka topic randomly, our downstream stream processors will have to shuffle data across the network to group the riders and drivers.

  • The Fix: We strictly configure the Kafka producer to partition by city_id (or a coarse regional H3 resolution). This mathematically guarantees that all events for "Downtown Manhattan" land on the exact same Kafka partition, completely eliminating the network Shuffle in the next step.

Step 3: The Real-Time Brain (Minutes 15-30)

This is the core engine. We must calculate the demand (riders opening the app) versus the supply (available drivers) for every single hexagon, every single minute. Spark Micro-batching is too slow here. We need true continuous streaming.

The Architecture: We deploy Apache Flink to consume the Kafka partitions.

The Workflow:

  1. Tumbling Windows: Flink groups the incoming Kafka stream into strict 1-minute time windows (TumblingEventTimeWindows.of(Time.minutes(1))).
  2. Local State (RocksDB): Inside that minute, Flink uses its embedded RocksDB state to keep a running tally.
  • Hexagon A: 500 Rider App Opens, 50 Available Drivers.
  1. The Calculation: At the end of the minute, the window closes. Flink executes the surge pricing algorithm. A highly simplified version looks like this: $$Surge = \max\left(1.0, \alpha \times \frac{Demand}{Supply}\right)$$

(Where $\alpha$ is a machine learning weight for that specific city based on historical traffic). 4. The Output: Flink calculates that Hexagon A needs a 2.5x surge multiplier. It instantly emits this single tiny record downstream. We just reduced 6 million raw GPS pings into a few thousand pricing multipliers.

Step 4: The Serving Layer (Minutes 30-40)

Flink has calculated the surge multipliers, but Flink is not a database. When a rider opens their app to request a ride, the backend needs to know the price instantly.

The Architecture: We route Flink's output to a database optimized for extreme read concurrency and $O(1)$ lookups. A wide-column store like Apache Cassandra or a key-value store like Redis is perfect here.

The Workflow:

  1. Flink runs an UPSERT into Cassandra: UPDATE surge_prices SET multiplier = 2.5 WHERE hexagon_id = 'HexA'.
  2. The Rider opens the app. The backend calculates their route, looks at the starting hexagon_id, queries Cassandra, gets the 2.5x multiplier in 1 millisecond, and displays the final price to the user.

Step 5: The Historical Loop (Minutes 40-45)

How did Flink know what the machine learning $\alpha$ weight should be?

The Lambda/Kappa Hybrid: While Flink is processing the live Kafka stream, we have a secondary consumer dumping the exact same raw Kafka events into an AWS S3 Data Lake (Bronze Layer).

Overnight, your heavy Apache Spark batch jobs sweep through S3. They analyze years of historical data to train the Machine Learning models predicting traffic patterns, weather impacts, and baseline surge caps. These Spark models output the static $\alpha$ weights and load them into a fast cache so Flink can join them with the live stream the next day.