Bộ lọc Bloom: Kiểm tra khả năng thuộc tập ở quy mô lớn

Một API có thể nhận hàng triệu yêu cầu đọc object trong khi phần lớn ID không tồn tại. Mỗi lần trượt vẫn đi qua mạng, cơ sở dữ liệu và index. Set trong bộ nhớ chặn được chúng, nhưng lưu toàn bộ ID có thể tốn gần bằng index cần bảo vệ.

Bloom filter dùng mảng bit nhỏ và các vị trí băm để trả lời: âm nghĩa là chắc chắn không tồn tại, dương chỉ là “có thể tồn tại”. Đổi một tỷ lệ dương tính giả có kiểm soát lấy vài bit cho mỗi key, hệ thống tránh được phần lớn lookup vô ích. Muốn cam kết ấy đúng, ta phải tính kích thước, nạp dữ liệu, triển khai và giám sát cẩn thận.

Cam kết thành viên chỉ theo một chiều

Bloom filter chứa $m$ bit ban đầu bằng không và dùng $k$ vị trí băm cho mỗi key. Thêm key nghĩa là đặt cả $k$ bit thành một. Khi truy vấn, chỉ cần một bit bằng không thì key chắc chắn chưa được thêm; nếu tất cả bằng một, key có thể tồn tại hoặc các key khác đã tình cờ đặt chúng.

Vì thế filter chỉ đưa ra hai loại kết luận:

Chắc chắn không tồn tại: ít nhất một bit bắt buộc bằng không, nên có thể bỏ qua kho dữ liệu phía sau.
Có thể tồn tại: tất cả bit bắt buộc đều bằng một, nên kho dữ liệu thật vẫn phải quyết định.

Không có âm tính giả chỉ khi mọi key hiện hữu đã được thêm; writer và reader chuẩn hóa, mã hóa giống nhau; mảng bit không bị hỏng hay thay bằng snapshot cũ; và cập nhật đồng thời không làm mất thao tác đặt bit. Filter chuẩn cũng không được xóa bằng cách tắt bit dùng chung.

Warning

“Không có âm tính giả” không tự động trở thành thuộc tính của cả hệ thống phân tán. Replica chậm, sự kiện thay đổi bị mất, quy tắc chuẩn hóa key khác nhau hoặc việc đổi filter quá sớm đều có thể khiến một key thật trong cơ sở dữ liệu bị báo là không tồn tại dù thuật toán Bloom không sai.

Thêm và truy vấn tốn $O(k)$ ; không gian là $O(m)$ . Vì không giữ key, filter không thể liệt kê thành viên, trả dữ liệu hay giải thích nguyên nhân của kết quả dương.

Tính kích thước mảng bit và số hàm băm

Thiết kế filter bắt đầu từ hai thông số workload: số phần tử dự kiến $n$ và xác suất dương tính giả chấp nhận được $p$ . Sau khi thêm $n$ phần tử vào $m$ bit với $k$ vị trí cho mỗi phần tử, xác suất dương tính giả xấp xỉ là:

p = \left(1 - e^{-kn/m}\right)^k

Khi $m$ và $n$ cố định, số vị trí băm tối ưu là:

k_{\mathrm{opt}} = \frac{m}{n}\ln 2

Biến đổi công thức để tìm số bit cần thiết cho ta:

m = -\frac{n\ln p}{(\ln 2)^2}

Với mười triệu key và tỷ lệ dương tính giả một phần trăm, ta cần khoảng 95,9 triệu bit, tức 11,4 MiB, và $k=7$ . Ở mức 0,1 phần trăm, bộ nhớ khoảng 17,1 MiB và $k=10$ , vẫn thường nhỏ hơn mười triệu chuỗi cùng overhead của hash table.

Ước lượng $n$ phải thực tế. Filter thiết kế cho một triệu phần tử nhưng chứa ba triệu sẽ bão hòa và sai dương nhiều hơn hẳn. Capacity planning phải tính tăng trưởng, chu kỳ rebuild và traffic skew. Filter riêng theo tenant hoặc partition có thể cô lập tập dữ liệu nóng.

Note

