Filtr Blooma: czy element należy do zbioru?

4. 10. 2022

Filtr Blooma (ang. Bloom filter) to probabilistyczna struktura danych, która pozwala nam z pewnym prawdopodobieństwem powiedzieć, czy jakiś element x należy do zbioru M.

W naszym systemie potrzebujemy na przykład mierzyć, ile razy użytkownicy kliknęli w baner reklamowy. Po każdym kliknięciu przychodzi do nas żądanie HTTP GET, które informuje nas, że użytkownik XYZ kliknął w reklamę 123. Czasem zdarza się, że użytkownik przez pomyłkę kliknie myszą dwukrotnie i przychodzą do nas dwa żądania. Chcielibyśmy takie żądania odfiltrować i mieć je w bazie danych zapisane jako jedno kliknięcie.

Potrzebujemy więc aplikacji, która będzie czytać kanał z wiadomościami o kliknięciach i odfiltrowywać duplikaty. Jak byśmy to zrobili? Każda taka wiadomość ma jakieś ID, nie musimy więc porównywać całej wiadomości, wystarczy nam sprawdzić, czy nie przetworzyliśmy już kiedyś wiadomości z tym samym ID. Prosty kod w JavaScripcie, który usuwałby duplikaty ze strumienia (tu dla uproszczenia z 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);
    }
});

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

To rozwiązanie wystarczy do czasu, aż skończy nam się pamięć — a kiedyś się skończy, bo zbiór processedIds będzie z czasem wyłącznie rósł. Możemy oczywiście dopisać jakieś wygasanie danych — możemy na przykład zawsze usuwać wiadomości starsze niż godzina albo coś podobnego.

Gorzej, kiedy nawet to nie wystarcza. Co jeśli w zbiorze processedIds potrzebujemy mieć dane z co najmniej jednego dnia, a przetwarzamy, powiedzmy, dziesięć tysięcy wiadomości na sekundę? W najgorszym przypadku potrzebujemy zapisać aż 864 000 000 identyfikatorów. Jeśli używamy uuid v4, każde ID ma długość 36, co oznacza, że za jeden dzień musimy zapisać co najmniej 31 GB. To trochę dużo. Czy nie dałoby się zmniejszyć zużycia pamięci?

Filtr Blooma

Zamiast zapisywać całe ID, możemy zapisywać tylko jego hasz. Możemy użyć klasycznej funkcji murmurhash, która dla każdego stringa zwraca 32-bitową liczbę całkowitą i do tego ma dobry rozkład:

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

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

Dalej użyjemy sztuczki z wektorem bitowym. To tablica, do której będziemy zapisywać tylko zera i jedynki. Jeśli mamy n-bitową funkcję haszującą, potrzebujemy wektora o rozmiarze 2ⁿ, żebyśmy byli w stanie zaadresować w wektorze wszystkie możliwe wyniki funkcji haszującej. Idea jest taka, że na początku wektor zawiera same zera. Jeśli potem funkcja haszująca zwróci nam dla wejścia "123" liczbę 47, po prostu wstawimy do wektora pod indeksem 47 jedynkę. W ten sposób zaznaczymy, że hasz o wartości 47 już widzieliśmy.

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

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

Kodem % numberOfValues jedynie przycięliśmy murmurhash tak, żeby powstała z niego n-bitowa funkcja haszująca, nic więcej. I to jest filtr Blooma. Choć w bardzo zdegenerowanej wersji. Problemem tego podejścia są oczywiście kolizje, które nieuchronnie wystąpią. Różne wartości wejściowe mogą mieć ten sam hasz wyjściowy. Żeby więc zmniejszyć prawdopodobieństwo, że dojdzie do kolizji, nie użyjemy tylko jednej funkcji haszującej, ale kilku. Więcej funkcji haszujących możemy utworzyć na przykład tak, że do wartości wejściowej dodamy jakąś sól. Prosta funkcja, która tworzyłaby różne n-bitowe funkcje haszujące, mogłaby wyglądać tak:

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

Klasę reprezentującą filtr Blooma możemy napisać tak:

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

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

Metoda add dodaje element do filtra Blooma: oblicza hasz wszystkimi funkcjami haszującymi i pod odpowiednimi indeksami zapisuje true.
Metoda contains sprawdza potem, czy dany element jest zawarty w filtrze Blooma.

Filtra Blooma możemy łatwo użyć:

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

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

I to cała magia podstawowego filtra Blooma. Ma takie podstawowe własności:

Jeśli metoda contains odpowie, że danego elementu w filtrze Blooma nie ma, oznacza to, że naprawdę nigdy go do niego nie wstawiłeś.
Jeśli metoda odpowie, że dany element w filtrze Blooma jest, nie musi to koniecznie oznaczać, że naprawdę go do niego wstawiłeś — mogła bowiem wystąpić kolizja funkcji haszujących (fałszywie dodatni wynik, ang. false positive).
Ogólnie zachodzi, że jeśli chcesz zmniejszyć prawdopodobieństwo błędnej odpowiedzi, zwiększ liczbę funkcji haszujących albo zwiększ ich rozmiar (chodzi o rozmiar wartości wyjściowej).
Im więcej funkcji haszujących użyjesz, tym wolniejszy będzie filtr Blooma.
Im większych funkcji haszujących użyjesz, tym więcej miejsca będzie filtr Blooma zajmował.
Jeśli jakiś element raz wstawisz do filtra Blooma, nie da się go już usunąć.

« Poprzedni: HyperLogLog

Dalszy: Blog »