Giao diện
Scale & Approximation Algorithms Masterclass
"Khi dataset vượt qua 1 tỷ records, mọi quy tắc cũ đều vô nghĩa." - HPN
The Cost of Scale
Trong thế giới Big Data và Real-time Systems, các cấu trúc dữ liệu cơ bản như List, Set, HashMap đều thất bại:
| Bài toán | Naive Approach | Vấn đề |
|---|---|---|
| Tìm tài xế gần nhất trong 1 triệu drivers | Duyệt List, tính distance | $O(N)$ mỗi query → Quá chậm |
| Đếm unique users truy cập (1 tỷ users) | HashSet.add(user_id) | 1 tỷ × 8 bytes = 8 GB RAM |
| Kiểm tra URL có malicious không (10 triệu URLs) | Lookup trong Set | Tốn bộ nhớ + Disk I/O |
❌ KHÔNG THỂ CHẤP NHẬN
Với hệ thống xử lý 1 triệu requests/giây, mỗi request tốn thêm 1ms đồng nghĩa với 1000 giây delay mỗi giây → System collapse.
The Paradigm Shift
Module này giới thiệu hai mindset mới:
1. Probabilistic Data Structures
"Đánh đổi một chút accuracy để tiết kiệm 1000x memory."
- Bloom Filter: "Có thể có" hoặc "Chắc chắn không có"
- HyperLogLog: Đếm 1 tỷ unique items với chỉ 12 KB RAM
2. Spatial Indexing
"Chia không gian 2D thành các ô để tìm kiếm nhanh."
- Quadtree: Recursive subdivision của bản đồ
- Geohash: Encode tọa độ thành string có thể sort
Roadmap Module
Ba Trụ Cột
| Algorithm | Memory | Accuracy | Use Case |
|---|---|---|---|
| Quadtree | $O(N)$ | 100% exact | Nearest neighbor, collision detection |
| Bloom Filter | $O(N/8)$ bits | ~99% (tunable) | Cache gating, duplicate detection |
| HyperLogLog | $O(1)$ ~12KB | ~97.7% | Unique visitors, cardinality |
📘 Industry Giants sử dụng
- Uber/Grab: Quadtree + Geohash cho driver matching
- Cassandra/Redis: Bloom Filter cho disk I/O optimization
- Redis PFCOUNT: HyperLogLog native implementation
Bắt đầu từ đâu?
- Quadtree - Spatial Indexing - Chia để trị không gian 2D
- Bloom Filter - The Gatekeeper - Probabilistic set membership
- HyperLogLog - Count to a Billion - Đếm với constant memory
💡 HPN's Insight
Nếu bạn đang thiết kế hệ thống Location-Based Service, Analytics Pipeline, hoặc Caching Layer - đây là module bắt buộc.