✖

ตัวกรองของบลูม: สมาชิกอยู่ในเซตหรือไม่

ตัวกรองของบลูม (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 GB ซึ่งค่อนข้างมาก จะลดหน่วยความจำที่ใช้ได้หรือไม่

ตัวกรองของบลูม

แทนที่จะเก็บ ID ทั้งตัว จะเก็บเพียงค่าแฮชของ 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" }

ต่อไปใช้เทคนิคเวกเตอร์บิต ซึ่งคืออาร์เรย์ที่เก็บเพียงเลข 0 และ 1 ถ้ามีฟังก์ชันแฮช n บิต ต้องใช้เวกเตอร์ขนาด 2n เพื่อให้อ้างถึงผลลัพธ์ที่เป็นไปได้ทุกค่าของฟังก์ชันแฮชในเวกเตอร์ได้ แนวคิดคือ ตอนเริ่มต้นเวกเตอร์เป็นศูนย์ทั้งหมด ถ้าฟังก์ชันแฮชคืนจำนวน 47 สำหรับข้อมูลขาเข้า "123" ก็เพียงใส่เลข 1 ลงในเวกเตอร์ที่ดัชนี 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 บิต ไม่มีอะไรมากกว่านั้น และนี่คือตัวกรองของบลูม แม้จะเป็นรุ่นที่ลดรูปมากก็ตาม ปัญหาของวิธีนี้ย่อมเป็นการชน ซึ่งต้องเกิดขึ้นแน่นอน ค่าขาเข้าที่ต่างกันอาจมีค่าแฮชผลลัพธ์เดียวกัน เพื่อลดความน่าจะเป็นที่จะเกิดการชน จึงไม่ใช้ฟังก์ชันแฮชเพียงฟังก์ชันเดียว แต่ใช้หลายฟังก์ชัน การสร้างฟังก์ชันแฮชหลายฟังก์ชันทำได้ เช่น โดยเติมซอลต์ (salt) เข้าไปในค่าขาเข้า ฟังก์ชันง่าย ๆ ที่สร้างฟังก์ชันแฮช 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 ตอบว่าสมาชิกที่กำหนดไม่อยู่ในตัวกรองของบลูม แสดงว่าไม่เคยใส่สมาชิกนั้นเข้าไปจริง ๆ
  • ถ้าเมท็อดตอบว่าสมาชิกที่กำหนดอยู่ในตัวกรองของบลูม ไม่จำเป็นต้องหมายความว่าเคยเก็บสมาชิกนั้นไว้จริง เพราะอาจเกิดการชนของฟังก์ชันแฮช
  • โดยทั่วไป ถ้าต้องการลดความน่าจะเป็นที่จะได้คำตอบผิด ให้เพิ่มจำนวนฟังก์ชันแฮช หรือเพิ่มขนาดของฟังก์ชันแฮช (หมายถึงขนาดของค่าผลลัพธ์)
  • ยิ่งใช้ฟังก์ชันแฮชมาก ตัวกรองของบลูมก็ยิ่งทำงานช้า
  • ยิ่งใช้ฟังก์ชันแฮชขนาดใหญ่ ตัวกรองของบลูมก็ยิ่งใช้พื้นที่มาก
  • เมื่อใส่สมาชิกลงในตัวกรองของบลูมแล้ว จะลบออกไม่ได้อีก