Module 3 — Tổng kết & cheat sheet

TL;DR: Module 3 trang bị năm kỹ thuật cho thế giới dữ liệu lớn hơn RAM: external merge sort chia dữ liệu thành chunk vừa bộ nhớ rồi k-way merge tuần tự; reservoir sampling lấy mẫu đại diện O(k) từ stream chưa biết độ dài; HyperLogLog đếm distinct với 12 KB và sai số 0.81%; Count-Min Sketch ước lượng tần suất trong ma trận d×w; sliding window duy trì thống kê cửa sổ N phần tử gần nhất với deque đơn điệu O(1). Redis HLL và Kafka là hai hệ thống production triển khai trực tiếp hai trong số kỹ thuật này. Trang này là cheat sheet để bookmark: bảng chọn thuật toán, glossary 12 thuật ngữ, 6 pitfall hay gặp, và self-assessment 4 câu khớp learning outcomes.

Đã đi qua những gì

Bài 01 — External sort đặt câu hỏi nền tảng: khi dữ liệu lớn hơn RAM, làm thế nào? Chiến lược: chia thành chunk vừa RAM, sort từng chunk (tạo sorted run), sau đó k-way merge bằng min-heap. Sequential I/O nhanh hơn random I/O hàng chục lần trên HDD — đây là lý do toàn bộ thiết kế ưu tiên đọc/ghi tuần tự. Độ phức tạp I/O: O(n × số_pass) với số_pass = ⌈log_k(N/M)⌉; bộ nhớ: O(chunk_size + k) hằng số.

Bài 02 — Reservoir sampling giới thiệu chiến lược thứ hai: lấy mẫu thay vì xử lý toàn bộ. Với stream chưa biết độ dài n, reservoir sampling giữ mảng k phần tử và với mỗi phần tử thứ i (i > k), thay thế một phần tử ngẫu nhiên trong reservoir với xác suất k/i. Chứng minh quy nạp đảm bảo mọi phần tử trong stream có xác suất k/n được chọn — mẫu đồng đều không bias. Bộ nhớ O(k), không cần biết n trước.

Bài 03 — HyperLogLog là bước nhảy quan trọng nhất: đổi vài % độ chính xác lấy bộ nhớ hằng số. Ý tưởng: hash mỗi phần tử, dùng 14 bit đầu để chọn register (1 trong 16,384), dùng 50 bit còn lại để đếm leading zero. Mỗi register lưu maximum leading-zero count — giá trị M trong register cho thấy khoảng 2^M phần tử đã hash vào đó. Harmonic mean của 16,384 register loại bỏ outlier → sai số tổng chỉ 0.81%. Redis triển khai với PFADD / PFCOUNT / PFMERGE và sparse/dense encoding tự động.

Bài 04 — Count-Min Sketch tổng quát sang bài toán tần suất: ma trận d hàng × w cột, mỗi hàng dùng một hàm hash độc lập. update(x) tăng d counter tương ứng. estimate(x) trả về min của d counter — min giảm ảnh hưởng của collision. Bất biến: estimate(x) >= freq(x) luôn đúng (over-estimate, không bao giờ under-estimate). Kết hợp với min-heap K phần tử để giải bài top-K heavy hitters trên stream.

Bài 05 — Sliding window đóng tam giác: duy trì thống kê cửa sổ N phần tử gần nhất mà không lưu toàn bộ lịch sử. Hai cấu trúc then chốt: monotonic deque (deque đơn điệu) cho max/min cửa sổ trong O(1) amortized; two-pointer cho sum/điều kiện trên subarray. Ứng dụng: rate limiting (đếm request trong window 60 giây), real-time analytics (max response time trong window 5 phút).

Bài 06 — Mini-challenge tổng hợp CMS + min-heap để tìm K phần tử xuất hiện nhiều nhất trên stream: update CMS với mỗi phần tử, estimate tần suất, duy trì heap K phần tử. Bộ nhớ O(d×w + K) — hằng số theo stream length.

Bài 07 — Case study cho thấy Redis HLL (16,384 register 6-bit, sparse/dense auto-switch, PFMERGE qua max) và Kafka partition (append-only log, offset bất biến, consumer group độc lập, sequential I/O, retention policy). Hai hệ thống, hai triết lý: Redis đổi độ chính xác lấy bộ nhớ; Kafka giữ toàn bộ stream cho đến hết retention để nhiều consumer replay độc lập.

