Bloom Filter Là Cái Vẹo Gì?

Header Image

Giới thiệu

Bloom Filter là một cấu trúc dữ liệu xác suất (probabilistic data structure). Tại sao nói xác suất? Nó có thể nhanh chóng kết luận một phần tử CHẮC CHẮN KHÔNG nằm trong tập hợp, nhưng chỉ có thể dự đoán một phần tử CÓ THỂ CÓ nằm trong tập hợp mà thôi.

Cấu trúc dữ liệu này phát huy được tính ứng dụng của mình rõ nhất thông qua việc truy vấn những tài nguyên expensive-to-access như gửi request lên server qua internet, hay đọc dữ liệu từ ổ đĩa. Giả sử, để kiểm tra xem phần tử foo có tồn tại trong một cơ sở dữ liệu (CSDL) hay không, ta có thể truy vấn Bloom Filter trước; nếu không tồn tại trong filter, ta có thể yên tâm bỏ qua bước truy vấn tốn kém vào CSDL; ngược lại, ta vẫn cần truy vấn vào CSDL để chắc chắn foo tồn tại thật. Ngoài ra, nó cũng tiết kiệm không gian bộ nhớ (memory efficient) hơn rất nhiều so với bảng băm (hash table), trong khi hiệu năng hoàn toàn tương đương.

Dẫu vậy, Bloom Filter vẫn có nhược điểm. Luôn tồn tại một tỉ lệ lỗi false positives (có thể kiểm soát được) khi nó khẳng định một phần tử có tồn tại, nhưng trên thực tế thì không. Không như bảng băm, Bloom Filter không lưu trực tiếp giá trị của phần tử vào bộ nhớ nên không có cách nào lấy lại giá trị ấy. Ta cũng không thể xoá một phần tử ra khỏi filter.

Một vài biến thể: Counting Bloom Filter, Partitioned Bloom Filter, Cuckoo Filter, Count Min Sketch,…

Cách thức hoạt động

Bloom Filter thực chất là một dãy bits (bit array/vector). Trước khi một phần tử được thêm vào, nó sẽ được băm (hashed). bits[hashval % nbits] được chuyển thành 1. Cơ chế này tương đối giống bảng băm. Để kiểm tra một phần tử tồn tại hay không, filter sẽ kiểm tra giá trị băm và bit tương ứng trong dãy bits đã được chuyển thành 1 hay chưa.

VD: hash(item) % 8 = 2

0	0	1	0	0	0	0	0

Bạn có thể thấy, cơ chế hoạt động như trên có thể dẫn đến xung đột (collisions). Nếu hash(another_item) % 8 = 2, filter sẽ bị lỗi false positive - khẳng định another_item có tồn tại trong khi thực tế không phải vậy.

Có hai cách để giảm thiểu tỉ lệ xảy ra lỗi này. Cách đầu tiên là tăng kích thước dãy bits. Cách thứ hai là sử dụng nhiều hơn 1 bit để xác định một phần tử, tức là thực hiện băm nhiều lần (multiple hashing).

VD:

hash(item, 0) % 16 = 2
hash(item, 1) % 16 = 0
hash(item, 1) % 16 = 11

1	0	1	0	0	0	0	0	0	0	0	1	0	0	0	0

Ở đây, ta đã tăng gấp đôi kích thước dãy bits (từ 8 lên 16). Thay vì băm một lần, ta cũng đã tăng lên ba lần với 3 seeds khác nhau để nhận được các giá trị băm khác nhau. Để chắc chắn item không có trong filter, chỉ cần 1 trong 3 bits 0, 2 hoặc 11 được tắt.

Bloom Filter + Redis = RedisBloom

Trong thực tế, mình sử dụng Bloom Filter với Redis (in-memory database), thông qua RedisBloom module. Để sử dụng module này trong Node.js một cách thuận tiện hơn, mình đã và đang phát triển một thư viện client mang tên Rebloom. Bạn có thể ngó qua trang Github của nó tại đây và NPM package tại đây.

Đọc thêm

Cảm ơn các bạn đã dành thời gian đọc hết bài viết này của mình. Nếu quan tâm và muốn đóng góp cho Rebloom, đừng ngần ngại, just fork it.