Top 10 Thuật Toán System Design Các Bạn Nên Biết Và Thường Được Hỏi Trong Phỏng Vấn - Top 3 Bloom Filters

Nov 24, 2024 49 min read System Design

Giả sử bạn muốn lập một tài khoảng phở bò, username là phamduytung, bạn hăng hái hăm hở gõ vào cái tên đó trong ô username và .. bùm, phở bò báo lại cho bạn rằng username đó đã được sử dụng, bạn cố gắng thử với vài trường hợp như nhét năm sinh của bạn vào, nhét thêm chữ viết tắt của trường đại học vào, nhưng phở bò vẫn trả lời lại là tên username đó đã được sử dụng, thật là bực bội phải không?

Khoan khoan trút nỗi bực bội hoặc tìm cách đặt tên ở đây, chúng ta trở lại bản chất của vấn đề là hệ thống search username hoạt động như thế nào?

Phương án a: tìm kiếm tuyến tính, duyệt tất cả các username, nếu gặp 1 username trùng với username mình nhập vào -> báo username đó đã tồn tại

Phương án b: tìm kiếm nhị phân binary search, so sánh tên người dùng với tên ở giữa danh sách, nếu khớp thì trả ra đã có , nếu không khớp thì xem tên người dùng lớn hơn hay nhỏ hơn tên ở giữa, nếu lớn hơn thì chúng ta sẽ chỉ lặp lại việc tìm kiếm như trên nhưng ở phạm vi còn 1 phần 2 từ tên ở giữa đến hết. Nếu nhỏ hơn thì phạm vi tìm kiếm cũng còn là 1 phần 2 từ đầu đến tên ở giữa, lặp đi lặp lại việc này đến khi tìm thấy ( trả ra tên đã sử dụng) hoặc hết phạm vi tìm kiếm (trả ra tên khả dụng). Cách này ổn nhưng việc tìm kiếm cũng trải qua khá nhiều bước.

Phương án c: lưu toàn bộ user dưới dạng 1 cái cây rồi duyệt node. Cách này ổn, nhưng khá tốn bộ nhớ khi tên username dài

Còn phương án nào khác không?

Có, tất nhiên là có rồi, đó chính là Bloom Filters

I. Bloom Filters là gì?

Bloom filter, được phát minh bởi Burton Howard Bloom năm 1970, là một cấu trúc dữ liệu xác suất dựa trên thuật toán hasing. Nó được sử dụng để kiểm tra xem một phần tử có phải thuộc về một tập hợp hay không. Tất nhiên, người ta cũng có thể sử dụng các cấu trúc dữ liệu khác để thực hiện việc này, nhưng Bloom filter có ưu điểm về hiệu quả về không gian và thời gian.

II. Nguyên lý Bloom Filters hoạt động

Cấu trúc dữ liệu

Bloom Filters được cấu thành từ 2 thành phần, thứ nhất là một mảng N bit , mỗi phần tử trong mảng mang giá trị 0 hoặc 1, giá trị khởi tạo ban đầu là 0. Thành phần thứ 2 là k thuật toán hash khác nhau, mỗi hàm hash sẽ được chia lấy dư cho N, và kích hoạt ô nhớ tương ứng với giá trị sau chia dư của hash.

Giả sử

chúng ta có N = 5, k =3 nghĩa là có 3 hàm hash , đặt tên là hash1, hash2, hash 3, từ khoá cần check và nếu không có thì thêm vào là chữ “duy” và chữ “tung”

Ở thời điểm bắt đầu , chúng ta có 1 mảng 5 phần tử đều mang giá trị 0

[0,0,0,0,0]

kiểm tra chữ “duy”

hash1(“duy”) %5 = 1 hash2(“duy”) %5 = 2 hash3(“duy”) %5 = 4

check các giá trị ở vị trí 1,2,4, chúng ta có toàn số 0, do dó từ khoá chưa có trong mảng, thêm vào mảng.

vậy mảng chúng ta thu được sau khi thêm chữ “duy” sẽ là [0,1,1,0,1]

kiểm tra chữ “tung”

hash1(“tung”) %5 = 1 hash2(“tung”) %5 = 3 hash3(“tung”) %5 = 4

check các giá trị ở bị trí 1,3,4, chúng ta thấy ở 1 và 4 đã là 1, nhưng ở 3 là 0, vậy là chữ “tung” chưa có, thêm vào mảng

vậy mảng chúng ta có sau khi thêm chữ “tung” sẽ là [0,1,1,1,1]

giờ giả sử thêm chữ “pham” nha

kiểm tra chữ “pham”

hash1(“tung”) %5 = 2 hash2(“tung”) %5 = 3 hash3(“tung”) %5 = 4

check các giá trị ở bị trí 2,3,4, chúng ta thấy cả 3 vị trí 2 , 3, 4 đều là 1 -> chữ “pham” đã có, thông báo với người dùng là đã có , không thêm vào

Khoan khoan, ủa gì kỳ vậy, rõ ràng chữ “pham” chưa có mà

Xác suất dương tính sai

Đây, là vấn đề, cấu trúc này tồn tại một cái gọi là Xác suất dương tính sai, nghĩa là phần tử chưa có nhưng báo có.

Để hạn chế cái này, chúng ta có công thức tính, phần chứng minh xác xuất đụng độ thì chắc các bạn đọc wiki để hiểu thêm, do nó khá rõ ràng và dễ hiểu đối với các bạn đã học toán cơ bản rồi, còn bạn nào chưa học thì bỏ qua nó đi, chứ mình đem gõ lại mấy công thức này thì các bạn chưa học cũng chưa chắc sẽ hiểu

https://en.wikipedia.org/wiki/Bloom_filter

Công thức ước tính số lượng phần tử còn lại có thể được lưu trữ

$$ [ n* =- \frac{m}{k}ln\left[ 1-\frac{X}{n} \right] ] $$

Trong đó:

n* là số lượng phần tử ước tính còn lại có thể được lưu trữ

k là số lượng hàm hash

m là chiều dài của mảng

X là số lượng phần tử đã được gán 1

Công thức ước lượng số phần tử và số hàm hash

Có nhiều cách thức, nhưng theo wiki, phần Probability of false positives thì chúng ta sẽ có, các bạn nên đọc kỹ

$$ [ m =-n * ln(p)/ln(2)^2 ] $$

$$ [ k =- \frac{m}{n}ln2 ] $$

Trong đó:

k là số hàm hash

m là chiều dài mảng

n là số lượng cần lưu trữ, ví dụ facebook mình thiết kế cho 20 tỷ username, thì set n = 20 tỷ

p là Xác suất dương tính sai, ví dụ là 0.1% thì p= 0.001

Chúng ta tính được m = 383,402,335 và k = 14

III. Ưu điểm của bộ lọc Bloom

Bloom Filter là một cấu trúc dữ liệu nhỏ gọn và hiệu quả, thường được sử dụng để kiểm tra thành viên (membership) trong tập hợp. Dưới đây là các ưu điểm nổi bật của Bloom Filter:

1. Tiết kiệm bộ nhớ

  • Kích thước nhỏ gọn: Bloom Filter sử dụng ít bộ nhớ hơn nhiều so với các cấu trúc dữ liệu khác như bảng băm (hash table) hoặc danh sách.
  • Thích hợp cho dữ liệu lớn: Đặc biệt hữu ích khi làm việc với tập dữ liệu khổng lồ, nơi mà việc lưu trữ đầy đủ các phần tử không khả thi.

2. Kiểm tra thành viên nhanh chóng

  • Độ phức tạp O(1): Bloom Filter có thể kiểm tra một phần tử có khả năng nằm trong tập hợp hay không trong thời gian hằng số.
  • Không lưu trữ phần tử: Điều này giúp Bloom Filter hoạt động nhanh hơn và giảm chi phí lưu trữ.

3. Không có false negative

  • Đảm bảo độ chính xác khi kiểm tra sự tồn tại: Nếu Bloom Filter xác nhận rằng một phần tử nằm trong tập hợp, điều đó luôn đúng (không có false negative).
  • Kiểm soát false positive: False positive (khi phần tử không thuộc tập nhưng lại được báo là thuộc) có thể được giảm bằng cách điều chỉnh kích thước mảng bit và số lượng hàm băm.

4. Dễ dàng mở rộng

  • Điều chỉnh linh hoạt: Có thể thay đổi kích thước mảng bit hoặc số hàm băm để tối ưu hóa hiệu suất hoặc giảm tỷ lệ false positive.
  • Các biến thể mạnh mẽ: Scalable Bloom Filter và Counting Bloom Filter cho phép Bloom Filter mở rộng hoặc hỗ trợ cập nhật dữ liệu dễ dàng.

5. Thiết kế đơn giản

  • Không cần xử lý xung đột: Không như bảng băm, Bloom Filter không cần các cơ chế xử lý xung đột phức tạp.
  • Không cần thay đổi kích thước: Bloom Filter không yêu cầu “resize” như các cấu trúc dữ liệu khác khi dữ liệu tăng lên.

