Bài 93: RedisBloom — Bloom Filter cho Membership Check

• Hiểu Bloom Filter là gì: probabilistic membership check, hai kết quả có thể ("definitely NO" / "probably YES"), no false negative, configurable false positive rate.
• Nắm intuition toán học: bit array M, K hash functions, công thức FPR, mối quan hệ giữa M/N/K/FPR.
• Biết khi nào Bloom Filter tiết kiệm memory đáng kể so với Redis Set thông thường.
• Dùng được RedisBloom qua Redis Stack: BF.RESERVE, BF.ADD, BF.MADD, BF.EXISTS, BF.MEXISTS, BF.INFO.
• Triển khai được ba use case thực tế: email dedup, URL blacklist, recommendation dedup với code Python.
• Biết Scalable Bloom Filter (tự mở rộng khi đầy) và Cuckoo Filter (hỗ trợ delete).
• Đọc được bảng memory-FPR trade-off và chọn cấu hình phù hợp.
• Nhận diện các anti-pattern: coi Bloom như exact set, underestimate capacity, không backup.

Bloom Filter, được Burton Howard Bloom đề xuất năm 1970, là một probabilistic data structure trả lời câu hỏi membership: "phần tử X có trong tập hợp S không?". Khác với Set thông thường, Bloom Filter không lưu chính xác các phần tử, mà lưu một bản đại diện nén lại qua nhiều hash function trên một bit array.

Hai loại kết quả mà Bloom Filter có thể trả về:

• "Definitely NO": phần tử chắc chắn không có trong tập hợp. Kết quả này luôn đúng — không có false negative.
• "Probably YES": phần tử có thể có trong tập hợp. Kết quả này đôi khi sai — đây là false positive (FP). Xác suất FP được cấu hình khi tạo filter.

Đặc điểm cốt lõi:

• No false negative: nếu Bloom nói "không" thì chắc chắn không. Đây là đảm bảo quan trọng nhất.
• False positive rate (FPR) configurable: ví dụ FPR = 0.01 nghĩa là cứ 100 lần "probably YES" thì có ~1 lần sai (item thực ra không có trong set).
• Space-efficient: memory usage không tỷ lệ tuyến tính với số phần tử như Set thông thường.
• Không thể delete trong Bloom Filter tiêu chuẩn (Cuckoo Filter giải quyết được điểm này — xem mục 12).

# Minh hoạ logic
BF.ADD filter "[email protected]"   # thêm vào filter

BF.EXISTS filter "[email protected]"  # → 1 (probably YES)
BF.EXISTS filter "[email protected]"    # → 0 (definitely NO)
BF.EXISTS filter "[email protected]"   # → 1 (probably YES — có thể FP)
                                       # hoặc → 0 (definitely NO)

Bloom Filter hoạt động trên một bit array kích thước M và K hash function độc lập.

ADD(x): hash x với K hash function, thu được K chỉ số vị trí trong bit array. Set tất cả K bit đó thành 1.

CHECK(x): hash x với cùng K hash function → thu được K chỉ số. Nếu tất cả K bit đó đều là 1 → "probably YES". Nếu bất kỳ bit nào là 0 → "definitely NO".

Tại sao có false positive? Do collision: nhiều phần tử khác nhau có thể cùng set một số bit chung. Khi check một phần tử chưa từng được thêm, tất cả K bit của nó có thể đã được set bởi các phần tử khác.

Công thức FPR (False Positive Rate) với N phần tử đã thêm vào, M bit, K hash function:

FPR ≈ (1 - e^(-K*N/M))^K

Trong đó:
  N = số phần tử đã ADD vào filter
  M = kích thước bit array
  K = số hash function
  e = hằng số Euler (~2.718)

Giá trị K tối ưu (minimize FPR): K = (M/N) * ln(2) ≈ 0.693 * (M/N)

Ví dụ: N=1,000,000, FPR=0.01 (1%)
  → M ≈ 9,585,059 bits ≈ 1.14 MB
  → K ≈ 7 hash functions

Redis Stack tự tính M và K tối ưu khi bạn cung cấp error_rate và capacity trong BF.RESERVE.

