بلوم فلٹر کیسے کام کرتا ہے: ازگر میں شروع سے ایک کی تعمیر

بلوم فلٹرز ایسی چیز فراہم کرتے ہیں جو جادو کی طرح محسوس ہوتا ہے۔ صرف چند کلو بائٹس میموری کا استعمال کرتے ہوئے، یہ آپ کو بتا سکتا ہے کہ آیا کوئی شے اربوں کے سیٹ میں ہے۔ اور یہ اسی مختصر مدت کے اندر جواب دیتا ہے چاہے آپ نے کتنی بچت کی ہو۔

یہ ناممکن لگتا ہے۔ ایک باقاعدہ سیٹ کے لیے ہر چیز کو یاد رکھنے کی ضرورت ہوتی ہے، اس لیے ڈیٹا کے ساتھ میموری بڑھتی ہے۔ تاہم، بلوم فلٹر اپنے آپ کو اشیاء کے بارے میں تقریباً کچھ بھی یاد نہیں رکھتا، لیکن پھر بھی رکنیت کے سوالات کے جوابات دیتا ہے۔ مسئلہ یہ ہے کہ غلطیوں کی اجازت بعض، قابل کنٹرول سمتوں میں ہے۔

یہ جادو نہیں ہے اور جس لمحے آپ اسے خود بناتے ہیں راز واضح ہو جاتا ہے اور آپ کو یہ سمجھنے کی ضرورت ہے کہ یہ کیا وعدہ کر سکتا ہے اور کیا وعدہ نہیں کر سکتا۔

اس ٹیوٹوریل میں، ہم صرف بٹس کی فہرست اور چند ہیش فنکشنز کا استعمال کرتے ہوئے ازگر میں شروع سے کام کرنے والا بلوم فلٹر بناتے ہیں۔ آخر تک، آپ بِٹ اریز کو سمجھ جائیں گے، ہم ایک سے زیادہ ہیش کیوں استعمال کرتے ہیں، کیا غلط مثبت ہیں، کیا اس بات کو یقینی بناتا ہے کہ بلوم فلٹر نہیں ٹوٹتا، اور اپنے ہدف کی خرابی کی شرح کو کیسے پیمانہ کرنا ہے۔

انڈیکس

بلوم فلٹر اصل میں کیا ہے؟

بلوم فلٹر امکانی ڈیٹا کا ڈھانچہ. پورا کام ایک سوال کا جواب دینا ہے: "کیا یہ شے سیٹ میں ہے؟” اور دو میں سے صرف ایک جواب دیں:

• یقینی طور پر سیٹ میں نہیں۔ یہ جواب ہمیشہ درست ہوتا ہے۔

• شاید سیٹ پر۔ یہ جواب عام طور پر درست ہے، لیکن بعض اوقات غلط بھی ہو سکتا ہے۔

حیرت کی بات یہ ہے کہ یہ کسی بھی چیز کو ذخیرہ کیے بغیر جواب دیتا ہے۔ Python جیسے عام سیٹ set متبادل طور پر، ایک ہیش ٹیبل تمام اشیاء کو دیکھے ہوئے رکھتا ہے، لہذا میموری اشیاء کی تعداد اور ہر آئٹم کے سائز کے ساتھ بڑھتی ہے۔

بلوم فلٹرز صرف بٹس کی قطاریں طے کرتے ہیں۔ چاہے آپ مختصر الفاظ، لمبے URLs، یا پوری فائلوں کو محفوظ کریں، سائز پہلے سے طے شدہ ہے اور کبھی تبدیل نہیں ہوتا ہے۔

لہذا بلوم فلٹر واقعی ایک کنٹینر نہیں ہے۔ کے قریب پرنٹس کا سیٹ. آپ ان سے اندر کی چیزوں کی فہرست بنانے کے لیے نہیں کہہ سکتے ہیں یا آپ سے چیز واپس کرنے کے لیے نہیں کہہ سکتے ہیں۔ آپ صرف یہ پوچھ سکتے ہیں کہ "کیا آپ نے کبھی یہ دیکھا ہے؟” اور جواب "نہیں” مکمل طور پر قابل اعتماد ہے۔

