Чтобы решить проблему, связанную с тем, что фильтр Блума не может удалять элементы, был создан фильтр с кукушкой. Автор статьи «Фильтр с кукушкой: лучше, чем Блум» подробно сравнивает фильтр с кукушкой и фильтр Блума. По сравнению с фильтром с кукушкой фильтр Блума имеет следующие недостатки: слабая производительность запросов, низкая эффективность использования пространства, отсутствие поддержки обратных операций (удаления) и поддержки подсчета.
Производительность запросов низкая, поскольку фильтру Блума необходимо использовать несколько хеш-функций для обнаружения нескольких разных местоположений в растровом изображении, которые охватывают большой объем памяти и приводят к низкой частоте попаданий в строку кэша ЦП.
Низкая эффективность использования пространства связана с тем, что при том же уровне ложных срабатываний коэффициент использования пространства фильтра с кукушкой значительно выше, чем у фильтра Блума, и пространство может быть сэкономлено примерно на 40%. Однако фильтр Блума не требует, чтобы длина растрового изображения была равна 2, а фильтр кукушки должен иметь это требование. С этого момента кажется, что фильтр Блума более масштабируем в пространстве.
Проблема отсутствия поддержки операции обратного удаления действительно затрагивает слабое место фильтра Блума. В динамической системе элементы всегда приходят и уходят. Фильтры Блума — как кляксы, когда ты придешь, останутся следы, и ты не сможешь их убрать, даже если уйдешь. Например, в вашей системе осталось всего 1кВт элементов, а в целом пришли сотни миллионов текущих элементов, и фильтр Блума очень беспомощен, он будет хранить там следы этих потерянных элементов навсегда. Со временем этот фильтр будет становиться все более и более переполненным, пока однажды вы не обнаружите, что его уровень ложных срабатываний слишком высок, и вам придется перестроить его.
Фильтр с кукушкой утверждает, что решает эту проблему в статье, он может эффективно поддерживать операцию обратного удаления. И используйте это в качестве важного аргумента в пользу продажи, чтобы соблазнить вас отказаться от фильтра Блума и использовать вместо него фильтр с кукушкой.
Но через некоторое время исследований я обнаружил, что фильтр с кукушкой не так хорош, как утверждается. Поддерживаемая им операция обратного удаления настолько бесполезна, что вы вообще не можете использовать эту функцию. Прежде чем подробно объяснить читателю эту проблему, пусть читатель подробно объяснит принцип работы фильтра с кукушкой.
Кукушка Хэш
Фильтр кукушки получен из алгоритма хеширования кукушки, а алгоритм хеширования кукушки получен из жизни - кукушка, которая любит "голуби занимают гнездо сороки". Кукушки любят распущенность (свободу) и никогда не строят себе гнезд. Он откладывает свои яйца в чужие гнезда и просит других помочь вылупиться. После того, как кукушонок вырвался из скорлупы, поскольку кукушонок был относительно крупным, он выдавил из гнезда остальных детей (еще яйца) приемной матери - упал с высоты и погиб.
Простейшая хэш-структура с кукушкой представляет собой структуру одномерного массива с двумя алгоритмами хеширования, которые отображают входящие элементы в две позиции в массиве. Если одна из двух позиций пуста, то можно поставить элемент напрямую. Но если обе позиции заняты, ему придется «занять гнездо сороки», пнуть одну наугад, а затем занять позицию самостоятельно.
p1 = hash1(x) % l
p2 = hash2(x) % l
В отличие от кукушки алгоритм хеширования кукушки поможет этим жертвам (выжатым яйцам) найти другие гнезда. Поскольку каждый элемент можно разместить в двух местах, если в любом из них есть пустое место, его можно вставить. Так что это грустное, сжатое яйцо будет проверять, свободно ли еще одно его собственное место, и если это так, он будет счастлив, если переедет туда. Но что, если эту должность также занимает кто-то другой? Ну а потом опять "оккупирует сороки гнезда" и переложит роль жертвы на других. Затем новая жертва повторяет процесс, пока все яйца не найдут свои гнезда.
Как сказал Лу Синь: «Займите свое гнездо и дайте выбраться другим!»
Но будет проблема, то есть если массив будет слишком переполнен, он будет продолжать пинать сотни раз без остановки, что серьезно скажется на эффективности вставки. В это время хэш с кукушкой установит порог.Когда непрерывное занятие гнезда превышает определенный порог, массив считается почти полным. В это время его нужно расширить и переставить все элементы.
Будет еще одна проблема, и это возможность цикла выполнения. Например, для двух разных элементов две позиции после хэша абсолютно одинаковы, и на данный момент проблем с каждой из них нет. Но в это время приходит третий элемент, и его позиция после хэша такая же, как и у них, очевидно, в это время будет цикл выполнения. Однако вероятность наличия трех разных элементов в одной и той же позиции после двойного хеширования не очень высока, если только ваш алгоритм хеширования не слишком нарушен.
Отношение алгоритма хеширования кукушки к этому циклу выполнения состоит в том, что массив слишком переполнен и его нужно расширять (на самом деле это не так).
оптимизация
Среднее использование пространства вышеописанным алгоритмом хэширования с кукушкой невелико, всего около 50%. При этом проценте количество последовательных запусков очень быстро превышает пороговое значение. Ценность такого хэш-алгоритма не очевидна, поэтому его нужно улучшать.
Одним из улучшенных решений является увеличение хэш-функции, чтобы у каждого элемента было не только два гнезда, но и три гнезда, и четыре гнезда. Это может значительно снизить вероятность столкновения и увеличить использование пространства примерно до 95%.
Еще одно улучшение состоит в том, чтобы повесить несколько мест на каждую позицию массива, так что даже если два элемента хэшируются в одной и той же позиции, нет необходимости немедленно «занимать гнездо», потому что есть несколько мест, вы можете не стесняться сидеть один. Пробег требуется только в том случае, если несколько мест заняты. Очевидно, что это также значительно уменьшит количество прогонов. Использование пространства в этой схеме составляет всего около 85%, но эффективность запросов будет очень высокой.Несколько рабочих мест в одном и том же месте являются смежными в пространстве памяти, что может эффективно использовать кэш ЦП.
Таким образом, более эффективным решением является объединение двух приведенных выше улучшенных решений, таких как использование 4 хеш-функций и размещение 2 рабочих мест на каждой позиции. Таким образом, можно получить как эффективность использования времени, так и эффективность использования пространства. Такая комбинация может даже увеличить использование пространства на 99%, что является очень впечатляющей эффективностью использования пространства.
фильтр с кукушкой
Фильтр с кукушкой такой же, как структура хэша с кукушкой, это также одномерный массив, но отличается от хеша с кукушкой, хеш с кукушкой будет хранить весь элемент, а фильтр с кукушкой будет хранить только информацию об отпечатке элемента (несколько биты, похожие на фильтр Блума). Здесь фильтр жертвует точностью данных ради эффективности использования пространства. Именно потому, что хранится информация об отпечатке элемента, существует частота ложных срабатываний, которая точно такая же, как у фильтра Блума.
Во-первых, фильтр с кукушкой по-прежнему использует только две хеш-функции, но в каждой позиции может быть несколько мест. Выбор этих двух хеш-функций особенный, поскольку в фильтре может храниться только информация об отпечатках пальцев. При запуске отпечатка пальца в этой позиции необходимо вычислить другую двойную позицию. Для вычисления этой двойной позиции нужен сам элемент.Вспомним предыдущую формулу расчета позиции хеша.
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l
Мы знаем отпечатки p1 и x, и нет возможности напрямую вычислить p2.
специальная хэш-функция
Гениальная часть фильтра с кукушкой заключается в том, что он разрабатывает уникальную хеш-функцию, так что p2 можно вычислить напрямую на основе p1 и отпечатков элементов без необходимости полного элемента x.
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 异或
Как видно из приведенной выше формулы, когда мы знаем fp и p1, мы можем напрямую вычислить p2. Точно так же, если мы знаем p2 и fp, мы можем напрямую вычислить p1 — двойственность.
p1 = p2 ^ hash(fp)
Таким образом, нам вообще не нужно знать, является ли текущая позиция p1 или p2, нам просто нужно XOR текущей позиции и хеш (fp), чтобы получить двойную позицию. И вам нужно только убедиться, что hash(fp) != 0, чтобы убедиться, что p1 != p2, так что не будет проблем с тем, чтобы ударить себя ногой и вызвать бесконечный цикл.
Вы можете спросить, почему хеш-функции здесь не нужно по модулю длины массива? На самом деле это требуется, но фильтр с кукушкой требует, чтобы длина массива была в степени 2, поэтому по модулю длина массива эквивалентна получению последних n бит хеш-значения. При выполнении операции исключающее ИЛИ просто игнорируйте остальные биты, кроме младших n битов. Сохранение рассчитанной позиции p в младших n битах является конечной двойной позицией.
// l = power(2, 8)
p_ = p & 0xff
структура данных
Для простоты будем считать, что отпечаток занимает один байт, а каждая позиция имеет 4 места.
type bucket [4]byte // 一个桶，4个座位
type cuckoo_filter struct {
buckets [size]bucket // 一维数组
nums int // 容纳的元素的个数
kick_max // 最大挤兑次数
}
Алгоритм вставки
Вставка должна учитывать наихудший сценарий, который представляет собой цикл выполнения. Поэтому вам нужно установить максимальный предел пробега
def insert(x):
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)
// 尝试加入第一个位置
if !buckets[p1].full():
buckets[p1].add(fp)
nums++
return true
// 尝试加入第二个位置
if !buckets[p2].full():
buckets[p2].add(fp)
nums++
return true
// 随机挤兑一个位置
p = rand(p1, p2)
c = 0
while c < kick_max:
// 挤兑
old_fp = buckets[p].replace_with(fp)
fp = old_fp
// 计算对偶位置
p = p ^ hash(fp)
// 尝试加入对偶位置
if !buckets[p].full():
buckets[p].add(fp)
nums++
return true
c++
return false
алгоритм поиска
Поиск очень простой, можно узнать, есть ли в ведрах двух хеш-позиций собственный отпечаток пальца.
def contains(x):
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)
return buckets[p1].contains(fp) || buckets[p2].contains(fp)
удалить алгоритм
Алгоритм удаления аналогичен алгоритму поиска, и он также очень прост, можно стереть отпечатки пальцев в двух ведрах.
def delete(x):
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)
ok = buckets[p1].delete(fp) || buckets[p2].delete(fp)
if ok:
nums--
return ok
очевидная слабость
Все идет нормально! Фильтр с кукушкой выглядит идеально! Доступны как функция удаления, так и функция получения количества элементов, которая намного мощнее фильтра Блума, и логика вроде бы очень простая, а вышеописанное делается всего несколькими строчками кода. Если операция вставки возвращает false, значит, ее нужно расширить, что тоже очень очевидно.
Но подумайте, что, если фильтр с кукушкой делает несколько последовательных вставок одного и того же элемента?
Исходя из логики выше, можно не сомневаться, что отпечаток элемента займет все места в обоих положениях — 8 мест. Значения на этих 8 сиденьях одинаковые, и все они являются отпечатками этого элемента. Если вы продолжите вставку, произойдет немедленный цикл выполнения. Из слота p1 в слот p2 и из слота p2 в слот p1.
Может быть, вы думаете, можно ли сделать проверку перед вставкой, чтобы спросить, существует ли уже элемент в фильтре? Это решает проблему, и вставка одного и того же элемента не вызывает цикл выполнения. Однако будет велика вероятность ошибочного удаления при удалении. Поскольку вероятность того, что разные элементы будут хешированы в одну и ту же позицию, по-прежнему очень высока, а отпечаток состоит только из одного байта, существует 256 возможностей, и очень вероятно, что один и тот же отпечаток появится в одной и той же позиции. Если два элемента имеют одинаковую хеш-позицию и один и тот же отпечаток, то эта проверка вставки считает их равными.
Вставьте x, который считается содержащим y при проверке. Из-за этого механизма проверки будет сохранен только один отпечаток (отпечаток x). Тогда удаление y также эквивалентно удалению x. Это приводит к более высокому уровню ложных срабатываний.
Газета нас не обманула, она тоже упомянула об этом. (Читатель не должен понимать вторую половину предложения)
В реальных приложениях почти невозможно гарантировать, что элемент не будет вставлен заданное количество раз. Если вы думаете, что можете это сделать, подумайте, как это сделать! Вам все еще нужно поддерживать внешний словарь, чтобы отслеживать, сколько раз был вставлен каждый элемент? Как насчет места для хранения этого внешнего словаря?
Поскольку операция удаления не может быть полностью поддержана, невозможно более точно оценить количество внутренних элементов.
доказывать
Ниже мы используем библиотеку фильтров с кукушкой с открытым исходным кодом, чтобы доказать приведенный выше вывод.
go get github.com/seiflotfy/cuckoofilter
Этот фильтр с кукушкой хранит информацию об отпечатках пальцев для каждого элемента в виде одного байта, и в одной и той же позиции будет 4 места. Пробуем вставить в него один и тот же элемент 15 раз.
package main
import (
"fmt"
"github.com/seiflotfy/cuckoofilter"
)
func main() {
cf := cuckoo.NewFilter(100000)
for i := 0; i < 15; i++ {
var ok = cf.Insert([]byte("geeky ogre"))
fmt.Println(ok)
}
}
-------
true
true
true
true
true
true
true
true
false
false
false
false
false
false
false
Мы обнаружили, что при его вставке один и тот же элемент вставляется только до 8 раз. Каждый последующий возврат к false будет проходить через сотни циклов выполнения, пока не будет достигнуто максимальное количество запусков.
Если 8 мест в обоих положениях хранят один и тот же элемент, то потеря пространства также очень серьезна, а эффективность использования пространства напрямую сокращается до 1/8, что вообще не может конкурировать с фильтром Блума.
Если операция удаления не поддерживается, то фильтр с кукушкой по-прежнему сопоставим с точки зрения эффективности использования пространства. Это действительно немного лучше, чем то, что может сделать фильтр Блума, но опять же эффективность использования пространства снижается из-за 2-экспоненциального требования к пространству для фильтра с кукушкой.
Похожие материалы
Фильтровальная бумага с кукушкой:Cuckoo Filter: Practically Better Than Bloom
Модуль фильтра Redis с кукушкой:GitHub.com/Kristo Method — ИТ…
Самая влиятельная C-библиотека фильтров с кукушкой:GitHub.com/efficient/ из…