Основы фильтра с кукушкой

Обзор фильтров с кукушкой

Фильтры с кукушкой – это вероятностная структура данных, широко используемая в сетевых приложениях с 2014 года для проверки того, является ли элемент "вероятно" членом множества или "определенно" нет. Это означает, что ложноположительные совпадения возможны, а ложноотрицательные — нет. Другими словами, запрос возвращает либо «возможно, в наборе», либо «определенно не в наборе». Фильтры с кукушкой состоят из слотов, ведер и отпечатков пальцев (битовых массивов). Название кукушка происходит от птицы, которая откладывает яйца в другое гнездо, а после вылупления птенцов выбрасывает другие яйца из гнезда. Согласно официальной статье, представленной Фаном, фильтры с кукушкой могут иметь равную или меньшую пространственную сложность, чем фильтры Блума. Некоторые из больших различий между фильтрами Блума и фильтрами кукушки показаны ниже:

Сложность пространства

Фильтр с кукушкой

Фильтр Блума

Фильтры с кукушкой обеспечивают аналогичную эффективность пространства и времени с меньшими затратами на хеширование, чем фильтры Блума (поскольку фильтры с кукушкой имеют только 2 хэш-функции, а фильтры Блума имеют k функций). Однако главное преимущество заключается в том, что из-за двумерной вставки и вставки отпечатков пальцев фильтры с кукушкой могут удалять элементы из набора членства. Это может привести к интересному улучшению для таких баз данных, как Hbase, где SSTables постоянно объединяются и уплотняются. Вот некоторые из новых функций, недавно добавленных в фильтры с кукушкой:

Удаление элементов
Ограниченный подсчет
Ограниченная ложноположительная вероятность
Аналогичная космическая сложность

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

Структура фильтров с кукушкой

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

Ведра

Единица, в которой сгенерированные отпечатки пальцев из хеширования значений будут храниться в записях. Фильтр с кукушкой будет иметь n количество сегментов, представляющих емкость хранилища отпечатков пальцев в массиве.

Две хеш-функции:

Функция h1 сопоставляет каждому потенциальному элементу набора число от 0 до N−1. Это дает расположение одной из двух ячеек хеш-таблицы, в которую можно поместить отпечаток пальца для этого элемента.
Функция h2 сопоставляет отпечатки пальцев с числами в диапазоне от 1 до N−1 (включительно). Это не индекс ячейки хэш-таблицы, а скорее разница (или, точнее, побитовое исключающее XOR) любой пары местоположений, в которых должен храниться этот отпечаток.

Отпечатки пальцев

Отпечаток пальца — это bit-string, полученный с помощью хэш-функции. Базовое значение bit-array для преобразования и вставки значений в фильтр.

`b`-количество отпечатков пальцев

Это значение выражает количество отпечатков пальцев, которые может хранить ячейка (слот) в фильтре.

Кукушки Операции

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

Вставки

Фильтры с кукушкой вставляют данные в следующую логическую процедуру:

Вычислите хеш-значение ключа x, а затем уменьшите его значение в соответствии с возможностью получения корзины 1 этого значения. После получения позиции значение вставляется в корзину, назначенную из первой хэш-функции.
Если корзина, рассчитанная по первой хеш-функции, заполнена, вторая хеш-функция вычисляет дополнительную «вторую корзину». Это ведро будет хэш-значением отпечатка пальца, а затем XOR с первым хеш-значением первой хеш-функции. Индекс должен быть рассчитан, поэтому рассчитанное значение затем уменьшается % до его емкости и вставляется позже.

Значения, которые вставляются в фильтры с кукушкой, обычно вставляют значение в первое ведро, назначенное из первой хеш-функции. Если емкость первого и второго указанных сегментов заполнена, то вставляемый новый ключ случайным образом удалит ключ из первого сегмента, и этот удаленный ключ будет помещен во второй сегмент.

Искать

Cuckoo фильтрует поиск ключей в следующей логической процедуре:

Вычислите хеш-значение ключа x, а затем уменьшите его значение в соответствии с возможностью получения корзины 1 этого значения. После получения позиции возвращается подтверждение true/false для проверки существования ключа.
Если корзина, рассчитанная по первой хеш-функции, заполнена, вторая хеш-функция вычисляет дополнительную «вторую корзину». Это ведро будет хэш-значением отпечатка пальца, а затем XOR с первым хеш-значением первой хеш-функции. Индекс должен быть рассчитан, поэтому вычисленное значение затем уменьшается % до возможности проверки его существования.

