Частный фильтр

Факторный фильтр с эффективным использованием пространства, — это вероятностная структура данных используемая для проверки того, является ли элемент членом набора ( приблизительный фильтр запроса членства , AMQ). Запрос вызовет ответ, в котором будет указано, что элемент определенно отсутствует в наборе или что элемент, вероятно, находится в наборе. Первый результат является окончательным; т.е. тест не дает ложноотрицательных результатов . Но в случае последнего результата существует некоторая вероятность ε того, что тест вернет «элемент находится в наборе», хотя на самом деле элемент отсутствует в наборе ( т. е . ложноположительный результат ). Существует компромисс между ε, частотой ложных срабатываний и размером хранилища; увеличение размера памяти фильтра уменьшает ε. Другие операции AMQ включают «вставить» и «необязательно удалить». Чем больше элементов добавляется в набор, тем больше вероятность ложных срабатываний.

Типичное применение частных фильтров и других фильтров AMQ — служить прокси-сервером для ключей в базе данных на диске. Когда ключи добавляются в базу данных или удаляются из нее, фильтр обновляется, чтобы отразить это. Любой поиск сначала будет обращаться к быстрому факторному фильтру, а затем искать в базе данных (предположительно гораздо более медленной) только в том случае, если факторный фильтр сообщил о наличии ключа. Если фильтр возвращает отсутствие, то известно, что ключа нет в базе данных, если не было выполнено никаких обращений к диску.

Факторный фильтр имеет обычные операции AMQ: вставку и запрос. Кроме того, его также можно объединить и изменить размер без необходимости повторного хеширования исходных ключей (тем самым избегая необходимости доступа к этим ключам из вторичного хранилища). Это свойство дает преимущества некоторым видам деревьев слияния с логической структурой .

История [ править ]

Компактная хеш-таблица, лежащая в основе фактор-фильтра, была описана Клири в 1984 году. ^[1] Первая известная ссылка на использование этой структуры в качестве фильтра AMQ принадлежит Pagh et al. в 2005 году. ^[2] В 2009 году Диллинджер и Манолиос оптимизировали метаданные структуры, добавили размещение большего количества элементов на месте и применили структуру для проверки модели с явным состоянием . ^[3] В 2011 году Бендер и др. придумал название «частный фильтр», описал несколько вариантов с различными компромиссами в кодировании метаданных, показал, как объединять и изменять размер частных фильтров, представил оптимизированную для записи версию частного фильтра для использования на диске и применил эту структуру к хранилищу базы данных. проблемы. ^[4]^[5]В 2017 году Панди и др. описал версию, которая использует аппаратные инструкции по битовой манипуляции для повышения производительности, поддерживает одновременные обновления и добавляет поддержку связывания счетчика переменного размера с каждым элементом. ^[6]

Описание алгоритма [ править ]

Факторный фильтр основан на своего рода хеш-таблице , в которой записи содержат только часть ключа плюс некоторые дополнительные биты метаданных. Эти биты используются в случае, когда разные ключи хэшируют одну и ту же запись таблицы. Напротив, другие типы хеш-таблиц, которые справляются с такими коллизиями путем связывания с областями переполнения, не являются компактными, поскольку накладные расходы из-за связывания могут превышать объем памяти, используемой для хранения ключа. ^[1] В фактор-фильтре хэш-функция генерирует p -битный отпечаток пальца. наименее r значимых битов называется остатком, а q = p - r наиболее значимых битов называется фактором, отсюда и название «факторирование» (придуманное Кнутом) . ^[7])В хеш-таблице есть 2 ^д слоты.

Для некоторого ключа d, хэшируется с отпечатком пальца d _H , пусть его частное будет d _Q, а остаток будет d _R. который QF попытается сохранить остаток в слоте d _Q , который известен как канонический слот .Однако канонический слот может быть уже занят, потому что несколько ключей могут хэшироваться с одним и тем же отпечатком пальца ( жесткая коллизия ) или потому, что даже если отпечатки ключей различны, они могут иметь одинаковое частное ( мягкое столкновение) . Если канонический слот занят, остаток сохраняется в каком-то слоте справа.

Как описано ниже, алгоритм вставки гарантирует, что все отпечатки пальцев, имеющие одинаковое частное, хранятся в смежных слотах. Такой набор отпечатков пальцев определяется как пробег . ^[4] Обратите внимание, что первый отпечаток прогона может не занимать свой канонический слот, если прогон был принудительно перемещен вправо из-за какого-то прогона влево.

