Bloom Filter trong Golang
Trước khi bắt đầu, cùng xét tới một bài toán khá cơ bản:
Cho tập S gồm n phần tử, kiểm tra 𝑥 có là phần tử của tập S (𝑥 ∈ S) hay không.Bài toán trên tương đối đơn giản và dễ dàng cài đặt. Nhưng nếu như tập S là lớn (cho đến cực lớn) thì sao? Hoặc nói chung hơn, chi phí để duyệt được S là tốn kém, dẫn tới làm cho chi phí kiểm tra cũng là không hề nhỏ. Vậy làm sao để giảm thiểu chi phí này?
Vào năm 1970, Burton Howard Bloom giới thiệu một Cấu trúc Dữ liệu được đặt theo tên ông — Bloom Filter. Nó nhanh chóng phát huy được tính ứng dụng của mình thông qua việc giảm truy vấn tới những tài nguyên expensive-to-access (như database, disk, network, …).
Vậy cụ thể Bloom filter là gì?
Bloom filter là cấu trúc dữ liệu xác suất (probabilistic data structure). Tư tưởng của nó có phần nào đó giống với HashTable nhưng lại tối ưu về không gian hơn. Nó được sử dụng để kiểm tra phần tử có-khả-năng thuộc một tập hợp hay không. Nếu là kết quả kiểm tra trả về không (false), thì chắc chắn nó không nằm trong tập hợp. Nhưng dù kết quả là có (true), thì cũng chưa chắc phần tử đó đã nằm trong tập hợp (false positive, nên nó vẫn cần phải có một bước kiểm tra để chắc chắn). Hay nói một cách ngắn gọn, Bloom filter có thể nhanh chóng đưa ra kết luận một phần tử KHÔNG nằm trong tập hợp, qua đó giảm chi phí tìm kiếm với những truy vấn không cần thiết.
Nguyên lý hoạt động của Bloom Filter tương đối đơn giản. Mỗi khi một phần tử được thêm, nó sẽ được hash và lấy vị trí trong mảng bit, sau đó chuyển vị trí này thành 1 (hoặc true). Cùng tham khảo đoạn pseudocode sau đây:
func Add(value):
position = hash_function(value) % num_of_bit_set
bit_set[position] = 1Để 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.
func MightContain(value):
position = hash_function(value) % num_of_bit_set
if bit_set[position] == 0:
return false
return trueTuy nhiên, như bạn đã thấy, nếu chỉ đơn giản như trên thì khả năng xung đột (collisions) tương đối cao, tức là 2 item khác nhau có chung 1 index trong bit set, dẫn tới báo dương tính giả làm giảm hiệu suất hoạt động của filter.
Để giải quyết vấn đề, ta có thể chọn một kích thước của mảng bit set hợp lý hơn và dùng nhiều hàm băm để xác định index của phần tử. Cụ thể, hãy cùng tham khảo hình dưới đây:
Giả sử chúng ta có tập hợp S gồm các phần tử x, y và z. Đồng thời H là tập hợp các hàm hash, còn A có độ dài xác định là mảng bit set gồm giá trị 0 hoặc 1. Chúng ta lần lượt băm các giá trị trong tập S bằng các hàm trong tập H để lấy index đánh dấu vào tập A.
Tiếp theo, để kiểm tra phần tử a có thuộc tập S hay không, ta lại lần lượt hash nó với bằng các hàm thuộc tập H để lấy index kiểm tra với mảng bit set (tập A). Nếu khi truy xuất 1 trong những index ấy là 0 thì chắc chắn nó không thuộc S. Ngược lại thì nó rất có khả năng a là phần tử thuộc S, tuy nhiên vẫn cần kiểm tra tiếp để chắc chắn (nếu thực sự a không nằm trong S thì đây chính là trường hợp rơi vào xác suất dương tính giả — false positive).
Độ phức tạp của Bloom Filter là hằng số. Time complexity của nó là O(k) với k là số lượng hàm hash có trong tập hợp H (và vì k là hằng số nên tựu chung sẽ là O(1)). Còn space complexity là O(m) với m được chỉ định trước (có công thức tính hợp lý), chính là số lượng bit nằm trong A.
Để tính toán, lựa chọn các thông số n, m, k, p tốt hơn, cũng như visualize bạn có thể tham khảo tại đây.
Cài đặt bằng Golang
Hãy cùng định nghĩa interface và concrete của nó:
Với Interface BloomFilter, chúng ta có các phương thức gồm Add là để đánh dấu một phần tử vào trong Bit Set, còn MightContain dùng để kiểm tra liệu một giá trị có thuộc danh sách hay không. Struct bloomFilterImpl là một thể hiện của interface BloomFilter (tuy nhiên chú ý viết thường chữ cái đầu để báo với Go rằng đây là private struct, nhằm tránh khởi tạo trực tiếp do thuộc tính bitSet và size cần được tính toán tối ưu như công thức bên dưới).
Bước cuối cùng, tích hợp vào Gin Framework bằng cách tạo một middleware kiểm tra trước mỗi request:
Bạn có thể tham khảo toàn bộ source tại đây.
Performance Test
Sau đây hãy cùng làm một vài load test để kiểm tra hoạt động của Bloom Filter. Điều kiện là giả lập 25 user cùng truy cập hệ thống, lặp lại 500 lần trên 4 url (nằm trong file test_urls.txt, bao gồm truy vấn product có và không có trong dataset). Như vậy chúng ta có 12,500 request gửi đến hệ thống. Ở đây tôi chọn công cụ siege do support test cùng lúc nhiều url. Bạn hoàn toàn có thể thay thế bằng ab (apache bench) tích hợp sẵn trong *nix.
Trước hết cùng start server:
$ cd src/demo/cmd/; go run main.go
...
[GIN-debug] Listening and serving HTTP on :8080Sau đó bắt đầu thử nghiệm với BloomFilter được tắt (de-attached Bloom Filter middleware trong code trước đó):
$ siege -f test_urls.txt -r500 -c25
...
Transactions: 12500 hits
Availability: 100.00 %
Elapsed time: 45.00 secs
Data transferred: 0.40 MB
Response time: 0.09 secs
Transaction rate: 277.78 trans/sec
Throughput: 0.01 MB/sec
Concurrency: 24.50
Successful transactions: 3125
Failed transactions: 0
Longest transaction: 0.92
Shortest transaction: 0.01Và sau khi được bật lên:
$ siege -f test_urls.txt -r500 -c25
...
Transactions: 12500 hits
Availability: 100.00 %
Elapsed time: 35.41 secs
Data transferred: 0.60 MB
Response time: 0.07 secs
Transaction rate: 353.01 trans/sec
Throughput: 0.02 MB/sec
Concurrency: 24.30
Successful transactions: 3097
Failed transactions: 0
Longest transaction: 0.85
Shortest transaction: 0.00Có thể thấy rằng, khi Bloom Filter được bật thì Elapsed time đã giảm khoảng 10s so với trước đó. Tất nhiên do quy mô bài test nhỏ, lại không có những tác vụ nặng (database query, network roundtrip, …) nên kết quả chưa có sự khác biệt rõ ràng. Trong điều kiện thực tế có lẽ kết quả sẽ có khác biệt lớn hơn nhiều.
Ứng dụng của Bloom Filters rất rộng, sau đây là một vài ví dụ:
- Google BigTable, Apache HBase, Apache Cassandra và PostgreSQL sử dụng Bloom Filter để giảm chi phí tìm kiếm dữ liệu.
- Google Chrome ứng dụng để lọc ra và cảnh báo những trang web gây hại cho người dùng.
- Medium dùng để tránh gợi ý lại những bài viết mà user đã đọc.
- Chống DDoS hệ thống.
- Kiểm tra weak password hoặc username/email đã tồn tại trong hệ thống.
- Kiểm tra chính tả bằng cách kiểm tra các từ tồn tại trong từ điển.
Tuy nhiên, cũng có một số lưu ý đi kèm:
- Bloom Filter truyền thống không hỗ trợ thao tác xoá, nhưng có nhiều biến thể của nó giải quyết được vấn đề này (Counting bloom filter, Cuckoo Filter, …).
- Kích thước của mảng bit set thường cố định. Tuy nhiên khi n tăng dẫn tới cần đánh dấu chúng trong mảng bit set, do đó false positive sẽ theo đó tăng lên. Vì vậy chúng ta cũng cần tính toán lại kích thước bit set.
- Nên chọn các hàm băm là dạng phi mật mã (non-cryptographic) như
fnvvàmurmurđể cho performance tốt hơn, phân phối (distribution) đều hơn, cũng như hạn chế xung đột (collision resistance). - Bloom filter không lưu trữ phần tử như các CTDL thông thường, nó chỉ kiểm tra khả năng tồn tại của phần tử, vậy nên vẫn cần một bước truy vấn thật sự để lấy ra phần tử mong muốn (và vì thế nó được gọi là filter).