Cần làm tròn $k$ về số nguyên. Thử cả hai số nguyên kề nhau sẽ tìm được kết quả chính xác hơn, nhưng Math.round((m / n) * Math.LN2) thường đã đủ. Nhiều hash hơn không phải lúc nào cũng tốt: vượt quá điểm tối ưu sẽ đặt bit nhanh hơn và làm tăng CPU cho mỗi truy vấn.

Production thường dùng double hashing Kirsch-Mitzenmacher: vị trí thứ $i$ là $h_1(x) + i h_2(x)$ . Hai hash nền phân phối tốt tránh phải chạy $k$ digest; hash tương quan hoặc phân phối kém sẽ phá vỡ mô hình xác suất.

Implementation TypeScript thực tế

Implementation sau tự tính kích thước, kiểm tra tham số, đóng gói bit trong Uint8Array và sinh mọi vị trí từ hai hash 32-bit. Nó còn cung cấp tỷ lệ bit đã bật và tỷ lệ dương tính giả hiện tại ước tính để theo dõi mức bão hòa.

export type BloomFilterStats = {
  bitSize: number;
  hashCount: number;
  setBits: number;
  fillRatio: number;
  estimatedFalsePositiveRate: number;
};

export class BloomFilter {
  readonly bitSize: number;
  readonly hashCount: number;
  private readonly bits: Uint8Array;

  constructor(expectedItems: number, falsePositiveRate: number) {
    if (!Number.isInteger(expectedItems) || expectedItems <= 0) {
      throw new RangeError('expectedItems must be a positive integer');
    }
    if (!(falsePositiveRate > 0 && falsePositiveRate < 1)) {
      throw new RangeError('falsePositiveRate must be between 0 and 1');
    }

    const rawBitSize =
      (-expectedItems * Math.log(falsePositiveRate)) /
      Math.LN2 ** 2;

    this.bitSize = Math.ceil(rawBitSize);
    this.hashCount = Math.max(
      1,
      Math.round((this.bitSize / expectedItems) * Math.LN2),
    );
    this.bits = new Uint8Array(Math.ceil(this.bitSize / 8));
  }

  add(value: string): void {
    for (const bitIndex of this.positions(value)) {
      const byteIndex = Math.floor(bitIndex / 8);
      const mask = 1 << (bitIndex % 8);
      this.bits[byteIndex]! |= mask;
    }
  }

  has(value: string): boolean {
    for (const bitIndex of this.positions(value)) {
      const byteIndex = Math.floor(bitIndex / 8);
      const mask = 1 << (bitIndex % 8);
      if ((this.bits[byteIndex]! & mask) === 0) {
        return false;
      }
    }
    return true;
  }

  stats(): BloomFilterStats {
    let setBits = 0;
    for (const byte of this.bits) {
      let remaining = byte;
      while (remaining !== 0) {
        remaining &= remaining - 1;
        setBits += 1;
      }
    }

    const fillRatio = setBits / this.bitSize;
    return {
      bitSize: this.bitSize,
      hashCount: this.hashCount,
      setBits,
      fillRatio,
      estimatedFalsePositiveRate: fillRatio ** this.hashCount,
    };
  }

  private *positions(value: string): Generator<number> {
    const bytes = new TextEncoder().encode(value);
    const first = BloomFilter.hash32(bytes, 0x811c9dc5);
    const second = BloomFilter.hash32(bytes, 0x9e3779b9) | 1;

    for (let index = 0; index < this.hashCount; index += 1) {
      const combined =
        (first + Math.imul(index, second) + Math.imul(index, index)) >>> 0;
      yield combined % this.bitSize;
    }
  }

  private static hash32(bytes: Uint8Array, seed: number): number {
    let hash = seed >>> 0;
    for (const byte of bytes) {
      hash ^= byte;
      hash = Math.imul(hash, 0x01000193);
    }

    hash ^= hash >>> 16;
    hash = Math.imul(hash, 0x85ebca6b);
    hash ^= hash >>> 13;
    hash = Math.imul(hash, 0xc2b2ae35);
    return (hash ^ (hash >>> 16)) >>> 0;
  }
}

