System requirements


Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

  1. Post and Delete the tweets
  2. Like and unlike the tweets
  3. Search the tweets
  4. Check the home timeline
  5. Check the user timeline
  6. Follow and unfollow an account


Non-Functional:

List non-functional requirements for the system...

  1. Low latency. Twitter has huge amount of users globally so there will be huge QPS, we need to serve the requests with low latency to ensure good user experience.
  2. Availability. Twitter should always be available whenever user view, post or take other actions for good user experience.
  3. Scalability. Twitter users grows quickly, the design should support easy scaling up when we have more load in the future.
  4. Consistency. When different users take actions on the same tweet, for example, like or unlike, follow or unfollow, they need to see consistent data.
  5. Reliability. The contents and accounts user uploaded should always be there and findable.


Capacity estimation

Estimate the scale of the system you are going to design...

Assume 500M DAU


Server capacity:

  • Assume each user sends 20 requests per day, QPS = 5*10^8*20/(3600*24) ~= 100k
  • Assume the peak traffic is ~5X the normal traffic, peak QPS = 500K
  • Assume each single server could support 50K QPS, we will need ~10 servers


Storage capacity:

  • Assume each user post 2 tweets per day, 20% of them has image, 10% of them has video. In each tweet, text takes ~250 bytes, image takes ~200KB, video takes ~3M.
  • Then each day text will occupy storage: 5*10^8*2*250 bytes = 250G
  • Each day image will occupy storage: 5*10^8*0.2*200KB = 20TB
  • Each day video will occupy storage: 5*10^8*0.1*3M = 150TB
  • In total each day will use: 150+20+0.25 = 170.25TB





API design

Define what APIs are expected from the system...

According to the functional requirements, the API includes:


  • postTweet(user_id, tweet_type, content, content_length, media_field)
  • deleteTweet(user_id, tweet_id)
  • searchTweet(user_id, tweet_type, keyword, hash_tag, max_result)
  • likeTweet(user_id, tweet_id, tweet_user_id)
  • unlikeTweet(user_id, tweet_id, tweet_user_id)
  • getHomeTimeline(user_id, max_result, exclude, user_location)
  • getUserTimeline(user_id, max_result, exclude)
  • followUser(user_id, followed_user_id)
  • unfollowUser(user_id, followed_user_id)


Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...


Data Model:

  • User table
    • user_id: unique id for each user
    • user_location: location of the user
  • Friendship table
    • user_id: id of the follower
    • followed_user_id: id of the user who is followed
  • Tweet table
    • user_id: id of the user that tweet belongs to
    • tweet_id: unique id of each tweet
    • tweet_type: type of the tweet
    • content: text content of the tweet
    • media_field: media info, including the link to the image, link to the video etc
    • hash_tag: hash tags associated with the tweet
    • like_count: count of likes for this tweet
  • Timeline table
    • user_id: id of the user who owns the timeline
    • tweet_id: id of the friend's tweet in the timeline
    • create_timestamp: the timestamp this tweet is created
    • treet_type
    • content
    • media_field
    • hash_tag
    • like_count


Storage System

The data storage will contain the below components:


  • Cache (Redis): save the most updated and most popular contents in the cache for lower latency
  • SQL and NoSQL DB: store the tweets text contents and metadata
  • Blob Store: store the large size contents like tweet images and videos
  • CDN: stores the commonly used images and videos in local CDN
  • Message Queue: real time processing the data asynchronously




High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...


