انسٹاگرام پر 500 ملین سے زیادہ رجسٹرڈ صارف نام ہیں۔ جب کوئی نیا صارف رجسٹر کرنے کی کوشش کرتا ہے، تو پلیٹ فارم کو تقریباً فوراً ایک سوال کا جواب دینا چاہیے۔ کیا یہ صارف نام پہلے ہی لیا جا چکا ہے؟
سادہ جواب ڈیٹا بیس کے سوالات ہیں۔ یہ صارف کی میز لیتا ہے، صارف نام کی تلاش کرتا ہے، اور واپس آتا ہے چاہے یہ موجود ہے یا نہیں۔ یہ چھوٹے پیمانے پر اچھا کام کرتا ہے۔ تاہم، 500 ملین ریکارڈز سے روزانہ لاکھوں بار استفسار کیا جاتا ہے، یہ ایک سنگین رکاوٹ پیدا کرتا ہے۔ یہاں تک کہ اشاریہ سازی کے ساتھ، ڈیٹا بیس ہر بار جب رجسٹر کرنے کی کوشش کرتا ہے ایک مہنگا آپریشن کرتا ہے۔
خوش قسمتی سے، ایک ہوشیار نقطہ نظر ہے. ڈیٹا بیس تک رسائی سے پہلے دوسرے سسٹمز سے بہت تیز سوالات پوچھیں۔ نظام دو جوابات میں سے ایک فراہم کرتا ہے:
یقینی طور پر یہاں نہیں: اس بات کی ضمانت ہے۔ کوئی مستثنیات نہیں ہیں. آپ اپنا صارف نام استعمال کر سکتے ہیں اور ڈیٹا بیس کو مکمل طور پر چھوڑ سکتے ہیں۔
شاید یہاں: اس کی ضمانت نہیں ہے۔ یہ چوری شدہ صارف نام یا غلط الارم ہو سکتا ہے۔ آپ کو اسے ڈیٹا بیس کے ذریعے چیک کرنے کی ضرورت ہے۔
وہ سسٹم بلوم فلٹر ہے۔ آپ یقین سے نہیں کہہ سکتے کہ کچھ موجود ہے۔ لیکن یہ آپ کو پورے یقین کے ساتھ بتا سکتا ہے کہ کچھ ہونے والا ہے۔ ~ نہیں موجود ہے اور بڑے سسٹمز میں، یہ یک طرفہ ضمانتیں سب سے مہنگے ڈیٹا بیس کے سوالات کو ختم کرتی ہیں۔
انڈیکس
شرطیں
اس مضمون کو پڑھنے سے پہلے، آپ کو درج ذیل سے واقف ہونا چاہیے:
-
بنیادی ڈیٹا سٹرکچرز: ارے اور انڈیکسنگ کیسے کام کرتی ہے۔
-
تصوراتی سطح پر ہیش فنکشن کیا ہے؟ ایک فنکشن جو ان پٹ لیتا ہے اور ایک مقررہ سائز کا آؤٹ پٹ تیار کرتا ہے۔
-
ڈارٹ یا C# میں پروگرامنگ کے بنیادی تصورات
آپ کو ڈیٹا بیس انٹرنلز یا ڈسٹری بیوٹڈ سسٹمز کی گہری سمجھ کی ضرورت نہیں ہے۔ اس مضمون میں، وہ صرف یہ بتانے کے لیے استعمال کیے گئے ہیں کہ عملی انجینئرنگ میں بلوم فلٹرز کیوں اہم ہیں۔
بلوم فلٹر کیا ہے؟
بلوم فلٹر ایک ممکنہ ڈیٹا ڈھانچہ ہے جو اس سیٹ میں اصل قدروں کو ذخیرہ کیے بغیر کسی سیٹ کی نمائندگی کرتا ہے۔
احتمال کا لفظ اہم ہے۔ باقاعدہ سیٹ یا ڈیٹا بیس کے برعکس، بلوم فلٹرز رکنیت کے بارے میں قطعی جواب فراہم نہیں کرتے ہیں۔ امکانی جوابات فراہم کرتا ہے۔ اور احتمالات جان بوجھ کر غیر متناسب ہیں۔
ہم کبھی نہیں کہیں گے کہ اس میں کسی ایسی چیز کی کمی ہے جو حقیقت میں موجود ہے۔ اسے کوئی غلط منفی کہا جاتا ہے۔
کبھی کبھی آپ کہہ سکتے ہیں کہ کچھ موجود ہے جب وہ واقعی نہیں ہے۔ اسے غلط مثبت کہا جاتا ہے۔ جس شرح سے یہ ہوتا ہے وہ چھوٹا، کنٹرول شدہ، اور ریاضی کے لحاظ سے قابل پیشن گوئی ہے۔
یہ توازن بلوم فلٹرز کو کارآمد بناتا ہے۔ جواب "یقینی طور پر یہاں نہیں” قابل اعتماد ہے۔ جواب "شاید یہاں” کہیں اور جانے کا اشارہ ہے۔
بلوم فلٹر کے دو اجزاء
بلوم فلٹر دو چیزوں پر مشتمل ہوتا ہے:
1. بٹ کا انتظام
تمام زیرو پر شروع کی گئی بٹس کی ایک مقررہ سائز کی صف۔ یہ فلٹر کے لیے کل اسٹوریج کی جگہ ہے۔ یہ کوئی تار یا شے نہیں ہے، یہ صرف بٹس ہے۔ 0 اور 1۔
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Value: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
اس صف کے سائز کا انتخاب ان اشیاء کی تعداد کی بنیاد پر کیا جاتا ہے جن کی ذخیرہ کیے جانے کی توقع ہے اور غلط مثبت شرح جس کو برداشت کیا جا سکتا ہے۔ بڑی صفیں غلط مثبت شرح کو کم کرتی ہیں لیکن زیادہ میموری کی ضرورت ہوتی ہے۔
2. ایک سے زیادہ ہیش فنکشنز
عام طور پر 3 سے 7 ہیش فنکشنز ہوتے ہیں۔ ہر ایک ان پٹ لیتا ہے اور ایک نمبر تیار کرتا ہے جو بٹ سرنی میں پوزیشن پر نقشہ بناتا ہے۔ مختلف ہیش فنکشنز ایک ہی ان پٹ کے لیے مختلف پوزیشنز تیار کرتے ہیں۔
ہیش فنکشنز کو تیز ہونا چاہیے، ایک دوسرے سے آزاد ہونا چاہیے، اور اپنے آؤٹ پٹ کو بٹ اری میں یکساں طور پر تقسیم کرنا چاہیے۔ ہیش فنکشن کا معیار غلط مثبت شرح کو براہ راست متاثر کرتا ہے۔
آئٹمز کو شامل کرنا کیسے کام کرتا ہے۔
فلٹر میں صارف نام "seyi_codes” شامل کرنے کے لیے، ہم اسے تینوں ہیش فنکشنز کے ذریعے چلاتے ہیں۔
hash1("seyi_codes") = 3
hash2("seyi_codes") = 7
hash3("seyi_codes") = 11
بٹ سرنی میں تین پوزیشنیں 1 پر سیٹ کریں۔
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Value: 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0
^ ^ ^
hash1 hash2 hash3
صارف کا نام "seyi_codes” اب فلٹر میں ظاہر ہوگا۔ تاہم، سٹرنگ خود کہیں بھی محفوظ نہیں ہے۔ صرف یہ حقیقت ہے کہ 3rd، 7th، اور 11th کسی چیز کے ذریعہ ترتیب دیا گیا تھا۔
اب دوسرا صارف نام "aderonke” شامل کریں۔
hash1("aderonke") = 1
hash2("aderonke") = 7
hash3("aderonke") = 13
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Value: 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0
^ ^ ^ ^ ^
پوزیشن 7 پہلے ہی "seyi_codes” کے ذریعے سیٹ کر دی گئی ہے اور "aderonke” کے ذریعے دوبارہ سیٹ کی جائے گی۔ یہ عام بات ہے۔ بٹس کو متعدد آئٹمز میں شیئر کیا جا سکتا ہے۔ یہ شیئرنگ غلط مثبت کا باعث بھی بن سکتی ہے۔ ہم ذیل میں اس کے بارے میں مزید بات کریں گے۔
اشیاء کو کیسے چیک کریں۔
یہ چیک کرنے کے لیے کہ آیا فلٹر میں صارف نام موجود ہے، اسے اسی ہیش فنکشن کے ذریعے چلائیں اور یقینی بنائیں کہ نتیجے میں آنے والی پوزیشنیں 1 پر سیٹ ہیں۔
شامل کردہ "seyi_codes” کو چیک کریں:
hash1("seyi_codes") = 3 → bit[3] = 1 ✓
hash2("seyi_codes") = 7 → bit[7] = 1 ✓
hash3("seyi_codes") = 11 → bit[11] = 1 ✓
تینوں پوزیشنز 1 ہیں۔ فلٹر کہتا ہے "شاید یہاں”۔ اپنا ڈیٹا بیس چیک کریں اور دیکھیں کہ آیا آپ کا صارف نام استعمال ہوا ہے۔
چیک کریں کہ "john_doe” کو شامل نہیں کیا جا رہا ہے:
hash1("john_doe") = 2 → bit[2] = 0 ✗
پہلی ہیش نے پھر بھی 0 کی پوزیشن لوٹائی۔ فوراً رک جائیں۔ فلٹر کہتا ہے "یہاں کبھی نہیں”۔ باقی ہیش فنکشنز کو چیک نہیں کیا گیا ہے۔ ہم ڈیٹا بیس کو ہاتھ نہیں لگاتے۔ آپ اپنا صارف نام استعمال کر سکتے ہیں۔
بلوم فلٹرز تیز کیوں ہوتے ہیں اس کو سمجھنے کے لیے یہ جلد ختم کرنا اہم ہے۔ جس لمحے ہیش فنکشن بٹ 0 واپس کرتا ہے، چیک ختم ہوجاتا ہے۔ جو اصل میں شامل کیا جاتا ہے وہ تمام پوزیشنز کو 1 پر سیٹ کرتا ہے۔ کہیں بھی صفر اس بات کی نشاندہی کرتا ہے کہ کوئی چیز شامل نہیں کی گئی۔
غلط مثبت وضاحت
یہ وہ جگہ ہے جہاں امکانی حصہ کنکریٹ بن جاتا ہے۔
براہ کرم صارف نام "tiwa_codes” کو چیک کریں جو شامل نہیں کیا گیا ہے۔
hash1("tiwa_codes") = 3 → bit[3] = 1 ✓ (set by seyi_codes)
hash2("tiwa_codes") = 7 → bit[7] = 1 ✓ (set by seyi_codes and aderonke)
hash3("tiwa_codes") = 13 → bit[13] = 1 ✓ (set by aderonke)
تینوں پوزیشنز 1 ہیں۔ فلٹر کہتا ہے "شاید یہاں”۔ تاہم، "tiwa_codes” شامل نہیں کیا گیا۔ پوزیشنز 3، 7 اور 13 میں بٹس مختلف صارف ناموں کے ذریعے سیٹ کیے گئے تھے۔ "tiwa_codes” کو پہلے سے زیر قبضہ جگہ پر ہیش کر دیا گیا ہے۔
یہ ایک غلط مثبت ہے۔ فلٹر غلط ہے۔ لیکن قابل قبول سمت غلط ہے۔ جواب دراصل تھا "یہاں نہیں” لیکن میں نے کہا "شاید یہاں۔” ڈیٹابیس پر جائیں اور آگے بڑھنے سے پہلے چیک کریں کہ آیا صارف نام واقعی دستیاب ہے۔
فلٹرز کبھی بھی مخالف غلطی نہیں کرتے ہیں۔ جب آپ کوئی آئٹم شامل کرتے ہیں، تو یہ تمام پوزیشنز کو 1 پر سیٹ کرتا ہے اور یہ دیکھنے کے لیے چیک کرتا ہے کہ آیا تمام پوزیشنز 1 ہیں، لہذا آپ کو ان آئٹمز کے لیے "یقینی طور پر یہاں نہیں” نظر نہیں آئے گا جو اصل میں شامل کیے گئے تھے۔
میں بلوم فلٹرز سے حذف کیوں نہیں کر سکتا؟
معیاری بلوم فلٹر میں حذف کرنا ممکن نہیں ہے۔
اگر ہم بٹ کو واپس 0 پر پلٹ کر "seyi_codes” کو حذف کرنے کی کوشش کرتے ہیں، تو ہم پوزیشن 7 کو واپس 0 پر پلٹ دیتے ہیں۔ تاہم، پوزیشن 7 کو "aderonke” میں بھی استعمال کیا جاتا ہے۔ اب ایسا لگتا ہے کہ "aderonke” فلٹر میں نہیں ہے، حالانکہ اسے ہٹایا نہیں گیا ہے۔
یہ ایک بنیادی حد ہے۔ فلٹرز اس بات کو ٹریک نہیں کرتے ہیں کہ کن آئٹمز نے کون سے بٹس سیٹ کیے ہیں۔ بٹس مشترکہ ہیں۔ ایک آئٹم سے تھوڑا سا ہٹانے سے دوسری شے کی نمائندگی ٹوٹ جاتی ہے۔
کاؤنٹنگ بلوم فلٹر جیسی مختلف حالتیں اس مسئلے کو ایک بٹ کے بجائے ہر مقام پر شمار ذخیرہ کرکے حل کرتی ہیں (اضافے پر گنتی کو بڑھا کر اور حذف کرنے پر اسے کم کر کے)۔ تاہم، کمپیوٹیشنل فلٹرز بہت زیادہ میموری استعمال کرتے ہیں۔
غلط مثبت شرح
غلط مثبت شرح بے ترتیب نہیں ہے۔ یہ ریاضیاتی طور پر تین پیرامیٹرز سے طے ہوتا ہے:
درمیانی بٹ سرنی کا سائز۔ بڑی صفوں میں زیادہ مقامات دستیاب ہوتے ہیں، کم تصادم، کم غلط مثبت شرحیں، اور زیادہ میموری کی کھپت۔
ن فلٹر میں شامل کردہ آئٹمز کی تعداد۔ جیسے جیسے مزید آئٹمز شامل کیے جاتے ہیں، مزید بٹس 1 پر سیٹ ہو جاتے ہیں۔ 1 پر زیادہ بٹس سیٹ ہونے کا مطلب ہے کہ پوزیشن کا زیادہ حصہ پہلے سے ہی دوسری آئٹمز کے قبضے میں ہے، جس کا مطلب ہے کہ جھوٹے مثبت ہونے کا زیادہ امکان ہے۔
کے ہیش فنکشنز کی تعداد۔ مزید ہیش فنکشنز کا مطلب یہ ہے کہ ہر اندراج زیادہ مخصوص فنگر پرنٹ چھوڑتا ہے۔ ابتدائی طور پر، کم غلط مثبت ہوں گے. تاہم، جیسے جیسے ارے بھرتا ہے، جتنے زیادہ ہیش فنکشنز ہوتے ہیں، اتنی ہی زیادہ پوزیشنز کو چیک کرنا ہوتا ہے، اور اتنا ہی زیادہ امکان ہوتا ہے کہ ہر پوزیشن پہلے سے سیٹ ہے۔
100 ملین آئٹمز کی نمائندگی کرنے والی 1% غلط مثبت شرح والے فلٹر کے لیے تقریباً 958 ملین بٹس (تقریباً 120 MB) درکار ہوں گے۔ سٹرنگ کے طور پر ذخیرہ شدہ اصل صارف نام کئی گیگا بائٹس لے گا۔ فلٹر اقدار کے بجائے فنگر پرنٹس کو اسٹور کرتا ہے، میموری کو 95 فیصد تک کم کرتا ہے۔
زیادہ تر پیداواری نظاموں کے لیے، 0.1% اور 1% کے درمیان غلط مثبت شرح ایک اچھا توازن ہے۔ 1% سے 99% "صارف نام دستیاب ہے” سوالات کا ڈیٹا بیس پر قطعی طور پر کوئی اثر نہیں ہوتا ہے۔ 1% جو غلط مثبت ہیں تصدیق کے لیے ڈیٹا بیس میں جاتے ہیں اور درست طریقے سے حل ہو جاتے ہیں۔
ڈارٹ میں نفاذ
یہ ایک تعلیمی نفاذ ہے جو ظاہر کرتا ہے کہ بلوم فلٹر کیسے کام کرتا ہے۔ پروڈکشن سسٹمز میں، بلوم فلٹرز کو ایپلیکیشن کی سطح پر لاگو نہیں کیا جاتا ہے، بلکہ بنیادی ڈھانچے کی تہہ (ڈیٹا بیس، کیشے، یا CDN) میں بنایا جاتا ہے۔
import 'dart:typed_data';
class BloomFilter {
final Uint8List _bitArray;
final int _size;
final int _hashCount;
BloomFilter({required int size, required int hashCount})
: _size = size,
_hashCount = hashCount,
_bitArray = Uint8List((size / 8).ceil());
// set a bit at the given position
void _setBit(int position) {
final byteIndex = position ~/ 8;
final bitIndex = position % 8;
_bitArray[byteIndex] |= (1 << bitIndex);
}
// check if a bit is set at the given position
bool _getBit(int position) {
final byteIndex = position ~/ 8;
final bitIndex = position % 8;
return (_bitArray[byteIndex] & (1 << bitIndex)) != 0;
}
// generate k hash positions for a given value
List _getHashPositions(String value) {
final positions = [];
for (int i = 0; i < _hashCount; i++) {
int hash = 0;
final input="$i:$value";
for (final char in input.codeUnits) {
hash = (hash * 31 + char) & 0x7FFFFFFF;
}
positions.add(hash % _size);
}
return positions;
}
// add an item to the filter
void add(String value) {
for (final position in _getHashPositions(value)) {
_setBit(position);
}
}
// check if an item might be in the filter
// returns false: definitely NOT in the set
// returns true: PROBABLY in the set (may be a false positive)
bool mightContain(String value) {
for (final position in _getHashPositions(value)) {
if (!_getBit(position)) {
return false;
}
}
return true;
}
}
آئیے اس نفاذ کے اہم فیصلوں کو دیکھتے ہیں۔
سب سے پہلے Uint8List اس کے بجائے، یہ بٹ arrays کے لیے استعمال ہوتا ہے۔ List. کوئی راستہ نہیں List ڈارٹ فی عنصر ایک پوری آبجیکٹ مختص کرتا ہے۔ کوئی راستہ نہیں Uint8List بلوم فلٹرز جس طرح میموری کی کارکردگی کو حاصل کرتے ہیں وہ 8 بٹس فی بائٹ ہے۔ کہ _setBit اور _getBit طریقہ بائٹ اور بٹ انڈیکس ریاضی کو ہینڈل کرتا ہے۔
_getHashPositions انڈیکس i کا استعمال کرتے ہوئے ہر ہیش کے فنکشن کو مختلف طریقے سے سیڈ کریں تاکہ ایک دی گئی قدر کے لیے k مختلف پوزیشنیں پیدا کریں۔ سامنے شامل کریں '$i:$value' چیک کریں کہ آیا k ہیش فنکشن میں سے ہر ایک ایک ہی ان پٹ کے لیے مختلف نتائج پیدا کرتا ہے۔ نتائج کو ماڈیول لیا جاتا ہے۔ _size فلٹر میں ہیش کو درست بٹ پوزیشنوں پر نقشہ بناتا ہے۔
mightContain جس لمحے مقام متعین نہیں ہوتا ہے، یہ غلط لوٹ آتا ہے۔ یہ ایک ابتدائی اخراج ہے جس کی جلد تصدیق کی جا سکتی ہے۔ اگر تمام پوزیشنیں سیٹ ہیں تو صحیح لوٹاتا ہے۔ اس کا مطلب یہ ہے کہ آئٹم سیٹ میں ہونے کا امکان ہے، لیکن غلط مثبت ہو سکتا ہے۔
بلوم فلٹر استعمال کریں:
void main() {
// filter sized for roughly 1000 items with low false positive rate
final filter = BloomFilter(size: 10000, hashCount: 3);
// add usernames to the filter
final registeredUsernames = [
'seyi_codes',
'aderonke_dev',
'inioluwa_tech',
'tiwaloluwa',
'flutter_ninja',
];
for (final username in registeredUsernames) {
filter.add(username);
print('Added: $username');
}
print('');
// check some usernames
final usernamesToCheck = [
'seyi_codes', // was added — should return true
'aderonke_dev', // was added — should return true
'john_doe', // was not added — should return false
'new_user_123', // was not added — should return false
'random_handle', // was not added — should return false
];
for (final username in usernamesToCheck) {
final result = filter.mightContain(username);
if (result) {
print('$username: PROBABLY taken — confirm with database');
} else {
print('$username: DEFINITELY available — skip the database');
}
}
}
حساب کتاب:
Added: seyi_codes
Added: aderonke_dev
Added: inioluwa_tech
Added: tiwaloluwa
Added: flutter_ninja
seyi_codes: PROBABLY taken — confirm with database
aderonke_dev: PROBABLY taken — confirm with database
john_doe: DEFINITELY available — skip the database
new_user_123: DEFINITELY available — skip the database
random_handle: DEFINITELY available — skip the database
شامل کردہ آئٹم "شاید درآمد شدہ” لوٹاتا ہے اور ڈیٹا بیس کی جانچ کو متحرک کرتا ہے۔ جو آئٹمز شامل نہیں کیے گئے ہیں وہ "یقینی طور پر دستیاب” واپس آئیں گے اور ڈیٹا بیس کو مکمل طور پر چھوڑ دیں گے۔
غلط مثبت شرح نقلی:
void measureFalsePositiveRate() {
final filter = BloomFilter(size: 1000, hashCount: 3);
final random = Random();
// add 100 items
final addedItems = {};
for (int i = 0; i < 100; i++) {
final item = 'user_$i';
filter.add(item);
addedItems.add(item);
}
// check 1000 items that were never added
int falsePositives = 0;
int totalChecks = 1000;
for (int i = 100; i < 100 + totalChecks; i++) {
final item = 'user_$i';
if (filter.mightContain(item)) {
falsePositives++;
}
}
final rate = (falsePositives / totalChecks * 100).toStringAsFixed(2);
print('False positive rate: $rate% ($falsePositives out of $totalChecks)');
}
اس کو چلانے سے ظاہر ہوتا ہے کہ جھوٹے مثبت حقیقی، لیکن کنٹرول شدہ ہیں۔ فلٹر کے سائز اور ہیش کی تعداد کو تبدیل کرکے، آپ غلط مثبت شرح میں اسی تبدیلی کا مشاہدہ کر سکتے ہیں۔
C# میں لاگو
using System;
using System.Collections;
using System.Text;
public class BloomFilter
{
private readonly BitArray _bitArray;
private readonly int _size;
private readonly int _hashCount;
public BloomFilter(int size, int hashCount)
{
_size = size;
_hashCount = hashCount;
_bitArray = new BitArray(size);
}
private int[] GetHashPositions(string value)
{
var positions = new int[_hashCount];
for (int i = 0; i < _hashCount; i++)
{
var input = $"{i}:{value}";
var bytes = Encoding.UTF8.GetBytes(input);
int hash = 0;
foreach (var b in bytes)
{
hash = (hash * 31 + b) & 0x7FFFFFFF;
}
positions[i] = hash % _size;
}
return positions;
}
public void Add(string value)
{
foreach (var position in GetHashPositions(value))
{
_bitArray[position] = true;
}
}
// false = definitely NOT in the set
// true = PROBABLY in the set
public bool MightContain(string value)
{
foreach (var position in GetHashPositions(value))
{
if (!_bitArray[position])
return false;
}
return true;
}
}
C# BitArray سے System.Collections بٹ لیول اسٹوریج کو مقامی طور پر ہینڈل کرتا ہے۔ منطق ڈارٹ کے نفاذ کی طرح ہے۔ وہی ہیشنگ اپروچ، 0 بٹس کا وہی ابتدائی خاتمہ، اور وہی ممکنہ واپسی کی قدر۔
حقیقت پسندانہ C# API منظرناموں میں استعمال کیا جاتا ہے:
public class UsernameService
{
private readonly BloomFilter _bloomFilter;
private readonly IUserRepository _userRepository;
public UsernameService(IUserRepository userRepository)
{
_userRepository = userRepository;
// sized for 10 million usernames, ~1% false positive rate
_bloomFilter = new BloomFilter(size: 95_850_584, hashCount: 7);
// populate the filter from existing usernames on startup
LoadExistingUsernames();
}
private void LoadExistingUsernames()
{
// stream usernames from database to avoid loading all into memory
foreach (var username in _userRepository.StreamAllUsernames())
{
_bloomFilter.Add(username);
}
}
public async Task IsUsernameAvailableAsync(string username)
{
// check the filter first — O(k) where k is the number of hash functions
if (!_bloomFilter.MightContain(username))
{
// definitely not taken — no database query needed
return true;
}
// probably taken — confirm with the database
// this handles both true positives and false positives
var existingUser = await _userRepository.FindByUsernameAsync(username);
return existingUser == null;
}
public async Task RegisterUsernameAsync(string username)
{
// add to the filter when a new username is registered
_bloomFilter.Add(username);
await _userRepository.CreateUserAsync(username);
}
}
یہ پیداواری نظام میں استعمال ہونے والا نمونہ ہے۔ بلوم فلٹر ڈیٹا بیس کے سامنے واقع ہے۔ زیادہ تر صارف نام کی دستیابی کے چیک ڈیٹا بیس تک نہیں پہنچتے ہیں۔ ایسا کرنا یا تو صحیح مثبت ہے (صارف کا نام اصل میں استعمال کیا گیا تھا) یا غلط مثبت (فلٹر غلط تھا، لیکن صارف کا نام اصل میں ڈیٹا بیس میں دستیاب پایا گیا تھا)۔
رجسٹریشن کے بعد، سروس نئے صارف نام کو فلٹر اور ڈیٹا بیس دونوں میں شامل کر دیتی ہے۔ سٹارٹ اپ پر ایک ساتھ ہر چیز کو میموری میں لوڈ کرنے کے بجائے، موجودہ ڈیٹا بیس ریکارڈز کو سٹریم کرکے فلٹرز کو آباد کیا جاتا ہے۔
جہاں بلوم فلٹرز اصلی سسٹمز میں استعمال ہوتے ہیں۔
انسٹاگرام اور ٹویٹر: صارف نام کی دستیابی
ڈیٹا بیس سے استفسار کرنے سے پہلے فلٹرز کی جانچ پڑتال کی جاتی ہے۔ "یقینی طور پر یہاں نہیں" نتیجہ ڈیٹا بیس کو مکمل طور پر چھوڑ دے گا۔ ایک "شاید یہاں" نتیجہ ڈیٹا بیس کی جانچ کو متحرک کرتا ہے۔ رجسٹریشن کی زیادہ تر کوششیں ڈیٹا بیس کو چھوئے بغیر حل ہو جاتی ہیں۔
گوگل کروم: محفوظ براؤزنگ
کروم معلوم نقصان دہ URLs کے بلوم فلٹر کے ساتھ آتا ہے جو براہ راست براؤزر میں لگایا جاتا ہے۔ جب آپ کسی URL پر جاتے ہیں، تو Chrome پہلے مقامی فلٹرز کو چیک کرتا ہے۔ اگر فلٹر کہتا ہے "یقینی طور پر بدنیتی پر مبنی نہیں ہے"، تو نیٹ ورک کی درخواست نہیں کی جائے گی۔ اگر اسے "ممکنہ طور پر نقصان دہ" کے طور پر نشان زد کیا گیا ہے، تو کروم تصدیق کے لیے Google سرورز سے رابطہ کرے گا۔ اربوں URL ریزولوشنز مقامی طور پر بغیر کسی نیٹ ورک میں تاخیر کے انجام دی جاتی ہیں۔
اپاچی کیسینڈرا۔
ہر SSTable (ڈسک پر ذخیرہ شدہ فائل) کے ساتھ میموری میں ایک بلوم فلٹر منسلک ہوتا ہے۔ کلید سے استفسار کرتے وقت، کیسینڈرا سب سے پہلے ہر SSTable کے فلٹر کو چیک کرتی ہے۔ "یقینی طور پر یہاں نہیں" نتیجہ کا مطلب ہے کہ کیسینڈرا اس SSTable کو مکمل طور پر چھوڑ دے گی، مہنگی ڈسک ریڈز سے گریز کرے گی۔ یہ ایک اہم وجہ ہے جس کی وجہ سے کیسینڈرا بڑے ڈیٹا سیٹس پر ہائی ریڈ تھرو پٹ برقرار رکھ سکتی ہے۔
میڈیم: تجویز کرنے والا انجن
میڈیم بلوم فلٹرز کا استعمال کرتا ہے یہ ٹریک کرنے کے لیے کہ ہر صارف نے کون سے مضامین پڑھے ہیں۔ ہم مضامین کی سفارش کرنے سے پہلے فلٹرز چیک کرتے ہیں۔ "یقینی طور پر نہیں پڑھا گیا" نتیجہ کا مطلب ہے کہ مضمون سفارش کے لیے امیدوار ہے۔ فلٹر ایک ہی مضمون کو ان صارفین کے لیے تجویز کیے جانے سے روکتا ہے جو پہلے ہی اسے دیکھ چکے ہیں، ہر سفارش کی درخواست کے لیے قابل استفسار ڈیٹا بیس میں پڑھنے کی پوری تاریخ کو ذخیرہ کیے بغیر۔
اکامائی سی ڈی این: کیش مینجمنٹ
اکمائی ون ہٹ مواد کی شناخت کے لیے بلوم فلٹرز کا استعمال کرتا ہے، جو کہ ایسا مواد ہے جس کی درخواست صرف ایک بار کی جاتی ہے اور کیشنگ کے قابل نہیں ہے۔ جب مواد کی پہلی بار درخواست کی جاتی ہے، تو اسے فلٹر میں شامل کر دیا جاتا ہے۔ اگر یہ بعد کی درخواستوں کے فلٹرز میں ظاہر ہوتا ہے، تو یہ کیش کرنے کے قابل ہو سکتا ہے۔ فلٹر میں دو بار ظاہر نہ ہونے والا مواد کیش نہیں کیا جاتا ہے، جس سے آپ کو ایسے مواد کے لیے مہنگے کیش اسٹوریج کی بچت ہوتی ہے جو درحقیقت آپ کو فائدہ پہنچاتا ہے۔
بلوم فلٹر کب استعمال کریں۔
بلوم فلٹرز استعمال کریں جب آپ کو ایک بہت بڑے سیٹ پر ممبرشپ چیک کرنے کی ضرورت ہو اور اس کی غلط مثبت قیمت کم ہو۔
مثالی منظر نامہ وہ ہے جہاں جواب "یقینی طور پر یہاں نہیں" ہے، جس سے مہنگے آپریشنز جیسے ڈیٹا بیس کے سوالات، نیٹ ورک کی درخواستیں، ڈسک ریڈز، یا کیش مسز کو مکمل طور پر چھوڑ دیا جائے۔ اگر اس آپریشن کی لاگت اہم ہے اور زیادہ تر چیک "یہاں نہیں" واپس آتے ہیں، تو بلوم فلٹر زیادہ تر مہنگے آپریشن کو ختم کر سکتا ہے۔
یہ اس وقت بھی استعمال کیا جا سکتا ہے جب میموری کی کارکردگی اہم ہو۔ اگر سیٹ اتنا بڑا ہے کہ اصل اقدار کو ذخیرہ کرنا میموری میں ممنوعہ طور پر مہنگا ہو گا، تو بلوم فلٹر اس سیٹ کو جگہ کے ایک حصے کے طور پر ظاہر کرتا ہے۔
اور یہ مناسب ہے جب غلط مثبت قابل قبول اور بازیافت ہوں۔ غلط مثبت قابل قبول ہے اگر اس کا مطلب ایک اضافی ڈیٹا بیس استفسار ہے۔ اگر غلط مثبت کا مطلب ڈیٹا کا نقصان یا غلط رویہ ہے، تو بلوم فلٹر صحیح ٹول نہیں ہے۔
کب استعمال نہ کریں۔
اگر آپ کو جھوٹے مثبت کے بغیر درست رکنیت کی جانچ کی ضرورت ہے، تو بلوم فلٹرز استعمال نہ کریں۔ ایک ہیش سیٹ یا ڈیٹا بیس انڈیکس آپ کو صحیح جواب دے گا۔ اگر غلط مثبت کی قیمت ناقابل قبول ہے، درست ڈیٹا ڈھانچہ استعمال کریں۔
جب آپ کو اصل ذخیرہ شدہ قیمت کو بازیافت کرنے کی ضرورت ہو تو استعمال نہ کریں۔ بلوم فلٹرز اقدار کو محفوظ نہیں کرتے ہیں۔ آپ کو اس کے بدلے میں آپ کے ہاں یا ناں جواب کے علاوہ کچھ نہیں ملے گا۔
اگر آپ کو آئٹم کو حذف کرنا پڑے تو یہ بھی اچھا خیال نہیں ہے۔ معیاری بلوم فلٹرز حذف کرنے کی حمایت نہیں کرتے ہیں۔ اگر آپ کے استعمال کے معاملے میں سیٹ سے آئٹمز کو ہٹانے کی ضرورت ہے، تو کمپیوٹیشنل بلوم فلٹر یا بالکل مختلف ڈیٹا ڈھانچہ استعمال کریں۔
آخر میں، اسے چھوٹے سیٹوں پر استعمال نہ کریں۔ جب سیٹ میموری میں فٹ ہونے کے لیے کافی چھوٹا ہو تو ہیش سیٹ استعمال کریں۔ بلوم فلٹر کی پیچیدگی جائز نہیں ہے جب ایک ہی میموری کی قیمت کے لئے ایک درست حل دستیاب ہے.
نتیجہ
بلوم فلٹرز مخصوص مسائل کو خاص خوبصورتی کے ساتھ حل کرتے ہیں۔ جب سیٹ بہت بڑا ہوتا ہے اور براہ راست ممبرشپ کی جانچ کرنا مہنگا ہوتا ہے، تو فلٹرز ایک تیز رفتار، میموری سے موثر پری چیک کے طور پر کام کرتے ہیں۔
یہ آپ کو مکمل یقین کے ساتھ بتائے گا جب سیٹ سے کچھ غائب ہے۔ یہی اعتماد اسے قابل قدر بناتا ہے۔ تمام "یہاں نہیں" جوابات ڈیٹا بیس کے سوالات سے گریز، نیٹ ورک کی درخواستوں کو محفوظ کرنے، اور ڈسک ریڈز کو چھوڑ رہے ہیں۔
غلط مثبت اس کارکردگی کی قیمت ہیں۔ "شاید یہاں" سمت میں غلط جوابات کا ایک چھوٹا، کنٹرول شدہ، اور ریاضی کے لحاظ سے قابل قیاس تناسب۔ غلط سمت جس کی قیمت ایک اضافی چیک ہے۔ یہ اس طرح سے کبھی غلط نہیں ہوتا ہے جس سے آپ کو یاد ہو کہ وہاں کیا تھا۔
Instagram اسے اپنے 500 ملین قطاروں کے ڈیٹا بیس کی حفاظت کے لیے استعمال کرتا ہے۔ گوگل اسے نیٹ ورک کی درخواست کے بغیر نقصان دہ یو آر ایل کو چیک کرنے کے لیے استعمال کرتا ہے۔ کیسینڈرا اسے ٹیرا بائٹس ڈیٹا کے لیے ڈسک ریڈز کو چھوڑنے کے لیے استعمال کرتی ہے۔ پیٹرن تمام معاملات میں ایک ہی ہے. تیز رفتار اور اسٹاکسٹک گیٹس کے پیچھے مہنگے آپریشن ہوتے ہیں۔ دروازہ صرف وہی گزرنے دیتا ہے جس سے گزرنے کی ضرورت ہوتی ہے۔
بلوم فلٹر یہی کرتا ہے۔ یہی وجہ ہے کہ یہ جدید سسٹم انجینئرنگ میں خاموشی سے طاقتور ڈیٹا ڈھانچے میں سے ایک ہے۔
اس کو سمجھنے سے آپ کو بڑے سسٹم کے سوالات اور ڈیٹا سیٹس کے لیے باخبر تعمیراتی فیصلے کرنے میں مدد ملے گی۔
کوڈنگ کا مزہ لیں !!