Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Platform has ~1 billion users globally.
Out of them, 20% use location service = 200 million
Per second, ~50 million are active and reporting location.
Assume each user has ~400 friends out of which 40 are active per second and location data is transmitted.
Num location updates transmitted and received per second = 50 million * 40
= 2 * 10^9 updates per second
Amount of data in each update is small - ~20 bytes
So amount of data transmitted per second = 40 GB
This amount of QPS and data rate requires sharding.
Real-time Location updates are in a cache. They are persisted in a Location DB for historical analysis.
Define what APIs are expected from the system...
POST wss://
{
latitude:
longitude:
timestamp:
userId:
}
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
User DB, Friends DB: Given the scale of service, a NoSQL DB like Dynamo DB or Cassandra can be used. Friends relations are stored using a GraphDB
Location History DB: This DB gets heavy writes. Cassandra is a suitable choice for DB.
Location Cache: Stores real-time updates. It has a TTL so that location data can be evicted if no update is received for a predetermined time (30 seconds). Redis is a good option as it has in-built TTL eviction feature.
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
User: End-user reporting and getting location updates
User/Friend Management Service: Responsible for general user registration, add/remove friends, view etc.
Location Servers: Maintain a web-socket connection with users.
Location Cache: Redis cache storing real-time location update. The cache has TTL eviction policy.
Location History DB: Stores location history of each user for analytics and personalization
Friends DB: Persistent Store for Friends, User data
Redis PubSub Cluster: Gets and sends location updates to subscribed users. It is like a fan-out service which publishes location update of a user to all friends.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
On Sign-in
==========
Location Updated
================
Some of these steps can be done in parallel
Receive Location Update of A Friend
===========================
Continueing the above flow, when a user's location update is published on her channel, all subscribers(friends) of the user will get the update.
The connection handler will calculate the user's distance from that reported by the update and if within threshold, send this update.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Web Sockets
===========
Communication pattern here is real-time and 2-way between clients/users and location servers.
Instead of making the user poll for updates, keeping a long-running connection saves connection establishment overhead, processing power, battery etc. which is especially important for mobile clients.
Redis Pub/Sub
============
The publish-subscribe model is suitable for this use-case where friends subscribe to location updates of their friend. Redis Pub/Sub is a lightweight solution and it can create many channels, 1 per user to publish the updates.
Internally, a set of friends subscribe to this channel and get the updates. This is implemented using a hash table and linked list. If no update is published or a user is not online, that channel will occupy minimal memory and have no CPU overhead.
Also, the updates on the channel are not persisted and dropped after receipt(if there are subscribers) or immediately if there are no subscribers.
Explain any trade offs you have made and why you made certain tech choices...
Web Sockets
===========
Communication pattern here is real-time and 2-way between clients/users and location servers.
Instead of making the user poll for updates, keeping a long-running connection saves connection establishment overhead, processing power, battery etc. which is especially important for mobile clients.
Redis Pub/Sub
============
The publish-subscribe model is suitable for this use-case where friends subscribe to location updates of their friend. Redis Pub/Sub is a lightweight solution and it can create many channels, 1 per user to publish the updates.
Internally, a set of friends subscribe to this channel and get the updates. This is implemented using a hash table and linked list. If no update is published or a user is not online, that channel will occupy minimal memory and have no CPU overhead.
Also, the updates on the channel are not persisted and dropped after receipt(if there are subscribers) or immediately if there are no subscribers.
Try to discuss as many failure scenarios/bottlenecks as possible.
Sharding
=========
Database can be sharded as per user id.
Scaling Redis PubSub
==================
All user's channels cannot be on a single server. Use consistent hashing to assign a pub-sub server to a user. When this assignment is redistributed, many subscriptions, flood of updates will arrive. Some location updates can be dropped also. This can be reduced by scheduling this activity during quiet times of the day.
WebSocket connections are stateful
=========================
When a websocket server gets replaced, all location updates of a user and connection handler sending updates from friends is destroyed and must be recreated. It can cause missed location updates. To avoid it, connections can be first drained to the new server.
Users with Many Friends
====================
Some users have more friends than others. PubSub channels of such users will have many subscribers. However, as users are sharded to different pubsub servers as per user id, no single pub-sub server will get overwhelmed.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?