Однако запуск, первый отпечаток которого занимает свой канонический слот, указывает на начало кластера . ^[4] Начальный запуск и все последующие запуски составляют кластер, который завершается в незанятом слоте или начале другого кластера.

Три дополнительных бита используются для восстановления отпечатка слота. Они имеют следующую функцию:

занято: устанавливается, когда слот является каноническим слотом для некоторого ключа, хранящегося (где-то) в фильтре (но не обязательно в этом слоте).
is_continuation: устанавливается, когда слот занят, но не первым остатком в серии.
is_shifted: устанавливается, когда остаток в слоте не находится в его каноническом слоте.

Различные комбинации имеют следующее значение:

занято	is_continuation	is_shifted	значение
0	0	0	Пустой слот
0	0	1	Слот удерживает начало запуска, которое было смещено из канонического слота.
0	1	0	не используется.
0	1	1	В слоте находится продолжение тиража, который был перенесен из канонического слота.
1	0	0	Слот удерживает начало выполнения, которое находится в его каноническом слоте. Это также начало кластера.
1	0	1	Слот удерживает начало запуска, которое было смещено из канонического слота. Также серия, для которой это канонический слот, существует, но сдвинута вправо.
1	1	0	не используется.
1	1	1	В слоте находится продолжение тиража, который был перенесен из канонического слота. Также серия, для которой это канонический слот, существует, но сдвинута вправо.

Поиск [ править ]

Мы можем проверить, содержит ли фактор-фильтр некоторый ключ d, следующим образом. ^[4]

Мы хешируем ключ, чтобы получить его отпечаток dH _, который затем разделяем на q бит старшего порядка, dQ _, которые составляют его частное, и его младшие r биты, dR _, которые составляют его остаток. Слот d _Q — канонический слот ключа. Этот слот пуст, если его три бита метаданных ложны. В этом случае фильтр не содержит ключа.

Если каноническое место занято, мы должны найти пробег частного. Набор слотов, в которых хранятся остатки, принадлежащие одному и тому же частному, хранятся последовательно и составляют серию частного. Первый слот в серии может быть каноническим, но также возможно, что вся серия была смещена вправо из-за вторжения слева в другую серию.

Чтобы найти серию частного, мы должны сначала найти начало кластера. Кластер состоит из непрерывного набора прогонов. Начиная с канонического слота частного, мы можем сканировать влево, чтобы найти начало кластера, а затем сканировать вправо, чтобы найти прогон частного.

Мы сканируем влево в поисках слота, для которого значение is_shifted равно false. Это указывает на начало кластера. Затем мы сканируем вправо, подсчитывая количество проходов, которые мы должны пропустить. Каждый слот слева от канонического слота, имеющий is_occupied, набор указывает на другой прогон, который нужно пропустить, поэтому мы увеличиваем счетчик прогонов. Каждый слот, имеющий is_continuation очистку , указывает на начало другого запуска, то есть на конец предыдущего запуска, поэтому мы уменьшаем счетчик запусков. Когда текущий счетчик достигает нуля, мы сканируем ход частного. Мы можем сравнить остаток в каждом слоте в серии с d _R . Если он найден, мы сообщаем, что ключ (вероятно) находится в фильтре, в противном случае сообщаем, что ключа точно нет в фильтре.

Пример поиска [ править ]

Возьмем, к примеру, поиск элемента e . См. состояние 3 на рисунке. Мы бы вычислили hash(e) , разделили его на остаток e _R и частное e _Q , равное 4. Сканируя слева от слота 4, мы обнаруживаем три is_occupied слота с индексами 4, 2 и 1, обозначающие _Q. e run — это третий запуск в кластере. Сканирование останавливается на слоте 1, который мы определяем как начало кластера, поскольку он не пуст и не сдвинут. Теперь нам нужно просканировать вплоть до третьего прогона. Начало выполнения обозначается значением is_continuation , равным false. Первый прогон находится по индексу 1, второй — по индексу 4 и третий — по индексу 5. Мы сравниваем остаток, удерживаемый в каждом слоте в прогоне, который начинается с индекса 5. В этом прогоне есть только один слот, но в нашем примере его остаток равен e _R , что указывает на то, что e действительно является членом фильтра с вероятностью 1 - ε.

Вставка [ править ]

