Requirements
Functional Requirements:
- Allow users to tweet messages up to 140 characters.
- Enable users to follow other users.
- Allow users to like tweets from other users.
- Display tweets from followed users in the home feed.
- Show top K popular tweets in the home feed based on likes and followers.
Non-Functional Requirements:
- For users, the p99 latency for viewing their home page should be less than 100ms, and the p99 latency for following other users and liking tweets should be less than 50ms.
- The app should be available 99.99% of time.
- The app can be eventually consistent. For example, if user A posts a new tweet, it's okay for his follower A to see it while his follower B hasn't. However, users should never experience time travel, where they see a tweet, then the tweet disappears on refresh.
- The system should be easily scalable as number of users and content continuously grow.
Capacity Estimation
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.
API Design
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
}
High-Level Design
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:
- We update the corresponding relational database on the like count/follower list
- We trigger an event to be ingested by Kafka, which writes this like/follow event to a cassandra database that stores the logging of all events. This will help us to do analysis later.
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.
Database Design
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:
- Metadata and text about a tweet
- Media associated with a tweet
- Follower list for each user
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:
- We need ACID guarantees for data, which a relational SQL database provides.
- We need complex join queries across different tables, which relational database easily supports.
Here's tradeoffs:
- Compared to document database like mongoDB, we won't have a as flexible schema. However, this is acceptable since our data schema doesn't change often.
- Compared to noSQL database like cassandra, we won't be able to scale horizontally as easily and won't be able to handle high write throughput as easily. However, we could scale the database cluster to handle our scale through sharding and replication.
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
}
Detailed Component Design
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:
- Metadata and text about a tweet
- Media associated with a tweet
- Follower list for each user
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:
- We need ACID guarantees for data, which a relational SQL database provides.
- We need complex join queries across different tables, which relational database easily supports.
Here's tradeoffs:
- Compared to document database like mongoDB, we won't have a as flexible schema. However, this is acceptable since our data schema doesn't change often.
- Compared to noSQL database like cassandra, we won't be able to scale horizontally as easily and won't be able to handle high write throughput as easily. However, we could scale the database cluster to handle our scale through sharding and replication.
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:
- We update the corresponding relational database on the like count/follower list
- We trigger an event to be ingested by Kafka, which writes this like/follow event to a cassandra database that stores the logging of all events. This will help us to do analysis later.
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.