Fan-out on write

Deep dive

How it works

Parts:

• follower index — author to follower ids; sizes decide push vs pull.
• timeline store — per user, capped list/sorted set of post ids (newest at one end).
• author log — each author's own recent ids, the source for pulls and backfill.
• fan-out worker — turns one post into follower appends, off the request path (durable queue), batched.
• reader — merges the user's timeline with recent posts of pulled followees, dedupes, takes N.

1. Post: assign an increasing id (sequence numbers), append to the author log, enqueue a fan-out job.
2. Worker: if followers > threshold stop (pull author); else for each active follower append the id, trim to N, in pipelined batches.
3. Read: fetch the timeline, fetch the newest ids of each pulled followee, k-way merge by id descending, dedupe, take the page; then load bodies by id.
4. Follow: backfill the author's recent ids into the timeline (skip pulled authors). Unfollow/delete: remove that author's or post's ids.
5. Inactive users: no pushes; rebuild their timeline on return from the author logs.

post --> author log --> queue --> worker --(per active follower)--> timeline[f]  (capped N)
                                   \-- followers > T: skip
read(u) = merge( timeline[u], recent(author) for each pulled followee of u ) -> top N

Code

Capped timelines, threshold hybrid, backfill and unfollow. Compiled; asserts that the hybrid read equals the pure pull read for all sampled users on a 20,000-user power-law graph (std only).

use std::collections::VecDeque;

pub type PostId = u64; // global, increasing: id order = time order

pub struct Feed {
    cap: usize,                  // timeline length per user
    threshold: usize,            // more followers than this: pulled
    followers: Vec<Vec<u32>>,    // author -> followers
    followees: Vec<Vec<u32>>,    // user -> authors followed
    own: Vec<VecDeque<PostId>>,  // author -> own recent post ids (newest at back, capped)
    timeline: Vec<VecDeque<PostId>>, // user -> pushed ids, newest at back, capped
    pub active: Vec<bool>,       // inactive users get no pushes
    next_id: PostId,
    pub writes: u64,             // timeline inserts = write amplification
}

impl Feed {
    pub fn new(users: usize, cap: usize, threshold: usize) -> Self {
        Feed {
            cap, threshold,
            followers: vec![vec![]; users], followees: vec![vec![]; users],
            own: vec![VecDeque::new(); users], timeline: vec![VecDeque::new(); users],
            active: vec![true; users], next_id: 1, writes: 0,
        }
    }
    fn big(&self, author: u32) -> bool { self.followers[author as usize].len() > self.threshold }

    pub fn follow(&mut self, user: u32, author: u32) {
        self.followers[author as usize].push(user);
        self.followees[user as usize].push(author);
        // backfill (pulled authors are merged at read time)
        if !self.big(author) {
            let mut merged: Vec<PostId> = self.timeline[user as usize].iter().copied().collect();
            merged.extend(self.own[author as usize].iter().copied());
            merged.sort_unstable();
            merged.dedup();
            let skip = merged.len().saturating_sub(self.cap);
            self.timeline[user as usize] = merged.into_iter().skip(skip).collect();
        }
    }

    pub fn unfollow(&mut self, user: u32, author: u32) {
        self.followers[author as usize].retain(|&u| u != user);
        self.followees[user as usize].retain(|&a| a != author);
        let theirs = &self.own[author as usize];
        self.timeline[user as usize].retain(|id| !theirs.contains(id));
    }

    pub fn post(&mut self, author: u32) -> PostId {
        let id = self.next_id;
        self.next_id += 1;
        let own = &mut self.own[author as usize];
        own.push_back(id);
        if own.len() > self.cap { own.pop_front(); }
        if !self.big(author) {
            for &f in &self.followers[author as usize] {
                if !self.active[f as usize] { continue; }
                let t = &mut self.timeline[f as usize];
                t.push_back(id);
                if t.len() > self.cap { t.pop_front(); }
                self.writes += 1;
            }
        }
        id
    }

    /// Newest `n` ids (n <= cap): pushed timeline merged with the recent posts of pulled authors.
    pub fn read(&self, user: u32, n: usize) -> Vec<PostId> {
        let mut c: Vec<PostId> = self.timeline[user as usize].iter().copied().collect();
        for &a in &self.followees[user as usize] {
            if self.big(a) { c.extend(self.own[a as usize].iter().rev().take(n).copied()); }
        }
        c.sort_unstable_by(|a, b| b.cmp(a));
        c.dedup(); // an author may have crossed the threshold after pushing
        c.truncate(n);
        c
    }

