Bloom Filter’ı Örneklerle Anlamak

• Bloom filter, bir küme içindeki bir öğenin varlığını hızlıca kontrol etmek için kullanılan, bellek açısından verimli bir olasılıksal veri yapısıdır
• Bir öğenin kümede kesin olarak bulunmadığını ya da belki bulunabileceğini söyler; yanlış pozitif olasılığı vardır
• Temel yapı, bit vektörü ile birden fazla hash fonksiyonu kullanarak her öğeye karşılık gelen bitleri 1 yapar
• Hata oranı ve performans, filtrenin boyutu ile hash fonksiyonu sayısına göre belirlenir ve kullanım amacına göre ayarlanabilir
• Önerilen hash fonksiyonları, en uygun ayar yöntemi, alan verimliliği ve gerçek kullanım örnekleri de tanıtılır

---

Bloom Filter Nedir

• Bloom filter, belirli bir öğenin bir kümede bulunup bulunmadığını hızlı ve bellek açısından verimli şekilde belirleyen bir veri yapısıdır
• Bu verimlilik için bloom filter olasılıksal bir veri yapısıdır; sorgu sonucu ya "kümede kesinlikle yok" ya da "kümede olabilir" şeklinde ayrılır
• Bloom filter’ın temel yapısı bit vektörüdür
• Öğe eklenirken her öğe birden fazla kez hash edilerek ilgili indekslerdeki bitler 1 yapılır
• Her hash fonksiyonundan çıkan indekse karşılık gelen bitlerin tümü 1 ise "bulunabilir" olarak değerlendirilir; aksi halde "kesinlikle yok" kabul edilir

Çalışma Prensibi Örneği

• Birden fazla hash fonksiyonu (ör. Fnv, Murmur) üzerinden öğeler birden çok bit indeksine eşlenir
• Öğe eklenirken hesaplanan indekslerdeki bitler 1’e çevrilir
• Belirli bir öğenin varlığı kontrol edilirken, aynı hash fonksiyonlarıyla üretilen indekslerin hepsi 1 ise "bulunabilir" kabul edilir
• Eğer bu bitlerden biri bile 0 ise "kümede yok" olduğu kesin olarak anlaşılır
• Bu nedenle false positive (yanlış pozitif) olasılığı ortaya çıkar

İleri Konular

Not: Yazarın bloom filter’ı gerçek büyük ölçekli bir serviste uygulamış deneyimi yoktur

Hash fonksiyonu seçimi

• Bağımsız ve uniform dağılıma sahip hash fonksiyonları önerilir
• Kriptografik hash fonksiyonları (sha1 vb.) yavaş olduğu için uygun değildir
• Hızlı ve basit hash fonksiyonlarına örnek olarak Murmur, xxHash, Fnv, HashMix verilebilir
• Gerçek bir örnekte md5’ten murmur’a geçildiğinde %800’ün üzerinde hız artışı yaşanmıştır

Bloom filter boyutunu belirleme

• Filtre boyutu (m) büyüdükçe yanlış pozitif oranı azalır
• Yanlış pozitif oranı genellikle (1-e^(-kn/m))^k ile yaklaşık hesaplanabilir
• Beklenen öğe sayısı (n), filtre boyutu (m) ve hash fonksiyonu sayısı (k) uygun şekilde belirlenmelidir

Hash fonksiyonu sayısı kaç olmalı?

• Hash fonksiyonu sayısı arttıkça hız düşer ve filtre daha hızlı dolar
• Çok az olursa yanlış pozitif oranı yükselir
• İdeal k değeri (m/n)ln(2) ile hesaplanır
• Tasarım sırasında şu adımlar izlenir:
  • Beklenen öğe sayısı n tahmin edilir
  • Bit sayısı m belirlenir
  • En uygun k hesaplanır
  • İstenen hata oranının çıkıp çıkmadığı kontrol edilir; çıkmıyorsa m ayarlanır

Performans ve alan verimliliği

