مرشح بلوم: هل ينتمي العنصر إلى المجموعة؟
مرشح بلوم (Bloom filter) بنية احتمالية تمكّننا من أن نقول، باحتمال معيّن، هل ينتمي عنصر ما x إلى المجموعة M.
لنفرض مثلاً أننا نحتاج في نظامنا إلى قياس عدد المرات التي نقر فيها المستخدمون على شريط إعلاني. بعد كل نقرة يصلنا طلب HTTP GET يخبرنا بأنّ المستخدم XYZ نقر على الإعلان 123. ويحدث أحياناً أن ينقر المستخدم بالفأرة نقرة مزدوجة عن غير قصد، فيصلنا طلبان. ونريد أن نرشّح هذه الطلبات ونسجّلها في قاعدة البيانات نقرة واحدة.
نحتاج إذن إلى تطبيق يقرأ قناة الرسائل الخاصة بالنقرات ويحذف التكرارات. فكيف نفعل ذلك؟ لكل رسالة معرّف 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، فطول كل معرّف 36 محرفاً، أي أننا نحتاج إلى تخزين 31 GB على الأقل في اليوم. وهذا كثير بعض الشيء. فهل يمكن تقليل متطلبات الذاكرة؟
فكرة مرشح بلوم
بدلاً من أن نخزّن المعرّف كله، يمكننا أن نخزّن قيمة تجزئته (hash) فقط. ويمكننا أن نستعمل دالة 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 بت، احتجنا إلى متجه حجمه 2n لكي نستطيع أن نعنون في المتجه كل المخرجات الممكنة لدالة التجزئة. والفكرة أنّ المتجه يحتوي في البداية على أصفار فقط. فإذا أعادت دالة التجزئة للمدخل "123" العدد 47، وضعنا ببساطة في المتجه الرقم 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بأنّ العنصر المعطى ليس في مرشح بلوم، فهذا يعني أنّ هذا العنصر لم يُدخَل إليه فعلاً أبداً. - إذا أجابت الطريقة بأنّ العنصر المعطى موجود في مرشح بلوم، فلا يعني ذلك بالضرورة أنه خُزّن فيه فعلاً، فقد يكون حدث تصادم بين دوال التجزئة.
- عموماً، لتقليل احتمال الإجابة الخاطئة نزيد عدد دوال التجزئة أو نزيد حجمها (أي حجم قيمة المخرجات).
- كلما زاد عدد دوال التجزئة المستعملة، صار مرشح بلوم أبطأ.
- كلما كبرت دوال التجزئة المستعملة، زادت المساحة التي يشغلها مرشح بلوم.
- إذا أُدخل عنصر إلى مرشح بلوم مرة، فلا يمكن حذفه بعد ذلك.