Фильтры Блума и фильтры с кукушкой используются в похожих ситуациях, но под ними много различий, которые обычно определяют, какой вариант лучше.
Фильтры Блума используются внутри движков баз данных, в частности, Apache Cassandra. Причины, как говорили другие авторы, заключаются в том, чтобы снизить стоимость медленных операций набора. По сути, любая операция «может ли это быть или, безусловно, не существует» с высокой стоимостью может использовать фильтр Блума для уменьшения количества выполненных проверок.
Другим распространенным примером с современной моделью SaaS может быть удаленный REST-сервис с платой за звонок. Любой вызов API с бинарным ответом, например, «является ли этот адрес недействительным», может использовать фильтр Блума, чтобы исключить более 90% повторяющихся запросов! Обратите внимание, что, поскольку фильтры Блума и Кукушки имеют ложные срабатывания, они НЕ полезны для обратной операции "этот адрес VALID"
Важно помнить, что фильтры Bloom и Cuckoo НЕ содержат ложных негативов. Это делает эти фильтры полезными для проверок типа «определенно нет или, может быть, спам», но бесполезно для операций, где ложные срабатывания недопустимы, например, для проверки прав доступа пользователей. В этом аспекте их можно концептуально считать противоположностью кеша. Фильтр Bloom / Cuckoo и кэши используются главным образом для снижения затрат на дорогостоящие операции с логическим ответом, за исключением того, что у кэшей нет ложных срабатываний, а у Bloom / Cuckoo нет ложных отрицательных.
Заметные различия между Cuckoo / Bloom включают в себя:
Combination. Фильтры Блума могут быть эффективно объединены, если они созданы с одинаковыми параметрами. И быстро, и с небольшой пропускной способностью. Вот почему вы видите, что они часто используются в массово распределенных системах, замена фильтров Bloom происходит быстро. Фильтры с кукушкой нелегко компонуются, что делает их менее полезными в этих условиях.
Неверно положительный показатель. Фильтры с кукушкой более экономичны. Многие варианты использования для обеих структур ориентированы на низкоуровневую сеть. На слабом оборудовании может быть важно повышение эффективности фильтров Cuckoo на ~ 40% при той же частоте ложных срабатываний. Эталонная реализация в C ++ сортирует элементы в каждом сегменте для дополнительной экономии места, используя преимущество позиции элемента в сегменте для хранения меньших отпечатков пальцев. Дополнительные библиотеки, которые я упомяну позже (включая мою), похоже, не делают этого. Если кто-нибудь когда-нибудь использует мою библиотеку, я мог бы добавить ее:).
Постоянный уровень ложных срабатываний. Фильтры Блума имеют асимптотически худшие показатели ложных срабатываний, поскольку они превосходят свой расчетный размер. Вы можете продолжать вставлять предметы вечно, но в конечном итоге ваш уровень ложных срабатываний составит почти 100%. Фильтры с кукушкой, основанные на хешировании кукушки, имеют установленную емкость, при которой вставки фактически не будут выполняться. Повторная вставка неслучайных хэшей элементов может привести к сбою фильтров Cuckoo, возможно, задолго до их заданного уровня заполнения.
Скорость. Это субъективно и во многом зависит от аппаратного обеспечения, но фильтры Cuckoo в среднем работают быстрее (по моему опыту). Большинство конструкций фильтров Bloom запускают хэш-функцию дважды. Особенно при использовании безопасных хеш-функций это может быть большим препятствием по сравнению с фильтрами Cuckoo, которые хешируют элементы только один раз. Код, который я видел, использует различные функции хеширования для фильтров Bloom и Cuckoo. Guava Bloom от Google использует Murmur3, многие другие реализации используют SHA1 или что-то еще. Если для вашего случая могут использоваться коллизии хеша, убедитесь, что библиотека использует безопасный хеш. Важно знать, что фильтрам Bloom требуется приблизительно постоянное время для вставки, в то время как фильтры Cuckoo имеют постоянный случай AVERAGE. Поскольку фильтры Cuckoo попадают в несколько процентов от емкости, скорость вставки значительно замедляется. Даже тогда замедляется только скорость вставки, все остальные операции имеют постоянное среднее время.
Гибкость. Фильтры Блума поддерживают только вставки и содержат. Фильтры с кукушкой дополнительно поддерживают удаление и ограниченный подсчет. В эталонном дизайне фильтры Cuckoo могут определять, сколько раз элемент был вставлен, до 7 раз. Фильтры Блума могут определять только да-нет. Фильтры с кукушкой также поддерживают удаление вставленных элементов, что является большим плюсом во многих случаях использования по сравнению с Bloom. При использовании фильтров Блума довольно стандартно воссоздавать фильтр с нуля, когда он «полный» (предполагаемая частота ложных срабатываний превышает пороговое значение), поскольку вы не можете удалять старые элементы. Обратите внимание, что восстановление фильтра по-прежнему происходит с фильтрами Cuckoo, когда вставки начинают давать сбой, поэтому в зависимости от варианта использования это может быть спорным. В определенных ситуациях фильтры Cuckoo более полезны, так как вы можете удалять элементы, чтобы они не выходили за пределы фильтра, а не перестраиваться.
Поддержка. Фильтры с кукушкой - это новые и стабильные библиотеки для многих языков, которых просто не существует.
Самым большим преимуществом фильтров Bloom является то, что они имеют более развитую поддержку библиотек на большинстве языков. Математика за фильтрами Блума также лучше понята учеными. Большинство характеристик фильтров Cuckoo были определены опытным путем, тогда как фильтры Bloom имеют надежную числовую основу. Это исключает фильтры Cuckoo для систем реального времени и критически важных систем, которые должны проверять свою производительность, хотя экспериментальные данные показывают, что фильтры Cuckoo работают лучше в большинстве случаев.
Бесстыдный плагин: я разработчик библиотеки фильтров Cuckoo для Java. CuckooFilter4J . В нем отсутствует полусортировка ведра, используемая в статье, поэтому эффективность использования пространства несколько ниже, чем у эталонной реализации. В проекте readme у меня есть ссылки на другие реализации, которые мне известны. Какая структура лучше, зависит от вашего варианта использования, но в основном от того, существует ли для вашего языка надежная реализация фильтра Cuckoo.
Вы обязательно должны взглянуть на источник, прежде чем использовать фильтр Cuckoo / Bloom в производстве. Я читал различные библиотеки перед тем, как написать свой собственный ... у многих из них были ограничения по размеру из-за 32-битных массивов или очевидных проблем с производительностью. У большинства были нулевые тесты. Реализация Guava Bloom от Google показала лучшее качество кода и тестирований (и поддерживает ограничения на 64-битные массивы) Единственным недостатком Bloom в Guava является то, что он не имеет возможности использовать безопасную хеш-функцию и не является многопоточным.
В производственной системе вам может потребоваться многопоточность для скорости. Ответ для Блума Гуавы состоит в том, чтобы сделать разные фильтры для каждого потока и иногда комбинировать их. Поскольку фильтры Cuckoo не могут быть объединены, я добавил параллельные потоки в свою библиотеку фильтров Cuckoo. Другой, о котором я знаю, не является потокобезопасным или не является параллельным.