6. Thân thiện với hệ thống phân tán

  • Hiệu quả trên mạng: Bloom Filter có thể được truyền qua mạng với dung lượng nhỏ, giúp đồng bộ dữ liệu giữa các hệ thống phân tán hiệu quả.
  • Ứng dụng trong hệ thống lưu trữ: Giảm số lần truy cập không cần thiết vào cơ sở dữ liệu phân tán.

7. Ứng dụng rộng rãi

  • Đa dạng ứng dụng: Được sử dụng trong các hệ thống cơ sở dữ liệu, mạng, công cụ tìm kiếm, bảo mật, và nhiều lĩnh vực khác.
  • Ví dụ sử dụng:
    • Cơ sở dữ liệu: Kiểm tra nhanh sự tồn tại của khóa để giảm chi phí truy cập ổ đĩa.
    • Bộ lọc web: Loại bỏ nhanh các URL trùng lặp hoặc không hợp lệ.
    • Phát hiện thư rác: Xác định địa chỉ email hoặc domain trong danh sách đen.

8. Hỗ trợ tính toán song song

  • Tính toán hàm băm độc lập: Các hàm băm có thể được tính toán song song, giúp Bloom Filter tận dụng được hệ thống đa lõi hoặc phân tán.
  • Tăng tốc bằng phần cứng: Có thể triển khai trên phần cứng (như FPGA, GPU) để đạt hiệu năng cao.

9. Ứng dụng trong bảo mật và quyền riêng tư

  • Truy vấn ẩn danh: Hỗ trợ các giao thức truy vấn thông tin riêng tư mà không làm lộ dữ liệu.
  • Phát hiện nhanh chóng: Xác định IP hoặc hành vi đáng ngờ mà không cần lưu trữ toàn bộ dữ liệu nhạy cảm.

10. Dễ bảo trì

  • Không lưu dữ liệu thô: Vì Bloom Filter không lưu trữ chính xác dữ liệu thô, chi phí quản lý và bảo trì thấp hơn.
  • Hoạt động tĩnh: Một Bloom Filter được tạo trước có thể được sử dụng lặp lại mà không cần cập nhật.

Khi nào nên sử dụng Bloom Filter?

  • Bộ nhớ hạn chế: Khi không gian lưu trữ là vấn đề quan trọng, chẳng hạn trong các hệ thống nhúng hoặc thiết bị IoT.
  • Cần kiểm tra nhanh: Khi tốc độ kiểm tra thành viên quan trọng hơn độ chính xác tuyệt đối.
  • Chấp nhận false positive: Các ứng dụng có thể chịu được một số trường hợp false positive, ví dụ như bộ lọc spam.

Hạn chế của bộ lọc Bloom Filter

Mặc dù Bloom Filter có nhiều ưu điểm vượt trội, nhưng cũng tồn tại một số hạn chế cần xem xét trước khi sử dụng. Dưới đây là các nhược điểm chính:

1. False Positive (Kết quả dương tính giả)

  • Không chính xác tuyệt đối: Bloom Filter có thể báo rằng một phần tử nằm trong tập hợp mặc dù thực tế không phải vậy. Điều này xảy ra do bản chất xác suất của cấu trúc dữ liệu.
  • Không phù hợp cho các ứng dụng yêu cầu chính xác tuyệt đối: Ví dụ, không thể sử dụng Bloom Filter để lưu trữ dữ liệu nhạy cảm hoặc khi cần đảm bảo 100% độ tin cậy.

2. Không hỗ trợ xóa phần tử

  • Không thể xóa trong phiên bản cơ bản: Một phần tử đã được thêm vào Bloom Filter không thể bị xóa, vì việc thay đổi bất kỳ bit nào có thể ảnh hưởng đến các phần tử khác đã được băm vào cùng bit.
  • Giải pháp: Sử dụng Counting Bloom Filter, nhưng điều này đòi hỏi nhiều bộ nhớ hơn.

3. Không lưu trữ dữ liệu gốc

  • Không thể trích xuất lại dữ liệu: Bloom Filter chỉ lưu dấu vết của phần tử thông qua mảng bit, vì vậy không thể truy xuất lại các phần tử thực tế từ Bloom Filter.
  • Ứng dụng hạn chế: Không thể sử dụng Bloom Filter trong các hệ thống cần lưu trữ hoặc quản lý dữ liệu thực tế.

4. Khó điều chỉnh tỷ lệ false positive

  • Cần thiết kế trước: Tỷ lệ false positive phụ thuộc vào kích thước mảng bit, số lượng hàm băm, và số lượng phần tử. Nếu các tham số này không được thiết kế cẩn thận từ đầu, Bloom Filter có thể hoạt động không hiệu quả.
  • Không linh hoạt: Việc thay đổi các tham số (như kích thước hoặc số hàm băm) thường đòi hỏi phải tạo lại toàn bộ Bloom Filter.

5. Yêu cầu chọn hàm băm phù hợp

  • Hiệu suất phụ thuộc vào hàm băm: Nếu các hàm băm không được chọn tốt, chúng có thể tạo ra các xung đột lớn, dẫn đến tỷ lệ false positive cao.
  • Hao tổn tài nguyên: Tính toán các hàm băm phức tạp có thể tiêu tốn tài nguyên CPU, đặc biệt khi sử dụng nhiều hàm băm.

6. Không hiệu quả với tập dữ liệu nhỏ

  • Quá phức tạp so với bài toán nhỏ: Khi tập dữ liệu nhỏ, việc sử dụng Bloom Filter có thể phức tạp và tốn tài nguyên hơn so với các giải pháp khác như danh sách liên kết hoặc bảng băm.

7. Không thể mở rộng một cách đơn giản

  • Khó thêm phần tử mới: Khi tập dữ liệu lớn hơn dự kiến, Bloom Filter ban đầu có thể không đủ để lưu trữ thêm phần tử mà không tăng tỷ lệ false positive.
  • Giải pháp: Sử dụng Scalable Bloom Filter, nhưng điều này làm tăng độ phức tạp và chi phí.

8. Không hỗ trợ kiểm tra phủ định (No False Negatives)

  • Chỉ kiểm tra thành viên: Bloom Filter chỉ xác nhận rằng phần tử “có thể có” hoặc “chắc chắn không có” trong tập hợp, và không thể sử dụng để so sánh hoặc tìm kiếm dữ liệu thực tế.
  • Ứng dụng giới hạn: Không phù hợp cho các bài toán yêu cầu thông tin chính xác về phần tử (như vị trí, giá trị cụ thể).

9. Khó triển khai và bảo trì trong hệ thống lớn

  • Cần đồng bộ hóa: Trong hệ thống phân tán, Bloom Filter cần được cập nhật hoặc đồng bộ liên tục, điều này có thể gây phức tạp khi dữ liệu thay đổi nhanh.
  • Chi phí bộ nhớ: Mặc dù Bloom Filter tiết kiệm bộ nhớ, nhưng khi yêu cầu tỷ lệ false positive thấp, kích thước mảng bit có thể trở nên lớn, làm giảm lợi ích của nó.

10. Không phù hợp với dữ liệu động

  • Không tối ưu cho dữ liệu thay đổi thường xuyên: Khi tập dữ liệu thay đổi liên tục (thêm hoặc xóa phần tử), Bloom Filter cơ bản không phù hợp vì không hỗ trợ xóa và tái sử dụng không gian.

Khi nào không nên sử dụng Bloom Filter?

  • Khi yêu cầu kết quả chính xác tuyệt đối (không chấp nhận false positive).
  • Khi dữ liệu thay đổi liên tục và cần cập nhật (thêm hoặc xóa phần tử).
  • Khi tập dữ liệu nhỏ, Bloom Filter có thể phức tạp và tốn tài nguyên hơn các giải pháp đơn giản khác.

Một số biến thể của Bloom Filter

Double Hashing Bloom Filter:

Double Hashing Bloom Filter là một biến thể của Bloom Filter truyền thống sử dụng double hashing để tính toán nhiều giá trị băm từ một cặp hàm băm cơ sở thay vì sử dụng một tập hợp các hàm băm độc lập. Điều này giúp giảm độ phức tạp và tối ưu hóa hiệu suất khi triển khai.

Cách hoạt động của Double Hashing Bloom Filter

  1. Ý tưởng chính của Double Hashing:

    • Sử dụng hai hàm băm cơ bản, ( h_1(x) ) và ( h_2(x) ), để tạo ra ( k ) hàm băm cho Bloom Filter.
    • Các giá trị băm được tính theo công thức: [ g_i(x) = (h_1(x) + i \cdot h_2(x)) \mod m ]
      • ( g_i(x) ) là giá trị băm thứ ( i ) cho phần tử ( x ).
      • ( m ) là kích thước của mảng bit.
      • ( i ) là chỉ số (0 đến ( k-1 )).

  2. Thêm phần tử (Insert):

    • Tính ( k ) giá trị băm từ hai hàm băm ( h_1(x) ) và ( h_2(x) ).
    • Đặt các bit tại các vị trí tương ứng trong mảng thành 1.

  3. Kiểm tra phần tử (Check):

    • Tính ( k ) giá trị băm tương tự.
    • Kiểm tra xem tất cả các bit tương ứng đã được đặt thành 1 chưa.

