✖

Filtr Blooma: czy istnieje element w zbiorze?

Filtr Blooma jest strukturą probabilistyczną, która pozwala nam stwierdzić z pewnym prawdopodobieństwem, czy dany element x znajduje się w zbiorze M.

Na przykład, w naszym systemie musimy zmierzyć, ile razy użytkownicy kliknęli na baner reklamowy. Po każdym kliknięciu otrzymujemy żądanie HTTP GET informujące nas, że użytkownik XYZ kliknął reklamę 123. Czasami użytkownik przypadkowo kliknie dwukrotnie i otrzymamy dwa żądania. Chcielibyśmy odfiltrować te żądania i zapisać je w bazie danych jako jedno kliknięcie.

W związku z tym potrzebujemy aplikacji, która odczyta wiadomość o kliknięciu i odfiltruje duplikaty. Jak to zrobić? Każda taka wiadomość ma identyfikator, więc nie musimy porównywać całej wiadomości, musimy tylko sprawdzić, czy kiedykolwiek przetworzyliśmy wiadomość o tym samym identyfikatorze. Prosty kod JavaScript, który usuwałby duplikaty ze strumienia (tutaj dla uproszczenia tablicy) wiadomości mógłby wyglądać tak:

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

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

To rozwiązanie będzie wystarczające, dopóki nie zabraknie nam pamięci - a kiedyś nam jej zabraknie, ponieważ zbiór przetwarzanych identyfikatorów będzie się tylko powiększał w czasie. Możemy oczywiście zaprogramować wygasanie danych - zawsze możemy usunąć wiadomości starsze niż godzina lub coś podobnego.

Gorzej, gdy nawet to nie wystarczy. Co jeśli musimy mieć co najmniej jeden dzień danych w zestawie processedIds, a przechodzimy przez, powiedzmy, dziesięć tysięcy wiadomości na sekundę? W najgorszym przypadku musimy przechowywać do 864 000 000 Ids. Jeśli używamy uuid v4, każdy identyfikator ma długość 36, co oznacza, że musimy przechowywać co najmniej 32 GB dziennie. To trochę dużo. Czy nie można zmniejszyć zapotrzebowania na pamięć?

Filtr Blooma

Zamiast przechowywać cały identyfikator, możemy przechowywać tylko jego skrót. Możemy użyć klasycznego murmurhash, który zwraca 32-bitową liczbę całkowitą dla każdego ciągu, a ponadto ma dobrą dystrybucję:

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

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

Następnie używamy sztuczki z wektorem bitów. Jest to tablica, w której będziemy przechowywać tylko zera i jedynki. Jeśli mamy n-bitową funkcję haszującą, potrzebujemy wektora o rozmiarze 2n, aby móc zaadresować wszystkie możliwe wyjścia funkcji haszującej w wektorze. Pomysł polega na tym, że wektor początkowo zawiera wszystkie zera. Następnie, jeśli funkcja skrótu zwróci liczbę 47 dla wejścia "123", po prostu umieścimy jedynkę w wektorze w indeksie 47. Będzie to oznaczać, że widzieliśmy już hash 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);
    }
});

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

W kodzie %numberOfValues po prostu przycięliśmy murmurhash, aby uczynić go n-bitową funkcją skrótu, nic więcej. A to jest filtr Blooma. Aczkolwiek bardzo zdegenerowana wersja. Problemem tego podejścia są oczywiście kolizje, które z pewnością wystąpią. Różne wartości wejściowe mogą mieć ten sam hash wyjściowy. Aby więc zmniejszyć prawdopodobieństwo kolizji, nie używamy tylko jednej funkcji skrótu, ale kilku. Na przykład, możemy utworzyć wiele funkcji skrótu, dodając sól do wartości wejściowej. Prosta funkcja tworząca różne n-bitowe funkcje skrótu może wyglądać następująco:

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

Możemy napisać klasę reprezentującą filtr Blooma w następujący sposób:

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]<4>;
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i]<5>;
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}
  • Metoda add dodaje element do filtra Blooma: oblicza hash wszystkich funkcji hashujących i zapisuje wartość true w odpowiednim indeksie.
  • Metoda contains sprawdza następnie, czy element znajduje się w filtrze Blooma.

Możemy łatwo korzystać z filtra Blooma:

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

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

To cała magia podstawowego filtra Blooma. Ma on następujące podstawowe właściwości:

  • Jeśli metoda contains odpowie, że element nie znajduje się w filtrze Blooma, oznacza to, że tak naprawdę nigdy nie umieściłeś elementu w filtrze Blooma.
  • Jeśli metoda odpowie, że element jest obecny w filtrze Blooma, niekoniecznie oznacza to, że umieściłeś element w filtrze Blooma - mogła wystąpić kolizja hash.
  • Ogólnie rzecz biorąc, jeśli chcesz zmniejszyć prawdopodobieństwo nieprawidłowej odpowiedzi, zwiększ liczbę funkcji skrótu lub zwiększ ich rozmiar (czyli rozmiar wartości wyjściowej).
  • Im więcej funkcji skrótu zostanie użytych, tym wolniejszy będzie filtr Blooma.
  • Im więcej funkcji skrótu zostanie użytych, tym więcej miejsca zajmie filtr Blooma.
  • Po wstawieniu elementu do Bloom Filter nie można go usunąć.