So sánh memory cho 100 triệu user_id (giả sử mỗi ID là UUID dạng string ~36 bytes):

# Redis Set 100M user_id (36-byte string mỗi ID)
# Overhead per member: ~64 bytes (hashtable entry + string object + pointer)
# Tổng: 100,000,000 * 64 bytes ≈ 6.4 GB

# Redis Bloom Filter 100M items, FPR 1% (0.01)
# M = 958,505,844 bits ≈ 114 MB
# Tiết kiệm: ~56x

# Bloom Filter 100M items, FPR 0.1% (0.001)
# M ≈ 1,437,758,767 bits ≈ 171 MB
# Tiết kiệm: ~37x

Với dataset lớn, Bloom Filter tiết kiệm hàng chục lần memory. Đánh đổi là chấp nhận FPR — tức là một số lượng nhỏ trường hợp phải tốn thêm một lookup xuống tầng chính xác hơn (Redis cache hoặc DB).

Nếu ứng dụng có thể chịu được "đôi khi hỏi nhầm DB" thì Bloom Filter là lựa chọn hợp lý ở scale lớn.

Dùng Bloom Filter khi:

• Dataset đủ lớn để Set tiêu tốn quá nhiều memory (thường > 1M items trở lên).
• Bài toán là pre-filter trước expensive lookup: "nếu Bloom nói không thì bỏ qua, nếu Bloom nói có thì mới query DB".
• FP là chấp nhận được — tức là ứng dụng có một bước confirm thứ hai khi Bloom trả về "có".
• Dữ liệu chỉ tăng thêm, không cần delete.

Use case phù hợp:

• Email/username signup dedup: trước khi query DB kiểm tra trùng.
• URL blacklist anti-spam: check URL trước khi cho phép truy cập.
• Recommendation dedup: "đã show ad/content này cho user chưa?".
• Cache negative lookup: tránh cache miss tấn công DB (kết hợp với negative caching).

Không dùng Bloom Filter khi:

• Cần exact result (zero FP) — ví dụ: xác nhận thanh toán, kiểm tra quyền truy cập quan trọng. Dùng Set hoặc DB trực tiếp.
• Cần delete element — dùng Cuckoo Filter (CF.* commands trong RedisBloom).
• Dataset nhỏ (< 10k items) — Set Redis đơn giản hơn nhiều, memory không phải vấn đề.
• Cần biết đếm số lần xuất hiện — Bloom chỉ trả lời "có / không", không đếm được.

RedisBloom là một module Redis cung cấp Bloom Filter, Cuckoo Filter, Count-Min Sketch, Top-K, và T-Digest. Module này được tích hợp sẵn trong Redis Stack.

Cách 1 — Redis Stack qua Docker (khuyến nghị cho dev):

docker run -p 6379:6379 redis/redis-stack-server

# Redis Stack bao gồm:
# RedisBloom + RedisJSON + RediSearch + RedisTimeSeries + RedisGraph (deprecated)

Cách 2 — Load module standalone (production):

# Tải redisbloom.so từ https://github.com/RedisBloom/RedisBloom/releases
# Trong redis.conf:
loadmodule /path/to/redisbloom.so

# Hoặc khi khởi động:
redis-server --loadmodule /path/to/redisbloom.so

Cách 3 — Redis Cloud / Upstash: Redis Cloud và Upstash đều hỗ trợ Redis Stack built-in, không cần cấu hình thêm.

Kiểm tra module đã load chưa:

redis-cli MODULE LIST
# → nếu thấy "bf" trong danh sách → RedisBloom đã active

# Tạo filter với FPR và capacity dự kiến
BF.RESERVE key error_rate capacity
# error_rate: FPR mong muốn (0.0 - 1.0), ví dụ 0.01 = 1%
# capacity: số items dự kiến tối đa trước khi FPR bắt đầu tăng
# Ví dụ:
BF.RESERVE filter:emails 0.001 1000000  # FPR 0.1%, expect 1M items

# Thêm 1 item
BF.ADD key item
# → 1 nếu item mới được thêm lần đầu (bit state thay đổi)
# → 0 nếu item đã tồn tại (không có nghĩa là chắc chắn trùng — BF không lưu exact)