اپنی طرف متوجہ کرنے کی ایک تیز چال: مہمانوں کے ناموں کی فہرست رکھنے کے بجائے، دیوار پر لائٹ سوئچ رکھیں۔ جب آپ کے مہمان آتے ہیں، تو ان کے ناموں سے منتخب کردہ چند سوئچ آن کریں۔ سوئچ کو دیکھیں کہ آیا کوئی آیا ہے۔ اگر ان میں سے کوئی بند ہے، تو آپ وہاں کبھی نہیں پہنچے۔ اگر یہ سب چل رہا تھا تو شاید یہ تھا۔ لیکن یہ بھی ممکن ہے کہ کسی اور کا نام وہی سوئچ پلٹ گیا ہو۔

یہ تصویر یہ بھی بتاتی ہے کہ میں باقاعدہ سیٹ کے مقابلے میں ایک کا انتخاب کیوں کروں گا۔ ایک ملین یو آر ایل کے لیے اوسطاً 50 بائٹس ہر ایک، اصل سیٹ لاگت دسیوں میگا بائٹس ہے، یو آر ایل کی لمبائی کے ساتھ بڑھ رہی ہے۔ 1% غلطی کی شرح کے ساتھ ایک ہی ملین آئٹمز کے لیے بلوم فلٹر کی قیمت تقریباً 1.2 MB ہے، طے شدہ، URL کی لمبائی سے قطع نظر۔

اگر آپ کا سیٹ بہت بڑا ہے، ہر سسٹم کی میموری میں رہنے کی ضرورت ہے، یا اس کے پاس رکھنے کے لیے بڑی چیزیں ہیں، تو بچت عملی اور ناممکن کے درمیان فرق ہو سکتی ہے۔ قیمت ایک نایاب غلط مثبت ہے اور ایک عام نمونہ قیمت کو سستا بناتا ہے۔ "نہیں” مہنگی تلاش کو چھوڑ دے گا، اور "ہاں” ایک سست، زیادہ درست چیک کو متحرک کرے گا جو بہرحال چلایا جاتا۔

انگوٹھے کا اصول: اگر آپ کو درست جوابات، حذف شدہ، یا محفوظ کردہ مواد کی فہرست بنانے کی اہلیت درکار ہے، تو فزیکل سیٹ استعمال کریں۔ جب آپ کو ایک چھوٹے، تیز گیٹ کی ضرورت ہو تو بلوم فلٹر کا استعمال کریں جو ایک مہنگے آپریشن کے سامنے بیٹھتا ہے اور آپ کو قابل اعتماد طریقے سے بتاتا ہے کہ اسے کب چھوڑا جا سکتا ہے۔

مختصر تاریخ

اس ڈھانچے کا نام برٹن ہاورڈ بلوم کے نام پر رکھا گیا ہے، جس نے اسے 1970 کے ایک مقالے میں کمیونیکیشنز آف ACM میں بیان کیا، "اسپیس/ٹائم ٹریڈ آف ہیش کوڈنگ میں قابل برداشت غلطیوں کے ساتھ۔”

اس کی حوصلہ افزا مثال حیرت انگیز طور پر عام تھی۔ لغت میں کسی لفظ کو تلاش کرنے کے لیے متن کو ہائفنیٹ کرنے اور ہجے چیک کرنے کے لیے ایک پروگرام کی ضرورت ہوتی ہے، اور میری 1970 کی چھوٹی سی یادداشت میں ایک پوری لغت کو ذخیرہ کرنا بہت مہنگا تھا۔ بلوم کا خیال خلا میں بڑی بچت کے بدلے ایک چھوٹی، کنٹرول شدہ غلطی کی شرح کو قبول کرنا تھا۔ ایک واحد لین دین جو تھوڑی سی غلطی کی اجازت دیتا ہے اور بہت زیادہ میموری کو بچاتا ہے یہی وجہ ہے کہ یہ فن تعمیر 50 سال بعد بھی بہت سے بڑے سسٹمز میں ظاہر ہوتا ہے۔

