Bloom filter: trả lời "chắc chắn không có" với vài bit mỗi phần tử

Một con bot gọi GET /api/san-pham/{ma} khoảng 1.000 lần mỗi giây (minh họa), mỗi lần một mã khác: SP-99999, SP-31337, SP-77777. BanHang chỉ có 5.000 sản phẩm, từ SP-00001 đến SP-05000. Không mã nào bot hỏi có trong cache, nên request nào cũng xuống SQL Server rồi trả 404. Bloom filter chặn loại request này ngay trong RAM của API, với khoảng 9,6 bit mỗi khóa ở tỉ lệ sai 1%. Bài này dựng nó bằng Python, tính kích thước cho 1.000.000 khóa, đo tỉ lệ sai thật, và chỉ ra chỗ nó không dùng được.

1. Request xuyên qua cache #

Đường đọc sản phẩm của BanHang là cache-aside: hỏi cache trước, miss thì đọc dbo.SanPham qua UQ_SanPham_Ma rồi nạp vào cache. Mã không tồn tại thì không có gì để nạp, lần sau lại miss. Hiện tượng này gọi là cache penetration. 1.000 request mỗi giây của bot gấp hơn ba lần lưu lượng thật lúc cao điểm. Mỗi index seek rẻ, nhưng vẫn tốn một round-trip, một connection trong pool, và CPU mà khách thật cần.

Cache luôn kết quả "không có" (negative caching) chỉ giúp khi bot hỏi lại cùng một mã. Mã ngẫu nhiên gần như không lặp lại, nên cache chỉ đầy thêm mục vô ích. Cần một bước kiểm tra trong RAM, đứng trước cache:

flowchart LR
    A["GET /api/san-pham/SP-99999"] --> B{"Bloom filter"}
    B -->|"chắc chắn không có"| C["404 ngay, không gọi cache hay DB"]
    B -->|"có thể có"| D{"Cache"}
    D -->|"hit"| E["200"]
    D -->|"miss"| F["SQL Server"]

Với 5.000 mã, một set trong bộ nhớ là đủ và không bao giờ sai. Bài toán đổi khi tập khóa lớn: bot cũng dò 1.000.000 mã giảm giá BanHang đã phát hành, dạng GG-0123456789. Set Python chứa chừng ấy mã chiếm 83,5 MiB (đo ở mục 5). Bloom filter chiếm 1,14 MiB, đổi lại khoảng 1% mã không tồn tại vẫn lọt qua.

2. Cơ chế: m bit và k hàm hash #

Bloom filter (Burton Bloom, 1970) gồm một mảng m bit, ban đầu toàn 0, và k hàm hash biến khóa thành vị trí từ 0 đến m − 1. Thêm khóa thì bật k bit tại k vị trí. Hỏi khóa mà gặp một bit 0 thì trả lời "chắc chắn không có", vì khóa đã thêm thì bit đó phải là 1. Cả k bit là 1 thì trả lời "có thể có". Minh họa với m = 16, k = 3, vị trí chọn tay:

Thêm SP-00042 -> 3, 7, 12     Thêm SP-00043 -> 1, 7, 14     (bit 7 dùng chung)
vị trí   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bit      0  1  0  1  0  0  0  1  0  0  0  0  1  0  1  0
Hỏi SP-99999 -> 3, 9, 14      bit 9 = 0: chắc chắn không có
Hỏi SP-77777 -> 1, 3, 12      cả ba bit = 1: có thể có (dương tính giả)

SP-77777 chưa từng được thêm, nhưng ba bit của nó do hai khóa khác bật. Chiều ngược lại không xảy ra: bit đã bật không bao giờ tắt. Vì vậy Bloom filter không có âm tính giả, với hai điều kiện: không ai xóa bit, và khóa thật sự đã được thêm (mục 6).

Sau n lần thêm, một bit vẫn là 0 với xác suất xấp xỉ e^(−kn/m). Khóa lạ lọt qua khi cả k vị trí của nó rơi vào bit 1, nên p ≈ (1 − e^(−kn/m))^k. Với filter ở mục 3 (n = 5.000, m = 47.928, k = 7): tỉ lệ bit 1 là 1 − e^(−0,7303) = 0,518, và p ≈ 0,518^7 = 1,00%.

