Design a Twitter Feed

Fan-out on write against fan-out on read, why celebrities break the first one, and the hybrid real systems settle on.

SyntaxZADD tl:{userId} {snowflakeId} {snowflakeId} / ZREVRANGEBYSCORE tl:{userId} +inf -inf LIMIT 0 20

A home timeline is the merge of posts from everyone a user follows, newest first. The only real question is when that merge happens: at write time, at read time, or both.

Fan-out on write

When someone posts, append the post id to a materialised timeline per follower, held in a cache. A read is then one range query against one key, which is why it is the default for a read-heavy feed. Twitter described exactly this in Timelines at Scale: home timelines live in Redis and are capped at 800 entries, with older pages served from a slower path. The cost is write amplification — one post by an account with N followers is N cache writes — and it is spent on followers who may never log in, which is why Twitter skipped inactive users during fan-out.

Fan-out on read

The opposite: store posts once, and at read time fetch the recent posts of every followed account and merge them. Writes become trivial, reads become a scatter-gather over hundreds of keys, and the tail latency is set by the slowest shard. Fine for a user who follows thirty accounts, unusable for one who follows five thousand.

The hybrid

Fan out on write for ordinary accounts, and exclude accounts above a follower threshold — around ten thousand in Twitter's public account of the design — from fan-out entirely. Their posts are fetched and merged into the timeline at read time, so one post by a popular account costs a handful of writes instead of millions.

What trips people up

Merging two sources needs a globally sortable id, not a wall-clock timestamp, or posts interleave wrongly across shards.

Example

Example · javascript
// Fan-out worker. Runs off a queue, never inside the user's POST request.
const FANOUT_THRESHOLD = 10_000;  // above this, the read path merges instead
const TIMELINE_CAP = 800;         // the cap Twitter used for home timelines

async function onPost(post) {
  // 1. Durable store first. Timelines below are a derived cache.
  await postStore.put(post);

  // 2. Popular accounts are not fanned out at all.
  const followers = await graph.followerCount(post.authorId);
  if (followers > FANOUT_THRESHOLD) {
    await celebrityIndex.add(post.authorId, post.id); // read path picks it up
    return;
  }

  // 3. Everyone else: push the id into each follower's timeline. Only
  //    followers seen recently are worth the write.
  for await (const batch of graph.activeFollowers(post.authorId, {
    batchSize: 1000,
    activeSince: Date.now() - 30 * 86_400_000,
  })) {
    const pipe = redis.pipeline();     // one round trip per 1000 followers
    for (const followerId of batch) {
      const key = `tl:${followerId}`;
      // Snowflake ids are time-ordered, so the id doubles as the sort score.
      pipe.zadd(key, post.id, post.id);
      // Trim to the newest TIMELINE_CAP entries; scores ascend, so drop the head.
      pipe.zremrangebyrank(key, 0, -(TIMELINE_CAP + 1));
      pipe.expire(key, 14 * 86_400);   // dormant users' timelines cost nothing
    }
    await pipe.exec();
  }
}

When to use it

  • Serving a home timeline in one cache read instead of a scatter-gather over every followed account.
  • Stopping a single post by an account with ten million followers from saturating the fan-out tier.
  • Backfilling the first page of a timeline the moment a user follows someone new.
  • Merging two differently-sharded sources into one correctly ordered page using sortable ids.

More examples

The hybrid read path

Shows the merge that makes the threshold workable: a range read of the materialised timeline, plus a bounded fetch for the handful of popular accounts this user follows. Reach for this once a single account's follower count can no longer be fanned out inside your write budget.

Example · javascript
async function homeTimeline(userId, limit = 20) {
  const [materialised, celebs] = await Promise.all([
    // Pre-merged portion: one range read, already in score order.
    redis.zrevrange(`tl:${userId}`, 0, limit * 2 - 1),
    // The few followed accounts that were excluded from fan-out.
    graph.followedCelebrities(userId),
  ]);

  // Read-time fan-out, but only over a short list - this is why the
  // threshold exists at all.
  const celebIds = (
    await Promise.all(celebs.map(id => celebrityIndex.recent(id, limit)))
  ).flat();

  // Merge on the id itself. A wall-clock timestamp from the writing host
  // would interleave wrongly; a Snowflake id is monotonic by construction.
  const ids = [...new Set([...materialised, ...celebIds])]
    .map(BigInt)
    .sort((a, b) => (a < b ? 1 : a > b ? -1 : 0))
    .slice(0, limit);

  // Hydrate in one batch. Deleted posts come back missing, not as an error.
  const posts = await postStore.mget(ids.map(String));
  return posts.filter(Boolean);
}

Backfilling a timeline on follow

Fan-out on write leaves a hole: a brand-new follow has no entries from that account. Backfill a bounded slice at follow time instead of rebuilding the whole timeline, and reach for this whenever the materialised timeline is the only read path.

Example · javascript
// Following someone must not wait on a full timeline rebuild. Insert a small
// recent slice synchronously and let the normal fan-out handle everything new.
async function follow(userId, targetId) {
  await graph.addEdge(userId, targetId);

  const followers = await graph.followerCount(targetId);
  // Popular accounts are read-merged, so there is nothing to backfill.
  if (followers > FANOUT_THRESHOLD) return;

  const recent = await postStore.recentByAuthor(targetId, 50);
  if (recent.length === 0) return;

  const key = `tl:${userId}`;
  const pipe = redis.pipeline();
  for (const p of recent) pipe.zadd(key, p.id, p.id);
  pipe.zremrangebyrank(key, 0, -(TIMELINE_CAP + 1));
  await pipe.exec();
}

// Unfollow does the mirror image, lazily: filtering at read time is cheaper
// than a ZREM per post, and the entries fall out of the 800-entry cap anyway.
async function unfollow(userId, targetId) {
  await graph.removeEdge(userId, targetId);
  await redis.del(`tl:${userId}:filtered`); // drop any cached filtered view
}

Bounding fan-out cost before accepting the write

Makes the write budget explicit: the publish request returns as soon as the post is durable, and the fan-out cost is estimated so a single post can never queue millions of cache writes. Use this when a viral account would otherwise saturate the fan-out tier and delay every other user's timeline.

Example · javascript
// POST /posts. The user's request is bounded: durable write plus one enqueue.
app.post("/posts", async (req, res) => {
  const { text } = req.body;
  const id = snowflake.next();           // time-sortable, 64-bit
  const post = { id, authorId: req.userId, text, createdAt: Date.now() };

  await postStore.put(post);             // durable before anything derived

  const followers = await graph.followerCount(req.userId);
  await fanoutQueue.send({
    postId: String(id),
    // The worker re-reads the count, but carrying it lets the queue route
    // large jobs to a separate pool so they cannot head-of-line block
    // ordinary posts.
    priority: followers > FANOUT_THRESHOLD ? "celebrity" : "standard",
  });

  // 201 now; the post is visible on the author's own profile immediately and
  // in followers' timelines within seconds.
  res.status(201).json({ id: String(id) });
});

Related

sd design newsfeed rankingsd design instagramsd hot keyssd design unique idsd denormalisation

Discussion

  • Be the first to comment on this lesson.