System requirements

Functional:

User can tweet (send) up to 140 character message.

User can follow other users.

User can like other users' tweets.

User's home feed will show tweets from the users they are following.

The home feed will show top K popular tweets, based on the number of likes they receive, and the number of the followers the author has.

Non-Functional:

Scalability. It will have to serve a very large population, e.g., 500M DAU.

Response time. User has to see tweets quickly. When user opens home feed, the first 10 tweets should show up within 500ms.

Availability.

Consistency requirement can be a little bit relaxed. It does not require strong consistency like banking transactions. Eventual consistency would suffice.

For example, if a user tweets something. If a user in the same geographic region sees the tweet in 1 second, and another user on the other side of the earth sees it after 30 seconds, that would be acceptable.

Security, content moderation, and anti abuse protection are all important, but I will not focus on them in this exercise due to lack of time. I will come back to them if I have time.

Capacity estimation

500M DAU

Each user, on average, tweets twice a day. 1B tweets / day.

Each user, on average, views 100 tweets a day.

At peak, the system should scale up to 20% of DAU - 100M users - interacting with the system.

I will think about storage capacity first.

1B tweets a day. Each tweet is 140 chars. Considering international encoding and metadata, it seems reasonable to assume each message takes up to 512 bytes.

140 characters of text

• In UTF-8, some characters (e.g. emojis or non-Latin scripts) can cost up to 4 bytes each, so in the absolute worst case 140 × 4 = 560 bytes.
• Most tweets are predominantly ASCII (1 byte/char), so the average text payload is much smaller (often ≲140 bytes), but we need headroom.

Metadata overhead

• Tweet ID (8 bytes), author ID (8 bytes), timestamp (8 bytes)
• Flags/booleans (reply, retweet, quote, etc.)
• Pointers to attachments or media URLs (even if stored elsewhere)
• Any indexing or storage‐engine framing (length prefixes, checksums, alignment padding)

So this data increases by 512GB every day. In two years, it would be 365 TB.

This goes beyond the typical capacity of RDB. So we'll pick a NoSQL DB.

A document based NoSQL DB, e.g., MongoDB, seems like a good candidate. it is more scalable than RDBs. It has schema flexibility, which allows future enhancements of the application.

The data model would look something like:

Tweet document:

• tweet_ID: primary key
• created_by: user ID
• posted_time
• content
• medialink: link to picture or video content
• number_of_likes
• hashtags: list of hashtag strings used in the tweet.
• users_mentioned: list of users mentioned in the tweet

In MongoDB, every document must have an _id field that serves as its primary key.

If you don’t explicitly include one, the server will silently add auto-generated unique ID.

User:

• user_ID: primary key
• email
• name
• nickname
• date of birth
• gender

Bottleneck analysis:

1 - In this data model, number_of_likes seems to be a challenge to me. If a famous person posts something, and millions of users click "Like" button within one minute, it would overwhelm this document of this database.

