Requirements

Functional Requirements:

• User is able to request ride
• Match user with the nearby avialable driver
• Real-time driver location tracking
• Driver can go online/offline
• Driver can accept/reject ride
• User is charged for the ride after trip completion

Non-Functional Requirements:

• Highly available: 99.9% uptime
• Low latency for matching drivers <1s (does not include the time it takes for dispatching ride to top driver and waiting for acceptance)
• Eventual consistency for location updates
• Highly scalable
• High write throughput for location updates ~200K updates/sec
• Strong consitency for payments and trip updates

Capacity Estimation

• 10M rides/daily -> 100-1000 rides/sec -> peak 5x -> ~5kreq/sec
• 1M drivers active
• Locaiton update every 5 sec -> 1M/5 -> 200K updates/sec

API Design

Driver APIs

Update driver status -> AVAILABLE, RESERVED, ON TRIP

POST /drivers/{id}/status

request: {

status

}

Location Update

POST /drivers/{id}/location

req:{

lat,

long,

timestamp

}

Accept ride

POST /rides/{id}/accept

Rider APIs

Request Ride/trip

POST /rides

req:{

riderId,

pickup: {

lat,

long

}

dest:{

lat,

long

}

}

Get ride status

GET /rides/{id}

Update ride status ->Requested, Matched, In progress, Completed, Cancelled

POST /ride/{id}/status

High-Level Design

API Gateway

Acts as the entry point for all client requests.

Responsibilities:

• Authentication (if required)
• Rate limiting - Applied using token bucket per IP to prevent fraudulent or bot views
• Request routing

Load Balancer

Distributes traffic across multiple instances of all services to improve scalability and availability.

Rider Service

• Rider CRUD service,
• Manages rider profile, including ratings, trip history etc

Driver service

• Driver crud service
• Manages driver profile, including ratings, trip history etc

Location Service

• Handles Driver's spatial geo indexing
• Receives drivers updates every 5 sec
• Validates teh request and emits LocationUpdated event to kafka

Trip Service

• Trip state machine
• Manages full end to end trip states from requested to completed
• Updates state to DB and pushes event to Kafka so downstream services can consume for further procesing

Payment Service

• Consumes TripCompleted event from Kafka
• Calculates the trip fare
• Chareges the user card for the trip
• Also consumes TripCancelled event and compensates user if any payment was chareged like hold charge etc

Matching Service

• Core uber brain
• Consumes TripCreated event from Kafka
• Determines user GeoIndex cell
• Fetches all the drivers at that cell
• Ranks and filters those drivers, resulting in top k drivers

Notification Service

• Notifies drivers of available rides
• Notifies riders of their rides being accepted
• Handles all other notifications

Geo Index Service

• Consumes the location updated event
• determines the geo cell from driver location and stores in redis
  • eg : d3sdsf3 -> driver1, driver2, driver3

Websocket gateway

• Manages all active websocket connections w
• Sends driver's real-time location updates to the trip that driver is on.

Kafka

• Event backbone
• Consumes all trip related event
• Gurantes atleast once delivery
• Uses tripid as the partition key fro trip events
• And for locaiton update events uses driverid as parition key

PostreSQl

• Primary perisnent DB for consitent data -> riders, drivers, payments, trips

Redis

• Primary store for Geo indexing

Database Design

We use hybrid apporach for Database, using SQL -> PostreSQL for stroing strong consisten data where transactrions matter like Users, Drivers, Trips etc and NOSqL -> redis for stroing geo index locations of driver

Riders

id

name

email

rating

Drivers

id

name

status -> AVAILABLE, RESERVED, ON TRIP

vehicle type

rating

Trip

id

riderId

driverId

pickup_lat

pickup_long

dest_lat

dest_long

status -> Requested, Matched, In progress, Completed, Cancelled

UserPaymentMethods

id

userId

method_id -> id from payment provider

providerId

Payments

id

tripid

amount

status -> PENDING, SUCCESS, FAILEd

provider_id

Geo Index -> stored in Redis

structure:

Driver -> cell mapping

eg:

der334s -> driver1, driver2, driver 3

Driver latest location (comes from the api)

driver1 -> lat, long, timestamp

Detailed Component Design

We will now deep dive into these topics

Geo-Spatial Indexing

-> Problem: how do we find nearyby drivers efficiently?

Doing:

Select * from drivers where distance <1km

is impossible at scale

Solution: Use GeoHash

eg: each smaller location is divided into a cell, for eg

Cell A

Cell B

Cell C

• When driver location update comes in, their lat and long is used to determine their geo index cell, so each driver belongs to a cell

Eg

CellA -> driver1, driver2, driver3

in our sytem this is done via:

• Location update is send
• Location service emits the event to kakfa
• Geo index service consumes it
• Uses GeoHash= to determine the geo-index cell of lat, long it recieves
• Updates driver geo index in redis

eg ->

ds3dwad -> driver1, driver2

-> now rider requests ride

• matching service lookup riders lcaotion, detemrine their cell
• Fetches all driver in cell
• If no driver in that cell, expand the search

Driver matching -> Matching service

End to end flow:

• Matching services reqceives trip requested event
• Determines user cell index
• Get candidates -> from redis geo index
• Filter canditaes -> available, vehicel type, rating etc
• Rank candidates
  • Scoring forumla

• Now we get top K drivers
• Notify the top driver and offer the ride
• Wait ~5sec if no response/rejected
• offer ride to next candidate
• If all candiate in the cell are rejected, expand the search and repeat the process

Race Condition

-> Two riderss request same driver at the same time

• Scenario
  • Ride A was requested
  • Rider B was requested
  • Both at teh same time requested Driver C
  • Now driver C ended up with two rides
• Soltuon: Driver state machine & Atomic row locking uppdatges
  • Maintain driver state -> Available, Rerserved, On Trip
  • Do the state updates via row locking.
  • When selecting a driver, use FOR update, eg;
    • Select from driver where id = 123 adn Status = Avialable FOR UPDATE
  • This will lock that driver row for any other rides
  • Then update the driver as Reserved - extra protection

Eg: Ride A and Ride B reqeust comes in

• Ride A requests Driver C
• Now driver C row is locked
• Simaltenouly Ride B also reequests same driver
• But because of row locking ride B request is rejected and ride B tries another driver
• Ride A also updates the Driver C status to reserved so any upcoing ride request cant access driver C

Real time locaiton update

• When trip starts, the rider app requests and opens a websocket connection
• When the driver lcoaiton is send every 5 sec
• The Websocket gateway service also conszuems the locaitonUpdated event
• Checks if for that driver ther any active trips
• For active trips cehcsk if there arny active websocket connection
• To that websocket conneciton, it sends out the locaiton upadte
• Thus, rider sees real time driver locaiton update with no polling

Failure Handling

Driver Disconnects

• Driver online hearbeat missing i.e. 30sec timeout
• Mark offline

Matching/Location service crash

• Once events are in kafka they are retained
• so neww instance continues processing

Websocket gateway crash

• Rdier app reconnects automatically and resubscribes
• Starts receiveng updates again

Redis crash

• Redis is a critical service for all criticial functions
• So to prevent system being down when redis crashes we uses replications
• So primary + replicas
• When primary crashes, the replica becomes primary -> automatic failover