Byte đóng gói giữ allocation gần kích thước lý thuyết, khác boolean[] có overhead lớn. TextEncoder cố định UTF-8; seed cố định tạo kết quả tất định. Hash thứ hai được ép lẻ để không rơi về không, còn thành phần bậc hai hạn chế chu kỳ ngắn.

Class trên dành cho một execution context. Nhiều worker cần cập nhật bit nguyên tử. Serialization phân tán phải có version và ghi bitSize, hashCount, thuật toán, seed, encoding; đổi một tham số nghĩa là đổi filter.

Đặt filter vào luồng request thật

Ứng dụng phổ biến nhất là bảo vệ một kho dữ liệu chậm hơn nhưng có thẩm quyền. Filter chỉ đóng vai trò tư vấn: kết quả âm có thể bỏ qua công việc, nhưng kết quả dương không thể tự trả lời request.

flowchart LR Client[Client request] --> API[API service] API --> Filter{Bloom filter} Filter -->|Definitely absent| Miss[Return not found] Filter -->|Maybe present| Cache{Cache lookup} Cache -->|Hit| Value[Return value] Cache -->|Miss| DB[(Database)] DB -->|Row found| Warm[Warm cache and return] DB -->|No row| Empty[Return not found] Writer[Committed writer] --> Events[Change stream] Events --> Filter

Để chống cache penetration, thêm mọi ID hợp lệ vào filter. ID ngẫu nhiên không tồn tại dừng trước cache và database; kết quả “có thể” vẫn phải lookup nguồn thật. Negative cache thì lưu miss gần đây theo TTL. Có thể dùng cả hai: Bloom filter chặn traffic chưa từng hợp lệ, negative cache hấp thụ dương tính giả lặp lại hoặc key vừa xóa.

Trong LSM-tree, mỗi SSTable bất biến có thể có filter riêng. Kết quả âm giúp bỏ qua file hoặc block I/O; kết quả dương mới tìm index thật. Partitioned filter cải thiện locality vì chỉ block filter liên quan được nạp.

Cấu trúc	Kết quả âm	Kết quả dương	Xóa	Trường hợp dùng
`Set` hoặc hash table	Chính xác	Chính xác	Có	Membership chính xác trong bộ nhớ
Bloom filter	Chính xác	Xác suất	Không an toàn	Bảo vệ cache, database hoặc storage read
Negative cache	Đúng đến TTL/invalidation	Không biểu diễn	Hết hạn hoặc invalidate	Lần miss lặp lại
Cuckoo filter	Chính xác	Xác suất	Có	Membership gần đúng có thay đổi
Counting Bloom filter	Chính xác	Xác suất	Có, kèm điều kiện	Luồng membership xóa nhiều

Khởi tạo thuộc về tính đúng đắn: dựng từ snapshot nhất quán rồi đọc các commit sau vị trí đó, hoặc dựng version mới, bắt kịp log và đổi reader nguyên tử. Không được tin kết quả âm từ filter rỗng đang nạp dần, vì key cũ chưa nạp sẽ thành âm tính giả.

Xóa, bộ đếm và các biến thể co giãn

Không được tắt bit trong filter chuẩn. Nếu alice và bob dùng chung vị trí, xóa alice sẽ làm bob có vẻ vắng mặt. Cứ giữ bit sẽ chỉ biến key đã xóa thành dương tính giả; rebuild định kỳ loại bỏ nhiễu này.

Counting Bloom filter thay bit bằng counter: insert tăng, delete giảm các vị trí. Xóa chỉ an toàn khi hai luồng cân bằng chính xác; xóa nhầm, xóa hai lần, tràn counter hoặc mất event có thể tạo âm tính giả. Counter bốn bit phổ biến nhưng tốn nhiều bộ nhớ hơn.

Cuckoo filter lưu fingerprint trong bucket, hỗ trợ xóa nhưng cần relocation và có thể hết chỗ. Stable Bloom filter làm già counter để giữ bộ nhớ cố định cho stream vô hạn, chấp nhận quên phần tử cũ. Scalable Bloom filter thêm subfilter lớn hơn với error budget giảm dần khi dữ liệu tăng.

