Apakah formula algoritma untuk saiz penapis mekar Redis?

1. Pengenalan

Pelanggan: Adakah kunci ini wujud?

Pelayan: tidak wujud/tidak tahu

Penapis Bloom ialah struktur data probabilistik yang bijak, yang pada asasnya ialah struktur data. Ia menampilkan sisipan dan pertanyaan yang cekap. Tetapi apabila kita ingin menyemak sama ada kunci wujud dalam struktur tertentu, dengan menggunakan penapis Bloom, kita boleh mengetahui dengan cepat bahawa "kunci ini mesti tidak wujud atau mungkin wujud." Berbanding dengan struktur data tradisional seperti Senarai, Set dan Peta, ia lebih cekap dan mengambil sedikit ruang, tetapi hasil yang dipulangkan adalah berkemungkinan dan tidak tepat.

Penapis Bloom hanya digunakan untuk menguji keahlian dalam koleksi. Contoh penapis Bloom klasik adalah untuk meningkatkan kecekapan dengan mengurangkan carian cakera (atau rangkaian) yang mahal untuk kunci yang tidak wujud. Seperti yang dapat kita lihat, penapis Bloom boleh mencari kunci dalam masa tetap O(k), dengan k ialah bilangan fungsi cincang, dan ujian untuk ketiadaan kunci akan menjadi sangat pantas.

2. Senario Aplikasi

2.1 Penembusan Cache

Untuk meningkatkan kecekapan akses, kami akan meletakkan beberapa data dalam cache Redis. Apabila melakukan pertanyaan data, anda boleh mendapatkan data daripada cache terlebih dahulu tanpa membaca pangkalan data. Ini boleh meningkatkan prestasi dengan berkesan.
Apabila membuat pertanyaan data, anda mesti terlebih dahulu menentukan sama ada terdapat data dalam cache Jika terdapat data, dapatkan data terus daripada cache.
Tetapi jika tiada data, anda perlu mendapatkan data daripada pangkalan data dan memasukkannya ke dalam cache. Jika sebilangan besar akses gagal mencapai cache, ia akan memberi banyak tekanan pada pangkalan data, menyebabkan pangkalan data ranap. Menggunakan penapis Bloom, apabila mengakses cache yang tidak wujud, anda boleh kembali dengan cepat untuk mengelakkan cache atau ranap DB.

2.2 Tentukan sama ada data tertentu wujud dalam data besar

HBase menyimpan jumlah data yang sangat besar Untuk menentukan sama ada ROWKEYS atau lajur tertentu wujud, gunakan penapis Bloom Anda boleh cepat dapatkan sama ada data tertentu wujud. Tetapi terdapat kadar salah penilaian tertentu. Tetapi jika kunci tidak wujud, ia mesti tepat.

3. Masalah dengan HashMap

Untuk menentukan sama ada unsur tertentu wujud, kecekapan menggunakan HashMap adalah sangat tinggi. HashMap boleh mencapai kerumitan masa tetap O(1) dengan memetakan nilai ke Kunci HashMap.
Namun, jika jumlah data yang disimpan adalah sangat besar (contohnya: ratusan juta data), HashMap akan menggunakan jumlah memori yang sangat besar. Dan adalah mustahil untuk membaca sejumlah besar data ke dalam memori pada satu masa.

4. Fahami gambarajah prinsip kerja penapis Bloom

:

Penapis Bloom ialah susunan bit atau vektor binari sedikit
Elemen dalam tatasusunan ini disimpan sama ada 0 atau 1
k fungsi cincang adalah bebas antara satu sama lain, dan hasil pengiraan setiap fungsi cincang ialah modulo panjang m tatasusunan, dan tetapkan bit yang sepadan kepada 1 (sel biru)
Kami menetapkan sel untuk setiap kekunci dengan cara ini, iaitu "Penapis Bloom"

5 Menurut elemen pertanyaan penapis panjang kain

Anggap itu kunci dimasukkan. Kami menggunakan fungsi cincangan k sebelumnya untuk mencari cincangan dan mendapatkan nilai k
untuk menentukan sama ada nilai k semuanya berwarna biru Jika satu bukan Biru, maka kunci itu mestilah tidak wujud
Jika kedua-duanya berwarna biru, maka kunci mungkin wujud (Penapis Bloom akan menyebabkan salah penilaian)
Kerana jika terdapat banyak objek input dan setnya agak kecil, ia akan Akibatnya, kebanyakan kedudukan dalam koleksi akan dicat biru. Kemudian apabila kunci tertentu ditandakan sebagai biru, kedudukan tertentu akan ditetapkan kepada biru Pada masa ini, ia akan tersilap percaya bahawa kunci itu berada dalam koleksi
Contoh:

