Q: Design Uber or Lyft (a ride sharing service)
While designing a ride-sharing service, discuss things like:
- The most critical use case — when a customer requests a ride and how to efficiently match them with the nearby drivers?
- How to store millions of geographical locations for drivers and riders who are always moving.
- How to handle updates to driver/rider locations (millions of updates every second)? Comparable to market data systems, but less latency sensitive.
- How to scale out (or scale up)?
- What data store? See below
- sharding policy? by location?
- Any MOM?
- Any multicast?
- Any queuing/buffering? I doubt it.
- –secondary features
- payment? I feel is less challenging in terms of performance and data volume. It’s like a post-trade system.
–minimize location update messaging volume
If a rider app is in the background, then the location should not be monitored. Server would ignore any location data on this rider. When a rider app goes foreground, then a rider is possibly looking at the Uber app screen, then the app will send a msg to the server and server will start tracking its location.
Driver would log in to start receiving requests. we can log her out after a timeout like not responding to any requests, or staying background. By default, we could log out a driver after a configured time. Driver app can also have a feature to stay always-on.
Driver location updates should be 10 times more frequent than rider.
–Data store for driver movement (static data will go to a separate, slower data store)
Let’s stick to something we know well — RDBMS. I feel a single big database is enough for any country including U.S. A traditional SQL table can hold 200 million rows (drivers) easily and support concurrent updates like
- location update — most common, perhaps 10 times/minutes for each driver
- driver logout, when she decides not to receive booking requests
- driver login
(It’s possible to upgrade to a in-memory database or a noSQL.)
We need to have at least an index on DriverId and an index on Location i.e. latitude/longitude/zipcode