[SYSTEM DESIGN TẬP 13] CƠN BÃO NGƯỜI NỔI TIẾNG ĐĂNG BÀI 20,600 WRITES/S, TUYỆT KỸ '3 CÁI HÒM' VÀ THUẬT TOÁN HYBRID FAN-OUT ($80.00 ★★★)! 📬⚡

Sau cú chốt hạ $1,999.07 rực rỡ 3 Sao ở trận Flash Sale tập trước, sảnh đấu System Design Arena lập tức mở cổng bước sang Thế Giới 2: High Load. Không còn là câu chuyện giỏ hàng thương mại điện tử, lần này đối thủ của chúng tôi là bài toán kinh điển của mọi kỹ sư phân tán: Bảng tin Mạng xã hội (Activity Feed).

Bước vào Màn 21 (event_sourcing_feed), thằng Đ nhìn đề bài rồi cười khẩy:

• "Mỗi giây có 400 lượt mở timeline mà chỉ có 10 bài đăng mới. Mỗi người theo dõi 50 bạn bè. Dễ quá anh ơi!"

Nó dựng ngay kiến trúc mặc định (timeline: on_read). Nhưng vừa bấm chạy, con Database đã lăn đùng ra chết nghẹn ở giây thứ tư: $$\text{Tải đọc DB} = 400\text{ mở feed/s} \times 50\text{ bạn bè} = \mathbf{20.000\text{ sql_read/s}} \gg 1.500\text{ req/s của DB L}!$$

Mỗi lượt mở timeline là một câu truy vấn JOIN quét ngang 50 tài khoản. Tôi bảo Đ bật chế độ Fan-out on Write (Inbox Model): Khi một người đăng bài (10 req/s), Worker chủ động ship bài viết vào hòm thư riêng (user_inbox) của 50 người bạn ($10 \times 50 = 500\text{ sql_write/s}$). Khi user mở app, chỉ cần SELECT * FROM user_inbox LIMIT 20 tốn đúng $1\text{ query O(1)}$. Tổng tải DB tụt xuống: $$\text{Tổng tải} = 400\text{ đọc} + 500\text{ ghi} = \mathbf{900\text{ req/s}} < 1.500\text{ req/s}!$$

Với 1 App Server Tier S ($15) và 1 Relational DB Tier L ($50), tổng chi phí cán đích đúng $65.00/tháng (dưới trần $75.00), rinh trọn 3 Sao Màn 21! Thằng Đ vỗ đùi đánh đét:

• "Từ nay chân lý cuộc đời em là Fan-out on Write! Cứ ghi trước vào hòm thư là vô địch thiên hạ!"

1. CƠN ÁC MỘNG MÀN 22: THẦN TƯỢNG ĐĂNG STATUS VÀ CÚ NỔ 20,600 WRITES/S 💥😱

Thế nhưng, đời kỹ sư không bao giờ êm đềm như một bài toán mẫu. Bảng điều khiển chuyển sang Màn 22: fan_out_celebrity (Người nổi tiếng đăng bài).

Đề bài dội một gáo nước lạnh vào mặt hai anh em:

*Mỗi giây có 300 lượt mở timeline, 6 bài đăng thường và 1 bài đăng từ Người nổi tiếng (Celebrity). Người thường có 50 follower, nhưng mỗi Người nổi tiếng sở hữu tới 20,000 follower! Mỗi người dùng theo dõi 50 người, trong đó có đúng 2 Người nổi tiếng.*

Thằng Đ tự tin giữ nguyên chế độ timeline: on_write từ Màn 21:

• "Sợ gì anh, DB L 1.500 req/s lận mà!"

Nó bấm nút Simulate. Giây thứ nhất trôi qua... Giây thứ hai bình yên... Đúng giây thứ ba, sự kiện celebrity_post kích hoạt!

[FATAL ALERT: Relational DB Tier L]
Ngưỡng tối đa: 1.500 req/s. Lưu lượng ghi thực tế: 20.600 writes/s! (Vượt 1.373% công suất!)
Connection Pool: EXHAUSTED (100/100 connections locked). WAL Disk IOPS: 100% SATURATED!
Tỷ lệ rớt gói tin: 98.4%! Latency mở timeline: 14.820 ms!

Toàn bộ màn hình đỏ rực như lò than. Database sập nguồn ngay tắp lự. Thằng Đ hoảng loạn:

• *"Trời đất ơi! Một status của ông Sao Hạng A mà xả ra tới 20.000 lệnh ghi trong một giây! Cộng với 300 lệnh ghi của người thường ($6 \times 50$), tổng tải ghi vọt lên tới hơn 20.600 writes/s! Đến con Database Tier XL khủng nhất giá $200 cũng chỉ chịu được 5.000 req/s, làm sao đỡ nổi 20.600 writes/s hả anh?!"*

