Memahami Bloom Filter lewat Contoh

• Bloom filter adalah struktur data probabilistik yang efisien memori untuk memeriksa dengan cepat apakah suatu elemen ada di dalam himpunan
• Struktur ini hanya memberi tahu apakah elemen pasti tidak ada, atau mungkin ada di dalam himpunan, dan memiliki kemungkinan false positive
• Struktur dasarnya menggunakan vektor bit dan beberapa fungsi hash untuk mengatur bit yang sesuai dengan tiap elemen menjadi 1
• Tingkat kesalahan dan performa ditentukan oleh ukuran filter dan jumlah fungsi hash, sehingga bisa disesuaikan dengan kebutuhan penggunaan
• Juga diperkenalkan fungsi hash yang direkomendasikan serta cara menentukan konfigurasi optimal, efisiensi ruang, dan contoh penerapan nyata

---

Apa itu Bloom Filter

• Bloom filter adalah struktur data untuk menentukan dengan cepat dan efisien memori apakah suatu elemen ada di dalam himpunan tertentu
• Demi efisiensi ini, Bloom filter merupakan struktur data probabilistik, sehingga hasil pemeriksaannya terbagi menjadi "pasti tidak ada di dalam himpunan" atau "mungkin ada di dalam himpunan"
• Struktur inti Bloom filter adalah vektor bit
• Saat menambahkan elemen, setiap elemen di-hash beberapa kali lalu bit pada indeks tersebut diatur menjadi 1
• Jika bit pada indeks yang dihasilkan oleh tiap fungsi hash semuanya bernilai 1, maka elemen dinilai "mungkin ada"; jika tidak, maka diproses sebagai "pasti tidak ada"

Contoh prinsip kerja

• Beberapa fungsi hash (misalnya Fnv, Murmur) digunakan untuk memetakan elemen ke beberapa indeks bit
• Saat elemen ditambahkan, bit pada indeks yang dihitung diubah menjadi 1
• Saat memeriksa apakah elemen tertentu ada, jika semua indeks yang dihasilkan dengan fungsi hash yang sama dan cara yang sama bernilai 1, maka elemen dianggap "mungkin ada"
• Jika ada satu saja bit terkait yang bernilai 0, maka bisa dipastikan elemen itu "tidak ada di dalam himpunan"
• Karena itu, muncul kemungkinan false positive

Topik lanjutan

Perhatian: penulis sebenarnya tidak memiliki pengalaman menerapkan Bloom filter pada layanan berskala besar

Pemilihan fungsi hash

• Fungsi hash yang independen dan memiliki distribusi merata direkomendasikan
• Fungsi hash kriptografis (seperti sha1) tidak cocok karena lambat
• Contoh fungsi hash yang cepat dan sederhana: Murmur, xxHash, Fnv, HashMix, dan lain-lain
• Dalam kasus nyata, mengganti md5 ke murmur menghasilkan peningkatan kecepatan lebih dari 800%

Menentukan ukuran Bloom filter

• Semakin besar ukuran filter (m), semakin rendah tingkat false positive
• Tingkat false positive umumnya dapat didekati dengan (1-e^(-kn/m))^k
• Jumlah elemen yang diharapkan (n), ukuran filter (m), dan jumlah fungsi hash (k) harus ditentukan dengan tepat

Berapa jumlah fungsi hash?

• Semakin banyak fungsi hash, semakin lambat kecepatannya dan filter akan lebih cepat penuh
• Jika terlalu sedikit, tingkat false positive menjadi tinggi
• Nilai k yang ideal dihitung dengan (m/n)ln(2)
• Saat merancang, lakukan prosedur berikut:
  • memperkirakan jumlah elemen yang diharapkan n
  • menentukan jumlah bit m
  • menghitung k yang optimal
  • memeriksa apakah tingkat kesalahan yang diinginkan tercapai; jika tidak, sesuaikan m

Performa dan efisiensi ruang

