Algorithms & Applications
Trang chủ / Module 12
🎲 Module 12 / 14 · 4-5 ngày

Cấu trúc dữ liệu Xác suất: Bloom Filter, HyperLogLog

Đánh đổi độ chính xác lấy bộ nhớ — Bloom Filter cho kiểm tra thành viên gần đúng, và HyperLogLog cho đếm số phần tử duy nhất ở quy mô khổng lồ.

Bloom FilterHyperLogLog
📌 Vì sao module này quan trọng

Ở quy mô dữ liệu thực sự lớn (hàng tỷ phần tử), cấu trúc dữ liệu chính xác tuyệt đối (Hash Set — Module 4) đòi hỏi bộ nhớ khổng lồ. Cấu trúc dữ liệu xác suất chấp nhận 1 tỉ lệ sai số nhỏ, có thể kiểm soát được, để đổi lấy bộ nhớ giảm hàng trăm-hàng nghìn lần — đây là kỹ thuật thực tế được dùng rộng rãi trong hệ thống quy mô lớn mà nhiều kỹ sư chưa từng nghe đến.

🎯 Mục tiêu học tập

  • Hiểu nguyên lý Bloom Filter: kiểm tra thành viên với false positive có kiểm soát, không bao giờ false negative
  • Ứng dụng Bloom Filter cho các bài toán thực tế: cache miss filtering, kiểm tra trùng lặp quy mô lớn
  • Hiểu ý tưởng của HyperLogLog cho đếm số phần tử duy nhất (cardinality) với bộ nhớ cực nhỏ
  • Nhận diện đúng khi nào đánh đổi độ chính xác lấy hiệu năng là chấp nhận được

Bloom Filter — Kiểm tra thành viên với Bộ nhớ cực nhỏ

Bloom Filter là 1 mảng bit (bit array) kích thước m, dùng k hash function độc lập. Khi thêm 1 phần tử: tính k giá trị hash, bật (set = 1) k bit tương ứng. Khi kiểm tra 1 phần tử có tồn tại không: tính lại k vị trí hash, nếu tất cả k bit đều là 1 → "có thể có" ( có thể là false positive); nếu bất kỳ bit nào là 0 → "chắc chắn không có" (không bao giờ false negative).

# Ý tưởng cốt lõi (giản lược, không phải triển khai production)
class BloomFilter:
    def __init__(self, size: int, num_hashes: int):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = [0] * size

    def _hashes(self, item: str) -> list[int]:
        return [hash(f"{item}_{i}") % self.size for i in range(self.num_hashes)]

    def add(self, item: str):
        for pos in self._hashes(item):
            self.bits[pos] = 1

    def might_contain(self, item: str) -> bool:
        return all(self.bits[pos] == 1 for pos in self._hashes(item))

Tỉ lệ false positive được kiểm soát bằng cách chọn đúng kích thước m và số hash function k theo số lượng phần tử dự kiến — có công thức toán học chính xác để tính (không cần thuộc lòng, các thư viện Bloom Filter đều tự tính giúp).

Ứng dụng thực tế của Bloom Filter

  • Cache miss filtering: trước khi query database (chậm) để kiểm tra 1 key có tồn tại không, kiểm tra Bloom Filter trước (cực nhanh, bộ nhớ nhỏ) — nếu Bloom Filter nói "chắc chắn không có", bỏ qua ngay database query; nếu "có thể có", mới thực sự query để xác nhận. Giảm đáng kể tải lên database cho các truy vấn "chắc chắn không tồn tại" (một pattern rất phổ biến, ví dụ kiểm tra username đã tồn tại chưa lúc đăng ký).
  • Kiểm tra trùng lặp ở quy mô khổng lồ: phát hiện URL đã crawl chưa (web crawler quy mô lớn), phát hiện email đã gửi chưa — không cần lưu chính xác toàn bộ tập đã thấy (tốn hàng chục GB) mà chỉ cần Bloom Filter vài MB với tỉ lệ sai số chấp nhận được.
  • Distributed system: Cassandra và nhiều hệ NoSQL dùng Bloom Filter để nhanh chóng loại trừ các SSTable chắc chắn không chứa key đang tìm, tránh đọc đĩa không cần thiết.

HyperLogLog — Đếm số phần tử Duy nhất với Bộ nhớ Cực nhỏ

Bài toán: đếm số lượng giá trị duy nhất (cardinality) trong 1 tập dữ liệu khổng lồ (ví dụ: số lượng IP address duy nhất đã truy cập website trong 1 ngày, có thể lên đến hàng trăm triệu). Đếm chính xác cần lưu toàn bộ giá trị đã thấy (Hash Set — tốn bộ nhớ tuyến tính theo số phần tử duy nhất). HyperLogLog ước lượng cardinality với sai số nhỏ (thường <2%) chỉ dùng vài KB bộ nhớ cố định, bất kể có bao nhiêu triệu phần tử duy nhất — dựa trên ý tưởng thống kê: quan sát số bit 0 liên tiếp đầu tiên trong giá trị hash của các phần tử, số lượng phần tử duy nhất càng lớn thì càng có khả năng gặp chuỗi bit 0 dài.

💡 Ứng dụng có sẵn, không cần tự cài đặt

Redis có lệnh PFADD/PFCOUNT triển khai sẵn HyperLogLog — dùng trực tiếp cho bài toán đếm unique visitor/unique event ở quy mô lớn mà không cần tự implement thuật toán phức tạp bên dưới.

🏋️ Bài tập thực hành

So sánh Bloom Filter với Hash Set thông thường

Triển khai Bloom Filter đơn giản (theo mẫu ở trên). Nạp 100.000 chuỗi ngẫu nhiên vào cả Bloom Filter và 1 Hash Set thông thường (Module 4). So sánh: (1) bộ nhớ ước tính mỗi cấu trúc chiếm dụng, (2) thời gian kiểm tra thành viên cho 10.000 truy vấn, (3) đo tỉ lệ false positive thực tế của Bloom Filter bằng cách kiểm tra các chuỗi CHẮC CHẮN không có trong tập đã thêm.

📚 Tài nguyên học tập

✅ Tự đánh giá hoàn thành

  • Giải thích được Bloom Filter không bao giờ false negative nhưng có thể false positive
  • Triển khai được Bloom Filter đơn giản và đo được tỉ lệ false positive thực tế
  • Nhận diện được ít nhất 2 ứng dụng thực tế phù hợp cho Bloom Filter
  • Giải thích được ý tưởng HyperLogLog ước lượng cardinality với bộ nhớ cực nhỏ