/ / Блок филтър или кукувица хеширане? - алгоритъм, хеш, филтър

Блум филтър или кукувица хеширане? - алгоритъм, хеш, филтър

Кои предпочитате и защо?

И двата вида могат да бъдат използвани за изпълнение на подобни задачи, но съм любопитен да видя какво са използвали хората в действителните приложения и техните мотиви за това.

Отговори:

9 за отговор № 1

В подобни ситуации се използват филтри с разцвет и филтри с кукувице, но има много разлики под тях, които обикновено определят кой е по-добър избор.

Блум филтрите се използват вътрешно в базата даннидвигатели, а именно Apache Cassandra. Причините са, както казаха другите плакати, да се намалят разходите за бавни операции. По принцип всяка операция "прави това може би или определено не съществува" с висока цена може да използва филтър Bloom за намаляване на броя на извършените проверки.

Друг често срещан пример с днешния SaaS моделще бъде отдалечена услуга REST с цена на повикване. Всяко обаждане в приложния програмен интерфейс (API) с двоичен отговор като "това е адрес INVALID" може да използва филтър за разцвет, за да премахне над 90% от дублиращите се заявки! Имайте предвид, че тъй като филтрите Bloom и Cuckoo имат фалшиви положителни знаци, те НЕ са полезни за обратната операция "този адрес е валиден"

Важно е да запомните, че Блум и кукувицафилтрите НЯМА лъжливи негативи. Това прави тези филтри полезни за проверки като "това определено не е или може би спам", но не е полезно за операции, при които фалшивите положителни знаци са неприемливи, като проверка на разрешенията на потребителите. В този аспект те могат да бъдат считани концептуално за обратното на кеш. Както филтърът Bloom / Cucoo, така и кешът се използват главно за намаляване на разходите за скъпи операции с булев отговор, с изключение на кешките, които нямат фалшиви положителни качества и Bloom / Cuckoo нямат фалшиви отрицателни резултати.

Забележителните разлики между кукувицата / цъфтежа включват:

  • Комбинация. Bloom филтрите могат ефективно да се слеят, стига да са създадени със същите параметри. И бързо, и с малко трафик. Ето защо ги виждате често използвани в масивно разпределени системи, като обменяте Bloom филтри е бърз. Кукувичните филтри не са лесно компостируеми, което ги прави по-малко полезни при тези обстоятелства.

  • Фалшива положителна скорост. Кукувичните филтри са по-ефективни в пространството. Много случаи на използване и за двете структури са фокусирани върху ниско ниво на работа в мрежа. При слабия хардуер може да бъде важно постигането на ~ 40% по-висока ефективност на кукувиковите филтри за една и съща фалшиво положителна честота. Референтната реализация в C ++ сортира елементите във всяка кофа за допълнително спестяване на пространство, като се възползва от позицията на елемента в кофата, за да съхранява по-малки отпечатъци. Допълнителните библиотеки, които ще спомена по-късно (включително моите), не изглеждат Ако някой някога използва библиотеката ми, бих могъл да я добавя :).

  • Постоянен фалшив положителен процент. Блум филтрите имат асимптомно по-лоши фалшиво положителни темпове, тъй като надвишават размера им. Можете да продължите да поставяте елементи завинаги, но в крайна сметка фалшивият ви положителен процент ще бъде почти 100%. Филтрите с кукувици, които се основават на хеширането на кукувиците, имат зададен капацитет, където вмъкванията действително ще се провалят. Повтарящото се вмъкване на хешове, които не са произволни, може да доведе до неуспешно вмъкване на кукувически филтри, вероятно далеч преди тяхното ниво на запълване.

  • Speed. Това е субективно и зависи много от хардуера, но кукувичестите филтри обикновено са по-бързи в средния случай (по мое преживяване). Повечето дизайни на Bloom филтри изпълняват две функции за хеш. При използването на сигурни хеш функции, това може да е голямо неблагоприятно въздействие в сравнение с филтрите с кукувица, в които само веднъж са вмъкнали елементи. Кодът, който видях, използва различни хеширащи функции за филтрите Bloom и Cuckoo. Google Guava Bloom използва Murmur3, много други приложения използват SHA1 или нещо друго. Ако хеш сблъсъка може да бъде използван за случая, използвайте случая, уверете се, че библиотеката използва защитен хеш. Важно е да знаете, че филтрите Bloom изискват приблизително постоянно време за вмъкване, докато филтрите с кукувица имат постоянно време в AVERAGE случай. Тъй като филтрите с кукувици се намират в рамките на няколко процента от капацитета, скоростта на вмъкване се забавя значително. Дори и тогава, само скоростта на вмъкване се забавя, всички други операции са постоянно средно време.

  • Гъвкавост. Филтрите за цъфтеж само поддържат вмъкване и съдържат. Филтрите с кукувици допълнително поддържат изтриването и ограниченото броене. В референтния дизайн филтрите с кукувиче могат да определят колко пъти е поставен елемент, до 7 пъти. Блум филтрите могат да определят само да-не. Клауковите филтри също поддържат изтриването на вмъкнати елементи, което е много положително в много случаи на употреба в сравнение с Bloom. Когато използвате филтри Bloom, е доста нормално да пресъздадете филтъра от нулата, когато е "пълен" (изчислената грешна положителна стойност надхвърля прага), тъй като не можете да изтриете старите елементи. Имайте предвид, че повторното създаване на филтъра все още се случва с филтрите с кукувица, когато се вмъкват за да не успеете, така че в зависимост от случая на употреба това може да е мотив.В някои ситуации кукувическите филтри са по-полезни, тъй като можете да изтриете елементи, за да останете в границите на филтъра вместо да ги възстановите.

  • Поддържа. Кукувическите филтри са нови и стабилни библиотеки за много езици просто не съществуват.

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