# Thêm nhiều items
BF.MADD key item1 item2 item3 ...
# → array [1, 0, 1, ...] tương ứng từng item

# Check 1 item
BF.EXISTS key item
# → 1 (probably YES) hoặc 0 (definitely NO)

# Check nhiều items
BF.MEXISTS key item1 item2 item3 ...
# → array [1, 0, 1, ...] tương ứng từng item

# Xem thống kê filter
BF.INFO key
# → Capacity, Size (bytes), Number of filters (sub-filters), Number of items inserted,
#    Expansion rate, Max iterations

Lưu ý: nếu không gọi BF.RESERVE trước, BF.ADD sẽ tự tạo filter với default parameters (error_rate=0.01, capacity=100). Với production, luôn gọi BF.RESERVE để kiểm soát FPR và capacity.

Khi user đăng ký, cần kiểm tra email đã tồn tại chưa. Với hàng triệu user, mỗi request signup đều query DB là tốn kém. Bloom Filter làm pre-filter:

import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

# Khởi tạo filter một lần (có thể trong app startup hoặc migration)
# FPR 0.1%, capacity 5 triệu emails (overshoot 5x so với 1M user hiện tại)
def init_email_filter():
    try:
        r.bf().create("filter:emails", 0.001, 5_000_000)
    except Exception:
        pass  # filter đã tồn tại

# Khi ứng dụng khởi động: nạp emails từ DB vào filter (warm up)
def warm_up_email_filter(db_session):
    pipeline = r.pipeline(transaction=False)
    for i, email in enumerate(db_session.query_all_emails()):
        pipeline.bf().add("filter:emails", email)
        if i % 5000 == 0:
            pipeline.execute()
            pipeline = r.pipeline(transaction=False)
    pipeline.execute()

def signup(email: str, password: str, db_session):
    # Bước 1: Bloom pre-check (rất nhanh, không tốn DB)
    if r.bf().exists("filter:emails", email):
        # "Probably YES" — confirm với DB để tránh FP gây từ chối sai
        if db_session.user_exists_by_email(email):
            raise ValueError("Email already registered")
        # FP case: Bloom nói có nhưng DB không có → vẫn cho đăng ký

    # Bước 2: "Definitely NO" hoặc FP đã xử lý → tạo user
    user = db_session.create_user(email=email, password_hash=hash_password(password))

    # Bước 3: Thêm email mới vào filter
    r.bf().add("filter:emails", email)

    return user

Kịch bản FP: Bloom báo "có" nhưng DB không có email đó → vẫn cho đăng ký bình thường. FP chỉ gây ra thêm 1 query DB không cần thiết, không gây lỗi nghiêm trọng.

Kịch bản FN: không tồn tại (đảm bảo của Bloom Filter). Nếu Bloom nói "không có" thì chắc chắn email chưa được đăng ký.

Kiểm tra một URL có trong danh sách blacklist không (malware, phishing, spam). Số lượng blacklist URLs có thể lên tới hàng trăm triệu entries. Bloom Filter phù hợp vì FP chỉ gây "block nhầm 1 URL an toàn" — chấp nhận được hơn là FN (bỏ qua URL độc hại).

def init_url_blacklist(db_session):
    """Khởi tạo và nạp blacklist từ DB."""
    r.bf().create("filter:malicious_urls", 0.001, 50_000_000)  # 0.1% FPR, 50M URLs

    pipeline = r.pipeline(transaction=False)
    count = 0
    for url in db_session.query_malicious_urls():
        pipeline.bf().add("filter:malicious_urls", url)
        count += 1
        if count % 10000 == 0:
            pipeline.execute()
            pipeline = r.pipeline(transaction=False)
    pipeline.execute()

def is_url_safe(url: str) -> bool:
    """
    Trả về True nếu URL an toàn, False nếu cần chặn.
    FP: block nhầm URL an toàn (rare, ~0.1%).
    FN: không tồn tại — nếu Bloom nói an toàn thì chắc chắn an toàn.
    """
    return not r.bf().exists("filter:malicious_urls", url)

# Bulk check nhiều URLs cùng lúc (hiệu quả hơn loop)
def filter_safe_urls(urls: list[str]) -> list[str]:
    results = r.bf().mexists("filter:malicious_urls", *urls)
    return [url for url, is_blocked in zip(urls, results) if not is_blocked]

