Big data & streaming: tổng kết và cheat sheet
Recap streaming: bảng chọn sketch/sampling theo bài toán (distinct, tần suất, mẫu, window), thuật ngữ, tự kiểm tra.
TL;DR: Module này 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 HyperLogLog là bản triển khai production của một sketch; Kafka cho thấy cùng nguyên lý ghi đọc tuần tự mà external sort khai thác. Trang này là cheat sheet để bookmark: bảng chọn thuật toán, 12 thuật ngữ, các bẫy hay gặp, và 6 câu tự kiểm tra liên bài.
Đã đi qua những gì
Bảy bài, mỗi bài bán đi một thứ để lấy bộ nhớ nhỏ hoặc I/O tuần tự:
| Bài | Công cụ | Bán đi thứ gì | Con số neo |
|---|---|---|---|
| 01 | External sort | Số lượt đọc ghi đĩa | Số lượt = ⌈log_k(N/M)⌉, 100 GB với RAM 8 GB |
| 02 | Reservoir sampling | Việc nhìn toàn bộ dữ liệu | O(k) bộ nhớ, mỗi phần tử vào mẫu với xác suất k/n |
| 03 | HyperLogLog | Khả năng liệt kê phần tử | 16.384 register, 12 KB, sai số chuẩn 1.04/√m ≈ 0.81% |
| 04 | Count-Min Sketch | Độ chính xác (chỉ đếm dư) | Ma trận d×w, estimate(x) >= freq(x) |
| 05 | Sliding window | Lịch sử ngoài cửa sổ | Deque O(1) amortized; rate limiter chọn log hay counter |
| 06 | Mini-challenge top-K | Thứ hạng chính xác | CMS + min-heap, bộ nhớ O(d×w + K) |
| 07 | Redis HLL và Kafka | Redis bán độ chính xác, Kafka bán dung lượng đĩa | 12 KB tối đa mỗi key; log giữ đến hết retention |
Cả module quy về một luật: không công cụ nào cho không bộ nhớ hằng số, mỗi cái đều bán đi một thứ. Chọn công cụ nghĩa là chọn món mình chịu mất được.
All-Access Pass
Phần còn lại của bài dành cho All-Access Pass
Bạn vừa đọc phần xem trước. Hai bài đầu của mỗi khoá luôn đọc trọn miễn phí.
- Đọc trọn mọi bài trong 6 khoá System Design và dữ liệu phân tán
- AI Mentor trả lời theo toàn bộ nội dung bài
- Trả một lần, không tự gia hạn, không tự trừ tiền
Trọn đời
1.690.000 ₫
Trả một lần, dùng mãi mãi
Gói năm
699.000 ₫
365 ngày · ≈ 58.000 ₫/tháng
Thanh toán bằng thẻ Visa/Master/JCB qua Polar. Xem bảng giá
Case study — Redis HLL & Kafka offset
Bài tiếp Thuật toán phân tánModule 9 — Thuật toán phân tán: tổng quan
Bài này có giúp bạn hiểu bản chất không?
Bài này đáng gửi cho bạn học cùng?
Copy link đã gắn nguồn — dán group, chat, hoặc LinkedIn.
Thảo luận & góp ý
Hỏi đáp về bài này