Bloom Filter di Jawa menggunakan Jambu Biji

1. Ikhtisar

Pada artikel ini, kita akan melihat konstruksi filter Bloom dari pustaka Guava . Filter Bloom adalah struktur data probabilistik yang hemat memori yang dapat kita gunakan untuk menjawab pertanyaan apakah elemen tertentu ada dalam suatu himpunan atau tidak .

Tidak ada negatif palsu dengan filter Bloom, jadi ketika kembali salah , kita bisa 100% yakin bahwa elemen tersebut tidak ada dalam kumpulan.

Namun, filter Bloom dapat mengembalikan positif palsu , jadi ketika mengembalikan nilai benar , ada kemungkinan besar bahwa elemen tersebut ada dalam kumpulan, tetapi kami tidak bisa 100% yakin.

Untuk analisis yang lebih mendalam tentang cara kerja filter Bloom, Anda dapat mengikuti tutorial ini.

2. Ketergantungan Maven

Kami akan menggunakan implementasi Guava dari filter Bloom, jadi mari tambahkan ketergantungan guava :

 com.google.guava guava 29.0-jre 

Versi terbaru dapat ditemukan di Maven Central.

3. Mengapa Menggunakan Filter Bloom?

Filter Bloom dirancang agar hemat ruang dan cepat . Saat menggunakannya, kami dapat menentukan probabilitas respons positif palsu yang dapat kami terima dan, menurut konfigurasi itu, filter Bloom akan menggunakan memori sesedikit mungkin.

Karena efisiensi ruang ini, filter Bloom akan dengan mudah masuk ke dalam memori bahkan untuk sejumlah besar elemen. Beberapa database, termasuk Cassandra dan Oracle, menggunakan filter ini sebagai pemeriksaan pertama sebelum masuk ke disk atau cache, misalnya, saat permintaan untuk ID tertentu masuk.

Jika filter mengembalikan bahwa ID tidak ada, database dapat menghentikan pemrosesan permintaan lebih lanjut dan kembali ke klien. Jika tidak, ini masuk ke disk dan mengembalikan elemen jika ditemukan di disk.

4. Membuat Filter Bloom

Misalkan kita ingin membuat filter Bloom hingga 500 Integer dan kita dapat mentolerir probabilitas positif palsu sebesar satu persen (0,01).

Kita bisa menggunakan kelas BloomFilter dari perpustakaan Guava untuk mencapai ini. Kita perlu meneruskan jumlah elemen yang ingin dimasukkan ke dalam filter dan probabilitas positif palsu yang diinginkan:

BloomFilter filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01);

Sekarang mari tambahkan beberapa angka ke filter:

filter.put(1); filter.put(2); filter.put(3);

Kami hanya menambahkan tiga elemen, dan kami menetapkan bahwa jumlah maksimum penyisipan adalah 500, jadi filter Bloom kami akan memberikan hasil yang sangat akurat . Mari kita uji menggunakan metode mightContain () :

assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse();

Seperti namanya, kita tidak bisa 100% yakin bahwa elemen tertentu sebenarnya ada di filter ketika metode mengembalikan nilai true .

Ketika mightContain () mengembalikan nilai true dalam contoh kita, kita bisa 99% yakin bahwa elemen tersebut ada dalam filter, dan ada kemungkinan satu persen bahwa hasilnya adalah positif palsu. Ketika filter mengembalikan false , kita bisa 100% yakin bahwa elemen tersebut tidak ada.

5. Filter Bloom yang Terlalu Jenuh

Saat mendesain filter Bloom, penting bagi kami untuk memberikan nilai yang cukup akurat untuk jumlah elemen yang diharapkan . Jika tidak, filter kami akan mengembalikan positif palsu dengan rasio yang jauh lebih tinggi dari yang diinginkan. Mari kita lihat contohnya.

Misalkan kita membuat filter dengan probabilitas positif-palsu yang diinginkan sebesar satu persen dan beberapa elemen yang diharapkan sama dengan lima, tetapi kemudian kita memasukkan 100.000 elemen:

BloomFilter filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Karena jumlah elemen yang diharapkan sangat kecil, filter akan menggunakan sedikit memori.

Namun, saat kami menambahkan lebih banyak item daripada yang diharapkan, filter menjadi terlalu jenuh dan memiliki kemungkinan lebih tinggi untuk mengembalikan hasil positif palsu daripada satu persen yang diinginkan:

assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(1_000_000)).isTrue();

Perhatikan bahwa mightContatin () metode kembali benar bahkan untuk nilai yang kita tidak memasukkan ke filter sebelumnya.

6. Kesimpulan

Dalam tutorial singkat ini, kita melihat sifat probabilistik dari struktur data filter Bloom - memanfaatkan implementasi Guava .

Anda dapat menemukan implementasi dari semua contoh dan cuplikan kode ini di proyek GitHub.

Ini adalah proyek Maven, jadi semestinya mudah untuk mengimpor dan menjalankannya apa adanya.