Fan-out: on write vs on read

Fan-out on write is conceptually the simplest feed architecture: when a user publishes a post, a background worker iterates over their follower list and inserts the post identifier into each follower's inbox. The inbox is almost always a Redis sorted set (ZSET) keyed by the follower's user id, with the post timestamp (or a snowflake id) as the score. The ZADD command is O(log N) per member where N is the inbox size, and since we bound inboxes to ~800 entries, each write is effectively O(1).

The write path looks like this: the post service persists the post to the posts database, then enqueues a fan-out task. The fan-out worker reads the author's follower list (paginated, from a follow-graph service), pipelines batches of ZADD commands to the inbox Redis cluster, and after each batch calls ZREMRANGEBYRANK to trim the inbox to its maximum size. A Redis pipeline of 50 ZADDs completes in under 1ms on a local cluster, so fanning out to 10,000 followers takes ~200ms — fast enough to feel real-time.

This is essentially what Twitter used before 2012. Every tweet triggered a fan-out to every follower's inbox. For the median user with ~200 followers, this was perfect — 200 writes per tweet, amortised across a fleet of fan-out workers, with sub-second delivery. Feed reads were a single ZREVRANGE call returning the top 50 post ids, followed by a multi-get to hydrate the post objects. Total read latency: ~5ms.

The model breaks catastrophically on celebrity posts. When Justin Bieber tweets to 100M+ followers, the fan-out queue receives a task that expands to 100 million ZADD operations. Even at 100K writes/second per worker, that's 1,000 seconds of fan-out time from a single tweet. During that window, the fan-out queue backs up, other users' tweets are delayed, and followers see stale feeds. This is the "celebrity post storm" — the defining failure mode of pure push.

There's a subtler problem too: wasted storage. In any social network, a large fraction of accounts are inactive — they signed up, followed some people, and never came back. Pure push writes into their inboxes anyway. At Twitter's scale, inactive-user inbox writes consumed a significant fraction of Redis memory for content no one would ever read.

Despite these limitations, pure push remains the right answer for bounded fan-out scenarios: team activity feeds (Slack channels, GitHub repo watchers), notification delivery to device tokens (where the fan-out is from event to registered devices), and any system where the maximum follower count is architecturally bounded.

Fan-out on read inverts the cost structure: writes are O(1) — the author appends a post to their own timeline — and reads pay the aggregation cost. When a reader opens their feed, the feed service looks up the reader's follow list, fetches the last N posts from each followed account's timeline, merges them into a single sorted stream, and returns the top page.

The merge operation is a classic K-way merge. You have K sorted streams (one per followed account), each producing posts in reverse-chronological order. A min-heap of size K lets you extract the global top-N in O(N log K) time. In practice, K is the number of accounts the reader follows — for a typical user following 200 accounts, this means a heap of 200 entries and ~50 extractMin operations to fill a page.

This was Facebook's early approach (before the shift to algorithmic ranking): at news feed render time, pull the latest posts from each friend's wall, merge, and display. For the median user with ~150 friends, this was manageable. But the p99 user follows 2,000+ accounts, and the feed service must issue 2,000 parallel timeline reads, wait for the slowest one, then merge. Even with aggressive caching (each timeline cached in memcached with a 60-second TTL), the tail latency was painful.

The deeper problem is cache efficiency. In a push model, the inbox is a single hot key per user — extremely cache-friendly. In a pull model, each followed account's timeline is a separate cache entry, and the hit rate depends on how many other readers are also following that account. Celebrity timelines are hot (millions of readers pull them) and stay cached. But the long tail of low-follower accounts has poor cache hit rates, and a cache miss means a database read for a timeline that might be read once and evicted.

Pull does have genuine advantages. Writes are trivially fast — one append, no fan-out queue, no worker fleet. There's no wasted work on inactive readers. And when you add algorithmic ranking (which requires scoring each candidate against the reader's interest model), pull naturally produces the candidate set you need to rank. Push pre-materialises a chronological inbox that you then have to re-rank anyway, which partly defeats the purpose.

