Twitter, Lady Gaga and a Telegram channel: fan-out on write, or on read?

01One tweet, a lot of work

It is past midnight, the coffee beside me has gone cold, and I am on the page of Designing Data-Intensive Applications that made me put the book down and stare at the wall. Picture a pop star typing one short tweet and tapping send. For her that is a single action; for the database it is a single row. Then the book does the multiplication: posting a tweet is one write, but delivering it to everyone who follows you can be thirty million writes. This is the first of a series of notes from reading the book (chapter numbers in this series follow the first edition, 2017), and the whole chapter on scalability hides inside that gap.

Picture a town post office in the 1800s. A clerk receives one letter addressed "to all my readers". There are two honest ways to deal with it. Make a hundred copies now and drop one into every reader's pigeonhole, so that anyone who walks in finds their mail waiting. Or pin the single original on the wall and let each reader read it when they come. Neither is wrong. Which one is right depends on how many readers there are and how often they walk in. That sentence is the entire post; the rest is making it precise.

02Load parameters: describe the load before you design

Before choosing how to sort the mail, someone has to count it. Kleppmann's first move is to set aside the question "does it scale?" and ask: scale along which number? He calls these numbers load parameters: requests per second to a web server, the read/write ratio of a database, the number of simultaneously active users, the hit rate of a cache. Every system has its own one or two that decide whether it lives or dies, and the average is often not the one that matters. Sometimes it is the extreme: the handful of accounts that sit far out on the tail.

For Twitter, the book gives two operations. Post tweet: a user publishes a message to their followers, at about 4,600 requests per second on average (peaking above 12,000). Home timeline: a user views the tweets of the people they follow, at about 300,000 requests per second. Those are the book's figures for the era it describes, so treat them as an illustration of the shape, not as today's numbers.

tweets posted (avg)

4.6k/s

home timeline reads

300k/s

more reads than writes

~65×

followers on the biggest accounts

30M+

And here is the first lesson, one that I had to read twice: 4,600 tweets a second is not the hard part. Any decent database shrugs that off. What makes the problem hard is fan-out: each user follows many people, and each user is followed by many people. The term comes from electronics, a gate whose output feeds many inputs. One input in, a crowd out.

03The back-of-the-envelope math

Let me do the arithmetic that convinced me. The book supplies one more number: an average account has about 75 followers. So if every tweet is copied into each follower's personal timeline:

writes into mailboxes  = 4,600 tweets/s x 75 followers
                       = 345,000 writes/s      (same order as the 300k reads/s)

one celebrity tweet    = 30,000,000 followers
                       = 30,000,000 writes for ONE tweet

Two things jump out. First, on average the two sides are of the same order: 345k mailbox writes per second against 300k timeline reads per second. Neither is obviously the one to optimize, which is exactly why the decision is not obvious. Second, averages hide the monster: one account with 30 million followers turns a single tweet into 30 million writes, and those accounts are precisely the ones whose tweets everyone wants to see immediately.

04Two ways to build a timeline

So the arithmetic leaves us with two candidate designs, and they are exact mirror images: one keeps the author cheap and makes every reader pay, the other does the reverse.

Approach 1: assemble at read time

The first design is the one any of us would write on day one: tweets live in one table, and a timeline is a query. When you open the app, the system looks up everyone you follow and merges their recent tweets.

SELECT t.id, t.author_id, t.body, t.created_at
FROM   follows f
JOIN   tweets  t ON t.author_id = f.followee_id
WHERE  f.follower_id = $1            -- me
ORDER  BY t.created_at DESC
LIMIT  50;

Writing is as cheap as it can be: one insert. Reading is where you pay, and you pay at the worst possible moment, while a human is waiting. At 300k opens per second, each touching the recent tweets of ~75 accounts, that is about 22 million tweet lookups per second (300,000 × 75, a rough multiplication of mine, not a figure from the book). According to the book, Twitter's first version worked this way. It is the right design while the product is small and the wrong one once reads dominate.

Approach 2: deliver at write time

The second design flips the cost. Every user gets a personal mailbox, a cache of their home timeline. When someone tweets, the system looks up the author's followers and pushes the tweet into each follower's mailbox. Opening the app is then one cheap read of your own list. The book describes this as the move Twitter made once reads outgrew the join.

// the mailbox holds tweet ids, not tweet bodies (bodies are fetched by id)
async function postTweet(authorId: string, body: string) {
  const tweetId = await db.tweets.insert({ authorId, body });
  const followers = await db.follows.followersOf(authorId);   // ~75 on average

  const pipe = redis.pipeline();
  for (const f of followers) {
    pipe.lpush(timeline:${f}, tweetId);
    pipe.ltrim(timeline:${f}, 0, 799);                      // keep the latest 800
  }
  await pipe.exec();
}

// opening the app: one cheap read
const ids = await redis.lrange(timeline:${me}, 0, 49);

