System Requirements


Functional:


  1. Users can send messages (tweets) for up to 200 characters
  2. Users can follow other users, called friends
  3. Users can like another user's tweet
  4. A user's home page will show the messages of the users it is following in chronological order, with the most recent post appearing first
  5. The user's home page will also show the top K messages from the users it is following. The popularity of the message will be decided based on the number of likes the message has
  6. Users 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. Latency - A user upon entering their homepage should be able to see their feed in under 500 milliseconds
  4. Consistency - This can be a bit more relaxed, a user does not need to immediately see the posts from the users it is following, a delay is acceptable. Instead of strong consistency, we aim for eventual consistency
  5. Security - Content moderation and anti-abuse protection can be implemented, although we are not going through that in this design


Capacity Estimation


  1. We assume 500M daily active users and a maximum message size of 200 characters or 200 bytes
  2. We assume that the average user sends 2 messages a day. Total number of messages sent in a day would be 1 billion = 10^9
  3. 200 bytes of message data in a message, plus additional data, we assume that a message is of size 512 bytes
  4. Data generated in a day = 2 * 512 * 10^9 = 10^12 bytes = 1 TB
  5. In one year, we would need 365 TB data
  6. Factoring in replication of data, each year we would need 1000 TB data = 1 PB
  7. Over 10 years, the service would consume 10 PB data


API Design

  1. tweet (userID, content)
    1. Allows user with userID to post a message with the given content. Contents of the message 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 with ID userID to like the post with ID postID. This increases the like counter of the post by 1
  3. follow (followerID, followeeID)
    1. User with ID followerID starts following the user with ID followeeID
  4. unfollow (followerID, followeeID)
    1. User with ID followerID unfollows user with ID followeeID
  5. homeFeed (userID, offset)
    1. Returns a JSON document containing the post data of the user's home page with ID userID
    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 keeps scrolling lower in their feed, we can keep requesting more posts using this API



Database Design


  1. Based on the capacity estimations done earlier, a relational database is not advised
  2. We do not utilize joins in any capacity here, another reason to not use a relational database
  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 since it is a document style store and will also allow us schema flexibility
  5. The data model will be as given below.
    1. tweet
      1. Stores post related data
      2. postID Primary Key
      3. userID Index
      4. created_at
      5. content
      6. link
      7. like_count
    2. user
      1. Stores user information
      2. userID Primary Key
      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 post, all the users following it need to see the post
      2. userID Primary Key
      3. followerList List of users that follow this user
  6. Instead of having this in the document store, we can have a separate graph database that can 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 configured later. In this case, shared counters would do the counting using multiple different 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 which 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 shared 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.