Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

System DesignSenior19 phút đọc

Thiết kế news feed kiểu Threads: push, pull, hybrid và người nổi tiếng

Ôn 13 thẻ
Trong bài này

News feed là đề system design kinh điển vì nó buộc bạn chọn giữa ghi đắt và đọc đắt. Bài này đi đủ các bước của một buổi phỏng vấn cho một mạng xã hội kiểu Threads: từ yêu cầu, phép tính, tới mô hình lai push/pull và các chi tiết như celebrity, user không hoạt động, bộ đếm like. Đọc trước bài URL shortener nếu muốn xem khung trình bày 45 phút đầy đủ.

1. Hỏi yêu cầu

Ý chính: chốt năm chức năng (theo dõi, đăng bài, thông báo, feed, reaction) và hỏi ngay câu quyết định thiết kế: user quan tâm bài nào nhất.

Chức năng:

  • B theo dõi (follow) A.
  • A đăng bài, chỉ có chữ.
  • B nhận thông báo khi A đăng bài.
  • Mỗi user có một feed, sắp mới nhất trước (reverse chronological), chưa cần xếp hạng bằng ML.
  • B reaction bài: like, comment, share; hiển thị số reaction.
Câu hỏi Trả lời
Bao nhiêu user, bao nhiêu DAU? 500M user, 50M DAU
Mỗi user đăng bao nhiêu bài/ngày? 1 bài mỗi DAU
Trung bình bao nhiêu comment/bài? 10
User quan tâm bài nào nhất? bài trong 7 ngày gần nhất và bài trending

Câu cuối quan trọng nhất: nó cho phép chỉ cache 7 ngày và bỏ qua dữ liệu cũ khi dựng feed.

Phi chức năng: trả feed dưới 100 ms; bài mới xuất hiện ở feed follower trong vài giây; mở rộng được; sẵn sàng cao; chấp nhận eventual consistency (feed của B chậm vài giây so với lúc A đăng là được).

2. Ước lượng

Ý chính: ghi bài ít (~580/giây), đọc feed nhiều hơn 10 lần, và thứ đắt nhất là fan-out: 50M bài × 200 follower = 10 tỷ lần ghi inbox mỗi ngày.

Giả định thêm (nói rõ khi phỏng vấn): mỗi DAU mở feed 10 lần/ngày, trung bình 200 follower, bài 3 KB (slide cho, khá rộng rãi với bài chỉ có chữ), comment 500 byte.

  • Đăng bài: 5 × 10⁷ / 10⁵ ≈ 500–580/giây, đỉnh ×3 ≈ 1,7K/giây.
  • Comment: 10 × 50M = 500M/ngày ≈ 5,8K/giây.
  • Đọc feed: 50M × 10 = 5 × 10⁸/ngày ≈ 5,8K/giây, đỉnh ×5 ≈ 30K/giây. Mỗi lần đọc còn kéo 20 bài, tức ~600K lần đọc bài/giây lúc đỉnh, phải phục vụ từ cache.
  • Fan-out nếu push hết: 5 × 10⁷ × 200 = 10¹⁰ lần ghi inbox/ngày ≈ 116K/giây. Chỉ push cho user hoạt động (giả sử 20% follower) còn ~23K/giây.
  • Lưu trữ 5 năm: mỗi bài kèm comment = 3 + 10 × 0,5 = 8 KB; 8 KB × 5 × 10⁷ × 1.825 ngày ≈ 730 TB (slide làm tròn 2.000 ngày ra 800 TB); ×3 replica ≈ 2,2 PB.
  • Cache bài 7 ngày: 3 KB × 5 × 10⁷ × 7 ≈ 1 TB, một cụm Redis vài chục node.
  • Cache feed: mỗi user giữ 200 post id × 8 byte ≈ 1,6 KB; 50M DAU ≈ 80 GB (thêm overhead cấu trúc Redis có thể gấp vài lần).

3. API và data model

Ý chính: feed là danh sách id có thứ tự theo từng user, phân trang bằng cursor. Bảng nào cũng partition theo đúng thứ được tra: bài theo post_id, feed theo user_id, outbox theo author_id.

POST /api/v1/posts                      { "content": "..." }           → 201 { "postId": "..." }
GET  /api/v1/feed?cursor=<postId>&limit=20                             → 200 { "items": [...], "nextCursor": "..." }
POST /api/v1/users/{id}/follow          → 204
POST /api/v1/posts/{id}/reactions       { "type": "LIKE" }             → 204
GET  /api/v1/posts/{id}/comments?cursor=...

