Bloom filter: Phần tử có thuộc tập hợp không?

Bloom filter (bộ lọc Bloom) là một cấu trúc dữ liệu xác suất cho phép trả lời, với một mức xác suất nhất định, câu hỏi phần tử x có thuộc tập hợp M hay không.

Chẳng hạn, hệ thống của ta cần đo số lần người dùng nhấp vào một banner quảng cáo. Sau mỗi lần nhấp, ta nhận được một yêu cầu HTTP GET báo rằng người dùng XYZ đã nhấp vào quảng cáo 123. Đôi khi người dùng lỡ nhấp đúp chuột, và ta nhận được hai yêu cầu. Ta muốn lọc bỏ các yêu cầu trùng này và chỉ ghi vào cơ sở dữ liệu một lần nhấp.

Vì vậy ta cần một ứng dụng đọc kênh tin nhắn về các lần nhấp và lọc bỏ các bản trùng. Làm thế nào? Mỗi tin nhắn có một ID, nên không cần so sánh toàn bộ tin nhắn, chỉ cần kiểm tra xem trước đây ta đã xử lí tin nhắn có cùng ID hay chưa. Một đoạn mã JavaScript đơn giản loại bỏ các bản trùng khỏi luồng tin nhắn (ở đây cho đơn giản là một mảng) có thể như sau:

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

// In ra: { id: "123" } { id: "456" } { id: "789" }

Cách này dùng được cho đến khi hết bộ nhớ – mà sớm muộn gì cũng hết, vì tập hợp processedIds theo thời gian chỉ có tăng lên. Tất nhiên có thể lập trình thêm việc xoá dữ liệu hết hạn – chẳng hạn luôn xoá các tin nhắn cũ hơn 1 giờ hoặc tương tự.

Tệ hơn là khi ngay cả như vậy cũng không đủ. Nếu tập hợp processedIds phải chứa dữ liệu của ít nhất 1 ngày và ta xử lí, chẳng hạn, 10.000 tin nhắn mỗi giây thì sao? Trong trường hợp xấu nhất, ta cần lưu đến 864.000.000 mã. Nếu dùng uuid v4, mỗi ID có độ dài 36, nghĩa là mỗi ngày ta cần lưu ít nhất 31 GB. Hơi nhiều. Có thể giảm lượng bộ nhớ cần dùng không?

Bloom filter

Thay vì lưu toàn bộ ID, ta có thể chỉ lưu giá trị băm của nó. Có thể dùng hàm murmurhash quen thuộc, trả về một số nguyên 32 bit cho mỗi xâu và có phân bố tốt:

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

// In ra: { id: "123" } { id: "456" } { id: "789" }

Tiếp theo ta dùng mẹo với vectơ bit. Đó là một mảng chỉ lưu các số 0 và 1. Với hàm băm n bit, ta cần một vectơ kích thước 2ⁿ để đánh địa chỉ được mọi đầu ra có thể có của hàm băm. Ý tưởng là ban đầu vectơ chứa toàn số 0. Nếu với đầu vào "123" hàm băm trả về số 47, ta chỉ việc ghi số 1 vào vectơ tại chỉ số 47. Như vậy ta đánh dấu rằng giá trị băm 47 đã gặp.

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

// In ra: { id: "123" } { id: "456" } { id: "789" }

Đoạn mã % numberOfValues chỉ cắt bớt murmurhash để được một hàm băm n bit, không gì hơn. Và đây chính là Bloom filter, dù là một phiên bản rất suy biến. Vấn đề của cách làm này dĩ nhiên là xung đột, điều chắc chắn sẽ xảy ra. Các giá trị đầu vào khác nhau có thể có cùng giá trị băm. Để giảm xác suất xảy ra xung đột, ta không dùng một hàm băm mà dùng nhiều hàm băm. Có thể tạo nhiều hàm băm, chẳng hạn, bằng cách thêm một “muối” (salt) vào giá trị đầu vào. Một hàm đơn giản tạo ra các hàm băm n bit khác nhau có thể như sau:

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

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

Lớp biểu diễn Bloom filter có thể viết như sau:

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

Phương thức add thêm một phần tử vào Bloom filter: tính giá trị băm bằng mọi hàm băm và ghi true vào các chỉ số tương ứng.
Phương thức contains kiểm tra xem phần tử đã cho có thuộc Bloom filter hay không.

Dùng Bloom filter rất dễ:

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

// In ra: { id: "123" } { id: "456" } { id: "789" }

Đó là toàn bộ “phép màu” của Bloom filter cơ bản. Nó có các tính chất cơ bản sau:

Nếu phương thức contains trả lời rằng phần tử đã cho không có trong Bloom filter, thì đúng là bạn chưa bao giờ thêm phần tử đó vào.
Nếu phương thức trả lời rằng phần tử đã cho có trong Bloom filter, thì không nhất thiết bạn đã thực sự thêm phần tử đó vào – vì có thể đã xảy ra xung đột của các hàm băm.
Nói chung, muốn giảm xác suất trả lời sai, hãy tăng số hàm băm hoặc tăng kích thước của chúng (tức là kích thước của giá trị đầu ra).
Dùng càng nhiều hàm băm, Bloom filter càng chậm.
Dùng hàm băm càng lớn, Bloom filter càng chiếm nhiều bộ nhớ.
Một khi đã thêm một phần tử vào Bloom filter, không thể xoá phần tử đó.

« Bài trước: HyperLogLog: Cách ước lượng thật chính xác số giá trị phân biệt

Bài tiếp: Mật mã Caesar »