FB Newfeeds

Functional requirements

Core requirement

1. User should be able to create posts
2. Users should be able to friend/follow people
3. Users should be able to page through their feed
4. Users should be able to page through the feed

Out of scope:

1. Users should be able to like and comment on posts
2. Posts can be private or have restricted visibility

Non-functional requirement

Core requirement

1. System should be high available, post visible < 1 min of eventually consistent
2. Posting and viewing feed should be fast < 500ms
3. Should be able to handle up to 2B users
4. User can follow unlimited number of users, the user can be followed by unlimited amount of users

Core identity

1. User: User in our system
2. Follow: link between user and follower
3. Post: Post make by user

API

User can create a post

POST /v1/posts
{
    "content": {}
} -> { "postId": "" }

User can follow

PUT /v1/users/:userId/follow  
{ } -> 200 ok

We choose PUT here for Idempotent, if the user follow twice it's unchange. The platform auto parse the user id from header and use that to initate a follow. For unfollow it's out of scope.

User can see the post feed

GET /v1/feed?pageSize={size}&cursor={timestamp?} 
{
    items: Post[],
    nextCursor: string
}

Our requirement is to return posts in chronological order so we have the timestamp here

[!important]
For senior candidate, you need to make sure you know which important part to spend time on. If it's non important just say "I'll come back to this when we have time"

High level design

User should be able to create posts

Post service will be behind a load balancer which allow us to horizontally scale out if need to. We will not have cache layer here yet and leavign the caching for later.

Post by the user is written straight to the meta database. In here we would choose DynamoDB because it allow us to provision with extreme high throughput.

[!note]
Dynamodb manage capacity across many machines, it's easier to provision a high throughput by adding more shard

User should be able to follow other users

From this case, let's avoid Graph Database since our use cases is simple enough and can be done using another table. If we bring graph database we might got asked how we are gonna scale Neo4J which might be tricky if we're not familiar with the technology

In here we want to create a Follow table which has

• userId: the current user id (primary key)
• follow_user_id: the user id that this user_id follows (sort key)

The reason we create a sort key here is to quickly check if userA is following userB.

How do we check if userB is followed by userA quickly? In this case, we need to create a DynamoDB Global Secondary Index (GSI) which works similar to a Database index (Secondary Key). This will allow us to do a reverse lookup:

• follow_user_id: the current user id (primary key)
• user_id: the user id that folows this follow_user_id follows (sort key)

Now we can answer quickly the question "is userB followed by userA?" quickly.

NOTE If you're using postgres, we can create an index on compound key

create index follow_user_id on follow (follow_user_id, user_id)

Use should be able to view feed of posts from people they know

We will go with the following

1. User find the followers that they followed using the Follow GSI.
2. User find all the post by that user using Post GSI
   • Post GSI have the creator id that would link back to the Post and the createdAt sort key allow us to find the post at anytime for the user
3. We sort all the post in the right timestamp and return back to the user

Now this would not be ideal since the user could follow millions of other people and it will be a time consuming process.

However, in the interview, says I will start with an inefficeint solution and solve the scaling problem separately. It's important to move quickly and at least have a full complete design

Users should be able to page through their feed

To do this, we need the timestamp of the last post user is seeing and only show the post that's older than that. We already have all the infras to do so

1. User get all the given users they're following using Follow table
2. User get all the posts from those users thats older than the input timestamp using Post GSI
3. We sort all the posts by time and return back to the user

Deep dive

1) How do we handle users who are following large number of users

The current flow of viewing feed is

1. Find all the follower for current user
2. Find all the post by each follower
3. Sort them and return back

This is creating a fanout on read problem — 1 follower leads to a fanout of request that need to fetch each post. This is very in efficient.

Since our application is mostly read we need to use fanout on write which will write O(n) to make read O(1)

1. When creating a post, for each of the follower of current user, add to PrecomputedFeed table the following records:
   1. userId: the user that follows us (Primary key)
   2. postId: our post id
   3. createdAt: timestamp of post id (Sort key)
2. Our follower online and query the PrecomputedFeed for their userId at timestamp. Getting all the postId necessary

[!note]
In actual social media product like Facebook, they do have a max number of friends (5000). So it's realistic to ask interviewer can the product have the upper limit of this

For this PrecomputedFeed, we can keep the maximum limit of 200 or something to avoid it keep growing. If the user scroll past to 200 most of the social media will say "sorry that's all your feed for today" — normally no one get past 200, however if someone does, we can fall back to our naive approach to do a manual query.

Assume a postId is 10b, storing 200 is 2KB per user. If we have 2billion user it will be 4.000.000.000 KB = 4 TB for the whole table, is reasonable.

What if the user has large number of followers?

If an user with million of followers, one new post would go to that million user, that would be very slow. In order to do this, we need to support hybrid workers.

• For normal post with 0 - hundred thousands of follower, put the post to a queue where async worker can work on building the PrecomputedFeed
• For post with millions of user, have a flag (precomputed) on the Follow table to not not precompute and instead the user need to come and fetch directly from their wall — this will avoid flood our worker with millions of tasks!
• Feed service will query the Follow table to manually fetch the user precomputed flag = False and append it on top of the PrecomputedFeed

How do we scale post reads

DynamoDB has good through put but with 1 condition — the throughput needs to be distributed evenly. In the case where we have 1 popular post, it will go into 1 shard and DynamoDB would have a problem.

In this case, we need to introduce cache layer to help us. However the important is how do we cache?

If our cache shard by the post id, we would have the same problem as well.

The solution is to duplicate the same popular post across all shard, and load balance the shard. This will avoid 1 shard gets heated

Yes we might have more cache miss, for example here we have 3 shard, if the first shard get populate the post, the 2 or third might still have cache miss until they get populated. However this one saves us when millions of request comes at once.

For the cache itself, we can use LRUCache for eviction and Cache aside. The cache is very rare change so we have a long TTL. If the post has been edit, we can invalidate the cache.

Final design