Module 3 — Big data & streaming: tổng quan

TL;DR: Module 3 trả lời một câu hỏi thực tiễn: khi dữ liệu lớn hơn RAM, ta làm gì? Ba chiến lược: (1) External sort — chia dữ liệu thành chunk vừa RAM, sort từng chunk, merge lại; (2) Sampling — chọn mẫu đại diện thay vì xử lý toàn bộ (reservoir sampling O(k) bộ nhớ); (3) Sketch — đổi độ chính xác lấy bộ nhớ hằng số (HyperLogLog đếm distinct với sai số 2%, Count-Min Sketch đếm tần suất). Redis và Kafka là hai hệ thống production triển khai trực tiếp các kỹ thuật này.

Vì sao module này tồn tại

Kịch bản 1 — Đếm unique visitor: Hệ thống analytics của một trang thương mại điện tử ghi nhận 1 tỷ sự kiện click/ngày, mỗi sự kiện chứa user ID 8 byte. Đếm chính xác số user khác nhau cần hash set — 1 tỷ × 8 byte = 8 GB RAM chỉ cho một ngày. Với HyperLogLog, con số đó xuống còn 12 KB với sai số dưới 1% (cấu hình Redis 16384 register cho sai số chuẩn 0.81%).

Kịch bản 2 — Log sampling: Một API gateway xử lý 200,000 request/giây. Ghi toàn bộ log vào disk: 200,000 × 1 KB = 200 MB/s → 17 TB/ngày. Reservoir sampling chọn ngẫu nhiên 1% request để phân tích, đảm bảo mọi request có cùng xác suất được chọn — không cần biết trước tổng số request.

Kịch bản 3 — ORDER BY trên 100 GB: Một data warehouse cần sort bảng log 100 GB để tạo report. RAM chỉ có 8 GB. External merge sort chia thành các chunk 8 GB (tối đa bộ nhớ khả dụng), sort từng chunk, sau đó k-way merge — số pass = ⌈log_k(N/M)⌉, bộ nhớ hằng số 8 GB.

Kịch bản 4 — Rate limiting real-time: Một API gateway cần biết trong 60 giây vừa qua, user X đã gọi bao nhiêu lần, để enforce rate limit. Cửa sổ trượt (sliding window) với monotonic deque cho câu trả lời trong O(1) mỗi request mà không cần lưu toàn bộ lịch sử.

Module này không chỉ dạy thuật toán — nó dạy tư duy đánh đổi có chủ đích: exact vs approximate, random access vs sequential, memory vs accuracy. Đây là kỹ năng cốt lõi của system design.

Sau module này bạn sẽ

• Explain vì sao các thuật toán streaming tồn tại: khi dữ liệu vượt RAM, cần đổi độ chính xác hoặc truy cập ngẫu nhiên để lấy bộ nhớ hằng số.
• Implement external merge sort (chunk → sort → k-way merge) và reservoir sampling với chứng minh xác suất đồng đều.
• Compare HyperLogLog, Count-Min Sketch và đếm chính xác theo bộ nhớ, sai số và loại bài toán (distinct/tần suất).
• Choose sketch hoặc sampling phù hợp cho từng bài toán streaming: distinct count, tần suất phần tử, lấy mẫu ngẫu nhiên, thống kê cửa sổ trượt.

Ý tưởng cốt lõi của module

Chunk → sort → k-way merge. Dữ liệu lớn hơn RAM, I/O tuần tự thay random access

Mẫu đại diện O(k) bộ nhớ từ stream chưa biết độ dài — xác suất đồng đều

HyperLogLog + Count-Min: đổi vài % sai số lấy bộ nhớ hằng số KB thay vì GB

Lộ trình module

flowchart LR
    OV["00\nTổng quan"] --> ES["01\nExternal sort\nchunk + merge"]
    ES --> RS["02\nReservoir\nsampling"]
    RS --> HLL["03\nHyperLogLog\ndistinct xấp xỉ"]
    HLL --> CMS["04\nCount-Min\nSketch"]
    CMS --> SW["05\nSliding\nwindow"]
    SW --> MC["06\nMini-challenge\ntop-K stream"]
    MC --> CS["07\nCase study\nRedis & Kafka"]
    CS --> REC["08\nTổng kết"]

Thứ tự bài — vì sao thiết kế như vậy

Bài 01 — External sort là điểm xuất phát đúng vì nó đặt câu hỏi cốt lõi: khi RAM không đủ, truy cập tuần tự (sequential I/O) tốt hơn truy cập ngẫu nhiên (random I/O) bao nhiêu? Hiểu external sort là hiểu vì sao database dùng B-tree thay vì hash index cho range query, và vì sao shuffle trong MapReduce tốn kém.