• Bloom filter’da öğe ekleme/varlık kontrolü O(k) zaman karmaşıklığına sahiptir
• Alan verimliliği, kabul edilen hata oranı ile öğe aralığına göre belirlenir
• Öğe aralığı kabaca da olsa öngörülemiyorsa hash tablosu ya da ölçeklenebilir bloom filter daha iyi olabilir

Kullanım örnekleri

• Ayrıntılı kullanım örnekleri için Wikipedia incelenebilir
• C. Titus Brown, bloom filter’ın biyoinformatikteki kullanım örneklerini sunar

Referanslar

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — bloom filter’a genel bakış sunan bir makale
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida ve diğerleri: Scalable Bloom Filters

[GN⁺]

Hacker News görüşü

• Bu yazı tam da benim gibi insanlar içinmiş gibi hissettirdi. Adını duymuştum ama her seferinde bakmayı ertelemiştim. Bu yazıyı görünce sonunda inceledim ve tam istediğim gibi bir giriş yazısı olduğunu düşündüm
  • Bloom filter’ı ilk kez iBooks’un arama özelliğinin nasıl uygulandığını incelerken öğrenmiştim. Üzerinden 10 yıldan fazla geçmiş bile
  • Bloom filter gerçekten çok eğlenceli. Bir problemi çözerken Bloom filter’a ihtiyaç duyulan bir an gelirse insan gerçekten heyecanlanıyor, ama alana göre böyle durumlar çok sık çıkmadığı için biraz üzücü
• Yazara bir önerim var. İnteraktif kısım çok başarılı. Bloom filter’ın özelliklerini daha iyi anlatmak için, iki dizgenin hash çakışması oluşturduğu bir örnek verip birini girdirtmek, ardından diğerini ikinci giriş alanına yazdırmak iyi olabilir. Böylece neden kendine özgü olarak "kümenin içinde olduğu kesin değil ama muhtemelen var (maybe)" sonucunu verdiği daha kolay anlaşılır
  • Örnek olarak bloom ile demonstrators (sonunda boşluk var) fnv: 7, murmur: 12 değerlerinde çakışıyor
• 2009’da üniversitedeyken CUDA ile Bloom filter uygulamıştım. Danışman hocam eski bir Nvidia çalışanıydı. Ama kariyerimde GPU programlamayla hiç ilgisi olmayan bir yola girdim. Başka bir seçim yapsaydım belki 100 milyon dolar kazanabilirdim diye düşünüyorum
  • Bunun 1970’ten kalma bir bilgisayar bilimi fikri olması nedeniyle bunun pek mümkün olmayacağını düşünüyorum. GPGPU ile ilgili fikirler zaten yeterince çalışılmış gibiydi. Ben de 10 yıl önce GPU ile Hashcash uygulamıştım ama bugün bakınca değeri neredeyse sıfır
  • Üniversite bitirme projesi olarak bir makine öğrenimi algoritmasını CUDA’ya port ettikten sonra, bunu çok da önemli bir şey saymayıp gömülü programlamaya yöneldim
  • Benim de benzer bir deneyimim oldu. 2009’da GeForce 8 ve CUDA v1(!) ile muhtemelen GPU için optimize edilmiş ilk biyoinformatik araç setini yapmıştım. Sadece meraktan yapıp sonra tamamen başka bir yola gittim ve büyük para kazanma fırsatını kaçırdım
  • Bitcoin alsaydın daha da büyük para kazanabilirdin diye takılanlar da oldu
• Sevdiğim bir numara var. Eleman sayısının az olabileceği ve üyelik kontrolünün sık yapılacağı küçük bir set için, çok basit bir hash fonksiyonuyla birlikte 64 bitlik bir Bloom filter eklemek. Aptalca görünebilir ama maliyeti o kadar düşük ki bir çeşit kumar gibi denenebilir. İşe yaramazsa üyelik kontrolü ya da insert işlemine sadece yaklaşık 10ns ekler; ama tuttuğunda çok büyük miktarda işi ortadan kaldırabilir
  • Chromium da birçok yerde bu numarayı kullanıyor. Yazıda sadece Safe Browsing geçiyor ama Blink katmanında rapidhash ve bu tür mikro filtreler yoğun biçimde kullanılıyor. Örneğin querySelector(), CSS bucket’larında hash lookup için ön filtreleme, erişilebilirlik amacıyla Aria niteliklerini gezerken hızlı red gibi. 32 bit ve 64 bit küçük filtreler pratikte gerçekten işe yarıyor. Daha büyük Bloom filter’lar da uygun yerlerde kullanılıyor; ben de bu tür özellikleri bizzat ekledim