Kirsch và Mitzenmacher (2008) chứng minh chỉ cần hai giá trị hash h1, h2: vị trí thứ i là (h1 + i·h2) mod m, và tỉ lệ dương tính giả tiệm cận không đổi. Code dưới đây lấy h1, h2 từ một lần BLAKE2b 128 bit.

3. Code: Bloom filter bằng thư viện chuẩn #

Lưu thành bloom.py. Cần Python 3.10 trở lên vì có int.bit_count(). Bài chạy bằng Python 3.14.3.

import hashlib
import math


class BloomFilter:
    def __init__(self, n: int, p: float):
        bits = math.ceil(-n * math.log(p) / math.log(2) ** 2)
        self.bits = bytearray((bits + 7) // 8)   # làm tròn lên cả byte
        self.m = len(self.bits) * 8              # nên m luôn chẵn
        self.k = max(1, round(self.m / n * math.log(2)))

    def _positions(self, key: str) -> list[int]:
        d = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1  # số lẻ: h2 mod m không bao giờ bằng 0
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key: str) -> None:
        for pos in self._positions(key):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, key: str) -> bool:
        return all(self.bits[pos >> 3] >> (pos & 7) & 1 for pos in self._positions(key))

    def fill_ratio(self) -> float:
        return int.from_bytes(self.bits, "little").bit_count() / self.m


if __name__ == "__main__":
    san_pham = [f"SP-{i:05d}" for i in range(1, 5001)]  # 5.000 mã thật
    bf = BloomFilter(n=len(san_pham), p=0.01)
    for ma in san_pham:
        bf.add(ma)
    print(f"m = {bf.m} bit = {bf.m // 8} byte, k = {bf.k}")
    print("SP-00042:", "SP-00042" in bf, "| SP-99999:", "SP-99999" in bf)
    quet = [f"SP-{i:05d}" for i in range(5001, 100000)]   # bot quét mọi mã còn lại
    lot = sum(ma in bf for ma in quet)
    print(f"bot quét {len(quet)} mã không tồn tại, lọt qua {lot} = {lot / len(quet):.2%}")

Nếu h2 mod m bằng 0, cả k vị trí sẽ trùng vào một bit. Vì vậy m được giữ chẵn và h2 luôn lẻ.

Kết quả python bloom.py:

m = 47928 bit = 5991 byte, k = 7
SP-00042: True | SP-99999: False
bot quét 94999 mã không tồn tại, lọt qua 950 = 1.00%

5.000 mã tốn 5.991 byte. Trong 94.999 mã bot quét, 950 mã lọt qua, đúng 1,00%. Từ 1.000 request mỗi giây của bot, chỉ khoảng 10 request đi tiếp xuống cache và database.

4. Chọn m và k #

Với m và n cố định, k nhỏ thì khóa lạ dễ lọt, k lớn thì mảng đầy nhanh. Tối ưu là k = (m/n)·ln 2: khi đó một nửa số bit là 1 và p = (1/2)^k. Đảo lại, m = −n·ln p / (ln 2)². Cho 1.000.000 mã giảm giá với p = 1%:

m = 1.000.000 × 4,6052 / 0,48045 = 9.585.059 bit = 1.198.133 byte ≈ 1,14 MiB, tức 9,59 bit mỗi mã
k = 9,585 × 0,6931 = 6,64, làm tròn thành 7

• Độ dài khóa không có trong công thức. Mã 13 ký tự hay email 40 ký tự đều tốn 9,59 bit mỗi khóa ở 1%.
• k phải đúng. Giữ 9,59 bit mỗi khóa mà dùng k = 3 thì p = 1,94%, dùng k = 14 thì p = 2,48%.

5. Đo trên 1.000.000 mã giảm giá #

Lưu thành thu_nghiem.py cạnh bloom.py. Từ hạt giống 2026, script sinh 2.200.000 mã khác nhau: 1.000.000 mã đã phát hành, 1.000.000 mã cho phép thử quá tải, và 200.000 mã bot thử.

import math
import random
import sys

from bloom import BloomFilter