• Pada Bloom filter, penambahan elemen/pemeriksaan keberadaan memiliki kompleksitas waktu O(k)
• Efisiensi ruang ditentukan oleh batas toleransi tingkat kesalahan dan rentang elemen
• Jika rentang elemen bahkan secara kasar pun tidak bisa diprediksi, hash table atau scalable Bloom filter mungkin lebih baik

Contoh penggunaan

• Untuk contoh penggunaan yang lebih rinci, lihat Wikipedia
• C. Titus Brown menunjukkan contoh penerapan Bloom filter dalam bioinformatika

Referensi

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — makalah gambaran umum Bloom filter
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida dkk.: Scalable Bloom Filters

[GN⁺]

Komentar Hacker News

• Tulisan ini terasa sangat pas untuk orang seperti saya. Pernah dengar namanya, tapi setiap kali mau mencari tahu selalu ditunda terus. Kali ini setelah membaca tulisannya, akhirnya saya benar-benar mencarinya, dan rasanya persis seperti pengantar yang saya inginkan
  • Saya pertama kali mengenal Bloom filter saat mengimplementasikan fitur pencarian di iBooks. Itu sudah lebih dari 10 tahun yang lalu
  • Bloom filter memang sangat menarik. Saat menyelesaikan masalah dan tiba waktunya membutuhkan Bloom filter, rasanya benar-benar seru, tapi sayangnya situasi seperti itu tidak sering muncul tergantung domainnya
• Satu usulan untuk penulis. Bagian interaktifnya sangat memuaskan. Untuk membantu memahami sifat Bloom filter dengan lebih baik, akan bagus jika diberi contoh dua string yang menimbulkan hash collision, lalu pengguna diminta memasukkan salah satunya dan memasukkan yang lain ke kotak input kedua. Dengan begitu, akan lebih mudah memahami mengapa muncul logika hasil khas seperti "tidak pasti ada di dalam himpunan, tapi mungkin ada (maybe)"
  • Sebagai contoh, "bloom" dan "demonstrators " (termasuk spasi terakhir) bertabrakan pada fnv: 7, murmur: 12
• Saat kuliah pada 2009, saya pernah mengimplementasikan Bloom filter dengan CUDA. Dosen pembimbing saya dulunya bekerja di Nvidia. Tapi dalam karier saya, jalurnya sama sekali tidak berhubungan dengan pemrograman GPU. Kadang terpikir, kalau saya memilih jalan lain, mungkin saya bisa menghasilkan 100 juta dolar
  • Karena ini ide ilmu komputer yang sudah muncul pada 1970, mungkin itu memang mustahil. Rasanya ide-ide terkait GPGPU sudah cukup banyak diteliti. Saya juga pernah mengimplementasikan Hashcash di GPU 10 tahun lalu, dan kalau dilihat sekarang nilainya nyaris nol
  • Setelah mem-porting algoritme machine learning ke CUDA untuk proyek kelulusan, saya malah berpikir itu bukan hal besar lalu beralih ke pemrograman embedded
  • Saya juga punya pengalaman serupa. Pada 2009, dengan GeForce 8 dan CUDA v1(!), saya mungkin membuat toolkit bioinformatika yang dioptimalkan untuk GPU untuk pertama kalinya. Awalnya hanya karena penasaran, lalu setelah itu saya sepenuhnya menempuh jalan yang berbeda dan kehilangan kesempatan menghasilkan banyak uang
  • Candaan bahwa kalau saja dulu membeli Bitcoin, uang yang didapat pasti lebih besar
• Ada trik yang saya suka. Untuk set kecil yang jumlah elemennya mungkin sedikit tetapi sering diperiksa keanggotaannya, saya menyisipkan Bloom filter 64-bit dengan fungsi hash yang sangat sederhana. Kedengarannya bodoh, tetapi biayanya sangat rendah sehingga bisa dipakai seperti berjudi. Kalau tidak cocok, paling hanya menambah sekitar 10ns pada membership check atau insert, tapi kalau cocok, beban kerja yang dikurangi bisa sangat besar
  • Chromium juga memakai trik seperti ini di berbagai tempat. Tulisan itu hanya menyebut Safe Browsing, tetapi di layer Blink mereka aktif memakai rapidhash dan mikro-filter semacam ini. Contohnya pada querySelector(), prefilter kamus lookup hash di bucket CSS, dan rapid reject saat menelusuri atribut Aria untuk aksesibilitas. Filter kecil 32-bit dan 64-bit juga benar-benar bekerja dengan baik. Bloom filter yang lebih besar juga dipakai secara tepat, dan saya sendiri pernah menambahkan fitur seperti ini secara langsung