Безсрамен Plug: Аз съм разработчик на библиотека за кукувиче за Java. CuckooFilter4J , Липсва полу-сортирането на кофата, използвана вхартия, така че ефективността на пространството е малко по-ниска от референтната реализация. В проекта readme имам линкове към други реализации, за които съм наясно, коя структура е по-добра, зависи от вашия случай на използване, но най-вече от това дали е налице солидно изпълнение на кукувичен филтър за вашия език.

Определено трябва да погледнете източникапреди да използвате филтър с кукувица / цъфтеж в производството. Прочетох различни libs, преди да напиша собствения си ... много от тях са имали ограничени размери, поради 32-битови подредени масиви или очевидни проблеми с производителността. Повечето са имали нулеви тестове. Изпълнението на Guava Bloom от Google е с най-доброто качество на кода и тестове (и поддържа 64-битови граници на масива). Единствените недостатъци с Guava's Bloom са, че няма опция за използване на сигурна хеш функция и не е " t с много резба.

В производствена система, която може да искатемного резба за скорост. Отговорът на Guava's Bloom е да направите различен филтър за всяка нишка и да ги комбинирате от време на време. Тъй като кукувиковите филтри не могат да бъдат комбинирани, добавих едновременно threading към моята кукувица филтър библиотека. Другият, който съм наясно, че не са безопасни или не са едновременно.


8 за отговор № 2

Кои предпочитате, вино или сирене?

А филтър цъфтеж е, когато имате ограничено пространство, висока цена на заявката, и предимно отрицателни запитвания.
В този случай, a филтър цъфтеж с 8 бита на ключ и 4 хеш функции дава ти 2,5% фалшиво положително ниво; обработвате почти всички заявки 40 пъти по-бързо отколкото преди, за сметка на 1 байт за ключ.

От друга страна, ако някой от предишните условия не задържат, a хеш таблицата действа като кеш има смисъл, макар че очевидно ще отнеме много повече от един байт на запис :-)

Можете дори да пропуснете твърдите ръбове на кукува хашиш ако това е кеш. Това също така прави проблема с увеличаването на размера на кушет хаш таблици (или нещо различно от линеен хеш).


5 за отговор № 3

Филтър с кукувиче.

"Кукувичен филтър: практически по-добър от Bloom." Бин Фен, Дейвид Андерсън, Майкъл Камински, Майкъл Мицензмашер CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994

От един от авторите " блог:

Позволете ми да опиша един кукувичен филтър и някои от тяхтова, което е в хартията за вас.Ако искате да избегнете техническа дискусия, всичко, което трябва да знаете е, че за сравнително големи размери, за една и съща фалшиво положителна скорост като съответния филтър Bloom, кукувическите филтри използват по-малко пространство от Bloom филтри, са по-бързи при търсенето (но по-бавно при вмъквания / за конструиране) и удивително позволяват и изтривания на ключове (които Bloom филтрите не могат да направят.) Ако искате да разгледате код, github хранилище за вас с код за кукувични филтри.


2 за отговор № 4

Предпочитам кукувическото хеширане. Аз съм предпазлив от фалшивите позитиви, които могат да се появят с филтри с разцвет при по-високи фактори за запълване.
Използвахме хеширане с кукувица в приложение, в което имахме много големи маси и имаше проблеми с паметта. Моля, вижте моята библиотека eCollections в http://codeplex.com/ecollections за реализирането на вариант за хеширане на кукувицата.

Поздрави,


0 за отговор № 5

Ако мога да толерирам фалшивите позитиви и пространството е от решаващо значение, използвам филтър Bloom, защото отнема по-малко място. В противен случай използвам хеш.