Pull is the right answer when the fan-in is low (users follow <100 accounts), when celebrity content dominates the feed, or in read-light workloads where most users check their feed infrequently. It's also the simpler starting point — no fan-out infrastructure, no inbox storage, just timelines and a merge service.

The hybrid is not a compromise — it is the only architecture that survives production at scale. The insight is that push and pull are two regimes of the same cost function, and the follower-count threshold is the phase boundary.

Set a threshold — say, 1 million followers. Below it, the post triggers fan-out on write: the fan-out worker pushes the post id into every follower's inbox. Above it, the post is stored only in the celebrity's own timeline; no fan-out occurs. At feed-read time, the service reads the user's inbox (pre-materialised by push) and also pulls the latest posts from each celebrity the user follows. A typical user follows 5-15 celebrities, so this pull adds at most 15 timeline reads to an otherwise O(1) inbox read. The merged result is passed to the ranking service.

The threshold is not a magic number — it's a cost boundary. Below it, the per-post fan-out cost (N ZADD operations) is cheaper than the aggregate read-time pull cost across all readers. Above it, the fan-out cost exceeds the read-time cost. The exact value depends on the ratio of post frequency to feed-read frequency, the Redis write throughput, and the celebrity's posting cadence. Twitter's engineering team settled on a threshold in the low millions of followers, tuned dynamically: users crossing the threshold during viral moments are reclassified within minutes by a follower-count monitoring service.

This is what Twitter, Instagram, and LinkedIn all do. Twitter's Raffi Krikorian described this architecture at QCon: the fan-out service checks the author's follower count before deciding the write path. Instagram extends it with heavier algorithmic ranking — the pull path feeds celebrity content into a ML-based scoring pipeline that weighs recency, engagement prediction, and interest-graph affinity. LinkedIn's variant exploits the fact that connections are bounded (~500 average) so the push path handles connections, while company and influencer follows use the pull path.

The complexity cost is real: two code paths, two storage layers, a merge step at read time, and a monitoring system for threshold crossings. But the alternative — pure push that melts during a Bieber tweet, or pure pull that can't serve p99 latency for power users — doesn't ship.

Not every fan-out problem has a celebrity problem. Activity streams — GitHub's notification feed, Slack's channel activity, JIRA's project activity log — differ from social feeds in one structural way: the source set is bounded by system design, not by user behaviour.

On GitHub, a repository might have 10,000 watchers. When someone pushes a commit, the activity service fans out a notification to those 10,000 watchers' activity feeds. The fan-out is bounded because repository watchers are bounded (and self-selected). There is no "celebrity repository" with 100 million watchers that breaks the push path. Slack channels have a hard member limit. JIRA projects have bounded team sizes.

In these systems, pure fan-out on write is the correct answer and the hybrid complexity is unnecessary. The architecture is straightforward: event source → message queue → fan-out worker → per-user activity inbox (often a bounded list in Redis or a DynamoDB partition). The fan-out is measured in thousands, not millions, and completes in milliseconds.

The key difference from social fan-out is that the architect controls the maximum fan-out by controlling the maximum group size. If you can enforce that no single source fans out to more than N recipients, and N is bounded by product rules (not by user growth), pure push is simpler, cheaper, and more predictable than any hybrid.

Store posts in a posts table, follows in a follows table. When a user requests their feed, run a join: SELECT p.* FROM posts p JOIN follows f ON p.author_id = f.followed_id WHERE f.follower_id = ? ORDER BY p.created_at DESC LIMIT 50. This is pure pull — no fan-out, no inbox, no workers.

This works for the first 10K users. The join is fast when the follows table fits in memory and the posts table is indexed on (author_id, created_at). Read latency is 10-50ms depending on the number of followed accounts.

Add a fan-out worker: when a user posts, iterate their follower list and ZADD the post id (scored by timestamp) into each follower's inbox ZSET. Feed reads become a single ZREVRANGE call — O(1) regardless of follow count.

