✖

Filter Bloom: apakah suatu elemen ada dalam himpunan?

Filter Bloom adalah struktur probabilistik yang memungkinkan kita menyatakan, dengan tingkat peluang tertentu, apakah suatu elemen x ada dalam himpunan M.

Misalnya, dalam sistem kita, kita perlu mengukur berapa kali pengguna mengeklik suatu banner iklan. Setelah setiap klik, kita menerima permintaan HTTP GET yang memberi tahu bahwa pengguna XYZ mengeklik iklan 123. Kadang-kadang pengguna tidak sengaja mengeklik dua kali, sehingga kita menerima dua permintaan. Kita ingin menyaring permintaan seperti ini dan mencatatnya di basis data sebagai satu klik.

Karena itu, kita memerlukan aplikasi yang membaca saluran pesan tentang klik dan menyaring duplikatnya. Bagaimana caranya? Setiap pesan memiliki ID, jadi kita tidak perlu membandingkan seluruh pesan; kita cukup memeriksa apakah pesan dengan ID yang sama pernah kita proses. Kode JavaScript sederhana yang menghapus duplikat dari aliran (stream) pesan (di sini, supaya sederhana, dari larik) bisa seperti ini:

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

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

Solusi ini cukup sampai memori kita habis — dan suatu saat memori pasti habis, karena himpunan processedIds hanya akan terus bertambah besar. Tentu saja kita bisa menambahkan semacam kedaluwarsa data — misalnya selalu menghapus pesan yang berumur lebih dari satu jam, atau semacamnya.

Lebih buruk lagi jika cara itu pun tidak cukup. Bagaimana jika himpunan processedIds harus memuat data setidaknya untuk satu hari dan kita memproses, misalnya, sepuluh ribu pesan per detik? Dalam kasus terburuk, kita perlu menyimpan hingga 864.000.000 ID. Jika kita memakai uuid v4, setiap ID memiliki panjang 36, artinya per hari kita perlu menyimpan setidaknya 31 GB. Itu agak terlalu banyak. Dapatkah kebutuhan memori ini dikurangi?

Filter Bloom

Alih-alih menyimpan seluruh ID, kita dapat menyimpan nilai hash-nya saja. Kita dapat memakai murmurhash yang klasik, yang untuk setiap string mengembalikan bilangan bulat 32-bit dan sebarannya juga baik:

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

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

Selanjutnya, kita pakai trik dengan larik bit (bit vector), yaitu larik yang hanya diisi angka nol dan satu. Jika kita memiliki fungsi hash n-bit, kita memerlukan larik berukuran 2n agar semua output yang mungkin dari fungsi hash dapat dialamatkan dalam larik. Idenya, pada awalnya larik hanya berisi nol. Jika kemudian fungsi hash untuk input "123" mengembalikan bilangan 47, kita cukup menuliskan angka satu ke larik pada indeks 47. Dengan begitu, kita menandai bahwa nilai hash 47 sudah pernah kita lihat.

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

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

Dengan kode % numberOfValues, kita hanya memotong murmurhash menjadi fungsi hash n-bit, tidak lebih. Dan inilah filter Bloom, meskipun versinya sangat sederhana. Masalah cara ini tentu saja tabrakan (collision), yang pasti terjadi. Nilai input yang berbeda dapat memiliki nilai hash output yang sama. Karena itu, untuk memperkecil peluang terjadinya tabrakan, kita tidak hanya memakai satu fungsi hash, tetapi beberapa. Beberapa fungsi hash dapat dibuat, misalnya, dengan menambahkan salt ke nilai input. Fungsi sederhana yang membuat berbagai fungsi hash n-bit bisa seperti ini:

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

Kelas yang merepresentasikan filter Bloom dapat ditulis sebagai berikut:

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;
}
  • Metode add menambahkan elemen ke filter Bloom: metode ini menghitung nilai hash dengan semua fungsi hash dan menyimpan true pada indeks yang bersesuaian.
  • Metode contains memeriksa apakah elemen tertentu termuat dalam filter Bloom.

Filter Bloom mudah digunakan:

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

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

Itulah seluruh keajaiban filter Bloom dasar. Sifat-sifat dasarnya sebagai berikut:

  • Jika metode contains menjawab bahwa elemen tertentu tidak ada dalam filter Bloom, artinya kamu memang belum pernah memasukkan elemen tersebut.
  • Jika metode tersebut menjawab bahwa elemen tertentu ada dalam filter Bloom, belum tentu kamu benar-benar pernah memasukkan elemen tersebut — bisa saja terjadi tabrakan fungsi hash.
  • Secara umum, jika ingin memperkecil peluang jawaban yang salah, tambahlah banyaknya fungsi hash atau perbesar ukurannya (yang dimaksud adalah ukuran nilai output).
  • Makin banyak fungsi hash yang kamu gunakan, makin lambat filter Bloom.
  • Makin besar fungsi hash yang kamu gunakan, makin banyak ruang yang dipakai filter Bloom.
  • Elemen yang sudah dimasukkan ke filter Bloom tidak dapat dihapus lagi.