فیلتر بلوم (Bloom Filter) و فیلتر کوکو (Cuckoo Filter)

درک ساده از دو ساختار داده‌ی پرکاربرد برای جستجوی سریع

در دنیای داده‌های بزرگ (Big Data) و سیستم‌های توزیع‌شده، همیشه یک سؤال تکراری وجود دارد:
«چطور می‌توان سریع بفهمیم که یک عنصر در مجموعه‌ای از داده‌ها وجود دارد یا نه، بدون اینکه مجبور باشیم کل داده‌ها را جستجو کنیم؟»

پاسخ این سؤال در ساختارهای داده‌ی احتمالاتی (Probabilistic Data Structures) مثل Bloom Filter و Cuckoo Filter نهفته است.
این دو ابزار کمک می‌کنند تا بتوانیم با حافظه بسیار کم و سرعت بالا، وجود یا عدم وجود یک آیتم را بررسی کنیم.

آشنایی با Bloom Filter

تعریف ساده

فیلتر بلوم در واقع یک آرایه‌ای از بیت‌ها (0 و 1) است که در ابتدا همه صفر هستند.
با کمک چند تابع هش (Hash Function)، می‌توان تشخیص داد که آیا یک داده قبلاً در مجموعه ذخیره شده یا نه.

https://en.wikipedia.org/wiki/Bloom_filter

https://vrgl.ir/cHttn

روش کار Bloom Filter

فرض کنید می‌خواهیم بفهمیم آیا یک کلمه (مثلاً "apple") قبلاً در مجموعه بوده است یا نه:

1. در مرحله افزودن (Insert):

   • کلمه‌ی "apple" از طریق چند تابع هش (مثلاً ۳ تابع هش مختلف) پردازش می‌شود.

   • هر تابع هش یک موقعیت خاص در آرایه‌ی بیت‌ها برمی‌گرداند (مثلاً خانه‌های 4، 10 و 20).

   • در این خانه‌ها مقدار بیت را از 0 به 1 تغییر می‌دهیم.

2. در مرحله جستجو (Query):

   • دوباره همان هش‌ها روی "apple" اعمال می‌شود.

   • اگر تمام خانه‌های مربوطه مقدار 1 داشته باشند، احتمال می‌دهیم که "apple" در مجموعه وجود دارد.

   • اگر حتی یکی از خانه‌ها 0 باشد، مطمئن می‌شویم که این کلمه وجود ندارد.

نکته مهم:

فیلتر بلوم هرگز خطای منفی (False Negative) ندارد؛ یعنی اگر بگوید داده‌ای وجود ندارد، قطعاً این داده را ندارد.
اما ممکن است خطای مثبت (False Positive) داشته باشد؛ یعنی بگوید وجود دارد، در حالی که در واقع این داده وجود ندارد.

مزایای Bloom Filter

1. بسیار سریع در درج و جستجو

2. حافظه بسیار کم نسبت به نگهداری کل داده‌ها.

3. پیاده‌سازی ساده با آرایه بیتی و چند تابع هش.

4. کاربردی در سیستم‌های بزرگ مثل دیتابیس‌ها، کش‌ها و موتورهای جستجو.

معایب Bloom Filter

1. امکان خطای مثبت: ممکن است بگوید داده‌ای وجود دارد در حالی که ندارد.

2. عدم حذف عناصر: در نسخه‌ی معمولی، نمی‌توان داده‌ای را حذف کرد چون ممکن است بیت‌هایش با داده‌های دیگر مشترک باشد.

3. نیاز به تخمین اندازه اولیه: باید از قبل بدانیم چند داده قرار است وارد شود تا اندازه فیلتر و تعداد هش‌ها را درست انتخاب کنیم.

4. افزایش نرخ خطا با افزایش داده‌ها: اگر بیش از حد ظرفیتش داده وارد شود، خطاها زیاد می‌شود.

آشنایی با Cuckoo Filter

تعریف ساده

فیلتر کوکو (Cuckoo Filter) در سال ۲۰۱۴ معرفی شد و بر پایه‌ی Cuckoo Hashing ساخته شده است.
هدف آن، رفع برخی محدودیت‌های Bloom Filter است؛ مخصوصاً قابلیت حذف داده‌ها و دقت بالاتر در برخی کاربردها.

https://en.wikipedia.org/wiki/Cuckoo_filter

روش کار Cuckoo Filter

فیلتر کوکو به جای استفاده از آرایه بیتی، از یک آرایه از سطل‌ها (Buckets) استفاده می‌کند.
هر سطل می‌تواند چند مقدار کوچک (به نام Fingerprint) ذخیره کند.

وقتی می‌خواهیم یک مقدار مثلاً "apple" را ذخیره کنیم:

1. از طریق یک تابع هش، یک Fingerprint کوتاه از داده تولید می‌شود (مثلاً 8 بیت).

2. سپس این هش برای یافتن دو مکان احتمالی در جدول استفاده می‌شود (index1 و index2).

3. اگر یکی از سطل‌ها جا داشته باشد، fingerprint در آن قرار می‌گیرد.

4. اگر هر دو پر باشند، فیلتر یک مقدار قدیمی را بیرون می‌اندازد (مثل رفتار پرنده‌ی کوکو!) و آن مقدار را به موقعیت جایگزین خودش می‌فرستد.
   این فرآیند ممکن است چند بار تکرار شود تا جا پیدا شود.

در مرحله جستجو:

• همان fingerprint تولید می‌شود.

• فقط دو مکان احتمالی بررسی می‌شود (index1 و index2).

• اگر fingerprint در یکی از آنها وجود داشت، داده احتمالاً وجود دارد.

در مرحله حذف:

• اگر fingerprint پیدا شد، به‌راحتی حذف می‌شود؛ بدون تأثیر روی سایر داده‌ها.
  (این یکی از برتری‌های بزرگ نسبت به Bloom Filter است.)

⚙️ مزایای Cuckoo Filter

1. قابلیت حذف عناصر : بر خلاف Bloom Filter.

2. نرخ خطای کمتر در بسیاری از موارد، مخصوصاً در چگالی پایین.

3. کارایی بالا: فقط دو مکان بررسی می‌شود، که سرعت بالایی دارد.

4. استفاده کارآمد از حافظه: به‌خصوص وقتی fingerprint کوچک انتخاب شود.

5. عدم نیاز به دانستن تعداد دقیق داده‌ها از قبل: نسبت به Bloom Filter انعطاف‌پذیرتر است.

معایب Cuckoo Filter

1. پیچیدگی پیاده‌سازی: نسبت به Bloom Filter، ساختار و منطق درونی آن دشوارتر است.

2. احتمال شکست درج (Insertion Failure): اگر جدول بیش از حد پر شود، ممکن است نتوانیم به آن آیتم جدید وارد کرد.

3. نیاز به تنظیم دقیق اندازه سطل‌ها و fingerprintها: چون تعادل بین حافظه، خطا و کارایی حساس است.

4. مصرف بیشتر حافظه در داده‌های خیلی کوچک: در برخی کاربردها، Bloom Filter همچنان ساده‌تر و بهینه‌تر است.

یک نکته را توجه داشته باشید که برای استفاده باید از سیستم های cache و فشرده سازی استفاده کنید.

کلاس های بالا صرفا جهت آشنایی با روش کار این دو فیلتر هست.

امیدوارم از این مطلب استفاده کامل رو برده باشید.