Feed dùng cursor (id bài cuối đã xem), không dùng offset: bài mới chèn lên đầu sẽ làm offset lệch và lặp bài (xem REST API nâng cao).

-- ScyllaDB (CQL). post_id là Snowflake: tăng theo thời gian nên sắp được.
CREATE TABLE posts (post_id bigint PRIMARY KEY, author_id bigint, content text,
                    status text, created_at timestamp, updated_at timestamp);

CREATE TABLE user_posts (author_id bigint, post_id bigint,          -- outbox của tác giả
                         PRIMARY KEY (author_id, post_id)) WITH CLUSTERING ORDER BY (post_id DESC);

CREATE TABLE feed (user_id bigint, post_id bigint, author_id bigint, -- inbox của người đọc
                   PRIMARY KEY (user_id, post_id)) WITH CLUSTERING ORDER BY (post_id DESC)
                   AND default_time_to_live = 2592000;              -- giữ 30 ngày

CREATE TABLE followers (user_id bigint, follower_id bigint, PRIMARY KEY (user_id, follower_id));
CREATE TABLE following (user_id bigint, followee_id bigint, PRIMARY KEY (user_id, followee_id));

Slide có cột order trong bảng Feed; dùng post_id kiểu Snowflake làm clustering key thì thứ tự có sẵn và không cần cột riêng. User và gói dịch vụ để ở PostgreSQL.

4. Push, pull hay lai

Ý chính: push dồn chi phí vào lúc ghi để đọc rẻ; pull dồn vào lúc đọc để ghi rẻ. Không mô hình nào sống được một mình với cả người thường lẫn celebrity, nên chọn lai.

Push (fan-out on write). Mỗi user có outbox (bài mình đăng) và inbox (bài của người mình theo dõi). Đăng bài là bỏ thư vào outbox, rồi hệ thống như bưu tá chép post id vào inbox của từng follower. Đọc feed chỉ là đọc inbox.

Pull (fan-out on read). Không có inbox. Lúc mở feed, lấy danh sách người mình theo dõi, đọc bài mới nhất từ outbox của từng người, trộn và sắp.

Push Pull
Đọc feed rất nhanh, một lần đọc inbox chậm: N lần đọc outbox rồi trộn
Đăng bài đắt: ghi vào inbox của mọi follower rẻ: một lần ghi
Celebrity 100M follower 100M lần ghi cho một bài, bài tới follower trễ hàng phút không vấn đề
User không hoạt động phí công và chỗ chép bài cho người không đọc không tốn gì
Unfollow phải dọn bài cũ trong inbox tự đúng
Theo dõi chủ đề (tech, travel) phải fan-out theo cả chủ đề dễ thêm nguồn

Slide kết luận “chọn pull vì dễ mở rộng”, rồi thiết kế cuối cùng lại là lai. Mình nói thẳng: chọn lai, vì pull thuần không đạt 100 ms khi user theo dõi 500 người.

flowchart LR
  A[Tác giả đăng bài] --> PS[Post service]
  PS --> PDB[(posts, user_posts)]
  PS --> K[Kafka: post-created]
  K --> FB[Feed builder]
  FB -->|tác giả thường, follower đang hoạt động| IN[(Inbox: Redis + feed table)]
  FB -.->|celebrity| X[Không fan-out, chỉ cache bài gần đây]
  R[Người đọc mở feed] --> FS[Feed service]
  FS --> IN
  FS -->|pull bài mới của celebrity mình theo dõi| CC[(Cache bài gần đây của celebrity)]
  FS --> H[Hydrate: nội dung, tác giả, bộ đếm]

Đường ghi: feed builder

  1. Post service lưu bài, ghi user_posts, phát sự kiện post-created vào Kafka.
  2. Feed builder đọc sự kiện, hỏi relationship service: tác giả là người thường hay celebrity (ví dụ > 100K follower)?
  3. Người thường: lấy follower theo trang 1.000 người, lọc ra người còn hoạt động, ghi post id vào inbox của họ (Redis LPUSH + LTRIM giữ 200 phần tử, và bảng feed).
  4. Celebrity: không fan-out. Chỉ đẩy bài vào cache “bài gần đây của celebrity”.

