Bloom Filter’ı örneklerle anlamak

 (llimllib.github.io)
2 puan yazan GN⁺ 2025-07-01 | 1 yorum | WhatsApp'ta paylaş
  • Bloom filter, büyük kümelerde üyelik durumunu az bellekle hızlıca elemek için kullanılan bir veri yapısıdır; yalnızca “kesinlikle yok” ve “olabilir” ayrımını yapar
  • Temelinde bit vektörü ve birden fazla hash fonksiyonu vardır; ekleme sırasında hash sonuçlarının işaret ettiği konumlardaki bitler 1 yapılır
  • Sorgulamada aynı konumlar kontrol edilir; bunlardan biri bile 0 ise eleme yapılabilir, ancak hepsi 1 olsa bile false positive olasılığı kalır
  • Hash fonksiyonları bağımsız, uniform dağılıma yakın ve hızlı olmalıdır; md5’ten murmur’a geçilerek yaklaşık %800 hız artışı elde edilen bir örnek vardır
  • Filtrenin doğruluğu ve maliyeti, beklenen öğe sayısı n, bit sayısı m, hash sayısı k arasındaki dengeye bağlıdır; ekleme ve sorgulama işlemleri de O(k) düzeyindedir

Bloom Filter’ın çalışma biçimi

  • Bloom filter, bir öğenin kümeye dahil olup olmadığını hızlı ve bellek açısından verimli şekilde belirleyen olasılıksal bir veri yapısıdır
  • Sonuç iki durumla sınırlıdır
    • Öğe kümede kesinlikle yoktur
    • Öğe kümede olabilir
  • İç yapısı bir bit vektörüdür; öğe eklenirken giriş birden fazla hash fonksiyonundan geçirilir
  • Her hash değerinin işaret ettiği bit indeksini 1 yapmak ekleme işlemini tamamlar
  • Örnekte Fnv ve Murmur basit hash fonksiyonları olarak kullanılır

Üyelik kontrolü ve false positive

  • Sorgulama da ekleme sırasında kullanılan aynı hash fonksiyonlarını kullanır
  • Hash değerlerinin işaret ettiği bitlerden biri bile 0 ise ilgili öğe kesinlikle kümede yoktur
  • İlgili bitlerin hepsi 1 ise ilgili öğe kümede olabilir
    • Aynı bitler daha önce başka bir öğe ya da birden fazla öğenin birleşik etkisiyle zaten ayarlanmış olabilir
  • Bu çakışma nedeniyle Bloom filter’da false positive olasılığı vardır

Hash fonksiyonu seçme kriterleri

  • Bloom filter için hash fonksiyonları bağımsız olmalı, uniform dağılıma yakın olmalı ve mümkün olduğunca hızlı çalışmalıdır
  • sha1 gibi kriptografik hash’ler yaygın kullanılır, ancak Bloom filter için her zaman iyi bir seçim olmayabilir
  • Hızlı ve basit hash örnekleri şunlardır
  • Bir Bloom filter uygulamasında md5 yerine murmur kullanıldıktan sonra yaklaşık %800 hız artışı sağlayan bir örnek vardır

Gerçek uygulamalarda kullanılan hash’ler

  • Farklı implementasyonlar Bloom filter için farklı hash fonksiyonları kullanır

Filtre boyutu ve hash fonksiyonu sayısını belirleme

  • Bloom filter’da false positive oranı ayarlanabilir
    • Daha büyük filtre false positive oranını azaltır
    • Daha küçük filtre false positive oranını artırır
  • False positive oranı yaklaşık olarak (1-e^-kn/m)^k ile hesaplanır
    • n: ekleneceği öngörülen öğe sayısı
    • m: filtredeki bit sayısı
    • k: hash fonksiyonu sayısı
  • Hash fonksiyonları arttıkça sorgulama ve ekleme yavaşlar, filtre de daha hızlı dolar
  • Tersine, hash fonksiyonu sayısı çok azsa false positive oranı aşırı yüksilebilir
  • Verilen m ve n için optimal k, (m/n)ln(2) olarak seçilebilir
  • Filtre boyutu şu sırayla ayarlanabilir
    • Tahmini n değerini kabaca belirleyin
    • m değerini seçin
    • Optimal k değerini hesaplayın
    • Seçilen n, m, k ile hata oranını hesaplayın
    • Hata oranı kabul edilemezse m değerini değiştirip yeniden hesaplayın

