Bloom Filter Nedir? Ne İşe Yarar? Nerelerde Kullanılır?
Bloom filtreleri bir elemanın akan bir verisetinde(data stream) geçip geçmediğini tespit edebilen bir yaklaşımı tariflemektedir. Bloom filtresini daha iyi anlayabilmek için problemi detaylıca irdeleyelim. “Bir akan veri içerisinde, verilen bir değer geçiyor mu ?” probleminin birden fazla çözümü vardır.
Örneğin; Bir akan veride ahmet, mehmet, ali, veli, ayşe, fatma, hayriye … şeklinde verilerin sırayla geldiğini düşünelim. Ve bu verisetinde muhittin isminin geçip geçmediğini araştırıyor olalım.
Yaklaşım 1: Dictionary Kullanmak
Bu yaklaşımda bir dictionary(HashMap vb.) kullanarak gelen her farklı değer öncelikle dictionary’de bulunup bulunmadığına bakıllır. Eğer gelen değer daha önce geçtiyse dictonary içinde bulunmaktadır. Aksi takdirde sorgulanan değer akan veri kümesinde daha önce hiç geçmemiştir. Dictionary benzeri veri yapıları da arka planda Hash algoritmaları kullandığı için tek bir hash operasyonuyla problem çözülebilir. Yani işlem karmaşıklığı açısından O(1) karmaşıklıkta çözülebilecek basit bir problem olarak düşünülebilir.
Ancak aranan bir verinin, akan veride geçip geçmeme problemi saniyede birkaç milyon olayın işlendiği ve yoğun yük altında çalışan bir uygulamada uygulanmaya çalışılırsa karşılacağımız senaryo ne olur? Muhtemelen bellek sarfiyatımız oldukça artacak ve belki de programımız bellek yetersizliği sebebiyle işletim sistemi tarafından sonsuzluğa uğurlanacaktır.
Yaklaşım 2: Bloom Filtresi Kullanmak
Bloom filtresi çalışma dinamiği açısından birden fazla hash değerinin sonuçlarını bitler halinde kaydeden bir bit array’dir. Bloom filtrelerinden faydalanarak bir değerin çok büyük veri setlerinde geçip geçmediğini bulabiliriz. Temelinde bloom filteleri olasılıksal bir veri yapısı olarak tariflenebilir. Olasılıksal bir yapı olması itibariyle deterministik çalışmadığı durumlar oluyor. Şöyle ki;
Eğer bloom filtresi bir değer geçiyor şeklinde sonuç veriyorsa değer geçebilir de geçmeyebilir de.
Ancak bloom filtresi bir değer geçmiyor diyorsa o değer kesinlikle verisetinde geçmemektedir.
Bloom Filter Çalışma Mekanizması
Problemi ve olası çözüm yöntemlerini tanımladıktan sonra gelelim bloom filter’ın çalışma mantığına. Bloom filter’ı derinlemesine anlamak için öncelikle hashing kavramına hakim olmak gerekir. Kısaca tanımlamak gerekirse hash işlemi bir verinin keyfi büyüklükteki bir dizideki karşılığı (özeti) olarak tanımlanabilir.
ADIM 1: Filtreyi Oluştur
Bloom filtre oluşturmanın ilk adımı olarak N tane eleman içeren ve elemanlarının değerleri başlangıçta 0 olan bir dizi tanımlanır.ADIM 2: Hash Fonksiyonlarını Oluştur
M adet ayrı bir hash fonksiyonu oluşturulur.ADIM 3: Büyük Veriseti İle Filtreyi Oluştur.
Akan verideki her eleman M tane hash değerinden geçirilir. Hash değerlerinin her birinin N’e göre modu alınır ve çıkan indis değerinde bulunan eleman 1 olarak set edilir.ADIM4: İstenilen Değeri Sorgula
Sorgulanmak istenen beri de M tane hash algoritmasından geçirilir ve N’e göre mod alınarak indisler bulunur. Bulunan indislerdeki değerlerden bir tanesi bile 0 ise sorgulanan değer kesinlikle verisetinde geçmiyor demektir.
Dikkat Edilmesi Gerkenler
Bloom filtresinin işe yaradığı örnekler büyük veride olasılıksal tahminlemeye dayalıdır. Dolayısıyla kesin bulunup bulunmadığını garanti etmez, yani false positive cevap dönebilir. Ancak aranan bir değerin bulunmadığını garanti eder.
Olası Kullanım Senaryoları
Bloom filtresini kullanabileceğiniz örneklerden biri cache (önbellek) mekanizmaları olabilir. Çünkü gelen verinin daha önce önbellekte bulunmadığını garanti etmeniz gerekli. Bu durumda bloom filtresi kullanmak işlemlerinizi hızlandıracaktır. Öte yandan blacklist/whitelist engelleme yaptığınız uygulamalarda eğer kural setiniz çok büyük ise bloom filtresi kullanmak bellekten tasarruf etmenize olanak tanıyacaktır.
Kaynaklar
Daha derinlemesine araştırmak ve örnek kodları incelemek isterseniz aşağıdaki bağlantıları ziyaret etmenizi tavsiye ederim.
