System requirements

Functional:

• A user can post a new tweet, which can contain text, pictures, videos, and etc
• A user can follow other users
• A user can view the timeline (news feed)
• A user can favoriate, share, comment on a tweet

...

Non-Functional:

• The sytem has to be highly available
• The system has to be highly reliable which store our tweets and data for a long period
• The system has to be scable to handle large amount of tweets generated

Capacity estimation

Assume we have 1B users registerd, and 100M daily active uses.

Assume each of them post 1 tweet each day and the average size of the tweet is 2M as it may contain photo and videos. 100M * 1 * 2MB = 200TB/day => 200TB * 365 * 5 = 365PB to store all tweets

API design

• post(tweetId, userId, time, location..) - user post a new tweet
• follow(uerId1, userId2) - a user can follow another user
• timeline(userId..) - user can view the timeline in the homepage
• like(tweetId, userId) - user can like a tweet
• comment()
• delete()
• share()

Database design

We need to design a user table, and tweet table, and following relationship table

• user(useId, username, password, creation_time)
• tweet(tweetId, userId, post_time, location, likes)
• follow(userId_1, userId_2)

High-level design

Request flows

1.post a new tweet

• a user write a new tweet and send the post request ->
• load balancer distribute the request to an appropriate server ->
• metadata and text conent of tweet will be stored into database and the video and picture will be stored into the blob, (its path then is stored to database with the metadata

2.view the timeline

• a user send a requset to view the timeline ->
• load balancer distribute the requset to an appropriate server ->
• server confirms the people followed by this user, and collect all the tweets post by these people from database, aggregate, sort, rank and return the reusult to the client

Detailed component design

Partition

Since this system has a high througput, so we need to partition the database, and store data across all partitions. Here are two approach to partitioning our database

1.Partition by userId

• pros of this approach is tweets of one user is all stored in the same partition, so it is very quick to retrieve tweets post by certain user.
• cons of this approach is hot user issue. If a user has way more tweets than other users, which may cause unbalanced partitions. Also if a user is celebrity, it will undertake overloaded read queries.

2.Partition by tweetId

• pros of this approach is tweets are distrubuted to the paritions evenly. We apply a hash function to the tweetId, then we can find the appropriate partition to store this tweet.
• cons of this approach is if we want to retrieve tweets from certain user, we have to check all the parition. Aggregrate the results returned from all paritions. In this case the performance might be affected and the latency is high.

Timeline

The straight forward way to generate timeline for a user is we first query database to find all the people this user follows. Then check all the paritions to retrieve the tweets post by these people. Aggregate, sort, rank and return the top K tweets. The problem with this approach is it's very slow because it has to hit the database frequently.

Here is the optimized solution. We can pre generate the timeline for each user, and store it in a key-value store in the Cache. The key is userId, the value is a list of tweets post by the people that this user follows. So every time if a user request to view the timeline, we can directly read it from the cache.

How to update the timeline?? If a user post a tweet, we can push this to all the people following this user.

But here is a problem with the push mode. If a user is a celebrity with large number of followers, then push mode will affact the performance. In this case, we can just let the user send a pull request to the server to retrive tweet of this celebrity from the database.

Therefore, we can implement a hybrid mode. For people with small number of followers, say 500, we can use push mode if he post a new tweet; otherwise we use pull mode.

Trade offs/Tech choices

• Cache

Store the data in the in-memory cache is costly, but for a read heavy system, it's very necessary to implement caching. We can store the tweets post from last three days. In most case people will only check the most recent tweets.

• Consistency vs availabilty

In this system, we may sacrifice the complete consistency for availabity. Since we have a huge number of tweets to store, we need to partition the database, and distribute tweets to them. And we have replicate each partition to avoid single point of failure. The propagation of update to all replicas take time, so we may not see the most recent update immediately. But in the end we will see that.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?