Đường đọc: trộn và hydrate

  1. Đọc inbox đã tính sẵn (200 id mới nhất) từ Redis.
  2. Lấy danh sách celebrity mình theo dõi (thường ít, vài chục), đọc bài mới nhất của họ từ cache.
  3. Trộn các danh sách đã sắp (k-way merge), lấy 20 id đầu sau cursor.
  4. Hydrate: MGET nội dung bài, thông tin tác giả, bộ đếm từ cache; bỏ bài đã xoá hoặc tác giả đã bị unfollow.

Ngân sách 100 ms: đọc inbox ~2 ms, đọc bài celebrity ~5 ms, hydrate song song ~10 ms. Còn dư cho mạng và serialize.

Chi tiết đường ghi: chia trang follower, idempotent và ưu tiên
  • Chia việc: một sự kiện post-created của tác giả 50K follower sinh 50 việc con (mỗi việc 1.000 follower) vào topic fanout-tasks. Nhiều worker xử lý song song; một worker chết thì Kafka giao lại việc đó.
  • Idempotent: ghi inbox bằng khoá (user_id, post_id) nên giao lại không tạo trùng. Với Redis list, kiểm tra trước bằng một set phụ hoặc dùng ZSET với score = post_id (ZADD tự idempotent).
  • Ưu tiên: fan-out cho user đang online trước (đọc từ presence), user offline nhưng còn “hoạt động” sau.
  • Backpressure: khi worker tụt lại (Kafka lag tăng), feed chậm nhưng không mất; theo dõi lag như một SLO “bài xuất hiện trong feed trong 5 giây”.
  • Unfollow: không dọn inbox ngay. Lúc hydrate, lọc bài của người không còn theo dõi bằng tập following trong cache. Job nền dọn sau.
  • Xoá bài: đổi status; lúc hydrate bỏ bài có status khác ACTIVE. Không cần đi xoá ở 10 triệu inbox.

5. Theo dõi user hoạt động

Ý chính: fan-out cho người không mở app là phí. Đánh dấu user “hoạt động” bằng heartbeat khi mở app, giới hạn tần suất bằng Redis, và để một service phân nhóm đổi trạng thái sau 7 ngày im lặng.

  • Heartbeat = mở app hoặc làm mới feed. Định nghĩa “hoạt động” là quyết định nghiệp vụ (đăng nhập trong 7 ngày, ví dụ).
  • Quá nhiều lượt: 50M DAU × vài chục lần/ngày. Chặn bằng SET user:active:{id} <ts> NX EX 86400: chỉ lần đầu trong ngày mới đi tiếp vào hệ thống, các lần sau dừng ở Redis.
  • Lần đầu trong ngày phát sự kiện vào topic user-status; segmentation service cập nhật tập user hoạt động. Sau 7 ngày không có sự kiện, user thành “không hoạt động” (đây chính là bài toán liveness và timing wheel ở quy mô ngày).
  • User quay lại sau thời gian dài: inbox rỗng. Lần đầu dựng feed bằng pull, ghi kết quả vào inbox, từ đó nhận push như bình thường.

Ý chính: reaction ghi một dòng theo khoá (post_id, user_id) để không đếm trùng, còn số đếm hiển thị đi qua Kafka và được gộp theo lô trước khi cộng vào Redis.

  • Ghi reaction: bảng reactions (post_id, user_id, type): like hai lần vẫn là một dòng. Phát sự kiện vào topic reactions.
  • Counter service gom sự kiện trong 1 giây hoặc 10 sự kiện, rồi HINCRBY post:counters:{id} likes 37 một lần. Một bài viral 50K like/giây chỉ thành vài nghìn lệnh Redis.
  • Định kỳ chép bộ đếm từ Redis xuống DB. Số hiển thị lệch vài giây hay vài đơn vị là chấp nhận được.
  • Thông báo: notification service nghe post-created. Với celebrity, gửi thông báo theo lô và giới hạn tốc độ, ưu tiên user bật thông báo cho tác giả đó.
  • Trending: một job luồng tính điểm tương tác có giảm dần theo thời gian, ví dụ (likes + 2·comments + 3·shares) / (tuổi_giờ + 2)^1,5, giữ top-k bằng ZSET. Rule engine hoặc mô hình ML gắn nhãn chủ đề (tech, business, health) để có trending theo chủ đề.

7. Thiết kế tổng thể

Ý chính: mỗi service sở hữu dữ liệu của mình, nói chuyện bất đồng bộ qua Kafka. Feed builder là trái tim của đường ghi, feed service là trái tim của đường đọc.

