Bộ lọc Bloom một hàm băm: Bí quyết giúp Bluesky tiết kiệm hàng triệu truy vấn mỗi giây

Bộ lọc Bloom (Bloom filter) là cấu trúc dữ liệu xác suất giúp trả lời nhanh câu hỏi "khóa X có trong tập hợp này không?" với hai kết quả: "chắc chắn không" hoặc "có thể có". Bluesky đã tối ưu kỹ thuật này bằng cách chỉ dùng một hàm băm duy nhất, mang lại hiệu quả đáng kể cho hệ thống backend của mình.

Bài viết dưới đây phân tích chi tiết cách hoạt động của bộ lọc Bloom truyền thống, phương pháp băm kép, và cuối cùng là kỹ thuật bộ lọc Bloom một hàm băm (OHBF) đang được Bluesky sử dụng trong môi trường production suốt 9 tháng qua.

Bộ lọc Bloom là gì và vì sao nó quan trọng?

Bộ lọc Bloom là một mảng bit kết hợp với k hàm băm. Bạn chọn trước kích thước mảng và số lượng hàm băm k, sao cho phù hợp với khối lượng công việc và phần cứng để đạt được tỷ lệ dương tính giả (false positive) chấp nhận được.

• Thêm khóa vào tập hợp: chạy khóa qua k hàm băm và bật các bit tại những vị trí tương ứng.
• Kiểm tra khóa: băm khóa k lần và kiểm tra từng vị trí. Nếu có bất kỳ bit nào bằng 0, khóa chắc chắn chưa từng được thêm vào. Nếu tất cả bit đều bằng 1, khóa có thể đã có trong tập hợp.

Minh họa bộ lọc Bloom truyền thống khi tất cả các bit đều bằng một

Ưu điểm lớn nhất của bộ lọc Bloom là tiêu tốn rất ít bộ nhớ so với số lượng phần tử trong tập hợp và chi phí tính toán cực thấp. Nhờ vậy, chúng xuất hiện khắp nơi trong các hệ thống dữ liệu hiệu năng cao.

Ví dụ, một cơ sở dữ liệu có thể giữ bộ lọc Bloom trong bộ nhớ và kiểm tra nó trước khi thực sự đọc đĩa. Điều này tiết kiệm đáng kể lượng I/O đĩa vốn rất chậm.

Tại backend của Bluesky, bộ lọc Bloom giúp tiết kiệm hàng triệu truy vấn mỗi giây xuống cơ sở dữ liệu Scylla khi tra cứu khối chặn, tắt tiếng, nhãn và nhiều thứ khác. Chẳng hạn, hệ thống thường trả lời được câu hỏi "người dùng X có chặn người dùng Y không" mà không cần chạm vào cơ sở dữ liệu.

Tỷ lệ dương tính của bộ lọc Bloom tại Bluesky trong nhiều ngày

Đường màu vàng trong biểu đồ trên có tỷ lệ dương tính khoảng 1%, nghĩa là 99% thời gian hệ thống bỏ qua hoàn toàn việc truy vấn cơ sở dữ liệu. Đây là yếu tố then chốt giúp Bluesky mở rộng quy mô và vận hành nền tảng với chi phí thấp.

Băm kép: giảm chi phí mà vẫn giữ chất lượng

Dù rẻ hơn nhiều so với đọc đĩa, việc tính k hàm băm độc lập cho mỗi khóa vẫn khá tốn kém với các hệ thống yêu cầu hiệu năng cực cao.

Năm 2008, Kirsch và Mitzenmacher công bố nghiên cứu chứng minh rằng chỉ cần hai hàm băm là đủ để cho kết quả tương đương. Cụ thể, nếu tính vị trí thứ i theo công thức (hash_1 + i*hash_2) % n, tỷ lệ dương tính giả gần như không đổi so với việc dùng k hàm băm độc lập.

Thư viện bits-and-blooms/bloom do Daniel Lemire duy trì là một cài đặt bộ lọc Bloom băm kép rất chất lượng, viết bằng Go. Nó chạy murmur3 128-bit hai lần để lấy bốn giá trị 64-bit, rồi kết hợp chúng để tạo ra toàn bộ k vị trí bit. Bluesky đã dùng thư viện này trong production một thời gian dài.