# Khi phát hiện URL độc hại mới
def report_malicious_url(url: str, db_session):
    db_session.add_malicious_url(url)
    r.bf().add("filter:malicious_urls", url)

Lưu ý: Bloom Filter không hỗ trợ xóa. Nếu một URL bị oan và cần xóa khỏi blacklist, bạn không thể xóa khỏi Bloom — cần rebuild filter từ DB. Đây là lý do một số hệ thống dùng Cuckoo Filter thay thế.

Khi recommend content hoặc hiển thị quảng cáo, cần tránh show lại những item user đã thấy. Với hàng triệu user, mỗi user một filter riêng:

class RecommendationDedup:
    def __init__(self, redis_client, fpr=0.01, capacity=2000):
        self.r = redis_client
        self.fpr = fpr           # 1% FPR — đôi khi bỏ sót item đã seen
        self.capacity = capacity  # 2000 items per user

    def _key(self, user_id: int) -> str:
        return f"filter:shown:{user_id}"

    def has_seen(self, user_id: int, item_id: str) -> bool:
        """True = probably seen. False = definitely not seen."""
        return bool(self.r.bf().exists(self._key(user_id), item_id))

    def mark_seen(self, user_id: int, item_id: str):
        """Ghi nhận user đã thấy item này."""
        key = self._key(user_id)
        # Auto-create với default nếu chưa có
        # Hoặc explicit reserve nếu muốn control FPR
        try:
            self.r.bf().create(key, self.fpr, self.capacity, expansion=2)
            self.r.expire(key, 86400 * 30)  # TTL 30 ngày
        except Exception:
            pass  # đã tồn tại
        self.r.bf().add(key, item_id)

    def filter_unseen(self, user_id: int, item_ids: list[str]) -> list[str]:
        """Trả về danh sách items user chưa thấy (chắc chắn chưa thấy)."""
        if not item_ids:
            return []
        results = self.r.bf().mexists(self._key(user_id), *item_ids)
        return [item for item, seen in zip(item_ids, results) if not seen]

# Sử dụng
dedup = RecommendationDedup(r)
candidates = get_candidate_items(user_id=42, limit=100)
unseen = dedup.filter_unseen(user_id=42, item_ids=candidates)
# FP 1%: ~1 item trong 100 bị bỏ sót (nghĩ là đã seen khi thực ra chưa)
# Chấp nhận được cho recommendation use case

Trade-off: FPR 1% nghĩa là cứ 100 item candidates, ~1 item bị bỏ qua nhầm (Bloom nghĩ đã seen nhưng thực ra chưa). Với recommendation, đây thường là chấp nhận được — user không nhận ra 1 item bị miss, trong khi hệ thống tiết kiệm đáng kể memory.

Bloom Filter tiêu chuẩn có fixed capacity: khi số items vượt capacity, FPR thực tế sẽ tăng vượt mức cấu hình. Nếu dataset không thể ước lượng chính xác trước, dùng Scalable Bloom Filter.

Scalable Bloom (SBF) hoạt động bằng cách tạo thêm sub-filter mới khi sub-filter hiện tại đầy, với capacity mỗi lần tăng theo hệ số expansion. FPR target được duy trì qua các lần expand.

# Tạo Scalable Bloom Filter
BF.RESERVE filter:users 0.01 10000 EXPANSION 2
# error_rate: 0.01 (1%)
# capacity: 10000 items (capacity của sub-filter đầu tiên)
# EXPANSION 2: mỗi lần expand, sub-filter mới có capacity gấp đôi

# Không cần làm gì thêm — filter tự expand khi đầy
BF.ADD filter:users "user:1001"  # thêm bình thường

# Python redis-py
r.bf().create("filter:users", 0.01, 10000, expansion=2)
r.bf().add("filter:users", "user:1001")

# Xem trạng thái expansion
info = r.bf().info("filter:users")
# info.filters → số sub-filters hiện có
# info.insertedNum → tổng số items đã insert

