Uber

AP(Avilable, Partition Tolerant). eventual consistent is fine.read heavy system
There are 2 entities in system:
- Driver(who updates his location(lat,long) in system).
- User(Customer) who gets nearby(within 10 lm radius) drivers based on his location(lat,lon)

Requirements

Functional:
  User(Customer)/Driver should be able to create profile
  Driver should be able to add/update their location
  User should be able to check rides, make booking, cancel booking
  User should be able to pay
Non-Functional: Available, Fault tolerant, Scalable

All requirements are around CRUD(create, read, update, delete)

BOE

Assumed. Users(300 Million) Drivers(1M). DAU(1M), DA Drivers(500k). Daily rides(1M) Drivers update their location every 5 seconds.
QPS (Queries Per Second)
  User Queries: 1M / 86400 = 12 queries per second
  Driver does not do queries, but updates are pushed to driver when driver is not on trip.
Bandwidth Estimates
1 User Requests for cab location size = 90 bytes. 12 x 90 = 1080 bytes/sec TCP, IP, DL Header sizes. 


|App Hdr + (userlong, lat, userId, preference)|Transport TCP(src,dst port)|NW(src, dst IP)| DL Hdr(src, dst MAC) |
  20bytes         17bytes                       20 bytes                    20 bytes         14 bytes             => 90bytes

HLD

QuadTree

QuadTree to store driver location(lat, long) and to effectively user App query nearby 10km radius drivers.
We will extend quadtree design of yelp here
Frequent Updates on quadtree:
Difference b/w Uber & yelp is there would be more frequent updates on quadtree wrt yelp. Since Drivers update their location(driver_id, lat, long) every 5 seconds, Will we update quadtree on every update?
No. We will create a local datastructure(Hash Table), which will store info of drivers and will send the information after 10-15 seconds. This will reduce frequent updates on system. 


      Hash Table:
      key=driver_id(3 bytes), value={lat(8bytes), long(8bytes)} //19 bytes
    
      500k driver. 10Mbytes of storage

System Blocks

%%{init: {'themeVariables': {'fontSize': '13px'}, 'sequence': {'actorMargin': 45, 'messageMargin': 30, 'boxMargin': 8, 'useMaxWidth': true}}}%%
flowchart LR

%% Clients
Customer["Customer App"]
Driver["Driver App"]

GLB["Global Load Balancer"]
RLB["Regional Load Balancer"]
AZLB["AZ Load Balancer"]

APIGW["API Gateway"]
UserService["User Service"]
RideService["Ride Service"]
LocationService["Location Service"]
PaymentService["Payment Service"]
UserDB[(User DB)]
RideDB[(Ride DB)]
PaymentDB[(Payment DB)]
LocationCache["Redis Cache"]
QuadTree["QuadTree / Geospatial Index"]
Kafka["Kafka"]
MatchingService["Ride Matching Service"]
NotificationService["Notification Service"]
AnalyticsService["Analytics Service"]
SurgePricing["Surge Pricing Service"]


%% Entry
Customer --> GLB
Driver --> GLB

GLB --> RLB
RLB --> AZLB
AZLB --> APIGW

%% Core Services
APIGW --> UserService
APIGW --> RideService
APIGW --> LocationService
APIGW --> PaymentService

%% Databases
UserService --> UserDB
RideService --> RideDB
PaymentService --> PaymentDB

%% Location
LocationService --> LocationCache
LocationService --> QuadTree

%% Async
LocationService --> Kafka
RideService --> Kafka

Kafka --> MatchingService
Kafka --> NotificationService
Kafka --> AnalyticsService
Kafka --> SurgePricing

%% Notifications
NotificationService --> Customer
NotificationService --> Driver

Driver Location update

%%{init: {'themeVariables': {'fontSize': '13px'}, 'sequence': {'actorMargin': 45, 'messageMargin': 30, 'boxMargin': 8, 'useMaxWidth': true}}}%%
sequenceDiagram
autonumber

participant Driver
participant API
participant LocationService
participant RedisCache
participant QuadTree
participant Kafka
participant NotificationService

Driver->>API: POST /location(lat,lng)
Note over API: REST endpoint aware
/location -> locationSvc 
/neearbydrivers -> RideSvc

API->>LocationService: Update Driver Location(lat,lng)
Note over LocationService: Cache Check
if prev location same as present

LocationService->>RedisCache: Check Previous Driver Location

alt Cache Miss or Location Changed
    RedisCache-->>LocationService: Update Required
    LocationService->>QuadTree: Update Driver Position
    LocationService->>RedisCache: Update Latest Location
    LocationService->>Kafka: Publish driver-location-updated
