Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии по
Вероятностные структуры данных
Случайные деревья
Связанный

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

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

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

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

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

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

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

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

В течение некоторого ключа D , который Хэши к отпечаткам пальцев д Н , пусть его фактор будет d Q , а остальные будут d R . QF попытается сохранить остаток в слоте d Q , который известен как канонический слот . Однако канонический слот может уже быть занят, потому что несколько ключей могут хешировать один и тот же отпечаток пальца - жесткая коллизия - или потому что даже когда отпечатки клавиш различны, они могут иметь одно и то же отношение - мягкое коллизия . Если канонический слот занят, то остаток сохраняется в некотором слоте справа.

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

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

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

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

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

is_occupied
is_continuation
is_shifted
смысл
000Пустой слот
001Слот удерживает начало запуска, которое было сдвинуто с его канонического слота.
010не используется.
011Слот удерживает продолжение запуска, которое было перемещено из его канонического слота.
100Слот удерживает начало запуска, которое находится в его каноническом слоте.
Это тоже начало кластера.
101Слот удерживает начало запуска, которое было сдвинуто с его канонического слота.
Также существует прогон, для которого это канонический слот, но он сдвинут вправо.
110не используется.
111Слот удерживает продолжение запуска, которое было перемещено из его канонического слота.
Также существует прогон, для которого это канонический слот, но он сдвинут вправо.

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

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

Мы хэшируем ключ для получения его отпечатка d H , который затем разделяем на q битов старшего порядка d Q , составляющих частное, и r битов младшего порядка d R , составляющие остаток. Слот d Q - канонический слот ключа. Этот слот пуст, если его три бита метаданных ложны. В этом случае фильтр не содержит ключа.

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

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

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

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

Пример фильтра частных, показывающий порядок вставки элементов b , e , f , c , d и a

Возьмем, к примеру, поиск элемента e . См. Состояние 3 на рисунке. Мы хотели бы вычислить хэш (е) , раздел его на его остаток, е R и его фактор - е Q , который является 4. Сканирование слева от слота 4 мы встречаем три is_occupied слота, при индексов 4, 2 и 1, что указывает на адрес Q «S run - это третий запуск в кластере. Сканирование останавливается на слоте 1, который мы определяем как начало кластера, потому что он не пуст и не сдвинут. Теперь мы должны сканировать прямо до третьего запуска. Начало прогона обозначается is_continuationложь. Первый прогон находится с индексом 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. Мы предполагаем, что a 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]

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

Bender [4] вычисляет вероятность ложного срабатывания (т. Е. Когда хэш двух ключей приводит к одному и тому же отпечатку пальца) в терминах размера остатка хеш-таблицы и коэффициента загрузки. Напомним, что отпечаток p битов делится на q- битное частное, которое определяет размер таблицы m = 2 q слотов, и остаток r битов. Коэффициент загрузки - это отношение занятых слотов n к общему количеству слотов m : . Тогда для хорошей хеш-функции - это приблизительно вероятность жесткого столкновения.

Пространство / перформанс [ править ]

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

Заявление [ править ]

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

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

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

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

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

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

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

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

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

  • MinHash
  • Фильтр Блума
  • Кукушечный фильтр

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

  1. ^ a b Клири, Джон Г. (сентябрь 1984 г.). «Компактные хеш-таблицы с использованием двунаправленного линейного зондирования» . Транзакции IEEE на компьютерах . 33 (9): 828–834. DOI : 10.1109 / TC.1984.1676499 . S2CID  195908955 .
  2. ^ Паг, Анна; Паг, Расмус; Рао, С. Шриниваса (2005). «Оптимальная замена фильтра Блума» (PDF) . Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 823–829.
  3. ^ Диллинджер, Питер С .; Манолиос, Панайотис (2009). «Быстрое универсальное хранилище состояний» . 16-й Международный семинар SPIN по программному обеспечению для проверки моделей . Спрингер, Конспект лекций по информатике 5578.
  4. ^ a b c d e f g h я Бендер, Майкл А .; Фарач-Колтон, Мартин ; Джонсон, Роб; Kuszmaul, Bradley C .; Медедович, Джейла; Монтес, Пабло; Шетти, Прадип; Spillane, Ричард П .; Задок, Эрез (июнь 2011 г.). «Не трэш: как кэшировать хэш на флэш» (PDF) . Материалы 3-й конференции USENIX по актуальным вопросам хранения и файловых систем (HotStorage'11) . Проверено 21 июля 2012 года .
  5. ^ Бендер, Майкл А .; Фарач-Колтон, Мартин ; Джонсон, Роб; Кранер, Рассел; Kuszmaul, Bradley C .; Медедович, Джейла; Монтес, Пабло; Шетти, Прадип; Spillane, Ричард П .; Садок, Эрез (27–31 августа 2012 г.). «Не трэш: как кэшировать хэш на флэш» (PDF) . Труды эндаумента VLDB . 5 (11): 1627–1637. arXiv : 1208.0290 . Bibcode : 2012arXiv1208.0290B . DOI : 10.14778 / 2350229.2350275 . S2CID 47180056 .  
  6. ^ а б Панди, Прашант; Бендер, Майкл А .; Джонсон, Роб; Патро, Роб (май 2017). «Счетный фильтр общего назначения: считая каждый бит» . Материалы Международной конференции ACM по управлению данными 2017 г. (SIGMOD '17) . Дата обращения 2 декабря 2020 .
  7. ^ Кнут, Дональд (1973). Искусство программирования: поиск и сортировка, том 3 . Раздел 6.4, упражнение 13: Эддисон Уэсли.CS1 maint: location ( ссылка )
  8. ^ Чанг, Фэй; и другие. (2006). «Bigtable: распределенная система хранения структурированных данных» (PDF) . OSDI '06: Материалы 7-го симпозиума USENIX по разработке и внедрению операционных систем : 15 . Проверено 21 июля 2012 года .
  9. ^ О'Нил, Патрик; и другие. (1996). «Лог-структурированное дерево слияния (LSM-дерево)» . Acta Informatica . 33 (4): 351–385. DOI : 10.1007 / s002360050048 . S2CID 12627452 . 
  10. ^ Спиллейн, Ричард (май 2012 г.). «Эффективное, масштабируемое и универсальное управление приложениями и системными транзакциями для уровней прямого хранения» (PDF) . Проверено 21 июля 2012 года . Цитировать журнал требует |journal=( помощь )

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

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