System requirements

Functional:

1. User can post a tweet (less than 100 characters)
2. User can follow other users to see their tweets
3. User can search a single user's tweet
4. User can search tweets by text

Non-Functional:

1. Latency - user should be able to view their timeline in less than one second.
2. Availability - after a tweet is created, they should be visible to all other users in seconds.
3. Scalability - the system should handle growth in number of users and tweets
4. Durability - once stored, user tweets is not lost

Capacity estimation

Assume there are 1 million daily active user. Each one of them post a tweet daily on average. A tweet object is about 200B. Every day, we're storing 200MB of data without compression. That's 73GB over 5 years.

On the user side, each object is less than 100B. This is about 100MB total. If we forecast growth to 1billion user, this is still 100GB data. In addition, there is followership entity. It would follow a power-law distribution: some power user are super connected, while most are not. We can assume there are 10 followers on average per user. That's 10 million followings. So about 100MB.

To estimate request rate, we previously had 1 million write requests per day. That's about 11 requests/s on average. This is not a big number, even if we account it to be coming during active hours and not evenly over 24 hours. The factor to consider here is fanout and we will discuss it next during read.

For read, the most important piece is timeline. It requires reading tweets from followed users. One strategy which won't scale well is to join on request. If a user followed 10 users on average, this would mean it joins 10 times. It will create 10x load on the database. And for some power user it may be 1000x.

The alternative would be a early push strategy - write to users who followed this user. This will on average create 10 times more write, but read will be much simpler. The caveat is we have a variable number of followed user (in a power law distribution). So it would have a high write latency. Standard technique is to use a message queue for processing. The other aspect is that it will also increase storage cost by 10x if we all write it onto disk. We can consider storing recent timeline in cache so that storage is minimized but cache would contain the replicated version of timeline per user.

To estimate the cache size, it is about 200MB of data for new tweets per day. Suppose we replicate each tweet 10 times, and store only most recent 30 days. It would cost 60GB of memory. You can support this with redis or memcache.

API design

1. POST /tweet should authenticate the user and post tweet content under that user.
2. GET /tweet should show the recent tweets from a specific user. It would also support pagination.
3. DELETE /tweet should accept user id and tweet id to facilitate deletion.
4. GET /followed_tweets should show relevant tweets to the user who followed other users. It is a mix of recent tweets from followed user by the user.So to support timeline, it would be paginated calls to GET tweet endpoint. A user can submit new tweet via POST tweet; or remove his old tweets via DELETE.

Database design

Two entity: User and Tweet.

User:

• id primary key
• username
• email

Tweet:

• id primary key
• user_id foreign key
• content
• created_at

Follow:

1. follower_id
2. followed_id

To view a user timeline, a query will join the followed_id and show the top N recent tweet. To support text search, we can build a full text search index on tweet. This is typically done by having an inverted index on doc list and doc ids.

High-level design

We will have a API layer, a cache layer, and a database layer.

The API will receive read and write requests from users or clients. On read, it will read the cache layer for particular tweet or a whole timeline. On write, it will send write request to a message queue, which will be handled by storing the tweet into database and propagating it to the cache layer.

The cache layer is a distributed cache layer. It supports appending tweets to followed user. When data is not in cache, it is responsible to fetch from the database. It will keep recent tweets in cache and expired in LRU manner.

The database will be a relational database with tables specified in the database section. The user table can be sharded by user id and the tweet table sharded by tweet id. The follower table can be a child table of the user table.

Request flows

In this diagram:

1. The user sends a POST request to the API to create a new tweet.
2. The API server saves the tweet in the database and confirms the action.
3. When the user requests followed tweets, the API retrieves the relevant tweets from the database and returns them to the user.

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

Trade offs/Tech choices

1. I would use redis as node in the cache layer. It is more extensible than memcached.
2. I would use a distributed database to not worry about manual sharding or other operations.
3. 
   

Failure scenarios/bottlenecks

1. Monitoring and alert. We must have appropriate monitoring and alert in place to keep the system up and running. As a start, we can monitor request sucessful and failure rate, latency, cpu and memory usage; also utilize health check and watch in the background. We may even consider having canary test in the production.
2. Failure in cache layer is very important. If the layer failed, traffic will hit database layer and potentially cause a cascading failure. To guard against this, we can introduce redundancy and availability in the cache layer. i.e. having more than one node stores the timeline of a user. They do not need to have same data. In fact, this will be good product experience since user can see variations of their timeline when they refresh.
3. Rate limiting. We must rate limit in the api layer to prevent abuse. It is also important to have rate limit in the database layer to prevent overload, such as when the caching layer fails or is requesting too much data due to logical bugs.
4. Monitor database. Watch out for volume, request rate, and locks contention etc.

Future improvements

1. More details on full text search and async write.