Design A New Feed System

The main thing of a new feed system is the feed distribution which takes the data from Post Database and User database to distribute the feeds.

When distribute the feeds, we can use cache instead of database since the newfeed is changing daily.

We use Pull model here since it the workers can dynamically generate the newfeed during read time. Using push model can achieve real time but however expensive.

Step 1: Understand the problem

Some important questions:

1. Question: Mobile app or web app or both?
   • Mobile app we might need to handle notification
   • Answer: Both
2. What are the important features?
   • We need to check which features are needed for the design
   • Answer:
     • See and post feed
3. Is the new feed sorted by score or something?
   • Answer: no, just sort by order post time
4. How many friends can a user have
   • Answer: 5000
5. What's the traffic volume:
   • Answer: 10 million DAU
6. Can feed contain images, videos or just text
   • Answer: can contain media files, both image and video

Step 2: propose high level design

We have 2 tasks:

1. Feed publishing:
   • When user publishes a post, data is written into cache and database. Post is then deliver to friends new feed
2. Feed building:
   • New feed is built by aggregating friends' posts from newest to oldest

Newsfeed api

Post the feed

POST /v1/me/feed
- content: content of the text (request body)
- auth_token: auth token to authenticate API request (request header)

Retrieve the feed

GET /v1/me/feed
- auth_token: auth token to authenticate API request

Feed publishing

Components:

• Web server: to route to different service (orchestrator) (will need to trigger 3 service at the same time when someone post something), also authenticating, rate limiting if needed
• Fanout service: distribute your post to other feed
• Post service: persist your post in database
• Notification service: push to your friends phone that you posted a new post

Feed building

Components:

• Web server: to route to different service (orchestrator), also authenticating, rate limiting if needed
• New feed service: micro service to handle new feed fetching stuff
• New feed cache: new feed ID to render the new feeds. Note that 1 user has their own cache

Step 3: Design deep dive

Feed publishing

The web server itself has both Rate Limiter and Autonegotation This is more of a lazy design, for actual design we can refer to Design rate limiter where we divide into middle tier.

Note: When submiting to the fanout here is push model. Where we push directly to the user feed (their friend feed). The reason we do this is we need latest information, therefore we can't do pull, we need to do push.

However, when the user is a celebrity with a lot of friends (or followers), we can't push to everyone. As a result, we need to do a pull model for those.

Feed retrieving

We first need to get all the feed for current user first, Each feed would have <post_id, user_id> the user_id here is the user friend.

For each one, we can:

1. Get more detail about the user: i.e user name, profile picture etc from the User cache
2. Get more detail about the post: i.e post content, picture, images from the Post cache

Hybrid Model with Push & Pull

Above model is the push model — we push the content of the feed directly to the user home, the user just go and read it. However for celebrity user (one with 10m+ followers), we can't all push to 10 millions new feed. That's very costly.

The solution is we introduce a pull model. So for celebrity only, we will pull from the celebrity post list itself and append to the current feed instead. This requires us to maintain a user_post_cache[user_id]

Publishing

In here for each fanout service, we also add a post_id in the User Post Cache [user_id]

Retriving

On retrieving, we fetch the user celebrity post and merge with the news feed cache.

• NOTE: it makes no sense to add it back to the news feed cache since it's the same thing to fanout 10M post to followers now but the trigger is on read. Also we always need to refetch the celebrity post cache anyways

Cache architecture

1. New feeds: store the ID of each feed
2. Content:
   1. Hot cache: popular content
      1. We need to separate this out to avoid hot key problem from the main cache
      2. We can spend more ram and computing power on hot cache
      3. Major hits will go to the hot cache, the normal cache is protected
   2. Normal cache: store post data
3. Social graph: store user relationship data, follower and following
4. Actions: liked, replied, others
5. Counters: like counter, reply counter

For caching, we can use Cache aside and Write through > Write through with invalidation

Question

