✖

Φίλτρο Bloom: ανήκει το στοιχείο στο σύνολο;

Το φίλτρο Bloom είναι μια πιθανοτική δομή που μας επιτρέπει να πούμε με κάποιο βαθμό πιθανότητας αν ένα στοιχείο x ανήκει σε ένα σύνολο M.

Στο σύστημά μας για παράδειγμα χρειάζεται να μετράμε πόσες φορές οι χρήστες έκαναν κλικ σε ένα διαφημιστικό banner. Μετά από κάθε κλικ φτάνει σε εμάς ένα αίτημα 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);
    }
});

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

Αυτή η λύση θα αρκεί μέχρι να τελειώσει η μνήμη – και κάποτε θα τελειώσει, επειδή το σύνολο processedIds με τον καιρό θα μεγαλώνει μόνο και μόνο. Μπορούμε φυσικά να προγραμματίσουμε και κάποια λήξη των δεδομένων – μπορούμε να αφαιρούμε πάντα τα μηνύματα παλαιότερα από μία ώρα ή κάτι παρόμοιο.

Χειρότερο είναι όταν ούτε αυτό αρκεί. Τι γίνεται αν χρειαζόμαστε στο σύνολο processedIds δεδομένα τουλάχιστον μίας ημέρας και επεξεργαζόμαστε ας πούμε δέκα χιλιάδες μηνύματα το δευτερόλεπτο; Στη χειρότερη περίπτωση χρειάζεται να αποθηκεύσουμε έως και 864.000.000 αναγνωριστικά. Αν χρησιμοποιούμε uuid v4, κάθε ID έχει μήκος 36, που σημαίνει ότι σε μία ημέρα χρειάζεται να αποθηκεύσουμε τουλάχιστον 31 GB. Αυτό είναι λίγο πολύ. Δεν θα μπορούσαμε να μειώσουμε την απαίτηση σε μνήμη;

Φίλτρο Bloom

Αντί να αποθηκεύουμε ολόκληρο το ID, μπορούμε να αποθηκεύουμε μόνο το hash του. Μπορούμε να χρησιμοποιήσουμε την κλασική murmurhash, που επιστρέφει για κάθε string έναν ακέραιο αριθμό 32 bit και επιπλέον έχει καλή κατανομή:

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

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

Στη συνέχεια θα χρησιμοποιήσουμε το κόλπο του πίνακα bit. Αυτός είναι ένας πίνακας στον οποίο θα αποθηκεύουμε μόνο μηδενικά και άσους. Αν έχουμε συνάρτηση κατακερματισμού n bit, χρειαζόμαστε πίνακα μεγέθους 2n, ώστε να μπορούμε να διευθυνσιοδοτούμε στον πίνακα όλες τις πιθανές εξόδους της συνάρτησης κατακερματισμού. Η ιδέα είναι ότι στην αρχή ο πίνακας περιέχει μόνο μηδενικά. Αν η συνάρτηση κατακερματισμού για την είσοδο "123" μας επιστρέψει τον αριθμό 47, απλώς βάζουμε στον πίνακα στη θέση 47 έναν άσο. Έτσι σημειώνουμε ότι το 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);
    }
});

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

Με τον κώδικα % numberOfValues απλώς περικόψαμε τη murmurhash ώστε να γίνει συνάρτηση κατακερματισμού n bit, τίποτε παραπάνω. Και αυτό είναι ένα φίλτρο Bloom. Έστω και μια πολύ εκφυλισμένη έκδοσή του. Πρόβλημα αυτής της προσέγγισης είναι φυσικά οι συγκρούσεις, που αναγκαστικά θα συμβούν. Διαφορετικές τιμές εισόδου μπορούν να έχουν το ίδιο hash εξόδου. Για να μειώσουμε λοιπόν την πιθανότητα σύγκρουσης, δεν θα χρησιμοποιήσουμε μόνο μία συνάρτηση κατακερματισμού, αλλά περισσότερες. Περισσότερες συναρτήσεις κατακερματισμού μπορούμε να δημιουργήσουμε για παράδειγμα προσθέτοντας στην τιμή εισόδου κάποιο αλάτι (salt). Μια απλή συνάρτηση που θα δημιουργούσε διαφορετικές συναρτήσεις κατακερματισμού n bit θα μπορούσε να μοιάζει έτσι:

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, "someSalt");
var secondHashFunction = createNBitHashFunction(8, "someOtherSalt");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

Την κλάση που αναπαριστά ένα φίλτρο Bloom μπορούμε να τη γράψουμε έτσι:

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 προσθέτει ένα στοιχείο στο φίλτρο Bloom: υπολογίζει το hash με όλες τις συναρτήσεις κατακερματισμού και στον αντίστοιχο δείκτη αποθηκεύει true.
  • Η μέθοδος contains διαπιστώνει αν το δοσμένο στοιχείο περιέχεται στο φίλτρο Bloom.

Το φίλτρο Bloom μπορούμε να το χρησιμοποιήσουμε εύκολα:

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

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

Και αυτή είναι όλη η μαγεία του βασικού φίλτρου Bloom. Έχει τις εξής βασικές ιδιότητες:

  • Αν η μέθοδος contains απαντήσει ότι το δοσμένο στοιχείο δεν υπάρχει στο φίλτρο Bloom, σημαίνει ότι πράγματι δεν το έχεις βάλει ποτέ σε αυτό.
  • Αν η μέθοδος απαντήσει ότι το δοσμένο στοιχείο υπάρχει στο φίλτρο Bloom, δεν σημαίνει απαραίτητα ότι πράγματι το έχεις αποθηκεύσει – μπορεί να έγινε σύγκρουση των συναρτήσεων κατακερματισμού.
  • Γενικά ισχύει ότι, αν θέλεις να μειώσεις την πιθανότητα λανθασμένης απάντησης, αύξησε το πλήθος των συναρτήσεων κατακερματισμού ή αύξησε το μέγεθός τους (εννοείται το μέγεθος της τιμής εξόδου).
  • Όσο περισσότερες συναρτήσεις κατακερματισμού χρησιμοποιείς, τόσο πιο αργό θα είναι το φίλτρο Bloom.
  • Όσο μεγαλύτερες συναρτήσεις κατακερματισμού χρησιμοποιείς, τόσο περισσότερο χώρο θα καταλαμβάνει το φίλτρο Bloom.
  • Αν κάποτε βάλεις ένα στοιχείο στο φίλτρο Bloom, δεν είναι πλέον δυνατό να το αφαιρέσεις.