Вставка выполняется по пути, аналогичному поиску, пока мы не убедимся, что ключа определенно нет в фильтре. ^[4] В этот момент мы вставляем остаток в слот текущего прогона, слот, выбранный для сохранения отсортированного порядка прогона. Мы сдвигаем вперед остатки в любых слотах кластера в выбранном слоте или после него и обновляем биты слота.

Сдвиг остатка слота не влияет на бит is_occupied слота , поскольку он относится к слоту, а не к остатку, содержащемуся в слоте.
Если мы вставляем остаток в начало существующего выполнения, предыдущий остаток смещается и становится слотом продолжения, поэтому мы устанавливаем его is_continuation . бит
Мы устанавливаем бит is_shifted любого остатка, который мы сдвигаем.

Пример вставки [ править ]

На рисунке показан фактор-фильтр, проходящий через серию состояний по мере добавления элементов. В состоянии 1 были добавлены три элемента. Слот, который занимает каждый из них, образует серию из одного слота, которая также является отдельным кластером.

В состояние 2 элемента c и d добавлены . Элемент c имеет частное 1, такое же, как и b . Мы предполагаем, что b _R < c _R, поэтому c _R сдвигается в слот 2 и помечается одновременно как продолжение и как сдвиг . Элемент d имеет частное 2. Поскольку его канонический слот используется, он перемещается в слот 3 и помечается как сдвинутый . Кроме того, его канонический слот помечен как занятый . Прогоны для частных 1 и 2 теперь составляют кластер.

В состоянии 3 элемент a был добавлен . Его частное равно 1. Мы предполагаем, что _R < b _R, поэтому остатки в слотах с 1 по 4 должны быть сдвинуты. Слот 2 получает b _R и помечается как продолжение и смещается . Слот 5 получает e _R и помечается как сдвинутый . Прогоны для частных 1, 2 и 4 теперь составляют кластер, и наличие этих трех прогонов в кластере обозначается тем, что слоты 1, 2 и 4 помечены как занятые .

Стоимость/производительность [ править ]

Длина кластера [ править ]

Бендеры ^[4] утверждает, что кластеры малы. Это важно, поскольку поиск и вставка требуют определения начала и длины всего кластера. Если хэш-функция генерирует равномерно распределенные отпечатки пальцев, то длина большинства прогонов равна O (1), и весьма вероятно, что все прогоны имеют длину O (log m ), где m — количество слотов в таблице. ^[4]

Вероятность ложных срабатываний [ править ]

Бендеры ^[4] вычисляет вероятность ложного срабатывания (т. е. когда хэш двух ключей дает один и тот же отпечаток пальца) с точки зрения размера остатка хеш-таблицы и коэффициента загрузки. Напомним, что отпечаток бита p разбивается на частное бита q , которое определяет размер таблицы m = 2. ^д слоты и немного остатка. Коэффициент нагрузки $\alpha$ — доля занятых слотов n от общего количества слотов m : $\alpha =n/m$ . Тогда для хорошей хеш-функции $1-e^{-\alpha /2^{r}}\leq 2^{-r}$ приблизительно равна вероятности жесткого столкновения.

Пространство/производительность [ править ]

Версия частного фильтра Панди требует меньше места, чем сопоставимый фильтр Блума, когда целевой уровень ложноположительных результатов меньше 1/64. ^[6]

Приложение [ править ]

Частные фильтры представляют собой AMQ и, как таковые, предоставляют многие из тех же преимуществ, что и фильтры Блума . Большая база данных, например Webtable ^[8] может состоять из меньших подтаблиц, каждая из которых имеет связанный фильтр. Каждый запрос распространяется одновременно по всем подтаблицам. Если подтаблица не содержит запрошенный элемент, ее фильтр может быстро выполнить запрос без каких-либо операций ввода-вывода.

Частные фильтры дают два преимущества в некоторых приложениях.

Два факторных фильтра можно эффективно объединить, не влияя на их частоту ложных срабатываний. Это невозможно с фильтрами Блума.
Несколько дубликатов можно эффективно допустить и удалить.

Пространство, используемое факторными фильтрами, сопоставимо с пространством фильтров Блума. Однако частные фильтры можно эффективно объединять в памяти без необходимости повторной вставки исходных ключей.

