Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 1 billion MAU, and 40% of them are DAU, so we have 400 million DAU.
For each DAU, assume that they refresh their home page 10 times a day, and post 2 tweets per day on average.
This gives us roughly 100K RPS for reads, and 20K RPS for writes.
We also need to consider storage, for each tweet, we store text and metadata in the database, and media in file storage.
2 tweets per day * 400 million DAU * (365 * 5) days = 1 trillion 460 billion tweets.
Assume on average, the text and metadata for each tweet is 1KB, and 1MB for media.
We need 1.46PB of database storage, and 182.5PB of file storage.
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
For a user to see their home page feed:
GET V1/home_feed {
user_id: UUID
}
For a user to post a tweet:
POST v1/post_tweet {
user_id: UUID,
created_at: Timestamp,
tweet_text: String,
tweet_image_url: String,
hashtags: String
}
For a user to like a tweet:
POST v1/like_tweet {
user_id: UUID,
tweet_author_id: UUID,
tweet_id: UUID
}
For a user to follow a user:
POST v1/follow_user {
user_id: UUID,
follow_user_id: UUID
}
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
For all the requests the system processes, we first go through an API gateway that does authentication and rate limiting. We rate limit each user based on IP/device/login info etc. to 50 read requests per minute, preventing single user from overloading the system. We authorizes a user in login, and uses JWT tokens for further requests. After API gateway, we hit a load balancer, that routes requests to different servers of a service based on consistent hashing.
We will walk through the write path and read path for users. First of all, we have a redis cache cluster that stores the tweet feed for each user, with an TTL of 1 hour. This caching layer ensures that requests to read user feed for a user is processed very fast.
When the cache entry expires for a user's user feed, next time when the user requests their user feed, we look at the list of users that user follows, and we retrieves the latest tweets for each of those users, build the home page feed based on likes, followers and timestamps, and store it in the cache. To prevent cache stampede, we add jittering to cache TTL, as well as do stale-while-revalidate for cache expiries. In case of redis cluster downtime, we rely on the database to return tweet feed. However, with no caching layer, the database will likely be overwhelmed in peak hours, and we will do load shedding until cache recovers.
When users post a tweet, we need to update both the tweet relational database, as well as the home page feed stored in the redis cluster.
For the home page feed in the redis cluster, we distinguish between a pull vs push model based on whether the user is a celebrity. If the user is a celebrity with millions of followers, we avoid updating the home page feed for all of their followers. Instead, we let their follower get latest update next time when the cache refreshes. This strategy could lead to stale data for some users in their home page feed, however, this prevents the bulk update requests from overloadding the cache. For ordinary users, when they post a new tweet, we write to the home page feed of all of their followers. When users actually read their home page feed, we can quickly load from the redis cache.
Whenever users like/repost a tweet, or follow a new user, we do 2 things:
For the relational database, in order to handle the large capacity and traffic throughput, we need to do sharding and replication.
First of all, we shard the users and tweets tables by user_id, on multiple database replicas. We use consistent hashing to evenly distribute the load.
We also create several read replicas for each write replica, to increase read throughput. We will let write replica to synchronously update each write to all read replicas, which increases write latency a bit, but ensures consistency at read time.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
For data storage, we store below information:
Other than media information which we will store in object storage like S3, the rest of data will be stored in a distributed relational SQL database.
Here's why:
Here's tradeoffs:
Here's the detailed table schemas:
table users {
user_id: UUID,
user_name: String,
followers: List
following: List
}
table tweets {
tweet_id: UUID,
author_id: UUID,
like_count: Integer,
repost_count: Integer,
tweet_text: String,
tweet_media_links: List
tweet_created_at: Timestamp
}
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
For data storage, we store below information:
Other than media information which we will store in object storage like S3, the rest of data will be stored in a distributed relational SQL database.
Here's why:
Here's tradeoffs:
Here's the detailed table schemas:
table users {
user_id: UUID,
user_name: String,
followers: List
following: List
}
table tweets {
tweet_id: UUID,
author_id: UUID,
like_count: Integer,
repost_count: Integer,
tweet_text: String,
tweet_media_links: List
tweet_created_at: Timestamp
}
For all the requests the system processes, we first go through an API gateway that does authentication and rate limiting. We rate limit each user based on IP/device/login info etc. to 50 read requests per minute, preventing single user from overloading the system. We authorizes a user in login, and uses JWT tokens for further requests. After API gateway, we hit a load balancer, that routes requests to different servers of a service based on consistent hashing.
We will walk through the write path and read path for users. First of all, we have a redis cache cluster that stores the tweet feed for each user, with an TTL of 1 hour. This caching layer ensures that requests to read user feed for a user is processed very fast.
When the cache entry expires for a user's user feed, next time when the user requests their user feed, we look at the list of users that user follows, and we retrieves the latest tweets for each of those users, build the home page feed based on likes, followers and timestamps, and store it in the cache. To prevent cache stampede, we add jittering to cache TTL, as well as do stale-while-revalidate for cache expiries. In case of redis cluster downtime, we rely on the database to return tweet feed. However, with no caching layer, the database will likely be overwhelmed in peak hours, and we will do load shedding until cache recovers.
When users post a tweet, we need to update both the tweet relational database, as well as the home page feed stored in the redis cluster.
For the home page feed in the redis cluster, we distinguish between a pull vs push model based on whether the user is a celebrity. If the user is a celebrity with millions of followers, we avoid updating the home page feed for all of their followers. Instead, we let their follower get latest update next time when the cache refreshes. This strategy could lead to stale data for some users in their home page feed, however, this prevents the bulk update requests from overloadding the cache. For ordinary users, when they post a new tweet, we write to the home page feed of all of their followers. When users actually read their home page feed, we can quickly load from the redis cache.
Whenever users like/repost a tweet, or follow a new user, we do 2 things:
For the relational database, in order to handle the large capacity and traffic throughput, we need to do sharding and replication.
First of all, we shard the users and tweets tables by user_id, on multiple database replicas. We use consistent hashing to evenly distribute the load.
We also create several read replicas for each write replica, to increase read throughput. We will let write replica to synchronously update each write to all read replicas, which increases write latency a bit, but ensures consistency at read time.