Nhược điểm của Scalable Bloom: CHECK phải scan qua tất cả sub-filter → latency tăng nhẹ khi số sub-filter nhiều. Với expansion=2 và 10 lần expand, bạn có 10 sub-filter, mỗi CHECK cần tối đa 10 lần hash. Trong thực tế, filter được check từ mới nhất → cũ nhất, dừng khi tìm thấy.

Bloom Filter không hỗ trợ xóa phần tử. Nếu cần delete (ví dụ: user unsubscribe khỏi blacklist, rút lại báo cáo URL), dùng Cuckoo Filter — cũng có trong RedisBloom.

Cuckoo Filter dùng cuckoo hashing thay vì bit array. Đặc điểm:

• Hỗ trợ delete với CF.DEL.
• FPR thấp hơn một chút so với Bloom cùng kích thước.
• Memory slightly larger hơn Bloom ở cùng FPR target.
• Không hỗ trợ Scalable (fixed capacity).

# Cuckoo Filter commands
CF.RESERVE key capacity              # tạo filter
CF.ADD key item                      # thêm item (cho phép duplicate)
CF.ADDNX key item                    # thêm chỉ nếu chưa có
CF.INSERT key item1 item2 ...        # bulk add
CF.EXISTS key item                   # check
CF.DEL key item                      # xóa 1 lần xuất hiện
CF.COUNT key item                    # đếm số lần item được add
CF.INFO key                          # stats

# Ví dụ: user unsubscribe
def unsubscribe(user_id: int):
    r.cf().delete("filter:subscribers", str(user_id))
    # Sau này BF.EXISTS sẽ trả về 0 cho user_id này

# Lưu ý: CF.DEL xóa 1 lần insert. Nếu add 2 lần thì cần del 2 lần
r.cf().add("filter:subscribers", "user:42")
r.cf().add("filter:subscribers", "user:42")  # add 2 lần
r.cf().delete("filter:subscribers", "user:42")  # xóa 1 lần
r.cf().exists("filter:subscribers", "user:42")   # → 1 (vẫn còn 1 count)

Khi nào chọn Cuckoo thay Bloom: dataset có thể xóa (blacklist URL có thể gỡ, subscription toggle, session revocation phức tạp). Trong các trường hợp khác, Bloom là đủ và đơn giản hơn.

Bảng memory ước tính cho các cấu hình Bloom Filter với 1 triệu items:

FPR        | Bits per item | Memory (1M items) | K (hash fns)
-----------|---------------|-------------------|-------------
0.1%       |     14.4      |     ~1.7 MB       |    10
0.5%       |     11.5      |     ~1.4 MB       |     8
1%         |     9.6       |     ~1.2 MB       |     7
5%         |     6.2       |     ~0.75 MB      |     5
10%        |     4.8       |     ~0.58 MB      |     4

# Công thức: bits_per_item = -log2(FPR) / ln(2) ≈ 1.44 * log2(1/FPR)
# 1% FPR → ~9.6 bits/item
# 0.1% FPR → ~14.4 bits/item (chỉ tăng 50% memory cho 10x accuracy)

Với 100M items:

FPR 1%   → ~120 MB
FPR 0.1% → ~171 MB
FPR 0.01% → ~229 MB

# So sánh với Redis Set 100M UUID (36-byte string):
# ~6.4 GB → tiết kiệm 37x - 56x tùy FPR

Quy tắc thực tế: với application dùng FPR 1% là đủ trong hầu hết trường hợp. Chỉ giảm FPR xuống 0.1% khi chi phí FP cao (ví dụ: mỗi FP gây 1 DB query tốn kém). Giảm xuống 0.01% ít khi cần thiết.

Bloom Filter phổ biến nhất khi kết hợp với các tầng lưu trữ khác, tạo thành kiến trúc 3 tầng:

Request
  │
  ▼
┌─────────────────────────────┐
│ Tier 1: Bloom Filter        │  → "definitely NO" → stop, no DB/cache call
│ (probabilistic, ~MB)        │  → "probably YES"  → check tier 2
└─────────────────────────────┘
  │ probably YES
  ▼
┌─────────────────────────────┐
│ Tier 2: Redis Cache         │  → HIT  → return exact data
│ (exact, sub-millisecond)    │  → MISS → check tier 3
└─────────────────────────────┘
  │ miss
  ▼