flowchart TB
  C[Client] --> GW[API gateway]
  GW --> PS[Post service]
  GW --> FS[Feed service]
  GW --> RS[Reaction service]
  GW --> REL[Relationship service]
  GW --> LV[Liveness service]
  PS --> KP[Kafka: post-created]
  KP --> FB[Feed builder]
  KP --> NS[Notification service]
  FB --> FD[(Feed: Redis + ScyllaDB)]
  FS --> FD
  RS --> KR[Kafka: reactions]
  KR --> CS[Counter service]
  CS --> RC[(Redis counters)]
  LV --> KU[Kafka: user-status]
  KU --> SG[Segmentation service]
  FB --> SG
  FB --> REL

Về chỗ lưu quan hệ follow: slide dùng graph database (Neo4j). Cho feed, chỉ cần tra một bước “ai theo dõi A” và “A theo dõi ai”, hai bảng kề (followers, following) trên ScyllaDB là đủ và dễ mở rộng hơn. Graph DB đáng giá khi cần gợi ý “bạn của bạn” nhiều bước.

Các tình huống lỗi và cách hệ thống phản ứng
Sự cố Ảnh hưởng Phản ứng
Feed builder tụt lại (Kafka lag) bài mới xuất hiện chậm thêm worker, ưu tiên user online; feed vẫn đọc được
Mất Redis inbox của một shard user thuộc shard đó thấy feed rỗng dựng lại từ bảng feed trên ScyllaDB hoặc pull
Celebrity đăng bài, triệu người mở cùng lúc key bài đó nóng cache trong tiến trình vài giây, nhân bản key nóng
Relationship service chậm feed builder không biết thường hay celebrity cache phân loại tác giả, mặc định coi là celebrity (không fan-out) khi không chắc
Counter service chết số like đứng yên sự kiện còn trong Kafka, xử lý tiếp khi sống lại; số đếm “eventually” đúng
Notification gửi trùng user nhận hai thông báo khoá idempotency theo (user_id, post_id) với TTL

8. Trình bày trong 45 phút

Ý chính: dành 5 phút yêu cầu, 5 phút ước lượng, 10 phút API và data model, 15 phút cho push/pull/hybrid (đây là phần người phỏng vấn muốn nghe), 7 phút cho lỗi và mở rộng, 3 phút tóm tắt.

  1. 0–5: yêu cầu. Hỏi ngay “user quan tâm bài nào” và “feed sắp theo thời gian hay xếp hạng”.
  2. 5–10: ước lượng. Nêu con số fan-out 116K ghi/giây: đây là lý do cả bài tồn tại.
  3. 10–20: API (cursor), bảng posts, user_posts, feed, followers.
  4. 20–35: vẽ push, nêu vấn đề celebrity; vẽ pull, nêu vấn đề latency; chốt hybrid, đường ghi và đường đọc, user hoạt động.
  5. 35–42: bộ đếm, thông báo, trending, các sự cố.
  6. 42–45: ba quyết định chính: hybrid fan-out, feed chỉ lưu id rồi hydrate, chỉ push cho user hoạt động.

Quy ước vẽ sơ đồ và mẹo trình bày có ở bài URL shortener. Bài tập về nhà của buổi này (thiết kế hệ thống chat kiểu Discord) có lời giải riêng ở bài thiết kế hệ thống chat.

Ghi nhớ

  • Tự tính được đọc feed, ghi bài và fan-out mỗi giây từ DAU, và chỉ ra chỗ slide sai.
  • So sánh được push và pull trên sáu tiêu chí, và giải thích vì sao chọn lai.
  • Vẽ được đường ghi (feed builder) và đường đọc (trộn, hydrate) của mô hình lai.
  • Biết cách theo dõi user hoạt động mà không làm quá tải hệ thống.
  • Biết cách đếm like cho bài viral mà không có dòng hay key nóng.

Câu hỏi phỏng vấn

Mid

Fan-out on write và fan-out on read khác nhau thế nào?

On write (push): đăng bài thì chép post id vào inbox mọi follower, đọc feed rất nhanh. On read (pull): đọc feed mới gom bài từ những người mình theo dõi, ghi rẻ nhưng đọc chậm.

Push hỏng với celebrity và user không hoạt động; pull hỏng với latency khi theo dõi nhiều người. Thực tế dùng lai.

Vì sao feed chỉ lưu post id, không lưu cả nội dung bài?

Vì một bài nằm trong hàng nghìn inbox: lưu nội dung thì tốn gấp nghìn lần bộ nhớ và mỗi lần sửa hay xoá bài phải cập nhật hàng nghìn chỗ.