Append-only và file bất biến hợp với filter chuẩn; xóa thường xuyên có thể hợp với Cuckoo; cửa sổ stream có thể chấp nhận aging. Nếu update không đáng tin mà âm tính giả bị cấm, hãy dùng exact index hoặc nguồn có thẩm quyền.

Kiểm thử, giám sát và giới hạn vận hành

Test phải khẳng định mọi key đã thêm đều trả true. Truy vấn một tập lớn, tất định và tách biệt để đo tỷ lệ dương tính giả với biên thống kê hợp lý. Cũng cần test Unicode, chuỗi rỗng, key dài, insert trùng, tham số sai và tương thích serialize/restore.

Trong production, ít nhất phải đo bốn giá trị: request bị filter trả âm, request bị trả dương, số lần backing store không tìm thấy sau kết quả dương, và tỷ lệ bit đã bật. Tỷ lệ dương tính giả thực nghiệm là:

p_{\mathrm{observed}} = \frac{\mathrm{positive\ backing\ misses}}{\mathrm{filter\ positives}}

Tỷ lệ này phụ thuộc traffic, không giống lấy mẫu đều từ không gian key. Tuy vậy, nó và fill level tăng là tín hiệu rebuild tốt. Hãy theo dõi số insert, tuổi version, change-stream lag, thời gian rebuild, checksum và cảnh báo consumer cũ hơn safe watermark.

Filter chỉ có lợi khi lookup âm phổ biến và thao tác được bảo vệ đắt hơn hashing. Nó gây thêm latency nếu hầu hết key tồn tại. Kết quả dương mơ hồ nên không thể làm ranh giới authorization, che giấu membership hay thay unique constraint. Nó cũng không tự chống hash-flooding. Filter tốn hơn hot exact index hoặc vẫn để database quá tải là một thiết kế thất bại.

Tip

Hãy xem tỷ lệ dương tính giả mục tiêu như một capacity contract. Lưu expected items, actual inserts, version và cấu hình hash cạnh mảng byte để operator có thể giải thích hành vi và rebuild trước khi filter bão hòa.

Điều cần ghi nhớ

Bloom filter chuẩn trả lời an toàn “chắc chắn không tồn tại” và chỉ có thể nói “có thể tồn tại.”
Cam kết không âm tính giả đòi hỏi nạp đủ dữ liệu, encoding và hashing ổn định, cập nhật bit đơn điệu cùng replica còn mới.
Hãy tính kích thước từ cardinality dự kiến và error budget; theo dõi fill ratio vì vượt dung lượng làm độ chính xác suy giảm rất nhanh.
Double hashing khiến việc sinh $k$ vị trí trở nên thực tế, còn mảng bit đóng gói giữ bộ nhớ gần mức lý thuyết.
Đặt filter trước cache, cơ sở dữ liệu hoặc file storage bất biến có thẩm quyền; không dùng nó làm nguồn sự thật.
Không tắt bit để xóa; hãy rebuild, dùng counter cẩn thận hoặc chọn Cuckoo filter hay biến thể phù hợp vòng đời.
Kiểm thử invariant của key đã thêm và hành vi xác suất, rồi giám sát backing miss, lag, tuổi version và mức bão hòa trong production.

Bloom filter mạnh chính vì nó hứa ít hơn một tập hợp chính xác. Khi luồng request tôn trọng lời hứa giới hạn ấy, vài megabyte bit có thể loại bỏ một lượng lớn công việc mạng, cache và storage mà không thay đổi sự thật do hệ thống phía sau quản lý.

Cam kết thành viên chỉ theo một chiều #

Tính kích thước mảng bit và số hàm băm #

Implementation TypeScript thực tế #

Đặt filter vào luồng request thật #

Xóa, bộ đếm và các biến thể co giãn #

Kiểm thử, giám sát và giới hạn vận hành #

Điều cần ghi nhớ #

Trie: Giải thích tìm kiếm tiền tố tốc độ cao

Các thuật toán đồ thị mọi kỹ sư nên biết

Hiểu Big-O vượt ra ngoài bảng tra cứu