Ưu điểm của Double Hashing Bloom Filter

  1. Giảm số hàm băm cần thiết:

    • Chỉ cần hai hàm băm thay vì ( k ), giúp đơn giản hóa triển khai.

  2. Tăng hiệu quả tính toán:

    • Việc tính toán các giá trị băm sử dụng ( h_1(x) ) và ( h_2(x) ) là nhanh chóng và dễ dàng.

  3. Tối ưu hóa bộ nhớ:

    • Không cần lưu trữ hoặc triển khai nhiều hàm băm riêng lẻ.

Hạn chế của Double Hashing Bloom Filter

  1. Độ chính xác phụ thuộc vào hàm băm cơ sở:

    • Nếu ( h_1(x) ) và ( h_2(x) ) không tốt, phân phối giá trị băm có thể không đều.

  2. False positive vẫn tồn tại:

    • Giống Bloom Filter truyền thống, nó không thể tránh hoàn toàn false positive.

Ứng dụng của Double Hashing Bloom Filter

  1. Cơ sở dữ liệu:

    • Giảm chi phí kiểm tra sự tồn tại của các khóa trong hệ thống lưu trữ.

  2. Cache và bộ lọc web:

    • Xác định nhanh chóng xem một URL có nằm trong danh sách chặn hay không.

  3. Hệ thống mạng:

    • Theo dõi và lọc gói tin hoặc địa chỉ IP.

Triển khai Double Hashing Bloom Filter bằng Python

 1import hashlib
 2
 3class DoubleHashingBloomFilter:
 4    def __init__(self, size, num_hashes):
 5        self.size = size
 6        self.num_hashes = num_hashes
 7        self.bit_array = [0] * size
 8
 9    def _hashes(self, item):
