System requirements
Functional:
- Follow and unfollow users.
- Post tweets.
- Search tweets.
- The tweets could contain text, image and video.
- View tweets in user's timeline.
- Like a tweets.
- Comment a tweets.
- Search tweets.
Non-Functional:
- Availability
- Scalability
- Latency
- Reliability
- Consistency
Capacity estimation
Assume twitter have 1B Daily Active Users.
Read QPS is 1B / 100k = 10k. Peak read QPS is 2 * 10k = 20k.
Assume 1% users write 10 tweets per day.
Write QPS is 1B / 100k * 1% * 10 = 1k. Peak write QPS is 2 * 1k = 2k.
Data storage estimation:
Assume 10% tweets contains image or videos. Average Tweets storage usage is 10k. The total daily storage usage is:
1B * 1% * 10 * 10k = 1TB. Each storage will need two more replica. So in total daily storage usage is 1TB * 3 = 3TB.
API design
GET getNewsFeed(
authToken,
userId,
lastSeenKey (for pagination)
count
) => Tweet[] / Error
GET getComments(
authToken,
userId,
parentId, (Could be either a tweet or comment)
lastSeenKey (pagination)
) => Comments / Error
POST postTweet(
authToken,
userId,
content: Content
) => Succeed / Error
POST postComments(
authToken,
userId,
parentId (Could be either a tweet or comment)
) => Succeed / Error
POST likeTweet(
authToken,
userId,
tweetId
) => Succeed / Error
GET searchTweet(
authToken,
userId,
searchText,
lastSeenKey (for pagination)
)
PUT editTweet
POST followUser
POST unfollowUser
For error handling, the api could send back different http error code with detailed error message with different kind errors. Some example http status error codes are:
400 Bad Request
401 Unauthorized
403 Forbidden
404 Not Found
503 Service Unavailable
For authentication, each api will be attached with authentication token. The token could be either cookies, auth 2 token or JWT token to validate user's identity.
Here are the objects in the api above:
Tweet {
tweetId,
creators,
createdAt,
likeCount,
content: Content
topComments: Comment[]
}
Content {
contentId,
tweetId,
text,
media: Media[]
}
Media {
mediaType,
mediaSolution,
mediaURL
}
Database design
High-level design
I will use sql database to store user, tweets and comments information. Because these data are relational data in nature. It is easier to combine and queries the data.
I will use graph database to store the follow and unfollow relationship between users.
I will use no-sql database to store media metadata.
I will use blob storage to store the actual image or video of the tweets.
I will use data storage like elastic search to store indexes of the tweets, which allows searching tweets faster.
SQL database Schema:
User Table: userId, userInfo, numberOfTweets, numberOfComments ...
Tweet Table: tweetId, userId, content, mediaId, likeCount, commentIds, createdAt, updatedAt
Comment Table: commentId, parentTweetId, parentCommentId, userId, content, createdAt, updatedAt
Graph database Schema: The node will be the userId, the edges will be the relationship (following, follow) between users.
no-sql database stores media metadata: key is the id of the media, values contain the type of the media, whether it's image or video. The values also contain the actual urls of different resolution of the medias stored in blob storage.
Request flows
- Client post a tweets or comments.
- The post request go through load balancer to do load balancing
- The post request go through api gateway to do authentication, rate limiting and security check.
- The post request go through tweets service.
- The tweets service publish the request to tweets message queue.
- The tweets service publish the comments request to comments message queue.
- The tweets service publish the request to the media message queue if there is a media in the posts.
- One worker which subscribes tweets message queue will store the tweet information into SQL database.
- Another worker which subscribes tweets message will store the tweets into elastic search data store to index the tweets contents. The data store will provide fast search when searching tweets.
- The comment message queue subscriber will save the comment request into SQL database.
- The SQL database will update RDB Cache.
- NewsFeed service will read from RDB cache for any new tweets update. The NewsFeed service will be responsible to run ML model and recommend user's news feed post timeline based on the user's followings, posts' popularity, user's region, user's interests and more factors.
- When client request posts in their timeline, the request will be routed to get timeline service. The get timeline service will call NewsFeed service to return the pre-generated news feed for the client.
- When client request media inside tweets, the request will be routed to the CND near the client's location. The CND stores the media for the client.
- When client searches tweets, the request will be routed to search tweets service. The search tweets service will query elastic search cache and indexes to return search results.
- When client request follow or unfollow a user, the request will be routed to following service. The following service will update Graph Database to update the relationship between users.
- When client like a tweets or comments, the request will be routed to tweets service. The tweets service will send the request to sharded counters and aggregators to count the number of likes for a tweets generated. Finally the number will send to RDB database to update the number likes in the database.
Detailed component design
Dive deep into SQL database:
The SQL Database to store User, Tweets, Comments in User table, Tweets table and Comments table.
The User table, the prime key is userId. The user table could be indexed by userId, numberOfTweets and numberOfComments columns. The purpose of indexing the three columns is to shard the table. To horizontally shard the database. The User table could be sharded by a combination of userId and numberOfTweets, numberOfComments. This will make sure each database shard evenly distributed with the similar content size.
The Tweets table, the prime key is tweetId. The reference key is userId, which reference who post the tweet. Another reference key is the mediaId, which reference to the mediaId stored in the media NoSQL database. The Tweets table could be indexed by tweetId, userId and mediaId. The Tweets table could be sharded by userId as well. Try to put all the tweets posted by the same userId in the same shard, which would be easier to look up.
The Comments table, the prime key is commentId. The reference key is userId and parentTweetId and parentCommentId. UserId reference to who post the comment in the User Table. ParentTweetId reference to which tweet the comment commented to in Tweet table. ParentCommentId reference to the case that the comment commented to a comment. ParentCommentId reference to Comments table. The Comments table could be indexed by commentId, userId, parentTweetId and parentCommentId. The comments table could be sharded by parentTweetId. Try to put all the comments of a tweet in same shard, which would be easier to look up.
Dive deep into elastic search component.
When a new post posted, it will be stored to the elastic search data store. The store will be index by tweets content, create time, updated time, region and popularity. When user search a tweet by search text, the request will be routed to the elastic search to search from the indexed contents. The result will be returned to the machine learning model. The machine learning model will sort the results by multiple factors, for example user's followings, posts' popularity, user's region, user's interests. To speed up the search latency, there will be cache layer on top of the elastic search. The cache layer will store search results for popular search terms for a certain timeframe.
The data stored in the elastic search data store could be eventual consistency.
Trade offs/Tech choices
The reason I choose SQL/relational database to store User, Tweets and Comments is that These data are relational data in natural. It is easier to search and query by reference key in SQL database. For example, the following query is much easier in relational database: Query all the tweets certain user posted today.
The reason I choose Graph database to store users' relationship is that graph database has the advantage to store this kind of relationship. The node will be the user and the edge will be the following/follower relationship between user. The graph database makes it faster to travel the users to find their followings and followers.
The reason I choose NoSQL database to store the media metadata is that the metadata is key value based data. The key is the mediaId and the value is the type, resolution and url of the actual media.
The reason I choose Blob storage to store media data is that blob storage is good to store large un-related data like images and videos.
The reason I choose Elastic Search for data store is that elastic search is faster to index and search for text content, which is suitable to search tweets contents.
Failure scenarios/bottlenecks
Our non-functional requirements for the proposed twitter system design are scalability, fault tolerance, availability, and low latency. Let’s discuss how the proposed system fulfills these requirements:
- Scalability: The proposed system is scalable to handle an ever-increasing number of users. The required resources, including load balancers, web servers, and other relevant servers, are added/removed on demand.
- Fault tolerance: The replication of data consisting of users’ metadata, posts, and newsfeed makes the system fault-tolerant. Moreover, the redundant resources are always there to handle the failure of a server or its component. Monitoring service is used to enhance reliability by continuously observing system health, detecting issues early, providing insights for optimization, and assisting in timely incident response.
- Availability: The system is highly available by providing redundant servers and replicating data on them. When a user gets disconnected due to some fault in the server, the session is re-created via a load balancer with a different server. Moreover, the data (users metadata, posts, and newsfeeds) is stored on different and redundant database clusters, which provides high availability and durability.
- Low latency: We can minimize the system’s latency at various levels by:
- Geographically distributed servers and the cache associated with them. This way, we bring the service close to users.
- Using CDNs for frequently accessed newsfeeds and media content.
Future improvements
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?