Cuckoo filters: probabilistic с deletion

Зачем

Bloom filter не поддерживает delete. Если вы попробуете «убрать» элемент, обнулив его k bits, то сломаете все другие keys, которые делят эти bits — нарушите святое правило фильтра: no false negatives. Counting Bloom (4-bit счётчики вместо одиночных bits) решает проблему за 4x памяти — дорого.

А workload часто требует именно удаления: CDN-edge выкидывает items по TTL, allow/deny lists меняются, rolling membership в стриминговых данных. Для таких задач нужен фильтр, который умеет всё — add / exists / delete — и при этом не жирнее Bloom.

Cuckoo filter (Fan, Andersen, Kaminsky, Mitzenmacher, CoNEXT 2014) решает три задачи сразу:

• Delete работает — просто обнуляем fingerprint в slot. Никакой коррупции.
• Меньше памяти при FPR ≤3% — ~9 bits/element при ε=3%, ~14 bits при ε=0.1%.
• Cache locality лучше — lookup читает 1-2 cache lines (2 bucket'а), Bloom читает k=7 random bits.

Цена — сложнее реализация, insert может fail при load >95%, и нет dynamic resize.

Mental model

Cuckoo filter = hash table из buckets, каждый bucket держит несколько коротких fingerprints (хэшей элемента, 8-12 bits). Каждый element имеет два candidate-bucket'а. Lookup проверяет оба. Insert при конфликте «выселяет» существующий fingerprint в его альтернативный bucket — отсюда «cuckoo» (как кукушка выталкивает яйца из чужого гнезда).

Ключевой трюк — partial-key cuckoo hashing: альтернативный bucket вычисляется как i2 = i1 XOR h(fingerprint). Это значит, что мы можем «переключаться» между bucket'ами зная только fingerprint, без оригинального key. В классическом cuckoo hashing нужен сам key для recompute — здесь хватает fingerprint, что и даёт фиксированный размер storage.

Insert(x):
  fp = fp(x)
  i1 = h(x) mod m
  i2 = i1 XOR h(fp) mod m
  if bucket[i1] свободен: insert; return
  if bucket[i2] свободен: insert; return
  # оба заняты → cuckoo eviction
  for kick in 1..500:
    swap fp с random slot в выбранном bucket
    bucket = bucket XOR h(evicted_fp)
    if bucket свободен: insert; return
  return FAIL  # filter «полный», нужен rebuild

Lookup(x):  fp в bucket[i1] OR fp в bucket[i2]
Delete(x):  убрать одно вхождение fp в bucket[i1] или bucket[i2]

Что показывает диаграмма

На диаграмме — три слоя: Client → App (RAM, query engine) → CF (cuckoo filter) → Buckets. Cuckoo filter сидит в RAM рядом с приложением: типичная сцена — Snowflake-style query coordinator, который перед чтением 5MB micro-partition спрашивает CF «есть ли тут id=X?» и пропускает партиции, где CF говорит «definitely no».

Bucket-слой показан тремя нодами: bucket[i1] (primary), bucket[i2] (alternate), bucket[alt] (куда улетит выселенный fingerprint в сценарии с kick chain). В реальности m таких bucket'ов десятки тысяч и более — это просто визуализация двух candidate-позиций для одного элемента.

Edges: CF.ADD / EXISTS / DEL от клиента, потом fingerprint и индексы внутрь CF, дальше к buckets — h(x) mod m для primary, i1 XOR h(fp) для alternate, и kick chain для каскадного выселения.

Сценарии

▶Walkthrough: insert-happy (not found)

Самый частый путь: один из двух candidate bucket'ов имеет свободный slot, fingerprint туда записывается, готово. Одна cache-line write, ~100ns. Cuckoo filter старается жить именно здесь — пока load factor ≤70%, kicks почти не случаются.

▶Walkthrough: insert-kick (not found)

Когда оба bucket'а full, начинается «cuckoo dance»: выбираем random bucket, выселяем оттуда random fingerprint, кладём наш на его место. Выселенный fingerprint летит в свой alternate (i XOR h(fp)), и если там тоже full — выселяет кого-то ещё. Каскад продолжается до MAX_KICKS (типично 500). Это amortized O(1), но worst-case может стать миллисекундами при load >95% — и в худшем случае insert fail.

▶Walkthrough: lookup-hit (not found)

Read fingerprint, вычисли i1 и i2, прочитай bucket[i1] — match, return TRUE. Одна cache line, ~50ns. Это и есть главное преимущество в latency: Bloom читает k=7 random bits, разбросанных по всему bit-array, что выливается в 7 cache-line misses под нагрузкой.

▶Walkthrough: lookup-miss (not found)

Если в i1 не нашли — обязательно проверяем i2 (partial-key cuckoo гарантирует, что элемент мог быть выселен в alternate). Обе пусты → return FALSE. Гарантия: если CF говорит «нет», то нет (no false negatives). Если говорит «да» — может быть false positive (~3% при b=4, f=8).

▶Walkthrough: delete (not found)

Главный сценарий «зачем мы вообще это взяли вместо Bloom». Найдём fingerprint в одном из двух bucket'ов → обнулим slot → готово. Никакой коррупции других keys. Bloom такое сделать не может — потому что bits в Bloom share между keys, и unset любого bit испортит все keys, которые этот bit устанавливали.

Важный нюанс: удалять можно только если элемент действительно был вставлен. Если вы попробуете delete элемента, которого не было, и его fingerprint случайно совпадёт с чужим (FP probability) — вы удалите чужой fingerprint. Поэтому delete без предварительного EXISTS — рискованно.

▶Walkthrough: vs-bloom (not found)

Сравнительная таблица в одном сценарии: где Cuckoo, где Bloom. Память почти одинакова при ε=1%, но CF выигрывает при ε≤0.1% и проигрывает при ε>3%. Lookup latency — CF лучше всегда (cache locality). Insert — Bloom никогда не fails, CF может. Delete — только CF. Resize — никто.

▶Walkthrough: real-uses (not found)

Production-показ: RedisBloom (CF.RESERVE / ADD / EXISTS / DEL), Snowflake (micro-partition pruning, сейчас уже Xor filters в новых версиях), Apache Kudu (column predicate filtering), CDN edge (TTL-based eviction), TiKV (transactional metadata), Meta hot key cache (Xor filter, 2019).

Trade-offs (ADR)

ADR-001 — Cuckoo filter вместо Bloom: deletion + cache locality.

• Контекст. Workload — rolling membership на CDN edge: items постоянно evict из cache по TTL и добавляются заново. Bloom filter не умеет delete без catastrophe — unset bits сломают другие keys, sharing этих bits, что даст false negatives (a CDN запросит origin даже для items, которые там были). Counting Bloom решает за 4x памяти, что на 100M items = 4GB вместо 1GB — больно. FPR target ε=1%, в зоне где Cuckoo и Bloom равны по памяти, но CF даёт delete бесплатно.
• Решение. Cuckoo filter с параметрами b=4 entries/bucket, f=8 bit fingerprint → ~9 bits/element при ε≈3%, либо f=12 → ~14 bits при ε≈0.1%. Партиционируем по hash key для concurrent access (per-partition locks). Load factor мониторим, при >85% триггерим rebuild с большим m в background.
• Альтернативы рассмотрены. Counting Bloom — отбросили из-за 4x памяти. Quotient Filter — лучше для disk-backed, но в RAM CF cache-friendlier. Xor Filter — read-only, не подходит для writable workload. Cuckoo Filter+ / Vacuum Filter — варианты, отложили на v2.
• Последствия. Положительные: delete работает, lookup 1-2 cache lines, FPR контролируем через f. Отрицательные: insert может fail (надо мониторить load factor и rebuild proactively), реализация сложнее Bloom, hash function quality критична (partial-key cuckoo требует равномерного распределения XOR fingerprint).

Другие важные trade-offs (без отдельных ADR):

• MAX_KICKS=500 vs latency tail. Чем больше kicks допускаем — тем выше load factor можем держать, но тем хуже p99 latency insert. На load 90%+ kick chains регулярно бывают по 20-50 итераций.
• Fingerprint length f. Маленький f (8 bits) → меньше памяти, выше FPR. Большой f (16 bits) → ниже FPR, больше памяти, но FPR-выигрыш над Bloom растёт. Sweet spot — 12 bits для ε≈0.1%.
• No dynamic resize. В отличие от Scalable Bloom (несколько filters разного размера в цепочке), у CF нет красивого пути «роста». Если переоценили или недооценили N — нужен полный rebuild с новым m. Sizing заранее критичен.

Реальные системы

• RedisBloom. Модуль для Redis с командами CF.RESERVE, CF.ADD, CF.ADDNX, CF.EXISTS, CF.DEL, CF.COUNT. De facto «as-a-service» Cuckoo filter, используется в продакшене многими.
• Snowflake. Per micro-partition CF (и Xor variants в новых версиях) для query pruning: перед чтением 5-100MB SSTable из cold storage CF отвечает «есть ли там id=X?» и SSTable может быть skip'нут. Огромная экономия I/O.
• Apache Kudu. Cuckoo filter для column predicate filtering на storage layer.
• TiKV. Transactional metadata — быстрые existence checks для distributed transactions.
• CDN edge cache. Cuckoo filter трекает «что у нас в cache» — items постоянно выкидываются по TTL, CF удаляет их fingerprint при eviction. Bloom бы сломался на первом же delete.
• Meta (Facebook), 2019. Перешли на Xor filter (вариант Cuckoo с лучшим space efficiency) для hot key cache. Xor — read-only, строится один раз, занимает меньше CF и Bloom при одинаковом FPR.
• Google internal systems. Различное использование, заменяет некоторые Bloom usage.
• Bitcoin / Ethereum mempool. Некоторые клиенты для dedup передаваемых tx между peers.

Anti-patterns

• CF при FPR > 3%. Bloom меньше памяти в этой зоне. Используйте Bloom если ε=5-10% устраивает и delete не нужен.
• Push load factor к 100%. Eviction chains взрываются, insert latency растёт экспоненциально, в итоге fail. Держите ≤85-90%, мониторьте, делайте rebuild proactively.
• Не учитывать insert failure. В отличие от Bloom (где insert никогда не fails), CF может вернуть FAIL. Нужен fallback: rebuild с большим m, или spillover в overflow structure, или просто 503 на upstream.
• Delete без проверки. Удалять fingerprint, не убедившись, что элемент действительно был вставлен, — рискованно. Из-за false positives может удалиться чужой fingerprint с тем же hash. В критичных системах — CF.EXISTS перед CF.DEL, либо отдельный source of truth (БД).
• Counting/duplicates без CHECK. Если вы insert одного элемента N раз → N occupied slots, space waste. Используйте CF.ADDNX (add if not exists) или предварительный EXISTS.
• Ignore concurrent access. Multi-thread без locks на bucket даёт corruption (две конкурирующие eviction chain могут потерять fingerprint). Per-bucket lock или CAS на slot обязательны.
• Игнорировать Xor filter для read-only. Если workload «build once, read many» (например, hot key cache, который перестраивается раз в час) — Xor filter меньше Cuckoo и Bloom, лучше использовать его.
• Adversarial input для fast ingestion. Атакующий, контролирующий keys, может trigger eviction chains через коллизии fingerprint и сделать insert latency очень плохим. Если входные данные не доверенные — используйте randomized seed для hash function.

Когда НЕ использовать

Не берите Cuckoo, если:

• Delete не нужен. Insert-only workload (например, дедуп URL для краулера) — берите Bloom. Проще, нет insert failure, нет проблемы с false-positive delete.
• FPR > 3% устраивает. Bloom меньше в этой зоне.
• Write-heavy с непредсказуемой нагрузкой. Если N может вырасти 10x — CF не resize'нется, придётся пересобирать всё с нуля. Scalable Bloom лучше для этого случая.
• Workload read-only после build. Xor filter — ещё меньше памяти и быстрее lookup.
• Disk-backed structure нужна. Cuckoo плохо ложится на диск из-за random access pattern в eviction chains. Quotient filter лучше для disk.
• Простоту цените выше всего. Bloom — 50 строк кода. Cuckoo — несколько сотен с edge cases (MAX_KICKS, partial-key invariants, concurrent locking). В прототипе берите Bloom, мигрируйте на CF только если есть конкретная причина (delete или cache locality).

Дальше читать

Концепты-предшественники:

• ::concept{slug="probabilistic-data-structures"} — обзор всего семейства (Bloom, Count-Min, HLL, Cuckoo, MinHash, t-digest).
• ::concept{slug="bloom-filters"} — классический membership filter, основа для всего остального.

Foundational papers:

• Fan, Andersen, Kaminsky, Mitzenmacher, Cuckoo Filter: Practically Better Than Bloom (CoNEXT 2014) — оригинал, разбор partial-key cuckoo. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
• Pagh, Rodler, Cuckoo Hashing (Journal of Algorithms 2004) — алгоритм-предок.
• Graf, Lemire, Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters (ACM JEA 2020) — read-only alternative. https://arxiv.org/abs/1912.08258
• Wang et al., Vacuum Filters (VLDB 2019) — Cuckoo с поддержкой resize.
• Breslow et al., Morton Filters (VLDB 2018) — Cuckoo с лучшей cache efficiency через compressed buckets.

Книга:

• Probabilistic Data Structures and Algorithms (Andrii Gakhov), глава 3.

Production blog posts:

• RedisBloom docs: https://redis.io/docs/data-types/probabilistic/cuckoo-filter/
• Daniel Lemire's blog — серия про Xor Filters в production.

Reference implementations:

• Original C++: https://github.com/efficient/cuckoofilter
• Go: https://github.com/seiflotfy/cuckoofilter
• Rust: https://github.com/axiomhq/rust-cuckoofilter
• Java: https://github.com/MGunlogson/CuckooFilter4J