Фільтр Кукушки

Чому не використовувати просто фільтр Блума?

Фільтр Блума відповідає на запити щодо членства шляхом хешування елемента з кількома незалежними хеш-функціями та встановлення відповідних бітів у спільній бітовій масі. Перевірка членства передбачає перевірку, чи всі ці біти встановлені. Цей дизайн компактний і швидкий, але має структурну недоліковість: коли біти встановлюються, фільтр не знає, який елемент спричинив перемикання цього біта, оскільки багато елементів можуть ділитися одним бітом. Це означає, що ви ніколи не можете безпечно очистити біт для видалення одного елемента, оскільки це може безшумно порушити тести членства для інших елементів, які випадково покладаються на той самий біт. Фільтр Кюкко обходить цю проблему повністю, змінюючи те, що зберігається. Замість розкидання бітів по спільній масі, він зберігає невеликий, явний відбиток пальця – коротку бітову послідовність, отриману шляхом хешування елемента, у певному слоті закладеного хеш-таблиці. Кожен відбиток пальця займає свій ідентифікований слот замість того, щоб анонімно сприяти спільним бітам. Ця структурна різниця робить видалення обґрунтованим: для видалення елемента фільтр просто повинен знайти його відбиток пальця в одному з двох кандидатських контейнерів і очистити цей конкретний слот, без ризику пошкодження інших збережених елементів. Це не означає, що фільтри Кюкко кращі за всіма параметрами. Фільтри Блума простіші у реалізації, не потребують логіки виселення та можуть плавно налаштовуватися для дуже низьких частот хибних позитивних результатів шляхом додавання більшої кількості хеш-функцій і бітів. Фільтри Кюкко, в обмін на підтримку видалення, потребують трохи більше облікових записів та можуть, у рідкісних випадках, не вставити елемент, якщо ланцюги виселення не завершуються протягом обмеженої кількості ударів. Однак, на практиці, для досягнення однієї й тієї ж цільової частоти хибних позитивних результатів фільтри Кюкко часто більш ефективні за простором, ніж фільтри Блума, особливо при низьких частотах хибних позитивних результатів, і вони додають пошук та видалення, які поводяться передбачувано щодо окремих відбитків пальців, а не спільних бітів. Вибір між двома залежить від простого питання: чи потребує ваша робоча навантаження коли-небудь видаляти елементи з множини? Якщо так, то перевага в конструкції фільтра Кюкко стає вирішальною.

Відбитки замість бітових переходів

Основний будівельний блок фільтра ‘Кукушка’ – це відбиток: короткий, фіксованою довжиною біт-рядок, що генерується шляхом хешування оригінального елемента та отримання компактного узагальнення з цього хешу. Типовий відбиток може мати лише 4–16 бітів, значно менший за сам елемент. Це навмисне втрачаюче стиснення. Фільтр ніколи не зберігає оригінальний елемент, лише цей малий відбиток, який підтримує компактність структури в цілому. Оскільки відбиток короткий, багато різних елементів можуть хешуватися до одного й того ж значення відбитка. Це є джерелом хибнопозитивних результатів у фільтрі ‘Кукушка’: якщо запитати елемент, який не був вставлений, але його відбиток випадково збігається з відбитком, що вже знаходиться в одному з двох кандидатських контейнерів, фільтр неправильно повідомить про наявність цього елемента. Ймовірність цього відбувається безпосередньо залежить від довжини відбитка. Більші відбитки зменшують кількість зіткнень і знижують ймовірність хибнопозитивних результатів, але вони також означають, що таблиця споживає більше пам’яті на збережений елемент, тому довжина відбитка є основним регулюючим параметром для торгівлі між точністю та простором.

Відбитки не зберігають жодної корисної інформації про оригінальний елемент. Неможливо відновити елемент з його відбитка, і фільтру ніколи не потрібно цього робити, оскільки кожне операція – вставка, пошук, видалення – потребує лише значення відбитка та два індекси контейнерів, у яких він може знаходитися. Це свідома конструктивна обмеженість, яка підтримує компактність і самодостатність структури: все, що фільтру потрібно для переміщення або перевірки відбитка, можна отримати на місці з самого значення відбитка, ніколи не з збереженої копії оригінальних даних.

Два-Ящикового Трюк: Знаходження Альтернативного Місця Відбитка Пальця

Класичне кукузування зберігає повні ключі або пари ключ-значення, і індекс альтернативного ящика для кожного ключа зазвичай обчислюється шляхом хешування ключа само собою з використанням другої хеш-функції. Кукузуючий фільтр не може цього зробити безпосередньо, оскільки він свідомо викидає оригінальний елемент після обчислення відбитка пальця, зберігаючи лише короткий відбиток у таблиці. Отже, як він знає, де знаходиться інший кандидат на ящик для відбитка пальця, якщо більше немає елемента для перехешування? Відповідь – це невеликий шматочок математичної елегантності. Коли елемент вперше вставляється, фільтр обчислює його перший індекс ящика шляхом хешування елемента безпосередньо, назвемо цей ящик i1. Потім він обчислює відбиток пальця f зазвичай. Другий кандидат на ящик, i2, обчислюється не шляхом хешування елемента знову, а шляхом XOR-операції між i1 та хешем відбитка пальця f. Ця формула має прекрасну властивість самовідкидання: застосування точно тієї ж операції ще раз, XOR-операція між i2 та хешем відбитка f, повертає вас до i1. Іншими словами, з будь-якого індексу ящика окремо, плюс відбиток пальця, що знаходиться всередині нього, фільтр завжди може перерахувати інший кандидат на ящик без необхідності ніколи використовувати оригінальний елемент знову.