جہاں بلوم فلٹرز استعمال کیے جاتے ہیں۔

آج، آپ ممکنہ طور پر ایسا سافٹ ویئر استعمال کر رہے ہیں جو بلوم فلٹرز کو سپورٹ کرتا ہے۔ یہ ضروری ہے جب:

• ڈیٹا بیس اور اسٹوریج انجن: کیسینڈرا، ایچ بیس، بگ ٹیبل، اور بہت سے لاگ ساختہ (ایل ایس ایم ٹری) اسٹورز ہر ڈسک فائل کے لیے بلوم فلٹر برقرار رکھتے ہیں۔ سست ڈسک پڑھنے سے پہلے، انجن فلٹر سے پوچھتا ہے: "کیا یہ کلید اس فائل میں موجود ہو سکتی ہے؟” "نہیں” کا انتخاب آپ کو فائل کو مکمل طور پر چھوڑنے کی اجازت دے گا، پڑھنے کی ایک بڑی تعداد کو روکتا ہے۔

• محفوظ براؤزنگ: گوگل کروم کے ابتدائی ورژن نے معلوم خطرناک سائٹس کے لیے مقامی بلوم فلٹر کے خلاف ہر یو آر ایل کو چیک کیا۔ "نہیں” کا مطلب ہے بغیر نیٹ ورک کالز کے محفوظ۔ شاذ و نادر ہی جواب "ہاں” تھا اور پوری فہرست کے خلاف ایک حقیقی چیک چلایا گیا تھا۔

• کیشے اور CDN: ایک عام عمل یہ ہے کہ کسی چیز کو ایک سے زیادہ بار درخواست کرنے کے بعد ہی کیش کیا جائے۔ بلوم فلٹرز آسانی سے یاد رکھتے ہیں "کیا میں نے اسے پہلے دیکھا ہے؟” یک طرفہ درخواستوں کے سیلاب کو فلٹر کرنا۔

• سفارشات: میڈیم نے وضاحت کی کہ آپ پہلے سے پڑھے ہوئے مضامین کی سفارش کرنے سے بچنے کے لیے بلوم فلٹرز کا استعمال کیسے کریں۔

• نیٹ ورکنگ اور کریپٹو کرنسی: راؤٹرز نے اسے ڈپلیکیٹ پیکٹوں کا پتہ لگانے کے لیے استعمال کیا، اور ابتدائی Bitcoin لائٹ کلائنٹس نے اس کا استعمال متعلقہ لین دین کی درخواست کرنے کے لیے کیا، یہ ظاہر کیے بغیر کہ وہ کس پتے میں دلچسپی رکھتے ہیں۔

شکل ہمیشہ ایک جیسی رہتی ہے۔ بلوم فلٹرز مہنگے آپریشنز (ڈسک ریڈز، نیٹ ورک کی درخواستیں، ڈیٹا بیس کے سوالات) کے سامنے کھڑے ہوتے ہیں اور ان میں سے زیادہ تر مہنگے چیکوں کو چند تیز صفوں میں تبدیل کرتے ہیں۔ اب آئیے ایک بناتے ہیں اور دیکھتے ہیں کہ یہ کیسے ہوتا ہے۔

کلیدی خیال: بٹ اری اور کچھ ہیش

بلوم فلٹر دو حصوں پر مشتمل ہے:

1. کوئی راستہ نہیں بٹ سرنی: بٹس کی ایک لمبی قطار جو سب 0 سے شروع ہوتی ہے۔

2. چند ہیش فنکشن ہر ایک آئٹم کو متعلقہ صف میں اس کی پوزیشن سے بدل دیتا ہے۔

کو شامل کریں ہم آئٹم کو ہر ہیش فنکشن کے ذریعے چلاتے ہیں، متعدد پوزیشن حاصل کرتے ہیں، اور پھر ہر پوزیشن میں بٹ کو 1 پر سیٹ کرتے ہیں۔

