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

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

Мотивирующий пример

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

Крайне важно избегать дублирования одной и той же функции на одном работнике. Наличие списка функций в режиме реального времени на ~10 000 быстро меняющихся рабочих узлах, каждый из которых выполняет около 1 000 функций, может решить эту проблему, но получение этой информации оказывается сложной задачей из-за огромного объема данных, которые необходимо постоянно передавать.

Теперь рассмотрим другое решение. Каждые несколько секунд каждый рабочий узел создает фильтр Блума размером ~ 1 КБ, включающий все имена его активных функций, и передает его на серверы размещения. Этот фильтр помогает определить, куда назначать новые функции, сводя к минимуму связанные рабочие нагрузки. Этот подход требует лишь части передачи данных по сравнению с предыдущим подходом, при этом исключая сложности дельта-/антиэнтропийных протоколов или обслуживания базы данных. Счетные фильтры Блума также могут отслеживать количество запущенных копий для каждой функции, если вы можете позволить себе больше памяти.

Вероятностное членство

Вероятностное членство — это класс алгоритмов, в которых мы можем выполнить операцию .contains(), сохранив лишь небольшую часть исходных данных. С другой стороны, в зависимости от того, как вы спроектируете свою структуру данных, вы увидите некоторые ложные срабатывания (.contains говорит «да», но элемента нет в наборе), но никогда не увидите ложноотрицательных результатов. Хотя эта базовая модель уже довольно полезна, за прошедшие годы было предложено много вариантов, которые добавляют гораздо больше интересных функций.

На высоком уровне АТД — назовем его ProbableSet — выглядит так:

class ProbableSet:
  def insert(key) -> None:
    # Must be implemented in all impl
    pass

  def maybe_contains(key) -> bool:
    # Must be implemented in all impl
    pass

  def delete(key) -> None:
    # The deleter must know the key was inserted
    # Only select implementations like Counting BF and Cuckoo filter
    pass

  def get_count_if_contains(key) -> int:
    # Will return wrong value if it's a false positive
    # Only select implementations like Counting BF
    pass

  def count() -> int:
    # Returns the count of keys
    # Most implementations can approximate this but it's easy enough to 
    # track the actual number.
    pass

Существует два класса алгоритмов, которые используются для реализации этого АТД, а именно: 1) фильтр Блума и его производные и 2) алгоритмы на основе идеальной хеш-функции.

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

Производные фильтра Блума

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

k = ln 2 * (m / n)

если вы выберете k таким образом, отношение между m, n и вероятностью ложного срабатывания p будет примерно таким:

m/n = - 1.44 log2(p)

Итак, если у вас есть ~ 1000 ключей и вам нужна вероятность ложного срабатывания 0,01, вам нужно около 9,5 КБ бит (около КБ).

Классические фильтры Блума

Эта структура данных была изобретена в 1970 году и до сих пор находит широкое применение на практике. Это наиболее компактная структура данных, но она поддерживает только запросы на членство. Вы не можете удалять, подсчитывать или удалять вещи.

Подсчет фильтров Блума

Это очень универсальная и, пожалуй, моя любимая структура данных. Он использует больше битов на позицию в массиве и сохраняет количество хэш-функций, попадающих в эту позицию, а не только 1 и 0. При проверке только существования вы ищете ненулевое значение вместо 1. При удалении элемента вы уменьшаете значение число на 1. При проверке количества вы просматриваете все k позиций и возвращаете наименьшее из этих чисел.

Счетный аспект этой структуры данных делает ее идеальной для хранения частот ключей в большом потоке данных, когда количество ключей относительно невелико, например, в службах метрик. Точно такая же структура данных в мире метрик называется Count-min Sketch. Использование двух копий вместо одной — это хак, который используется для улучшения показателей ложных срабатываний классического фильтра Блума и требует только 2*m памяти вместо m.

Скользящие фильтры Блума

Здесь вы храните два массива вместо одного — старый и новый. Это может быть как классический, так и счетный фильтр Блума. Вставки и удаления всегда происходят в новом массиве, в то время как при поиске используется и то, и другое (путем добавления или объединения ИЛИ). Когда выполняется определенное условие, например, прошло X минут или вставлено Y элементов, мы выбрасываем старый массив и дорабатываем другой. Это полезно, когда вы используете их в потоке запросов в течение длительного времени.

