Nếu mỗi lần bạn gõ một địa chỉ vào thanh địa chỉ, trình duyệt lại phải tải về danh sách mọi trang nguy hiểm trên toàn internet để đối chiếu, thì sẽ quá chậm và quá nặng. Còn chứa hàng triệu địa chỉ trên thiết bị cũng là một gánh nặng. Trong những trường hợp như vậy, người ta dùng một công cụ chỉ cần lượng bộ nhớ rất nhỏ mà vẫn nhanh chóng loại ra được những địa chỉ “chắc chắn không có trong danh sách”.
Công cụ này gọi là bộ lọc Bloom (Bloom Filter). Đó là một cấu trúc dữ liệu xác suất kiểm tra xem một giá trị có nằm trong tập hợp hay không bằng rất ít dung lượng, do Burton Howard Bloom đề xuất năm 1970. Đổi lại, nó mang một cam kết đặc biệt: câu trả lời “không có” luôn đúng, còn câu trả lời “có” thỉnh thoảng có thể sai.
Trong bài này, chúng ta lần lượt xem bộ lọc Bloom xuất phát từ vấn đề nào, quá trình đưa giá trị vào và kiểm tra diễn ra ra sao, khả năng sai được kiểm soát thế nào, và cuối cùng là công dụng cũng như giới hạn trong các dịch vụ thực tế.
Kỹ thuật loại ra “không có” bằng một mảng bit nhỏ
Nhường một chút độ chính xác để tiết kiệm bộ nhớ
Bloom lấy ví dụ về việc xử lý ngắt từ bằng dấu gạch nối cho 500.000 từ trong từ điển. Với 90 phần trăm số từ, chỉ cần một quy tắc đơn giản là ngắt được, nhưng 10 phần trăm còn lại phải đọc mẫu riêng từ đĩa. Muốn nhớ chính xác từ nào là ngoại lệ thì cần rất nhiều bộ nhớ.
(1) Gánh nặng của băm chính xác
Muốn lập một bảng nhớ các từ ngoại lệ mà không sai một ly nào thì cần một bộ nhớ lớn tương ứng.
(2) Ý tưởng cho phép sai sót
Nếu chấp nhận thỉnh thoảng có một lần tra đĩa không cần thiết thì một bảng nhỏ hơn nhiều là đủ.
(3) Hiệu quả
Theo bài báo của Bloom, chỉ với bảng có kích thước bằng 18 phần trăm bảng lý tưởng cũng loại bỏ được 87 phần trăm lượt truy cập đĩa không cần thiết.
Điểm mấu chốt là chỉ cho phép sai theo một hướng. Không bao giờ bỏ sót một lượt tra cần thiết, mà chỉ sai ở chỗ còn lại ít lượt tra không cần thiết, nên kết quả luôn an toàn. Vì vậy, bộ lọc Bloom không phải công cụ đưa ra đáp án, mà giống người gác cổng hơn, hỏi trước xem có thể bỏ qua một lần kiểm tra tốn kém hay không.
Mảng bit và hàm băm làm việc như thế nào
Thân của bộ lọc Bloom là một mảng bit dài lúc đầu toàn số 0, cùng k hàm băm, mỗi hàm cho ra một giá trị khác nhau.
- Thêm (Add): Đưa giá trị qua k hàm băm và đổi cả k ô tìm được thành 1.
- Kiểm tra (Query): Tính k ô theo cách tương tự, chỉ cần một ô là 0 thì trả lời “chắc chắn không có”.
- Khi tất cả đều là 1 (Possibly in Set): Có thể giá trị đó thật sự nằm trong tập, cũng có thể các giá trị khác đã tình cờ lấp đầy các ô, nên chỉ trả lời được “có thể có”.
- Thời gian tính toán (Time): Việc kiểm tra chỉ tốn k phép tính, nên không đổi dù đã có bao nhiêu giá trị trong bộ lọc.
Cấu trúc này không lưu bản thân giá trị. Vì thế giá trị dài hay ngắn đều chiếm dung lượng như nhau, thêm cùng một giá trị nhiều lần cũng không làm mảng thay đổi thêm, và cũng không thể lần ngược xem đã đưa vào những giá trị nào.
Hãy hình dung một ví dụ nhỏ: bộ lọc có 18 bit và 3 hàm băm. Thêm ba giá trị thì nhiều nhất có 9 ô thành 1. Lúc này, nếu trong ba ô mà giá trị mới trỏ tới có dù chỉ một ô là 0, đó là bằng chứng chắc chắn rằng giá trị này chưa từng được thêm. Ngoài ra, hai bộ lọc cùng kích thước và dùng cùng các hàm băm còn có thể gộp thành một bằng phép hợp theo từng bit.
Kiểm soát khả năng sai bằng cách nào
Câu trả lời “có” sai, tức dương tính giả (False Positive), tăng lên khi bạn thêm càng nhiều giá trị. Các bit dần bị lấp đầy bằng 1, nên khả năng tất cả các ô tình cờ đều là 1 càng lớn. Mảng nhỏ đến mấy thì việc thêm giá trị cũng không thất bại, nhưng nếu cứ thêm mãi thì mọi ô đều thành 1 và bộ lọc sẽ trả lời “có thể có” cho mọi câu hỏi.
(1) Kích thước mảng
Mảng càng lớn thì xác suất dương tính giả càng giảm. Cách làm cơ bản là định kích thước tỷ lệ với số giá trị sẽ thêm vào.
(2) Số lượng hàm băm
Quá ít thì khả năng phân biệt giảm, quá nhiều thì các ô nhanh đầy. Về lý thuyết, giá trị tốt nhất nằm gần thương của kích thước mảng chia cho số giá trị, nhân với logarit tự nhiên của 2.
(3) Cảm nhận về dung lượng
Để giữ dương tính giả ở mức 1 phần trăm, mỗi giá trị cần khoảng 9,6 bit, và thêm khoảng 4,8 bit nữa thì xác suất giảm thêm mười lần. Đây là những con số không phụ thuộc vào kích thước của giá trị.
(4) Không có âm tính giả
Miễn là sau khi thêm giá trị bạn không xóa bit nào khỏi mảng, bộ lọc sẽ không bao giờ trả lời “không có” cho thứ đang có.
Công dụng trong dịch vụ và giới hạn
Các cơ sở dữ liệu như Google Bigtable, Apache HBase và Apache Cassandra dùng bộ lọc Bloom để giảm số lần đọc đĩa chỉ để tìm những hàng không tồn tại. Công ty phân phối nội dung Akamai nhận thấy các đối tượng web chỉ được yêu cầu một lần chiếm gần ba phần tư số đối tượng được lưu đệm, và đã dùng công cụ này để lọc, chỉ lưu từ lần yêu cầu thứ hai. Google Chrome cũng từng dùng bộ lọc này để sàng địa chỉ độc hại trước, và chỉ kiểm tra chính xác những địa chỉ bị bắt.
- Không xóa được (No Deletion): Dạng cơ bản không thể gỡ một giá trị. Một ô được nhiều giá trị dùng chung nên xóa đi có thể làm mất cả các giá trị khác.
- Bộ lọc Bloom đếm (Counting Bloom Filter): Thay mỗi ô 1 bit bằng một số nhỏ để hỗ trợ xóa, nhưng cần dung lượng gấp ba đến bốn lần.
- Bộ lọc Cuckoo (Cuckoo Filter): Phương án thay thế hỗ trợ xóa bằng cách lưu một dấu vân tay ngắn của mỗi giá trị.
- Khi đầy (Saturation): Nếu đưa vào quá nhiều giá trị thì dương tính giả tăng và rốt cuộc phải lập lại bộ lọc.
Như trường hợp ví Bitcoin từng dùng bộ lọc này để tăng tốc đồng bộ rồi sau đó lộ ra vấn đề lộ thông tin riêng tư, bạn cũng cần có con mắt chọn đúng chỗ để dùng. Ở nơi không cần câu trả lời hoàn hảo, chỉ cần nhanh chóng loại ra “chắc chắn không phải” là đã bớt được phần lớn công việc. Buông bỏ ham muốn nhớ chính xác mọi thứ và quyết định trước mình có thể sai đến đâu, đó là bước đầu tiên của bộ lọc Bloom.
