News Feed: fan-out on write, fan-out on read và người nổi tiếng

Đề: user A follow B, C, D. Mở app, A thấy bài của B, C, D được sắp xếp phù hợp. Nghe đơn giản, nhưng có một bài toán thú vị: tính feed lúc đọc hay lúc ghi?

1. Requirements

• Đăng bài (text, ảnh). Follow/unfollow.
• Xem home feed: bài của người mình follow, mới nhất trước, cuộn vô hạn.
• Non-functional: mở feed < 200ms. Bài mới xuất hiện trong vài giây là đủ (eventual consistency chấp nhận được).

2. Ước lượng

300M DAU, mỗi người mở feed 10 lần/ngày → 3B feed read/ngày ≈ 35,000 read/giây
Mỗi người đăng 0.5 bài/ngày → 150M post/ngày ≈ 1,700 write/giây
Trung bình 200 follower/người

Read gấp ~20 lần write. Hệ thống read-heavy. Đọc phải rẻ.

3. API & data model

POST /posts                       { "content": "...", "mediaIds": [...] }
GET  /feed?cursor=<postId>&limit=20  → { "items": [...], "nextCursor": "p880" }
POST /users/{id}/follow

POST   (shard theo author_id)   post_id (Snowflake, tăng theo thời gian), author_id, content, created_at
FOLLOW (shard theo follower_id + bảng ngược theo followee_id)
FEED   (Redis, theo user_id)    feed:{userId} = sorted set [postId ...]  (giữ ~500 mục mới nhất)

Dùng cursor thay vì OFFSET: bài mới chèn liên tục, offset sẽ trùng hoặc sót bài.

4. Cách 1: Fan-out on Read (pull)

A mở feed
 ↓ tìm danh sách A follow: B, C, D, ...
 ↓ query bài mới của từng người
 ↓ merge + sort
 ↓ trả về

Ưu: đăng bài rất rẻ. Nhược: A follow 5.000 người thì mỗi lần mở feed phải query/merge rất nhiều. Read latency cao, đúng ở chỗ hệ thống chịu tải nhiều nhất.

5. Cách 2: Fan-out on Write (push)

B đăng POST-123, B có 1,000 follower
POST-123 ├→ feed:A
         ├→ feed:X
         └→ feed:Y ...
A mở feed → ZREVRANGE feed:A → đã tính sẵn

Ưu: đọc cực nhanh. Nhược: write amplification, một bài thành 1.000 lần ghi.

6. Kiến trúc

                    User
                     │
                 API Gateway
            ┌────────┴────────┐
            ▼                 ▼
       Post Service       Feed Service ──► Redis feed:{userId}
            │                 │                 (miss → rebuild từ Post DB)
         Post DB              └──► Post cache (batch get nội dung theo postId)
            │ outbox
            ▼
     POST_CREATED (Kafka)
            │
            ▼
     Fan-out Workers ──► Follow Service (danh sách follower)
            │
            ▼
     ZADD feed:{follower} postId   (ZREMRANGEBYRANK giữ 500 mục)

Media → Object Storage + CDN

Feed chỉ lưu postId, không copy nội dung. Khi đọc thì lấy 20 id rồi batch get nội dung từ cache. Sửa bài không phải sửa hàng nghìn feed.

7. Code: fan-out worker

@Component
@RequiredArgsConstructor
public class FanoutWorker {
    private static final int FEED_SIZE = 500;
    private final StringRedisTemplate redis;
    private final FollowClient follows;

    @KafkaListener(topics = "post-created", groupId = "fanout")
    public void onPostCreated(PostCreated e) {
        if (e.authorFollowerCount() > 100_000) return;            // celebrity: để lúc đọc
        double score = e.createdAt().toEpochMilli();
        follows.forEachFollowerPage(e.authorId(), 1_000, page ->
            redis.executePipelined((RedisCallback<Object>) conn -> {
                for (Long followerId : page) {
                    byte[] key = ("feed:" + followerId).getBytes();
                    conn.zSetCommands().zAdd(key, score, e.postId().toString().getBytes());
                    conn.zSetCommands().zRemRange(key, 0, -FEED_SIZE - 1);
                }
                return null;
            }));
    }
}

ZADD cùng postId hai lần vẫn chỉ một phần tử, nên worker chạy lại (at-least-once) không làm trùng bài.

8. So sánh

Đúng, đó chính là celebrity problem.

1 post × 100M follower = 100M lần ghi Redis 💥
Ở 1M ghi/giây cũng mất ~100 giây, chặn hàng đợi của mọi người khác

1. Hybrid

User thường (< 100k follower) → fan-out on write
Celebrity (≥ 100k follower)   → fan-out on read

