چگونه از crawl کردن آدرس‌های تکراری در ابعاد گوگل جلوگیری کنیم؟

گزینه ۱: استفاده از ساختار داده Set برای بررسی اینکه آیا یک URL قبلاً وجود دارد یا خیر. Set سریع است، اما از نظر فضایی کارآمد نیست.

گزینه ۲: ذخیره URLها در یک پایگاه داده و بررسی اینکه آیا یک URL جدید در پایگاه داده وجود دارد. این روش ممکن است به شیوه مناسب کار کند اما بار روی پایگاه داده بسیار بالا خواهد بود.

گزینه ۳:بلوم فیلتر (𝐁𝐥𝐨𝐨𝐦 𝐟𝐢𝐥𝐭𝐞𝐫). این گزینه ترجیح داده می‌شود. فیلتر بلوم توسط برتون هاوارد بلوم در سال ۱۹۷۰ پیشنهاد شد. این یک ساختار داده احتمالی است که برای آزمایش اینکه آیا یک عنصر عضوی از یک مجموعه است استفاده می‌شود.

• خطا: عنصر قطعاً در مجموعه نیست.
• درست: عنصر احتمالاً در مجموعه است.

تطابق‌های مثبت-نادرست(False-positive) امکان‌پذیر است، اما منفی‌های نادرست(false negatives) ممکن نیست. دیاگرام زیر نشان می‌دهد که بلوم فیلتر چگونه کار می‌کند. ساختار داده اصلی برای بلوم فیلتر از نوع بیت برداری(Bit Vector) است و هر بیت یک مقدار هش را بیان می‌کند.

مرحله ۱: برای افزودن یک عنصر به فیلتر بلوم، آن را به سه تابع هش مختلف (A، B و C) تغذیه می‌کنیم و بیت‌ها را در موقعیت‌های نتیجه تنظیم می‌کنیم. توجه داشته باشید که هر دو "www.myweb1.com" و "www.myweb2.com" همان بیت1را در ایندکس شماره ۵ برابر با ۱ علامت‌گذاری می‌کنند. درنتیجه امکان وقوع False-positive ممکن است زیرا یک بیت ممکن است توسط عنصر دیگری تنظیم شود.

مرحله ۲: هنگام آزمایش وجود یک رشته URL، همان توابع هش A، B و C به رشته URL اعمال می‌شوند. اگر هر سه بیت برابر ۱ باشند، آنگاه URL ممکن است در مجموعه داده‌ها وجود داشته باشد؛ اگر هر یک از بیت‌ها برابر ۰ باشد، آنگاه قطعاً URL در مجموعه داده‌ها وجود ندارد.

انتخاب تابع هش مهم است. آنها باید به طور یکنواخت توزیع شده و سریع باشند. به عنوان مثال، RedisBloom و Apache Spark از روش Murmur استفاده می‌کنند و InfluxDB از xxhash استفاده می‌کند.

MurmurHash یک تابع هش غیر رمزنگاری مناسب برای جستجوی کلی مبتنی بر هش است.