Memahami Bloom Filter lewat Contoh

 (llimllib.github.io)
2 poin oleh GN⁺ 2025-07-01 | 1 komentar | Bagikan ke WhatsApp
  • Bloom filter adalah struktur data yang dengan cepat menyaring apakah suatu elemen termasuk dalam himpunan besar menggunakan memori kecil, dan hanya membedakan antara “pasti tidak ada” dan “mungkin ada”
  • Intinya adalah vektor bit dan beberapa fungsi hash; saat penyisipan, bit pada posisi yang ditunjuk oleh hasil hash diubah menjadi 1
  • Saat pencarian, posisi yang sama diperiksa; jika ada satu saja yang bernilai 0, elemen bisa dikecualikan, tetapi meski semuanya 1, kemungkinan false positive tetap ada
  • Fungsi hash harus independen, mendekati distribusi seragam, dan cepat; ada kasus yang memperoleh peningkatan kecepatan sekitar 800% setelah mengganti md5 dengan murmur
  • Akurasi dan biaya filter bergantung pada keseimbangan antara jumlah elemen yang diperkirakan n, jumlah bit m, dan jumlah hash k; penyisipan maupun pencarian berada pada tingkat O(k)

Cara kerja Bloom filter

  • Bloom filter adalah struktur data probabilistik yang menentukan dengan cepat dan efisien memori apakah suatu elemen termasuk dalam sebuah himpunan
  • Hasilnya terbatas pada dua kemungkinan
    • Elemen pasti tidak ada dalam himpunan
    • Elemen mungkin ada dalam himpunan
  • Struktur internalnya adalah vektor bit, dan saat menambahkan elemen, input dilewatkan ke beberapa fungsi hash
  • Penyisipan selesai dengan menyetel indeks bit yang ditunjuk oleh setiap nilai hash menjadi 1
  • Dalam contoh ini, Fnv dan Murmur digunakan sebagai fungsi hash sederhana

Pemeriksaan keanggotaan dan false positive

  • Pencarian juga menggunakan fungsi hash yang sama seperti saat penyisipan
  • Jika salah satu bit yang ditunjuk oleh nilai hash bernilai 0, elemen tersebut pasti tidak ada dalam himpunan
  • Jika semua bit terkait bernilai 1, elemen tersebut mungkin ada
    • Bit-bit yang sama bisa saja sudah disetel oleh satu elemen lain atau kombinasi beberapa elemen lain
  • Karena tabrakan ini, Bloom filter memiliki kemungkinan false positive

Kriteria pemilihan fungsi hash

  • Fungsi hash untuk Bloom filter harus independen, mendekati distribusi seragam, dan secepat mungkin
  • Hash kriptografis seperti sha1 banyak digunakan, tetapi belum tentu selalu menjadi pilihan yang baik untuk Bloom filter
  • Contoh hash yang cepat dan sederhana adalah sebagai berikut
  • Ada kasus yang memperoleh peningkatan kecepatan sekitar 800% setelah implementasi Bloom filter diganti dari md5 ke murmur

Hash yang digunakan dalam implementasi nyata

  • Berbagai implementasi menggunakan fungsi hash yang berbeda untuk Bloom filter
    • Chromium: menggunakan murmur
    • Plan9: menggunakan hash sederhana yang diusulkan dalam Mitzenmacher 2005
    • Sdroege Bloom filter: menggunakan fnv1a
    • Squid: menggunakan MD5
    • RedisBloom: menggunakan murmur
    • Apache Spark: menggunakan murmur
    • influxdb: menggunakan xxhash
    • bloomd: dua hash pertama menggunakan murmur, dua hash berikutnya menggunakan SpookyHash, dan hash setelahnya menggunakan kombinasi keduanya
    • fleur, flor, bloom: menggunakan fnv
    • Sqlite: menambahkan Bloom filter untuk kueri analisis
    • RocksDB: dapat dikonfigurasi, dan di sumbernya disebutkan bahwa xxh3 dari keluarga xxhash memberikan hasil terbaik
    • ScyllaDB: menggunakan murmur