The key components to design a tweet system includes:

  • Client: the client starts the HTTP requests
    • Load balancer: distribute the high volume of requests to the cluster of servers.
    • CDN: some static media files could be directly fetched from local CDN.
  • Microservices: we will use separate services to deal with different business logics for better performance and failure tolerance. The main services include:
    • Tweet Service: process tweet, like post and delate post, update the like and unlike info to the tweet
      • Rate Limiter: in case of the high write volume, we add a rate limiter for write requests to increase the reliability and avoid DB crashes
      • Distributed Counter: to update like and unlike for a tweet, accurately counting concurrent like/unlike requests globally is important, we use distributed counter to efficiently handle this.
    • User Service: main user data and mutual relationship, to build the connection between users and their tweets
    • Timeline Service: build the home timeline and user timeline to the user, based on the tweet info and the user connections.
    • Search Service: search the tweets by keywords, user name or hashtag from the tweet DB. We will use the ElasticSearch and leverage its build-in high efficient features to handle this.
  • Database: each service will talk to different tables to handle their functions efficiently. In advantage of the distributed microservice design, we could use different types of DB for different services. In addition, multiple caches are used to optimize the performance.
    • Tweet DB (NoSQL): store the tweet contents, we could use NoSQL document DB, like MongoDB.
    • Tweet Cache (Redis): cache the user's recent tweets in favor of fast tweet read and pulling timeline.
    • Media Store (Blob Store): store the large media files like image and videos associated with tweets, we need blob store like Amazon S3.
    • Timeline DB (NoSQL): store the user's recent timeline, under the push model (after Message Queue fineout).
    • Timeline Cache (Redis): cache the user's timeline, under the pull model.
    • User DB (SQL): store the basic user profile, this data is more structured so we could use SQL DB like mySQL, although NoSQL DB is also fine.
    • Friendship DB (NoSQL): store the users friendship relationship to track follow/unfollow as well as building the timeline. We separate it from User DB for more flexibility and read/write efficiency.




Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...


  1. After getting the Application IP address from DNS, the client requests will be sent to load balancer.
  2. Different requests will be sent to different services accordingly. Each service contains a cluster of servers. With the algorithm like round robin, the load balancing will distribute to different servers.
  3. When fetching the static media like images, videos associated to the tweets, the client may also directly fetch from local CDN if available.
  4. Before reaching the main business logic in each service, there are components to optimize the performance, like Distributed Counter and Rate Limit before Tweet Service to optimize the high concurrent write requests.
  5. Each service will send the requests to downstream components for some tasks, like ElasticSearch to fulfill the search tweets, and Massage Queue for timeline fineout.
  6. In the end, the services will communicate with the corresponding database to read the data or update the records. In some services like tweet service and timeline service, it will directly read form cache when cache hit, if cache miss we will read from DB and update cache as well.






Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...


  • In Timeline Service, there are two types of methods we could use to build timeline efficiently: Push Model vs. Pull Model
    • With Push model, when a user post a new tweet, we could send it to Message Queue and let it fineout the tweet to all his/her friends' timeline table asynchronously. This enables fast read and the high write volume is efficiently optimized by the async Message Queue.
      • Read: 1 DB read.
      • Write: each new tweet leads to N DB write, where N = num of followers.
      • Extra DB is used to record timeline, but considering disk is cheap this is considerable to reduce read latency.
    • With Pull model, when a user view timeline, we pull his/her friends form friend relationship table, then query and merge friend's tweets as timeline. This doesn't need extra effort for write, but could be high cost for read. This could be further optimized by caching user's timeline and tweet.
      • Read: N DB read and 1 merge sort, this could be optimized to N cache read.
      • Write: 1 DB write.
      • Extra timeline DB is not necessary, but extra timeline cache could efficiently reduce read latency.
    • We will adopt a combination of Push + Poll model, where using Push for normal users, and Pull for celebrities (distinguished by tag or follower numbers).
  • In each DB, the data partition and replication are needed to ensure low latency, availability and reliability.
    • Distributed DB, the data are stored in the distributed DB, in different data servers, and even better, different data centers if possible.
    • Data Partition: tweet data is huge, it will be sharded by user_id. In case of concurrent read, those requests will be sent to different servers to mitigate hotspots.
    • Data Replication: data should be replicated in different data servers and data centers, so that when one data center is down the data won't be lost or unavailable.
    • Mast-slave model will be used for data partition and replication.





Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...


  • The timeline push/pull model trade offs as discussed in the Detailed Component Design session above.
  • Separate tables for user data and friendship data.
    • The friendship is one field in the user profile, so intuitively we could store that as a field of user table. However the downside includes:
      • Not efficient to store relationship list in the structured SQL DB
      • Search relationship is not efficient, if friendship is stored as list
    • So we will use a separate table to store friendship, keyed by user id. One record just store single following direction, so mutual friends will have two records. Although extra storage is occupied, the read latency could be largely reduced.



Failure scenarios/bottlenecks

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


  • Hot event. When there is a hot event happening, like new year, president election, celebrity big news etc, there could be multiple times of normal traffic requesting same info, which make cause application services crashes or DB crashes.
    • To deal with such cases, some extra temporary servers could be prepared forehead in the specific regions.
    • We could put the hot event tweets in cache.
  • Data center outage. Data center could down but the service should not be down.
    • Appropriate data partition and replication across different regions is perferred.




Future improvements

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

  • Dedicated Monitoring System. Monitoring is very helpful in finding issues reactively and proactively.
    • A system actively monitoring critical client and server side performances, like read/write QPS, latency, cpu usage, storage usage is needed.
    • Logging is needed, and some monitoring metrics could be built on top of logging metrics.
    • Once abnormality detected, alters should be triggered and send pagers.
  • Security. Some components could help to improve the security, like authorization, data encryption etc.