🐤Cuckoo Filter: удаление через fingerprints/вытеснение и поиск через XOR Дорогой читатель подкинул другие варианты вероятностных фильтров получше, ничего не могу поделать, разбираем Cuckoo Filter... Фишка этого фильтра в том, что в отличии от установки n бит в общем битсете, как в Bloom Filter, он хранит отрезок хеша - fingerprint (или fp) и размещает его в одном из двух возможных бакетов. Если оба бакета заняты, используется алгоритм cuckoo-kicks (вытеснения). Для каждого ключа вычисляется fp и два индекса бакетов, где fp может содержаться. Второй индекс считается через XOR: операция обратима, поэтому, зная fp и один индекс, можно однозначно восстановить второй. Это ключевое свойство, на котором держится весь механизм «вытеснения». Если оба бакета заняты, фильтр вытесняет один рандомный fp в его другой бакет через XOR, освобождая слот для нового. Процесс повторяется по цепочке, пока не найдётся свободный слот или не будет достигнут лимит вытеснений. И это быстро, потому что поиск (который предшествует вставке) проверяет не более двух бакетов, то есть по факту выполняем проход по двум кэш-линиям. Внутри каждый бакет содержит около 4 слотов, поэтому даже линейный поиск будет дешёвым. В отличии от bloom фильтра, cuckoo 1) имеет такой же поиск за константу, но за max 2 шага, а не n хеш-функций 2) поддерживает удаление (в Bloom это возможно только через счётчики, что усложняет реализацию и дает рост памяти) Структура держится на - fingerprint = несколько бит от перемешанного хеша (обычно 8 бит) В HAMT используются последовательные фрагменты всего хеша и за счёт уровней накапливается энтропия (= разброс по нодам). В Cuckoo Filter уровней нет, поэтому берётся один короткий отрезок, который сначала перемешивают, чтобы он было более случайным. Тут берем просто модуль, сразу исключаем ноль тк он будет обозначать пустой слот fingerprint := uint8(hash.Sum32()%255 + 1) - массиве бакетов - групп по 4 fingerprint, чтобы помещаться в кешлинию Далее индексы: Первый вычисляем напрямую из хеша ключа: func (cf CuckooFilter) index1(key []byte) uint32 { h := fnv.New32a() h.Write(key) return h.Sum32() % uint32(len(cf.buckets)) } Второй вычисляется из первого и fingerprint через XOR: func (cf CuckooFilter) index2(index1 uint32, fp uint8) uint32 { // перемешиваем через умножение на MurmurHash2 h := uint32(fp) 0x5bd1e995 return int((uint32(index1) ^ h) % uint32(len(cf.buckets))) } Итого для каждого ключа существует ровно два возможных бакета, и он всегда лежит в одном из них. Поиск и вставка Оба метода начинается одинаково с нахождения fp и двух индексов: func (cf CuckooFilter) Contains(key []byte) bool { // находим fp и два индекса fp, i1, i2 := cf.findIndexes(key) return cf.buckets[i1].has(fp) || cf.buckets[i2].has(fp) } При вставке: если хотя бы один бакет свободен - кладем в первый свободный слот по порядку наш fp. Если оба бакета переполнены - начинается вытеснение fingerprint. Cuckoo-kicks: вытеснения - в одном из бакетов выбраем рандомный fp, на его место кладем новый - вытесненный fp отправляем в его альтернативный бакет (через XOR) - если и там нет места, производим шаг 1 и так по цепочке «выталкиваем» fp и кладем в бакет по его другому индексу, пока не найдем свободное место Чтобы не было бесконечного цикла нужно следить за load factor и ограничить число вытеснений: func (cf *CuckooFilter) Insert(key []byte) bool { fp, i1, i2 := cf.findIndexes(key) if cf.buckets[i1].insert(fp) || cf.buckets[i2].insert(fp) { return true } i := i1 for n := 0; n < cf.maxKicks; n++ { // возвращаем вытестенный fp, на его место ставим наш fp = cf.buckets[i].swapRandom(fp) i = cf.index2(i, fp) if cf.buckets[i].insert(fp) { return true } } return false } Как и в Bloom, тут есть ложноположительные кейсы, и частота их зависит от схожих параметров типо длины fp, n бакетов, допустимого % заполненности. По итогу Cuckoo Filter действительно заметно удобнее Bloom Filter, ос