Филтър на Блум: намира ли се елементът в множеството?

Филтърът на Блум (Bloom filter) е вероятностна структура, която ни позволява с известна степен на вероятност да кажем дали някакъв елемент x се намира в множеството M.

В нашата система например трябва да мерим колко пъти потребителите са кликнали върху рекламен банер. След всяко кликване при нас идва HTTP GET заявка, която ни информира, че потребителят XYZ е кликнал върху рекламата 123. Понякога се случва потребителят по погрешка да кликне двукратно с мишката и така при нас да дойдат две заявки. Ние бихме искали да филтрираме тези заявки и да ги имаме записани в базата данни като едно кликване.

Затова ни трябва приложение, което ще чете канала със съобщения за кликванията и ще филтрира дубликатите. Как бихме го направили? Всяко такова съобщение има някакво ID, не е нужно да сравняваме цялото съобщение, достатъчно е да установим дали вече не сме обработвали съобщение със същото ID. Прост код на JavaScript, който би премахвал дубликатите от поток (тук за простота от масив) от съобщения, би могъл да изглежда така:

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

// Отпечатва: { id: "123" } { id: "456" } { id: "789" }

Това решение ще стига, докато не ни свърши паметта — а тя един ден ще свърши, защото множеството processedIds с времето само и единствено ще расте. Разбира се, можем да добавим в програмата изтичане на срока на данните — например винаги да премахваме съобщения, по-стари от един час, или нещо подобно.

По-лошо е, когато и това не стига. Какво ще стане, ако трябва да имаме в множеството processedIds данни най-малко за един ден и обработваме например десет хиляди съобщения в секунда? В най-лошия случай трябва да запазим до 864 000 000 идентификатора. Ако използваме uuid v4, всеки идентификатор има дължина 36, което означава, че за един ден трябва да запазим най-малко 31 GB. Това е малко много. Не би ли могло да се намали това изискване към паметта?

Филтър на Блум

Вместо да запазваме цялото ID, можем да запазваме само неговия хеш. Можем да използваме класическия murmurhash, който за всеки низ връща 32-битово цяло число и освен това има добро разпределение:

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

// Отпечатва: { id: "123" } { id: "456" } { id: "789" }

След това ще използваме трика с битовия вектор. Това е масив, в който ще запазваме само нули и единици. Ако имаме n-битова хеш функция, ни трябва вектор с големина 2ⁿ, за да можем във вектора да адресираме всички възможни изходи на хеш функцията. Идеята е в началото векторът да съдържа само нули. Ако след това хеш функцията за входа "123" ни върне числото 47, просто във вектора на индекс 47 слагаме единица. Така отбелязваме, че хеш със стойност 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);
    }
});

// Отпечатва: { id: "123" } { id: "456" } { id: "789" }

С кода % numberOfValues само отрязахме murmurhash така, че да стане n-битова хеш функция, нищо повече. И това е филтър на Блум. Макар и доста изродена версия. Проблемът на този подход, разбира се, са колизиите, които непременно ще настъпят. Различни входни стойности могат да имат един и същ изходен хеш. За да намалим затова вероятността да настъпи колизия, няма да използваме само една хеш функция, а няколко. Няколко хеш функции можем да създадем например като към входната стойност добавим някаква сол. Проста функция, която би създавала различни n-битови хеш функции, би могла да изглежда така:

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

Класа, който представя филтър на Блум, можем да напишем така:

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 добавя елемент във филтъра на Блум: пресмята хеша с всички хеш функции и на съответния индекс запазва true.
Методът contains след това установява дали даденият елемент се съдържа във филтъра на Блум.

Филтърът на Блум можем да използваме лесно:

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

// Отпечатва: { id: "123" } { id: "456" } { id: "789" }

И това е цялата магия на основния филтър на Блум. Той има тези основни свойства:

Ако методът contains отговори, че даденият елемент не е във филтъра на Блум, това означава, че наистина никога не си слагал този елемент в него.
Ако методът отговори, че даденият елемент присъства във филтъра на Блум, това не означава непременно, че наистина си запазил този елемент в него — можеше да е настъпила колизия на хеш функциите.
По принцип, ако искаш да намалиш вероятността от неправилен отговор, увеличи броя на хеш функциите или увеличи тяхната големина (имам предвид големината на изходната стойност).
Колкото повече хеш функции използваш, толкова по-бавен ще е филтърът на Блум.
Колкото по-големи хеш функции използваш, толкова повече място ще заема филтърът на Блум.
Ако веднъж сложиш някакъв елемент във филтъра на Блум, не е възможно да го премахнеш.

« Предишна: HyperLogLog: как да оценим много точно броя на уникалните стойности

Следваща: Цезаров шифър »