Design Uber

Topic: Design Uber

Interviewer: ken

Level: L4 (Experienced Individual Contributor)

Additional Resources:

• Live Stream

System Design Interview - Design Uber

8/28/2024

YouTube for the event:

Coach Ken LinkedIn:

https://commitway.com/linkedin

WeChat QRCodes

| | | 职场提升俱乐部 |

[45]

Uber: driver location

User: user location

[40]

[38]

Non functional requirements

Latency 1s

[throughput? # of riders/drivers?]

Solutions for nearby

1, la, lo.

2. geohash

3. quadTree

[what do we use geohash for?]

[33]

API:

User:

Send location API

[request ride]

Driver:

Approve request

See information from each other

what do we use geohash for? - search nearby drivers

[31]

Calculate the load

Set:

Car: id, lat,long, TTL, state, information, 20B, 200B

4M driver -> 1M DAU

[peak, full size, user side?]

1M * 20B = 20MB

1M * 200B = 200MB

[27]

Tradeoff: KV or DB

[27]

High level design

Rate limit

Load balance

Authorization

[24]

[22]

Request a car

10M * 2 times / 10^5 = 200 q/s

1 deny 1 approve

Driver:

2 * 200 q/s = 400 q/s

[not database]

[20]

Location update (driver)

[?]

1M * 5 s * 8h / 10 ^ 5 = 400 q/s

Total = 1k requests / sec

Peak = 1.5k req / sec

[17:34]

Location update write:

1M * 8h * 60 * 20 / 10 ^ 5 = 10 * 8 * 60 * 20 = 100k

Traditional machine

1k qps per machine

100 machines

Select KV vs DB:

Key value store. Redis (snapshot + write ahead log)

[12:44]

Geoadd

Geodel

…

Key: geo hash

Value: Set

SMOVE, S

Move car from one set to another

Q: How to update?

A: Driver [long, lat]

La, lo -> geohash

New driver: new_la, new_lo

Existing driver: Old_la, old_lo, new_la, new_lo

[8]

SMOVE old_geohash, new_geohash, id, la, lo, TTL

[6]

Driver: ID, status, lo, lat, ipaddress_of_websocker_server

[3]

How to send the request to the driver to request a ride?

Long pull - pull the search service

Websocket

Short pull

SSE

[2]

[1]

Multiple search service?

Which one?

SSE server send event

[0:35]

Single search service

=====

Functional

High level

Deep dive

Good design

Time allocation

Multiple server 1-1

===

Discussion:

Redis:

Which level

Key uses L6

How to L5

0-9a-z

3A5B77 Set

3A5B7[0-Z]

3A5B7

User = 3A5B76

Driver => 3A5B76 Set

Select cars where id startswith “3A5B7”

Assign driver时的race condition是怎么处理的呢？

Multiple riders may ask for the same driver