• Baru-baru ini saya memakai Bloom filter untuk fitur anti-spam pada pesan log. Pesan log di-hash lalu dimasukkan ke filter, dan jika sudah ada di filter maka tidak dicetak. Secara berkala, semua bit di filter dibersihkan. Tidak perlu menghapus seluruh bit secara atomik; meskipun beberapa bit terhapus saat pesan masuk, akibatnya pesan itu hanya akan tercetak lagi. Sebelumnya saya menyimpan penghitung terpisah untuk tiap pesan, tetapi cara ini jauh lebih efisien. Saya cukup puas karena benar-benar menerapkan Bloom filter sendiri untuk penggunaan ini
• Sebagai contoh visualisasi Bloom filter, ada materi bagus di bagian akhir halaman ini
• Saya juga merekomendasikan tulisan pengantar Bloom filter lain oleh Eli Bendersky. Kalau ingin lebih mendalam, lihat di sini
• Menurut saya, sekitar 95% konsep yang dibutuhkan untuk memahami Bloom filter, set, dan hash table itu saling tumpang tindih. Set adalah hash table yang hanya peduli pada key, sedangkan Bloom filter adalah set yang secara aktif memanfaatkan sifat collision dari hashing. Ia memakai fungsi hash yang sengaja dibuat agar collision mudah terjadi. Jika key tertentu pernah dimasukkan, hasilnya pasti cocok. Tetapi bisa saja ada key lain yang menghasilkan nilai hash yang sama. Jadi ini bukan bug, melainkan sifat yang memang disengaja
  • Saya juga cenderung memikirkan Bloom filter seperti hash table yang membuang datanya sendiri dan hanya melacak bucket-nya. Senang rasanya mengetahui saya bukan satu-satunya yang punya pola pikir seperti ini
  • Akan bagus jika ditambahkan penjelasan bahwa Bloom filter memakai beberapa fungsi hash untuk mengurangi collision. Misalnya, baru dianggap ada di dalam set jika ketiga fungsi hash itu semuanya cocok. Berkat struktur ini, probabilitas false positive bisa diturunkan sementara false negative sama sekali tidak akan muncul
  • Kalau sudah memahami Bloom filter, biasanya tidak lama lagi Anda juga bisa memahami random projection atau beberapa implementasi dari Locality Sensitive Hashes
• Saat men-debug lonjakan read di Cassandra, saya pernah benar-benar mendalami Bloom filter. Terasa aneh karena terlalu banyak lookup sstable untuk key yang sebenarnya tidak ada. Saya belakangan baru benar-benar memahami arti Bloom filter yang melekat pada tiap sstable. Rasio false positive bawaan 0.1 terlalu tinggi untuk situasi kami. Sebagian besar adalah cache miss, dan karena false positive, terlalu banyak lookup yang sia-sia. Setelah rasio diturunkan menjadi 0.01, penggunaan memori memang sedikit naik, tetapi read yang tidak perlu berkurang drastis sehingga p99 read latency turun 16~18%
• Saya benar-benar suka Bloom filter. Saat membahas teknologi, tiga konsep inti yang selalu saya perkenalkan adalah Bloom filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing), dan Cumulative flow diagram. Menurut saya, ketiga konsep ini sangat penting untuk mengoperasikan sistem terdistribusi yang kompleks
  • Menurut saya, struktur distributed hash table juga topik yang sama pentingnya. Misalnya arsitektur seperti circle, chord, CAN, kademlia, dan lain-lain