6. Bolehkah ia dipadamkan? Walau bagaimanapun, varian yang dipanggil penapis Counting Bloom boleh digunakan untuk menguji sama ada bilangan kiraan elemen benar-benar kurang daripada ambang tertentu dan ia menyokong pemadaman elemen. Prinsip dan pelaksanaan artikel Counting Bloom Filter ditulis dengan sangat terperinci dan anda boleh membacanya secara terperinci.

7. Bagaimana untuk memilih bilangan fungsi cincang dan panjang penapis Bloom

Jelas sekali, jika penapis Bloom terlalu kecil, semua bit tidak lama lagi akan menjadi 1, maka sebarang nilai boleh ditanya Semua akan kembali "mungkin wujud", yang mengalahkan tujuan penapisan. Apabila panjang penapis Bloom bertambah, kadar positif palsunya berkurangan.

Selain itu, bilangan fungsi cincang juga perlu ditimbang Lebih banyak nombor, lebih cepat kedudukan bit penapis Bloom ditetapkan kepada 1, dan lebih rendah kecekapan penapis Bloom; terlalu sedikit Jika ya, kadar penggera palsu kami akan menjadi lebih tinggi.

Seperti yang dapat dilihat daripada rajah di atas, meningkatkan bilangan fungsi cincang k akan mengurangkan kadar ralat p.

Jangan risau, kami sebenarnya perlu mengesahkan nilai m dan k. Kemudian, jika kita menentukan toleransi kesalahan p dan bilangan elemen n, kita boleh mengira parameter ini menggunakan formula berikut: Untuk mengira kadar penggera palsu p, formulanya adalah seperti berikut: Berdasarkan perkara di atas, bagaimana untuk memilih k dan nilai m sesuai untuk perniagaan?

Formula:

k ialah bilangan fungsi cincang, m ialah panjang penapis Bloom, n ialah bilangan elemen yang dimasukkan dan p ialah kadar positif palsu .

Bagaimana untuk mendapatkan formula ini, saya telah menerbitkan artikel tentang Zhihu jika anda berminat, anda boleh membacanya Jika anda tidak berminat, ingat formula di atas.

Saya juga ingin menyebut satu lagi perkara penting di sini. Memandangkan satu-satunya tujuan menggunakan penapis Bloom adalah untuk mencari lebih cepat, kita tidak boleh menggunakan fungsi cincang perlahan, bukan? Fungsi cincang kriptografi (cth. Sha-1, MD5) bukanlah pilihan yang baik untuk penapis bloom kerana ia agak perlahan. Jadi, pilihan yang lebih baik daripada pelaksanaan fungsi cincang yang lebih pantas ialah murmur, pencincangan keluarga fnv, pencincangan Jenkins dan HashMix.

Lagi Senario Aplikasi

Dalam contoh yang diberikan, anda telah melihat bahawa kami boleh menggunakan ini untuk memberi amaran kepada pengguna kerana memasukkan kata laluan yang lemah.

Anda boleh menggunakan penapis bloom untuk menghalang pengguna daripada melawati tapak web berniat jahat.

Daripada menanyakan pangkalan data SQL untuk menyemak sama ada pengguna dengan e-mel tertentu wujud, anda boleh menggunakan penapis Bloom Bloom dahulu untuk melakukan semakan carian murah. Jika e-mel itu tidak wujud, bagus! Jika ia wujud, anda mungkin perlu membuat pertanyaan tambahan kepada pangkalan data. Anda juga boleh melakukan perkara yang sama untuk mencari "nama pengguna sudah diambil."
Anda boleh menyimpan penapis Bloom berdasarkan alamat IP pelawat tapak web anda untuk menyemak sama ada pengguna tapak web anda adalah "Pengguna Kembali" atau "Pengguna Baharu". Beberapa positif palsu daripada "pengguna yang kembali" tidak boleh menyakiti anda, bukan?
Anda juga boleh melakukan semakan ejaan dengan menjejaki perkataan kamus menggunakan penapis Bloom.

Atas ialah kandungan terperinci Apakah formula algoritma untuk saiz penapis mekar Redis?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!