    /// Reference: pure fan-out on read (merge every followee's recent posts).
    pub fn read_pull(&self, user: u32, n: usize) -> Vec<PostId> {
        let mut c: Vec<PostId> = Vec::new();
        for &a in &self.followees[user as usize] {
            c.extend(self.own[a as usize].iter().rev().take(n).copied());
        }
        c.sort_unstable_by(|a, b| b.cmp(a));
        c.truncate(n);
        c
    }
}

Complexity and constants

• Post: followers x (list append + trim). A Redis LPUSH is O(1) per element and LTRIM O(removed), so one push is amortised O(1); ZADD + ZREMRANGEBYRANK (O(log N + M)) costs more but keeps order when ids arrive out of order.
• Memory: users x N x id size. 800 ids x 8 B is 6.4 KB raw per active user before container overhead; payloads live once, elsewhere.
• Measured by me (synthetic: 20,000 users, 307,763 follow edges, follower counts from 10,000/rank^0.8, authors posting uniformly, N=100; counts, not timings):

• Mean writes barely move; the point of the threshold is the tail: the largest author has 10,000 followers (one post = 10,000 appends under pure push), T=200 bounds a post at 199.

Efficiency

Cost: one post = one append per active follower (counted, not timed here); bound is the write command rate and round trips to the timeline store, not CPU. One read = 1 list fetch + 1 fetch per pulled followee + a body lookup.

Levers:

• Hybrid threshold — worst-case writes per post 10,000 to 199 at T=200 (measured above) — power-law follower graphs.
• Skip inactive users — with 70 % inactive in my sim, pure push writes/post fell 15.11 to 4.49 (measured; Mastodon skips users not recently signed in) — many dormant accounts; pay a rebuild on return.
• Ids only, capped length — memory = users x N x id size, trim keeps appends O(1) — payloads fetched by id and cached once.
• Batch/pipeline appends — a round trip is paid per batch, not per command (Redis pipelining docs: syscalls and context switches dominate otherwise) — worker sends 100s of appends per round trip.
• Queue the fan-out — post latency independent of follower count — always for more than a few hundred followers.

Naive → standard → state of the art:

• Pull: join posts of all followees per read · O(followees) fetches per open (16.4 here)
• Push with capped id lists and workers · 1 fetch per read, writes = followers
• Per-edge hybrid by rates (Feeding Frenzy: push or pull decided per producer-consumer pair from update and view rates) · lowest load in the paper's tests

Implementation notes

• Fan-out in chunks (Mastodon enqueues followers in batches via find_in_batches and push_bulk), each job idempotent: appending an id already present is a no-op.
• Keep an author log so backfill, rebuild and pull need no database scan; bound it too.
• Unfollow needs ids by author: scanning the timeline works at N=800; with a larger N keep an author tag in the entry.
• Resumable clients: page by id cursor (incremental sync cursors), not offset; the list shifts as posts arrive.

Pitfalls

• Threshold flips: an author that crosses T has old pushed ids and new pulled ones: dedupe on read. Dropping back below T leaves a gap of unpushed posts; use hysteresis and backfill.
• Capped timelines lose depth: a user who follows 5,000 quiet accounts and wants "everything since last week" needs the pull path.
• Deletes and edits: ids pushed to millions of lists cannot be recalled cheaply; hide at read by checking the post, and sweep lazily.
• Fan-out stampede when a celebrity's followers all become active: rate-limit workers per author.

Variants and alternatives

In production

Mastodon (social home timelines in Redis sorted sets, 800 entries, skips users not recently signed in); Twitter's timeline service (public description: Krikorian's talk); Stream Feeds, a hosted API for timelines, follow graphs and notification feeds used in app backends of any domain; per-recipient notification inboxes in SaaS and developer tools follow the same shape.

Implementations

Sources

• Adam Silberstein, Jeff Terrace, Brian F. Cooper, Raghu Ramakrishnan, Feeding Frenzy: Selectively Materializing Users' Event Feeds, SIGMOD 2010. paper
• Raffi Krikorian, Timelines at Scale, QCon talk on InfoQ. talk
• Stream, Activity Feeds docs. docs
• Mastodon source: feed_manager.rb, fan_out_on_write_service.rb
• Redis docs: LTRIM, LPUSH, ZREMRANGEBYRANK, pipelining