graph LR
    ES["External sort\nchunk + k-way merge\nO(n log n) I/O"] --> RS["Reservoir\nsampling\nO(k) memory"]
    RS --> HLL["HyperLogLog\n12 KB\nsai số 0.81%"]
    HLL --> CMS["Count-Min\nSketch\nd×w matrix"]
    CMS --> SW["Sliding\nwindow\nO(1) deque"]
    SW --> PROD["Production\nRedis HLL\nKafka log"]

🗺️ Cheat sheet

Bảng chọn thuật toán

Quyết định chọn thuật toán

graph TD
    START["Bài toán\ntrên stream lớn"] --> Q1{"Loại câu hỏi?"}
    Q1 -- "Sắp xếp" --> ES2["External merge sort"]
    Q1 -- "Lấy mẫu" --> RS2["Reservoir sampling"]
    Q1 -- "Đếm distinct\n(bao nhiêu unique?)" --> HLL2["HyperLogLog\n(Redis PFADD/PFCOUNT)"]
    Q1 -- "Tần suất phần tử\n(cái gì nhiều nhất?)" --> Q2{"Cần chính xác?"}
    Q2 -- "Có" --> MAP["Hash map\nO(n unique)"]
    Q2 -- "Xấp xỉ OK" --> CMS2["Count-Min Sketch\n+ min-heap cho top-K"]
    Q1 -- "Thống kê\ncửa sổ trượt" --> Q3{"Loại thống kê?"}
    Q3 -- "Max/min" --> DEQUE["Monotonic deque\nO(1) amortized"]
    Q3 -- "Sum/điều kiện" --> TP["Two-pointer\nO(n)"]

So sánh nhanh: exact vs approximate

📖 Glossary

⚠️ Pitfall tổng hợp

Pitfall 1 — External sort: chunk quá nhỏ, k-way merge cần quá nhiều file handle.

-- SAI: chunk 1 MB trên dataset 100 GB → 100,000 sorted run → k=100,000 → heap quá lớn
-- ĐÚNG: chunk = RAM / (k + buffer) → k = 100 → chunk = RAM/101 ≈ 80 MB với 8 GB RAM
-- Số pass = ceil(log_k(n/chunk_size)) → k lớn hơn = ít pass hơn = ít I/O hơn

Pitfall 2 — Reservoir sampling: reset reservoir khi stream thay đổi. Reservoir sampling chỉ đúng khi xem stream là một pass duy nhất từ đầu đến cuối. Nếu restart thuật toán giữa chừng (ví dụ crash rồi recover), phần stream đã đọc trước crash sẽ bị bỏ qua — mẫu không còn đồng đều. Cần checkpoint reservoir state để resume đúng.

Pitfall 3 — HyperLogLog: PFCOUNT nhiều key không phải sum của từng key.

-- SAI (tính tổng distinct theo từng key):
total_distinct <- PFCOUNT(key1) + PFCOUNT(key2)

-- ĐÚNG (dùng PFMERGE để tránh double-count):
PFMERGE temp_key key1 key2
total_distinct <- PFCOUNT(temp_key)
-- hoặc ngắn hơn:
total_distinct <- PFCOUNT key1 key2  -- Redis tự PFMERGE tạm thời

Lý do: user xem cả page1 lẫn page2 sẽ bị đếm hai lần nếu cộng riêng từng key.

Pitfall 4 — Count-Min Sketch: over-estimate khi w quá nhỏ.

-- SAI: w=10 cho stream 1 triệu phần tử → collision cao → over-estimate lớn
-- ĐÚNG: w >= e/epsilon với epsilon là sai số tối đa chấp nhận được
-- Ví dụ epsilon=0.1%: w >= e/0.001 ≈ 2719
-- Quy tắc thực tế: w = 10 × (N / K) với N = stream size, K = top-K mong muốn

Pitfall 5 — Sliding window deque: không pop phần tử ra ngoài cửa sổ.

-- SAI: duy trì monotonic nhưng quên loại chỉ số đã ra khỏi cửa sổ (ở front)
while DQ không rỗng và A[DQ.back()] <= A[i]:
    DQ.pop_back()
DQ.push_back(i)
-- thiếu bước pop_front -> front có thể là chỉ số quá cũ -> max sai

-- ĐÚNG: loại chỉ số ngoài cửa sổ TRƯỚC (khớp convention bài 05)
while DQ không rỗng và DQ.front() < i - windowSize + 1:
    DQ.pop_front()             -- xóa chỉ số đã ra khỏi cửa sổ
