CS Fundamentals Trainer · Guides

Design a news feed

Fan-out on write versus read, the celebrity problem and the hybrid, Redis timelines with measured memory, keyset versus OFFSET pagination timed on PostgreSQL, ranking, deletes and privacy.

31 min read

"Design a news feed" (or "design Twitter's home timeline", or "design Instagram's feed") is one of the richest system design questions, because the simple version works in an afternoon and the real version is full of trade-offs: who pays the cost, the writer or the reader, what happens when one user has fifty million followers, and what "page 2" even means when the list keeps changing. This guide builds the design step by step and backs each claim with a measurement: a fan-out model on a skewed follower graph, Redis timelines (memory and speed), and offset against keyset pagination on PostgreSQL.

1. What we are building

A user opens the app and sees a list of recent posts from the accounts they follow, newest first (or ranked), and can keep scrolling. People post; followers see it quickly.

Functional requirements

• Publish a post (text, maybe media references).
• Follow and unfollow accounts.
• Read the home feed: posts from the people I follow, newest first, with "load more".
• Read a profile timeline: one user's own posts (a much easier problem).

Non-functional requirements

• Reading the feed must be fast (a few hundred milliseconds), because it is the main screen.
• A new post should appear in followers' feeds within seconds, not hours.
• The system must survive skew: most accounts have few followers, a few have millions.
• It is fine if a feed is a little stale or briefly misses a post (eventual consistency, see the CAP guide). It is not fine to lose posts permanently.
• Out of scope here: the media pipeline, search, ads, and the notification system.

Back-of-the-envelope numbers

Write your assumptions down; they drive every later decision. Suppose 100 million daily active users, each opening the feed 10 times a day and posting 0.5 posts a day on average, following about 40 accounts.

Reads outnumber writes about 20 to 1, which suggests doing work at write time to make reads cheap. The last row is the reason it is not that simple.

2. The data model

Three things are stored durably (names are plain, adapt them to your database):

CREATE TABLE users   (id bigint PRIMARY KEY, handle text UNIQUE NOT NULL, followers_count int NOT NULL DEFAULT 0);
CREATE TABLE posts   (id bigint PRIMARY KEY,           -- a time-sortable id, see below
                      author_id bigint NOT NULL REFERENCES users,
                      body text NOT NULL,
                      created_at timestamptz NOT NULL DEFAULT now(),
                      deleted_at timestamptz);
CREATE INDEX posts_by_author ON posts (author_id, id DESC);
CREATE TABLE follows (follower_id bigint NOT NULL, followee_id bigint NOT NULL,
                      created_at timestamptz NOT NULL DEFAULT now(),
                      PRIMARY KEY (follower_id, followee_id));
CREATE INDEX follows_by_followee ON follows (followee_id, follower_id);   -- "who follows X": needed for fan-out

Notes that matter in an interview:

• Time-sortable post ids (Snowflake-style: timestamp bits, machine bits, sequence bits; see the URL shortener guide for the idea) mean "sort by id" is "sort by time", ties disappear, and an id works as a pagination cursor.
• The follow graph is read in both directions: "whom do I follow" for pulling, "who follows me" for pushing. Index both.
• Do not store the feed itself in this relational schema: a feed is a derived, rebuildable view. That is the key to everything below.

Diagram: The main pieces of a feed system

3. Approach 1: build the feed when it is read (fan-out on read, "pull")

When a user opens the feed, fetch the recent posts of everyone they follow and merge them:

SELECT p.id, p.author_id, p.body
FROM posts p
JOIN follows f ON f.followee_id = p.author_id
WHERE f.follower_id = $1 AND p.deleted_at IS NULL AND p.id < $2        -- $2 = the cursor
ORDER BY p.id DESC
LIMIT 20;

Writing a post is trivial: one insert. Reading costs one lookup per followee: with about 40 followees, a feed read touches 40 author lists and merges them. That does not sound like much, but multiply by the read rate. In my model of one million users (below), pull needs about 396 million followee-list reads per day, against 10 million feed opens, and every one of those reads sits on the user's waiting time. Pull is simple and always fresh, and it gets slow exactly where the product is busiest: the read path.

