Bloom Filter và Ứng dụng: Giải thích dễ hiểu cho Developer

Bloom Filter là một công cụ hữu ích và hiệu quả dành cho các developer khi xử lý các bài toán xác định sự tồn tại của phần tử trong các tập dữ liệu lớn. Các công ty công nghệ hàng đầu như Google, Facebook, Netflix và LinkedIn đã tích hợp Bloom Filter vào các hệ thống quan trọng để tối ưu hóa tài nguyên và cải thiện hiệu suất.

Vậy Bloom Filter là gì? Nó được áp dụng trong các bài toán thực tế như thế nào? Hãy cùng mình tìm hiểu trong bài viết sau đây nhé.

1. Bloom Filter là gì?

Bloom Filter là một cấu trúc dữ liệu xác suất (probabilistic data structure) được phát minh bởi Burton Howard Bloom vào năm 1970. Nó được thiết kế để kiểm tra nhanh chóng xem một phần tử có thuộc tập hợp hay không, với những đặc điểm chính:

• Tiết kiệm không gian bộ nhớ đáng kể so với lưu trữ toàn bộ dữ liệu
• Có thể trả lời câu hỏi "phần tử X có trong tập hợp không?" một cách nhanh chóng
• Không bao giờ có kết quả âm giả (false negative) - nếu Bloom Filter nói "không có", thì chắc chắn 100% phần tử đó không tồn tại
• Có thể có kết quả dương giả (false positive) - đôi khi Bloom Filter có thể nói "có" trong khi thực tế phần tử không tồn tại

Vì mình và các bạn đều là Developer nên phần giải thích cách thức hoạt động bằng các công thức toán học chúng ta sẽ skip nhé 😝.

2. Ứng dụng thực tế của Bloom Filter

2.1 1. Tối ưu hóa truy vấn database với dữ liệu lớn

Vấn đề: Truy vấn dữ liệu trong database lớn để kiểm tra sự tồn tại của một record tiêu tốn nhiều tài nguyên, đặc biệt với hệ thống có hàng triệu đến hàng tỷ record. Mỗi truy vấn có thể gây ra các hoạt động I/O không cần thiết, làm giảm hiệu suất.

Giải pháp với Bloom Filter: Sử dụng Bloom Filter làm lớp kiểm tra sơ bộ trước khi thực hiện truy vấn trực tiếp vào database.

function checkUserExists(username) {
    // Nếu Bloom Filter xác định "không có" -> chắc chắn không cần truy vấn database
    if (!userBloomFilter.contains(username)) {
        return false;
    }
    
    // Nếu kết quả là "có thể có" -> mới thực hiện truy vấn database để xác minh
    return database.checkUserExists(username);
}

Databases như Cassandra và HBase sử dụng Bloom Filter để giảm I/O operations. Cụ thể, khi bạn cần tìm kiếm một row, thay vì đọc từng SSTable (Sorted String Table) trên đĩa, database sẽ kiểm tra Bloom Filter của từng SSTable trước.

Nếu Bloom Filter cho biết row chắc chắn không có trong SSTable đó, database sẽ bỏ qua SSTable này hoàn toàn, giảm đáng kể số lần đọc đĩa. Điều này đặc biệt hiệu quả trong trường hợp tìm kiếm các key không tồn tại.

Ví dụ: Cassandra có thể có hàng chục SSTable cho mỗi table. Việc truy cập mỗi SSTable trên đĩa có thể tốn vài milliseconds. Với Bloom Filter, Cassandra có thể nhanh chóng loại bỏ những SSTable không chứa key bạn đang tìm kiếm, chỉ còn lại 1-2 SSTable cần kiểm tra, giúp giảm thời gian truy vấn từ 200ms xuống còn 10ms.

2.2 Chống trùng lặp khi crawl web

Vấn đề: Khi thực hiện crawl dữ liệu, bạn cần kiểm tra và theo dõi hàng triệu URL đã được truy cập trước đó để tránh lặp lại việc xử lý chúng. 

Giải pháp với Bloom Filter:

const seenUrlsFilter = new BloomFilter(10000000, 0.01); // ~10 triệu URLs với 1% false positive

function crawlPage(url) {
  // Nếu URL đã thấy rồi -> bỏ qua
  if (seenUrlsFilter.contains(url)) {
    return;
  }
  
  // Đánh dấu URL đã thấy
  seenUrlsFilter.add(url);
  
  // Tiếp tục xử lý và crawl
  const content = fetchPage(url);
  const links = extractLinks(content);
  links.forEach(link => crawlQueue.push(link));
}

