ব্লুম ফিল্টার: উপাদানটি কি সেটে আছে?
ব্লুম ফিল্টার (Bloom filter) হলো একটি সম্ভাবনাভিত্তিক ডেটা স্ট্রাকচার, যা দিয়ে কিছুটা সম্ভাবনাসহ বলা যায়, কোনো উপাদান x সেট M এ আছে কি না।
যেমন, আমাদের সিস্টেমে মাপতে হবে ব্যবহারকারীরা একটি বিজ্ঞাপনের ব্যানারে কতবার ক্লিক করেছেন। প্রত্যেক ক্লিকের পর আমাদের কাছে একটি HTTP GET অনুরোধ আসে, যা জানায় যে ব্যবহারকারী XYZ বিজ্ঞাপন 123 এ ক্লিক করেছেন। মাঝে মাঝে ব্যবহারকারী ভুল করে মাউসে ডাবল-ক্লিক করেন, ফলে আমাদের কাছে দুইটি অনুরোধ আসে। আমরা এমন অনুরোধগুলো ছেঁকে ফেলে ডেটাবেসে একটি ক্লিক হিসেবে রাখতে চাই।
তাই আমাদের এমন একটি অ্যাপ্লিকেশন দরকার, যা ক্লিকের বার্তাগুলোর চ্যানেল পড়বে এবং পুনরাবৃত্তি ছেঁকে ফেলবে। কীভাবে তা করব? এমন প্রত্যেক বার্তার একটি আইডি থাকে, তাই পুরো বার্তা তুলনা করার দরকার নেই, শুধু জানলেই চলে যে একই আইডির বার্তা আমরা আগে কখনো প্রক্রিয়া করেছি কি না। বার্তার স্ট্রিম (এখানে সরলতার জন্য একটি অ্যারে) থেকে পুনরাবৃত্তি বাদ দেওয়ার একটি সহজ জাভাস্ক্রিপ্ট কোড দেখতে এমন হতে পারে:
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 এ অন্তত এক দিনের ডেটা রাখতে হয়, আর আমরা প্রতি সেকেন্ডে ধরা যাক দশ হাজার বার্তা দেখি? সবচেয়ে খারাপ ক্ষেত্রে আমাদের রাখতে হবে 86,40,00,000 টি পর্যন্ত আইডি। uuid v4 ব্যবহার করলে প্রত্যেক আইডির দৈর্ঘ্য 36, অর্থাৎ দিনে আমাদের রাখতে হবে অন্তত 31 GB। একটু বেশিই। মেমোরির চাহিদা কি কমানো যায় না?
ব্লুম ফিল্টার
পুরো আইডি না রেখে শুধু এর হ্যাশ মান রাখা যায়। আমরা পরিচিত 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 দিলে সহজভাবে ভেক্টরের সূচক 47 এ 1 বসিয়ে দিই। এতে চিহ্ন দিয়ে রাখি যে মান 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যদি উত্তর দেয় যে প্রদত্ত উপাদানটি ব্লুম ফিল্টারে নেই, তাহলে বুঝতে হবে উপাদানটি তুমি সত্যিই কখনো এতে রাখনি। - মেথডটি যদি উত্তর দেয় যে প্রদত্ত উপাদানটি ব্লুম ফিল্টারে আছে, তাহলে উপাদানটি তুমি সত্যিই এতে রেখেছ, এমন হওয়া জরুরি নয়, কারণ হ্যাশ ফাংশনের সংঘর্ষ ঘটে থাকতে পারে।
- সাধারণভাবে, ভুল উত্তরের সম্ভাবনা কমাতে চাইলে হ্যাশ ফাংশনের সংখ্যা বাড়াও, অথবা এদের আকার (অর্থাৎ আউটপুট মানের আকার) বাড়াও।
- যত বেশি হ্যাশ ফাংশন ব্যবহার করবে, ব্লুম ফিল্টার তত ধীর হবে।
- যত বড় হ্যাশ ফাংশন ব্যবহার করবে, ব্লুম ফিল্টার তত বেশি জায়গা নেবে।
- কোনো উপাদান একবার ব্লুম ফিল্টারে রাখলে তা আর সরানো যায় না।