Nó luống cuống:

• "Hay là... mình quay xe về lại Fan-out on Read hả anh?"

Tôi kéo nó lại, cầm bút viết lên mặt bàn con số tử thần của phương án Thuần On-Read: $$\text{Tải đọc On-Read} = 300\text{ mở feed/s} \times 50\text{ bạn bè} = \mathbf{15.000\text{ sql_read/s}}!$$ $$+ 6\text{ post thường} + 1\text{ post VIP} = \mathbf{15.007\text{ req/s}}!$$

• *"Mày thấy chưa? Thuần On-Read thì chết vì Đọc ($15.007\text{ req/s}$), mà Thuần On-Write thì vỡ nợ vì Ghi ($20.600\text{ writes/s}$)! Cả hai con đường cực đoan đều dẫn thẳng tới nấm mồ hạ tầng!"*

2. TUYỆT KỸ "3 CÁI HÒM" (HYBRID FAN-OUT) VÀ PHÉP TÍNH THẦN THÁNH 1,201 REQ/S 📬⚡

Thằng Đ ngồi bệt xuống ghế, mặt thất thần:

• "Đọc cũng chết, Ghi cũng chết... Vậy các mạng xã hội triệu người dùng như Twitter, Threads họ sống bằng cách nào hả anh?"

Tôi rót cho nó cốc nước, mỉm cười:

• *"Bí quyết nằm ở tính chất bất đối xứng của đồ thị người dùng (Asymmetric User Graph). Hãy tưởng tượng tài khoản của mày đang theo dõi 50 người: gồm 48 đứa bạn thân bình thường và 2 ông Sao Hạng A (Sơn Tùng M-TP & Cristiano Ronaldo). Tại sao chúng ta phải đối xử với status của Sơn Tùng giống hệt như status của thằng bạn cùng bàn? Đó là lúc Tuyệt kỹ 3 Cái Hòm (Hybrid Fan-Out) xuất chiêu!"*

                     ┌── 48 Bạn Thường ──(On-Write)──> [ Hòm Thư Riêng Của Bạn ] ──┐
[ Người Dùng Mở App ] ┼── Sơn Tùng M-TP ──(On-Read)───> [ Hòm Thư Sơn Tùng M-TP ] ──┼─> [ Trộn 3 Dòng ]
                     └── Ronaldo       ──(On-Read)───> [ Hòm Thư Ronaldo ] ───────┘

Quy tắc phân luồng của "3 Cái Hòm":

1. 48 bạn thường (Fan-out on Write): Mỗi khi bạn bè đăng bài, shipper đẩy thẳng vào Hòm Thư Riêng của mày. Vì bạn thường ít follower, chi phí ghi cực thấp.
2. 2 ông Sao VIP (Bypass Fan-out on Read): Khi Sơn Tùng hay Ronaldo đăng bài, cấm tiệt không cho shipper đi phát 20.000 hòm thư! Họ chỉ ghi đúng 1 dòng duy nhất vào hòm thư cá nhân của chính họ (Hòm Sơn Tùng, Hòm Ronaldo).
3. Lúc mày mở app xem Timeline: App Server chỉ việc mở đúng 3 cái hòm:
   • Mở Hòm Thư Riêng: Đọc 1 lần, lấy trọn bài của 48 bạn bè đã ship sẵn.
   • Mở Hòm Sơn Tùng: Đọc 1 lần để bốc bài mới của Sơn Tùng.
   • Mở Hòm Ronaldo: Đọc 1 lần để bốc bài mới của Ronaldo. $$\mathbf{1\text{ Hòm riêng}} + \mathbf{2\text{ Hòm VIP}} = \mathbf{3\text{ lần đọc SQL / 1 user}}!$$

Hai mắt thằng Đ tròn xoe. Tôi cầm phấn tính toán lượng tải thực tế dội vào Database:

• Tải Đọc: $300\text{ user mở timeline/s} \times 3\text{ hòm} = \mathbf{900\text{ sql_read/s}}$ (gồm 300 đọc hòm riêng + 600 đọc hòm VIP).
• Tải Ghi bạn thường: $6\text{ bài/s} \times 50\text{ follower} = \mathbf{300\text{ sql_write/s}}$.
• Tải Ghi người nổi tiếng: $1\text{ bài/s} \times 1\text{ dòng} = \mathbf{1\text{ sql_write/s}}$.
• TỔNG LƯỢNG SQL CẦN XỬ LÝ: $$\text{Tổng tải DB} = 900\text{ đọc} + 300\text{ ghi thường} + 1\text{ ghi VIP} = \mathbf{1.201\text{ req/s}}!$$