One approach to overcome this is to break up this into multiple (let's say 100) sub-counters, and make different DB nodes be responsible for each sub-counter. I will come back to this if I have time.

2 - Another important bottleneck is when a user with millions of followers (e.g. famous people) tweets something, the tweet should show up on million of users' home feed. I will look into this deeper in DB design section.

They should also receive notifications, but I will punt notifications in this particular exercise.

I will consider concurrency in later sections: millions of users viewing the same message concurrently, tweeting messages with the same hash tag, etc.

API design

tweet ( user_ID, content )

User represented by user_ID tweets this content.

The content will be parsed by the server side for users and hashtags mentioned.

follow ( follower, followed )

User represented by follower user ID will follow user represented by followed user ID.

like ( user_ID, tweet_ID )

User represented by the user_ID likes the tweet represented by tweet_ID.

home_feed ( user_ID, offset, number )

Returns JSON document containing tweets that should be shown on the user's home feed.

offset represents where in the list of top tweets it should start from.

number represents the number of tweets this API requests.

For example, when a user first opens their home feed, it would be from offset 0. It is important for this API to respond quickly, so it would be advisable to keep number relatively small - for instance, 5 or 10 for a mobile app client. After the initial 5 or 10 tweets are shown to the user, the client can request more, potentially in the background, to prepare for more feeds in case user scrolls the home feed.

Error handling would follow HTTP error code.

For example, 4XX for client side error (e.g. liking a tweet ID that does not exist), 5XX for server side error (e.g. bug causing some of the APIs to fail). It would be important for client to handle too many requests error (429) correctly. For example, if home_feed() API returns 429, it would indicate the servers are too busy to service this potentially expensive call. Therefore, it would be advisable for the client to want for some time (say seconds) before calling this again.

Future direction: for a more dynamic content update (e.g. home feed), it might be helpful to consider a WebSocket based API for the client to receive real time update from the service. I will not focus on this for now, but may come back if I have time.

Database design

I chose MongoDB as the main database for its scalability and schema flexibility.

These are the data models.

Tweet:

• tweet_ID: primary key
• created_by: user ID, index
• posted_time: index
• content
• medialink: link to picture or video content
• number_of_likes

User:

• user_ID: primary key
• email: index
• name
• nickname
• DOB
• gender: index

Hashtag:

• hashtag_ID: primary key
• hashtag: the hashtag string
• tweets: tweet_IDs who have this hashtag.

UserMentioned:

• user_ID: the user that is mentioned
• array of tweet_ID: the tweets that mentions the user

I decided to take Hashtag is a separate document from Tweet document because the main functionality we want to implement efficiently is the mapping from hash tag to tweets (e.g. to display tags with this hash tag), instead of the other way around.

I decided to create UserMentioned document, which stores tweet IDs that mention a user, separate from the User document. A user (e.g. a famous person) can be mentioned by many tweets in a short amount of time. If I store the mentions in the User document, we would have to load and save the User document every single time. That seems redundant.

User.number_of_likes would have a scalability challenge. When a famous person tweets, it'd be possible millions of users would press the Like button. This would create the Tweet document a hot spot. To avoid this, I would create a sharded counter service for users with more than, e.g., 1,000 followers. For such users, the sharded counter service would do the counting, using multiple (let's say 100) subcounters, stored in a high performance key-value store like Redis Cache. Once in a while (say every 5 minutes or so), the service would write the number_of_likes in Tweet document.

tweeter create 100 shard keys for each sub-counter,

the Redis Cluster automatically assign each key to different Redis servers (nodes)

Follows:

• follower: user_ID of the user who is following
• followed: user_ID of the user being followed
• timestamp

Follows document borrows a concept of normalization from RDB. By having this document separated from User document, we can query the follows relationship in both ways efficiently:

(1) given a user, list all the users they are following,

(2) given a user, list all the users who are following them.

High-level design

CDN would be important to cache static contents that are written once and read many times. For example, images and videos posted by a user.

Rate Limiter protects all the backend servers from Denial of Service attack, intentional or unintentional.

Tweet Service's job is to receive new tweets from the client. It saves them in Tweet DB. It also creates a message in Message Queue, which initiates some async actions.

Tweet Analyzer pulls a message from the Message Queue. It analyzes the tweet and takes appropriate actions, e.g., extract hashtags and user mentions and update appropriate database. We would need another, similar service for content filtering.

Home Feed service constructs a list of tweets that are recommended for the user, and returns the list in JSON format.

I expect creating and viewing would show strong locality. For example, a tweet in Japanese language, made by a user in Japan, would be viewed mostly from Japan region. For this reason, it would be beneficial in terms of scalability to shard data and store them at an appropriate datacenter. Sharing by user ID seems reasonable.

Data should be replicated among data centers, too, for greater fault tolerance.

Every time someone hits “Like” (or “Unlike”), it’s your Like API (aka the “Sharded Counter” service) that actually does the INCR/DECR on Redis.

• Client calls your POST /tweets/{id}/like endpoint.
• Your Like‐handler picks a random shard key (likes:<tweetId>:shard:<0–99>) and does INCR (or DECR) against that Redis key right then and there.
• Response goes back to the client immediately.

Request flows

Detailed component design

Home Feed Service essentially recommends K most interesting tweets for a given user.

Score of Tweet = weight_like * number_of_likes + weight_followers * number of followers on the tweet's author + weight_retweet * number_of_retweets

Home Feed Service would implement top-k algorithm based on a heap data structure, which is a tree which can be used to guarantee that the root item has the highest score.

Home Feed Service would compute top K tweets for a given user, and stores them in cache. Since the recommendation changes in real time, the main storage for the recommendation (list of tweets) should be cache (instead of a database). Redis Cache can persist the data in a file, if it is desirable.

The “Min-Heap” Approach (O(N log k))

1. Create an empty min-heap (priority queue) of capacity k.
2. Iterate over each tweet (score_i, tweet_i) in your candidate set:
   • If the heap has fewer than k items, push (score_i, tweet_i).
   • Else, compare score_i to the heap’s root (the smallest in the heap this is why called Min-Heap):
   • Every peek() or pop() gives you the current minimum among whatever’s in the heap.
     • If score_i ≤ root_score → skip (it’s not in the top k).
     • If score_i > root_score → pop the root and push (score_i, tweet_i).
3. When you’ve seen all N tweets, the heap contains exactly the top k by score.
4. (Optional): Pop the heap into a list and reverse it if you need descending order.

• Time complexity:
  • Building/updating the heap takes O(log k) per item → O(N log k) total.
• Space complexity: O(k) for the heap.

Trade offs/Tech choices

Database choice for this service is an interesting decision.

If I picked RDB for tweets, it would give us strong consistency. However, it would struggle to scale in terms of size (estimated to be 365TB in two years).

If I picked a wide-column database like Cassandra, scalability would even be better than MongoDB. However, the schema would be rigid, making feature enhancements difficult.

MongoDB strikes the right balance - advantage in scalability and performance over RDB, while maintaining advantage such as schema flexibility and normalization than wide column DB.

1. What does “wide-column” mean?

• A table model where each partition (think “big row”) can hold an arbitrarily large number of columns—far more than the dozen or so you’d predefine in a relational table.
• Columns are grouped into families and stored column-family–wise for efficient reads/writes of subsets of data.

2. Can you show a Cassandra example?

• Wide-row for timelines:

• • user_timeline is the column family
  • The individual fields—user_id, posted_time, tweet_id, content—are the columns within that family.
  • Every new tweet becomes a new clustering entry under the same user_id partition, making that partition arbitrarily “wide.”
  • You declared PRIMARY KEY (user_id, posted_time).
  • user_id is the partition key. All tweets with the same user_id go into one partition.
  • posted_time is your clustering column. It determines the sort order and uniqueness within that partition.

• Dynamic columns via a map:

• user_id text PRIMARY KEY, ←─ inline shorthand for “PRIMARY KEY (user_id)”
• user_id is the only element of the primary key (no clustering columns), so every user gets exactly one row.
• In above user_timeline you needed a composite key (user_id, posted_time) because each user has many tweets (one row per timestamp).
• You can tack on new key/value pairs without altering the table schema.

3. What does the table “look like”?

• Tabular view hides the wide-column magic: rows share the same columns but are grouped into partitions by user_id, and within each partition you store as many clustering entries (posted_time, tweet_id, content) as needed—read with one partition read.

4. Why is it “wide” vs. a relational table?

• In Cassandra a single user_id partition is stored as one contiguous, on-disk structure that can contain thousands of tweets (clustering entries).
• In a relational DB, each tweet would be a separate row scattered across pages; here they’re co-located in one “wide” partition.

5. What is CQL?

• Cassandra Query Language, a SQL-inspired language for creating keyspaces/tables, inserting, updating, and querying data with explicit partition keys and clustering columns instead of joins or subqueries.

6. Why is Cassandra’s schema more rigid than MongoDB?

• Cassandra: even though you can tuck arbitrary key→value pairs into a map<…> column, you still must define that map (and every other column) up front, and your primary-key layout is fixed at table creation.
• MongoDB, by contrast, lets each document evolve its own shape on the fly, with zero DDL.

Fixed “envelope”

• Cassandra: You must declare up-front every top-level column (including the attributes map itself).
• MongoDB: You don’t even declare your top-level fields—any document can have any shape, anytime.

Limited typing

• Cassandra maps: All map values share one CQL type (e.g. text) and you can’t nest maps or arrays of mixed types as flexibly.
• MongoDB documents: You can mix numbers, strings, objects, arrays, nested arbitrarily, per document.

Immutable primary key design

• In Cassandra your partition and clustering keys are set once at table creation and can’t be changed without a full ALTER TABLE and data rewrite.
• MongoDB lets you shard on new fields or index new paths at any time without touching existing documents.

Failure scenarios/bottlenecks

Scalability challenge scenario 1 - If a famous person posts something, and millions of users click "Like" button within one minute, it would overwhelm this document of this database. I introduced Sharded Counter service, which uses multiple sub-counters to count likes (and dislikes) in a scalable fashion, and writes the aggregated number to the DB.

Scalability challenge scenario 2 - when a user with millions of followers (e.g. famous people) tweets something, the tweet should show up on million of users' home feed. Tweet Analyzer may overwhelm the DB if it naively tries to write into millions of documents in the DB. It may be better to create a new document that stores recent tweets from famous people. Home Feed Service can pull information from this document and synthesize the information into the tweets list it returns to the client.

Future improvements

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