Tuy nhiên, thư viện này không an toàn luồng (thread-safe) ở mức nội bộ, nên mọi truy cập phải bọc trong mutex để tránh tranh chấp dữ liệu. Công cụ pprof cho thấy chính sự tranh chấp mutex là nút thắt cổ chai khi khởi động tiến trình: một lần triển khai từng mất tới 90 phút để hoàn tất!

Giải pháp là một bản fork có tên atomic-bloom, dùng các lệnh CPU nguyên tử để thực hiện logic tương tự nhưng an toàn và không cần mutex. Kết quả là thời gian triển khai giảm từ 90 phút xuống còn khoảng 15 phút, cho phép đội ngũ phát hành nhanh hơn và tự tin hơn.

Bộ lọc Bloom một hàm băm hoạt động thế nào?

Nghiên cứu của Lu và cộng sự đưa ra phương pháp dùng bộ lọc Bloom chỉ với một hàm băm duy nhất. Nguyên lý như sau:

• Thay vì một mảng bit lớn, chia thành k phân vùng có kích thước cố định.
• Mỗi phân vùng có kích thước khác nhau, và các kích thước này nguyên tố cùng nhau theo từng cặp (không cặp nào có ước chung lớn hơn 1).
• Băm khóa đúng một lần để lấy giá trị hash.
• Vị trí bit trong phân vùng p là hash % size_p.
• Từ một hash duy nhất, bạn thu được k vị trí bit để kiểm tra, dùng y hệt như các loại bộ lọc Bloom khác.

Tác giả bài viết đã xây dựng thư viện jcalabro/gloom, một cài đặt OHBF bằng Go. Thư viện này đã chạy trong backend Bluesky suốt 9 tháng và hoạt động rất ổn định, đồng thời cũng được dùng trong jetstream — dịch vụ đồng bộ hiệu năng cao của nền tảng.

Cách sử dụng rất đơn giản: khởi tạo bộ lọc với dung lượng dự kiến và tỷ lệ dương tính giả mong muốn, sau đó gọi TestString để kiểm tra và AddString để thêm khóa. Bộ lọc mặc định an toàn luồng nhờ cơ chế nguyên tử.

Minh họa một vị trí băm trong bộ lọc Bloom một hàm băm

Tối ưu hiệu năng ở tầng thấp

Ngoài việc chỉ dùng một hàm băm, thư viện còn áp dụng nhiều kỹ thuật tối ưu thú vị:

• Chia thành các khối 64 byte để khớp với kích thước cache line phổ biến của CPU.
• Căn chỉnh bộ nhớ: vì bộ cấp phát của Go không đảm bảo căn chỉnh cache, thư viện cấp phát dư một chút và dùng unsafe để đảm bảo căn chỉnh. Hai kỹ thuật này kết hợp lại đảm bảo trong trường hợp xấu nhất, một lần tra cứu bộ lọc Bloom chỉ gây một lần cache miss.
• Chọn khối bằng một lệnh MUL thay vì phép chia lấy dư vốn tốn kém — một mẹo tối ưu khác của Daniel Lemire.
• ShardedAtomicFilter: trải đều ghi lên nhiều phân mảnh để giảm khả năng tranh chấp, hữu ích khi chạy trên các cụm máy chủ bare metal nhiều lõi.

Kết luận

Bộ lọc Bloom (và roaring bitmap) là những cấu trúc dữ liệu thiết yếu trong các hệ thống hiện đại. Việc tối ưu từ băm kép sang một hàm băm duy nhất, kết hợp với các kỹ thuật căn chỉnh bộ nhớ và giảm tranh chấp, cho thấy những cải tiến ở tầng thấp có thể mang lại tác động rất lớn về hiệu năng và chi phí vận hành.

Với các kỹ sư Việt Nam đang xây dựng hệ thống quy mô lớn, đây là bài học đáng tham khảo: đôi khi nút thắt cổ chai không nằm ở thuật toán mà ở chi tiết triển khai, và một thay đổi nhỏ đúng chỗ có thể tiết kiệm hàng giờ đồng hồ mỗi lần triển khai.

"Bộ lọc Bloom (và roaring bitmap) khiến thế giới vận hành trơn tru."