Lưu id (8 byte), lúc đọc hydrate nội dung, tác giả, bộ đếm từ cache bằng một lệnh MGET. Bài bị xoá thì lọc lúc hydrate.

Vì sao phân trang feed bằng cursor thay vì offset?

Vì bài mới liên tục chèn lên đầu: với offset, trang 2 bị đẩy lệch và người dùng thấy lại bài đã xem hoặc bỏ sót bài.

Cursor là post id cuối đã trả; trang sau lấy các bài có id nhỏ hơn. Với post id kiểu Snowflake, đó chính là thứ tự thời gian.

Senior

Một celebrity 100 triệu follower đăng bài. Hệ thống của bạn làm gì?

Không fan-out. Bài chỉ vào cache “bài gần đây của celebrity”; follower nào mở feed thì feed service kéo bài đó về và trộn với inbox.

Thông báo thì gửi theo lô có giới hạn tốc độ. Key của bài đó sẽ rất nóng, nên thêm cache trong tiến trình và nhân bản key.

Thiết kế đường đọc feed để đạt dưới 100 ms.

Đọc inbox tính sẵn từ Redis, đọc bài mới của các celebrity đang theo dõi từ cache, trộn k-way lấy 20 id, rồi hydrate song song bằng MGET.

Không có lần đọc DB nào trên đường nóng. Inbox trống (user mới quay lại) thì dựng bằng pull một lần rồi lưu lại.

User bỏ theo dõi A. Bài của A trong inbox của họ xử lý thế nào?

Không xoá ngay; lúc hydrate lọc bỏ bài của người không còn trong tập following (đã cache), và để job nền dọn inbox sau.

Xoá đồng bộ ở inbox là ghi thêm không cần thiết; lọc lúc đọc rẻ vì tập following đã nằm trong cache.

Làm sao giảm chi phí fan-out cho hàng trăm triệu user không hoạt động?

Theo dõi user hoạt động bằng heartbeat khi mở app (giới hạn bằng SET NX EX một lần mỗi ngày), chỉ push cho người hoạt động; ai quay lại sau thời gian dài thì dựng feed bằng pull một lần.

Giảm fan-out theo tỉ lệ user hoạt động, đổi lại thêm liveness service, segmentation service và đường cold start.

Bộ đếm like cho bài viral 50K like mỗi giây: thiết kế thế nào?

Mỗi like ghi một dòng (post_id, user_id) để không trùng, phát sự kiện qua Kafka; counter service gộp theo lô rồi HINCRBY một lần, định kỳ chép xuống DB.

Không UPDATE ... SET likes = likes + 1 trực tiếp (dòng nóng), không COUNT(*) lúc đọc. Có thể chia bộ đếm thành nhiều key con.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
fan-out /ˈfæn.aʊt/ toả ra nhiều nơi “Fan-out on write makes reads cheap but writes expensive.”
inbox / outbox /ˈɪn.bɑːks/ /ˈaʊt.bɑːks/ hộp thư đến / đi “Each user has an outbox of their own posts and an inbox of others’.”
celebrity problem /səˈleb.rə.ti ˈprɑː.bləm/ vấn đề người nổi tiếng “The celebrity problem is why I don’t push for big accounts.”
hydrate /ˈhaɪ.dreɪt/ điền dữ liệu đầy đủ vào id “The feed stores IDs, and we hydrate them from the post cache.”
reverse chronological /rɪˈvɝːs ˌkrɑː.nəˈlɑː.dʒɪ.kəl/ mới nhất trước “For now the feed is reverse chronological, no ranking.”
cursor-based pagination /ˈkɝː.sɚ beɪst ˌpædʒ.əˈneɪ.ʃən/ phân trang bằng con trỏ “Cursor-based pagination avoids duplicates when new posts arrive.”
eventual consistency /ɪˈven.tʃu.əl kənˈsɪs.tən.si/ nhất quán sau một lúc “A few seconds of delay in the feed is acceptable.”
hot partition /hɑːt pɑːrˈtɪʃ.ən/ partition bị dồn tải “A celebrity’s follower list becomes a hot partition.”
engagement /ɪnˈɡeɪdʒ.mənt/ mức tương tác “Trending is scored by engagement with time decay.”
cold start /koʊld stɑːrt/ khởi động khi chưa có dữ liệu “A returning user has a cold start, so we build their feed by pulling.”

Ghi chép dựa trên khoá System Design (Ronin Engineer), viết lại theo cách hiểu của mình.