Это особенно важно в некоторых системах хранения с журнальной структурой, которые используют дерево слияния с журнальной структурой или LSM-дерево. ^[9] LSM-дерево на самом деле представляет собой набор деревьев, но рассматривается как единое хранилище значений ключа. Одним из вариантов LSM-дерева является дерево слияния отсортированных массивов или SAMT. ^[10] В этом варианте деревья компонентов SAMT называются Wanna-B-деревьями . Каждое Wanna- B -дерево имеет связанный с ним фактор-фильтр. Запрос к SAMT направлен только на избранные Wanna- B -деревья, о чем свидетельствуют их частные фильтры.

деревья SAMT Система хранения при нормальной работе сжимает Wanna- B- , объединяя меньшие Wanna- B- деревья с более крупными и объединяя их частные фильтры. Важным свойством частных фильтров является то, что их можно эффективно объединять без необходимости повторной вставки исходных ключей. Учитывая, что для больших наборов данных Wanna- B -деревья могут отсутствовать в памяти, доступ к ним для получения исходных ключей потребует большого количества операций ввода-вывода.

По своей конструкции значения в факторном фильтре хранятся в отсортированном порядке. Каждый прогон связан с определенным значением частного, которое обеспечивает наиболее значимую часть «отпечатка», прогоны сохраняются по порядку, и каждый слот в прогоне представляет наименее значимую часть «отпечатка».

Таким образом, работая слева направо, можно восстановить все отпечатки пальцев, и результирующий список целых чисел будет отсортирован. Объединение двух частных фильтров тогда представляет собой простой вопрос преобразования каждого частного фильтра в такой список, объединения двух списков и использования его для заполнения нового частного фильтра большего размера. Точно так же мы можем уменьшить вдвое или удвоить размер частного фильтра, не перефразируя ключи, поскольку отпечатки пальцев можно пересчитать, используя только частные и остатки. ^[4]

См. также [ править ]

Примечания [ править ]