N = 1_000_000
rng = random.Random(2026)
so = rng.sample(range(10**10), 2 * N + 200_000)       # các số khác nhau từng đôi
ma = [f"GG-{x:010d}" for x in so]
da_phat_hanh, phat_them, bot_thu = ma[:N], ma[N:2 * N], ma[2 * N:]


def do_fp(bf):                     # 200.000 mã bot thử, không mã nào đã phát hành
    return sum(c in bf for c in bot_thu) / len(bot_thu)


def cong_thuc(bf, n):              # p ≈ (1 − e^(−kn/m))^k
    return (1 - math.exp(-bf.k * n / bf.m)) ** bf.k


for p in (0.001, 0.01):
    bf = BloomFilter(N, p)
    for c in da_phat_hanh:
        bf.add(c)
    assert all(c in bf for c in da_phat_hanh)          # không có âm tính giả
    print(f"p = {p}: m = {bf.m} bit = {bf.m / 8 / 2**20:.2f} MiB, k = {bf.k}, "
          f"bit 1: {bf.fill_ratio():.1%}")
    print(f"  n = N : đo {do_fp(bf):.3%}, công thức {cong_thuc(bf, N):.3%}")

for c in phat_them:                # filter 1% vừa dựng, nạp gấp đôi số đã thiết kế
    bf.add(c)
print(f"  n = 2N: đo {do_fp(bf):.3%}, công thức {cong_thuc(bf, 2 * N):.3%}, "
      f"bit 1: {bf.fill_ratio():.1%}")

byte_set = sys.getsizeof(set(da_phat_hanh)) + sum(map(sys.getsizeof, da_phat_hanh))
print(f"set Python chứa {N} mã: {byte_set / 2**20:.1f} MiB")

Kết quả python thu_nghiem.py:

p = 0.001: m = 14377592 bit = 1.71 MiB, k = 10, bit 1: 50.1%
  n = N : đo 0.090%, công thức 0.100%
p = 0.01: m = 9585064 bit = 1.14 MiB, k = 7, bit 1: 51.8%
  n = N : đo 0.995%, công thức 1.004%
  n = 2N: đo 15.715%, công thức 15.745%, bit 1: 76.8%
set Python chứa 1000000 mã: 83.5 MiB

Đo trên Windows 11, Intel Core Ultra 5 125U, Python 3.14.3. Script mất 2 đến 4 phút tùy lần chạy, vì Python thuần chậm và máy đang bận việc khác. Các tỉ lệ thì chạy lại vẫn ra đúng như trên, vì hạt giống và BLAKE2b cố định.

• assert qua với cả 1.000.000 mã đã thêm: không có âm tính giả.
• Ở p = 1%: đo 0,995%, công thức 1,004%. Ở p = 0,1%: đo 0,090%, tức 180 lần trúng so với kỳ vọng 200, chênh khoảng 1,4 độ lệch chuẩn (√200 ≈ 14).
• Tỉ lệ bit 1 là 51,8% và 50,1%, đúng dự đoán "khoảng một nửa" ở k tối ưu.
• Set Python tốn 83,5 MiB, gấp 73 lần filter 1%. Con số này riêng cho Python, nhưng giữ nguyên khóa thì tối thiểu cũng 13 byte mỗi mã, tức 12,4 MiB, gần 11 lần filter.

Dòng n = 2N là phép thử quá tải: filter thiết kế cho 1.000.000 mã bị nạp 2.000.000 mã. Tỉ lệ bit 1 lên 76,8%, và 0,768^7 = 15,7%. Filter không báo lỗi, chỉ âm thầm cho lọt gần gấp 16 lần.

6. Giới hạn #

Không xóa được. Tắt một bit có thể xóa luôn khóa khác dùng chung bit đó, như bit 7 ở mục 2. Counting Bloom filter (Fan và cộng sự, 2000) thay mỗi bit bằng một bộ đếm, thường 4 bit: xóa được, nhưng tốn gấp 4 lần bộ nhớ. Cuckoo filter (Fan và cộng sự, 2014) lưu fingerprint ngắn của khóa, hỗ trợ xóa, và theo paper tốn ít bit hơn Bloom filter khi p dưới 3%. Cả hai chỉ được xóa khóa chắc chắn đã thêm. Với BanHang, sản phẩm đã gỡ mà còn trong filter chỉ gây dương tính giả, nên dựng lại filter định kỳ là đủ.