1. What is the read:write ratio
   • We assume read is much heavier than write (100:1) so that we pay the write time cost to make read O(1). Hence there is a worker pull for write
2. Type of database
   • We prioritise availability so we use NoSQL for this
3. How to make the new feed list sorted
   • Use Sorted Set and score by timestamp
4. If there are are 50 celebrity need to pull, what's the solution to optimise:
   • Have a cache just for celebrity post
5. What if your service queue go down?
   1. The queue itself should be highly available (multi-broker cluster like kafka with replication)
   2. Circuit breaker, health check
      1. Circuit breaker detect after 5 timesout cand cant post, Post service should not try to hit the queue anymore it will just save the post metadata and ignore
      2. This will then put in the post metadata is FANOUT_STATUS=SKIPPED
      3. A background service called reconciliation job will then scan the database in last 30 minutes see which one is failure, and then re-queue the missing item.
         1. SELECT * FROM posts WHERE fanout_status = 'SKIPPED' AND created_at > NOW() - INTERVAL '30 min'
   3. Producer side use write a head log, retry with exponential backoff.
   4. Consumer side: messages stay in the queue unacknowledge, auto redeliver
   5. Dead letter Queue after N retry, alerting + manual replay
      1. This store message that cannot retry, it will stay here instead of retrying forever.
      2. We can have some alerting here

Note

Always assume percentage of each tweet:

1. i.e tweet pool is 80% text only, 15% image, 5% video
2. text = 1kb, image = 2mb, video = 15MB
3. 0.8 x 1 + 0.15 x 2 + 0.05 x 15 = ~1MB / Tweet
4. Daily active user x 1MB tweet = storage

How to handle cross-region fanout

1. Tweet persist in the post DB in local region
2. Fanout worker in local region push the post id to sorted set to shard in local region
3. Followers in other region, the event is published to a cross-region replication channel
   1. This can be done through MirrorMaker 2
      1. Basically mirror maker 2 will push it to the replicated channel for us
   2. Worker in US region consume the replicated event and push post id to their local sorted redis

graph LR
  subgraph Asia Region
    PostSvc[Post Service] --> KafkaAsia[Kafka - Asia]
    KafkaAsia --> WorkersAsia[Workers - Asia]
    WorkersAsia -->|local followers| RedisAsia[(Redis - Asia)]
  end
  subgraph Replication Layer
    KafkaAsia -->|MM2 / Cluster Linking| KafkaUS[Kafka - US]
  end
  subgraph US Region
    KafkaUS --> WorkersUS[Workers - US]
    WorkersUS --> RedisUS[(Redis - US)]
  end

How to merge celeb wall with user wall

graph TD
  Client -->|GET /feed?cursor=T| FeedSvc[Feed Service]
  FeedSvc -->|ZREVRANGEBYSCORE| PushFeed[(Redis home:user_id)]
  FeedSvc -->|for each celeb| CelebWalls[(Redis wall:celeb_1..N)]
  PushFeed --> Merge[K-way Merge - heap by timestamp]
  CelebWalls --> Merge
  Merge -->|top 20 post_ids| Hydrate[Batch Hydrate metadata + media]
  Hydrate --> Client

GET /v1/feed?cursor=<timestamp>&limit=20

1. ZREVRANGEBYSCORE home:{user_id} cursor -inf LIMIT 0 20
   → gives you up to 20 post_ids from the precomputed push feed

2. Lookup user's celebrity follow list (cached, small — say 5-30 IDs)
   For each celeb:
     ZREVRANGEBYSCORE wall:{celeb_id} cursor -inf LIMIT 0 20

3. K-way merge (min-heap by timestamp, descending) across:
     - the push feed page
     - each celebrity wall page
   Take top 20 from the merged stream.

4. next_cursor = timestamp of the 20th item returned.

5. Batch-hydrate: post metadata from cache/DB, media URLs from CDN.

6. Return {posts: [...], next_cursor: ...}

Use Merge k Sorted Lists