System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

users on a web/mobile app

Compose tweet

• tweets can be multi-media

View tweets of following users in a timeline

• ordered reverse chronologically
• 
  

"like" a tweet

"follow" another user

users can be across multiple regions

Won't handle notifications just yet

Non-Functional:

List non-functional requirements for the system...

Rendering the timeline should be quick

• doesn't have to be quick for inactive users

"eventually" consistent - likes/follows don't have to be reflected right away

10M DAU

Avg DAU tweets 2x per day

Avg DAU views timeline 5x per day

avg tweet size is 1MB

Capacity estimation

Estimate the scale of the system you are going to design...

1e7 DAU * 2 tweets/users*day * 400 days/yr * 1e6 bytes/tweet -> 8e15 bytes/yr -> 8 PB/yr

1e7 DAU * 5 visited/user*day * 400 days/yr ...

API design

Define what APIs are expected from the system...

Post_tweet(text, media_file)

Like(post_id)

Follow(user_id)

view_timeline()

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

news feed cache: A key-value store, "eventually consistent" (eg: dynamo db)

news feed cache is a mapping of (user_id, post_id)

(with a configurable limit)

Graph database to track followers, so that we can query the followers for a given user:

follower_user_id, following_user_id

Users store - row for each user

relational db table:

id, name, etc

Posts store - stores all tweets, and references to images/videos within each tweet

Relational db table:

id, created_at, user_id

Cloud Blob Storage - stores blobs for images/videos

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

client (web or mobile app)

HTTP API server (behind load balancers)

handle all requests

Posting a new tweet goes to a "posting service"

Once post is created, message is added to our "posts queue" which builds up our news feed cache asynchronously

Posting service:

queries Posts store to insert new posts

Posts Queue: updates our news feeds asynchronously

Fanout workers:

consumes Posts Queue

Newsfeed Cache: new posts are added here, with a cache for each user

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

## Create Post:

from client to api server

-> posting service

-> insert into posts queue

"push based" timeline generation:

fanout worker reads from posts queue

-> fetch all followers for the user

-> optionally filter out "inactive" users

-> add a new entry to each follower's newsfeed cache

"pull based" timeline generation (for users with many followers):

Posts from "celebrity" users don't get added to newsfeed caches. Instead, these posts are fetched on demand

## View Timeline:

from client to api server

fetch the newsfeed cache

pull posts from any "celebrity" users

"hydrate" the newsfeed with all data

• fetch the posts and users from the post_id and user_id in the newsfeed cache mapping
• order reverse chronologically, or other heuristic

return newsfeed from api server to client

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Newsfeed cache:

• Use a configurable limit on the mapping table, to avoid taking up too much space
• Only use newsfeed cache for active users who are following non-celebrity users ("push based" model)
• The KV store leverages read-only replica since this is a read-heavy system
• "strong consistency" / linearizability is not required

Users, Posts, and Followers store:

• leverage caching for lower latency and performance
• leverage read-only replicas - this a read-heavy system
• sharding via consistent hashing
• "strong consistency" / linearizability is not required

API servers:

• multiple replicas behind a LB
• stateless

Posting queue and fanout workers:

• use queue replicas and worker replicas to handle failover
• 
  

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Push vs pull based model:

• pull-based model is better for celebrity users and inactive users
• push-based model is better for everyone else to reduce latency in generating the timeline

Using a KV store for the newsfeed cache:

• reduces latency
• strong consistency is not required

Use a configurable limit on the side of the newsfeed cache:

• most users only look at the most recent posts in their newsfeed, so a couple hundred limit is sufficient
• if they exceed that, we can generate more posts with regular queries

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Rate limiting users with too much activity

• prevent DOS from likes/follows/posts flooding
• token bucket, leaky bucket algorithms for rate limiting

Outages / failover

• consistent hashing on the KV store to distribute load evenly
• elect new leaders when the leader has failed
• use gossip protocol to detect failures
• use membership/coordinate service (eg: zookeeper) vote on proposals when electing new leaders
• use heartbeat to detect failures amongst load balancers

spikes in user activity:

• leverage autoscaling to increase api server replicas, read-replicas, etc during bursty times

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

Support notifications for when a new post is created, or when someone likes your post, etc