Hands-on design challenge

Challenge 10: Home timelines at scale

The situation

On a social network, users read their home timelines far more often than they post, and every timeline is different. Each post belongs in the home timeline of every one of its author's followers. Today each timeline is built from the post store when it is read. Only a user who has been away a long time should ever find no timeline ready.

Traffic

20,000 requests a second. Each write also updates 100 entries in a cache, or in the store when there is no cache. A read that no cache answers takes 10 reads from the store.

OperationShareSteps
Read95%Read data
Write5%Write data
  • Read95%Read data
  • Write5%Write data

Data

A cache answers 99% of the reads that reach it.

What you are proving

Work moved from reads to writes: each timeline is kept ready, so reading it is one lookup, and the cost of copying a post to its readers is paid once, when it is posted.

Rules

  • A CDN cannot answer these reads.Every home timeline is different, so no two users get the same response.
  • Every post is kept in the post store.A timeline that is lost with a cache node, or was never kept for a user who was away, is rebuilt from it.

Builds on

Further reading: System Design Interview, volume 1, chapter 11.

Targets

  • Serve all 20,000 requests a second
  • At least 99.99% available, with no single point of failure
  • At most 5,000 USD a month
  • Any tier loses one instance: nothing dropped, no tier over 80% busy

Hints