Trim inboxes to 800 entries with ZREMRANGEBYRANK after each ZADD batch. Older content is still available via the author's timeline (fallback for deep scroll). This handles millions of users with sub-10ms feed reads.

Introduce a follower-count threshold (~1M). Below it: push (fan-out on write into inboxes). Above it: skip fan-out, store in author timeline only. At read time: merge the pre-materialised inbox with pull-fetched celebrity timelines, then pass candidates through a ranking service that scores by recency, engagement prediction, and affinity.

The ranking service receives ~100-200 candidates (50 from inbox + 10-15 celebrity timeline pulls × 10 posts each), enriches them with features from the feature store, runs an ML scoring model, applies diversity filtering, and returns a ranked page of 50 items. Total read latency: 30-80ms.

Partition followers by region. When a post arrives, the region router splits the follower list into regional chunks and dispatches fan-out tasks to regional fan-out workers. Each region maintains its own inbox Redis cluster. Feed reads are served entirely from the local region — no cross-region calls for the inbox read path.

Celebrity timeline pulls still cross regions (the celebrity's timeline lives in their home region), but these are cached aggressively in each consuming region with a 30-second TTL. Cross-region replication lag for celebrity content is acceptable because feed freshness expectations are lower for celebrity posts (users don't expect to see a Bieber tweet within 1 second).

The celebrity threshold is the single most important tuning parameter in a hybrid fan-out system. Set it too low and you pull too many authors at read time, inflating feed latency. Set it too high and celebrity posts storm the fan-out queue. The right value depends on four variables: the average fan-out worker throughput (ZADD/sec), the SLA for fan-out completion time, the p99 number of celebrities a user follows, and the acceptable read-time pull latency.

A practical starting point is 1 million followers. At this level, a single post triggers up to 1M ZADD operations. With a fan-out worker fleet processing 500K writes/second aggregate, that's a 2-second fan-out — acceptable. Above 1M, the fan-out time grows linearly and starts competing with other posts in the queue.

Static thresholds break during viral moments. A user with 900K followers posts something that goes viral; within hours they cross 2M followers. If the threshold check happens only at post time, the system fans out to 900K inboxes for the viral post (fine) but then fans out to 2M for the next post (still fine but getting expensive). The real problem is the reverse: a user oscillates around the threshold, and some posts are pushed while others aren't, creating inconsistent feed behaviour for followers.

The solution is a dynamic threshold with hysteresis. The follower-count monitoring service checks counts every 5 minutes. When a user crosses from below to above the threshold, they're reclassified as a "celebrity" with a cooldown period (e.g., 1 hour) before they can be reclassified back down. This prevents oscillation.

The celebrity storm diagram shows what happens without a threshold: a 100M-follower post generates 100M fan-out tasks, saturates the queue, and delays all other fan-out for minutes. With the threshold, this post simply goes into the author's timeline — zero fan-out tasks, zero queue impact.

The inbox is the core data structure of fan-out on write. Each user's inbox is a Redis sorted set (ZSET) where members are post ids and scores are timestamps (or snowflake ids for ordering). The ZSET provides three critical operations:

1. 1ZADD — insert a post id with a score. O(log N) where N is the set size. With bounded inboxes (N ≤ 800), this is effectively O(1).
2. 2ZREVRANGE — read the top K entries by descending score. O(K + log N). For a feed page of 50 items: sub-millisecond.
3. 3ZREMRANGEBYRANK — trim the set to keep only the top N entries. Called after ZADD to enforce the size bound.

The fan-out worker pipelines these operations for efficiency. A typical batch: ZADD inbox:{user_id} {timestamp} {post_id} for each of 50 follower inboxes in a single Redis pipeline, followed by ZREMRANGEBYRANK inbox:{user_id} 0 -(max_size+1) to trim. The pipeline completes in under 1ms for 50 operations.

