Gesaan dan konteks
Laksanakan penapis Bloom dengan add(value) dan mightContain(value). Ia merupakan penapis awal sebelum carian mahal dilakukan: false bermaksud nilai tersebut pasti tiada, manakala true bermaksud stor berwibawa masih mesti diperiksa. Rangkumi n, p, m, k, pemadaman, saiz semula, konkurensi dan ujian.
Perkara yang diuji oleh penemu duga
Semantik keahlian yang betul
Penapis Bloom standard membenarkan positif palsu tetapi bukan negatif palsu. Nama mightContain harus menghalang pemanggil daripada menganggap true sebagai bukti keahlian.
Penentuan saiz yang boleh diterangkan
Panjang tatasusunan bit m dan bilangan cincangan k mengawal memori, kelajuan dan kadar ralat. Minta maklumat kardinaliti jangkaan dan p yang boleh diterima sebelum memilih parameter.
Batasan yang lengkap
Jawapan yang kukuh menyatakan bahawa struktur standard tidak boleh memadam satu nilai secara selamat, ketepuan meningkatkan kadar positif palsu, dan pertumbuhan memerlukan pembinaan semula atau reka bentuk berlapis yang berskala.
Soalan untuk dijelaskan terlebih dahulu
- Berapakah bilangan nilai yang dijangkakan, dan apakah kadar positif palsu p yang boleh diterima?
- Adakah nilai disiri kepada jujukan bait yang stabil merentas proses dan versi?
- Adakah penapis jenis tambah sahaja (append-only), atau adakah ia mesti menyokong pemadaman dan kemas kini?
- Apakah belanjawan memori, kependaman dan penulisan serentak?
- Apabila kapasiti dicapai, patutkah penapis membina semula, menolak penulisan, atau menambah lapisan?
- Bagaimanakah positif palsu dan pengesahan berwibawa akan diukur?
Jawapan 30 saat
“Saya akan menggunakan tatasusunan m-bit dan k kedudukan yang cukup bebas. add menetapkan k bit tersebut; bit sifar semasa pertanyaan membuktikan ketiadaan, manakala semua satu bermaksud kemungkinan kehadiran. Untuk n jangkaan dan sasaran p, gunakan m=-n ln(p)/(ln2)^2 dan k=(m/n)ln2. Penapis standard tidak boleh memadam secara selamat, jadi pemadaman memerlukan baldi pengiraan; perubahan kapasiti memerlukan pembinaan semula atau lapisan. Saya akan menguji ketiadaan negatif palsu, kadar positif palsu yang disampel, ketepuan dan jaminan konkurensi.”
Jawapan mendalam langkah demi langkah
Nyatakan invarians dan API
Semua bit bermula pada sifar. Fungsi cincangan yang stabil menghasilkan k indeks bagi setiap nilai; pemasukan hanya menukar bit daripada sifar kepada satu. Jika pertanyaan melihat sifar pada mana-mana indeks yang diperlukan, nilai tersebut tidak mungkin telah memasukkan set kedudukan yang tepat ini.
Kira m dan k
Untuk n item jangkaan dan kadar positif palsu sasaran p, gunakan m = -n * ln(p) / (ln(2)^2) dan k = (m/n) * ln(2). Dengan n=1,000,000 dan p=1%, m adalah kira-kira 9.6M bit, lebih kurang 1.14 MiB, dan k adalah kira-kira 7.
Pilih cincangan dan operasi bit
Pencincangan berganda boleh menerbitkan kedudukan sebagai h_i(x) = h1(x) + i*h2(x) modulo m, mengelakkan k pelaksanaan cincangan penuh. Tetapkan pengekodan bait, keendianan (endianness), dan benih (seeds); mengubahnya menjadikan penapis yang dikekalkan tidak serasi.
Terangkan pemadaman dan saiz semula
Beberapa nilai boleh berkongsi bit yang sama, jadi mengosongkannya untuk satu pemadaman boleh menghasilkan negatif palsu. Oleh itu, penapis Bloom standard tidak mempunyai operasi padam yang selamat. Penapis Bloom Pengiraan menambah pembilang bagi setiap baldi dengan kos memori. Apabila kapasiti jangkaan berubah, bina semula penapis yang lebih besar atau gunakan beberapa lapisan terhad kapasiti.
Kendalikan konkurensi dan kitaran hayat
Bacaan serentak biasanya mudah. Penulisan serentak tidak boleh kehilangan operasi penetapan bit; OR atomik, tatasusunan bit terpecah (sharded), atau kunci penulisan adalah pilihan yang mungkin. Kekalkan kapasiti, m, k, algoritma cincangan, benih dan versi format bersama-sama.
Pseudokod
~~~text add(x): for i in 0..k-1: bits[index(hash1(x), hash2(x), i)] = 1
mightContain(x): for i in 0..k-1: if bits[index(hash1(x), hash2(x), i)] == 0: return false return true ~~~
Kerumitan dan pengesahan
Setiap operasi menyemak atau menetapkan k kedudukan, jadi masa adalah O(k) dan ruang tambahan adalah O(m). Uji bahawa setiap nilai yang dimasukkan mengembalikan true, anggarkan positif palsu daripada sampel tiada secara rawak, perhatikan ketepuan berhampiran kapasiti, dan rangkumi kes kosong, pendua, benih/versi serta penulisan serentak.
| Operasi | Kontrak | Kerumitan |
|---|---|---|
add(x) | Menetapkan bit dan tidak pernah membuang bukti keahlian | O(k) |
mightContain(x) | false adalah ketiadaan pasti; true adalah kemungkinan kehadiran | O(k) |
| Saiz semula | Bina semula atau tambah lapisan terhad kapasiti | Bergantung pada kiraan item dan m |
Jawapan model
“Penapis Bloom ialah penapis awal keahlian kebarangkalian. Saya akan mengekalkan tatasusunan m-bit dan k fungsi kedudukan. Pemasukan menetapkan k bit; pertanyaan yang menemui sebarang sifar mengembalikan false, manakala semua satu mengembalikan true tetapi hanya sebagai ‘kemungkinan hadir’, jadi stor sandaran mengesahkannya. Kira m dan k daripada n dan p; satu juta item pada 1% positif palsu memerlukan kira-kira 9.6M bit dan tujuh kedudukan. Struktur standard tidak boleh memadam kerana bit dikongsi; gunakan varian pengiraan untuk pemadaman dan bina semula atau lapiskan penapis apabila kapasiti bertambah. Saya akan menetapkan pengekodan dan benih, kemudian menguji tiada negatif palsu dan mengukur positif palsu pada sampel yang tiada.”
Kesilapan lazim
Menganggap true sebagai bukti
Semua bit yang diperlukan bernilai satu boleh terhasil daripada nilai-nilai lain. Pemanggil masih memerlukan carian berwibawa.
Menggunakan satu cincangan
Satu cincangan boleh memesongkan taburan bit dan kadar ralat yang direka bentuk. Gunakan pencincangan berganda atau terangkan andaian kebebasan di sebalik berbilang kedudukan.
Mengosongkan bit untuk pemadaman
Mengosongkan bit yang dikongsi boleh menyebabkan nilai lain yang dimasukkan mengembalikan false. Gunakan baldi pengiraan atau bina semula sebagai ganti.
Mengabaikan ketepuan
Apabila lebih banyak bit menjadi satu, positif palsu meningkat. Jejaki anggaran kardinaliti dan nisbah bit yang ditetapkan, dan bina semula sebelum belanjawan melebihi had.
Menguji hit sahaja
Tanpa sampel yang tiada, kapasiti sempadan dan ujian pemasukan pendua, pelaksanaan tersebut tidak menunjukkan kontrak ralatnya.
Soalan susulan dan jawapan
Mengapakah positif palsu tidak boleh menjadi sifar?
Nilai yang berbeza boleh dipetakan kepada set bit terhingga yang sama. Lebih banyak memori dan k yang sesuai mengurangkan kadar tersebut tetapi tidak menghapuskan perlanggaran.
Bilakah anda akan memilih penapis Cuckoo?
Bandingkannya apabila pemadaman, penyimpanan cap jari (fingerprint), atau tingkah laku carian menjadi penting. Buat penanda aras memori, penulisan dan pemadaman daripada memilih berdasarkan nama sahaja.
Bagaimanakah anda mengekalkannya (persist)?
Simpan tatasusunan bit bersama m, k, algoritma cincangan, benih, versi pengekodan dan anggaran kapasiti. Sahkan versi semasa memuatkan.
Bagaimanakah anda memantau kualiti?
Ukur positif palsu yang disahkan bahagian belakang (backend), nisbah bit yang ditetapkan, anggaran kardinaliti, kependaman carian dan kiraan pembinaan semula. Cetuskan pembinaan semula atau lapisan baharu pada ambang yang ditetapkan.
Apakah andaian yang mendasari formula tersebut?
Ia mengandaikan pencincangan hampir seragam, volum pemasukan hampir dengan n, dan kebebasan yang mencukupi antara kedudukan. Tentukur dengan sampel daripada data sebenar.
Bagaimanakah anda mengelakkan kehilangan penulisan serentak?
Gunakan penetapan bit atomik atau kunci terpecah (sharded locks), dan pastikan pembaca melihat penulisan yang lengkap. Jika ketekalan akhirnya (eventual consistency) boleh diterima, terbitkan snapshot tidak boleh ubah yang digabungkan.