else Same Location
    RedisCache-->>LocationService: Ignore Update
end

Kafka-->>NotificationService: driver-location-updated

NotificationService-->>Driver: Optional Push/WebSocket

LocationService-->>API: Success
API-->>Driver: 200 OK
1. Driver sends its location(latitude,longitude) to an API gateway every 5 minutes. The API gateway is aware about the REST Endpoint and it sends the location to the location service.
3. The location service checks the cache that if this driver's location is same as previous. If not, it will not update.
5. Updated driver location in Quadtree. if quadtree node becomes heavy in Quadtree that is broken into sub quadtrees

User/Customer/Rider searches Nearby Drivers

%%{init: {'themeVariables': {'fontSize': '13px'}, 'sequence': {'actorMargin': 45, 'messageMargin': 30, 'boxMargin': 8, 'useMaxWidth': true}}}%%
sequenceDiagram
autonumber

participant Rider as Rider/User/Customer
participant API
participant RideService
participant LocationService
participant Redis
participant QuadTree
participant UserDB

Rider->>API: GET /nearbyDrivers
My location(lat,lng)
Note over API: REST endpoint aware
/location -> locationSvc 
/neearbydrivers -> RideSvc

API->>RideService: 10km Nearby Drivers
 to location(lat,lng)

RideService->>UserDB: Validate Customer
UserDB-->>RideService: OK
RideService->>LocationService: Find Nearby Drivers

LocationService->>Redis: Radius Lookup
alt Cache Hit
    Redis-->>LocationService: Driver List
else Cache Miss
    Redis-->>LocationService: Miss
    LocationService->>QuadTree: Radius Search(10 km)
    QuadTree-->>LocationService: Driver List
    LocationService->>Redis: Cache Result
end
LocationService->>QuadTree: Radius Search(10 km)

QuadTree-->>LocationService: Driver List

LocationService-->>RideService: Nearby Drivers
Note over RideService: No Kafka message is needed because
 Rider is waiting for an immediate response

RideService-->>API: Driver List

API-->>Rider: Driver Locations
The Notification Service does not participate in the synchronous "find nearby drivers" API because its a Kafka client and rider is waiting for an immediate response, we will not bank on kafka for sending notifications

kafka Messages

topic= driver-location-updated
 Message:
{
  "eventId": "uuid",
  "driverId": "D123",
  "latitude": 37.7749,
  "longitude": -122.4194,
  "heading": 90,
  "speed": 42,
  "status": "AVAILABLE",
  "timestamp": 1753185000
}
Consumers: Notification Service, Analytics Service, Surge Pricing Service, Ride Matching Service (optional, depending on architecture)

APIs (CRUD)

User APIs

REST API?
REST API Versioning(v1,v2)

1. User Creates a booking

2. User gets all nearby cabs

4. User can cancel the ride

 

curl -X POST -H "Content-Type: application/json" 
-d '{"user_id": "", "driver_id": "", "to": "", 
"from": "", "initial_price": "", "duration": "", }' 
http://127.0.0.1:8080/v1/booking/create -vvv
          

curl -X GET -H "Content-Type: application/json" 
-d '{"user_id": "", "long": "", "lat": ""}' 
http://127.0.0.1:8080/v1/booking/read -vvv
        

curl -X DELETE -H "Content-Type: application/json" 
-d '{"user_id": "", "booking_id": ""}' 
http://127.0.0.1:8080/v1/booking/cancel -vvv
          

POST https://url/v1/booking/create   //url=uber.com
header {
  Authorization: {Bearer "API_KEY_TOKEN"},

  /*Mandatory added by HTTP Start*/
  Content-len: 0                        
  Host:        //Calculated when req is sent
  UserAgent: Postman
  Accept: */*       
  Accept-Encoding: gzip, deflate, br
  Connection: Keepalive
  /*Mandatory added by HTTP End*/
}
body {  //JSON
"user_id": "", "driver_id": "", "to": "", 
"from": "", "initial_price": "", "duration": "", 
}
        

// All free cabs near user
GET https://url/v1/get_cabs
header {
  Authorization: {Bearer "API_KEY_TOKEN"},
  ..other fields..
}
body {  //JSON
  "long": ""
  "lat": ""
}
        

// User cancels the ride
GET https://url/v1/cancel_cab
header {
  Authorization: {Bearer "API_KEY_TOKEN"},
  ..other fields..
}
body {  //JSON
  "user_id": ""
  "booking_id": ""
}