Diberi nama pengguna pada halaman pendaftaran pengguna, bagaimana kami tahu jika sudah terdaftar?

Saat menanyakan database yang diindeks membantu, ini lambat dan menimbulkan panggilan jaringan.

Untuk mempercepat, kita dapat meng-cache daftar nama pengguna terdaftar di penyimpanan nilai kunci seperti Redis.

Namun, itu berarti menyimpan jutaan catatan dalam cache dan menggandakan jejak memori kita.

Bagaimana kita bisa berbuat lebih baik dalam masalah yang tampaknya sepele ini?

Filter mekar mungkin jawabannya, yuk simak!

Apa itu Filter Bloom?

Filter mekar menjawab satu pertanyaan sederhana,

Apakah ada elemen dalam himpunan tertentu?

Filter mekar adalah struktur data probabilistik. Mengingat pertanyaan di atas, itu menghasilkan salah satu dari jawaban berikut

• Mungkin Ya
• 100% Tidak

Dan keuntungan terbesarnya adalah, ini dilakukan dalam ruang dan waktu yang KONSTAN .

Bagaimana cara kerjanya?

Filter mekar terdiri dari dua komponen

• Array bit berukuran N
• Beberapa fungsi hashing

Ini pertama kali diinisialisasi sebagai larik bit ukuran-N dengan semua bitnya disetel ke nol. Mari kita asumsikan panjang array menjadi 10 untuk saat ini.

Menambahkan item

Menambahkan item itu sepele

• Item yang bertuliskan "harimau", di-hash menggunakan fungsi hashing
• Hash yang dihasilkan adalah mod dengan panjang array untuk mendapatkan indeks terbatas
• Indeks array bit kemudian diatur ke 1

Mirip dengan menambahkan item, kami melakukan hash pada elemen menggunakan fungsi hashing dan memodifikasinya untuk mendapatkan indeks terbatas.

Output dievaluasi sebagai berikut,

• Jika nilai indeks dari array bit adalah 0, item tersebut TIDAK ada di set.
• Jika tidak, item tersebut MUNGKIN ada di set

Menyimpan filter mekar

Alih-alih menyimpan filter mekar sebagai larik, kita dapat mengubah representasi bitnya menjadi angka desimal.

Misalnya, kita dapat mengonversi array yang berisi 1001119 dan menyimpannya dalam cache.

Jika daftar tidak terlalu sering berubah, server dapat mengirimkan angka desimal ke klien, memungkinkan validasi dilakukan di sisi klien.

Bisakah kita berbuat lebih baik?

Jika fungsi hashing menghasilkan indeks 1 untuk "harimau" dan "sapi", memeriksa apakah "sapi" ada di set menghasilkan jawaban Ya meskipun bukan .

Kami dapat mengurangi kemungkinan positif palsu melalui solusi berikut.

• Menambah panjang array
• Tingkatkan jumlah fungsi hashing

Alih-alih satu indeks, kita bisa mendapatkan banyak indeks menggunakan beberapa hash.

Saat menambahkan item, semua indeks yang diperoleh akan disetel ke 1.

Item diklaim mungkin ada di set, hanya jika SEMUA indeks disetel ke 1.

Dengan memanfaatkan metode ini, kami dapat secara signifikan menurunkan kemungkinan positif palsu.

Aplikasi

Mari kita lihat beberapa contoh kehidupan nyata.

Periksa apakah ada nama pengguna dalam alur pendaftaran pengguna

• Saat nama pengguna dibuat, nama pengguna ditambahkan ke filter mekar yang disimpan di penyimpanan nilai kunci.
• Saat pengguna memasukkan nama pengguna pada halaman pendaftaran pengguna, server terlebih dahulu menanyakan filter bloom.
• Jika nama pengguna TIDAK ada dalam filter mekar, server langsung mengembalikan kesalahan ke klien.
• Jika tidak, server melakukan kueri dan pemeriksaan silang di database.

• Medium mempertahankan filter mekar untuk setiap pengguna.
• Sebelum merekomendasikan artikel, Medium memeriksa apakah ID artikel ada di filter mekar pengguna.
• Artikel yang pasti TIDAK di filter mekar direkomendasikan kepada pengguna.

• Saat mengakses URL, Chrome terlebih dahulu memvalidasi apakah URL merupakan bagian dari daftar berbahaya.
• Alih-alih menanyakan server Google setiap kali, Google membuat filter mekar menggunakan daftar berbahaya yang telah ditentukan sebelumnya dan mengirimkannya ke browser.
• Peramban melakukan hash pada URL dan memeriksa ulang dengan filter mekar sebelum mengakses situs web.

Meskipun mungkin ada positif palsu , filter mekar berguna saat kami ingin mengetahui apakah suatu item benar- benar tidak ada dalam daftar.

Ini dapat digunakan sebagai lapisan pertama penyaringan karena efisiensinya dalam ruang dan waktu.

Saya harap Anda menemukan ini bermanfaat, dan sampai jumpa di yang berikutnya!