Performans ve uygun kullanım koşulları

  • m bit ve k hash fonksiyonuna sahip bir Bloom filter’da hem ekleme hem üyelik kontrolü O(k)’dir
  • Öğe eklerken veya sorgularken öğeyi k hash fonksiyonundan geçirip ilgili bitleri ayarlamak ya da kontrol etmek yeterlidir
  • Alan verimliliği, kabul edilebilir hata oranına göre değişir
  • Eklenebilecek öğe aralığı çok sınırlıysa deterministik bir bit vektörü daha iyi olabilir
  • Eklenecek öğe sayısı kabaca bile tahmin edilemiyorsa hash tablosu veya scalable Bloom filter daha uygun olabilir

Referanslar ve kullanım örnekleri

İlgili okumalar

1 yorum

 
GN⁺ 2025-07-01
Hacker News yorumları

  • Bu yazı tam da benim gibi insanları hedefliyor. Bloom filtresi adını duymuştum; her bahsi geçtiğinde bakmam gerektiğini düşünüp duruyordum. Bu yazıyı görünce sonunda baktım ve istediğim giriş yazısı olarak mükemmeldi :)

    • 10 yıldan da önce iBooks arama özelliği için uygulamam istenen bir işle Bloom filtresini öğrenmiştim
    • Gerçekten eğlenceli bir yapı. Bloom filtresine ihtiyaç duyan bir problem ortaya çıkınca heyecanlanıyorum; ama ne yazık ki alana göre böyle durumlar nadir olabiliyor

  • 2009'da üniversitede CUDA ile Bloom filtresi yapmıştım; danışman hocam da eski Nvidia çalışanıydı. Ama sonrasında kariyerimde hiç GPU programlama yapmadım
    O zaman farklı bir seçim yapsaydım belki 100 milyon dolar kazanabilirdim

    • Ben de benzer durumdayım. 2009'da meraktan GeForce 8 üzerinde CUDA v1 kullanarak GPU için optimize edilmiş biyoinformatik araç takımının çok erken bir biçimini yapmıştım sanırım
      Sonra başka işlere gittim ve büyük parayı kaçırdım
    • 1970'te ortaya çıkmış bir bilgisayar bilimi fikri olduğunu düşününce bu pek olası görünmüyor. Genel amaçlı GPU'larda denenmeye değer fikirler zaten herkesin radarına girebilirdi
      10 yıl önce GPU ile bir hashcash uygulaması yapmıştım; şimdi neredeyse değersiz olurdu herhalde
    • Lisans onur projemde bir makine öğrenmesi algoritmasını CUDA'ya port ettikten sonra omuz silkip gömülü programlamaya geçtim
    • Bitcoin alsaydın çok daha fazlasını kazanabilirdin

  • Yazara not: Etkileşimli kısım gerçekten güzel. Ana fikri daha net göstermek için hash çakışması yaşayan iki string örneği verip, birini ilk giriş kutusuna koydurup diğerini ikinci kutuda kontrol ettirmek iyi olurdu
    Böylece cevabın neden her zaman “kümede olabilir” olduğu, “var” olmadığı gösterilebilir

    • "bloom" ile "demonstrators " çakışıyor. İkinci string'in sonundaki boşluk karakterine dikkat etmek gerekiyor
      İkisi de fnv: 7, murmur: 12 değerlerinde çakışıyor

  • Sevdiğim bir numara var. Bazen küçük olma ihtimali olan bir kümede çok sayıda üyelik kontrolü yapmak gerekiyorsa, 64 bit Bloom filtresini çok basit bir hash fonksiyonuyla birlikte spekülatif olarak ekleyebilirsiniz
    Kulağa aşırı aptalca geliyor ama maliyeti o kadar düşük ki bir kumar gibi denemeye değer. İyi tutmazsa ekleme ve üyelik kontrolüne kabaca 10 ns ekler; iyi tutarsa muazzam miktarda işi azaltabilir

    • Chromium da bunu birçok yerde yapıyor. Yazıda yalnızca Safe Browsing'in murmur kullandığı örnek linklenmiş, ama render motoru Blink genelde rapidhash kullanıyor ve bu mikro filtreleri birçok yerde kullanıyor
      Örneğin belirli durumlarda querySelector(), CSS bucket'larında hash araması için ön filtreleme ve erişilebilirlik için belirli Aria nitelikleri aranırken öğeleri hızlıca elemekte kullanılıyor. 32 bit ya da 64 bitlik küçücük filtrelerin işe yaraması şaşırtıcı, ama pratikte sık sık etkili oluyor. Bazı daha büyük Bloom filtreleri de var. Bunlardan birkaçını ben ekledim

  • ChatGPT'den Python'da bir tane yapmasını istedim; temel olarak md5 digest'ini kesip birkaç hash gibi kullanma yöntemini kullandı. Kritik olmayan işler için iyi olur gibi

  • Bloom filtresinin başka bir görselleştirmesi bu sayfanın sonunda görülebilir:
    https://www.chrislaux.com/hashtable.html

  • Daha önce gördüğümü sanmıştım, ama aslında şu diğer sayfaymış: https://bdupras.github.io/filter-tutorial/
    Bu sayfa Bloom filtresi ile cuckoo filtresini karşılaştırdığı için biraz daha fazla bilgi içeriyor

  • Yakın zamanda Bloom filtresiyle log mesajı spam'ini önleme işlevi uyguladım. Logger'da mesajı hash'leyip filtreye koyuyor, öğe varsa mesajı yazdırmıyordum
    Birkaç saniyede bir filtrenin üzerinden geçip tüm bitleri temizliyordum; filtrenin tüm bitlerini atomik olarak temizleme meselesiyle uğraşmam gerekmediği için iyi uydu. Mesajlar gelirken bu bitlerden yalnızca bir kısmının temizlenmesi bile yeniden log'a düşmesi için yeterliydi. Önceki uygulama görülen mesaj sayısını sayıp N'de doygunluğa ulaşıyordu; belirli bir mesaj tekrar tekrar yazdırılırsa, filtrenin temizlenme hızının altında görünüyor gibi bir etki yaratıyordu
    Bloom filtresini sadece biliyorken bu kadar doğal bir gerçek kullanım alanı bulup büyük bir iyileştirme yapmak oldukça tatmin ediciydi

  • Daha fazla okumak isterseniz Eli Bendersky'nin Bloom filtresi yazısı da güzeldi:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Bloom filtrelerini, kümeleri ve hash tablolarını anlamak için gereken kavramlar hissiyatıma göre yaklaşık %95 örtüşüyor. Küme, değerlerle değil yalnızca anahtarlarla ilgilenen üyelik kontrolü için kullanılan bir hash tablosu; Bloom filtresi ise çoktan bire hash'lemenin çakışmalar yoluyla anahtar uzayını “sıkıştırdığı” gerçeğinden yararlanan bir küme
    Bilerek çok çakışma üreten bir hash fonksiyonu kullanmak gibi. Belirli bir anahtar bir kez bile hash'lendiyse sonuç mutlaka doğru çıkar; ama aynı hash'i üretmiş başka bir anahtar da olabilir. Bu bir hata değil, özellik

    • Bloom filtresini, gerçek veriyi izlemeyip yalnızca verinin bulunduğu bucket'ları izleyen bir hash tablosu olarak anlayan tek kişi olmadığımı görmek sevindirici
    • Bu açıklamada eksik kalan kilit nokta, Bloom filtresinin çakışmaları azaltmak için birden çok hash fonksiyonu kullanması. Örneğin 3 hash varsa, bir anahtarın kümede olduğuna karar vermek için üç hash'in de eşleşmesi gerekir
      Bu, yanlış pozitif çakışma olasılığını azaltırken yanlış negatif olmaması garantisini korur
    • Bloom filtresini düzgün anladıysanız, rastgele izdüşüm ve locality-sensitive hashing'in bazı uygulamalarını anlamaya da neredeyse varmışsınız demektir