Удаления

Фильтры с кукушкой удаляют данные в следующей логической процедуре:

Вычислите хеш-значение ключа x, а затем уменьшите его значение в соответствии с возможностью получения корзины 1 этого значения. После получения позиции значение удаляется из корзины, найденной в первой хэш-функции.
Если корзина, рассчитанная по первой хеш-функции, заполнена, вторая хеш-функция вычисляет дополнительную «вторую корзину». Это ведро будет хэш-значением отпечатка пальца, а затем XOR с первым хеш-значением первой хеш-функции. Индекс должен быть рассчитан, поэтому рассчитанное значение затем уменьшается на % до его емкости, а затем удаляется.

Кукушка плюсы и минусы

Преимущества

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

Недостатки

Может вызвать накладные расходы на вставки, когда таблица слишком заполнена
Он может удалять только те элементы, о которых известно, что они были вставлены ранее.
Вставка может завершиться ошибкой, и требуется повторное хеширование, как и в других хеш-таблицах с кукушкой.

Заключение

Фильтры с кукушкой — это структура данных, которая может предотвратить накладные расходы хеш-функций, вызванные фильтрами Блума. Они также могут иметь общий размер, равный или меньший, чем фильтры Блума. Однако одним из самых больших недостатков фильтров с кукушкой является проблема их перемещения, когда фильтр слишком загружен. Эта проблема обычно начинается, когда коэффициент загрузки превышает 50%. Одним из решений является изменение размера фильтра, когда коэффициент загрузки достигает определенного процента. По сути, фильтр должен быть создан с нуля. Несмотря на эту проблему, фильтры с кукушкой являются хорошим вариантом, поскольку они по-прежнему поддерживают низкий уровень ложных срабатываний, даже когда фильтр загружен на 95,5%. Напротив, фильтры Блума обычно имеют высокий уровень ложных срабатываний, когда они загружены на 100%.

Я надеюсь, что вам понравился этот пост, оставьте комментарий и, пожалуйста, подпишитесь на меня, если вам нравится и вы хотите поддержать мое исследование: D

СПАСИБО!!!!

Исходный код фильтра с кукушкой

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

Следующую таблицу я сделал, чтобы иметь ее в качестве эталона диапазона чисел в соответствии с желаемым размером отпечатка пальца.

import random 

class CuckooFilter:
    def __init__(self, capacity, bucket_size, fingerprint_size):
        self.capacity = capacity
        self.bucket_size = bucket_size
        self.fingerprint_size = fingerprint_size
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, value):
        return hash(value) % self.capacity

    def _get_fingerprint(self, value):
        random.seed(hash(value))
        return random.getrandbits(self.fingerprint_size)

    def insert(self, value):
        fingerprint = self._get_fingerprint(value)
        index1 = self._hash(value)
        index2 = (index1 ^ self._hash(fingerprint)) % self.capacity
        bucket1 = self.buckets[index1]
        bucket2 = self.buckets[index2]

        if fingerprint in bucket1 or fingerprint in bucket2:
            return True

        if len(bucket1) < self.bucket_size:
            bucket1.append(fingerprint)
            return True

        if len(bucket2) < self.bucket_size:
            bucket2.append(fingerprint)
            return True

        evicted_fingerprint = random.choice(bucket1)
        bucket1.remove(evicted_fingerprint)
        bucket2.append(evicted_fingerprint)

        return self.insert(value)

    def contains(self, value):
        fingerprint = self._get_fingerprint(value)
        index1 = self._hash(value)
        index2 = (index1 ^ self._hash(fingerprint)) % self.capacity
        bucket1 = self.buckets[index1]
        bucket2 = self.buckets[index2]

        return fingerprint in bucket1 or fingerprint in bucket2

    def delete(self, value):
        fingerprint = self._get_fingerprint(value)
        index1 = self._hash(value)
        index2 = (index1 ^ self._hash(fingerprint)) % self.capacity
        bucket1 = self.buckets[index1]
        bucket2 = self.buckets[index2]

        if fingerprint in bucket1:
            bucket1.remove(fingerprint)
            return True

        if fingerprint in bucket2:
            bucket2.remove(fingerprint)
            return True
        return False