فیلتر CUCKOO vs BLOOM ، از دیدگاه Gopher

در این مقاله ، من در تلاش هستم که کارایی یک فیلتر فاخته را روی یک فیلتر شکوفه پیاده سازی و تست کنم. (پست قبلی را در Chord DHT ، اجرای جدول هش توزیع شده در گلنگ بخوانید)

مقدمه

ساختار داده های احتمالی بسیار مفید هستند ، به خصوص هنگام پردازش مجموعه های داده های بزرگ. بیشتر اوقات ، هنگام کار در سمت داده ها ، فرد می خواهد یک سؤال ساده را انجام دهد "آیتم موجود نیست" یا "موردی است که در حال حاضر موجود است" هنگام پردازش داده های زمان واقعی. بگویید که اگر می خواهید یک آگهی قبلاً به کاربر ارائه شده باشد ، به زمان واقعی پاسخ دهید ، مانند تعدادی از آی پی های منحصر به فرد ، بیشترین نسخه های آیپد ، اگر یک آگهی قبلاً به یک کاربر ارائه شده است ، استفاده از ساختار داده های احتمالی روشی کارآمد برای فضایی برای پاسخگویی به این سؤالات ارائه می دهد. رویکرد معمولی برای چنین سؤالاتی استفاده از HashMap یا HashTable است ، یا ذخیره برخی حافظه پنهان خارجی (مانند redis) ، اما مشکل با مجموعه داده های بزرگ است ، این ساختارهای داده ساده نمی توانند در حافظه جا بگیرند. این جایی است که ساختار دادههای احتمالی به دلیل مزایای فضا و زمان آنها به مرحله اجرا در می آیند.

مثال استفاده از موارد

  • Google Bigtable ، Apache HBase و Apache Cassandra و Postgresql از فیلترهای Bloom برای کاهش جستجوی دیسک برای سطرها یا ستونهای غیرقابل استفاده استفاده می کنند. اجتناب از جستجوی گران قیمت دیسک عملکرد عملیات پرس و جو از پایگاه داده را به میزان قابل توجهی افزایش می دهد.
  • Medium از فیلترهای Bloom استفاده می کند تا بررسی کند آیا مقاله قبلاً به کاربر توصیه شده است یا خیر
  • اتریوم از فیلترهای Bloom برای یافتن سیاهههای مربوط به blockchain Ethereum استفاده می کند
  • مرورگر وب Google Chrome برای شناسایی URL های مخرب از فیلتر Bloom استفاده می کرد. هر URL ابتدا در برابر فیلتر محلی Bloom بررسی شد ، و تنها در صورت بازگشت فیلتر Bloom نتیجه مثبت ، بررسی کامل URL انجام شده (و کاربر هشدار می داد ، در صورت بازگشت نتیجه مثبت).

در "فاخته" چیست؟

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

فیلترهای فاخته با ارائه حذف ، شمارش محدود و احتمال مثبت کاذب ، در طراحی فیلتر شکوفه بهبود می یابند ، در حالی که هنوز یک پیچیدگی فضایی مشابه را حفظ می کند. آنها برای حل برخوردها از هش فاخته استفاده می کنند و در اصل یک میز هش فشرده هستند.

هنگامی که اندازه داده های اصلی بزرگ است ، فیلترهای فاخته و شکوفه برای تست عضویت مفید هستند. هر دو آنها فقط از 7 بیت در هر ورودی استفاده می کنند. آنها همچنین در مواردی که قبل از اجرای یک عملیات گرانقیمت توسط یک تست عضویت مجموعه اجتناب شود ، مفید هستند. به عنوان مثال ، قبل از پرسیدن یک پایگاه داده ، می توانید یک تست عضویت تنظیم شده را انجام دهید تا ببینید که شی مورد نظر حتی در پایگاه داده نیز وجود دارد یا خیر.

الگوریتم

پارامترهای فیلتر:
1. دو عملکرد Hash: h1 و h2
2. یک آرایه B با سطل n. سطل i به نام B [i] نامیده می شود.

ورودی: L ، لیستی از عناصری که باید در فیلتر فاخته درج شود.

الگوریتم:
در حالی که L خالی نیست:
    بگذارید x اولین مورد در لیست L. x را از لیست حذف کند.
    اگر B [h1 (x)] خالی باشد:
        x را در B قرار دهید [h1 (x)]
    در غیر این صورت ، اگر B [h2 (x) خالی باشد]:
        x را در B قرار دهید [h2 (x)]
    موارد دیگر:
        بگذارید y عنصر B باشد [h2 (x)].
        y را به L آماده کنید
        x را در B قرار دهید [h2 (x)]

پیاده سازی