A mở feed:
  feed:A (đã tính sẵn)
     +
  bài mới của các celebrity A follow (thường chỉ vài chục người, mỗi người cache "recent posts")
     ↓
  merge theo thời gian / điểm → 20 bài

public List<Long> homeFeed(long userId, long cursor, int limit) {
    List<Long> pushed = feedCache.range(userId, cursor, limit);
    List<Long> pulled = follows.celebritiesOf(userId).stream()
            .flatMap(c -> recentPosts.of(c, cursor, limit).stream())   // cache sẵn theo celebrity
            .toList();
    return Stream.concat(pushed.stream(), pulled.stream())
            .sorted(Comparator.reverseOrder())        // postId Snowflake ~ thời gian
            .limit(limit)
            .toList();
}

2. Thêm hai tối ưu

• Chỉ fan-out cho user active: người 30 ngày không mở app thì bỏ qua; khi họ quay lại thì rebuild feed theo fan-out on read.
• Tách hàng đợi: worker fan-out của tài khoản lớn chạy ở topic riêng để không chặn người khác (bulkhead).

System Design là trade-off, không có một thuật toán dùng cho mọi trường hợp.

Đúng, nhưng trong phỏng vấn hãy bắt đầu bằng chronological. Đừng tự nhảy vào ML nếu đề chỉ yêu cầu feed cơ bản. Sau đó mới nói hướng mở rộng.

1. Ranking ngắn gọn

Bước 1 (candidate): lấy ~500 postId từ feed:{user} + celebrity
Bước 2 (score)    : score = f(độ mới, quan hệ với tác giả, like/comment, loại nội dung)
Bước 3 (trả về)   : sắp theo score, lấy 20, lưu snapshot cho cursor

Ranking chạy lúc đọc, trên tập ứng viên nhỏ. Fan-out vẫn chỉ đẩy postId.

2. Đếm like: hot row

UPDATE post SET likes = likes + 1 WHERE id = ?
10k like/giây vào một bài → một row bị khoá liên tục

Số like hiển thị lệch vài giây không sao. Cần xác định rõ cái nào là source of truth.

Q1. Fan-out on write và fan-out on read khác nhau thế nào, chọn cái nào?

🇻🇳 Tiếng Việt:

Fan-out on write đẩy postId vào feed của từng follower lúc đăng bài, nên đọc rất nhanh nhưng ghi bị khuếch đại. Fan-out on read tính feed lúc mở app, ghi rẻ nhưng đọc chậm. Feed là read-heavy nên em dùng fan-out on write cho user thường, và fan-out on read cho celebrity, rồi merge lúc đọc.

🇬🇧 English:

Fan-out on write pushes the post id into each follower's feed at posting time, so reads are fast but writes are amplified. Fan-out on read builds the feed when the user opens the app, so writes are cheap but reads are slow. Feeds are read-heavy, so I use fan-out on write for normal users and fan-out on read for celebrities, merging both at read time.

Q2. Feed lưu ở đâu, phân trang thế nào?

🇻🇳 Tiếng Việt:

Em lưu feed trong Redis sorted set theo user, chỉ giữ khoảng 500 postId mới nhất, nội dung bài lấy bằng batch get từ cache. Phân trang bằng cursor theo postId, không dùng offset vì bài mới chèn liên tục. Cache mất thì rebuild từ Post DB, vì feed chỉ là dữ liệu dẫn xuất.

🇬🇧 English:

I store each user's feed as a Redis sorted set holding about 500 recent post ids, and fetch post content with a batch get from cache. Pagination uses a cursor on post id rather than offset, because new posts keep arriving. If the cache is lost we rebuild it from the post database, since the feed is derived data.

Q3. Đăng bài có phải chờ fan-out xong không?

🇻🇳 Tiếng Việt:

Không. Post Service lưu bài và ghi outbox trong cùng transaction, trả 201 ngay. Event POST_CREATED đi qua Kafka tới fan-out worker. Worker idempotent vì ZADD cùng postId không tạo bản trùng.

🇬🇧 English:

No. The post service saves the post and an outbox record in the same transaction and returns 201 immediately. A POST_CREATED event goes through Kafka to fan-out workers, which are idempotent because adding the same post id to a sorted set twice doesn't create a duplicate.

Cách nhớ ngắn gọn

• Read-heavy → tính sẵn lúc ghi (push).
• Celebrity → write explosion → hybrid: push cho thường, pull cho nổi tiếng.
• Feed chỉ chứa postId, Redis sorted set, cursor pagination.
• Fan-out async qua queue. Ranking và đếm like nói sau, ngắn gọn.