Gunakan pemeriksaan keanggotaan aproksimatif

Pertanyaan

Bagaimana menjawab "apakah item ini pernah terlihat?" tanpa menyimpan semua item, dan jenis kesalahan apa yang kita terima sebagai gantinya?

Setelah baca ini, kamu bisa menghitung ukuran Bloom filter untuk target false positive tertentu, dan menjelaskan kenapa jawaban "tidak ada" boleh dipercaya sementara "ada" harus dicek.

Prasyarat dan contoh

Kamu paham fungsi hash dan sudah melihat kebutuhan dedup di M12.01. Pengetahuan tentang cache miss dari M06 membantu, tapi tidak wajib.

Contoh: layanan crawler mau tahu apakah sebuah URL sudah pernah diunduh. Ada 1 miliar URL. Set eksak dengan rata-rata 60 byte per URL butuh sekitar 60 GB, belum termasuk overhead. Untuk pertanyaan yang diajukan jutaan kali per detik, itu mahal. Tapi kamu tidak butuh jawaban eksak di setiap pertanyaan. Kamu butuh cara murah untuk menghindari pencarian ke penyimpanan yang lambat pada sebagian besar URL baru.

Mekanisme

Bloom filter adalah array m bit yang awalnya 0 dan k fungsi hash.

• Tambah item: hitung k posisi, set semuanya menjadi 1.
• Cek item: hitung k posisi. Kalau ada satu bit 0, item pasti belum pernah ditambahkan. Kalau semuanya 1, item mungkin pernah ditambahkan.

Asimetri itu intinya. Bit tidak pernah kembali ke 0, jadi item yang sudah ditambahkan selalu lolos cek: tidak ada false negative. Sebaliknya, bit yang di-set item lain bisa kebetulan menutupi semua posisi item baru: itu false positive.

Probabilitas false positive setelah n item kira-kira (1 - e^(-kn/m))^k. Dari rumus itu, untuk target p:

• m ≈ -n · ln(p) / (ln 2)², sekitar 9,6 bit per item untuk p = 1%, dan 14,4 bit per item untuk p = 0,1%.
• k ≈ (m/n) · ln 2, sekitar 7 untuk p = 1%.

Untuk 1 miliar URL dan p = 1%, itu sekitar 9,6 miliar bit atau 1,2 GB. Bandingkan dengan 60 GB. Cukup di satu mesin.

Filter ini bisa digabung: dua filter dengan m dan fungsi hash yang sama digabung dengan OR bit per bit, dan hasilnya setara dengan filter yang menerima semua item dari keduanya. Itu berguna untuk membangun filter per partisi lalu menyatukannya.

Saat rancangan ini gagal

• Kelebihan beban. Rumus berlaku untuk n yang direncanakan. Filter yang dirancang untuk 1 miliar item tapi menerima 3 miliar akan penuh dengan bit 1, dan false positive-nya melonjak jauh di atas 1%, mendekati 100% kalau terus ditambah. Pantau jumlah item atau proporsi bit terisi (pada beban rancangan, sekitar 50%).
• Menganggap "mungkin ada" sebagai "ada". Kalau Bloom filter dipakai sebagai satu-satunya dedup untuk penagihan, 1% transaksi baru akan dibuang sebagai duplikat. Itu kehilangan data, bukan optimasi.
• Penghapusan. Bit tidak bisa dihapus tanpa berisiko membuat item lain hilang, dan itu melahirkan false negative. Varian counting Bloom filter mendukung hapus dengan menyimpan counter di tiap posisi, dengan memori beberapa kali lipat. Kalau data sering dihapus, pertimbangkan struktur lain atau bangun ulang filter berkala.
• Hash yang tidak independen atau lemah. Hash yang berkorelasi membuat bit menumpuk di posisi yang sama, dan false positive nyata lebih tinggi daripada rumus. Pakai hash berkualitas (misalnya dua hash dasar yang dikombinasikan untuk menghasilkan k posisi) dan ukur secara empiris.
• Data adversarial. Kalau penyerang bisa memilih input, ia bisa menyusun item yang memicu false positive. Pakai hash berkunci rahasia untuk input yang tidak dipercaya.

Latihan

Sebuah layanan email ingin menghindari pengiriman dua kali ke alamat yang sama dalam satu kampanye. Ada 50 juta alamat per kampanye.

1. Hitung ukuran Bloom filter untuk false positive 0,1%.
2. Apa akibatnya kalau filter dipakai sebagai satu-satunya pengecek dan false positive terjadi?
3. Rancang cara memakai filter yang aman.

Lihat pembahasan+

1. Sekitar 14,4 bit per item: 50 juta × 14,4 = 720 juta bit, kira-kira 90 MB, dengan k sekitar 10. Cek dengan rumus: m/n = 14,4, k = 14,4 × 0,693 ≈ 10.
2. Karena false positive 0,1%, sekitar 50.000 alamat yang belum pernah dikirimi dianggap sudah dikirimi, lalu dilewati. Itu pelanggan yang tidak menerima email tanpa ada yang tahu. Tidak ada false negative, jadi tidak ada pengiriman ganda, tapi ada pengiriman yang hilang.
3. Pakai filter sebagai jalur cepat. Kalau filter bilang "tidak ada", kirim dan tambahkan ke filter. Kalau bilang "mungkin ada", cek tabel eksak pengiriman. Hanya 0,1% kasus yang membayar pencarian itu. Filter menghemat hampir semua pembacaan, dan kebenaran tetap ada di tabel.

Terkait

• Sebelumnya: M12.02 Menghitung dalam kondisi berebut sumber daya.
• Lanjut ke M12.04 Perkirakan kardinalitas dan item teratas.
• Proyek B09 dan lab L12 belum tersedia.
• Cache dan negative caching dibahas di M06, yang belum tersedia.

Catatan

• Asumsi: hash independen dan seragam, dan n tidak melewati rancangan.
• Yang nggak dibahas: cuckoo filter, quotient filter, dan Bloom filter yang dapat diskalakan.
• Rumus dan angka bit per item adalah hasil standar. Ukur false positive nyata dengan data kamu sendiri.
• Terakhir ditinjau: 26 Oktober 2026.