اجرای بسیار ساده به نظر می رسد ، بنابراین من تصمیم گرفتم که به آن بپردازم و مقایسه یی از فضا / زمان کارآمد با یک فیلتر شکوفه مقایسه کردم. فیلتر Cuckoo شامل یک جدول هش Cuckoo است که "اثر انگشت" اقلام درج شده را ذخیره می کند. اثر انگشت یک مورد کمی رشته است که از هش آن آیتم حاصل می شود. جدول هش فاخته شامل مجموعه ای از سطل ها است که در آن کالای مورد نیاز برای قرار دادن بر روی دو سطل ممکن بر اساس دو عملکرد هش نقشه برداری می شود. هر سطل را می توان تنظیم کرد تا تعداد متغیر اثر انگشت را ذخیره کند. به طور معمول ، یک فیلتر Cuckoo با اثر انگشت و اندازه سطل آن مشخص می شود. به عنوان مثال ، یک فیلتر فاخته (2،4) اثر انگشت 2 بیتی دارد و هر سطل در جدول هش کوکو می تواند تا 4 اثر انگشت را ذخیره کند.

درج

الگوریتم:

f = اثر انگشت (x)؛
i1 = هش (x)؛
i2 = i1 ⊕ هش (f)؛
اگر سطل [i1] یا سطل [i2] از آن خالی باشد
   f را به آن سطل اضافه کنید؛
   بازگشت انجام شد؛
// باید موارد موجود را جابجا کند.
i = به طور تصادفی i1 یا i2 را انتخاب کنید؛
برای n = 0؛ n 
// هشتگ کامل تلقی می شود؛
بازگشت عدم موفقیت؛

کد:

جستجو کردن

الگوریتم:

f = اثر انگشت (x)؛
i1 = هش (x)؛
i2 = i1 ⊕ هش (f)؛
اگر سطل [i1] یا سطل [i2] آنگاه f دارد
    بازگشت واقعی؛
بازگشت غلط؛

کد:

حذف

الگوریتم:

f = اثر انگشت (x)؛
i1 = هش (x)؛
i2 = i1 ⊕ هش (f)؛
اگر سطل [i1] یا سطل [i2] آنگاه f دارد
   یک نسخه از f را از این سطل بردارید.
   بازگشت واقعی؛
بازگشت غلط؛

کد:

آزمون عملکرد

من از کتابخانه ویل فیتزجرالد برای آزمایش بر روی فیلتر Bloom استفاده کرده ام. جیره FPP (احتمال مثبت کاذب) که برای فیلتر فاخته گرفته شده است ، 0.001 است

پیچیدگی فضایی

با توجه به فیلترهای فاخته و شکوفه ، آنها با احتمال مثبت کاذب متفاوت عمل می کنند. هنگامی که احتمال مثبت کاذب فیلتر کمتر یا مساوی 3٪ باشد ، فیلتر فاخته در هر ورودی بیت کمتری دارد. هنگامی که بالاتر است ، فیلتر شکوفه در هر ورودی کمتری دارد.

پیچیدگی زمان

در حس کردن فاخته ، وارد کردن یک عنصر در بدترین حالت بسیار بدتر از O (1) است زیرا ممکن است موارد زیادی در حین تصادم وجود داشته باشد ، جایی که ما باید یک مقدار را حذف کنیم تا جایی برای ارزش فعلی ایجاد شود. به علاوه ، اگر یک چرخه وجود داشته باشد ، باید کل جدول مجدداً مجدداً باز شود.

انجام تحلیل زمان هر دو فیلتر نتایج زیر را به دست می آورد:

در طول این آزمایش (با در نظر گرفتن کد من ممکن است کاملاً بهینه نشده باشد) ، به نظر می رسد فیلترهای Bloom در پیچیدگی فضا عملکرد بسیار خوبی دارند و فضای کمتری را برای تعداد زیادی از موارد اشغال می کنند. به نظر می رسد که فیلتر فاخته در درج تعداد زیادی از موارد عملکرد بهتری دارد ، اما به دلیل اجرای آن کمی کندتر در جستجوی (زمان جستجو).

استنباط

من واقعاً فکر نمی کنم که کدام فیلتر را توصیه کند ، فکر می کنم هر دو مورد موارد استفاده خاص خود را دارند. فیلترهای Bloom از حذف پشتیبانی نمی کنند ، زیرا هش کردن ضرر و برگشت ناپذیر است. اگرچه شمارش فیلترهای شکوفه آن مشکل را حل می کند ، فیلترهای فاخته در مواردی که به حذف نیاز دارید مفید هستند. البته فیلترهای فاخته هنگام پر بودن خطا خطا می دهند ، و این مزایای خاص خود را دارد ، در حالی که در فیلتر Bloom هیچ کنترلی بر روی ظرفیت وجود ندارد ، فقط روی مجموعه بیت موجود مجدداً مورد تجدید نظر قرار می گیرد.

کد

منابع

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S اگر در آزمون / اجرای اشتباه مشکلی دارید ، لطفاً پیشنهاد / نظرات خود را ترک کنید.