^ Jump up to: Перейти обратно: ^а ^б Клири, Джон Г. (сентябрь 1984 г.). «Компактные хэш-таблицы с использованием двунаправленного линейного зондирования» . Транзакции IEEE на компьютерах . 33 (9): 828–834. дои : 10.1109/TC.1984.1676499 . S2CID 195908955 .
^ Паг, Анна; Паг, Расмус ; Рао, С. Шриниваса (2005). «Оптимальная замена фильтра Блума» (PDF) . Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 823–829. Архивировано из оригинала (PDF) 4 февраля 2012 г. Проверено 22 января 2019 г.
^ Диллинджер, Питер К.; Манолиос, Панайотис (2009). «Быстрое, универсальное хранилище состояний» . 16-й международный семинар SPIN по программному обеспечению для проверки моделей . Спрингер, Конспект лекций по информатике 5578.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Бендер, Майкл А.; Фарах-Колтон, Мартин ; Джонсон, Роб; Кушмаул, Брэдли С.; Медедович, Дзейла; Монтес, Пабло; Шетти, Прадип; Спиллейн, Ричард П.; Садок, Эрез (июнь 2011 г.). «Не ломайтесь: как кэшировать хеш на флэш-памяти» (PDF) . Материалы 3-й конференции USENIX «Актуальные темы в системах хранения и файловых системах» (HotStorage'11) . Проверено 21 июля 2012 г.
^ Бендер, Майкл А.; Фарах-Колтон, Мартин ; Джонсон, Роб; Кранер, Рассел; Кушмаул, Брэдли С.; Медедович, Дзейла; Монтес, Пабло; Шетти, Прадип; Спиллейн, Ричард П.; Садок, Эрез (27–31 августа 2012 г.). «Не ломайтесь: как кэшировать хеш на флэш-памяти» (PDF) . Труды Фонда VLDB . 5 (11): 1627–1637. arXiv : 1208.0290 . Бибкод : 2012arXiv1208.0290B . дои : 10.14778/2350229.2350275 . S2CID 47180056 .
^ Jump up to: Перейти обратно: ^а ^б Пандей, Прашант; Бендер, Майкл А.; Джонсон, Роб; Патро, Роб (май 2017 г.). «Счетный фильтр общего назначения: учитывается каждый бит». Материалы Международной конференции ACM по управлению данными 2017 г. (SIGMOD '17) . дои : 10.1145/3035918.3035963 .
^ Кнут, Дональд (1973). Искусство компьютерного программирования: Поиск и сортировка, том 3 . Раздел 6.4, упражнение 13: Эддисон Уэсли. {{cite book}}: CS1 maint: местоположение ( ссылка )
^ Чанг, Фэй; и др. (2006). «Bigtable: распределенная система хранения структурированных данных» (PDF) . OSDI '06: Материалы 7-го симпозиума USENIX по проектированию и внедрению операционных систем : 15 . Проверено 21 июля 2012 г.
^ О'Нил, Патрик; и др. (1996). «Дерево слияния с лог-структурой (LSM-дерево)». Акта Информатика . 33 (4): 351–385. дои : 10.1007/s002360050048 . S2CID 12627452 .
^ Спиллейн, Ричард (май 2012 г.). «Эффективное, масштабируемое и универсальное управление приложениями и системными транзакциями для уровней прямого хранения» (PDF) . Проверено 21 июля 2012 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

Внешние ссылки [ править ]

СМИ, связанные с фильтром коэффициентов, на Викискладе?

[Cleary-1] Jump up to: Перейти обратно: ^а ^б Клири, Джон Г. (сентябрь 1984 г.). «Компактные хэш-таблицы с использованием двунаправленного линейного зондирования» . Транзакции IEEE на компьютерах . 33 (9): 828–834. дои : 10.1109/TC.1984.1676499 . S2CID 195908955 .

[Pagh-2] Паг, Анна; Паг, Расмус ; Рао, С. Шриниваса (2005). «Оптимальная замена фильтра Блума» (PDF) . Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 823–829. Архивировано из оригинала (PDF) 4 февраля 2012 г. Проверено 22 января 2019 г.

[Dillinger-3] Диллинджер, Питер К.; Манолиос, Панайотис (2009). «Быстрое, универсальное хранилище состояний» . 16-й международный семинар SPIN по программному обеспечению для проверки моделей . Спрингер, Конспект лекций по информатике 5578.

[Bender-4] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Бендер, Майкл А.; Фарах-Колтон, Мартин ; Джонсон, Роб; Кушмаул, Брэдли С.; Медедович, Дзейла; Монтес, Пабло; Шетти, Прадип; Спиллейн, Ричард П.; Садок, Эрез (июнь 2011 г.). «Не ломайтесь: как кэшировать хеш на флэш-памяти» (PDF) . Материалы 3-й конференции USENIX «Актуальные темы в системах хранения и файловых системах» (HotStorage'11) . Проверено 21 июля 2012 г.

[5] Бендер, Майкл А.; Фарах-Колтон, Мартин ; Джонсон, Роб; Кранер, Рассел; Кушмаул, Брэдли С.; Медедович, Дзейла; Монтес, Пабло; Шетти, Прадип; Спиллейн, Ричард П.; Садок, Эрез (27–31 августа 2012 г.). «Не ломайтесь: как кэшировать хеш на флэш-памяти» (PDF) . Труды Фонда VLDB . 5 (11): 1627–1637. arXiv : 1208.0290 . Бибкод : 2012arXiv1208.0290B . дои : 10.14778/2350229.2350275 . S2CID 47180056 .

[Pandey-6] Jump up to: Перейти обратно: ^а ^б Пандей, Прашант; Бендер, Майкл А.; Джонсон, Роб; Патро, Роб (май 2017 г.). «Счетный фильтр общего назначения: учитывается каждый бит». Материалы Международной конференции ACM по управлению данными 2017 г. (SIGMOD '17) . дои : 10.1145/3035918.3035963 .

[7] Кнут, Дональд (1973). Искусство компьютерного программирования: Поиск и сортировка, том 3 . Раздел 6.4, упражнение 13: Эддисон Уэсли. {{cite book}}: CS1 maint: местоположение ( ссылка )

[8] Чанг, Фэй; и др. (2006). «Bigtable: распределенная система хранения структурированных данных» (PDF) . OSDI '06: Материалы 7-го симпозиума USENIX по проектированию и внедрению операционных систем : 15 . Проверено 21 июля 2012 г.

[9] О'Нил, Патрик; и др. (1996). «Дерево слияния с лог-структурой (LSM-дерево)». Акта Информатика . 33 (4): 351–385. дои : 10.1007/s002360050048 . S2CID 12627452 .

[Spillane-10] Спиллейн, Ричард (май 2012 г.). «Эффективное, масштабируемое и универсальное управление приложениями и системными транзакциями для уровней прямого хранения» (PDF) . Проверено 21 июля 2012 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]