Це саме те, що дозволяє працювати ланцюгам виселення. Під час вставки, якщо обидва кандидати на відбиток пальця нового відбитка пальця вже заповнені, фільтр вибирає жертву відбитка пальця з одного з зайнятих слотів, виганяє її та потребує знайти цю жертву нове місце. Оскільки жертва – це лише відбиток пальця, що знаходиться в ящику, фільтр відновлює свій альтернативний ящик за допомогою формули XOR, потім намагається розмістити його там, потенційно викликаючи ще одну висаджування. Це ланцюжиться, ящик за ящиком, поки не знайдеться порожній слот або досягнуто максимальної кількості спроб переміщення. Це точно такий самий принцип заміщення, що й у кукузуванні, але він працює з компактними відбитками пальців замість повних ключів.

Вставка, Пошук та Каскадне Виключення

Вставлення елемента в фільтр «Кукушка» починається з обчислення його відбитка (відбитків) та двох кандидатів для бачків – i1 і i2 – за допомогою хешування елемента та встановленої вище XOR-відношення. Якщо будь-який з бачків має вільне місце, а бачки зазвичай містять кілька місць, щоб покращити коефіцієнт завантаження, відбиток просто поміщається туди, і вставлення завершено. Інтересним випадком є коли обидва кандидатських бачки повністю заповнені. Фільтр вибирає один з двох бачків, вибирає одне з зайнятих місць у ньому та виганяє цей відбиток, записуючи новий відбиток у звільнене місце. Вигнаний відбиток не викидається; фільтр обчислює його альтернативний бачок за допомогою того ж XOR-трюку і намагається вставити його туди, можливо, виганяючи ще один відбиток у відповідності. Ця ланцюг переміщень триває до тих пір, поки один з бачків не звільнить місце, або поки не буде вичерпано максимально дозволену кількість «удари», в цьому випадку фільтр вважається занадто повним, і вставлення невдало, сигналізуючи про те, що настав час розширити або перебудувати з більшим табличним розміром.

Пошук порівняно простий і завжди швидко завершується. Щоб перевірити, чи може елемент бути у наборі, фільтр обчислює його відбиток та обидва індекси кандидатських бачків, потім перевіряє, чи з'являється цей відбиток в будь-якому з бачків. Якщо він є, фільтр повідомляє, що елемент присутній, можливо, з хибним позитивом; якщо ні, він повідомляє, що елемент відсутній, і ця негативна відповідь завжди правильна, оскільки справжній вставлений відбиток обов’язково все ще знаходиться в одному з його двох кандидатських бачків. Видалення відображає пошук майже точно, що є повною метою структури. Фільтр обчислює відбиток та два кандидатські бачки, шукає обидва на відповідний відбиток, і якщо знайдено, очищає цей конкретний слот. Оскільки відбиток займає ідентифіковане місце замість спільних бітів, ця операція повністю безпечна і не може пошкодити статус членства будь-якого іншого збереженого елемента, що фільтр «Кукушка» фундаментально не може гарантувати.

Практичні Компроміси та Реальні Використання

Цукуфові фільтри особливо ефективні в системах, які потребують приблизного перевірки на членство в множинах, що змінюються з часом, а не просто ростуть. Класичні випадки використання фільтрів Блума, такі як швидке відхилення помилки пропуску кешу перед зверненням до повільного диска або мережевого запиту, перевірка URL-адреси на відомому чорному списку або фільтрація дублікатів елементів у потоці, часто також потребують видалення записів, коли дані стають застарілими або недійсними. Бази даних, маршрутизатори мережі, що відстежують трафік, та шари кешу спеціально прийняли цукуфові фільтри завдяки тому, що їхні робочі множини зменшуються разом із збільшенням, а перебудова всього фільтра Блума з нуля лише для видалення кількох застарілих елементів часто надто дорога для частішого повторення. Ці компроміси реальні. Цукуфові фільтри зазвичай потребують підтримки їхнього коефіцієнта завантаження нижче певного порогу, часто близько 90-95% в залежності від розміру розділів, щоб уникнути коротких ланцюгів виключень та рідкісних невдач при вставці. Якщо таблиця наближається до повної завантаженості, вставки можуть почати не вдаватися, навіть якщо теоретично є місце десь у таблиці; фільтр просто не може знайти шлях до нього протягом бюджету повторних спроб. Це означає, що планування обсягу має більше значення для цукуфових фільтрів, ніж для фільтрів Блума, які більш плавно деградують, лише з підвищенням частоти хибнопозитивних результатів, коли вони заповнюються. Також варто врахувати тонкий момент щодо коректності: видалення елемента, який ніколи не був вставлений, може бути небезпечним. Якщо перевірка повертає хибнопозитивний результат для певного елементу, а код помилково видаляє його, це видалення може призвести до видалення відбитка, що належить іншому, легітимно вставленому елементу з однаковим значенням відбитка, оскільки відбитки не є унікальними ідентифікаторами. Правильне використання вимагає, щоб видалення здійснювалися лише для елементів, які додаток може незалежно підтвердити, що вони були вставлені – дисципліна, яку фільтри Блума, не маючи можливості жодного видалення, ніколи не доводилося враховувати. Вибір між фільтром Блума, цукуфовим фільтром та більш важкими структурами, такими як підрахункові фільтри Блума, залежить від того, яку вагу надано бюджету пам'яті, потребам у змінюваності та можливостям оточуючого застосунку для уважного відстеження того, які елементи дійсно були вставлені.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Cuckoo Filter і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.