Фільтр часток

Фільтр часток (англ. quotient filter) — це економна за простором імовірнісна структура даних, яку використовують для перевірки, чи є елемент членом множини (фільтр наближеного запиту членства, AMQ). Запит дає відповідь, яка вказує або що елемента точно немає в множині, або що він, імовірно, у множині. Перший результат є остаточним; тобто перевірка не породжує хибнонегативних результатів. Але в другому випадку існує певна ймовірність ${\displaystyle \varepsilon }$, що перевірка поверне «елемент у множині», тоді як насправді його немає (хибнопозитивний результат). Є компроміс між частотою хибнопозитивних результатів ${\displaystyle \varepsilon }$ і розміром сховища; збільшення розміру фільтра зменшує ${\displaystyle \varepsilon }$.

Типове застосування фільтрів часток та інших AMQ-фільтрів — слугувати замінником ключів у базі даних на диску. У міру додавання чи видалення ключів фільтр оновлюють, щоб відбити це. Будь-який пошук спершу звертається до швидкого фільтра часток, а потім зазирає в (імовірно значно повільнішу) базу даних лише якщо фільтр повідомив про наявність ключа. На додачу до звичайних AMQ-операцій додавання та запиту фільтр часток можна зливати й змінювати його розмір без перегешування первісних ключів. Ця властивість корисна для певних видів дерев злиття з журнальною структурою (LSM-tree).

Компактну геш-таблицю, що лежить в основі фільтра часток, описав Кліарі 1984 року. Перше відоме посилання на використання структури як AMQ-фільтра належить Паґу та іншим (2005). 2009 року Діллінджер і Манолос оптимізували метадані структури. 2011 року Бендер та інші дали назву «фільтр часток», описали кілька варіантів з різними компромісами кодування метаданих, показали, як зливати й змінювати розмір фільтрів часток, і застосували структуру до задач зберігання баз даних. 2017 року Панді та інші описали версію, що використовує апаратні інструкції бітових маніпуляцій для підвищення продуктивності.

Фільтр часток ґрунтується на різновиді геш-таблиці, у якій записи містять лише частину ключа плюс кілька додаткових бітів метаданих. Ці біти використовують для опрацювання випадку, коли різні ключі випадково гешуються в той самий запис. У фільтрі часток геш-функція генерує ${\displaystyle p}$-бітний відбиток. ${\displaystyle r}$ найменш значущих біт називають остачею (remainder), а ${\displaystyle q=p-r}$ найбільш значущих біт — часткою (quotient), звідки й назва (термін запровадив Кнут).

Геш-таблиця має ${\displaystyle 2^{q}}$ комірок. Для деякого ключа ${\displaystyle d}$, що гешується у відбиток ${\displaystyle d_{H}}$, нехай його частка буде ${\displaystyle d_{Q}}$, а остача — ${\displaystyle d_{R}}$. Фільтр намагатиметься зберегти остачу в комірці ${\displaystyle d_{Q}}$, яку називають канонічною. Однак канонічна комірка може бути вже зайнята, бо кілька ключів можуть гешуватися в той самий відбиток (жорстка колізія) або мати однакову частку за різних відбитків (м'яка колізія). Якщо канонічна комірка зайнята, остачу зберігають у якійсь комірці праворуч.

Алгоритм додавання гарантує, що всі відбитки з однаковою часткою зберігаються в суміжних комірках. Таку множину відбитків називають пробіжкою (run). Пробіжка, перший відбиток якої займає свою канонічну комірку, позначає початок кластера. Три додаткові біти використовують для відтворення відбитку комірки:

• is_occupied — встановлено, коли комірка є канонічною для якогось збереженого в фільтрі ключа;
• is_continuation — встановлено, коли комірка зайнята, але не першою остачею в пробіжці;
• is_shifted — встановлено, коли остача в комірці не в своїй канонічній комірці.

Щоб перевірити, чи містить фільтр ключ ${\displaystyle d}$, гешуємо його у відбиток ${\displaystyle d_{H}}$, розбиваючи на частку ${\displaystyle d_{Q}}$ та остачу ${\displaystyle d_{R}}$. Комірка ${\displaystyle d_{Q}}$ — канонічна. Якщо всі три біти метаданих хибні, вона порожня і ключа у фільтрі немає. Якщо ж канонічна комірка зайнята, треба знайти пробіжку частки. Для цього спершу сканують ліворуч у пошуку комірки з хибним is_shifted (початок кластера), а потім сканують праворуч, підраховуючи пробіжки, які треба пропустити. Знайшовши пробіжку частки, порівнюють остачу в кожній її комірці з ${\displaystyle d_{R}}$. Якщо знайдено — повідомляють, що ключ (імовірно) у фільтрі; інакше — що його точно немає.

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

Якщо геш-функція генерує рівномірно розподілені відбитки, довжина більшості пробіжок становить ${\displaystyle O(1)}$, і дуже ймовірно, що всі пробіжки мають довжину ${\displaystyle O(\log m)}$, де ${\displaystyle m}$ — кількість комірок у таблиці.

Імовірність хибнопозитивного результату Бендер обчислює через розмір остачі та коефіцієнт заповнення. Коефіцієнт заповнення ${\displaystyle \alpha =n/m}$ — це частка зайнятих комірок. Тоді для доброї геш-функції ${\displaystyle 1-e^{-\alpha /2^{r}}\leq 2^{-r}}$ є приблизно ймовірністю жорсткої колізії. Версія фільтра часток Панді потребує менше простору за порівнянний фільтр Блума, коли цільова частота хибнопозитивних результатів менша за 1/64.

Фільтри часток є AMQ і дають багато тих самих переваг, що й фільтри Блума. Фільтри часток надають дві переваги в деяких застосуваннях:

• Два фільтри часток можна ефективно злити без впливу на частоту хибнопозитивних результатів. Для фільтрів Блума це неможливо.
• Кілька дублікатів можна ефективно допускати й видаляти.

Це особливо важливо в деяких системах зберігання з журнальною структурою, що використовують LSM-дерево. За побудовою значення у фільтрі часток зберігаються у відсортованому порядку, тож злиття двох фільтрів зводиться до перетворення кожного на список цілих чисел, їхнього злиття й заповнення нового більшого фільтра. Так само можна вдвічі зменшити чи збільшити розмір фільтра без перегешування ключів.

• Фільтр Блума
• Зозулиний фільтр
• Геш-таблиця

• Bender, Michael A. (2012). Don't thrash: how to cache your hash on flash. Proceedings of the VLDB Endowment.
• Оригінальна стаття в англійській Вікіпедії