┌─────────────────────────────┐
│ Tier 3: Database            │  → source of truth, exact
│ (persistent, ms latency)    │
└─────────────────────────────┘

def get_user(user_id: int) -> dict | None:
    """
    3-tier lookup với Bloom pre-filter.
    Tier 1: Bloom — nếu "NO" thì user chắc chắn không tồn tại
    Tier 2: Redis cache — nếu hit thì trả ngay
    Tier 3: DB — source of truth
    """
    uid = str(user_id)

    # Tier 1: Bloom check
    if not r.bf().exists("filter:users", uid):
        return None  # definitely NO — không cần hỏi cache hay DB

    # Tier 2: Redis cache check
    cache_key = f"user:{uid}"
    cached = r.get(cache_key)
    if cached:
        return json.loads(cached)

    # Tier 3: DB lookup (Bloom có thể FP → user không tồn tại trong DB)
    user = db.get_user_by_id(user_id)
    if user:
        r.setex(cache_key, 300, json.dumps(user))
    return user

Lợi ích rõ nhất trong trường hợp tấn công bằng random ID: nếu không có Bloom, mỗi request với ID không tồn tại đều miss cache và đánh xuống DB. Bloom loại hầu hết trong số đó ngay từ tầng đầu tiên.

Bloom Filter trong Redis được lưu dưới dạng một Redis key bình thường (kiểu string binary). Điều này có nghĩa là:

• RDB / AOF lưu được filter như mọi key thông thường. Restart Redis với persistence enabled → filter được restore.
• DUMP / RESTORE: có thể migrate filter sang instance khác.
• PERSIST / EXPIRE: gán TTL cho filter key như bình thường nếu cần filter tự xóa theo thời gian.

# Gán TTL cho filter (ví dụ filter dedup theo ngày)
EXPIRE filter:shown:2026-06-01 86400  # tự xóa sau 1 ngày

# Dump filter để migrate
DUMP filter:emails  # serialize
# Sau đó RESTORE trên instance đích

Điểm cần chú ý: nếu Redis restart không có persistence (no RDB, no AOF), filter sẽ mất. Lúc này cần rebuild từ DB (warm-up lại). Đây là lý do các hệ thống production thường bật RDB hoặc AOF, hoặc thiết kế warm-up script để chạy sau mỗi lần restart.

• Coi Bloom như exact set: thực hiện action quan trọng trực tiếp dựa trên kết quả "probably YES" mà không confirm lại. Ví dụ: từ chối đăng ký email chỉ vì Bloom nói "có" mà không query DB — sẽ từ chối nhầm user hợp lệ (FP case).

  # SAI — từ chối trực tiếp dựa vào Bloom
  if r.bf().exists("filter:emails", email):
      raise ValueError("Email already registered")  # BUG: FP = từ chối oan
  
  # ĐÚNG — confirm với DB khi Bloom nói "có"
  if r.bf().exists("filter:emails", email):
      if db.user_exists(email):
          raise ValueError("Email already registered")

• Underestimate capacity: đặt capacity quá thấp so với số items thực tế sẽ ADD. Khi số items vượt capacity, FPR thực tế tăng vượt mức cấu hình. Luôn overshoot capacity ít nhất 2x nếu không dùng Scalable Bloom.
• Không backup filter: restart Redis không có persistence → filter mất → phải rebuild từ DB (tốn thời gian, trong khi chờ warm-up, hệ thống thiếu protection). Bật RDB hoặc có warm-up script.
• Dùng Bloom cho dataset nhỏ: với < 10k items, Redis Set đơn giản hơn, không có FP, memory không phải vấn đề.
• Dùng Bloom khi cần delete: Bloom không hỗ trợ delete. Nếu xóa phần tử là yêu cầu bắt buộc, dùng Cuckoo Filter.
• Không đặt TTL cho per-user filter: mỗi user một filter (recommendation dedup) mà không có TTL → filter tích lũy mãi → memory leak theo thời gian. Đặt TTL phù hợp (ví dụ 30 ngày).