Storing only ids keeps the mailbox small: 800 ids of 8 bytes is about 6.4 KB per user, so a hundred million mailboxes is on the order of 640 GB of RAM (an illustrative figure for the raw ids, assuming that many active users; a real Redis list adds overhead on top). Not free, but a price you can plan for, and it is paid in advance, off the critical path of a human waiting.

05Then Lady Gaga tweets

Approach 2 looks like a clear winner until you reread the arithmetic. The cost of a write is N, the author's follower count, and followers are nothing like evenly spread. Most accounts have a few dozen; a few have tens of millions. When one of those posts, the fan-out service has to do 30 million mailbox writes for a single tweet. The book notes that Twitter tries to deliver a tweet to followers within about five seconds, and at this size that is a serious challenge: the followers at the end of the queue see it late, on the one account everybody refreshes the page for.

06The hybrid: deliver to the door, or pick up at the warehouse

So the celebrity gets the pin-on-the-wall treatment, and everyone else keeps their pigeonholes. When I first read the sentence about the hybrid, I admit I did not follow it, so here it is as a delivery service, which is how it finally clicked for me. Light parcels from ordinary shops are delivered to your door. But a giant supplier ships pallets, and no courier will put one pallet in thirty million houses. So its goods stay in its warehouse, and when you open the app you go and pick up the few pallets you actually ordered.

Why does the pickup stay cheap? Because you follow only a handful of celebrities, however many people follow each of them. Fan-out on write cost scales with followers of the author; fan-out on read cost for this slice scales with celebrities that you follow. A person who follows five stars does five small lookups, not 300,000 reads. The book describes Twitter moving towards exactly this mix of the two approaches.

const CELEB_THRESHOLD = 100_000;   // tuned from data, not a magic number

async function postTweet(authorId: string, body: string) {
  const tweetId = await db.tweets.insert({ authorId, body });
  if (await followerCount(authorId) >= CELEB_THRESHOLD) return;   // stays in the warehouse

  for (const f of await db.follows.followersOf(authorId)) {
    await redis.lpush(timeline:${f}, tweetId);
  }
}

async function homeTimeline(me: string) {
  const pushed = await redis.lrange(timeline:${me}, 0, 49);              // delivered
  const celebs = await db.follows.celebritiesFollowedBy(me);                  // a handful
  const pulled = await db.tweets.latestByAuthors(celebs, 50);                 // picked up
  return mergeByTime(pushed, pulled).slice(0, 50);
}

07500 people in a chat, a million in a channel

Once I trusted this idea, I started testing it on the apps on my phone, and the phone obliged: a Zalo group from my old class was buzzing with reunion photos. Say it has 500 members. Which design? Fan-out on write, and without hesitation: 500 copies is a trivial price, and in return opening the chat is instant, since your messages are already sitting in your own inbox. That matched my instinct. (I am reasoning about the shape of the problem here, not describing how Zalo or Messenger are really built; I do not know their internals.)

Then, thumb still on the screen, I asked myself a nastier question: what about a star's fan room on Instagram, where a singer drops one voice note and millions of fans sit in the same chat? I started to answer "same as the group, a copy per member" and stopped mid-sentence. A copy per member would be millions of writes for every single "good night, everyone". The ground shifted. I was no longer describing a group chat, I was describing a broadcast channel, and I already knew the answer from Twitter. Store a single copy in the channel and let whoever opens the channel pull it. That is fan-out on read, and as far as I understand it, it is how a Telegram channel is organised: one log, many readers (the shape, not a claim about Telegram's internals). I had derived the architecture without noticing, which was a pleasant surprise: the idea transfers because it is about the shape of the load, not about tweets.

08The interview reflex: ask which dimension scales

"Will your system scale?" is a trap if you answer yes or no. Scalability is not a label; it is a conditional: if the load grows this way, here is how we cope. So the senior reflex is to ask back before drawing a single box:

• What is the problem exactly, and which operation is the hot one: reads, writes, or fan-out?
• Which dimension grows: users, requests per second, data volume, followers per account?
• What are the numbers now, and the read/write ratio?
• Is the distribution flat, or is there a heavy tail (the celebrity)?

Those four questions are the load parameters wearing an interview suit. They also tell you which of the three designs above to propose, which is why the interviewer is usually happier with the questions than with a premature answer.

09The mantra

There is no architecture that is right in the abstract. The right one is the one that matches the distribution of your load.

Duy Anh, notes on DDIA chapter 1

• Name the load parameters first: requests per second, read/write ratio, followers per account.
• Fan-out on write when reads dominate and N is small; fan-out on read when N is huge or writes dominate.
• When the distribution has a tail, combine them: deliver light parcels, let the heavy ones wait at the warehouse.
• When asked "will it scale?", ask back: which dimension?

Back at the post office, the clerk with the stack of letters finally has a plan. Letters for the neighbours go into pigeonholes. The one letter half the country wants gets pinned to the wall, and the crowd walks up to read it. Same office, two methods, chosen by the shape of the mail. Next in the series: two people click "buy" on the last concert ticket at the same instant, and the database has to decide who gets it.

Written by Vũ Duy Anh, backend engineer in Hà Nội. Questions or corrections are welcome by email.