• **Functional Requirements** - Compose a tweet (up to 140 characters) - Follow/unfollow users - Like tweets - Display tweets from followed users in home feed - Show top K popular tweets based on likes **Non-Functional Requirements** - **High availability** — survives single datacenter failure - **Fast response** — P95 feed load under 1 second - **Scalability** — 100M concurrent readers, 1M writes/sec

Capacity Estimation

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

API Design

POST /api/v1/tweet -> Create a tweet with a payload

GET /api/v1/timeline -> get a list of tweets, paginated

POST /api/v1/tweet/{id}/like -> like a tweet

POST /api/v1/tweet/{id}/unlike -> unlike the tweet

POST /api/v1/user/{id}/follow -> follow the user

POST /api/v1/user/{id}/unfollow -> unfollow the user

High-Level Design

LB: load balancer

TH: Tweet processing handler

US: User service handling user follow / unfollow

LB -> TH -> Kafka -> Write to Tweets DB

LB -> TH -> Kafka -> Update the tweet like count DB by ID

LB -> US -> Kafka -> Update the followers graph

LB -> TH -> Read timeline

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...

Detailed Component Design

The pre-generated list would require an async service that reacts to the arrival of the tweet and does follow lookup and update each follower timeline with the arrival of the tweet.

Each client has a store of all the tweet IDs of people they follow or followed

tweet -> LB -> TH (auth, validation, generate unique ID) -> Q:queue (distributed across datacenters)

Q -> Calculator -> notification for each user about new timeline

Q -> Store the tweet with tweetID, clientID and timestamp

Role of calculator is to

• find all the users that follow the user
• update each of the user's timelines

Calculator is responsible to access the social graph and find all the clients the user has and update the client's timeline with the id of a new tweet

The few design choices

1. I chose to generate the unique id in TH so that all the downstream processes could have a unified knowledge of the tweet. I also wanted to separate the storing of the tweet from calculator to not have to synchronize the two
2. storing the tweet id only saves space and does not require updating the timelines if tweet is deleted

The benefit of pre-calculating is that it simplified the loading of the timeline and reduces the load on the store. There are a magnitude more reads than there are writes

The Drawback of the pre-calculation is

1. more complexity on writes
2. if user has millions of followers, updating each follower becomes a very consuming task. (we might want to set the users with many clients as a special group that timeline pulls from independently, to avoid updating millions of timelines)

Ranking: The tweet ranking model can be done on load of a timeline.

It's hard to re-rank the timelines on every engagement update but easier to do this on load.

When user just first opens the app the fetch of the timeline happens where

the TH gets 500 tweet ids, enriches each one with tweet, runs a ranking algo and returns top 50, the group can be cached in redis or some temporary cache to support scrolling. The client would also subscribe to notifications so when next tweet arrives the client can fetch it and place in the top.

Each of the services is redundant and should handle the spikes.

If TH fails the 500 error is returns

if queue write fails than 501 Bad Gateway is returned

the rest is done async and any delay will be eventually resolved