• Luôn gọi BF.RESERVE trước để kiểm soát FPR và capacity. Không dựa vào auto-create với default (capacity=100 quá nhỏ).
• Overshoot capacity 2x: nếu dự kiến 1M items, đặt capacity=2M. Bloom không scale tốt khi vượt capacity.
• Dùng Scalable Bloom cho dynamic dataset: khi không thể ước lượng chính xác số items, BF.RESERVE ... EXPANSION 2.
• Bloom là pre-filter, không phải final answer: luôn confirm với tầng chính xác hơn khi kết quả critical (billing, security, user-facing error).
• Bật persistence (RDB minimum) hoặc có warm-up script để rebuild filter sau restart.
• Monitor với BF.INFO: theo dõi số items inserted so với capacity. Khi > 80% capacity (non-scalable), cân nhắc rebuild với capacity lớn hơn.
• Document FPR config trong codebase: comment rõ FPR đang dùng là bao nhiêu, impact là gì, và tại sao chọn giá trị đó.
• Đặt TTL cho per-user filter: tránh memory leak từ filter của inactive user.

Bloom Filter giải quyết membership check ở scale lớn với memory nhỏ hơn nhiều lần so với Set thông thường. Đánh đổi là chấp nhận false positive rate — luôn cần bước confirm thứ hai khi kết quả critical. RedisBloom (có trong Redis Stack) cung cấp BF.RESERVE/BF.ADD/BF.EXISTS/BF.INFO. Với dataset có delete, dùng Cuckoo Filter. Với dataset size không biết trước, dùng Scalable Bloom với EXPANSION.

Quiz

1. Bloom Filter trả về "probably YES" — điều đó có nghĩa là gì? Ứng dụng nên làm gì tiếp theo?
2. Vì sao Bloom Filter không có false negative? Giải thích qua cơ chế bit array.
3. Dự án có 500k user hiện tại, dự kiến tăng lên 3M trong 1 năm. FPR yêu cầu là 0.5%. Nên cấu hình BF.RESERVE như thế nào?
4. User A report URL X là malware và sau đó rút lại. Tại sao không thể dùng Bloom Filter cho trường hợp này? Dùng gì thay thế?
5. Bloom Filter đang có 900k items trong capacity 1M (90% full). FPR đang xảy ra là bao nhiêu so với FPR lúc cấu hình? Nên làm gì?

Đáp án gợi ý

1. "Probably YES" nghĩa là phần tử có thể có hoặc không có trong set (false positive có thể xảy ra). Ứng dụng nên confirm với tầng chính xác hơn (Redis cache hoặc DB) trước khi thực hiện action có hệ quả.
2. Bloom CHECK hoạt động bằng cách check K bits. Nếu bất kỳ bit nào bằng 0, phần tử chắc chắn chưa được ADD (vì ADD set tất cả K bit thành 1). Một bit 0 duy nhất là bằng chứng đủ để kết luận "definitely NO".
3. BF.RESERVE filter:users 0.005 6000000 EXPANSION 2 — capacity 6M (overshoot 2x của 3M), hoặc dùng Scalable Bloom để tự expand. FPR 0.005 = 0.5%.
4. Bloom Filter không hỗ trợ delete — không thể xóa URL X khỏi filter sau khi đã ADD. Dùng Cuckoo Filter (CF.*) để có khả năng CF.DEL khi cần gỡ URL khỏi blacklist.
5. Khi số items gần hoặc vượt capacity, FPR thực tế tăng đáng kể vượt FPR cấu hình. Nên: (a) rebuild filter với capacity lớn hơn từ DB, hoặc (b) nếu đã dùng Scalable Bloom thì filter tự thêm sub-filter mới — BF.INFO để kiểm tra expansion đã xảy ra chưa.

Bài tiếp theo

Bài 94 đi sâu vào HyperLogLog: thuật toán, độ chính xác (standard error 0.81%), use case distinct count ở scale lớn, và so sánh với Bloom Filter ở điểm giao nhau.

Tham khảo

• Redis Docs — Bloom Filter
• Redis Docs — Cuckoo Filter
• Redis Docs — BF.* Commands Reference
• Redis Docs — CF.* Commands Reference
• RedisBloom — GitHub Repository
• Redis Stack — RedisBloom Module
• Bloom Filter Calculator — Thomas Hurst