Memory budget: each ZSET entry costs ~80 bytes (64-byte member + 8-byte score + 8-byte overhead). An inbox of 800 entries costs ~64KB. For 200M users: 200M × 64KB = 12.8TB. This is the primary cost driver and the reason inboxes must be bounded. Without the bound, memory grows linearly with post volume × follower count, which is unsustainable.

Deep scroll (page 2+) works by continuing the ZREVRANGE with an offset. Beyond the inbox's 800 entries, the feed service falls back to pulling from author timelines — switching from push to pull for historical content. This is acceptable because deep scroll is rare (<5% of feed reads go past page 1) and latency expectations are relaxed.

TTL is an additional lever: set a 7-day TTL on inbox keys so that users who haven't opened the app in a week don't consume memory. When they return, the feed service detects the empty/expired inbox and does a full pull-based reconstruction, then resumes normal push delivery.

In the hybrid model, feed reads merge two data sources: the pre-materialised inbox (from push) and K celebrity timelines (from pull). The merge is a K-way merge of sorted streams, where K = 1 (inbox) + number of celebrities the user follows.

The algorithm uses a min-heap of size K+1. Initialise the heap with the most recent entry from each stream. To produce the next feed item, extract the max from the heap, then insert the next entry from that item's source stream. Repeat until you have a full page (typically 50 items).

Time complexity: O(N log K) where N is the page size and K is the number of streams. For a typical user following 10 celebrities: O(50 × log 11) ≈ 170 comparisons — trivial.

The expensive part isn't the merge — it's fetching the celebrity timelines. Each timeline read is a ZREVRANGE against a Redis key or a database query. With 10 celebrity pulls, and each taking 2-5ms (cached) or 20-50ms (cache miss), the total pull latency is 2-50ms depending on cache hit rates. Celebrity timelines are hot (millions of readers access them) so cache hit rates exceed 99% in practice.

Caching the merged result is tempting but tricky. The merged feed is personalised (different users follow different celebrities), so you can't share it across users. You can cache it per-user with a short TTL (30-60 seconds) to handle rapid pull-to-refresh. The cache key includes the user id and a version number that increments on each inbox write, ensuring the user sees new posts within one refresh cycle.

For the ranking pipeline, the merge step produces a candidate set of ~100-200 items (50 from inbox + 10-15 × 10 from celebrity timelines). This candidate set is then scored and re-ranked by the ranking model, which may reorder items based on engagement prediction, recency decay, and interest-graph affinity. The merge-K step is therefore a pre-filter, not the final ordering.

The hybrid threshold handles mega-celebrities (>1M followers) by routing them to pull. But what about mid-tier celebrities — users with 100K to 1M followers who are still on the push path? A single post from a 500K-follower user generates 500K ZADD operations. If ten such users post simultaneously, that's 5M fan-out tasks hitting the queue at once.

Spread fan-out addresses this by chunking the follower list and scheduling chunks over time. Instead of enqueuing a single "fan out to 500K followers" task, the fan-out scheduler splits the follower list into chunks of 50K and schedules them with staggered delays: chunk 1 at t=0, chunk 2 at t=10s, chunk 3 at t=20s, and so on. The fan-out workers drain at a steady rate, never spiking above their provisioned throughput.

The trade-off is fan-out latency. A 500K-follower post now takes ~100 seconds to reach all followers instead of ~10 seconds. For most users, this is invisible — they don't notice whether a post appears in their feed 5 seconds or 50 seconds after publication. The only users who might notice are the author's most engaged followers, who are typically in the first chunk (sorted by recent activity).

Implementation details: the fan-out scheduler stores chunk metadata in a delayed message queue (e.g., SQS with delay seconds, or a Redis sorted set used as a delay queue). Each chunk message contains the post id, the follower list offset, and the chunk size. Workers process chunks idempotently — if a chunk is retried, the ZADD operations are naturally idempotent (same member + same score = no-op).