کو چیک کریں ہم ایک ہی ہیش فنکشن کے ذریعے آئٹمز چلاتے ہیں اور انہی مقامات کو چیک کرتے ہیں۔ اگر سبھی 1 ہیں، تو آئٹم "شاید موجود ہے”۔ اگر کوئی آئٹم 0 ہے، تو آئٹم "یقینی طور پر موجود نہیں” ہے۔

دوسرا جواب اہم ہے۔ اگر بٹ اب بھی 0 ہے، تو آپ یقینی طور پر جانتے ہیں کہ آپ نے اسے سیٹ کرنے کے لیے کچھ شامل نہیں کیا ہے۔ فلٹر کبھی بھی وہ چیز نہیں چھوڑتا جو آپ اصل میں دیکھتے ہیں۔

Python میں مکمل ڈھانچہ مندرجہ ذیل ہے:

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size              # number of bits in the array (m)
        self.num_hashes = num_hashes  # number of hash functions (k)
        self.bits = [0] * size        # every bit starts at 0

کسی آئٹم کو مقام میں تبدیل کریں۔

ہمیں ضرورت ہے num_hashes ہر آئٹم کا الگ مقام ہوتا ہے، لہذا آپ کو اسے پھیلانے کی ضرورت ہے۔ یہاں ایک عام اور صاف چال ہے: ڈبل ہیشنگ: ایک بار دو آزاد ہیشوں کی گنتی کرتا ہے اور پھر ان کو ملا کر ضرورت کے مطابق زیادہ پوزیشنیں تیار کرتا ہے۔

def _positions(self, item):
    data = item.encode("utf-8")
    h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
    h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
    for i in range(self.num_hashes):
        yield (h1 + i * h2) % self.size

تین چیزیں ہو رہی ہیں:

• sha256 اور h2 سے md5 یہ آپ کو دو بڑی تعداد دیتا ہے جو ایک ہی سٹرنگ پر مستحکم اور دوسری سٹرنگ پر بے ترتیب دکھائی دیتے ہیں۔

• h1 + i * h2 ہر ایک مختلف قدر کے ساتھ مل جاتا ہے۔ iمقامات ایک دوسرے کے ساتھ کلسٹر ہونے کے بجائے پھیلے ہوئے ہیں۔

• % self.size ہر ایک قدر کو اس کے درست اشاریہ سے سمیٹیں۔ 0 کو size - 1.

اسے ایک آئٹم کے لیے چلائیں اور آپ کو ملے گا: num_hashes مقام وہ مقام فلٹر کے اندر موجود شے کا فنگر پرنٹ ہے۔

شامل کریں اور تصدیق کریں۔

اسے شامل کرنا تمام پوزیشنوں میں بٹس کو سیٹ کرتا ہے۔ ایک بار تصدیق ہو جانے کے بعد، یہ آپ سے پوچھے گا کہ کیا سب کچھ سیٹ ہو گیا ہے۔

def add(self, item):
    for idx in self._positions(item):
        self.bits[idx] = 1

def __contains__(self, item):
    return all(self.bits[idx] for idx in self._positions(item))

تعریف __contains__ آئیے ازگر کی قدرتی زبان استعمال کریں۔ in نحو آئیے کوشش کریں:

bf = BloomFilter(size=1000, num_hashes=4)
bf.add("alice")
bf.add("bob")

print("alice" in bf)   # True
print("bob" in bf)     # True
print("carol" in bf)   # almost always False

"carol" چونکہ کچھ بھی شامل نہیں کیا گیا ہے، یہ تقریباً یقینی ہے کہ چار بٹس میں سے کم از کم ایک اب بھی 0 ہے، اور فلٹر ایسی کسی چیز کی اطلاع نہیں دیتا ہے۔ یہ ایک عام معاملہ ہے۔ لیکن لفظ "تقریباً یقینی طور پر” دیکھیں۔ وہ باڑ اگلے حصے میں پوری کہانی ہے۔

جھوٹے مثبت معمول ہیں۔

