فیلترهای بلوم چیست؟

به گزارش reportaj.me و به نقل از medium آیا تا به حال هنگام بازدید از برخی وب سایت ها با چنین هشداری از سوی گوگل مواجه شده اید؟ اگر این کار را کردید، پس قبلاً کاربرد فیلترهای شکوفه را دیده اید.

همچنین ممکن است در صفحه ثبت نام با خطای زیر روبرو شده باشید؟

بنابراین دقیقا فیلتر بلوم چیست و گوگل چگونه از آن در برنامه خود استفاده می کند؟

فهرست، درخت، مجموعه‌ها و هشت‌شبل‌ها ساختارهای داده‌ای شناخته شده‌ای هستند که برای ذخیره داده‌ها به گونه‌ای طراحی شده‌اند که انواع خاصی از عملیات را به طور موثر انجام دهند.

فیلترهای بلوم ساختار داده های احتمالی هستند که به سرعت به ما می گویند که آیا یک مقدار “احتمالا” در یک ذخیره داده وجود دارد یا خیر. علاوه بر این، حافظه آن نیز بسیار کارآمد است. ما قطعیت را به قیمت پاسخ سریعتر کنار می گذاریم. فیلترهای بلوم می توانند پاسخ های مثبت کاذب بدهند (یعنی یک عنصر در datastore وجود دارد، اما در واقع وجود ندارد) اما هرگز پاسخ های منفی کاذب نمی دهد (هرگز اعلام نمی کند که یک مقدار در دیتا استور نیست، حتی اگر وجود داشته باشد). ویژگی بعدی فیلترهای بلوم دلیلی است که بسیاری از برنامه ها از آنها به شدت استفاده می کنند.

یک سوال قریب الوقوع که ممکن است به ذهن شما خطور کند این است که چرا فیلترها شکوفا می شوند و چرا هشتبل ها یا هش مپ ها نه؟

Hashmap ها در واقع یک ساختار داده خوب برای پاسخ دادن به وجود یا عدم وجود یک عنصر در مجموعه هستند. اما هزینه دارد. اگر ۱ میلیون عنصر منحصربه‌فرد در ذخیره‌سازی داده‌ها وجود داشته باشد، باید همه آنها را ذخیره کنیم تا پاسخ دهیم آیا عناصر خاصی وجود دارند یا خیر. با این حال، با فیلترهای شکوفه، می‌توانیم به همان پرس و جو به روشی با حافظه کارآمد پاسخ دهیم (اگرچه یک پاسخ احتمالی خواهد بود)

ما بیت‌ها را در شاخص‌های ۱، ۳ و ۷ بررسی می‌کنیم. از آنجایی که همه بیت‌ها روی ۱ تنظیم شده‌اند، فیلتر شکوفه می‌گوید «cat» «احتمالاً وجود دارد» در ذخیره‌سازی داده (نتیجه مثبت کاذب). حتی اگر گربه هرگز به دیتا استور اضافه نشد.

به جای اینکه ۱، ۳ و ۷ را به عنوان پاسخ از تابع هش برای «cat» دریافت کنیم، اگر ۲، ۳ و ۷ را می‌گرفتیم، با ۱۰۰% اطمینان پاسخ می‌دادیم که cat در دیتا استور وجود ندارد (همانطور که بیت در شاخص ۲ تنظیم نشده است). به این ترتیب فیلترهای شکوفه هرگز پاسخ منفی کاذب نمی دهند (بنابراین می توان با اطمینان گفت که عنصر در فروشگاه داده وجود ندارد)

بنابراین، اگر کلیدی را جستجو کنیم و هر یک از شاخص‌های هش شده روی «۰» تنظیم نشده باشد، قطعاً مقدار در ذخیره‌گاه داده نیست. اگر همه شاخص‌های هش شده روی ۱ تنظیم شده باشند، کلید «ممکن است» در ذخیره‌گاه داده وجود داشته باشد (این به این دلیل است که بسیاری از کلیدهای مختلف می‌توانند مجموعه شاخص یکسانی ایجاد کنند)

مرورگر وب گوگل کروم از فیلتر بلوم برای شناسایی URL های مخرب استفاده می کند. هر URL ابتدا در برابر فیلتر Bloom محلی بررسی می شود و تنها پس از ضربه زدن، بررسی کامل URL انجام می شود

جیمیل از فیلترهای بلوم برای بررسی اینکه آیا نام کاربری قبلاً از لیست میلیاردها نام کاربری گرفته شده است یا خیر استفاده می کند. Gmail با اجرای خوب فیلتر شکوفه، موارد مثبت کاذب را به زیر ۱ درصد کاهش می دهد. بنابراین ۹۹٪ از تماس های شبکه به داده های واقعی جلوگیری می کند

جیمیل همچنین از فیلترهای بلوم برای بررسی اینکه آیا رمز عبور ارائه شده توسط کاربر در مجموعه عظیمی از رمزهای عبور ضعیف وجود دارد یا خیر استفاده می کند.

سایر کاربردهای فیلتر شکوفه:

پایگاه‌های داده با استفاده از درخت‌های LSM، مانند HBase، Cassandra، و BigTable از فیلترهای شکوفه برای کاهش جستجو در بخش‌های مختلف (روی دیسک‌ها) برای ردیف‌ها یا ستون‌های موجود استفاده می‌کنند.

موتور توصیه Medium از فیلترهای شکوفه برای فیلتر کردن مقالاتی که قبلاً توسط کاربر دیده شده است استفاده می کند

Quora داستان‌هایی را که قبلاً توسط افراد با استفاده از فیلترهای بلوم دیده شده است فیلتر می‌کند

نحوه اجرای فیلترهای بلوم:

برای پیاده سازی فیلتر شکوفه به نوعی بیت مپ و چند توابع هش کارآمد نیاز دارید. برای تابع هش، می‌توانیم از الگوریتم‌های MD5 استفاده کنیم که هش نسبتاً طولانی ایجاد می‌کند و سپس چند بیت از مقادیر هش کوچک‌تر را استخراج می‌کند.

ما همچنین می توانیم از یک تابع هش رمزنگاری استفاده کنیم که ثبات و تضمین را ارائه می دهد.

با این حال، MD5 برای محاسبه هش بسیار کند است و تابع هش رمزنگاری گران است. در دنیای واقعی ما از توابع هش غیر رمزنگاری استفاده می کنیم که عملکرد خوبی را ارائه می دهند. اجرای سریعتر تابع هش عبارتند از murmur، سری fnv از هش، هش Jenkins و HashMix.