Phải biết trước n. Nạp gấp đôi thì 1% thành 15,7%. Vị trí phụ thuộc m, nên không nới filter tại chỗ được. Redis chọn cách xếp chồng: vượt capacity thì thêm một sub-filter lớn gấp EXPANSION lần (mặc định 2). Tỉ lệ sai giữ gần mức đặt trước, đổi lại mỗi lần hỏi phải đi qua nhiều sub-filter hơn.

Vô ích khi đa số truy vấn trúng. Filter chỉ tiết kiệm khi trả lời "không có". Nếu 99% truy vấn hỏi khóa có thật, nó chỉ thêm chi phí tính hash. RocksDB có tùy chọn optimize_filters_for_hits để bỏ filter ở level cuối cho loại tải này.

Filter không chặn bot, chỉ làm mỗi lần dò rẻ đi. Vẫn cần giới hạn tần suất.

7. Bloom filter trong hệ thống thật #

• RocksDB: mỗi SST file mới chứa một Bloom filter. Get bỏ qua những file mà filter trả "không có". Wiki RocksDB ghi 9,9 bit mỗi khóa cho 1%, sát con số 9,59 ở mục 4.
• Cassandra (tài liệu bản 5.0): Bloom filter giúp read path khỏi kiểm mọi SSTable. bloom_filter_fp_chance mặc định 0,01, riêng bảng dùng LeveledCompactionStrategy là 0,1.
• PostgreSQL: module bloom trong contrib cung cấp một loại index, hợp với truy vấn so sánh bằng trên tổ hợp tùy ý của nhiều cột. Kết quả luôn được kiểm tra lại với dòng trong heap.
• Redis: từ Redis Open Source 8.0 (tháng 5/2025), Bloom filter có sẵn: BF.RESERVE ma_giam_gia 0.01 1000000, rồi BF.ADD và BF.EXISTS. Tài liệu ghi 9,585 bit mỗi phần tử và 7 hàm hash cho 1%, khớp mục 4.
• SQL Server: kế hoạch song song có toán tử Bitmap. Tài liệu Microsoft mô tả nó là biểu diễn gọn của tập giá trị từ một nhánh, dùng để loại sớm những dòng ở nhánh khác không thể tạo ra kết quả join. Tài liệu không gọi nó là Bloom filter, nhưng nó cũng chỉ loại dòng chắc chắn không khớp.

Những chỗ hay hiểu sai #

• "Filter trả lời có thì khóa có." Sai. Đó chỉ là "có thể có": 0,995% mã không tồn tại ở mục 5 vẫn nhận "có". Phải kiểm tra lại ở nguồn thật.
• "Không có âm tính giả nên cập nhật filter lúc nào cũng được." Sai. Filter thiếu khóa mới sẽ trả "không có" cho khóa có thật.
• "Thiết kế 1% thì mãi là 1%." Sai. Nạp gấp đôi số khóa, đo được 15,7%.

Đọc tiếp #

• Consistent hashing: chia khóa cho nhiều node cache.
• Chỉ mục, thống kê: chi phí của index seek.
• Đọc kế hoạch thực thi: cách đọc toán tử, kể cả trong kế hoạch song song.

Nguồn #

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, 1970.
• Adam Kirsch, Michael Mitzenmacher, Less Hashing, Same Performance: Building a Better Bloom Filter, Random Structures & Algorithms, 2008.
• Flavio Bonomi và cộng sự, An Improved Construction for Counting Bloom Filters, ESA 2006.
• Bin Fan và cộng sự, Cuckoo Filter: Practically Better Than Bloom, CoNEXT 2014.
• RocksDB wiki, RocksDB Bloom Filter.
• Apache Cassandra 5.0, Bloom Filters.
• PostgreSQL 18, bloom.
• Redis, Bloom filter và Redis Open Source 8.0 release notes.
• Microsoft Learn, Showplan Logical and Physical Operators Reference, mục Bitmap.
• Python, PYTHONHASHSEED.