بٹس مشترکہ ہیں۔ اگر آپ کافی آئٹمز شامل کرتے ہیں تو، 4 بٹس جو اسے انکوڈ کرنے میں لیتا ہے۔ "carol" اسے کسی اور چیز کے ذریعے بھی تمام 1 پر سیٹ کیا جا سکتا ہے۔ "carol" خود کو شامل نہیں کیا گیا تھا۔ جب ایسا ہوتا ہے، فلٹر کہتا ہے "شاید موجود ہے” کسی ایسی چیز کے لیے جو وہاں نہیں ہے۔ کہ غلط مثبت.

وہ لوگ جو بلوم فلٹرز میں نئے ہیں کبھی کبھی سوچتے ہیں کہ یہ ایک بگ ہے۔ یہ سچ نہیں ہے۔ یہ وہ قیمت ہے جو آپ اتنی کم میموری استعمال کرنے کے لیے ادا کرتے ہیں، اور یہ ٹیون ایبل ہے۔ آپ بہت ساری اشیاء کو ایک چھوٹے سے فلٹر میں ڈال کر ایسا ہوتا دیکھ سکتے ہیں۔

bf = BloomFilter(size=200, num_hashes=4)
for i in range(100):
    bf.add(f"user-{i}")

# None of these were added, but some will sneak through as "present":
false_hits = sum(f"ghost-{i}" in bf for i in range(1000))
print(false_hits)  # a non-zero number: the false positive rate in action

لیکن فلٹرز دوسری سمت میں کبھی غلط نہیں ہوتے۔ ہر user-i آپ کے شامل کردہ آئٹمز اب بھی واپس کیے جائیں گے۔ Trueاس کی وجہ یہ ہے کہ کسی آئٹم کو شامل کرنے سے تمام بٹس سیٹ ہو جاتے ہیں اور وہ بٹس کبھی صاف نہیں ہوتے ہیں۔ یہ وہ وعدہ ہے جو بلوم فلٹرز ہمیشہ رکھتے ہیں:

• "نہیں” ہمیشہ درست ہوتا ہے۔ بالکل کوئی غلط منفی نہیں ہیں.

• "ہاں” غلط ہو سکتا ہے۔ غلط مثبت ممکن ہیں۔

یہ توازن وہی ہے جو بلوم فلٹرز کو کارآمد بناتا ہے۔ ویب براؤزر معلوم نقصان دہ URLs کے بلوم فلٹرز کو برقرار رکھ سکتے ہیں اور فوری طور پر تمام لنکس کو چیک کر سکتے ہیں۔ "نہیں” کا مطلب ہے کہ لنک محفوظ ہے اور مزید کارروائی کی ضرورت نہیں ہے۔ "ہاں” نایاب ہے اور اصل فہرست کے مقابلے میں ایک سست اور زیادہ درست جانچ پڑتال کرتا ہے۔ فلٹرز زیادہ تر استفسارات کو چند ارے ریڈز میں تبدیل کرتے ہیں۔

ہدف کی خرابی کی شرح تک پیمانہ کریں۔

غلط مثبت شرح تین نمبروں پر منحصر ہے: بٹ سرنی کا سائز۔ mشامل کیے جانے والے آئٹمز کی تعداد nاور ہیش فنکشنز کی تعداد k. تخمینی غلط مثبت شرح ہے:

p = (1 - e^(-k*n/m)) ** k

اس کا اندازہ لگانے کی ضرورت نہیں۔ اشیاء کی تعداد پر غور کرنا n ہدف غلط مثبت شرح p آپ بہترین کا انتخاب کر سکتے ہیں۔ m اور k براہ راست:

import math

def optimal_params(n, p):
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))  # bits needed
    k = max(1, round((m / n) * math.log(2)))               # hashes to use
    return m, k

print(optimal_params(1_000_000, 0.01))  # about (9_585_059, 7)

برائے مہربانی نتائج کو غور سے پڑھیں۔ 1% غلطی کی شرح کے ساتھ 1 ملین آئٹمز کو ٹریک کرنے کے لیے تقریباً 9.6 ملین بٹس (تقریباً 1.2 MB) اور 7 ہیش فنکشنز کی ضرورت ہوتی ہے۔