4. Approach 2: build the feed when a post is written (fan-out on write, "push")

Flip it. Each user has a precomputed timeline: a list of post ids, newest first. When someone posts, workers append the id to the timeline of every follower. Reading a feed is then one cheap lookup of one list.

Diagram: Fan-out on write: one post is copied into every follower's timeline

Notice the order: the post is saved first, and the fan-out happens asynchronously from a queue. If the workers fall behind, followers see the post a little later, but the author is never blocked. The queue gives retries; the writes must be idempotent, because the same event can be delivered twice (see message queues and delivery guarantees). Adding an id to a sorted set is naturally idempotent: adding the same member again changes nothing.

Timelines in Redis

A Redis sorted set per user fits well: member = post id, score = the same time-sortable id. I ran this against a real Redis 7:

ZADD tl:42 7000000000001 7000000000001          # add a post (a repeat changes nothing)
ZREMRANGEBYRANK tl:42 0 -801                    # keep only the newest 800
ZREVRANGEBYSCORE tl:42 +inf -inf LIMIT 0 20     # page 1, newest first
ZREVRANGEBYSCORE tl:42 (7000000000980 -inf LIMIT 0 20   # next page: strictly below the last id seen

What I measured:

Two planning facts follow. First, memory: 800 entries is about 82 KB per user, so 100 million users would need roughly 8 TB of RAM if every user kept a full timeline. Design responses: store ids only (never post bodies; fetch bodies from a post cache), keep fewer entries (200 entries is about 25 KB in the layout test below), and keep timelines only for recently active users. Second, speed: one Redis instance handled about 63,000 writes per second in this test, on a small machine, with a client on the same host and no network. A real deployment has a network between the workers and Redis, replication and bigger values, so expect less per instance and measure. Even so, the average 23,000 writes per second of the 100 M-user design fits a handful of shards, and the real design question is bursts, not averages.

Which memory layout for a timeline?

The sorted set is not the only way to store a list of ids. I stored the same ids (8-byte numbers, newest first) three ways in Redis 7 and asked Redis for each key's memory:

The sorted set is about 10 times bigger than the other two once it passes 128 entries, which is where Redis switches it from a compact array to a skip list (the default zset-max-listpack-entries is 128). So why pay for it?

Decision: the sorted set is the default here because the fan-out is at least once and idempotence is worth the memory. If memory is the constraint, the list at a tenth of the size is a real option, provided the write path is guarded against duplicates (for example, skip the push when the new id is not larger than the list's head: ids are time-sortable). Another cut is to keep sorted sets small: 128 entries stay compact at 24 bytes each, so a short timeline (and a pull fallback beyond it, below) can be much cheaper than an 800-entry one. The numbers are Redis 7.0.15 defaults; check yours with MEMORY USAGE.

Why push alone breaks: the celebrity problem

I built a model of one million users with a heavy-tailed follower distribution (a Pareto shape, so most accounts have few followers and a few have huge audiences; the exact numbers depend on my assumptions of 0.5 posts and 10 feed opens per user per day):

Pure push is far cheaper than pure pull overall (20 million writes against 396 million reads), but one post from the biggest account triggers half a million writes at once. It delays that account's followers, floods the queue so ordinary users' posts wait behind it, and most of those writes go to users who will not open the app today. The answer is a mix.

5. The hybrid: push for most, pull for the few

Choose a threshold (say 10,000 followers). Normal accounts are pushed; celebrity accounts are not. When someone opens the feed, the API reads their precomputed timeline and merges in the recent posts of the celebrities they follow, pulled at read time. A celebrity's posts are fetched from one hot, heavily cached list, so a million readers share the work of one lookup.

Diagram: Reading the home feed in the hybrid design

I ran the same million-user model for three thresholds:

Read this table as a dial. A low threshold removes more write cost and the biggest bursts, and makes every read merge more lists. A high threshold keeps reads simple, and leaves bursts (the top 19 accounts account for 13% of all writes in this model, in huge clumps). Choosing the threshold is a matter of measuring your own follower distribution, and it can be a per-account decision made from followers_count at publish time. (The "celebrity lists per feed open" column assumes followers are spread randomly; real people follow more famous accounts than average, so measure on real data.)

Other choices around the hybrid:

• Do not push to inactive users. If someone has not opened the app in 30 days, skip them; when they return, rebuild their timeline by pulling (a "cold start"). This alone can cut the write volume a lot, because many follow edges point at dormant accounts.
• Rebuild on loss. The timeline store is a cache of derived data. If a shard dies, rebuild timelines from the follow graph and the posts table, lazily, on the next read.
• Prioritise. Fan-out for small accounts should not wait behind a celebrity: use separate queues or priorities.

6. Reading the feed: pagination that does not break

The feed changes while you scroll: new posts arrive at the top. That makes "page 2" tricky. The common approach, LIMIT 20 OFFSET 20, has two defects, and I measured both on PostgreSQL with a timeline table of one million rows (500,000 for one user):

Slower the deeper you go. OFFSET n makes the database walk past n rows and throw them away.

Wrong when the list changes. I loaded page 1, inserted 5 new posts, then loaded page 2: OFFSET page 2 repeated 5 posts already seen (everything shifted down by five); the keyset page repeated 0.

Keyset (cursor, "seek") pagination asks for the rows after the last one you saw, using the sort key: WHERE (created_at, post_id) < (last_created_at, last_post_id) ORDER BY created_at DESC, post_id DESC LIMIT 20. The plan is an index-only backward scan that stops after 20 rows, and the cost does not depend on how deep you are [1]. The cursor is opaque to the client: encode the last item's sort key (for example base64 of the post id) and send it back as ?cursor=….

Here is the read path's core: merge the pushed timeline with celebrity posts after a cursor, and return one page and the next cursor (pick a language on the tabs; your choice is remembered):

import heapq

def feed_page(timeline_ids, celeb_lists, cursor, limit=20):
    """Each input list is sorted newest first (largest id first). cursor = the smallest id already
    shown, or None for the first page. Returns (page, next_cursor)."""
    def after_cursor(ids):
        return (i for i in ids if cursor is None or i < cursor)
    merged = heapq.merge(after_cursor(timeline_ids), *(after_cursor(l) for l in celeb_lists), reverse=True)
    page, last = [], None
    for i in merged:
        if i == last:                 # the same post can come from two lists: drop duplicates
            continue
        page.append(i)
        last = i
        if len(page) == limit:
            break
    return page, (page[-1] if len(page) == limit else None)

// Each input slice is sorted newest first (largest id first). cursor == 0 means the first page.
func FeedPage(timeline []int64, celebs [][]int64, cursor int64, limit int) (page []int64, next int64) {
	lists := append([][]int64{timeline}, celebs...)
	pos := make([]int, len(lists))
	for len(page) < limit {
		best, from := int64(-1), -1
		for i, l := range lists {
			for pos[i] < len(l) && cursor != 0 && l[pos[i]] >= cursor {
				pos[i]++ // skip what the cursor says was already shown
			}
			if pos[i] < len(l) && l[pos[i]] > best {
				best, from = l[pos[i]], i
			}
		}
		if from < 0 {
			return page, 0 // everything is used up: no next page
		}
		for i, l := range lists { // advance every list that holds the same id (duplicates)
			if pos[i] < len(l) && l[pos[i]] == best {
				pos[i]++
			}
		}
		page = append(page, best)
	}
	return page, page[len(page)-1]
}

// Each input array is sorted newest first (largest id first). cursor is null on the first page.
function feedPage(timeline, celebLists, cursor, limit = 20) {
  const lists = [timeline, ...celebLists].map((l) => l.filter((id) => cursor === null || id < cursor));
  const pos = lists.map(() => 0);
  const page = [];
  while (page.length < limit) {
    let best = null;
    lists.forEach((l, i) => {
      if (pos[i] < l.length && (best === null || l[pos[i]] > best)) best = l[pos[i]];
    });
    if (best === null) return { page, next: null };
    lists.forEach((l, i) => {
      if (pos[i] < l.length && l[pos[i]] === best) pos[i]++; // drop duplicates across lists
    });
    page.push(best);
  }
  return { page, next: page[page.length - 1] };
}

// Each input list is sorted newest first (largest id first). cursor == null means the first page.
public static (List<long> Page, long? Next) FeedPage(
    IReadOnlyList<long> timeline, IReadOnlyList<IReadOnlyList<long>> celebs, long? cursor, int limit = 20)
{
    var lists = new List<List<long>> { timeline.Where(i => cursor is null || i < cursor).ToList() };
    lists.AddRange(celebs.Select(l => l.Where(i => cursor is null || i < cursor).ToList()));
    var pos = new int[lists.Count];
    var page = new List<long>();
    while (page.Count < limit)
    {
        long? best = null;
        for (int i = 0; i < lists.Count; i++)
            if (pos[i] < lists[i].Count && (best is null || lists[i][pos[i]] > best)) best = lists[i][pos[i]];
        if (best is null) return (page, null);
        for (int i = 0; i < lists.Count; i++)
            if (pos[i] < lists[i].Count && lists[i][pos[i]] == best) pos[i]++;
        page.Add(best.Value);
    }
    return (page, page[^1]);
}

A real implementation reads only what it needs from each list (the next 20 after the cursor, from Redis), not whole lists; the merge logic is the same.

Also: new posts arriving while the user scrolls do not shift later pages (the cursor handles that); at the top, show a "3 new posts" button rather than inserting items under the reader's eyes (section 9).

Scrolling past the end of the timeline

The timeline keeps only the newest 800 ids, so a determined scroller will reach the end, and so will a user who comes back after a long absence. There are three honest options:

1. Stop with a clear end: "You're all caught up" (or "Load older posts" that opens search or the profile list). Simple, and many products do this; the cost is that very active users find a limit.
2. Fall back to pull for older pages: when the cursor goes below the oldest id in the timeline, read the followee list and the posts table with the same keyset condition (id < cursor) and merge, exactly as in approach 1 but for one page at a time. This is slow and expensive per request, so rate-limit it and cap the depth (for example, 7 days or a few thousand posts).
3. Keep a longer tail for the few who need it: a larger trim limit for heavy readers only.

To know whether the timeline is the whole story, record whether anything was ever dropped. ZREMRANGEBYRANK returns the number of members it removed (I checked: 1 when a fifth entry pushed out the oldest of four, 0 on the next call), so the worker can set a per-user flag when it is above zero. The read path then looks like this:

def older_page(user, cursor, limit=20):
    ids = timeline.below(user, cursor, limit)        # ZREVRANGEBYSCORE tl:user (cursor -inf LIMIT 0 limit
    if len(ids) == limit or not timeline.was_trimmed(user):
        return ids                                   # a full page, or the timeline holds everything there is
    last = ids[-1] if ids else cursor                # continue where the timeline ran out
    return ids + pull_page(user, below=last, limit=limit - len(ids))   # approach 1, one page, depth-capped

The same function covers the cold start of a returning user: an empty or stale timeline is simply a timeline that ran out immediately.

7. Ranked feeds

Many products rank instead of sorting by time. The usual shape is two stages:

1. Candidate generation: cheap and broad. The timeline from section 5 (a few hundred recent ids), plus a few recommended posts from outside the follow graph.
2. Ranking: a model scores each candidate for this user, from signals such as the author's relationship with the user (replies, likes, profile visits), the post's age and early engagement, the media type, and predicted actions (like, reply, share, hide). Sort by score, then apply rules: no more than two posts in a row from one author, mix media types, remove what the user already saw.

Design consequences:

• Ranking happens on the read path, on a small candidate set, so latency stays bounded; the heavy model work is done offline (training, features) or cached.
• Cursor pagination becomes harder, because the order is computed per request and changes as scores change. Typical fixes: compute the ranked list once per session and store it (a short-lived snapshot), page through the snapshot, and remember seen ids to avoid repeats.
• Keep a chronological option; users like to see it, and it is a handy fallback when the ranker is down.
• Watch for feedback loops (what gets shown gets engagement, which gets it shown more) and measure beyond clicks (hides, long-term retention). This is as much a product problem as a technical one.

8. Sharding and caching

• Timelines are sharded by user id (consistent hashing, see the consistent hashing guide). A user's whole feed lives on one shard, so a feed read is one round trip.
• Posts are looked up by id and are immutable except for edits and deletes; a read-through cache in front of the posts database (caching strategies) answers most body lookups. Celebrity posts are the hottest keys in the system; replicate them or cache them at the edge.
• The follow graph is read often and changes slowly. Cache each user's followee set; for fan-out, page through the followers of an author in batches (1,000 at a time) rather than loading them all.
• Replicas make a user's own new post appear missing from their feed if they read from a lagging copy. Add the author's own post to their own timeline immediately and read their own writes from the primary (the "read your writes" guarantee in the CAP guide).

9. Real-time updates

How does a feed show new posts without a refresh?

• Polling: every 30 to 60 seconds ask "anything newer than id X?". Simple, wasteful, and good enough for many products.
• Long polling, Server-Sent Events, WebSockets: the server pushes a small "new posts available" signal. Keep it a signal, not the posts themselves; the client then fetches the new items with the normal API and shows "N new posts". That keeps one code path for reading and keeps the connection layer light.
• Connections are expensive at scale (memory per connection, sticky routing); only keep them for users who are looking at the feed right now.

10. Deletes, edits, and privacy

• Deletes: do not chase a deleted post through millions of timelines. Mark the post deleted in the posts table and filter at read time when fetching bodies (the timeline holds only ids, which is why this works). Timelines tidy themselves as old entries are trimmed.
• Edits: the id stays the same, the body changes; the cache is invalidated by id.
• Blocks, mutes, private accounts: also filtered at read time, using the viewer's current settings; do not depend on what was true when the post was fanned out, because relationships change.
• Follow and unfollow: following someone should show their recent posts soon (backfill a few recent posts into the timeline); unfollowing should hide their posts (filter at read time by "do I still follow this author").

11. Reliability and operations

• Idempotent, retryable fan-out from a durable queue, with a dead-letter queue for events that keep failing and an alert on queue lag (the age of the oldest unprocessed post is the number users feel).
• Backpressure and priorities: separate queues for normal and very large accounts; cap the fan-out rate so Redis stays healthy.
• Degrade gracefully: if the timeline store is down, fall back to pull for a limited set of followees; if the ranker is down, serve the chronological feed.
• Rate limit posting and following (rate limiter guide); spam accounts mass-follow and mass-post.
• Metrics: feed read latency (p50, p99), fan-out lag, timeline memory, cache hit rate, queue depth, and the share of feed requests that needed a pull merge.
• Testing: unit tests for the merge and the cursor (duplicates, empty lists, the end of the feed); a load test with a skewed follower distribution, because a uniform test hides the celebrity problem entirely; a chaos test that kills a timeline shard and checks the rebuild.

12. Common mistakes

• Copying post bodies into timelines. Store ids; fetch bodies from a cache. Otherwise edits and deletes become a nightmare and memory explodes.
• Pure push for everyone, and a celebrity post that takes the system down. Measure the tail.
• Pure pull, and a slow home screen.
• OFFSET pagination on a list that changes: duplicates, gaps, and slow deep pages (measured above).
• A cursor that is not a unique sort key. If many posts share a timestamp, a timestamp-only cursor skips or repeats items; use the unique id (or (timestamp, id)).
• Fan-out inside the request that creates the post. Use a queue.
• Pushing to inactive users, which wastes most of the write volume.
• Treating the timeline store as the source of truth. It is derived data and must be rebuildable.
• Forgetting the viewer's own post in a lagging replica.

13. Questions interviewers like to add

"Why not just use a SQL query with a join, as in approach 1?"

It works for small scale and is a fine first answer. At the numbers above it puts a wide merge on every feed read, with no cache-friendly shape. Say that, then move to push.

"What if a user follows 10,000 people?"

Under push their timeline is still one list (they pay nothing extra at read time), but accounts they follow fan out into their list as usual. Under pull they would be the worst case. Heavy followers are a reason to keep push as the base.

"How do you handle a user who has not logged in for months?"

Do not push to them; when they return, build their timeline on demand by pulling the recent posts of their followees (and show a spinner or a slightly older feed meanwhile), then resume pushing.

"How do you make sure no post is lost?"

The post is written to the durable posts database before anything else; the event goes through a durable queue with retries and idempotent consumers. If a timeline write is lost anyway, the timeline can be rebuilt from the posts and the graph.

"How would you add ranking later?"

Keep timelines as the candidate set and add a ranking stage on the read path; store the ranked page for the session so pagination stays stable.

"What would you do differently for a feed of 1,000 users?"

Nothing fancy: a SQL query with the right index (pull) is simpler and fast enough. The design above is for when that stops being true, and the interview answer should say so.

14. Things to mention in an interview

• Start with requirements and numbers, and notice reads outnumber writes.
• Explain pull and push with their costs, and name the celebrity problem.
• Give the hybrid, with a threshold, and say you would choose it from data.
• Store ids, not bodies; shard timelines by user; trim to the newest N; skip inactive users.
• Use keyset pagination with a unique cursor, and say why OFFSET fails.
• Fan out asynchronously through a queue with idempotent writes.
• Filter deletes, blocks, and privacy at read time.
• Cover ranking as a second stage, and real-time updates as a "new posts" signal.
• Close with monitoring: queue lag, latency percentiles, memory.

Quick recap

1. A feed is a derived view of posts and the follow graph; it can be rebuilt.
2. Pull (merge at read time) is simple but makes reads slow; push (copy into followers' timelines) makes reads fast but a celebrity post can mean hundreds of thousands of writes.
3. The hybrid pushes normal accounts and pulls celebrities at read time; the threshold is a dial you set from data.
4. Timelines hold ids only, in a sorted set per user trimmed to the newest N (about 102 bytes per entry in Redis here).
5. Use keyset (cursor) pagination: constant time at any depth and stable while new posts arrive.
6. Fan out asynchronously from a queue with idempotent writes, and skip inactive users.
7. Apply deletes, blocks, and privacy at read time.
8. Ranking is a second stage on a small candidate set; keep a chronological fallback.

Appendix: the experiment code

The follower model, the Redis tests and the pagination benchmark are all short. You need Python 3, redis-py and a Redis on port 6399 for the Redis tests (redis-server --port 6399 --save "" --appendonly no), and psycopg plus a PostgreSQL for the pagination test (edit the connection string). All of them are throwaway: they delete what they create.

fanout.py: the follower model (one million users, Pareto shape 1.1 with a minimum of 5 followers, capped at half the users; 0.5 posts and 10 feed opens per user per day; seed 7). It prints the tables of the celebrity and hybrid sections. Change the seed or the shape and the numbers move; the pattern (a few accounts cause a large share of the writes) is what to check.

import random, math, statistics
rnd=random.Random(7)
N=1_000_000               # users
# follower counts ~ Pareto (a few accounts have a huge audience)
def followers():
    x=int(5*(1/(1-rnd.random()))**(1/1.1))   # shape 1.1, min 5
    return min(x,N//2)
F=[followers() for _ in range(N)]
tot=sum(F); F.sort(reverse=True)
print("users",N,"mean followers %.1f"%(tot/N),"median",F[N//2],"max",F[0])
print("top 1%% of accounts hold %.0f%% of all follow edges"%(100*sum(F[:N//100])/tot))
posts_per_user_day=0.5      # assumed
reads_per_user_day=10       # assumed feed opens
following_avg=tot/N         # edges / users = avg following
# push: every post is written to every follower's timeline
posts=N*posts_per_user_day
# post rate proportional to account (same for all) -> expected writes = posts * mean followers
push_writes=posts*tot/N
# pull: each feed open reads the last k posts of every followee
pull_reads_per_open=following_avg
pull_reads=N*reads_per_user_day*pull_reads_per_open
print("posts/day %.0f"%posts)
print("push: timeline writes/day %.2e, reads/day %.2e (one list per open)"%(push_writes,N*reads_per_user_day))
print("pull: reads of followee lists/day %.2e (avg %.0f followees per open)"%(pull_reads,pull_reads_per_open))
# the celebrity problem: one post by the biggest account
print("one post by the top account: push = %d timeline writes"%F[0])
for T in (1000,10000,100000):
    big=[f for f in F if f>T]
    # hybrid: push only for accounts with <=T followers; accounts above T are pulled at read time
    pushed=sum(f for f in F if f<=T)*posts_per_user_day
    celeb_count=len(big)
    # each feed open must also merge in posts of the celebrities that user follows: expected celebs followed
    expected_celebs=sum(big)/N
    print("T=%6d: %6d accounts above T; push writes/day %.2e (%.0f%% of full push); each open merges ~%.1f celebrity lists"%(T,celeb_count,pushed,100*pushed/push_writes,expected_celebs))

feedredis.py: fan-out speed, timeline size, trim and cursor paging:

import redis, time
r=redis.Redis(port=6399); r.flushall()
base=r.info("memory")["used_memory"]
followers=100_000; KEEP=800
post_id=7_000_000_000_001            # time-sortable id: larger = newer
t=time.perf_counter()
pipe=r.pipeline(transaction=False)
for i in range(followers):
    key=f"tl:{i}"
    pipe.zadd(key,{post_id:post_id}); pipe.zremrangebyrank(key,0,-(KEEP+1))
    if i%1000==999: pipe.execute()
pipe.execute()
dt=time.perf_counter()-t
used=r.info("memory")["used_memory"]-base
print("fan-out of one post to %d timelines: %.2f s (%.0f timeline writes/s), %.0f bytes per one-entry timeline"%(followers,dt,followers/dt,used/followers))
# a full timeline of 800 entries
for i in range(1,801): r.zadd("full",{post_id+i:post_id+i})
m=r.memory_usage("full"); print("one timeline of 800 entries: %d bytes (%.1f bytes per entry)"%(m,m/800))
# trim keeps the newest 800
for i in range(801,1001): r.zadd("full",{post_id+i:post_id+i}); r.zremrangebyrank("full",0,-(KEEP+1))
print("after 1000 inserts with trim: length",r.zcard("full"),"oldest kept offset",int(r.zrange("full",0,0)[0])-post_id)
# cursor pagination, newest first, exclusive cursor
page1=r.zrevrangebyscore("full","+inf","-inf",start=0,num=5); cur=int(page1[-1])
page2=r.zrevrangebyscore("full",f"({cur}","-inf",start=0,num=5)
print("page1",[int(x)-post_id for x in page1],"page2",[int(x)-post_id for x in page2])

layouts.py: the memory-layout comparison:

import redis, struct
r=redis.Redis(port=6399); r.flushall()
base=7_000_000_000_000
def size(key): return r.memory_usage(key)
for n in (100,128,129,200,800):
    ids=[base+i for i in range(n)]
    r.delete("z","l","b","zs")
    r.zadd("z",{str(i):i for i in ids})                                  # sorted set, member = id, score = id
    r.rpush("l",*[str(i) for i in reversed(ids)])                      # list of ids, newest first, as text
    r.set("b",b"".join(struct.pack(">Q",i) for i in reversed(ids)))    # one binary string, 8 bytes per id
    print("%4d entries | sorted set %6d B (%5.1f/entry, %s) | list %6d B (%5.1f/entry, %s) | binary string %6d B (%4.1f/entry)"%(
        n,size("z"),size("z")/n,r.object("encoding","z").decode(),size("l"),size("l")/n,r.object("encoding","l").decode(),size("b"),size("b")/n))

pag.py: OFFSET against keyset on PostgreSQL, and the duplicates test:

import psycopg, time, statistics
c=psycopg.connect("host=/tmp port=5499 user=postgres dbname=postgres",autocommit=True)
c.execute("DROP TABLE IF EXISTS timeline")
c.execute("CREATE TABLE timeline (user_id int, post_id bigint, created_at timestamptz, PRIMARY KEY (user_id, created_at, post_id))")
# one user with 500k timeline entries, ids increasing with time; plus 1000 other users x 500 entries
c.execute("""INSERT INTO timeline SELECT 1, g, timestamptz '2026-01-01' + g * interval '1 second' FROM generate_series(1,500000) g""")
c.execute("""INSERT INTO timeline SELECT 2+ (g % 1000), g, timestamptz '2026-01-01' + g * interval '1 second' FROM generate_series(1,500000) g""")
c.execute("ANALYZE timeline")
def timeit(sql,args=()):
    ts=[]
    for _ in range(7):
        t=time.perf_counter(); c.execute(sql,args).fetchall(); ts.append((time.perf_counter()-t)*1000)
    return statistics.median(ts)
print("rows",c.execute("select count(*) from timeline").fetchone()[0])
for page in (1,100,1000,10000):
    off=(page-1)*20
    t_off=timeit("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20 OFFSET %s",(off,))
    # keyset: the cursor is the last (created_at, post_id) of the previous page
    cur=c.execute("SELECT created_at, post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 1 OFFSET %s",(max(off-1,0),)).fetchone()
    t_key=timeit("SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id) < (%s,%s) ORDER BY created_at DESC, post_id DESC LIMIT 20",cur)
    print("page %5d (offset %6d): OFFSET %.2f ms   keyset %.2f ms"%(page,off,t_off,t_key))
print(c.execute("EXPLAIN SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id) < ('2026-01-03','1') ORDER BY created_at DESC, post_id DESC LIMIT 20").fetchall()[0][0])
# duplicates with OFFSET when new items arrive between page 1 and page 2
ids1=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20")]
last=c.execute("SELECT created_at, post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 1 OFFSET 19").fetchone()
c.execute("INSERT INTO timeline SELECT 1, g, timestamptz '2026-01-01' + g*interval '1 second' FROM generate_series(600001,600005) g")  # 5 new posts
off2=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20 OFFSET 20")]
key2=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id)<(%s,%s) ORDER BY created_at DESC, post_id DESC LIMIT 20",last)]
print("5 new posts arrive between page 1 and 2:")
print("  OFFSET page 2 repeats %d posts already seen on page 1"%len(set(ids1)&set(off2)))
print("  keyset page 2 repeats %d"%len(set(ids1)&set(key2)))

Sources

1. Markus Winand, Use The Index, Luke: paging through results without OFFSET (the seek method). Why OFFSET gets slower and how keyset paging avoids it.
2. Raffi Krikorian, Timelines at Scale (QCon, 2012). Twitter's fan-out on write for home timelines and how celebrity accounts are handled differently.
3. Redis documentation, Sorted sets and the commands ZADD, ZREVRANGEBYSCORE, ZREMRANGEBYRANK.
4. Nathan Bronson et al., TAO: Facebook's Distributed Data Store for the Social Graph, USENIX ATC 2013. Reads vastly outnumber writes in a social graph, and the caching layer built for it.
5. PostgreSQL documentation, LIMIT and OFFSET and row-wise comparison (used by the keyset query).
6. Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly, 2017. The Twitter timeline example in chapter 1 (describing load) and the chapters on replication and stream processing.
7. Alex Xu, System Design Interview, 2020, chapter "Design a news feed system". The standard interview treatment of this problem.

Practise this topic: System Design Distributed Systems & Messaging

More guides