Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Cara mendesain news feed: fan-out on write versus fan-out on read, masalah selebriti, feed Redis sorted set, cursor pagination dan ranking, lengkap dengan hitungannya.
Matthews Wong
Software Engineer
Ringkasan Utama
Untuk mendesain news feed, pakai fan-out on write bagi akun biasa: saat seseorang posting, dorong id post ke Redis sorted set setiap follower, sehingga membaca feed hanya satu lookup. Lewati push untuk akun dengan follower sangat banyak dan gabungkan post mereka saat feed dibaca. Paginasi dengan cursor dan ranking hanya beberapa ratus kandidat terbaru.
Feed terlihat seperti satu query: tampilkan post terbaru dari orang yang saya ikuti. Pada tabel kecil memang begitu, cukup join dan ORDER BY, dan itu sudah baik. Lalu Anda menuliskan seberapa sering feed dibuka dibandingkan seberapa sering orang posting, dan join itu menjadi hal paling mahal di seluruh sistem.
Ini desain contoh, bukan cerita pengalaman. Saya belum pernah menjalankan jejaring sosial, jadi setiap angka di bawah berasal dari asumsi yang saya sebutkan dengan hitungan yang ditampilkan, dan perilaku Redis berasal dari dokumentasinya. Stack-nya yang akan saya pakai di satu VPS: Postgres sebagai source of truth, Redis untuk feed, dan service NestJS di depannya.
Fan-out adalah satu event yang menyebar ke banyak tujuan. Wikipedia menjelaskannya dalam messaging sebagai pengiriman pesan ke satu atau beberapa tujuan, mungkin secara paralel. Pada feed, event-nya adalah post baru dan tujuannya adalah timeline semua orang yang mengikuti penulisnya. Keputusan sebenarnya hanya satu: kapan penyebaran itu dikerjakan.
Setiap desain feed adalah pilihan tentang di mana Anda membayar: saat write, sekali per follower, atau saat read, sekali per akun yang diikuti. Mana yang lebih murah bergantung pada perbandingan kedua jumlah itu terhadap seberapa sering tiap event terjadi, jadi bagian berikutnya memberi angkanya.
Tulis asumsi lebih dulu lalu turunkan semuanya darinya. Ini input untuk latihan desain di satu VPS, bukan hasil pengukuran produk nyata, dan sebaiknya Anda ganti dengan data log sendiri.
Assumed inputs (a design exercise, not a measurement):
registered users = 1,000,000
daily active users (DAU) = 200,000
feed opens per DAU per day = 10
posts per DAU per day = 0.5
average followers = 150 (so the average account follows 150 too)
peak vs average = 3x
seconds per day = 86,400
Reads and posts
feed opens per day = 200,000 x 10 = 2,000,000
average opens / s = 2,000,000 / 86,400 = 23.1 peak = 69.4
posts per day = 200,000 x 0.5 = 100,000
average posts / s = 100,000 / 86,400 = 1.16 peak = 3.5
reads per post = 2,000,000 / 100,000 = 20
Fan-out on write (push)
feed inserts per day = 100,000 x 150 = 15,000,000
average inserts / s = 15,000,000 / 86,400 = 173.6 peak = 520.8
per feed open = 1 range query (23.1 / s average)
Fan-out on read (pull)
inserts per day = 100,000 (1 per post)
outbox lookups per day = 2,000,000 x 150 = 300,000,000
average lookups / s = 300,000,000 / 86,400 = 3,472.2 peak = 10,416.7
Pull does 300,000,000 / 15,000,000 = 20x the lookups that push does inserts.
That 20 is just reads per post.Pull melakukan 300 juta lookup outbox per hari dibanding 15 juta insert feed pada push, selisih 20 kali, dan faktor itu sederhana saja: jumlah read per post, yaitu 2.000.000 pembukaan feed dibagi 100.000 post. Selama feed dibuka lebih sering daripada orang posting, yang hampir selalu terjadi, push adalah sisi yang lebih murah untuk dibayar. Harganya, pekerjaan itu tetap dilakukan walau follower tidak pernah membuka aplikasi.
| Model | Pekerjaan per post | Pekerjaan per buka feed | Kelemahan utama | Pilih bila |
|---|---|---|---|---|
| Fan-out on write (push) | Rata-rata 150 insert | 1 range query | Akun raksasa mengubah satu post menjadi lonjakan write; follower tidak aktif tetap diproses | Feed dibuka jauh lebih sering daripada orang posting dan jumlah follower terbatas |
| Fan-out on read (pull) | 1 insert | 150 lookup outbox ditambah merge | Latensi read naik seiring jumlah akun yang diikuti | Graph-nya kecil, atau sebagian besar user jarang membuka feed |
| Hybrid | 150 insert untuk penulis biasa, 1 untuk penulis besar | 1 range query ditambah sekitar 2 lookup outbox | Dua jalur kode dan satu threshold yang perlu disetel | Segelintir akun memegang porsi besar dari seluruh relasi follow |
Tabel ini menunjukkan mengapa tidak ada model yang gratis. Push memindahkan biaya ke write dan storage. Pull menjaga storage tetap kecil tetapi membuat setiap read lebih lambat dan sulit diprediksi, karena latensinya naik sesuai jumlah akun yang diikuti pembaca.
Rata-rata menyembunyikan akun yang merusak push. Anggap satu penulis punya 500.000 follower, separuh dari seluruh user. Satu post dari akun itu berarti 500.000 insert, jauh berbeda dari post rata-rata yang hanya 150.
One author with 500,000 followers (half the user base) posts once:
push inserts = 500,000
average push load = 173.6 inserts / s
500,000 / 173.6 = 2,880 s = 48 minutes of AVERAGE load, from one post
if workers sustain 20,000 inserts / s (assumed, load-test it):
500,000 / 20,000 = 25 s until the last follower's feed has the post
the same account posting 3 times in an hour = 1,500,000 inserts
Hybrid with a 10,000-follower threshold. Assume 20 such accounts average 100,000
followers and post 2 times a day (these posts are part of the 15,000,000 above):
inserts avoided = 20 x 2 x 100,000 = 4,000,000 per day (26.7% of 15,000,000)
push inserts remaining = 15,000,000 - 4,000,000 = 11,000,000 per day
average inserts / s = 11,000,000 / 86,400 = 127.3
Read side, assuming a reader follows 2 of those large accounts:
calls per feed open = 1 feed ZRANGE + 2 outbox ZRANGEs = 3 (pull would be 150)
calls per day = 2,000,000 x 3 = 6,000,000 = 69.4 / s averageAturan hybrid adalah threshold pada jumlah follower. Di bawahnya, push seperti biasa. Pada atau di atasnya, jangan fan-out sama sekali: tulis post hanya ke outbox penulis lalu gabungkan outbox itu ke feed pembaca saat feed dibaca. Pembaca hanya mengikuti segelintir akun semacam itu, sehingga merge hanya butuh beberapa lookup tambahan, bukan ratusan.
const PUSH_FOLLOWER_LIMIT = 10_000; // a starting guess; tune it from fan-out queue lag
const OUTBOX_CAP = 200;
export async function onPostCreated(post: { id: number; authorId: number }) {
// 1. Always write the author's outbox: it is the pull path AND the rebuild source.
const outbox = "outbox:" + post.authorId;
await redis.zadd(outbox, post.id, String(post.id));
await redis.zremrangebyrank(outbox, 0, -(OUTBOX_CAP + 1));
// 2. Large accounts are pulled at read time, so there is nothing to fan out.
const followers = await followerCount(post.authorId); // users.follower_count
if (followers >= PUSH_FOLLOWER_LIMIT) return;
// 3. Everyone else is pushed by a worker, never inside the request.
await fanOutQueue.enqueue({ postId: post.id, authorId: post.authorId });
}Threshold adalah tombol penyetelan, bukan konstanta alam. Saya akan mulai dari 10.000 follower, angka yang saya pilih dan bukan hasil ukur, lalu memantau lag antrean fan-out dan menggesernya. Menggesernya aman karena setiap feed bisa dibangun ulang dari Postgres.
Masukkan hanya id post ke feed, jangan isi post. Biaya satu entri feed jadi sama berapa pun panjang post-nya, edit tidak memerlukan fan-out, dan post yang dihapus tersaring saat id di-hydrate dari Postgres.
Postgres tetap menjadi source of truth untuk post dan follow. Redis menyimpan satu sorted set per user aktif, dengan id post sebagai member dan id yang sama sebagai score, sehingga membaca dari yang terbaru adalah range query. Dokumentasi Redis memberi ZRANGE biaya O(log(N)+M) untuk N elemen dan M hasil, dan ZREMRANGEBYRANK bentuk yang sama, itu sebabnya trim setelah setiap insert murah.
-- Source of truth. Redis feeds are rebuildable from these two tables.
CREATE TABLE posts (
id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY, -- also the Redis score
author_id bigint NOT NULL,
body text NOT NULL,
created_at timestamptz NOT NULL DEFAULT now(),
deleted_at timestamptz -- soft delete
);
CREATE INDEX posts_author_idx ON posts (author_id, id DESC); -- the outbox / pull query
CREATE TABLE follows (
follower_id bigint NOT NULL,
followee_id bigint NOT NULL,
created_at timestamptz NOT NULL DEFAULT now(),
PRIMARY KEY (followee_id, follower_id) -- fan-out: who follows X?
);
CREATE INDEX follows_follower_idx ON follows (follower_id); -- pull: whom do I follow?
-- users.follower_count is a maintained counter, so the hybrid check is one primary-key read.
-- The pure pull query. Correct, easy to measure, and fine until it is not:
SELECT p.id
FROM posts p
WHERE p.author_id IN (SELECT followee_id FROM follows WHERE follower_id = $1)
AND p.deleted_at IS NULL
ORDER BY p.id DESC
LIMIT 20;Worker fan-out yang menulis, di luar request yang membuat post: insert post, enqueue job, kembalikan respons. Worker menelusuri daftar follower dalam halaman keyset dan menulis ke Redis lewat pipeline.
const FEED_CAP = 200; // newest 200 entries per feed
const PAGE_SIZE = 1000;
export async function fanOut(postId: number, authorId: number) {
let afterId = 0;
for (;;) {
// Keyset page over the primary key (followee_id, follower_id). Never OFFSET.
const { rows } = await pg.query(
"SELECT follower_id FROM follows " +
"WHERE followee_id = $1 AND follower_id > $2 " +
"ORDER BY follower_id LIMIT $3",
[authorId, afterId, PAGE_SIZE],
);
if (rows.length === 0) return;
const pipe = redis.pipeline();
for (const { follower_id } of rows) {
const key = "feed:" + follower_id;
// Same member + same score twice is a no-op update, so a retried job is safe.
pipe.zadd(key, postId, String(postId));
// Ranks are 0-based from the LOWEST score; -1 is the newest. Removing 0 .. -201
// leaves exactly the newest 200.
pipe.zremrangebyrank(key, 0, -(FEED_CAP + 1));
}
await pipe.exec();
afterId = rows[rows.length - 1].follower_id;
// Production: skip followers inactive for 30 days; rebuild their feed when they return.
}
}Trim membatasi memori. 200 entri per feed aktif dikali 200.000 feed aktif adalah 40.000.000 entri. Dengan asumsi 50 byte per entri totalnya 2,0 GB, dan angka 50 itu hanya placeholder: ganti dengan hasil MEMORY USAGE pada data Anda sendiri sebelum mempercayai totalnya. User yang scroll melewati 200 entri jatuh ke query Postgres.
Feed di Redis adalah cache, bukan catatan resmi. Jika ia di-flush, fan-out tertinggal, atau ada follower terlewat, jawabannya adalah rebuild dari Postgres, jangan pernah menjadikan Redis satu-satunya salinan. Rancang jalur rebuild sejak hari pertama, karena Anda akan memakainya.
Feed berubah saat orang membacanya, sehingga nomor halaman bergeser: post baru mendorong semuanya ke bawah dan halaman 2 mengulang satu item dari halaman 1. Kasus umumnya sudah saya bahas di post cursor versus offset pagination. Di sini cursor hanyalah id item terakhir yang dikembalikan.
# Score and member are the same unique id.
ZADD feed:42 1001 1001 1002 1002 1003 1003 1004 1004 1005 1005
# Page 1: newest first, 3 entries, no cursor yet.
ZRANGE feed:42 +inf -inf BYSCORE REV LIMIT 0 3
# 1) "1005" 2) "1004" 3) "1003" -> cursor = 1003
# Page 2: strictly below the cursor. A new post (1006) would not shift this page.
ZRANGE feed:42 (1003 -inf BYSCORE REV LIMIT 0 3
# 1) "1002" 2) "1001"
# Wrong: ZRANGE feed:42 +inf -inf BYSCORE REV LIMIT 3 3
# An offset drifts when 1006 arrives, and the server must walk past 3 entries first.Dengan BYSCORE dan REV, ZRANGE mengambil score tertinggi lebih dulu, dan tanda kurung di depan membuat batas bersifat eksklusif, sehingga halaman berikutnya dimulai tepat di bawah id terakhir. Ini hanya bekerja bila tidak ada dua entri dengan score sama, karena Redis mengurutkan score yang sama secara leksikografis dan entri yang kembar di batas halaman akan terlewat. Id unik sebagai score menghindarinya. Dokumentasi juga memperingatkan bahwa offset LIMIT yang besar memaksa Redis melewati sebanyak itu elemen, alasan lain memakai cursor dan bukan offset. Double menyimpan bilangan bulat secara tepat sampai 2 pangkat 53, sekitar 9,0e15, jauh di atas jumlah baris yang realistis.
const PAGE = 20;
export async function readFeed(userId: number, cursor: string | null) {
// "(" makes the bound exclusive: strictly older than the last id already shown.
const max = cursor ? "(" + cursor : "+inf";
const largeAccounts = await largeAccountsFollowed(userId); // usually 0 to a handful
const keys = ["feed:" + userId, ...largeAccounts.map((a) => "outbox:" + a)];
// With BYSCORE + REV the FIRST bound is the highest score, the second the lowest.
const lists = await Promise.all(
keys.map((key) =>
redis.zrange(key, max, "-inf", "BYSCORE", "REV", "LIMIT", 0, PAGE + 1),
),
);
// Merge: ids are numbers below 2^53, so a numeric sort is exact. Fetch one extra to know
// whether another page exists.
const ids = [...new Set(lists.flat())]
.sort((a, b) => Number(b) - Number(a))
.slice(0, PAGE + 1);
const hasMore = ids.length > PAGE;
const pageIds = ids.slice(0, PAGE);
// Hydrate from Postgres. Deleted posts simply do not come back, so a page may be short.
const { rows } = await pg.query(
"SELECT id, author_id, body, created_at FROM posts " +
"WHERE id = ANY($1::bigint[]) AND deleted_at IS NULL",
[pageIds],
);
const byId = new Map(rows.map((r) => [String(r.id), r]));
const items = pageIds.map((id) => byId.get(id)).filter(Boolean);
return { items, nextCursor: hasMore ? pageIds[pageIds.length - 1] : null };
}Ranking adalah tahap kedua di atas feed, bukan model penyimpanan yang berbeda. Ambil kandidat dengan murah dulu: id terbaru dari feed ditambah outbox akun besar. Lalu beri skor dan urutkan hanya itu. Repositori rekomendasi Twitter yang dibuka sebagai open source menggambarkan bentuk yang sama, dengan candidate source, light ranker, heavy ranker berbasis neural network, visibility filter dan mixer, dan menyebut sekitar separuh post di timeline For You berasal dari sumber in-network.
Untuk versi pertama, rumus yang transparan lebih baik daripada model yang tidak bisa Anda debug. Rumus ini ilustrasi saya sendiri, bukan rekomendasi dari sumber mana pun, jadi setel bobotnya terhadap perilaku user Anda yang sebenarnya.
Illustrative score, my own toy formula, not taken from any source:
rank = (1 + 2 x likes + 3 x comments) / (age_hours + 2) ^ 1.5
Post A: 10 likes, 2 comments, 1 hour old
(1 + 20 + 6) / 3 ^ 1.5 = 27 / 5.196 = 5.20
Post B: 100 likes, 10 comments, 12 hours old
(1 + 200 + 30) / 14 ^ 1.5 = 231 / 52.38 = 4.41
Post C: 0 likes, 0 comments, just posted (0 hours)
1 / 2 ^ 1.5 = 1 / 2.828 = 0.35
Chronological order: C, A, B. Ranked order: A, B, C.
Cost of ranking 200 candidates per feed open:
2,000,000 opens x 200 = 400,000,000 score evaluations per day = 4,629.6 / s averageRanking merusak cursor berbasis score murni, karena urutan yang dikembalikan tidak lagi sama dengan urutan yang tersimpan. Pilih salah satu: snapshot daftar id hasil ranking selama beberapa menit lalu paginasi berdasarkan posisi di snapshot, atau tetap paginasi kronologis dan lakukan ranking di dalam tiap halaman. Putuskan mana yang Anda rilis dan sampaikan di produk, karena user sadar ketika feed berubah urutan di depan mata mereka.
Jalankan checklist ini sebelum membangun apa pun.
Yang rusak lebih dulu jarang soal hitungannya. Post yang dihapus dan unfollow meninggalkan id hantu di feed, jadi hydrate dari Postgres dan buang yang sudah tidak ada. Redis yang di-flush melayani feed kosong sampai Anda rebuild secara lazy pada read pertama dari post terbaru tiap akun yang diikuti. Dan lag fan-out saat lonjakan membuat post baru muncul terlambat, jadi pasang alert pada kedalaman antrean, bukan CPU.
Bayar fan-out di tempat yang trafiknya mudah diprediksi. Read lebih banyak daripada post, jadi push penulis biasa ke Redis sorted set per user yang dibatasi ukurannya, perlakukan akun besar sebagai pull, paginasi dengan cursor, dan ranking hanya beberapa ratus kandidat. Jadikan Postgres sumber kebenaran dan semua lapisan lain bisa dibuang.