System Requirements

Functional:

1. Users can send (tweet) a message for up to 200 characters.
2. Users can follow their friends.
3. Users can like another user's tweet.
4. User's home page will show tweets of the users it is following in chronological order, with the most recent post appearing first.
5. User's home page will also show the top K messages from the users it is following. The popularity of the tweet will be decided based on the number of likes the post has.
6. User can block posts of a certain user from appearing on their home page.

Non-Functional:

1. Scalability - We expect a high number of daily active users, probably 500 million.
2. Availability - The service needs to be highly available.
3. Response Time - A user upon entering their home page, should be able to see their feed in under 500 milliseconds.
4. Consistency - This can be a bit more relaxed, a user does not immediately need to see the posts from the users it is following, a delay is acceptable. Instead of strong consistency, we aim for eventual consistency here.
5. Security - Content moderation and anti-abuse protection can be implemented, although, here I am not going to delve into it.

Capacity Estimation

1. We assumed having 500 million daily active users and a maximum tweet size of 200 characters, or 200 bytes.
2. We assume that the average user makes 2 tweets a day, total number of tweets made everyday would be 1 billion = 10^9.
3. 200 Bytes of message data plus other data in a tweet, we can assume a tweet would consume 512 bytes of storage.
4. Data generated each day = 2 * 512 * 10^9 bytes = 10^12 bytes = 1 TB.
5. In one year, we generate 365 TB data.

API Design

1. tweet (userID, content)
   1. Allows the user with userID to post a tweet with the given content. Contents of the post would be passed on as a JSON and would be parsed by the server when displaying.
   2. Every post will have a unique ID auto generated and tagged to it.
2. like (userID, postID)
   1. Allows user having userID to like the post having postID. This increases the like counter of the post with ID postID by 1.
3. follow (followerID, followeeID)
   1. User with the ID followerID starts following the user with ID followeeID.
4. unfollow (followerID, followeeID)
   1. User with the ID followerID unfollows the user with ID followeeID.
5. homeFeed (userID, offset)
   1. Returns a JSON document containing the post data that should be shown on the user's home page.
   2. offset represents the number of tweets that need to be returned. When a user opens his home page, the offset will be 0. In case the user refreshes the home page, the offset can be a small number like 5 to reduce server load. Also, the offset can be device specific, something like a mobile device does not need a large offset figure.
   3. As the user scrolls lower in their feed, we can keep requesting more posts using this API.

Database Design

1. Based on the capacity calculations done earlier, a relational database is not advised.
2. We do not utilize joins in any capacity here, another reason to not use relational databases.
3. We opt for a non-relational database that uses a document style store to effectively store the posts made by users.
4. MongoDB is a good choice here since it a document store and will allow us schema flexibility.
5. The data models are given here.
   1. Tweet
      1. Stores the post related data
      2. postID Primary Key
      3. userID Index
      4. created_at Index
      5. content
      6. links
      7. like_count
   2. user
      1. Stores user information
      2. userID Primary
      3. email
      4. phone
      5. name
      6. date_of_birth
   3. follow
      1. Stores user follower relationship. This can be used to quickly fetch the users that follow the user with ID userID. We then know that when that user makes a most, all follows need to see the post
      2. userID Primary Key
      3. follows List of users that this user follows
6. Instead of implementing the follow relationship in a document store, we could have a graph database that could map the user follower relationship
7. The like counter would be a scalability challenge. If a celebrity person makes a post, it will be liked by a large number of people. This will make the like counter for that particular post a hot spot for change. To protect against this, we would implement a distributed counter service for users with over, let's say 10,000 users. This is a number that can be configured later. In this case, shared counters would do the counting, using multiple separate counters implemented in memory, using something like Redis and then once in a while, let's say every 5 minutes, we would hit our document store and update the like counter.

High-level design

1. A Content Delivery Network service like Akamai or Cloudfare can be used to serve all the static content.
2. A rate limiter can protect against denial of service attacks, intentional or otherwise.
3. Tweet service's job is to receive requests for new tweets and populate them in the document store. It can also queue the message in a message queue when can then be utilized for some other service, like analytics.
4. Tweet Analyzer pulls messages from the message queue that is populated by the tweet service and analyzes them for hashtags, inappropriate content.
5. Home Feed service handles populating the home feed of a user.
6. Data should be sharded by region as users of a certain region would be more interested in posts of that region. Globally trending posts could be cached in the CDN and served to all regions.
7. Data should be replicated among data centers for greater fault tolerance.

flowchart TD CL[client] --> CDN[CDN] CDN --> RL[Rate Limiter] RL --> LB[Load Balancer] LB --tweet()--> TW[Tweet Service] TW --Store--> DB[DB: MongoDB] TW --> MQ[Message Queue] TA[Tweet Analyzer] --Pull Message--> MQ TA --Update-->DB CA[Content Analyzer] --Pull Message-->MQ LB --home_feed()--> Home[Home Feed Service] Home --> DB Home --> Cache[Redis Cache] LB --like()-->CT[Sharded Counter] CT-->DB

Request flows

1. Populate Home Feed
   1. Get the user IDs of the users following the person making the post.
   2. Populate the post in the cache of all the users.
2. Get Home Feed
   1. Check if posts are present in the post cache, if yes, get them, if not, hit the DB
3. Follow User
   1. Go to the user ID which our current user wants to follow
   2. Add ID to the follower list

Detailed component design

Score of Tweet = weight_like * number_of_likes + weight_followers * number of followers on the tweet's author + weight_retweet * number_of_retweets

The top-K posts to be shown on a user's home page can cached for quick retrieval. The top posts can be found by inserting all of the posts in a max heap data structure and then picking the top K posts. The max heapify operation would run based on the tweet score calculated above.

The cached data can be stored in a caching system like Redis, this does not need to be persisted on disk since it is subject to change frequently.

For users that do not log in frequently, getting top K posts can be considered a waste of computing power. We can stop calculating the top K posts for users that have not logged in in the last 7 days, where the number of days is a configurable parameter. For these users, the posts can be populated on login and then these users can be added to the circulation of users for whom posts are cached.

Trade offs/Tech choices

1. We a non-relational database instead of a relational one, the relational database would have provided better consistency although it would not have as scalable as a non-relational database like MongoDB.
2. Cassandra would be better than MongoDB in terms of scalability but a column store would not have allowed us flexibility in storing our data.
3. Storing post data becomes very easy because of a document store like MongoDB.

Failure scenarios/bottlenecks

1. A celebrity makes a post that is liked by millions of other users and is retweeted by thousands of users, this can overwhelm the server. A distributed counter service can help in this situation.
2. If a celebrity with millions of followers makes a post, then post must be populated in the feed of millions of users, this can overwhelm the post service.

Future Improvements

1. Adding the functionality for a user to re-post a post made by a different user.
2. Adding filters to post to filter content on basis of certain words.
3. Post moderation service to prevent hateful speech, graphic content.
4. Ability to block posts from a certain user.