• Kısa süre önce log mesajı anti-spam özelliğinde Bloom filter kullandım. Log mesajlarını hash’leyip filtreye koyuyor, filtrede zaten varsa yazdırmıyordum. Periyodik olarak filtrenin bitlerini tamamen temizliyordum. Tüm bitleri atomik olarak sıfırlamaya gerek yoktu; mesajlar gelirken bazı bitler silinse bile log yeniden yazılırdı. Eskiden her mesaj için ayrı sayaç tutuyordum ama bu yöntem çok daha verimliydi. Bu amaç için Bloom filter’ı bizzat uygulayıp çok memnun kaldım
• Bloom filter görselleştirmesi için bu sayfanın son kısmında iyi bir örnek var
• Eli Bendersky’nin yazdığı başka bir Bloom filter giriş yazısını da tavsiye ederim. Daha ayrıntılı öğrenmek isterseniz buraya bakabilirsiniz
• Bence Bloom filter, set ve hash table’ı anlamak için gereken kavramların neredeyse %95’i ortak. Set, sadece key’lerle ilgilenen bir hash table’dır; Bloom filter ise hashing’in çakışma özelliğini bilinçli şekilde kullanan bir set’tir. Kasıtlı olarak çakışmanın daha kolay olduğu hash fonksiyonları kullanılır. Belirli bir key daha önce eklendiyse sonuç mutlaka tutar. Ama aynı hash değerini üreten başka bir key de olabilir. Yani bu bir bug değil, tasarlanmış bir özelliktir
  • Ben de Bloom filter’ı, hash table’daki verinin kendisini çıkarıp sadece bucket’ları izleyen bir yapı gibi düşünme eğilimindeyim. Bu zihniyete sahip tek kişinin ben olmadığını görmek güzel
  • Bloom filter’ın çakışmaları azaltmak için birden fazla hash fonksiyonu kullanması kısmı da eklenirse iyi olurdu. Örneğin 3 hash fonksiyonunun da eşleşmesi halinde elemanın set içinde olduğuna karar verilir. Bu yapı sayesinde false positive olasılığı düşerken false negative asla oluşmaz
  • Bloom filter’ı anladıysanız, random projection veya Locality Sensitive Hashes’in bazı uygulamalarını da kısa sürede anlayabilirsiniz
• Cassandra’daki read spike sorununu debug ederken Bloom filter’a derinden daldığım bir dönem olmuştu. Var olmayan bir key için bile sstable araması çok fazla yapıldığı için garip geliyordu. Sonradan her sstable’a bağlı Bloom filter’ın ne işe yaradığını tam kavradım. Varsayılan false positive oranı 0.1’di ve bizim durumumuz için fazla yüksekti. İsteklerin çoğu cache miss’ti ve false positive’ler yüzünden anlamsız arama sayısı çok artmıştı. Oranı 0.01’e düşürünce bellek kullanımı biraz arttı ama gereksiz read sayısı ciddi biçimde azaldı; p99 read latency de %16-18 düştü
• Bloom filter’ı gerçekten çok seviyorum. Teknik sohbetlerde mutlaka anlattığım üç temel kavram Bloom filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) ve Cumulative flow diagram. Bu üç kavramın karmaşık dağıtık sistemleri işletmek için vazgeçilmez olduğunu düşünüyorum
  • Dağıtık hash table yapıları da aynı derecede önemli bir konu. Örneğin circle, chord, CAN, kademlia gibi çeşitli mimariler