System requirements

Functional:

1. Users can publish posts, including text, images, and videos
2. Users can view all friends' feeds on the home page in reverse chronological order

Non-Functional:

1. Users can view the feed page in low latency
2. The system should be highly available
3. The data can eventually be consistent
4. The system should be highly scalable

Capacity estimation

1. Assume the DAU is 1 billion, and each user publishes 1 post per day
2. Based on the above assumption, the write QPS is 10^9/10^5 = 10k. Assume the read-write ratio is 10:1 and the read QPS is 100k.
3. Assume each post size is 1kb and there are 1 billion new posts every day, so we need 1tb for every day.

API design

1. POST /v1/myfeed
   1. parameter: auth_token and content
   2. return: feed_id
2. GET /v1/myfeeds
   1. parameter: auth_token, cursor_id, and limit
   2. return: friends' feeds

Database design

1. Users
   1. user_id
   2. user_name
   3. config
   4. created_at
2. Friendships
   1. following_user
   2. followed_user
   3. created_at
3. Posts
   1. post_id
   2. created_by
   3. created_at
   4. content

Read is crucial for the system, and there is a significant join case, so we can consider a key-value database like DynamoDB for all entities.

1. Users
   1. user_id is the partition key for easily even partition
2. Friendships
   1. key is following_user:followed_user
   2. partition key is following_user
   3. sort key is followed_user
   4. To easily fetch who follows a user, we can create a GSI: partition key is followed_user and sort key is following_user
3. Posts
   1. post_id is the partition key for easily even partition
   2. created_by and created_at are the sort keys
   3. To easily fetch all feeds by user_id and sort by reverse chronological order, we can create a GSI: partition key is created_by and sort keys are post_id and created_at

High-level design

1. Load balancer: distribute request
2. API gateway: redirect request to corresponding service
3. Post service: store posts into database and cache
4. Fanout service: push new feeds to followers' news feed page
5. News feed service: retrieve freiends' news feeds
6. Notification: send notification to inform user there is new content
7. CDN: user can fast retrieve post content, including images and videos

Request flows

1. Publish posts
   1. When user publishes a new post, post service will store the content into both post database and cache
   2. Fanout service will push it to all followers and store it into news feed cache
   3. Notification service will inform followers
2. Retrieve feeds
   1. When user requests to retrieve followers' feeds
   2. news feed service will friend ids from friendship database and post ids from post feed cache

Detailed component design

1. Fanout service
   1. When a user publishes a new post, the fanout service will get friend_id list and friend information, including configuration to determine how to fan out the new post.
   2. Fanout service will publish the post_id and friend_id list to message queue, and fanout worker will store post_id: user_id map in the cache for fast read by news feed service
2. News feed service
   1. It fetches a list of post_id from news feed cache
   2. To construct complete feed object, it also needs to fetch user data and post data from corresponding cache and send back to user a json object

Trade offs/Tech choices

How to fanout

1. Push: feed is precomputed when the new post is published and is delivered to user immediately
   1. Pro
      1. news feed is delivered in real time
      2. reading feed is fast because it is precompted
   2. Con
      1. if a user has tons of followers, server may be overloaded
      2. it will generate news feed for users who rarely logged in
2. Pull: feed is generated when user requests the news feed
   1. Pro
      1. it won't generate news feed for inactive users
      2. it won't overload server
   2. Con
      1. Computing feed consumes time, so news feed generation will be slow, especially for user who is following lots of friends

For most users, we can use push, while for celebrities and users who has tons of followers, we mark them and their feeds will be delivered when their friends request

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?