واقعی set اس کی لاگت دس لاکھ تاروں سے زیادہ ہے، اور اس میں سے زیادہ تر لاگت تار کی لمبائی کے ساتھ بڑھ جاتی ہے۔ بلوم فلٹرز اشیاء کی لمبائی کی پرواہ نہیں کرتے، صرف ان کی گنتی۔

آپ کیا نہیں کر سکتے: حذف کریں۔

ایماندار ہونے کی ایک اور حد ہے۔ وہ بٹس مشترکہ ہیں، لہذا آپ اس بٹ کو صاف کرکے کسی آئٹم کو نہیں ہٹا سکتے۔ صاف تھوڑا "alice" ہو سکتا ہے اسے تھوڑا واضح کر دیں۔ "bob" یہ منحصر ہے. اور اب "bob" غیر حاضریوں کی غلط اطلاع دے کر، آپ غلط منفی نہ ہونے کے اپنے وعدے کو توڑ دیتے ہیں۔

اگر حذف کرنا ضروری ہو تو، معیاری اصلاحات یہ ہیں: بلوم فلٹر کے حساب کتابیہاں ہر سلاٹ ایک بٹ کے بجائے ایک چھوٹا کاؤنٹر ہے۔ اضافہ کاؤنٹر کو بڑھاتا ہے، ہٹانے سے کاؤنٹر میں کمی آتی ہے، اور سلاٹس کو "سیٹ” کے طور پر شمار کیا جاتا ہے جب تک کہ کاؤنٹر 0 سے زیادہ ہو۔ میموری کے لیے زیادہ ادائیگی کرنا ایک عام تجارت ہے۔

ایک ساتھ رکھو

یہ ہے کہ ہم نے کیا بنایا اور اس کی قیمت کتنی ہے:

کام	خرچ
add	ٹھیک ہے)
in (چیک کریں)	ٹھیک ہے)
جگہ	کے لیے m تھوڑا سا n اشیاء کے سائز سے قطع نظر اشیاء

مضمرات:

• بلوم فلٹر بٹس کے علاوہ چند ہیش فنکشنز کی ایک صف ہے۔ سیٹ شامل کریں۔ k بٹ، یہ آپ سے پوچھے گا کہ آپ چیک کر رہے ہیں یا نہیں۔ k بٹس سب سیٹ ہیں.

• "نہیں” ہمیشہ درست ہوتا ہے۔ ایک "ہاں” غلط مثبت ہوسکتا ہے اور شرح وہ چیز ہے جسے آپ ایڈجسٹ کرتے ہیں۔ m اور k.

• یہ چھوٹا اور تیز ہے کیونکہ یہ آئٹمز کے بجائے فنگر پرنٹس کو اسٹور کرتا ہے، لہذا آپ بھول جاتے ہیں کہ آئٹمز اصل میں کیا ہیں۔

• بٹس کا اشتراک کیا جاتا ہے، لہذا انہیں کمپیوٹیشنل تبدیلی کے بغیر حذف نہیں کیا جا سکتا۔

اگلی بار جب سسٹم کہے گا کہ "یہ یقینی طور پر کیشے میں نہیں ہے، تلاش کو چھوڑ دیں” یا "یہ ایک معلوم آئٹم ہو سکتا ہے، آئیے دوبارہ چیک کریں”، آپ کو بالکل پتہ چل جائے گا کہ اس کے نیچے کیا ہے۔ اس کا مطلب ہے کہ بٹس کی قطاریں، چند ہیشز، اور احتیاط سے منتخب کردہ سمتیں ہیں جو غلط ہو سکتی ہیں۔

اگر آپ ڈیٹا کے ڈھانچے کو یاد کرنے کے بجائے ان کو بنا کر سیکھنے میں لطف اندوز ہوتے ہیں، تو یہ ایک ہینڈ آن لرننگ پلیٹ فارم کے پیچھے آئیڈیا ہے جسے میں نے IWTLP کہا ہے۔ یہاں یہ بلوم فلٹر ان مشقوں میں سے ایک ہے جو آپ ڈیٹا انجینئرنگ ٹریک میں خود کو بناتے ہیں۔