Bài 02 — Reservoir sampling giới thiệu chiến lược thứ hai: thay vì xử lý toàn bộ, lấy mẫu đại diện. Chứng minh xác suất đồng đều bằng quy nạp — đây là kiểu tư duy "approximate computing" lần đầu xuất hiện trong module.

Bài 03 — HyperLogLog là bước nhảy quan trọng nhất: đổi độ chính xác lấy bộ nhớ hằng số. Ý tưởng leading-zero của hash — đếm max leading zero trên stream của hash values — nghe có vẻ kỳ lạ nhưng có nền tảng lý thuyết xác suất vững chắc. Đọc sau reservoir sampling giúp thấy spectrum "exact → approximate".

Bài 04 — Count-Min Sketch tổng quát ý tưởng sketch sang bài toán tần suất: thay vì một mảng đếm (hash table), dùng nhiều mảng đếm với nhiều hàm hash độc lập, lấy min để giảm collision. Luôn over-estimate, nhưng over-estimate có giới hạn.

Bài 05 — Sliding window đóng tam giác: thay vì xử lý toàn bộ lịch sử, chỉ duy trì trạng thái của cửa sổ gần nhất. Monotonic deque là cấu trúc then chốt — bài này cũng nối ngược lại kỹ năng deque từ Thuật toán Cốt lõi — Module 2 (heap & priority queue).

Bài 06 — Mini-challenge tổng hợp Count-Min Sketch + min-heap để tìm top-K heavy hitters trên stream — bài toán Netflix "top K show được xem nhiều nhất trong giờ cao điểm".

Bài 07 — Case study cho thấy hai hệ thống production dùng hai kỹ thuật này: Redis HyperLogLog (PFADD/PFCOUNT) với cấu trúc dense/sparse 12 KB; Kafka append-only log với offset làm cơ chế consumer tracking.

Bài 08 — Tổng kết gom cheat sheet, glossary và self-assessment.

Bản đồ khái niệm

graph TD
    PROB["Dữ liệu lớn hơn RAM"] --> Q1{"Loại bài toán?"}
    Q1 -- "Sắp xếp" --> ES2["External merge sort\nO(n log n) I/O, O(RAM) memory"]
    Q1 -- "Lấy mẫu từ stream" --> RS2["Reservoir sampling\nO(k) memory"]
    Q1 -- "Đếm distinct" --> HLL2["HyperLogLog\n~12 KB, sai số ~2%"]
    Q1 -- "Đếm tần suất" --> CMS2["Count-Min Sketch\nd×w bộ nhớ, over-estimate"]
    Q1 -- "Thống kê cửa sổ" --> SW2["Sliding window\nMonotonic deque O(1)"]
    HLL2 -- "top-K tần suất?" --> CMS2
    CMS2 -- "kết hợp heap" --> TK["Top-K heavy hitters"]

Yêu cầu trước

Module này xây trên hai nền tảng từ các module trước:

• Heap và priority queue — từ Thuật toán Cốt lõi — Heap & heapsort: k-way merge trong external sort dùng min-heap size k; mini-challenge top-K dùng min-heap size K để duy trì K heavy hitters.
• Hash function — từ Thuật toán Cốt lõi — Hash function: HyperLogLog dùng hash uniform distribution; Count-Min Sketch dùng nhiều hàm hash độc lập. Hiểu collision probability giúp hiểu error bound.

Nếu bạn chưa quen với min-heap, đọc Thuật toán Cốt lõi — Module 2 trước khi học External sort và mini-challenge.

Time budget

Cách học module này hiệu quả

Không bỏ bài 01 dù bạn đã biết merge sort. External sort không phải là merge sort — điểm khác biệt nằm ở I/O cost: sequential read/write nhanh hơn random access hàng chục lần trên HDD và vài lần trên SSD. Hiểu tại sao external sort ưu tiên sequential I/O là nền tảng của cả module.

Với HyperLogLog, chấp nhận "magic" trước, giải thích sau. Kết quả nghe có vẻ không tưởng: 12 KB đếm được 1 tỷ phần tử distinct với sai số 2%. Đọc ý tưởng leading-zero trước khi đọc chứng minh — intuition đến trước, toán học đến sau.

Với Count-Min Sketch, chú ý over-estimate. Sketch luôn trả về giá trị lớn hơn hoặc bằng tần suất thực. Không phải bug — đây là bất biến thiết kế. Mọi ứng dụng (rate limiting, top-K) phải xây trên bất biến này.

Làm mini-challenge trước khi đọc case study. Tự implement CMS + heap một lần — sau đó Redis và Kafka sẽ dễ hiểu hơn nhiều vì bạn đã thấy các quyết định design từ góc độ người implement.

Bài tiếp theo: External merge sort — sắp xếp vượt RAM