Вы также можете выполнять выселения в стиле LRU, продвигая элементы от старых к новым, когда они «находятся». Есть много забавных вариантов этой структуры данных.

Другие варианты

Учитывая, насколько просты и гибки фильтры Блума, неудивительно, что существует целая кустарная промышленность по поиску способов их улучшения. Согласно этому опросу, существует 60+ известных вариантов. Если вы подумаете об этом некоторое время и придумаете умную идею, у нее уже есть имя.

фильтры с кукушкой

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

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

Одним из недостатков фильтров Cuckoo является то, что они имеют жесткое ограничение емкости, поэтому их использование в потоковых, долгосрочных случаях использования сложно. Их можно изменять или дополнять, но реализация для них нетривиальна.

Примечание о хеш-функциях

Вычисление такого количества хэшей также может показаться пугающим. Однако важно понимать, что не все хэши требуют больших вычислительных ресурсов. Что касается хэшей структур данных, держитесь подальше от криптографических хэшей, таких как SHA256, если у вас нет очень веской причины. Моя любимая хэш-функция для этих случаев использования — murmur-hash v3, которая дешева в вычислении и очень хороша со свойствами хэша, которые нам важны — равномерное распределение и случайность.

Более того, нам даже не нужно вычислять все k хешей. Есть замечательное исследование, которое показывает, что мы можем просто использовать одну 64-битную хеш-функцию, разбить вывод на два 32-битных значения, v1 и v2, а затем подделать столько хеш-функций, сколько нам нужно. хотите использовать форму v1 + k*v2. Код выглядит следующим образом:

def k_hashes(word, k):
    h = mmh3.hash64(word, signed=False)[0]
    h1 = h & (2**32 - 1)
    h2 = h>>32
    
    hashes = []
    for i in range(k):
        h = h1 + i * h2
        if h < 0:
            h = ~h
        hashes.append(h)
    return hashes

При использовании Java в Guava есть довольно хорошая реализация классических фильтров Блума, которая использует хэш Murmur с описанным выше трюком.

При использовании murmur3 имейте в виду, что оптимизированные версии для 32-битной и 64-битной платформ дают разные результаты для одних и тех же ключей, поэтому при совместном использовании фильтров в сети устройств, работающих на обоих типах машин, выберите одну реализацию и запустите на всех — даже если это не так. оптимальный.

Дополнительные примеры

В дополнение к приведенному ранее примеру, вот еще несколько идей, которые мотивируют вас попробовать эти замечательные структуры данных в вашей собственной работе:

  1. Фильтры Блума действуют как краткие хранилища часто используемых записей. Это отлично подходит для разогрева кешей при развертывании нового узла кеша. Вы можете ошибочно кэшировать небольшое количество записей, но никогда не кэшируйте недостаточно. Это отличная статья, описывающая эту систему ​​в Akamai.
  2. При поддержке пула независимых узлов кеша одна из стратегий для получения хорошей частоты попаданий — это регулярная синхронизация фильтра Блума содержимого узла кеша со всеми клиентами. С ложными срабатываниями можно справиться с помощью сквозного чтения или отсрочки на стороне клиента.
  3. Брандмауэры или средства проверки черного списка — отличный вариант использования фильтров Блума. Поскольку пакеты или запросы, как правило, неплохие, тот факт, что фильтры Блума не могут иметь ложных срабатываний, очень удобен. Если вы нажмете положительный результат, вы можете свериться с авторитетным источником и кэшировать результат локально.
  4. В распределенных базах данных операция соединения SQL может выиграть от фильтров Блума. Вместо отправки всех ключей соединения другой стороне вы отправляете только фильтр, а другая сторона отвечает всем, что соответствует фильтру. Пока ложные срабатывания незначительны, это экономит время и пропускную способность сети. Этот метод называется соединением Блума.
  5. В поисковых роботах фильтры Блума могут отслеживать уже посещенные URL-адреса. Они могут поддерживаться многими серверами по отдельности и могут сочетаться с операцией ИЛИ. В этом случае ложные срабатывания могут повредить, но поскольку поисковые роботы могут довольно точно оценить количество URL-адресов для сканирования, можно разработать фильтр с низким значением FP.
  6. Биткойн, по-видимому, использует фильтр Блума для загрузки несвязанных данных транзакций на легковесных клиентах. Это уместно, поскольку история транзакций в блокчейне представляет собой набор хэшей, как и фильтр Блума!