10        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16) % self.size
11        h2 = int(hashlib.sha256(item.encode()).hexdigest(), 16) % self.size
12        hashes = [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
13        return hashes
14
15    def add(self, item):
16        indices = self._hashes(item)
17        for idx in indices:
18            self.bit_array[idx] = 1
19
20    def contains(self, item):
21        indices = self._hashes(item)
22        return all(self.bit_array[idx] for idx in indices)
23
24
25# Example Usage
26dbf = DoubleHashingBloomFilter(size=100, num_hashes=5)
27
28# Add elements
29dbf.add("hello")
30dbf.add("world")
31
32# Check elements
33print(dbf.contains("hello"))  # True
34print(dbf.contains("world"))  # True
35print(dbf.contains("python"))  # False

Tóm tắt

  • Double Hashing Bloom Filter giảm số lượng hàm băm cần thiết bằng cách sử dụng hai hàm băm cơ sở để tạo ( k ) giá trị băm.
  • Phù hợp với các ứng dụng yêu cầu hiệu suất cao, dễ triển khai và bảo toàn tính chính xác của Bloom Filter.
  • Mã giả ở trên minh họa cách triển khai bằng cả Python và Golang.

Nếu cần giải thích thêm hoặc có yêu cầu cụ thể, hãy cho mình biết nhé! 😊

Partitioning Bloom Filter:

Partitioning Bloom Filter (PBF) là một biến thể của Bloom Filter, trong đó mảng bit được chia thành các phân đoạn riêng biệt (partitions). Mỗi hàm băm chỉ ảnh hưởng đến một phân đoạn cụ thể thay vì toàn bộ mảng. Phương pháp này cải thiện khả năng phân tán và giảm khả năng các hàm băm khác nhau ghi đè lẫn nhau (collision) trong mảng bit.

Cách hoạt động của Partitioning Bloom Filter

  1. Chia mảng bit thành nhiều phân đoạn (partitions):

    • Mảng bit tổng thể được chia thành ( k ) phân đoạn, trong đó ( k ) là số hàm băm.
    • Mỗi hàm băm chỉ hoạt động trên một phân đoạn riêng biệt.

  2. Thêm phần tử (Insert):

    • Khi một phần tử được thêm vào, các hàm băm ánh xạ nó đến các vị trí trong từng phân đoạn.
    • Chỉ các bit trong phân đoạn tương ứng được thiết lập.

  3. Kiểm tra phần tử (Check):

    • Để kiểm tra sự tồn tại, áp dụng các hàm băm để kiểm tra các vị trí trong các phân đoạn tương ứng.

  4. Giảm xung đột giữa các hàm băm:

    • Vì mỗi hàm băm chỉ làm việc trong một phân đoạn, khả năng ghi đè bit của nhau (collision) giảm đáng kể so với Bloom Filter thông thường.

Ưu điểm của Partitioning Bloom Filter

  1. Phân phối đồng đều hơn:

    • Việc phân chia mảng giúp giảm xung đột giữa các hàm băm và cải thiện độ chính xác.

  2. Kiểm soát false positive:

    • Xác suất false positive có thể giảm so với Bloom Filter thông thường nếu các phân đoạn được thiết kế tối ưu.

  3. Dễ dàng mở rộng:

    • Có thể tăng số phân đoạn hoặc kích thước từng phân đoạn để phù hợp với yêu cầu cụ thể.

Hạn chế của Partitioning Bloom Filter

  1. Tăng phức tạp quản lý:

    • Cần đảm bảo rằng mỗi hàm băm chỉ hoạt động trong phân đoạn tương ứng, tăng độ phức tạp khi triển khai.

  2. Bộ nhớ không linh hoạt:

    • Mỗi phân đoạn phải có kích thước giống nhau, dẫn đến việc sử dụng bộ nhớ không linh hoạt nếu dữ liệu không đồng đều.

Ứng dụng của Partitioning Bloom Filter

  1. Hệ thống lưu trữ và cache:

    • Theo dõi sự tồn tại của các phần tử trong các vùng dữ liệu riêng biệt.

  2. Quản lý tải trong mạng:

    • Chia nhỏ dữ liệu theo các nhóm (partitions) để giảm xung đột khi lưu trữ.

  3. Phân vùng cơ sở dữ liệu:

    • Giúp phân tán truy vấn và dữ liệu trong các cụm (cluster) cơ sở dữ liệu.

Triển khai Partitioning Bloom Filter bằng Python

 1import hashlib
 2
 3class PartitioningBloomFilter:
 4    def __init__(self, total_size, num_hashes):
 5        self.num_hashes = num_hashes
 6        self.partition_size = total_size // num_hashes
 7        self.bit_array = [0] * total_size
 8
 9    def _hashes(self, item):
10        hashes = []
11        for i in range(self.num_hashes):
12            hash_value = int(hashlib.md5((str(item) + str(i)).encode()).hexdigest(), 16)
13            # Map hash to the partition
14            partition_start = i * self.partition_size
15            index = partition_start + (hash_value % self.partition_size)
16            hashes.append(index)
17        return hashes
18
19    def add(self, item):
20        indices = self._hashes(item)
21        for idx in indices:
22            self.bit_array[idx] = 1
23
24    def contains(self, item):
25        indices = self._hashes(item)
26        return all(self.bit_array[idx] for idx in indices)
27
28
29# Example Usage
30pbf = PartitioningBloomFilter(total_size=100, num_hashes=5)
31
32# Add elements
33pbf.add("hello")
34pbf.add("world")
35
36# Check elements
37print(pbf.contains("hello"))  # True
38print(pbf.contains("world"))  # True
39print(pbf.contains("python"))  # False

Tóm tắt

  • Partitioning Bloom Filter cải thiện Bloom Filter bằng cách chia mảng bit thành các phân đoạn độc lập.
  • Nó giảm xung đột giữa các hàm băm và có thể cải thiện độ chính xác.
  • Thích hợp cho các ứng dụng yêu cầu truy vấn nhanh và đồng thời trong các vùng dữ liệu riêng biệt.

Counting Bloom Filter:

Counting Bloom Filter (CBF) là một biến thể của Bloom Filter hỗ trợ thêm khả năng xóa (delete) phần tử khỏi cấu trúc dữ liệu. Trong khi Bloom Filter truyền thống chỉ có thể thêm và kiểm tra sự tồn tại của phần tử, Counting Bloom Filter cho phép cả thêm, xóa, và kiểm tra với độ chính xác tương đối.

Cách hoạt động của Counting Bloom Filter

  1. Thay vì mảng bit, sử dụng mảng đếm (counting array):

    • Mỗi vị trí trong mảng không còn là một bit (0 hoặc 1) mà là một số nguyên (counter).
    • Bộ đếm ở mỗi vị trí cho biết số lần một phần tử hoặc nhiều phần tử khác nhau ánh xạ đến vị trí đó.

  2. Thêm phần tử (Insert):

    • Khi thêm một phần tử, tăng giá trị của các bộ đếm tại các chỉ mục được tính bởi các hàm băm.

  3. Xóa phần tử (Delete):

    • Khi xóa một phần tử, giảm giá trị của các bộ đếm tại các chỉ mục được tính bởi các hàm băm.
    • Nếu bất kỳ bộ đếm nào giảm về 0, vị trí đó được coi là trống.

  4. Kiểm tra phần tử (Check):

    • Phần tử được coi là có thể tồn tại nếu tất cả các chỉ mục băm tương ứng có giá trị lớn hơn 0.

Ưu điểm của Counting Bloom Filter

  1. Hỗ trợ xóa phần tử:

    • Khắc phục hạn chế lớn của Bloom Filter truyền thống là không hỗ trợ xóa.

  2. Giữ được tính gọn nhẹ:

    • Chỉ cần một lượng nhỏ bộ nhớ bổ sung (các bộ đếm thay vì bit).

  3. Hiệu quả với các tập dữ liệu động:

    • Rất phù hợp trong các ứng dụng mà các phần tử thường xuyên được thêm và xóa.

Hạn chế của Counting Bloom Filter

  1. False positive:

    • Giống như Bloom Filter, CBF vẫn có nguy cơ false positive (trả về “có thể tồn tại” cho phần tử không tồn tại).

  2. Không hỗ trợ kiểm tra “chắc chắn xóa”:

    • Khi một phần tử bị xóa, các phần tử khác có thể ánh xạ đến cùng chỉ mục vẫn giữ các bộ đếm.

  3. Tăng yêu cầu bộ nhớ:

    • Mỗi vị trí trong mảng cần lưu trữ một số nguyên thay vì một bit, dẫn đến tăng đáng kể dung lượng bộ nhớ.

Ứng dụng của Counting Bloom Filter

  1. Quản lý cache:

    • Theo dõi các phần tử trong cache, cho phép xóa khi hết hạn hoặc khi không còn cần thiết.

  2. Hệ thống mạng:

    • Theo dõi các gói tin hoặc lưu lượng mạng trong khoảng thời gian nhất định.

  3. Cơ sở dữ liệu:

    • Hỗ trợ trong các hệ thống lưu trữ, nơi các phần tử cần được thêm và xóa thường xuyên.

Triển khai bằng Python

 1import hashlib
 2
 3class CountingBloomFilter:
 4    def __init__(self, size, num_hashes):
 5        self.size = size
 6        self.num_hashes = num_hashes
 7        self.count_array = [0] * size
 8
 9    def _hashes(self, item):
10        hashes = []
11        for i in range(self.num_hashes):
12            hash_value = int(hashlib.md5((str(item) + str(i)).encode()).hexdigest(), 16)
13            hashes.append(hash_value % self.size)
14        return hashes
15
16    def add(self, item):
17        indices = self._hashes(item)
18        for idx in indices:
19            self.count_array[idx] += 1
20
21    def delete(self, item):
22        indices = self._hashes(item)
23        for idx in indices:
24            if self.count_array[idx] > 0:
25                self.count_array[idx] -= 1
26
27    def contains(self, item):
28        indices = self._hashes(item)
29        return all(self.count_array[idx] > 0 for idx in indices)
30
31
32# Example Usage
33cbf = CountingBloomFilter(size=100, num_hashes=3)
34
35# Add elements
36cbf.add("hello")
37cbf.add("world")
38
39# Check elements
40print(cbf.contains("hello"))  # True
41print(cbf.contains("world"))  # True
42print(cbf.contains("python"))  # False
43
44# Delete an element
45cbf.delete("hello")
46print(cbf.contains("hello"))  # False

Tóm tắt

  • Counting Bloom Filter cho phép thêm, xóa và kiểm tra phần tử, mở rộng tính năng của Bloom Filter truyền thống.
  • Nó phù hợp với các ứng dụng yêu cầu thao tác động với tập dữ liệu, nhưng vẫn giữ các ưu điểm về hiệu suất và bộ nhớ của Bloom Filter.

Nếu cần hỗ trợ thêm, hãy cho mình biết nhé! 😊

Scalable Bloom Filter

Scalable Bloom Filter (SBF) là một biến thể của Bloom Filter được thiết kế để khắc phục hạn chế cố hữu của Bloom Filter truyền thống: kích thước cố định. SBF có thể mở rộng động khi số lượng phần tử tăng mà không làm mất tính hiệu quả hoặc chính xác của Bloom Filter.

Vấn đề với Bloom Filter truyền thống

  • Giới hạn kích thước: Bloom Filter truyền thống yêu cầu kích thước mảng bit cố định khi khởi tạo, dựa trên số phần tử ước tính và tỷ lệ false positive mong muốn.
  • Nếu số phần tử vượt quá dự đoán ban đầu, tỷ lệ false positive tăng đáng kể.
  • Không thể thay đổi kích thước mà vẫn giữ nguyên các phần tử đã được thêm.

Scalable Bloom Filter giải quyết vấn đề như thế nào?

SBF khắc phục vấn đề này bằng cách:

  1. Tăng kích thước động:
    • Khi số phần tử vượt quá một ngưỡng (threshold), SBF thêm một Bloom Filter mới với kích thước lớn hơn.
  2. Giảm false positive:
    • Mỗi Bloom Filter mới được tạo ra sử dụng một tỷ lệ false positive thấp hơn so với các Bloom Filter trước đó. Điều này giúp giảm nguy cơ tổng thể của false positive.

Cấu trúc và cách hoạt động của Scalable Bloom Filter

  1. Cấu trúc:

    • SBF bao gồm một chuỗi các Bloom Filter được tạo ra khi cần mở rộng.
    • Mỗi Bloom Filter có kích thước và tỷ lệ false positive khác nhau, tăng dần theo thời gian.

  2. Chèn phần tử (Insert):

    • Phần tử mới được thêm vào Bloom Filter hiện tại (bloom filter cuối cùng trong chuỗi).
    • Nếu Bloom Filter hiện tại đạt ngưỡng tối đa, một Bloom Filter mới được tạo.

  3. Kiểm tra phần tử (Check):

    • Lần lượt kiểm tra phần tử trong từng Bloom Filter, từ đầu đến cuối chuỗi.
    • Nếu phần tử được tìm thấy trong bất kỳ Bloom Filter nào, kết quả trả về là “có thể tồn tại”.

  4. Ngưỡng mở rộng (Threshold):

    • SBF sử dụng một ngưỡng kiểm soát (thường dựa trên tải trọng, như số lượng phần tử đã thêm) để quyết định khi nào cần tạo một Bloom Filter mới.

Ưu điểm của Scalable Bloom Filter

  1. Khả năng mở rộng (Scalability):

    • SBF không giới hạn số lượng phần tử có thể thêm vào.
    • Tăng kích thước động mà không cần định cấu hình trước.

  2. Giảm false positive hiệu quả:

    • Mỗi Bloom Filter mới có tỷ lệ false positive thấp hơn, làm giảm tỷ lệ tổng thể.

  3. Tiết kiệm bộ nhớ:

    • SBF sử dụng kích thước bộ nhớ nhỏ hơn so với việc tạo một Bloom Filter rất lớn ngay từ đầu.

  4. Phù hợp với dữ liệu thay đổi:

    • SBF rất hữu ích trong các ứng dụng nơi số lượng phần tử khó dự đoán.

Hạn chế của Scalable Bloom Filter

  1. Tăng độ phức tạp:

    • Việc duy trì nhiều Bloom Filter khiến kiểm tra phần tử tốn thời gian hơn, đặc biệt khi chuỗi Bloom Filter dài.

  2. Overhead bộ nhớ:

    • Dù SBF tiết kiệm bộ nhớ hơn khi so sánh với Bloom Filter truyền thống không được tối ưu hóa, nó vẫn có overhead vì phải quản lý nhiều Bloom Filter.

  3. Không hỗ trợ xóa:

    • Như Bloom Filter truyền thống, SBF không hỗ trợ xóa phần tử.

Ứng dụng của Scalable Bloom Filter

  1. Quản lý cache:

    • Dùng để theo dõi các phần tử trong cache với số lượng phần tử thay đổi động.

  2. Hệ thống lưu trữ và cơ sở dữ liệu:

    • Được sử dụng trong các hệ thống lưu trữ phân tán như Bigtable, HBase, hoặc Cassandra.

  3. Hệ thống phân tán:

    • SBF giúp theo dõi trạng thái của các phần tử (như dữ liệu, gói tin) trong hệ thống mà kích thước tập hợp thay đổi liên tục.

  4. Dữ liệu lớn (Big Data):

    • SBF phù hợp với các ứng dụng xử lý dữ liệu lớn, nơi số lượng phần tử không thể dự đoán chính xác.

Triển khai Scalable Bloom Filter

Một cách phổ biến để triển khai SBF:

  • Bắt đầu với một Bloom Filter ban đầu có kích thước cố định.
  • Đặt ngưỡng tải trọng (load factor), ví dụ: khi số phần tử đạt 80% dung lượng tối đa.
  • Mỗi khi thêm một Bloom Filter mới, tăng kích thước mảng bit và giảm tỷ lệ false positive bằng cách thay đổi số lượng hàm băm.

Mã giả Scalable Bloom Filter

 1
 2import math
 3import hashlib
 4
 5class BloomFilter:
 6    def __init__(self, size, num_hashes):
 7        self.size = size
 8        self.num_hashes = num_hashes
 9        self.bit_array = [0] * size
10        self.count = 0
11
12    def _hash(self, item, seed):
13        hash_value = int(hashlib.md5((str(item) + str(seed)).encode()).hexdigest(), 16)
14        return hash_value % self.size
15
16    def add(self, item):
17        for i in range(self.num_hashes):
18            index = self._hash(item, i)
19            self.bit_array[index] = 1
20        self.count += 1
21
22    def contains(self, item):
23        for i in range(self.num_hashes):
24            index = self._hash(item, i)
25            if self.bit_array[index] == 0:
26                return False
27        return True
28
29
30class ScalableBloomFilter:
31    def __init__(self, initial_size=100, fp_rate=0.05, growth_factor=2):
32        self.filters = []
33        self.fp_rate = fp_rate
34        self.growth_factor = growth_factor
35        self.current_size = initial_size
36        self._add_new_filter()
37
38    def _optimal_num_hashes(self, size, items):
39        return max(1, math.ceil((size / items) * math.log(2)))
40
41    def _add_new_filter(self):
42        num_hashes = self._optimal_num_hashes(self.current_size, -math.log(self.fp_rate))
43        self.filters.append(BloomFilter(self.current_size, num_hashes))
44        self.current_size *= self.growth_factor
45
46    def add(self, item):
47        if self.filters[-1].count >= self.filters[-1].size:
48            self._add_new_filter()
49        self.filters[-1].add(item)
50
51    def contains(self, item):
52        return any(filter.contains(item) for filter in self.filters)
53
54
55# Example Usage:
56sbf = ScalableBloomFilter(initial_size=10, fp_rate=0.1)
57sbf.add("hello")
58print(sbf.contains("hello"))  # True
59print(sbf.contains("world"))  # False

Striped Bloom Filter

Striped Bloom Filter là một biến thể của Bloom Filter được thiết kế để hỗ trợ truy cập đồng thời (concurrent access) hiệu quả trong môi trường đa luồng (multi-threaded). Mục tiêu chính của Striped Bloom Filter là giảm thiểu việc khóa toàn bộ cấu trúc dữ liệu khi các luồng thực hiện thêm hoặc kiểm tra phần tử, qua đó cải thiện hiệu năng.

Đặc điểm của Striped Bloom Filter

  1. Phân chia thành các phân đoạn độc lập (Stripes):

    • Mảng bit của Bloom Filter được chia thành nhiều phân đoạn (segments) độc lập.
    • Mỗi phân đoạn được bảo vệ bởi một khóa riêng biệt (lock).
    • Các thao tác trên từng phân đoạn có thể thực hiện đồng thời mà không ảnh hưởng lẫn nhau.

  2. Tăng hiệu suất truy cập đồng thời:

    • Bằng cách phân chia mảng và sử dụng nhiều khóa, các luồng chỉ cần khóa một phân đoạn thay vì toàn bộ mảng.
    • Điều này giảm thiểu độ trễ trong các hệ thống đa luồng.

  3. Hoạt động giống Bloom Filter truyền thống:

    • Striped Bloom Filter vẫn đảm bảo các thuộc tính cơ bản của Bloom Filter như tỷ lệ false positive và sử dụng các hàm băm để xác định các chỉ mục.

Cách hoạt động của Striped Bloom Filter

1. Chèn phần tử (Insert):

  • Tính các chỉ mục băm (hash indices) của phần tử.
  • Xác định các phân đoạn tương ứng dựa trên chỉ mục.
  • Khóa các phân đoạn liên quan để thêm bit.

2. Kiểm tra phần tử (Check):

  • Tính các chỉ mục băm của phần tử.
  • Truy cập các phân đoạn tương ứng mà không cần khóa (nếu chỉ kiểm tra).
  • Nếu tất cả các bit tại các chỉ mục được đặt là 1, phần tử có thể tồn tại.

3. Phân đoạn (Segment):

  • Mảng bit được chia thành ( S ) phân đoạn.
  • Một hàm băm bổ sung được sử dụng để ánh xạ một phần tử đến một hoặc nhiều phân đoạn cụ thể.

4. Tăng hiệu suất đồng thời:

  • Các luồng chỉ cần khóa phân đoạn cần thao tác, thay vì toàn bộ cấu trúc dữ liệu.

Ưu điểm của Striped Bloom Filter

  1. Hỗ trợ đồng thời:
    • Nhiều luồng có thể thêm hoặc kiểm tra phần tử đồng thời mà không gây xung đột.
  2. Giảm độ trễ:
    • Phân đoạn độc lập giúp giảm thời gian chờ của các luồng khi khóa.
  3. Hiệu quả bộ nhớ:
    • Dù chia thành nhiều phân đoạn, tổng bộ nhớ sử dụng vẫn tương tự Bloom Filter truyền thống.

Hạn chế của Striped Bloom Filter

  1. Độ phức tạp quản lý khóa:
    • Cần quản lý nhiều khóa hơn, làm tăng độ phức tạp trong triển khai.
  2. False positive vẫn tồn tại:
    • Như Bloom Filter truyền thống, Striped Bloom Filter vẫn không loại bỏ được false positive.
  3. Không phù hợp với ứng dụng đơn luồng:
    • Trong môi trường đơn luồng, cơ chế phân đoạn và khóa trở nên dư thừa.

Triển khai bằng Python

 1import threading
 2import hashlib
 3
 4class StripedBloomFilter:
 5    def __init__(self, num_bits, num_hashes, num_stripes):
 6        self.num_bits = num_bits
 7        self.num_hashes = num_hashes
 8        self.num_stripes = num_stripes
 9        self.segment_size = num_bits // num_stripes
10        self.bit_array = [0] * num_bits
11        self.locks = [threading.Lock() for _ in range(num_stripes)]
12
13    def _hashes(self, item):
14        hashes = []
15        for i in range(self.num_hashes):
16            hash_value = int(hashlib.md5((str(item) + str(i)).encode()).hexdigest(), 16)
17            hashes.append(hash_value % self.num_bits)
18        return hashes
19
20    def add(self, item):
21        indices = self._hashes(item)
22        locked_segments = set()
23
24        # Lock relevant segments
25        for idx in indices:
26            segment = idx // self.segment_size
27            if segment not in locked_segments:
28                self.locks[segment].acquire()
29                locked_segments.add(segment)
30
31        try:
32            for idx in indices:
33                self.bit_array[idx] = 1
34        finally:
35            # Unlock segments
36            for segment in locked_segments:
37                self.locks[segment].release()
38
39    def contains(self, item):
40        indices = self._hashes(item)
41        for idx in indices:
42            if self.bit_array[idx] == 0:
43                return False
44        return True
45
46
47# Example Usage
48sbf = StripedBloomFilter(num_bits=1024, num_hashes=3, num_stripes=4)
49
50# Adding elements
51sbf.add("hello")
52sbf.add("world")
53
54# Checking elements
55print(sbf.contains("hello"))  # True
56print(sbf.contains("world"))  # True
57print(sbf.contains("python"))  # False

Quotient Filter (Bộ lọc thương số)

Quotient Filter (QF) là một cấu trúc dữ liệu xác suất tương tự Bloom Filter, được thiết kế để kiểm tra thành viên (membership) trong tập hợp với hiệu quả về mặt bộ nhớ. QF hoạt động dựa trên kỹ thuật băm (hashing) và chia thương số, cung cấp một giải pháp nhỏ gọn cho các bài toán kiểm tra thành viên.

Nguyên lý hoạt động

  1. Băm và chia thương số:

    • Tương tự Bloom Filter, QF sử dụng hàm băm để tạo ra một giá trị băm cho phần tử.
    • Giá trị băm được chia thành hai phần:
      • Thương số (Quotient): Xác định chỉ số của bucket (ô nhớ) trong một mảng cố định.
      • Phần dư (Remainder): Lưu lại như một chữ ký duy nhất trong mảng để kiểm tra.

  2. Buckets và mảng:

    • Thương số được dùng để xác định vị trí lưu phần dư trong mảng.
    • Trường hợp xung đột (collisions) được xử lý bằng cách kiểm tra tuần tự các ô liền kề (linear probing).

  3. Lưu trữ nhỏ gọn:

    • Chỉ phần dư được lưu trong mảng, giúp tiết kiệm bộ nhớ đáng kể so với bảng băm (hash table) truyền thống.
    • Metadata (dữ liệu phụ) được sử dụng để theo dõi trạng thái của các bucket (đầy hay rỗng, phần tử bị dời chỗ).

  4. Hỗ trợ thêm/xóa/kiểm tra:

    • QF hỗ trợ ba thao tác cơ bản: thêm phần tử, xóa phần tử, và kiểm tra thành viên, với hiệu suất cao và tiêu tốn ít bộ nhớ.

Ưu điểm của Quotient Filter

  1. Tiết kiệm bộ nhớ:

    • QF nhỏ gọn hơn bảng băm và tương đương Bloom Filter về mức độ sử dụng bộ nhớ.

  2. Hỗ trợ xóa phần tử:

    • Không như Bloom Filter cơ bản, QF hỗ trợ việc xóa phần tử mà không cần biến thể bổ sung như Counting Bloom Filter.

  3. Chỉ cần một hàm băm:

    • QF chỉ cần một hàm băm duy nhất, giúp giảm chi phí tính toán so với Bloom Filter (yêu cầu nhiều hàm băm).

  4. Hiệu suất cao:

    • Thao tác thêm, xóa và kiểm tra nhanh chóng với độ phức tạp thấp.

  5. Khả năng mở rộng động:

    • QF có thể mở rộng dung lượng hoặc tái cấu trúc mảng khi cần thiết mà không ảnh hưởng lớn đến hiệu suất.

Hạn chế của Quotient Filter

  1. False Positive (Kết quả dương tính giả):

    • Tương tự Bloom Filter, QF có thể báo rằng một phần tử thuộc tập hợp dù thực tế không phải vậy.
    • Tuy nhiên, không có false negative (kết quả âm tính giả).

  2. Phức tạp hơn Bloom Filter:

    • Việc quản lý metadata (trạng thái bucket, phần tử bị dời) khiến QF phức tạp hơn trong triển khai.

  3. Cố định dung lượng:

    • Dung lượng của QF cần được thiết kế trước. Khi vượt quá giới hạn, việc mở rộng dung lượng sẽ yêu cầu tái cấu trúc mảng, gây tốn kém tài nguyên.

  4. Hiệu suất giảm với các tập dữ liệu phân tán:

    • QF không phù hợp với các ứng dụng yêu cầu truy cập ngẫu nhiên, do cần kiểm tra tuần tự trong trường hợp xung đột.

Ứng dụng của Quotient Filter

  • Cơ sở dữ liệu: Lọc dữ liệu, kiểm tra thành viên trong chỉ mục hoặc giảm truy cập đĩa không cần thiết.
  • Hệ thống mạng: Lọc gói tin hoặc kiểm tra thành viên của địa chỉ IP trong bảng định tuyến.
  • Hệ thống phân tán: Đồng bộ dữ liệu giữa các nút hoặc kiểm tra tính nhất quán.
  • Lưu trữ: Loại bỏ trùng lặp dữ liệu (deduplication) trong các hệ thống lưu trữ.

So sánh với Bloom Filter

Tính năng Bloom Filter Quotient Filter
False Positive Có thể xảy ra Có thể xảy ra
False Negative Không Không
Hỗ trợ xóa Không (cần Counting BF) Có
Bộ nhớ Hiệu quả cao Hiệu quả (kèm metadata)
Hàm băm Nhiều Một
Mở rộng động Cần Scalable Bloom Filter Hỗ trợ giới hạn

Ví dụ mã giả bằng Python

 1class QuotientFilter:
 2    def __init__(self, size):
 3        self.size = size
 4        self.table = [None] * size
 5        self.metadata = [False] * size  # Trạng thái bucket
 6
 7    def _hash(self, value):
 8        h = hash(value)
 9        quotient = h // self.size
10        remainder = h % self.size
11        return quotient, remainder
12
13    def insert(self, value):
14        quotient, remainder = self._hash(value)
15        while self.metadata[quotient]:  # Xử lý xung đột
16            quotient = (quotient + 1) % self.size
17        self.table[quotient] = remainder
18        self.metadata[quotient] = True
19
20    def query(self, value):
21        quotient, remainder = self._hash(value)
22        while self.metadata[quotient]:
23            if self.table[quotient] == remainder:
24                return True
25            quotient = (quotient + 1) % self.size
26        return False
27
28    def delete(self, value):
29        quotient, remainder = self._hash(value)
30        while self.metadata[quotient]:
31            if self.table[quotient] == remainder:
32                self.table[quotient] = None
33                self.metadata[quotient] = False
34                return True
35            quotient = (quotient + 1) % self.size
36        return False

Kết luận

Quotient Filter là một giải pháp mạnh mẽ, kết hợp hiệu quả của Bloom Filter và bảng băm, phù hợp cho các ứng dụng cần kiểm tra thành viên, hỗ trợ xóa, và tiết kiệm bộ nhớ. Tuy nhiên, cần xem xét các hạn chế về thiết kế và ứng dụng để sử dụng tối ưu trong các bài toán cụ thể.

Cuckoo Filter

Cuckoo Filter là một cấu trúc dữ liệu xác suất được thiết kế để kiểm tra thành viên trong tập hợp (membership test) giống như Bloom Filter, nhưng với nhiều cải tiến. Nó sử dụng ý tưởng từ Cuckoo Hashing và cung cấp một số tính năng nổi bật như hỗ trợ xóa phần tử và hiệu quả về bộ nhớ.

Nguyên lý hoạt động

Cuckoo Filter hoạt động dựa trên hai khái niệm chính:

  1. Fingerprinting (Chữ ký):

    • Mỗi phần tử được băm để tạo ra một giá trị fingerprint ngắn, đại diện cho phần tử đó.
    • Chỉ lưu trữ giá trị fingerprint trong mảng, giúp tiết kiệm bộ nhớ.

  2. Cuckoo Hashing:

    • Mỗi phần tử có thể được lưu ở một trong hai vị trí tiềm năng trong mảng (table).
    • Khi thêm phần tử mới mà vị trí đã bị chiếm, một phần tử khác có thể bị “đẩy” đến vị trí thứ hai của nó, theo cách tương tự thuật toán Cuckoo Hashing.

Thao tác chính trong Cuckoo Filter

  1. Thêm phần tử (Insert):

    • Tính hai vị trí băm (bucket) cho phần tử dựa trên giá trị fingerprint.
    • Nếu một trong hai vị trí còn trống, lưu fingerprint tại đó.
    • Nếu cả hai vị trí đều đầy, chọn ngẫu nhiên một fingerprint trong bucket và “đẩy” nó đến vị trí thứ hai của nó. Tiếp tục lặp lại cho đến khi chèn thành công hoặc vượt quá số lần thử (rehash nếu cần).

  2. Kiểm tra phần tử (Query):

    • Tính hai vị trí băm dựa trên giá trị fingerprint.
    • Kiểm tra xem giá trị fingerprint có tồn tại tại một trong hai bucket không.

  3. Xóa phần tử (Delete):

    • Tính hai vị trí băm dựa trên giá trị fingerprint.
    • Nếu giá trị fingerprint tồn tại tại một trong hai vị trí, xóa nó.

Ưu điểm của Cuckoo Filter

  1. Hỗ trợ xóa phần tử:

    • Không giống Bloom Filter cơ bản, Cuckoo Filter hỗ trợ xóa phần tử dễ dàng mà không cần các biến thể phức tạp.

  2. Tỷ lệ false positive thấp:

    • Cuckoo Filter cung cấp tỷ lệ dương tính giả (false positive) thấp, đặc biệt khi tối ưu kích thước bucket và fingerprint.

  3. Tiết kiệm bộ nhớ:

    • Nhờ chỉ lưu trữ giá trị fingerprint ngắn, Cuckoo Filter thường tiết kiệm bộ nhớ hơn Bloom Filter trong nhiều trường hợp.

  4. Hiệu suất cao:

    • Thao tác thêm, xóa và kiểm tra nhanh chóng, thường có độ phức tạp ( O(1) ) trung bình.

  5. Hỗ trợ kiểm tra âm tính chính xác:

    • Không bao giờ xảy ra false negative (kết quả âm tính sai).

  6. Khả năng mở rộng:

    • Cuckoo Filter có thể mở rộng thông qua cơ chế rehash hoặc tăng kích thước mảng khi cần thiết.

Hạn chế của Cuckoo Filter

  1. Khó khăn với chèn phần tử dày đặc:

    • Khi mảng quá đầy, việc thêm phần tử mới có thể dẫn đến hiện tượng “cuckoo evictions” (đẩy vòng lặp không thành công), buộc phải tái cấu trúc (rehash) toàn bộ mảng.

  2. Cấu trúc phức tạp hơn Bloom Filter:

    • So với Bloom Filter, Cuckoo Filter yêu cầu quản lý nhiều bucket, cơ chế đẩy phần tử, và xử lý xung đột phức tạp hơn.

  3. Không tối ưu với số lượng phần tử lớn:

    • Với tập dữ liệu quá lớn, Bloom Filter có thể hiệu quả hơn về mặt bộ nhớ so với Cuckoo Filter.

Ứng dụng của Cuckoo Filter

  • Hệ thống cơ sở dữ liệu: Kiểm tra dữ liệu tồn tại trong các chỉ mục hoặc giảm truy cập đĩa.
  • Hệ thống mạng: Lọc gói tin hoặc kiểm tra địa chỉ IP trong bảng định tuyến.
  • Hệ thống phân tán: Đồng bộ dữ liệu, kiểm tra tính nhất quán.
  • Bộ nhớ đệm (Cache): Lọc nhanh các truy vấn trong bộ nhớ đệm.

So sánh với Bloom Filter

Tính năng Bloom Filter Cuckoo Filter
False Positive Có thể xảy ra Có thể xảy ra
False Negative Không Không
Hỗ trợ xóa Không (cần Counting BF) Có
Bộ nhớ Tiết kiệm cao Tiết kiệm tốt (nhưng phức tạp hơn)
Thao tác thêm Đơn giản, không đẩy phần tử Phức tạp hơn do đẩy phần tử
Khả năng mở rộng Cần Scalable Bloom Filter Có hỗ trợ mở rộng trực tiếp

Ví dụ mã giả Cuckoo Filter bằng Python

 1import random
 2
 3class CuckooFilter:
 4    def __init__(self, size, bucket_size=2, fingerprint_size=4):
 5        self.size = size
 6        self.bucket_size = bucket_size
 7        self.fingerprint_size = fingerprint_size
 8        self.buckets = [[] for _ in range(size)]
 9
10    def _hash(self, value):
11        return hash(value) % self.size
12
13    def _fingerprint(self, value):
14        return hash(value) % (2 ** self.fingerprint_size)
15
16    def insert(self, value):
17        fingerprint = self._fingerprint(value)
18        i1 = self._hash(value)
19        i2 = (i1 ^ hash(fingerprint)) % self.size
20
21        if len(self.buckets[i1]) < self.bucket_size:
22            self.buckets[i1].append(fingerprint)
23            return True
24        elif len(self.buckets[i2]) < self.bucket_size:
25            self.buckets[i2].append(fingerprint)
26            return True
27
28        # Eviction
29        i = random.choice([i1, i2])
30        for _ in range(self.size):
31            evicted_fingerprint = self.buckets[i].pop(0)
32            self.buckets[i].append(fingerprint)
33            fingerprint = evicted_fingerprint
34            i = (i ^ hash(fingerprint)) % self.size
35            if len(self.buckets[i]) < self.bucket_size:
36                self.buckets[i].append(fingerprint)
37                return True
38
39        return False  # Failed to insert after many attempts
40
41    def query(self, value):
42        fingerprint = self._fingerprint(value)
43        i1 = self._hash(value)
44        i2 = (i1 ^ hash(fingerprint)) % self.size
45
46        return fingerprint in self.buckets[i1] or fingerprint in self.buckets[i2]
47
48    def delete(self, value):
49        fingerprint = self._fingerprint(value)
50        i1 = self._hash(value)
51        i2 = (i1 ^ hash(fingerprint)) % self.size
52
53        if fingerprint in self.buckets[i1]:
54            self.buckets[i1].remove(fingerprint)
55            return True
56        elif fingerprint in self.buckets[i2]:
57            self.buckets[i2].remove(fingerprint)
58            return True
59        return False

Kết luận

Cuckoo Filter là một cấu trúc dữ liệu mạnh mẽ, hiệu quả và phù hợp cho các ứng dụng cần thêm, xóa, và kiểm tra thành viên nhanh chóng. Mặc dù phức tạp hơn Bloom Filter, nó mang lại nhiều tính năng hữu ích như hỗ trợ xóa và hiệu quả bộ nhớ cao hơn trong một số trường hợp.

Ứng Dụng của Bloom Filter trong Các Lĩnh Vực

1. Phát Hiện Gian Lận Tài Chính (Financial Fraud Detection)

  • Mục đích: Xác định hành vi đáng ngờ trong thói quen mua sắm của người dùng.

  • Cách sử dụng:

    • Sử dụng một Bloom Filter riêng cho mỗi người dùng.
    • Kiểm tra mọi giao dịch để trả lời câu hỏi: Người dùng này đã thanh toán từ địa điểm này trước đây chưa?
    • Bloom Filter cung cấp phản hồi cực kỳ nhanh (độ trễ thấp).
    • Nhân bản dữ liệu qua các khu vực để xử lý khi người dùng di chuyển.

  • Lợi ích khi sử dụng Bloom Filter:

    • Giao dịch hoàn tất nhanh chóng.
    • Giảm nguy cơ giao dịch bị gián đoạn trong trường hợp mạng bị phân vùng (kết nối được giữ trong thời gian ngắn hơn).
    • Tăng cường lớp bảo mật cho cả chủ thẻ tín dụng và nhà bán lẻ.

  • Các câu hỏi khác mà Bloom Filter có thể hỗ trợ trong ngành tài chính:

    • Người dùng đã từng mua sản phẩm/dịch vụ trong danh mục này chưa?
    • Có cần bỏ qua một số bước bảo mật khi mua sắm với các cửa hàng trực tuyến đáng tin cậy (như Amazon, Apple App Store)?
    • Thẻ tín dụng này có bị báo mất hoặc đánh cắp không?
      • Lợi ích bổ sung: Các tổ chức tài chính có thể trao đổi danh sách số thẻ bị mất/mất cắp mà không tiết lộ số thực.

2. Đặt Quảng Cáo (Ad Placement - Retail, Advertising)

  • Mục đích: Hiển thị quảng cáo hoặc đề xuất sản phẩm một cách cá nhân hóa.

  • Cách sử dụng:

    • Sử dụng một Bloom Filter cho mỗi người dùng, lưu trữ danh sách sản phẩm đã mua.
    • Khi hệ thống đề xuất sản phẩm mới:
      • Nếu sản phẩm chưa có trong Bloom Filter, quảng cáo được hiển thị và sản phẩm được thêm vào Bloom Filter.
      • Nếu sản phẩm đã có trong Bloom Filter, hệ thống tiếp tục kiểm tra sản phẩm khác cho đến khi tìm được sản phẩm chưa có.

  • Lợi ích khi sử dụng Bloom Filter:

    • Giải pháp chi phí thấp để tạo trải nghiệm cá nhân hóa gần như theo thời gian thực.
    • Không cần đầu tư vào cơ sở hạ tầng đắt đỏ.

3. Kiểm Tra Tên Người Dùng (SaaS, Content Publishing Platforms)

  • Mục đích: Xác định tên người dùng/email/domain name/slug đã được sử dụng chưa.

  • Cách sử dụng:

    • Sử dụng một Bloom Filter lưu tất cả các tên người dùng đã đăng ký.
    • Khi người dùng nhập tên mong muốn:
      • Nếu không có trong Bloom Filter, tài khoản được tạo và tên được thêm vào Bloom Filter.
      • Nếu có, ứng dụng quyết định kiểm tra cơ sở dữ liệu chính hoặc từ chối tên đó.

  • Lợi ích khi sử dụng Bloom Filter:

    • Phương pháp rất nhanh và hiệu quả để thực hiện thao tác phổ biến.
    • Không cần đầu tư vào cơ sở hạ tầng phức tạp.

4. Các Ứng Dụng Khác Của Bloom Filter

  1. Kiểm Tra Chính Tả (Spell Checker):

    • Trong thời kỳ đầu, bộ kiểm tra chính tả được triển khai bằng Bloom Filter.

  2. Cơ Sở Dữ Liệu (Databases):

    • Nhiều cơ sở dữ liệu phổ biến sử dụng Bloom Filter để giảm số lần truy cập đĩa tốn kém cho các hàng/cột không tồn tại.
    • Các hệ thống như PostgreSQL, Apache Cassandra, Cloud Bigtable sử dụng kỹ thuật này.

  3. Công Cụ Tìm Kiếm (Search Engines):

    • BitFunnel, một thuật toán lập chỉ mục cho công cụ tìm kiếm, sử dụng Bloom Filter để lưu trữ chỉ mục tìm kiếm.

  4. An Ninh (Security):

    • Dùng Bloom Filter để phát hiện mật khẩu yếu, URL độc hại, và các nguy cơ an ninh khác.

Bài tập

Financial Fraud Detection

xây dựng ứng dụng Financial Fraud Detection sử dụng Bloom Filter. Mục tiêu là kiểm tra xem người dùng đã thực hiện giao dịch từ một địa điểm cụ thể hay chưa để phát hiện hành vi gian lận. Nếu người dùng chưa thực hiện giao dịch ở 1 ban nào đó trong lịch sử thì cảnh báo lên

 1
 2import hashlib
 3
 4class BloomFilter:
 5    def __init__(self, size, num_hash_functions):
 6        # Kích thước Bloom filter (số lượng bit)
 7        self.size = size
 8        # Số hàm băm
 9        self.num_hash_functions = num_hash_functions
10        # Mảng bit để lưu trữ (khởi tạo với các bit = 0)
11        self.bit_array = [0] * size
12
13    def _hash(self, item, i):
14        """Hàm băm để tạo chỉ số từ item, với i là chỉ số của hàm băm."""
15        return int(hashlib.sha256(f"{item}{i}".encode('utf-8')).hexdigest(), 16) % self.size
16
17    def add(self, item):
18        """Thêm một item vào Bloom filter."""
19        for i in range(self.num_hash_functions):
20            index = self._hash(item, i)
21            self.bit_array[index] = 1
22
23    def check(self, item):
24        """Kiểm tra một item có trong Bloom filter không."""
25        for i in range(self.num_hash_functions):
26            index = self._hash(item, i)
27            if self.bit_array[index] == 0:
28                return False  # Nếu bất kỳ bit nào là 0, phần tử chắc chắn không có trong bộ lọc
29        return True  # Nếu tất cả các bit đều là 1, có khả năng phần tử có trong bộ lọc
30
31# Khởi tạo Bloom filter với kích thước 1000 bit và 3 hàm băm
32bloom_filter = BloomFilter(size=1000, num_hash_functions=3)
33
34# Mô phỏng thông tin giao dịch của người dùng
35users_transactions = {
36    "tung": ["New York", "Los Angeles", "Miami"],
37    "kim": ["London", "Paris", "Berlin"],
38    "tuan": ["Tokyo", "Osaka", "Kyoto"]
39}
40
41# Thêm tất cả các giao dịch vào Bloom filter
42for user, locations in users_transactions.items():
43    for location in locations:
44        bloom_filter.add(f"{user}-{location}")  # Kết hợp tên người dùng và địa điểm giao dịch
45
46# Kiểm tra một giao dịch mới từ người dùng
47def check_fraud(user, location):
48    if not bloom_filter.check(f"{user}-{location}"):
49        return f"Warning: Transaction from {location} by {user} might be suspicious!"
50    else:
51        return f"Transaction from {location} by {user} is normal."
52
53# Kiểm tra một số giao dịch
54test_transactions = [
55    ("tung", "Miami"),  # Giao dịch hợp lệ
56    ("tung", "Chicago"),  # Giao dịch mới (không có trong Bloom filter)
57    ("kim", "Paris"),  # Giao dịch hợp lệ
58    ("tuan", "Kyoto")   # Giao dịch hợp lệ
59]
60
61# Kiểm tra các giao dịch
62for user, location in test_transactions:
63    result = check_fraud(user, location)
64    print(result)

Kết quả:

1Transaction from Miami by tung is normal.
2Warning: Transaction from Chicago by tung might be suspicious!
3Transaction from Paris by kim is normal.
4Transaction from Kyoto by tuan is normal.

Spell Checker

xây dựng một Spell Checker sử dụng Bloom Filter. Mã này sẽ kiểm tra xem một từ có trong từ điển (dictionary) hay không và đưa ra kết quả.

 1
 2import hashlib
 3
 4class BloomFilter:
 5    def __init__(self, size, num_hash_functions):
 6        # Kích thước của Bloom filter (số lượng bit)
 7        self.size = size
 8        # Số hàm băm
 9        self.num_hash_functions = num_hash_functions
10        # Mảng bit để lưu trữ (được khởi tạo với tất cả các bit là 0)
11        self.bit_array = [0] * size
12
13    def _hash(self, item, i):
14        """Hàm băm để tạo chỉ số từ item, với i là chỉ số của hàm băm."""
15        # Dùng hàm băm SHA-256 và điều chỉnh với chỉ số i để tạo ra các chỉ số khác nhau
16        return int(hashlib.sha256(f"{item}{i}".encode('utf-8')).hexdigest(), 16) % self.size
17
18    def add(self, item):
19        """Thêm một item vào Bloom filter."""
20        for i in range(self.num_hash_functions):
21            index = self._hash(item, i)
22            self.bit_array[index] = 1
23
24    def check(self, item):
25        """Kiểm tra một item có trong Bloom filter không."""
26        for i in range(self.num_hash_functions):
27            index = self._hash(item, i)
28            if self.bit_array[index] == 0:
29                return False  # Nếu bất kỳ bit nào là 0, phần tử chắc chắn không có trong bộ lọc
30        return True  # Nếu tất cả các bit đều là 1, có khả năng phần tử có trong bộ lọc
31
32# Tạo một Bloom filter với kích thước 1000 bit và 3 hàm băm
33bloom_filter = BloomFilter(size=1000, num_hash_functions=3)
34
35# Từ điển mẫu
36dictionary = ["hello", "world", "spell", "check", "python", "bloom", "filter"]
37
38# Thêm tất cả các từ vào Bloom filter
39for word in dictionary:
40    bloom_filter.add(word)
41
42# Kiểm tra chính tả của một số từ
43test_words = ["hello", "world", "java", "python", "flutter"]
44
45for word in test_words:
46    if bloom_filter.check(word):
47        print(f"'{word}' có thể là một từ đúng.")
48    else:
49        print(f"'{word}' chắc chắn là một từ sai.")

Kết quả:

1
2'hello' có thể là một từ đúng.
3'world' có thể là một từ đúng.
4'java' chắc chắn là một từ sai.
5'python' có thể là một từ đúng.

Recommendation Systems Bloom Filters

triển khai việc tránh gợi ý các sản phẩm mà người dùng đã tương tác trước đó bằng cách sử dụng Bloom Filters.

 1
 2
 3import hashlib
 4
 5class BloomFilter:
 6    def __init__(self, size, num_hash_functions):
 7        # Kích thước Bloom filter (số lượng bit)
 8        self.size = size
 9        # Số hàm băm
10        self.num_hash_functions = num_hash_functions
11        # Mảng bit để lưu trữ (khởi tạo tất cả các bit là 0)
12        self.bit_array = [0] * size
13
14    def _hash(self, item, i):
15        """Hàm băm để tạo chỉ số từ item, với i là chỉ số của hàm băm."""
16        return int(hashlib.sha256(f"{item}{i}".encode('utf-8')).hexdigest(), 16) % self.size
17
18    def add(self, item):
19        """Thêm một item vào Bloom filter."""
20        for i in range(self.num_hash_functions):
21            index = self._hash(item, i)
22            self.bit_array[index] = 1
23
24    def check(self, item):
25        """Kiểm tra một item có trong Bloom filter không."""
26        for i in range(self.num_hash_functions):
27            index = self._hash(item, i)
28            if self.bit_array[index] == 0:
29                return False  # Nếu bất kỳ bit nào là 0, phần tử chắc chắn không có trong bộ lọc
30        return True  # Nếu tất cả các bit đều là 1, có khả năng phần tử có trong bộ lọc
31
32# Khởi tạo Bloom filter
33bloom_filter = BloomFilter(size=1000, num_hash_functions=3)
34
35# Mô phỏng danh sách sản phẩm người dùng đã tương tác
36user_interactions = {
37    "tung": ["thịt bò", "hành tây", "khoai tây"],
38    "tuan": ["thit heo", "trứng"],
39    "canh": ["thịt bò", "trứng", "sữa TH", "kem"]
40}
41
42# Thêm các sản phẩm đã tương tác vào Bloom filter
43for user, items in user_interactions.items():
44    for item in items:
45        bloom_filter.add(f"{user}-{item}")  # Kết hợp user và item để lưu trữ duy nhất
46
47# Hàm gợi ý sản phẩm
48def recommend_items(user, candidate_items):
49    """Đưa ra gợi ý các sản phẩm chưa tương tác."""
50    recommendations = []
51    for item in candidate_items:
52        if not bloom_filter.check(f"{user}-{item}"):
53            recommendations.append(item)  # Chỉ thêm sản phẩm nếu chưa tương tác
54    return recommendations
55
56# Danh sách các sản phẩm có thể gợi ý
57candidate_items = ["thịt bò", "hành tây", "khoai tây","trứng", "sữa TH", "kem","thit heo"]
58
59# Gợi ý sản phẩm cho tung
60user = "tung"
61recommendations = recommend_items(user, candidate_items)
62
63print(f"Recommendations for {user}: {recommendations}")

Kết quả:

1Recommendations for tung: ['trứng', 'sữa TH', 'kem', 'thit heo']

https://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

https://en.wikipedia.org/wiki/Bloom_filter

Cảm ơn các bạn đã theo dõi bài viết. Xin cảm ơn và hẹn gặp lại.

Top 10 Thuật Toán System Design Các Bạn Nên Biết Và Thường Được Hỏi Trong Phỏng Vấn - Top 2 Distributed Hash Tables

Comments