Big data & streaming — Khi RAM không đủ

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

Khi RAM không đủ: external sort, sampling, và sketch xấp xỉ (HyperLogLog, Count-Min). Đổi độ chính xác lấy bộ nhớ hằng số.

External merge sort — sắp xếp vượt RAM

Chia dữ liệu thành chunk vừa RAM, sort từng chunk, rồi k-way merge. Nền của ORDER BY trên database và shuffle MapReduce.

Reservoir sampling — mẫu ngẫu nhiên từ stream

Lấy k mẫu đều xác suất từ stream độ dài chưa biết, chỉ O(k) bộ nhớ. Chứng minh xác suất đồng đều và ứng dụng log sampling.

HyperLogLog — đếm distinct xấp xỉ

Đếm số phần tử khác nhau trên stream tỷ phần tử chỉ với vài KB, sai số ~2%. Ý tưởng leading-zero của hash và harmonic mean.

Count-Min Sketch — đếm tần suất xấp xỉ

Ước lượng tần suất phần tử trên stream với bộ nhớ cố định, dùng nhiều hàm băm + ma trận đếm. Luôn over-estimate; ứng dụng heavy hitters, rate limiting.

Sliding window — thống kê trên cửa sổ trượt

Tính max/min/sum/distinct trên N phần tử gần nhất: monotonic deque cho max O(1) amortized, two-pointer cho sum/điều kiện, hash map cho distinct.

Mini-challenge — top-K phần tử trên stream

Lab: tìm K phần tử xuất hiện nhiều nhất trên stream lớn bằng Count-Min Sketch + min-heap, so với đếm chính xác.

Case study — Redis HLL & Kafka offset

Redis hiện thực HyperLogLog (PFADD/PFCOUNT, 16384 register, 12KB) ra sao, và Kafka quản lý offset/partition log để xử lý stream tin cậy thế nào.

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

Recap streaming: bảng chọn sketch/sampling theo bài toán (distinct, tần suất, mẫu, window), glossary, self-assessment.