Фільтр Блума: як дізнатися, чи є елемент у множині

4. 10. 2022

Фільтр Блума (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, кожен ID має довжину 36, тобто за добу потрібно зберегти щонайменше 31 ГБ. Це трохи забагато. Чи не можна зменшити вимоги до пам'яті?

Фільтр Блума

Замість того щоб зберігати весь 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]<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;
}

Метод 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

Наступна: Блог »