Big data & streaming: tổng quan khi RAM không đủ

TL;DR: Module này 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ố cỡ 1%, Count-Min Sketch đếm tần suất). Redis có sẵn HyperLogLog để dùng ngay; Kafka cho thấy vì sao ghi đọc tuần tự trên đĩa lại nhanh đến vậ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 dùng 16384 register, tức 16384 ô nhớ nhỏ mỗi ô giữ một con số thống kê, 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. Lấy mẫu ngẫu nhiên 1% request (Bernoulli sampling: mỗi request được giữ với xác suất 1%) là đủ để phân tích. Khi cần giữ đúng k request mà không biết trước tổng số, dùng reservoir sampling: mọi request có cùng xác suất vào mẫu.

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 (đúng bằng lượng RAM có sẵn), sort từng chunk, sau đó k-way merge, số vòng trộn = ⌈log_k(N/M)⌉ (với N là tổng dữ liệu, M là RAM, k là số chunk trộn cùng lúc), bộ nhớ vẫn chỉ 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 hàng đợi timestamp (xoá các mốc đã quá 60 giây khỏi đầu hàng đợi) cho câu trả lời trong O(1) amortized mỗi request mà không cần lưu toàn bộ lịch sử.

Module này dạy thuật toán, nhưng cái đọng lại là tư duy đánh đổi có chủ đích: exact hay approximate, random access hay sequential, tốn bộ nhớ hay chấp nhận sai số. Kỹ năng này dùng lại mỗi khi bạn làm 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 dùng truy cập tuần tự để lấy bộ nhớ hằng số.
• Derive chi phí I/O của external merge sort theo k và RAM, cùng xác suất đồng đều k/n của reservoir sampling.
• 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.

Lộ trình module

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

Bài 01 — External sort là điểm xuất phát vì bài này đặ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 là đếm số bit 0 đứng đầu (leading zero) của giá trị hash, rồi lấy giá trị lớn nhất trên cả stream. Nghe lạ tai nhưng có nền xác suất vững. Đọc sau reservoir sampling để thấy dải từ "đúng tuyệt đối" tới "gần đúng".

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. Kết quả luôn đếm dư (over-estimate), nhưng mức dư có giới hạn.

Bài 05 — Sliding window là chiến lược cuối: thay vì xử lý toàn bộ lịch sử, chỉ giữ trạng thái của cửa sổ gần nhất. Monotonic deque là cấu trúc then chốt cho cửa sổ theo số phần tử; cửa sổ theo thời gian thì dùng sliding log hoặc sliding window counter cho rate limiter. Muốn xem cửa sổ chạy trong pipeline stream thật (tumbling, sliding, session), đọc thêm Windowing.

Bài 06, Mini-challenge tổng hợp Count-Min Sketch + min-heap để tìm top-K heavy hitters (những phần tử xuất hiện nhiều nhất) trên stream, bài toán "top K video đượ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 sparse/dense tối đa 12 KB; Kafka append-only log dùng offset để theo dõi consumer đã đọc tới đâu.

Bài 08 — Tổng kết gom cheat sheet, thuật ngữ và phần tự kiểm tra.

Bản đồ khái niệm

Vào từ phía câu hỏi, không phải từ phía kích thước dữ liệu. Hai nhánh giữa nghe gần giống nhau, "bao nhiêu phần tử khác nhau" và "phần tử nào nhiều nhất", nhưng dẫn tới hai cấu trúc khác hẳn.

Yêu cầu trước

Module này xây trên hai nền tảng từ khoá Thuật toán Cốt lõi:

• 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 cần hash phân bố đều; Count-Min Sketch dùng nhiều hàm hash độc lập. Hiểu xác suất đụng độ (collision) giúp hiểu cận sai số.

Nếu bạn chưa quen với min-heap, đọc bài Heap & heapsort 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ác merge sort thường ở chi phí I/O: sequential read/write nhanh hơn random access hàng chục tới hàng trăm lần trên ổ cứng quay (HDD), và ít hơn nhưng vẫn đáng kể 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ố khoảng 0,8%. Đọc ý tưởng leading-zero trước khi đọc chứng minh: trực giác đến trước, toán đế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, và đây là bất biến của thiết kế (điều luôn đúng với mọi dữ liệu đầu vào). 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, rồi Redis và Kafka sẽ dễ hiểu hơn nhiều vì bạn đã thấy các quyết định thiết kế từ góc nhìn của người tự cài đặt.

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