Thằng Đ nhảy dựng lên:

• *"Từ 20.600 req/s tụt xuống đúng 1.201 req/s! Con số $1.201$ nằm gọn gàng bên dưới trần $1.500\text{ req/s}$ của Relational DB Tier L ($50)! Còn App Server Tier S ($15) gánh $300 + 6 + 1 = 307\text{ HTTP req/s}$ ngon lành cành đào! Tổng tiền chỉ vỏn vẹn $65.00/tháng, dư sức ẵm trọn 3 Sao trong ngân sách $80.00!"*

3. THUẬT TOÁN BINARY MAX-HEAP $O(N \log K)$ VÀ SỰ RA ĐỜI CỦA @kido/hybrid-feed 🧩💻

• "Nhưng anh ơi," thằng Đ thắc mắc, "App Server bốc dữ liệu từ 3 cái hòm về thì làm sao ghép thành 1 bảng tin có thứ tự thời gian giảm dần nhanh nhất? Có phải dùng array.concat().sort() không?"

• "Mày dùng .sort() toàn phần với độ phức tạp $O(M \log M)$ thì khi user theo dõi 100 VIP, CPU của App Server sẽ bốc khói! Thuật toán chuẩn Big-Tech để giải quyết bài toán này là K-Way Cursor Merge sử dụng Binary Max-Heap với độ phức tạp tối ưu $O(N \log K)$ (với $K$ là số hòm thư, $N$ là số bài cần lấy cho trang đầu)!"

Tôi mở laptop, gõ trực tiếp đoạn mã nguồn mà sau này trở thành linh hồn của Package thứ 38 trong hệ sinh thái Kido:

// @kido/hybrid-feed - Binary Max-Heap K-Way Cursor Stream Merger
export interface FeedItem { id: string; authorId: string; createdAtMs: number; }

export function kWayMergeFeeds(streams: FeedItem[][], limit = 20): FeedItem[] {
  // Min-Heap theo chiều nghịch đảo để lấy Max timestamp
  const heap: { item: FeedItem; streamIdx: number; itemIdx: number }[] = [];
  const pushHeap = (node: typeof heap[0]) => {
    heap.push(node);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p].item.createdAtMs >= heap[i].item.createdAtMs) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  // Khởi tạo Heap với phần tử đầu tiên của K hòm thư: O(K log K)
  streams.forEach((s, idx) => { if (s.length > 0) pushHeap({ item: s[0], streamIdx: idx, itemIdx: 0 }); });

  const result: FeedItem[] = [];
  while (heap.length > 0 && result.length < limit) {
    const top = heap[0]; // Lấy bài viết mới nhất O(1)
    result.push(top.item);
    // Thay thế đỉnh heap bằng bài kế tiếp của cùng stream đó: O(log K)
    const nextIdx = top.itemIdx + 1;
    if (nextIdx < streams[top.streamIdx].length) {
      heap[0] = { item: streams[top.streamIdx][nextIdx], streamIdx: top.streamIdx, itemIdx: nextIdx };
      siftDown(heap, 0);
    } else {
      heap[0] = heap.pop()!;
      siftDown(heap, 0);
    }
  }
  return result;
}

Và trên tầng nhớ đệm Valkey / Redis, chúng tôi bọc nó bằng lệnh Lua nguyên tử khống chế đúng 800 bài viết cho mỗi hòm thư (LUA_ZADD_CAPPED_TIMELINE), kết hợp L1 In-Memory Cache (TTL 5 giây) cho hòm thư của VIP. Kết quả: 600 lượt đọc hòm thư của Sơn Tùng và Ronaldo mỗi giây được cache nuốt sạch $99.8%$, kéo số lượt đọc DB thực tế từ 900 xuống chỉ còn... hơn 300 req/s!

4. MÀN BẤM NÚT ĐỊNH MỆNH VÀ CÚ NỔ 3 SAO $80.00 🏆✨

Trở lại bàn cờ Màn 22 của System Design Arena:

• App Server: 1 máy Tier S ($15.00/tháng).
• Relational DB: 1 hộp Tier L ($50.00/tháng), cấu hình tùy chọn: timeline: hybrid.
• Tổng chi phí chốt hạ: $65.00/tháng (Ngân sách cho phép: $75.00 – $80.00).

[Users (300 read · 6 post · 1 celeb)] ──http──> [App Server Tier S ($15)]
                                                        │
                                                       sql (1.201 req/s: Push bạn bè + Pull celeb)
                                                        ▼
                                          [Relational DB Tier L ($50 · Hybrid)]

Thằng Đ nín thở, đặt ngón tay bấm SIMULATE!

