✖

Bloomin suodatin: onko alkio joukossa?

Bloomin suodatin on todennäköisyyspohjainen rakenne, jonka avulla voimme tietyllä todennäköisyydellä sanoa, onko jokin alkio x joukossa M.

Järjestelmässämme meidän täytyy esimerkiksi mitata, kuinka monta kertaa käyttäjät ovat napsauttaneet mainosbanneria. Jokaisen napsautuksen jälkeen meille tulee HTTP GET -pyyntö, joka kertoo, että käyttäjä XYZ napsautti mainosta 123. Joskus käy niin, että käyttäjä kaksoisnapsauttaa hiirellä vahingossa ja meille tulee siksi kaksi pyyntöä. Haluaisimme suodattaa nämä pyynnöt pois ja saada ne tietokantaan kirjattua yhtenä napsautuksena.

Tarvitsemme siis sovelluksen, joka lukee napsautusviestien kanavaa ja suodattaa pois kaksoiskappaleet. Miten tekisimme sen? Jokaisella tällaisella viestillä on jokin tunniste (ID), joten meidän ei tarvitse verrata koko viestiä, riittää selvittää, olemmeko jo joskus käsitelleet viestiä, jolla on sama tunniste. Yksinkertainen JavaScript-koodi, joka poistaisi kaksoiskappaleet viestien virrasta (tässä yksinkertaisuuden vuoksi taulukosta), voisi näyttää tältä:

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);
    }
});

// Tulostaa: { id: "123" } { id: "456" } { id: "789" }

Tämä ratkaisu riittää siihen asti, kunnes muisti loppuu — ja se loppuu aikansa kuluttua, koska joukko processedIds vain kasvaa ajan mittaan. Voimme tietenkin ohjelmoida lisäksi jonkin datan vanhenemisen — voimme aina poistaa tuntia vanhemmat viestit tai jotakin sen tapaista.

Pahempaa on, jos sekään ei riitä. Entä jos joukossa processedIds täytyy olla datan vähintään yhdeltä päivältä ja käymme läpi vaikkapa kymmenentuhatta viestiä sekunnissa? Pahimmassa tapauksessa täytyy tallentaa jopa 864 000 000 tunnistetta. Jos käytämme uuid v4:ää, jokaisen tunnisteen pituus on 36, mikä tarkoittaa, että päivässä täytyy tallentaa vähintään 31 GB. Se on vähän liikaa. Eikö muistivaatimusta voisi pienentää?

Bloomin suodatin

Sen sijaan, että tallentaisimme koko tunnisteen, voimme tallentaa vain sen tiivisteen. Voimme käyttää perinteistä murmurhashia, joka palauttaa jokaiselle merkkijonolle 32-bittisen kokonaisluvun ja jolla on lisäksi hyvä jakauma:

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);
    }
});

// Tulostaa: { id: "123" } { id: "456" } { id: "789" }

Seuraavaksi käytämme bittivektorin kikkaa. Se on taulukko, johon tallennamme vain nollia ja ykkösiä. Jos meillä on n-bittinen tiivistefunktio, tarvitsemme vektorin, jonka koko on 2n, jotta pystymme osoittamaan vektorista kaikki tiivistefunktion mahdolliset tulosteet. Ajatus on, että alussa vektori sisältää pelkkiä nollia. Jos tiivistefunktio sitten palauttaa syötteelle "123" luvun 47, yksinkertaisesti lisäämme vektoriin indeksiin 47 ykkösen. Merkitsemme näin, että olemme jo nähneet tiivisteen, jonka arvo on 47.

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);
    }
});

// Tulostaa: { id: "123" } { id: "456" } { id: "789" }

Koodilla % numberOfValues vain leikkasimme murmurhashin niin, että siitä tuli n-bittinen tiivistefunktio, ei muuta. Ja tämä on Bloomin suodatin. Tosin hyvin alkeellinen versio. Tämän lähestymistavan ongelmana ovat luonnollisesti törmäykset, joita väistämättä syntyy. Eri syötearvoilla voi olla sama tulostiiviste. Jotta pienentäisimme törmäyksen todennäköisyyttä, emme käytä vain yhtä tiivistefunktiota, vaan useampia. Useita tiivistefunktioita voi luoda esimerkiksi lisäämällä syötearvoon jonkin suolan. Yksinkertainen funktio, joka loisi erilaisia n-bittisiä tiivistefunktioita, voisi näyttää tältä:

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, "jokinSuola");
var secondHashFunction = createNBitHashFunction(8, "jokinToinenSuola");

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

Bloomin suodatinta esittävän luokan voi kirjoittaa näin:

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;
}
  • Metodi add lisää alkion Bloomin suodattimeen: se laskee tiivisteen kaikilla tiivistefunktioilla ja tallentaa vastaavaan indeksiin arvon true.
  • Metodi contains selvittää, onko annettu alkio Bloomin suodattimessa.

Bloomin suodatinta voi käyttää helposti:

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);
    }
});

// Tulostaa: { id: "123" } { id: "456" } { id: "789" }

Ja siinä on peruskäyttöisen Bloomin suodattimen koko taika. Sillä on nämä perusominaisuudet:

  • Jos metodi contains vastaa, ettei annettu alkio ole Bloomin suodattimessa, se tarkoittaa, ettet ole todella koskaan lisännyt kyseistä alkiota siihen.
  • Jos metodi vastaa, että annettu alkio on Bloomin suodattimessa, se ei välttämättä tarkoita, että olet todella tallentanut kyseisen alkion siihen — tiivistefunktioiden törmäys on voinut syntyä.
  • Yleisesti pätee, että jos haluat pienentää väärän vastauksen todennäköisyyttä, lisää tiivistefunktioiden lukumäärää tai suurenna niiden kokoa (tarkoitetaan tulosarvon kokoa).
  • Mitä useampia tiivistefunktioita käytät, sitä hitaampi Bloomin suodatin on.
  • Mitä suurempia tiivistefunktioita käytät, sitä enemmän tilaa Bloomin suodatin vie.
  • Kun olet kerran lisännyt alkion Bloomin suodattimeen, sitä ei voi enää poistaa.