Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

1. post a tweet
2. follow / unfollow users
3. view a home feed of people you follow
4. like a tweet

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

1. prioritize availability over consistency
2. low latency especially on reads
3. 500m daily active users
4. 500m tweets a day -> 6k tweets/s with 3x peak at 18k tweets/s
5. read : write = 100:1 -> 600k reads/s on average
6. supports global traffic
7. 50k likes/s at peak

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

storage requirements:

• assuming each tweet has maximum of 200 words -> assuming each word has size of 10bytes -> each tweet will require 2kb of storage
• on 500m tweets a day, that is 1tb of storage a day on average -> 350 day a year, 5000 days in 14 years -> 5pb of storage for 14 years -> 350tb storage a year

a popular account with 1 million followers will have each post fan-out to 1 million account feeds.

write QPS:

• able to handle 18k writes per second
• estimated 18k * average 500 followers = 3.6m writes to individual accounts feed

read QPS

• able to handle 1.8m reads per second

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

• POST v1/tweet
  • store in tweet table
  • finds list of followers - find all rows with "following"=="posterID"
  • use the "user" in the result rows to push the tweet into their feed cache
• POST v1/user/follow
  • add a new row to follows table with "follower"="follower", "following"=who the follower is following
• POST v1/user/unfollow
  • hard deletes the row in follows table
• GET v1/feed
  • searches feed cache with "user" as the key
  • the value is the list of top 50 most recent tweets
• POST v1/tweet/like
  • since likes are not critical, it can exist as a column in tweets table, but it is aggregated in the likes cache before it is periodically flushed to the tweets table. to prevent the database from being hammered by the likes, we can accept the tradeoff of aggregating it and syncing periodically, though the items in the cache might be lost
  • calling this endpoint adds the userID to the likes cache which is an append only list of likes and unlikes of a tweet. the aggregator service will then periodically dedupe the likes and unlikes then flush the final state at the point in time to persist in the tweets table
  • syncing the cache with the tweets table will update the row in tweets table to increment the likeCount and update the list of likers. the aggregator service will also dedupe and duplicated users that appear in the cache and "likers" field in tweets table

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

1. requests from client goes through gateway which is in charge of rate-limiting, authorization check, service discovery etc.
2. data then flows to the load balancer which is in charge of routing the data to a horizontally scaled backend server.

likes:

1. as described in the API above, requests to update likes passes through the aggregator service which collates the likes and unlikes of a tweet in a cache and periodically syncs the data with the tweets table

post tweets:

• posting tweets are a very heavy API. the server will return a 200 HTTP response when the request is received but asynchronously fanout the tweets to construct each user's feed in a cache
• there will be a short delay between a user posting tweets and a follower receiving the tweet in their feed due to the latency of updating each user's feed in cache. this is accepted as we are prioritising a lower read latency vs write latency

get feed:

• to ensure a low latency on reads for a user feed, we are using a in-memory cache like redis to keep track of a user's feed
• if a user scrolls their feed beyond the top 50 posts that we are maintaining in the cache, we will then query the database for the next 50 posts

follow and unfollow:

• user following another user will append a new row to the follows table
• user unfollowing another user will hard delete that row from the follows table

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

tweets table:

• SQL database because each row corresponds to a tweet and each row is frequently updated on who likes the tweets

likes cache:

• key value cache like redis to aggregate the likes and unlikes of a tweet before periodically flushing the data to tweets table

follows table:

• SQL database that indexes on the user and following user
• the idea is that we need a mapping between each user and the followers this user has. using a NoSQL means we store the followers as a list for each user as the key. a list has O(n) time complexity for lookups and remove so it won't be ideal for removing followers
• in SQL each row maps 1 follower to 1 following

feed cache:

• key value cache with the userID as the key and the list of top 50 tweets that form the feed of the user as the value
• every tweet posted by someone the user is following will append the tweet to the list
• a doubly ended queue can be used as the value so that new tweets can be appended on the left and old tweets can be popped from the right

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

feed generation:

• current approach:
  • push based model
  • user posts a tweet -> fanout and update every follower's feed asynchronously
• other approaches:
  • pull based model
  • when user requests for their feed -> then their feed cache is updated with the top 50 posts from everyone they are following
  • this approach is not chosen because we are prioritising lower read latencies over write latencies. this approach reduces the latencies on the writes when a user posts a tweet but more computation is done when a user requests for their feed
• considerations:
  • the celebrity problem - where a user with 100m followers post a tweet, we have to update 100m user's feed in the feed cache. This is an expensive operation.
    • this is an accepted trade off if we want to prioritize read latencies to be as low as possible.
    • if we want to balance read and write latencies, we could adopt a hybrid approach where user's feed are maintained with pushed tweets from non-celebrities. but at the time of calling the feed API, it is constructed by pulling the tweets from celebrities. this solution is not accepted because it increases the read latency on retrieving a user's feed.
  • since we are using a cache on the feed cache, we will have to set a TTL on the key value. redis need not be big enough to hold the feed of every single user of twitter.
    • each user's feed can be maintained for a week. when user is inactive for a week, their feed is evicted from the cache. this ensures that the cache does not reach max storage capacity.
    • if we notice cache reaching maximum storage space, we can decrease the TTL.
      • each post is 2kb -> 50 posts is 100kb per user -> for 100m active users, thats 10tb of cache size in redis. this can be achieved by horizontally scaling redis to include more nodes in a redis cluster
  • on a cache miss, the top 50 posts for the user is retrieved by querying the tweets table. this data is then cached.
    • this will present as a slower operation for user's opening their feed for the first time in the week, but it will be much faster afterwards.
    • a cache failure would mean an empty cache on startup. each user's feed will then be pulled and constructed in cache on demand
    • thundering herd problem is avoided as the feed is constructed on demand when user requests instead of trying to build the feed entirely for all users
  • the feed cache uses the userID as key and a doubly linked list as the value.
    • each node in the linked list should contain all the data and metadata needed to construct the tweet in the feed, so that the tweets table need not be queried again during the generation of the feed
  • the top 50 posts are ordered based on the requirements of the product - if ranking is needed
    • if it should be shown based on chronological order, a doubly linked list is good to append and pop
    • if it should be shown based on an engagement score, maybe a heap can be used to push and pop from heap based on this score. top 50 posts will then be ordered based on a score rather than time ordered. this scoring model can then be versioned and running offline and the cache is only updated on a TTL or when the model updates.
• GET v1/feed will have a query params to include cursor and page to include pagination in the API.
  • page 1 will alway retrieve from the feed cache while pages after 1 will require a lookup on tweets table by skipping the number of pages * page size

likes aggregator:

• this service will aggregate all the likes in the likes cache but having the <tweetID> as the key and a hash set as the value
  • this is done this way as a user can like and unlike a post as many times as they want. so lookups, add and remove are all O(1) time complexities on a hash set.
• every few seconds, the aggregator service will retrieve the set of users that like the tweet from the likes cache and the tweets table. it will dedupe the users that like the tweet and persist the entire list of users in the tweets table.