Menentukan ukuran filter dan jumlah fungsi hash

  • Bloom filter dapat menyesuaikan tingkat false positive
    • Filter yang lebih besar mengurangi false positive
    • Filter yang lebih kecil meningkatkan false positive
  • Tingkat false positive dihitung kira-kira dengan (1-e^-kn/m)^k
    • n: jumlah elemen yang diperkirakan akan disisipkan
    • m: jumlah bit dalam filter
    • k: jumlah fungsi hash
  • Semakin banyak fungsi hash, semakin lambat pencarian dan penyisipan, dan filter juga lebih cepat terisi
  • Sebaliknya, jika fungsi hash terlalu sedikit, false positive bisa menjadi terlalu banyak
  • Untuk m dan n tertentu, k optimal dapat dipilih sebagai (m/n)ln(2)
  • Ukuran filter dapat disesuaikan dengan urutan berikut
    • Tentukan perkiraan nilai n
    • Pilih nilai m
    • Hitung nilai k yang optimal
    • Hitung tingkat kesalahan dengan n, m, dan k yang dipilih
    • Jika tingkat kesalahan sulit diterima, ubah m dan hitung ulang

Performa dan kondisi penggunaan yang sesuai

  • Pada Bloom filter dengan m bit dan k fungsi hash, penyisipan dan pemeriksaan keanggotaan sama-sama O(k)
  • Saat menambahkan atau mencari elemen, cukup lewati elemen ke k fungsi hash lalu setel atau periksa bit terkait
  • Efisiensi ruang bergantung pada tingkat kesalahan yang dapat diterima
  • Jika rentang elemen yang dapat disisipkan sangat terbatas, vektor bit deterministik mungkin lebih baik
  • Jika jumlah elemen yang akan disisipkan tidak dapat diperkirakan bahkan secara kasar, tabel hash atau scalable Bloom filter mungkin lebih cocok

Referensi dan contoh penggunaan

Bacaan terkait