Web crawler, chẳng hạn như của Google, phải xử lý hàng tỷ URL trong quá trình thu thập thông tin. Tuy nhiên, lưu trữ tất cả các URL đã thực hiện trong RAM là điều không khả thi. Ví dụ, nếu mỗi URL trung bình chiếm 50 bytes, thì 1 tỷ URL sẽ cần khoảng 50GB RAM.

Với Bloom Filter, bạn có thể lưu trữ thông tin của 1 tỷ URL với tỷ lệ false positive chỉ 1%, nhưng chỉ cần khoảng 1.2GB RAM.  (tính theo công thức: m = -n*ln(p)/(ln(2)²), với n=1 tỷ, p=0.01).

Một crawler trong thực tế có thể sử dụng Bloom Filter như sau:

1. Khi gặp một URL mới, kiểm tra nó trong Bloom Filter.
2. Nếu Bloom Filter xác nhận URL chưa được thấy, crawler sẽ tải và xử lý URL đó, đồng thời thêm URL này vào Bloom Filter.
3. Nếu Bloom Filter báo URL có thể đã thấy (với một xác suất nhỏ là sai do false positive), có hai tùy chọn xử lý:
   • Bỏ qua URL, chấp nhận khả năng bỏ lỡ khoảng 1% trang do lỗi false positive.
   • Kiểm tra trong kho lưu trữ phụ (chẳng hạn như database) để xác nhận chính xác URL đó đã được crawl hay chưa.

Các web crawler lớn như Google và Bing áp dụng kỹ thuật này để tối ưu hóa bộ nhớ và đảm bảo không lặp lại việc xử lý các trang đã crawl, nhờ đó cải thiện hiệu suất và giảm chi phí tài nguyên đáng kể.

2.3 Kiểm tra mật khẩu yếu/bị lộ

Vấn đề: Bạn muốn ngăn người dùng sử dụng mật khẩu nằm trong danh sách hàng triệu mật khẩu đã bị lộ.

Giải pháp với Bloom Filter:

// Tạo Bloom Filter chứa các mật khẩu phổ biến/đã bị lộ
const weakPasswordsFilter = new BloomFilter();
loadWeakPasswords.forEach(pwd => weakPasswordsFilter.add(pwd));

function checkPasswordStrength(password) {
  if (weakPasswordsFilter.contains(password)) {
    return "Mật khẩu này quá phổ biến hoặc đã bị lộ, vui lòng chọn mật khẩu khác";
  }
  
  // Tiếp tục kiểm tra các yêu cầu khác
  return checkOtherPasswordRequirements(password);
}

Dịch vụ như Have I Been Pwned (HIBP) quản lý danh sách hơn 600 triệu mật khẩu đã bị lộ. Vì lý do bảo mật và hiệu suất, việc lưu trữ danh sách này trong ứng dụng client-side là không khả thi, nhưng bạn cũng không muốn gửi mật khẩu người dùng lên server để kiểm tra trực tiếp – điều này có thể làm lộ thêm thông tin nhạy cảm.

Trong thực tế, HIBP áp dụng kỹ thuật k-anonymity, còn các ứng dụng client-side có thể sử dụng Bloom Filter để kiểm tra mật khẩu ngay trên thiết bị của người dùng mà không cần dữ liệu gửi lên server.

Cách hoạt động:

1. Tạo một Bloom Filter chứa danh sách hàng triệu mật khẩu đã bị lộ, với kích thước được nén tối ưu (khoảng 10-15MB cho hàng trăm triệu mật khẩu).
2. Tích hợp Bloom Filter vào ứng dụng web hoặc mobile.
3. Khi người dùng tạo mật khẩu mới, ứng dụng kiểm tra mật khẩu đó ngay lập tức trong Bloom Filter, đảm bảo tính nhanh chóng và bảo mật mà không cần gửi mật khẩu lên server.

Ví dụ, Firefox Monitor đã triển khai phương pháp này trong một số sản phẩm. Với tỷ lệ false positive khoảng 0.5%, trong trường hợp tệ nhất, chỉ 1/200 người dùng có thể nhận được cảnh báo mật khẩu bị lộ không chính xác. Đây là một sự đánh đổi hợp lý để bảo vệ dữ liệu người dùng, bởi tỷ lệ này rất nhỏ và không ảnh hưởng đáng kể đến trải nghiệm tổng thể.

3. Kết luận

Mặc dù có một số hạn chế, chẳng hạn như tỷ lệ false positive (sai số dương) và không thể xóa phần tử đã thêm, nhưng những lợi ích về tốc độ và khả năng tiết kiệm bộ nhớ khiến Bloom Filter trở thành một giải pháp lý tưởng cho nhiều bài toán thực tế.