Rate limiting fan-out workers is the complementary control. Each worker has a configurable writes-per-second limit (e.g., 50K ZADD/sec). If the queue depth exceeds a threshold, the scheduler automatically increases the inter-chunk delay for new posts, providing backpressure without dropping fan-out tasks. The system self-regulates: during quiet periods, fan-out is near-instant; during peak load, it spreads gracefully.

The follow graph is not static. Users follow and unfollow accounts constantly — Twitter sees millions of follow/unfollow events per day. Each event has implications for the fan-out system that are easy to overlook in a design interview.

On follow: When user A follows user B, A's inbox should contain B's recent posts. Two approaches: (1) Backfill — a background worker fetches B's last N posts and ZADDs them into A's inbox. This provides immediate gratification but adds write load proportional to the follow rate. (2) Lazy — don't backfill; A will start seeing B's posts on the next fan-out. This is simpler but means A's feed looks sparse right after following someone. Most production systems use backfill with a small N (e.g., 10 posts).

On unfollow: When user A unfollows user B, B's posts should disappear from A's feed. Two approaches: (1) Eager deletion — scan A's inbox and remove all post ids authored by B. This requires a secondary index (post_id → author_id) and is expensive for large inboxes. (2) Lazy filter — leave B's posts in A's inbox but filter them out at read time by checking the follow graph. This is cheaper but means stale entries consume inbox space.

The production answer is lazy filter + nightly sweep. At read time, the feed service checks each candidate post's author against the reader's current follow set (cached) and filters out unfollowed authors. A nightly batch job scans inboxes and removes entries from unfollowed authors, reclaiming space. The lazy filter ensures correctness immediately; the nightly sweep ensures space efficiency eventually.

Edge case: A follows B, B posts, A unfollows B, A re-follows B. With lazy filter, B's posts are filtered out during the unfollow window and reappear on re-follow (because the filter checks current follow state). With eager deletion, the posts are gone and would need backfill on re-follow. The lazy approach handles this naturally.

Another subtlety: if B is above the celebrity threshold, follow/unfollow doesn't affect A's inbox at all (B's posts were never pushed). The follow graph update only affects the pull list used at read time — the feed service checks which celebrities to pull from based on A's current follow set.

A modern feed is not chronological — it is ranked. The ranking pipeline transforms a raw candidate set into a personalised, engaging feed. In the hybrid fan-out model, the pipeline sits between the merge step and the final response.

Stage 1: Candidate generation. The merge-K step produces 100-200 candidates from the inbox (push) and celebrity timelines (pull). This is the initial candidate pool.

Stage 2: Feature enrichment. Each candidate is annotated with features from the feature store: post age, author engagement rate, media type, number of likes/retweets in the first 5 minutes (early engagement signal), the reader's historical interaction rate with this author, topic embeddings, and recency decay. The feature store is typically a low-latency key-value store (Redis or a purpose-built feature service) pre-computed by offline pipelines.

Stage 3: Scoring. A lightweight ML model (typically a gradient-boosted tree or a small neural network) scores each candidate. The model predicts P(engagement) — the probability the reader will like, comment, or share the post. Training data comes from historical engagement logs. Inference must complete in <10ms for the full candidate set, which constrains model complexity.

Stage 4: Diversity filtering. A ranked list of the top 50 by score goes through a diversity filter that ensures no single author dominates the feed (e.g., max 3 posts per author in a single page), mixes content types (text, image, video), and injects exploration candidates (posts from authors the user hasn't interacted with recently) to avoid filter bubbles.

Stage 5: Materialisation. The final ranked page is cached per-user with a 60-second TTL. Subsequent feed reads within the TTL window return the cached result. On pull-to-refresh, the cache is invalidated and the pipeline runs again.

The ranking pipeline adds 20-50ms to feed read latency (on top of the ~10ms for inbox read + merge). The total feed read latency budget is typically 50-100ms. Keeping the pipeline within budget requires aggressive pre-computation (features in the feature store, not computed at serving time), model simplicity (inference must be <10ms), and parallelism (feature fetch and model inference can overlap for different candidates).