Lesson 10.2• 11 min read

Fan-out on write, on read, or both

Push versus pull, the cost of fanning out a celebrity’s tweet, and the hybrid that merges highly followed accounts at read time.

What you will learn

  • Compare fan-out on write (push) with fan-out on read (pull).
  • Explain why highly followed accounts break push.
  • Design the hybrid, and choose where to draw its threshold.

Two ways to build a home timeline

  • Fan-out on write (push): when someone tweets, copy the tweet ID into the cached home timeline of every follower. Reading a timeline is then a single list read.
  • Fan-out on read (pull): store each tweet once. When someone opens their home timeline, read the recent tweets of every account they follow and merge them.

The primer's design pushes. Fanning out to followers runs at 60,000 deliveries per second, which "will overload a traditional relational database". So the home timelines live in a store with fast writes, a memory cache or NoSQL database, while each user's own tweets live in SQL.

When a user posts, the Fan Out Service:

  1. asks the User Graph Service for the user's followers (held in the memory cache);
  2. stores the tweet in each follower's home timeline in the memory cache, an O(n)O(n)what its symbols mean operation for nnwhat its symbols mean followers: "1,000 followers = 1,000 lookups and inserts";
  3. adds the tweet to the Search Index Service, stores media in the Object Store, and queues push notifications.

Reading the home timeline then takes one O(1)O(1)what its symbols mean fetch of tweet and user IDs from the cache, plus two multigets, each one request for many keys, for the tweet and user details.

Push Pull
Work per tweet One insert per follower One insert
Work per timeline read One list read One read per followed account, then a merge
Memory A copy of each tweet ID per follower Each tweet stored once
Breaks down when An author has millions of followers A reader follows many accounts, or reads very often

The celebrity problem

Push costs one insert per follower. The primer warns that users with millions of followers "could take several minutes to have their tweets go through the fanout process". It adds that this "could lead to race conditions with @replies to the tweet": a reply can arrive before the tweet it answers. You can mitigate that by re-ordering tweets at serve time.

Twitter's own figures (2013) show the scale: a median of 3.5 seconds to deliver a tweet to 1 million followers, and up to 5 minutes at the 99th percentile.


The hybrid

The primer's fix: "avoid fanning out tweets from highly-followed users". Instead, find their recent tweets when the timeline is read, merge them with the user's precomputed home timeline, then re-order at serve time. Twitter did the same: "For people like Taylor Swift don't bother with fanout anymore, instead merge in her timeline at read time."

  1. Most authors: fan out on write, usually asynchronously through a queue.
  2. Highly followed authors: skip the fan-out and store the tweet once.
  3. On read: fetch the precomputed timeline, then fetch the recent tweets of the few highly followed accounts the user follows, and merge by time.

Where to draw the line is a design choice, so tune it against measurements. A lower threshold means fewer writes but more merging on every read.

The primer adds more savings:

  • Keep only several hundred tweets per home timeline in the cache.
  • Keep timelines only for active users. For someone inactive for 30 days, rebuild on demand: ask the User Graph Service who they follow, read those tweets from the SQL database and fill the cache.

Push, pull or hybrid fan-out

What one tweet costs to deliver, and what one home timeline costs to read.

Strategy
Timeline inserts for this tweet
25,000
Time to reach every follower
88 ms
Reads per home timeline (reader follows 300)
4

This author is below the threshold, so the tweet is pushed. The reader also merges 3 followed celebrities at read time. Delivery speed assumes about 285,714 inserts per second, from Twitter’s reported median of 3.5 s to reach 1 million followers.

Authors1× instanceReaders1× instanceLoad balancer23× instancesWrite API7× instancesRead API101× instancesMessage broker(fan-out jobs)2× instancesTweets database8× instancesFan-out workers7× instancesHome timeline cache15× instancesUser graph service7× instancesAuthors1× instanceReaders1× instanceLoad balancer23× instancesWrite API7× instancesRead API101× instancesMessage broker(fan-out jobs)2× instancesTweets database8× instancesFan-out workers7× instancesHome timeline cache15× instancesUser graph service7× instances
Figure 2

The hybrid: most tweets are fanned out to followers’ cached timelines through a message broker, and highly followed accounts’ tweets are merged in when a timeline is read.

Follow a tweet. The Write API stores it once in the tweets database. If its author is below the threshold, it also puts a fan-out job on the message broker, and the fan-out workers ask the user graph service for the author’s followers and insert the tweet’s ID into each follower’s home timeline in the cache. A highly followed author’s tweet skips that step. Now follow a read: the Read API fetches the reader’s home timeline from the cache, fetches the recent tweets of the few highly followed accounts the reader follows from the tweets database, and merges the two by time. Counts are sized for the primer’s 6,000 tweets and 100,000 reads a second, each plus one spare: about 1,000 a second per server for the two APIs, the fan-out workers and the user graph service (one job, and one lookup, per tweet), 5,000 per load balancer, and 12,000 per cache node for reads and inserts together. The tweets database is four shards of a leader and a standby, and the broker is one plus a spare.

  • Authors: 1 × Users
  • Readers: 1 × Users
  • Load balancer: 23 × Load balancer
  • Write API: 7 × App server
  • Read API: 101 × App server
  • Message broker (fan-out jobs): 2 × Queue
  • Tweets database: 8 × Relational database
  • Fan-out workers: 7 × App server
  • Home timeline cache: 15 × Cache
  • User graph service: 7 × App server
  • Authors sends requests to Load balancer
  • Readers sends requests to Load balancer
  • Load balancer sends requests to Write API
  • Load balancer sends requests to Read API
  • Write API sends requests to Tweets database
  • Write API sends requests to Message broker (fan-out jobs)
  • Read API sends requests to Home timeline cache
  • Read API sends requests to Tweets database
  • Message broker (fan-out jobs) sends requests to Fan-out workers
  • Fan-out workers sends requests to User graph service
  • Fan-out workers sends requests to Home timeline cache

Key takeaways

  • Push copies each tweet ID into every follower's cached timeline, so a read is one list fetch; pull stores each tweet once and merges at read time.
  • Push costs one insert per follower: 60,000 deliveries a second would overload a relational database, and an account with millions of followers can take minutes to reach them all.
  • The hybrid pushes most tweets, stores highly followed accounts' tweets once, and merges those in when a timeline is read.
  • A lower threshold means fewer writes but more merging on every read; tune it against measurements, and keep timelines only for active users.
Sources3