Loading...
Consider the below assumptions
With the above assumptions, let's answer the below question
How many requests do we need to handle every day?
Since we have 1 million daily users and each user makes 5 requests.
Total requests = daily active users * number of requests per user
Total requests = 1 million * 5 requests
Total requests = 5 million requests
How many Requests per Second (RPS)?
Total number of requests daily = 5 million requests (assuming each user performs 5 actions daily)
Therefore, requests per second (RPS) can be calculated as follows:
RPS = Total requests per day / Number of seconds in a day
RPS = 5,000,000 / 86,400 seconds (24 hours * 60 minutes * 60 seconds)
RPS ≈ 57.87
So, the system needs to handle approximately 58 requests per second on average.
How much storage do we need per day?
Each message is assumed to be about 500 bytes.
Total storage needed daily can be calculated as:
Daily storage = Total daily messages * Average message size
Daily storage = 5 million messages * 500 bytes per message
Daily storage = 2,500,000,000 bytes
Converting bytes to gigabytes (GB):
1 GB = 1,073,741,824 bytes
Therefore, Daily storage ≈ 2.33 GB
So, the system needs approximately 2.33 gigabytes of storage every day to accommodate the messages generated.
Database choices
Data Partitioning and Sharding
Given the distributed nature and high volume of data in a ride-sharing platform like Uber, a suitable partitioning strategy would be Horizontal Partitioning or "Sharding" based on geographical regions, where data related to users, drivers, rides, and bookings are partitioned across different geographic regions or cities.
This strategy ensures that data is distributed evenly, optimizing query performance and scalability, while also aligning with the natural segmentation of the platform's operations based on geographical locations.
The consistent hashing algorithm can be used for sharding, as it allows for efficient and balanced distribution of data across shards while minimizing data movement when the number of shards changes or nodes are added or removed from the system. This algorithm ensures that data remains evenly distributed even as the system scales, contributing to better load balancing and fault tolerance.
During peak load times or Surge, we will do a horizontal scaling of our system by adding more nodes to our system which allows for distributing the workload and data across multiple servers. This approach is preferable as it provides better scalability, fault tolerance, and flexibility to handle increasing data volume and user demand compared to vertical scaling
Fault tolerance and replication
We will need server replicas in case the Driver Location or Notification servers die. A secondary server can take control when a primary server dies. We can also store data in persistent storage like solid state drives (SSDs) to provide fast input and output. We can quickly use this persistent storage to recover data if both primary and secondary servers die.
Read/Write Separation:
Implementing read/write separation is beneficial for a ride-sharing platform like Uber. By separating read and write operations, it allows the system to optimize for performance and scalability. Read operations, such as retrieving ride details, user profiles, or driver information, are typically more frequent than write operations, such as updating ride statuses or booking new rides. Separating these operations enables the system to distribute the workload more effectively, scale read-heavy components independently, and improve overall system performance by reducing contention on the database resources. Additionally, it helps to ensure better fault tolerance and availability since read operations can still be served even if the write components experience issues or downtime.
The below diagram shows the flow of what happens when the user books a ride.
Efficiently sending and receiving live location data from clients (customers and drivers) to the backend can be achieved using either a pull model or a push model. Let's explore both approaches:
Comparison:
Decision:
Ride Matching
We need a way to efficiently store and query nearby drivers.
GeoHashing
Geohashing is a geocoding method used to encode geographic coordinates such as latitude and longitude into short alphanumeric strings. Geohash is a hierarchical spatial index that uses Base-32 alphabet encoding, the first character in a geohash identifies the initial location as one of the 32 cells. This cell will also contain 32 cells. This means that to represent a point, the world is recursively divided into smaller and smaller cells with each additional bit until the desired precision is attained.
San Francisco with coordinates 37.7564, -122.4016 can be represented in geohash as 9q8yy9mf. Now, using the customer's geohash we can determine the nearest available driver by simply comparing it with the driver's geohash. For better performance, we will index and store the geohash of the driver in memory for faster retrieval.
Quadtrees
A Quadtree is a tree data structure in which each internal node has exactly four children. They are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. Each child or leaf node stores spatial information. We can update the Quadtree every time we receive a new location update from the driver. To reduce the load on the quadtree servers we can use an in-memory datastore such as Redis to cache the latest updates.
How to find the best drivers nearby?
Once we have a list of nearby drivers from the Quadtree servers, we can perform some sort of ranking based on parameters like average ratings, relevance, past customer feedback, etc. This will allow us to broadcast notifications to the best available drivers first.
Dealing with high demand
In cases of high demand, we can use the concept of Surge Pricing. Surge pricing is a dynamic pricing method where prices are temporarily increased as a reaction to increased demand and mostly limited supply. This surge price can be added to the base price of the trip.
When prices are surging, a multiplier to standard rates, an additional surge amount, or an upfront fare including the surge amount is shown to the customer. This will vary depending on city of the user. Surge pricing rates can be updated based on the demand in real time, surge can change quickly. Surge pricing is also specific to different areas in a city, so some neighborhoods may have surge pricing at the same time that other neighborhoods do not.
Notifications
Using a message queue or a message broker like Apache Kafka with the notification service is indeed a robust approach for dispatching push notifications efficiently. Here's how the setup works:
Benefits of this approach:
Try to discuss as many failure scenarios/bottlenecks as possible.
To make our system more resilient we can do the following: