Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

feed generation:

current approach:
- push based model
- user posts a tweet -> fanout and update every follower's feed asynchronously
other approaches:
- pull based model
- when user requests for their feed -> then their feed cache is updated with the top 50 posts from everyone they are following
- this approach is not chosen because we are prioritising lower read latencies over write latencies. this approach reduces the latencies on the writes when a user posts a tweet but more computation is done when a user requests for their feed
considerations:
- the celebrity problem - where a user with 100m followers post a tweet, we have to update 100m user's feed in the feed cache. This is an expensive operation.
  - this is an accepted trade off if we want to prioritize read latencies to be as low as possible.
  - if we want to balance read and write latencies, we could adopt a hybrid approach where user's feed are maintained with pushed tweets from non-celebrities. but at the time of calling the feed API, it is constructed by pulling the tweets from celebrities. this solution is not accepted because it increases the read latency on retrieving a user's feed.
- since we are using a cache on the feed cache, we will have to set a TTL on the key value. redis need not be big enough to hold the feed of every single user of twitter.
  - each user's feed can be maintained for a week. when user is inactive for a week, their feed is evicted from the cache. this ensures that the cache does not reach max storage capacity.
  - if we notice cache reaching maximum storage space, we can decrease the TTL.
    - each post is 2kb -> 50 posts is 100kb per user -> for 100m active users, thats 10tb of cache size in redis. this can be achieved by horizontally scaling redis to include more nodes in a redis cluster
- on a cache miss, the top 50 posts for the user is retrieved by querying the tweets table. this data is then cached.
  - this will present as a slower operation for user's opening their feed for the first time in the week, but it will be much faster afterwards.
  - a cache failure would mean an empty cache on startup. each user's feed will then be pulled and constructed in cache on demand
  - thundering herd problem is avoided as the feed is constructed on demand when user requests instead of trying to build the feed entirely for all users
- the feed cache uses the userID as key and a doubly linked list as the value.
  - each node in the linked list should contain all the data and metadata needed to construct the tweet in the feed, so that the tweets table need not be queried again during the generation of the feed
- the top 50 posts are ordered based on the requirements of the product - if ranking is needed
  - if it should be shown based on chronological order, a doubly linked list is good to append and pop
  - if it should be shown based on an engagement score, maybe a heap can be used to push and pop from heap based on this score. top 50 posts will then be ordered based on a score rather than time ordered. this scoring model can then be versioned and running offline and the cache is only updated on a TTL or when the model updates.
GET v1/feed will have a query params to include cursor and page to include pagination in the API.
- page 1 will alway retrieve from the feed cache while pages after 1 will require a lookup on tweets table by skipping the number of pages * page size

likes aggregator:

this service will aggregate all the likes in the likes cache but having the <tweetID> as the key and a hash set as the value
- this is done this way as a user can like and unlike a post as many times as they want. so lookups, add and remove are all O(1) time complexities on a hash set.
every few seconds, the aggregator service will retrieve the set of users that like the tweet from the likes cache and the tweets table. it will dedupe the users that like the tweet and persist the entire list of users in the tweets table.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10