1 komentar

 
GN⁺ 2025-07-01
Komentar Hacker News

  • Artikel ini benar-benar ditujukan untuk orang seperti saya. Saya pernah mendengar nama Bloom filter, dan setiap kali disebut saya hanya berpikir harus mencarinya nanti. Setelah membaca artikel ini, akhirnya saya mencarinya, dan ini sempurna sebagai pengantar yang saya inginkan :)

    • Saya mengenal Bloom filter lebih dari 10 tahun lalu ketika ditugaskan mengimplementasikannya untuk fitur pencarian iBooks
    • Strukturnya benar-benar menarik. Kalau muncul masalah yang membutuhkan Bloom filter, rasanya menyenangkan, tetapi sayangnya tergantung bidangnya kasus seperti itu bisa jarang terjadi

  • Pada 2009, saya membuat Bloom filter dengan CUDA di universitas, dan dosen pembimbing saya mantan Nvidia. Namun setelah itu, dalam karier saya sama sekali tidak melakukan pemrograman GPU
    Kalau waktu itu saya mengambil pilihan lain, mungkin saya bisa menghasilkan 100 juta dolar

    • Saya juga mirip. Pada 2009, karena penasaran, saya memakai CUDA v1 di GeForce 8 dan sepertinya membuat salah satu bentuk sangat awal dari toolkit bioinformatika yang dioptimalkan untuk GPU
      Lalu saya pergi mengerjakan hal lain, dan melewatkan uang besar
    • Mengingat ini adalah ide ilmu komputer dari tahun 1970, kemungkinan itu tampaknya kecil. Ide yang layak dicoba di GPU serbaguna pasti sudah bisa diincar semua orang
      10 tahun lalu saya membuat implementasi hashcash dengan GPU, tetapi sekarang rasanya hampir tidak bernilai
    • Untuk proyek kehormatan sarjana, saya mem-porting algoritma machine learning ke CUDA, lalu hanya mengangkat bahu dan masuk ke pemrograman embedded
    • Kalau saja membeli Bitcoin, mungkin bisa menghasilkan jauh lebih banyak

  • Catatan untuk penulis: bagian interaktifnya sangat bagus. Agar inti idenya lebih jelas, akan baik jika memberi contoh dua string yang mengalami tabrakan hash, lalu meminta salah satunya dimasukkan ke kolom input pertama dan yang lain diperiksa di kolom kedua
    Dengan begitu bisa terlihat mengapa jawabannya selalu “mungkin ada di himpunan”, bukan “ada”

    • "bloom" dan "demonstrators " bertabrakan. Perhatikan karakter spasi di akhir string kedua
      Keduanya bertabrakan pada fnv: 7, murmur: 12

  • Ada satu trik yang saya suka. Jika kadang harus melakukan banyak pemeriksaan keanggotaan pada himpunan yang mungkin kecil, Anda bisa secara spekulatif menambahkan Bloom filter 64-bit dengan fungsi hash yang sangat sederhana
    Terdengar sangat bodoh, tetapi biayanya begitu kecil sehingga layak dicoba seperti taruhan. Jika tidak cocok, kira-kira hanya menambah sekitar 10 ns untuk penyisipan dan pemeriksaan keanggotaan; kalau cocok, bisa memangkas beban kerja yang sangat besar

    • Chromium juga melakukan ini di banyak tempat. Artikel itu hanya menautkan contoh Safe Browsing yang memakai murmur, tetapi renderer Blink biasanya memakai rapidhash dan menggunakan mikro-filter seperti ini di banyak tempat
      Misalnya untuk querySelector() dalam kasus tertentu, pra-penyaringan lookup hash di bucket CSS, dan menolak elemen dengan cepat saat mencari atribut Aria tertentu untuk aksesibilitas. Mengejutkan bahwa filter sangat kecil 32-bit atau 64-bit bisa bekerja, tetapi dalam praktiknya sering efektif. Ada juga beberapa Bloom filter yang lebih besar. Beberapa di antaranya saya yang menambahkan

  • Saya meminta ChatGPT membuatkannya dalam Python, dan memakai cara memotong digest md5 dasar untuk digunakan seperti beberapa hash. Untuk penggunaan yang tidak penting, sepertinya tidak masalah

  • Visualisasi Bloom filter lainnya bisa dilihat di akhir halaman ini:
    https://www.chrislaux.com/hashtable.html

  • Saya kira pernah melihatnya sebelumnya, tetapi ternyata yang saya lihat adalah halaman lain ini: https://bdupras.github.io/filter-tutorial/
    Halaman ini membandingkan Bloom filter dan cuckoo filter, jadi informasinya sedikit lebih lengkap

  • Baru-baru ini saya mengimplementasikan fitur pencegahan spam pesan log dengan Bloom filter. Di logger, pesan di-hash lalu dimasukkan ke filter, dan jika itemnya ada, pesan tidak dicetak
    Setiap beberapa detik saya menelusuri filter dan menghapus semua bitnya, dan ini cocok karena tidak perlu memikirkan masalah menghapus semua bit filter secara atomik. Kalau saat pesan masuk sebagian bitnya saja terhapus, itu sudah cukup untuk membuatnya tercatat lagi di log. Implementasi sebelumnya menghitung jumlah pesan yang pernah dilihat lalu jenuh pada N, dan jika pesan tertentu dicetak berulang, efeknya pesan itu hanya terlihat pada laju di bawah kecepatan filter dihapus
    Cukup memuaskan karena saya tadinya hanya tahu Bloom filter, lalu secara alami menemukan penggunaan nyata seperti ini dan membuat peningkatan besar

  • Jika ingin membaca lebih lanjut, tulisan Eli Bendersky tentang Bloom filter juga bagus:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Konsep yang diperlukan untuk memahami Bloom filter, himpunan, dan hash table terasa sekitar 95% tumpang tindih. Himpunan adalah hash table untuk pemeriksaan keanggotaan yang hanya peduli pada kunci, bukan nilai, dan Bloom filter adalah himpunan yang memanfaatkan fakta bahwa hashing banyak-ke-satu “memampatkan” ruang kunci lewat tabrakan
    Dengan kata lain, ini seperti memakai fungsi hash yang sengaja menghasilkan banyak tabrakan. Jika kunci tertentu pernah di-hash sekali, hasilnya pasti cocok, tetapi mungkin ada kunci lain yang menghasilkan hash yang sama. Itu bukan bug, melainkan fitur

    • Senang rasanya mengetahui bukan hanya saya yang memahami Bloom filter sebagai hash table yang tidak melacak data sebenarnya, melainkan hanya bucket yang berisi data
    • Poin penting yang hilang dari penjelasan ini adalah Bloom filter memakai beberapa fungsi hash untuk mengurangi tabrakan. Misalnya jika ada 3 hash, agar suatu kunci dianggap ada di himpunan, ketiga hash tersebut harus cocok semuanya
      Ini mengurangi kemungkinan tabrakan positif palsu sambil tetap mempertahankan jaminan tidak ada negatif palsu
    • Jika Anda benar-benar memahami Bloom filter, Anda hampir sampai untuk memahami proyeksi acak dan sebagian implementasi locality-sensitive hashing