CUCKOO срещу BLOOM филтър от гледна точка на Gopher

В тази статия се опитвам да внедря и тествам ефективността на филтър за кукувица над филтър за цъфтеж. (Прочетете предишната публикация на акорд DHT, внедрявайки разпределена хеш таблица в Golang)

Въведение

Вероятностните структури от данни са много полезни, особено при обработка на големи масиви от данни. Повечето пъти, докато работите върху информационната страна на нещата, бихте искали да направите просто запитване „дали елементът не присъства“ или „е елементът вече е налице“, докато обработвате данните в реално време. Кажете, че искате да отговорите на запитвания в реално време, като например брой уникални ips, най-честите ips, ако рекламата вече е била предоставена на потребителя, използвайки вероятностни структури от данни, осигуряват пространствено ефективен начин да отговорите на тези заявки. Типичният подход към такива заявки би бил използването на HashMap или HashTable или съхраняването му да е някакъв външен кеш (като redis), но проблемът е в големите набори от данни, тези прости структури от данни не могат да се поберат в паметта. Това е мястото, където вероятностните структури от данни влизат в игра поради своите пространствени и времеви предимства.

Пример Използване на случаи

  • Google Bigtable, Apache HBase и Apache Cassandra, и Postgresql използват филтрите Bloom, за да намалят търсенето на дискове за несъществуващи редове или колони. Избягването на скъпи издирвания на дискове значително увеличава производителността на операция по заявка на база данни.
  • Medium използва филтри Bloom, за да провери дали дадена статия вече е препоръчана на потребител
  • Ethereum използва филтри Bloom за бързо намиране на регистрационни файлове на блокчейн Ethereum
  • Уеб браузърът Google Chrome използваше филтър Bloom за идентифициране на злонамерени URL адреси. Всеки URL адрес първо се проверява срещу локален филтър на Bloom и само ако филтърът Bloom върне положителен резултат, беше пълна проверка на изпълнения URL адрес (и потребителят предупреди, ако и това върне положителен резултат)

Какво има в кукувицата?

Използвахме филтри за цъфтеж на много места, за да отговаряме на такива запитвания в платформата за данни. Наскоро попаднах на тази книга на филтъра за кукувици, която предизвика моя интерес. Самото заглавие гласи: „Филтър за кукувица: На практика по-добър от цъфтеж“, затова реших да го проверя.

Кукувичните филтри подобряват дизайна на цъфтящия филтър, като предлагат изтриване, ограничено броене и ограничена фалшива положителна вероятност, като в същото време поддържат подобна пространствена сложност. Те използват хешуване на кукувици за разрешаване на сблъсъци и по същество са компактна хеш-маса за кукувици.

Филтрите за кукувици и цветчета са полезни за задаване на тестове за членство, когато размерът на оригиналните данни е голям. И двамата използват само 7 бита на запис. Те също така са полезни, когато скъпа операция може да бъде избегната преди изпълнението чрез зададен тест за членство. Например, преди да се запитате в база данни, може да се направи тест за набор членство, за да се види дали желаният обект е дори в базата данни.

алгоритъм

Параметри на филтъра:
1. Две функции на хеш: 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, която съхранява „пръстовите отпечатъци“ на поставените елементи. Отпечатъкът на даден елемент е битов низ, получен от хеша на този елемент. Хеш-таблицата за кукувица се състои от масив от кофи, където елементът, който трябва да бъде вмъкнат, се картографира на две възможни кодове въз основа на две хеш-функции. Всяка кофа може да бъде конфигурирана да съхранява променлив брой отпечатъци. Обикновено филтър за кукувица се идентифицира по пръстов отпечатък и размер на кофата. Например, (2,4) филтър за кукувица съхранява пръстови отпечатъци с дължина 2 бита и всяка кофа в таблицата с хеш-кукувица може да съхранява до 4 пръстови отпечатъка.

вмъкване

алгоритъм:

f = пръстов отпечатък (x);
i1 = хеш (х);
i2 = i1 ⊕ хеш (f);
ако кофата [i1] или кофата [i2] има празен запис
   добавете f към тази кофа;
   връщане Готово;
// трябва да преместят съществуващите елементи;
i = произволно изберете i1 или i2;
за n = 0; n 
// Hashtable се счита за пълен;
отказ за връщане;

Код:

Търсене

алгоритъм:

f = пръстов отпечатък (x);
i1 = хеш (х);
i2 = i1 ⊕ хеш (f);
ако кофата [i1] или кофата [i2] има f тогава
    връщане Вярно;
връщане False;

Код:

Изтрий

алгоритъм:

f = пръстов отпечатък (x);
i1 = хеш (х);
i2 = i1 ⊕ хеш (f);
ако кофата [i1] или кофата [i2] има f тогава
   премахнете копие на f от тази кофа;
   връщане Вярно;
връщане False;

Код:

Тест за представяне

Използвах библиотеката на Уил Фицджералд за теста на филтъра 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 Ако откриете нещо нередно с тестовете / внедряването, не се колебайте да оставите своето предложение / коментари.