Đồng hồ 120 giây chạy vùn vụt:

• Giây thứ 10: Sao Hạng A đăng status! Tầng App Server đón bài, ghi đúng 1 dòng vào outbox của thần tượng. Không có bất kỳ vụ nổ fan-out nào xảy ra!
• Giây thứ 30: 300 người dùng liên tục bấm F5 bảng tin. App Server mở nhịp nhàng 3 cái hòm, gom bài qua Binary Max-Heap trong chưa đầy 3.2 ms.
• Tải Database ghim chặt ở mức 1.201 req/s (80.1% công suất), xanh rì từ đầu tới cuối!

╔════════════════════════════════════════════════════════════════════════╗
║                SYSTEM DESIGN ARENA - LEVEL 22: FAN OUT CELEBRITY       ║
║                           KẾT QUẢ CUỐI CÙNG                            ║
╠════════════════════════════════════════════════════════════════════════╣
║  • Tỷ lệ phản hồi Mở timeline (Read Timeline) : 100.0% (Latency: 42 ms)║
║  • Tỷ lệ phản hồi Đăng bài (Normal Post)      : 100.0% (Latency: 38 ms)║
║  • Tỷ lệ phản hồi VIP đăng bài (Celebrity Post): 100.0% (Latency: 29 ms)║
║                                                                        ║
║  ★ CHI PHÍ THỰC TẾ: $65.00 / $80.00                                    ║
║  ★ XẾP HẠNG       : TOP 1% TOÀN CẦU (★★★ 3 SAO XUẤT SẮC!)              ║
╚════════════════════════════════════════════════════════════════════════╝

Thằng Đ đập tay với tôi ăn mừng vang dội. Bài toán hóc búa từng làm đau đầu các kỹ sư kỳ cựu của Twitter đã bị khuất phục hoàn toàn bằng tư duy phân loại đồ thị và thuật toán heap tinh gọn.

Nhưng đúng lúc hai anh em chuẩn bị tắt máy đi ăn lẩu, màn hình phòng đấu bỗng nhấp nháy đèn vàng báo hiệu Màn 23 (search_index_lag):

• "Khoan đã anh Kido... Người dùng đăng bài xong xuôi rồi, sao họ sang thanh Tìm Kiếm gõ từ khóa lại... không thấy bài đâu cả?! Độ trễ đồng bộ Search Index đang bị dồn ứ hàng chục giây kìa!"

Tôi khẽ cười, kéo ghế ngồi lại:

• "Chào mừng chú mày đến với thế giới của Event-Driven Architecture, Change Data Capture (CDC) và Write-Ahead Log. Trận chiến thực sự... giờ mới bắt đầu!"

🧠 Góc Kỹ Sư Thực Chiến (Bài Học System Design)

1. Bản Chất Của Sự Đánh Đổi Fan-out on Read vs. Fan-out on Write:
   • Fan-out on Read (Pull Model): Chi phí ghi $O(1)$, nhưng chi phí đọc bị nhân bội $O(K)$ theo số người theo dõi. Thích hợp cho mạng xã hội ít đọc nhiều viết, hoặc tài khoản có lượng follower khổng lồ.
   • Fan-out on Write (Push / Inbox Model): Chi phí đọc là $O(1)$ truy vấn trên chỉ mục phân trang, nhưng chi phí ghi bị khuếch đại $O(F)$ theo số người hâm mộ. Tối ưu cho người dùng thông thường có ít bạn bè.
2. Kiến Trúc Hybrid Là Chìa Khóa Cho Phân Phối Lũy Thừa (Power-Law Distribution): Mọi đồ thị mạng xã hội đều tuân theo phân phối Pareto (quy tắc 80/20 hoặc 99/1): 1% người nổi tiếng sở hữu 99% lượng follower. Một hệ thống phân tán cấp Tier-1 không bao giờ áp dụng một chính sách cào bằng duy nhất cho tất cả các nút dữ liệu, mà luôn phải áp dụng kiến trúc bất đối xứng: Push cho người bình thường và Pull cho người nổi tiếng.
3. Tối Ưu Hóa K-Way Stream Merge Với Binary Max-Heap: Khi hợp nhất nhiều luồng dữ liệu đã sắp xếp sẵn theo thời gian (Timeline Streams), tránh xa cạm bẫy gộp mảng rồi sắp xếp toàn phần $O(N \log N)$. Sử dụng cấu trúc dữ liệu Binary Max-Heap duy trì đúng $K$ con trỏ giúp thời gian trích xuất mỗi phần tử chỉ tốn $O(\log K)$, triệt tiêu áp lực cấp phát bộ nhớ và giảm độ trễ xử lý xuống dưới ngưỡng miligiây.