Bloom Filtresi: Eleman Kümenin İçinde mi?

Bloom filtresi, bir x elemanının M kümesinde bulunup bulunmadığını belli bir olasılıkla söylememizi sağlayan olasılıksal bir yapıdır.

Örneğin kendi sistemimizde kullanıcıların bir banner reklama kaç kez tıkladığını ölçmemiz gerekiyor. Her tıklamadan sonra bize bir HTTP GET isteği geliyor ve XYZ kullanıcısının 123 numaralı reklama tıkladığını bildiriyor. Bazen kullanıcı yanlışlıkla fareyle çift tıklar ve bize iki istek gelir. Biz bu istekleri filtrelemek, veri tabanına tek bir tıklama olarak kaydetmek isteriz.

Bu yüzden tıklama mesajlarının akışını okuyan ve tekrarları ayıklayan bir uygulamaya ihtiyacımız var. Bunu nasıl yapardık? Her mesajın bir ID’si vardır, dolayısıyla mesajın tamamını karşılaştırmamıza gerek yok; aynı ID’ye sahip bir mesajı daha önce işleyip işlemediğimizi öğrenmemiz yeter. Bir mesaj akışından (burada basitlik için bir diziden) tekrarları çıkaran basit bir JavaScript kodu şöyle görünebilir:

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// Çıktı: { id: "123" } { id: "456" } { id: "789" }

Bu çözüm belleğimiz tükenene kadar işe yarar. Bellek de bir gün tükenecek, çünkü processedIds kümesi zamanla yalnızca büyüyecek. Elbette verilere bir son kullanma süresi de ekleyebiliriz; örneğin bir saatten eski mesajları her zaman silebiliriz.

Bu da yetmediğinde durum daha kötüdür. processedIds kümesinde en az bir günlük veriyi tutmamız gerekiyorsa ve saniyede on bin mesaj işliyorsak ne yaparız? En kötü durumda 864.000.000 ID saklamamız gerekir. uuid v4 kullanıyorsak her ID’nin uzunluğu 36’dır; yani bir günde en az 31 GB saklamamız gerekir. Bu biraz fazla. Bu bellek ihtiyacını azaltamaz mıyız?

Bloom Filtresi

ID’nin tamamını saklamak yerine yalnızca özetini (hash) saklayabiliriz. Her string için 32 bitlik bir tam sayı döndüren ve dağılımı da iyi olan klasik murmurhash fonksiyonunu kullanabiliriz:

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// Çıktı: { id: "123" } { id: "456" } { id: "789" }

Şimdi bit vektörü hilesini kullanacağız. Bu, içine yalnızca sıfırlar ve birler yazacağımız bir dizidir. n bitlik bir özet fonksiyonumuz varsa, özet fonksiyonunun olası tüm çıktılarına vektörde bir yer ayırabilmek için 2ⁿ boyutunda bir vektöre ihtiyacımız olur. Fikir şu: başlangıçta vektör tamamen sıfırlardan oluşur. Özet fonksiyonu "123" girdisi için 47 sayısını döndürürse, vektörde 47 numaralı indekse basitçe bir 1 yazarız. Böylece değeri 47 olan özeti daha önce gördüğümüzü işaretlemiş oluruz.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// Çıktı: { id: "123" } { id: "456" } { id: "789" }

% numberOfValues koduyla murmurhash çıktısını yalnızca kırptık ve onu n bitlik bir özet fonksiyonuna dönüştürdük, başka bir şey yapmadık. İşte Bloom filtresi budur; her ne kadar son derece ilkel bir sürümü olsa da. Bu yaklaşımın sorunu elbette kaçınılmaz olarak ortaya çıkacak çakışmalardır. Farklı girdilerin özeti aynı olabilir. Bu yüzden çakışma olasılığını azaltmak için tek bir özet fonksiyonu yerine birden fazlasını kullanırız. Birden fazla özet fonksiyonunu örneğin girdi değerine bir tuz (salt) ekleyerek elde edebiliriz. Farklı n bitlik özet fonksiyonları üreten basit bir fonksiyon şöyle olabilir:

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "nejakaSul");
var secondHashFunction = createNBitHashFunction(8, "nejakaJinaSul");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

Bloom filtresini temsil eden sınıfı şöyle yazabiliriz:

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}

• add metodu Bloom filtresine bir eleman ekler: tüm özet fonksiyonlarıyla özeti hesaplar ve ilgili indekse true yazar.
• contains metodu ise verilen elemanın Bloom filtresinde bulunup bulunmadığını kontrol eder.

Bloom filtresini kolayca kullanabiliriz:

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// Çıktı: { id: "123" } { id: "456" } { id: "789" }

Temel Bloom filtresinin bütün sihri bundan ibarettir. Başlıca özellikleri şunlardır:

• contains metodu elemanın Bloom filtresinde olmadığını söylüyorsa, o elemanı filtreye gerçekten hiç eklemediğin anlamına gelir.
• Metot elemanın Bloom filtresinde olduğunu söylüyorsa, elemanı gerçekten eklediğin anlamına gelmesi şart değildir; çünkü özet fonksiyonlarında bir çakışma olmuş olabilir.
• Genel olarak, yanlış cevap olasılığını azaltmak istiyorsan özet fonksiyonu sayısını veya özet fonksiyonlarının boyutunu (yani çıktı değerinin boyutunu) artır.
• Ne kadar çok özet fonksiyonu kullanırsan Bloom filtresi o kadar yavaş çalışır.
• Ne kadar büyük özet fonksiyonları kullanırsan Bloom filtresi o kadar çok yer kaplar.
• Bir eleman Bloom filtresine bir kez eklendiyse onu artık çıkarmak mümkün değildir.