while DQ không rỗng và A[DQ.back()] <= A[i]:
    DQ.pop_back()              -- duy trì giảm dần
DQ.push_back(i)
-- max cửa sổ hiện tại = A[DQ.front()]

Pitfall 6 — Kafka: commit offset TRƯỚC khi process dẫn đến mất message.

-- SAI (at-most-once — có thể mất message nếu crash sau commit):
records <- consumer.poll()
consumer.commitSync()    -- commit trước
for each record: process(record)

-- ĐÚNG (at-least-once — có thể duplicate nhưng không mất):
records <- consumer.poll()
for each record: process(record)
consumer.commitSync()    -- commit sau khi process xong
-- Đảm bảo idempotent processing để xử lý duplicate khi cần

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Giải thích được 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ố — cho ví dụ cụ thể với external sort (ORDER BY 100 GB, RAM 8 GB) và HyperLogLog (đếm 1 tỷ unique visitor với 12 KB).
  • Nếu chưa: đọc lại bài 00 — Tổng quan mục "Vì sao module này tồn tại" và bài 01 — External sort mục "Vì sao sequential I/O".
• Implement được external merge sort (chunk → sort → k-way merge bằng min-heap) và reservoir sampling (xác suất k/i khi đọc phần tử thứ i) với chứng minh xác suất đồng đều bằng quy nạp — bao gồm xử lý đúng trường hợp i nhỏ hơn hoặc bằng k.
  • Nếu chưa: làm lại bài 06 — Mini-challenge từ đầu không xem lời giải; đọc lại bài 02 — Reservoir sampling mục chứng minh quy nạp.
• Compare được HyperLogLog, Count-Min Sketch và đếm chính xác (hash map) theo bộ nhớ, sai số và loại bài toán — phân biệt rõ: HLL trả lời "bao nhiêu distinct?", CMS trả lời "tần suất phần tử X là bao nhiêu?", hash map trả lời cả hai nhưng cần O(n unique) bộ nhớ.
  • Nếu chưa: đọc lại bảng cheat sheet phần trên và bài 07 — Case study mục "Vì sao chọn cấu trúc nào".
• Choose được sketch hoặc sampling phù hợp cho từng bài toán streaming: distinct count (HLL), tần suất/top-K (CMS + heap), lấy mẫu ngẫu nhiên (reservoir), thống kê cửa sổ trượt (sliding window) — và biết khi nào không nên dùng approximate (billing, legal, cần enumerate).
  • Nếu chưa: đọc lại sơ đồ quyết định trong cheat sheet và so sánh Redis HLL vs Kafka trong bài 07.

🚀 What's next

Module 3 hoàn thành bức tranh về thuật toán đơn máy khi dữ liệu lớn. Module 4 — Thuật toán phân tán đưa những kỹ thuật này vào môi trường nhiều máy: khi một máy không đủ, cần chia dữ liệu và tính toán sang nhiều node. Consistent hashing (phân phối key đồng đều khi thêm/bớt node), Raft consensus (đồng thuận trên log phân tán — liên hệ trực tiếp với Kafka partition log), và MapReduce (external sort ở quy mô cluster) đều xây trên nền tảng của module này.

Bài tiếp theo: Module 4 — Thuật toán phân tán

📚 Tài liệu mở rộng

• Flajolet & Martin (1985) — "Probabilistic counting algorithms for data base applications": Bài báo gốc về probabilistic counting — tiền thân của HyperLogLog. Giới thiệu ý tưởng dùng leading zero của hash để ước lượng cardinality.
• Flajolet et al. (2007) — "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm": Bài báo giới thiệu HyperLogLog — harmonic mean thay vì geometric mean cho sai số 0.81%. Bản PDF miễn phí.
• Cormode & Muthukrishnan (2005) — "An improved data stream summary: the count-min sketch and its applications": Bài báo gốc Count-Min Sketch. PDF.
• Knuth, TAOCP Vol. 2, Section 3.4.2 — Reservoir sampling: Phân tích thuật toán reservoir sampling của Vitter (1985) với chứng minh xác suất và các variant hiệu quả hơn.
• Kafka documentation — "Design" section: Giải thích chi tiết quyết định thiết kế append-only log, offset, consumer group, partition. Tại kafka.apache.org/documentation.
• Redis source — src/hyperloglog.c: File C implement HyperLogLog trong Redis. Xem hllAdd, hllCount, sparse/dense switching. GitHub redis/redis.