Bloom Filter là gì? Cách tối ưu hiệu suất với Bloom Filter

Các bước tạo Bloom Filter và tối ưu hiệu suất

• Khi chúng ta tạo 1 user:

  1. Hash username/email của user tuỳ theo field cần unique.
  2. Modulo 64 để lấy vị trí bit (0–63).
  3. Set số bit đó trong memory. Bạn nên dùng in-memory để giảm thiểu network latency.

• Khi chúng ta check username/email:

  1. Hash và modulo 64 để lấy vị trí bits.
  2. Nếu bit là 0, user chắc chắn không tồn tại, bạn có thể tạo mà không cần check database.
  3. Nếu số bit = 1, maybe username/email đã tồn tại, lúc này bạn nên check database để logic được đi đúng hướng.

Hạn chế của Bloom Filter

Vậy, hạn chế của Bloom Filter là gì? Rõ ràng theo như chúng ta thấy, Bloom Filter đang sử dụng 1 dãy bit để kiểm tra xem, username/email đã tồn tại hay chưa. Vì vậy khi quá nhiều username/email được lưu vào dãy bit, Bloom filter sẽ luôn fallback là 1 và query database.

Giảm thiểu điểm yếu của bloom filter như thế nào?

Đơn giản nhất là bạn nên dùng 1 bit array lớn hơn.

Cách thứ 2 là dùng nhiều hash function để xác giảm thiểu việc checking sai.

Khi thêm phần tử

Tính:

pos1 = h1("haonam") % m
pos2 = h2("haonam") % m
pos3 = h3("haonam") % m

Sau đó:

• Set bit tại pos1 = 1
• Set bit tại pos2 = 1
• Set bit tại pos3 = 1

Tức là một username chiếm 3 vị trí bit khác nhau trong mảng.

Ví dụ: 1 user thay vì bật 1 công tắc thì sẽ có 3 cách bật công tắc khác nhau, khi chúng ta muốn kiểm tra 1 username/email đã tồn tại trong database hay chưa, chúng ta xác định qua cách bật công tắc, rõ ràng độ chính xác sẽ cao hơn.

Kết luận

Bloom Filter pattern giúp giảm thiểu việc truy cập database, nhưng chỉ đối với trường hợp false positive. Một số database như Cassandra cũng sử dụng pattern này như 1 phương pháp improve performance, vì vậy chọn Bloom filter trong dự án chính là 1 “right decision”.

Cám ơn bạn đã đọc blog này, trong phần tới, mình sẽ hướng dẫn code bloom filter pattern, code đã được nhúng trong 1 dự án thực tế của mình.