[Перевод] Как фильтры Блума в 16 раз ускорили API

Этот пост станет глубоким разбором того, как мы снизили задержки P95 конечной точки API с 5 до 0,3 секунды при помощи нишевого трюка computer science под названием «фильтр Блума». Мы расскажем о том, почему конечная точка была медленной, о решениях, которые мы рассматривали для повышения её скорости, и о критериях выбора между ними. Также мы объясним, как всё это устроено внутри. Введение Фундаментальная концепция нашего продукта по обеспечению дежурной поддержки (on-call) — это алерты. Алерт — это сообщение, которое мы получаем от систем мониторинга заказчика (например, Alertmanager, Datadog и так далее), информирующее нас о потенциально неправильном поведении его продукта. Наша задача — разобраться, кого нужно вызвать для изучения проблемы. Каждый получаемый алерт сохраняется в старой доброй таблице базы данных. Наличие полной истории о каждом отправленном нам алерте позволяет пользователю выявлять тренды, отлаживать сложные инциденты и анализировать здоровье системы. Также это помогает нам в создании нового поколения ИИ-инструментария SRE. История алертов отображается в дэшборде. Вот, например, как выглядит сегодня наш: Это здорово, но для больших организаций со множеством алертов такой режим отображения не особо информативен. Им нужно изучать подмножества этих данных. Именно это и позволяет делать небольшая кнопка «Filter» в UI. Можно выполнять фильтрацию по таким параметрам, как источник и приоритет. Источник — это система мониторинга, отправившая алерт, а приоритет настраивается индивидуально для каждого пользователя и указывается в получаемом нами сообщении алерта. В UI нашей системы также настроено отображение столбцов «Team» и «Features». Teams — это важнейший параметр в incident.io, а Feature — концепция, определяемая нами. Обе они созданы на основе Catalog. Любой пользователь incident.io может смоделировать в Catalog нужную ему конфигурацию, а затем определить правила, сообщающие нам, как сопоставлять алерт с конкретным элементом. Сегодня эта система очень мощна. Например, я могу сформировать такой запрос: «алерты с приоритетом „срочный“ или „критический“, назначенные дежурной команде и затрагивающие фичу алерта»: Эти фильтры удобны для наших пользователей, но, как выяснилось, потенциально они могут привести к ужасному снижению производительности. В процессе онбординга крупных заказчиков с миллионами алертов наша мощная и быстрая система фильтрации становилась... чуть менее быстрой. Некоторые заказчики сообщали о задержках отображения результатов до 12 секунд. Наши метрики показывали, что время ответов P95 в случае больших организаций составляет 5 секунд. Каждый раз, когда пользователи загружали эту страницу, обновляли фильтр или использовали бесконечный скроллинг для получения следующей страницы, им приходилось слишком долго смотреть на крутящийся индикатор загрузки. Как работает фильтрация (и почему она была медленной) Давайте начнём с объяснения того, как мы храним алерты в нашей базе данных Postgres, и с объяснения алгоритма, который используется для получения множества отфильтрованных результатов. Вот наша таблица alerts в упрощённом виде: +----------+------------------+----------------------+------------------+--------------------------------------------------+ | id | organisation_id | created_at | priority_id | attribute_values | +----------+------------------+----------------------+------------------+--------------------------------------------------+ | $ALERT1 | $ORG1 | 2025-10-31 00:00:00 | $lowPriorityID | { | | | | | | "$myTeamAttributeID": "$onCallTeamID", | | | | | | "$myFeatureAttributeID": "$alertFeatureID" | | | | | | } | +----------+------------------+----------------------+------------------+--------------------------------------------------+ | $ALERT2 | $ORG2 | 2025-10-31 00:01:00 | $highPriorityID | { | | | | | | "$myTeamAttributeID": "$responseTeamID" | | | | | | } | +----------+------------------+----------------------+------------------+--------------------------------------------------+ id — это ULID: уникальный идентификатор, который также можно сортировать лексикографически. Мы используем их для реализации пагинации.$ALERT{N} — это невалидный ULID, мы привели его просто для удобства.organisation_id — это ещё один ULID, идентифицирующий организацию/заказчика.created_at — это временная метка, смысл которой понятен из названия.priority_id — это внешний ключ, ссылающийся на приоритеты, заданные для организации. Каждый пользователь incident.io может настроить подходящие для него приоритеты. При настройке источника алертов наподобие Alertmanager указываются «атрибуты», которые должны находиться в получаемых нами метаданных. В данном примере это priority (приоритет), team (команда) и feature (фича). Такие размерности первого класса, как priority, имеют собственные столбцы в базе данных, а всё индивидуальное для заказчика хранится как attribute_values в JSONB. Алгоритм для вычисления отфильтрованного множества результатов работает следующим образом: Конструирует SQL-запрос с фильтрами, которые можно применить в базе данных Получает из базы данных группы по 500 строк и применяет фильтры в памяти Продолжает получать группы строк, пока не найдёт количество алертов, достаточное для заполнения всей страницы Давайте разберём его на том же примере, что и выше. UI с бесконечным скроллингом скрывает параметры пагинации, но внутри они всегда определены. Давайте сделаем такой запрос: «50 алертов с приоритетом „срочный“ или „критический“, назначенных дежурной команде и затрагивающих фичу алерта». У приоритета есть в базе данных свой столбец, поэтому эту фильтрацию можно поручить Postgres. SQL-запрос для получения первой группы алертов выглядит примерно так: SELECT * FROM alerts WHERE organisation_id = '$ORG1' -- фильтр приоритета можно применить в базе данных AND priority_id IN ('$highPriorityID', '$criticalPriorityID') -- пагинация (подробнее об этом чуть ниже) ORDER BY id DESC -- группирование LIMIT 500 Мы загружаем 500 строк из базы данных в память. Наш ORM десериализует строки в struct Go. Теперь нужно применить фильтры атрибутов, то есть десериализовать JSONB в другие struct Go. Мы проверяем атрибуты team и feature каждого из алертов в группе, и находим 10 совпадающих. Страница может содержать 50 элементов, поэтому нужно выполнить ещё один SQL-запрос для получения второй группы: SELECT * FROM alerts WHERE organisation_id = '$ORG1' -- фильтр приоритета можно применить в базе данных AND priority_id IN ('$highPriorityID', '$criticalPriorityID') -- если у нас 5000 алертов, то так мы пропустим первые 500 алертов AND id < '$ALERT4500' ORDER BY id DESC LIMIT 500 Продолжаем это делать, пока не найдём 50 соответствующих фильтру алертов. Для (organisation_id ASC, id DESC) у нас есть индекс на основе B-дерева, называющийся idx_alerts_pagination и предназначенный для решения именно этой задачи, что, в теории, позволяет сделать запрос каждой группы алертов удобным и эффективным. Однако наихудшим сценарием для этого алгоритма становится случай, когда фильтры базы данных не исключают большого количества строк, что заставляет нас запрашивать множество групп и применять к ним фильтры в памяти. Важнейшим узким местом здесь становится десериализация строки и данных JSONB в соответствующие struct. Наша телеметрия показала, что получение из базы данных и десериализация группы из 500 строк занимала ~500 мс, и только ~50 мс от этого времени тратилось на ожидание возврата результатов запроса. Вы можете подумать: «А затем выполнять фильтрацию атрибутов в памяти?» Хороший вопрос. Я говорил во введении, что атрибуты алертов настраиваются в Catalog. Catalog очень мощен, и чтобы не отвлекаться от темы, я показал лишь упрощённое описание того, что мы храним в JSONB. На самом же деле, значения атрибутов могут быть скалярными литералами, массивами литералов, ссылками на другие элементы Catalog (например, Team) или даже динамическими выражениями («если P1, алерт передаётся CTO, в противном случае — отвечающей за фичу команде»). Всё это сложно, а я хотел сразу перейти к рассказу о фильтре Блума, поэтому просто поверьте, что на тот момент это было разумное проектное решение! Как ускориться Узкое место — получение и десериализация больших объёмов данных из Postgres. Значит, для ускорения лучше всего перенести как можно большую часть фильтрации на сторону базы данных, то есть нужно, чтобы Postgres была способна эффективно использовать данные attribute_values для фильтрации алертов. Мы выделили два спайка решения. Вариант 1: индекс GIN. Это «стандартное» для Postgres решение. GIN (Generalized Inverted Index) создан для индексации сложных типов, в том числе jsonb . Можно создать индекс столбца attribute_values и использовать оператор jsonb_path_ops . Вариант 2: фильтры Блума. Эта идея была предложена Лоренсом Джонсом, одним из разработчиков-основателей компании. Благодаря кодированию атрибутов в виде битовых строк Postgres сможет быстро выполнять побитовые операции «один из». Что за фильтр Блума? Фильтр Блума описывает множество элементов. Мы можем проверить существование элемента и получить один из двух ответов: Элемент точно НЕ находится во множестве Элемент МОЖЕТ находиться во множестве В обмен на такую вероятностную природу этого фильтра мы сможем выполнять очень эффективные по времени и пространству запросы. Само множество — это двоичное представление всех элементов под названием «битовая карта» (bitmap). Элементы добавляются во множество вычислением нескольких хэшей, каждый из которых возвращает значение, соответствующее индексу битовой карты. Для проверки существования элемента мы применяем к элементу те же хэш-функции, создавая ещё одно двоичное представление под названием «битовая маска» (bitmask). Для битовой карты и битовой маски можно при помощи побитовой логики выполнять очень эффективные проверки: bitmap & bitmask == bitmask Давайте разберём это на вымышленном примере: Битовая карта: 8 бит (позиции 0-7), изначально равные 0 Хэш-функции: h1 ,h2 ,h3 (каждая возвращает значения 0-7) Для добавления элемента во множество мы применяем три хэш-функции, каждая из которых возвращает значение, соответствующее позиции в битовой карте. В каждой из этих позиций мы задаём значение 1 в битовой карте. Для добавления нескольких элементов мы повторяем процесс: Добавляем "apple": "apple" ┌───┼──────────┐ ↓ ↓ ↓ h1 h2 h3 │ │ │ 2 5 7 ↓ ↓ ↓ [0][0][1][0][0][1][0][1] 0 1 2 3 4 5 6 7 Добавляем "banana": "banana" ┌──────┼────┐ ↓ ↓ ↓ h1 h2 h3 │ │ │ 1 3 5 ↓ ↓ ↓ [0][1][1][1][0][1][0][1] 0 1 2 3 4 5 6 7 Чтобы проверить наличие элемента во множестве, используем те же три хэш-функции для вычисления других трёх позиций в битовой карте. Если ВСЕ эти позиции в битовой карте равны 1, то элемент МОЖЕТ быть во множестве. Если ЛЮБАЯ из них равна 0, элемент точно отсутствует во множестве. Это логическая операция И: Проверяем "apple": "apple" ┌───┼──────────┐ ↓ ↓ ↓ h1 h2 h3 │ │ │ 2 5 7 ✓ ✓ ✓ = ✅ МОЖЕТ быть во множестве [0][0][1][0][0][1][0][1] 0 1 2 3 4 5 6 7 Проверяем "cherry": "cherry" ┌──────┼───────┐ ↓ ↓ ↓ h1 h2 h3 │ │ │ 1 4 6 ✓ ✗ ✗ = ❌ НЕТ во множестве [0][1][1][1][0][1][0][1] 0 1 2 3 4 5 6 7 Проверяем "grape": "grape" ┌──────┼────┐ ↓ ↓ ↓ h1 h2 h3 │ │ │ 1 3 5 ✓ ✓ ✓ = ⚠️ МОЖЕТ быть во множестве [0][1][1][1][0][1][0][1] (ложноположительный результат!) 0 1 2 3 4 5 6 7 Размер битовой карты и количество хэш-функций можно настраивать для обеспечения баланса между пространством хранения и частотой ложноположительных результатов. Эту частоту можно снижать увеличением размера битовой карты с последующим использованием большего количества хэш-функций, чтобы каждый элемент описывался бóльшим количеством бит. Фильтры Блума атрибутов Узкое место нашего алгоритма фильтрации алертов — получение и десериализация больших объёмов данных из Postgres. Значит, нужно максимально перенести фильтрацию в базу данных. Как нам помогут в этом фильтры Блума? Для начала нам нужно сделать так, чтобы можно было обрабатывать фильтры значений атрибутов, как операции над множествами. Если алерт имеет следующие значения атрибутов JSONB: { "$teamAttributeID": "$onCallTeamID", "$featureAttributeID": [ "$alertsFeatureID", "$escalationsFeatureID" ] } то представив значение атрибута в виде строки, можно описать эти значения атрибутов, как множество строк: { "$teamAttributeID:$onCallTeamID", "$featureAttributeID:$alertsFeatureID", "$featureAttributeID:$escalationsFeatureID" } Теперь поиск алертов с определённым значением атрибута превратился в операцию над множествами — мы проверяем, присутствуют ли в этом множестве закодированный в строку ID и значение. Можно превратить множество значений атрибутов в фильтр Блума, хэшируя каждый закодированный в строку элемент для вычисления битовой карты. Также можно представить в виде битовой маски каждое значение атрибута, которое мы хотим фильтровать, и при помощи побитовой логики получать эффективный, хотя и вероятностный ответ. Существуют удобные математические операции для определения количества битов, необходимых в битовой карте, и количества хэш-функций, которые необходимо применять для достижения требуемой частоты ложноположительных результатов при указанной кардинальности. В нашем случае для достижения частоты в 1% ложноположительных результатов для всех значений атрибутов в таблице alerts понадобилось 512 бит и семь хэш-функций. Вычисление битовой карты выглядит так же, как и в искусственном примере выше, только с бóльшим количеством хэш-функций и бит: Добавляем "$teamAttributeID:$onCallTeamID": "$teamAttributeID:$onCallTeamID" ┌─────┬─────┬─────┼─────┬─────┬─────┐ ↓ ↓ ↓ ↓ ↓ ↓ ↓ h1 h2 h3 h4 h5 h6 h7 │ │ │ │ │ │ │ 2 17 143 216 342 487 501 ↓ ↓ ↓ ↓ ↓ ↓ ↓ [0] [0] [1]...[1]...[1]...[1]...[1]...[1]...[1]...[0] [0] 0 1 2 17 143 216 342 487 501 510 511 Мы вычисляем эту битовую карту при каждом изменении значений атрибутов алерта и храним её в столбце attribute_values_bitmap Postgres как тип Bit String: bit(512) . Когда нам нужно найти алерты, соответствующие каким-то фильтрам атрибутов, мы вычисляем битовые маски с использованием тех же функций кодирования строк «ключ-значение» и хэш-функций. Postgres может выполнять bitmap & bitmask == bitmask и делает это быстро благодаря типу Bit String. Вот SQL-запрос «50 алертов с приоритетом „срочный“ или „критический“, назначенных дежурной команде и затрагивающих фичу алерта»: SELECT * FROM alerts WHERE organisation_id = '$ORG1' -- фильтр приоритета можно применять в базе данных AND priority_id IN ('$highPriorityID', '$criticalPriorityID') -- теперь мы можем фильтровать значения атрибутов в базе данных! AND attribute_values_bitmap & '$onCallTeamBitmask' == '$onCallTeamBitmask' AND attribute_values_bitmap & '$alertsFeatureBitmask' == '$alertsFeatureBitmask' ORDER BY id DESC -- пагинация LIMIT 500 -- группирование Благодаря частоте ложноположительных результатов в 1% теперь мы выполняем лишь 1% от той работы по десериализации, которую мы проделывали раньше. Нам всё равно приходится проверять результаты в памяти для устранения ложноположительных результатов, но это вполне приемлемый оверхед. Отлично! GIN против Блума Теперь, когда мы знаем, как работают фильтры Блума, давайте перейдём к результатам спайков. Мы прототипировали каждый из вариантов и замерили скорость в паре ключевых сценариев. Вот результаты: GIN | Блум | | |---|---|---| Сценарий 1: частые алерты | 150 мс | 3 мс | Сценарий 2: редкие запросы | 20 мс | 2-300 мс | Оба сценария рассматривались для организации с ~1 миллионом алертов. «Частые алерты» — это запрос, находящий соответствие ~500 тысячам из 1 миллиона алертов, а «редкие алерты» — запрос, находящий соответствие только ~500. План запросов индекса GIN выглядел так: Используем индекс GIN для эффективного нахождения всех алертов, соответствующих фильтрам Считываем все алерты Сортируем и берём верхние 500 Когда фильтрам соответствуют 500 алертов, это происходит очень быстро. Когда фильтрам соответствует 500 тысяч алертов, то приходится считывать все 500 тысяч, а потом отбрасывать 495,5 тысяч в LIMIT 500 . План запросов фильтра Блума выглядит так: Используем idx_alerts_pagination для «потоковой передачи» кортежей алертов, отсортированных по IDФильтруем «поток» эффективной побитовой логикой Продолжаем, пока не найдём 500 соответствующих кортежей Когда фильтрам соответствует 500 тысяч алертов, это происходит очень быстро, потому что вероятность соответствия каждого алерта равна 50% и в конечном итоге мы считываем только небольшую часть индекса. При соответствии фильтрам 500 алертов вероятность соответствия каждого алерта равна 0,05%, и нам приходится считывать гораздо большую часть индекса. Задержки находятся с достаточным запасом в пределах допустимого, что улучшает user experience. Мы не смогли придумать веских причин, по которой сценарий с частыми алертами был бы предпочтительнее сценария с редкими, и наоборот, поэтому с точки зрения производительности это можно считать ничьей между двумя вариантами. Однако выше я уже объяснил критическую проблему обоих подходов — их объёмы растут с количеством алертов организации. Мы храним полную историю алертов заказчиков, поэтому хотя сегодня оба варианта обеспечивают нужные нам результаты, со временем производительность будет деградировать. Обманчивое время Пока мы занимались всеми этими вычислениями и computer science, оставался незамеченным очевидный факт. Для сортировки алертов по времени получения используется пагинация, и в UI мы первым делом показываем пользователям самые новые алерты. Чаще всего их интересует недавняя история, тем не менее, наши запросы могут становиться затратными, потому что мы выполняем поиск до самого первого отправленного нам алерта. Зачем? Если мы сможем разбить данные по времени, то у нас получится использовать этот вполне разумный перекос по давности алертов для сильного повышения производительности. В дэшборде есть фильтр для столбца created_at таблицы alerts . Мы сделали его обязательным и установили в качестве значения по умолчанию 30 дней. У нас уже даже есть готовый к использованию индекс idx_alerts_created_at для (organisation_id, created_at) ! Теперь в плане запросов индекса GIN применяется два индекса: Находим пересечение индексов для нахождения всех новых алертов, соответствующих фильтрам idx_alerts_attribute_values применяет фильтрыidx_alerts_created_at находит алерты за последние 30 дней Считываем все алерты Сортируем и берём верхние 500 Благодаря очень полезной особенности, о которой мы говорили в начале, план запросов фильтра Блума менять совершенно не нужно. ID алертов — это ULID: уникальные ID, которые можно сортировать лексикографически. ULID состоят из двух компонентов; временной метки и случайной части. Можно использовать в качестве временной метки «30 дней назад», добавить в конец немного случайности и использовать этот ID в запросе диапазона с idx_alerts_pagination . Строго говоря, оба плана масштабируются с количеством алертов организации, но амортизированные затраты в этом случае гораздо лучше. Пользователи могут выбирать для анализа большие временные диапазоны, обработка которых потребует какого-то времени, но в обмен мы получаем повышение производительности в гораздо более частых сценариях использования. Чтобы используемое по умолчанию окно в 30 дней начало вызывать проблемы UX, у нас должны появиться заказчики с чудовищными объёмами алертов. Это было бы интересной проблемой, но пока мы не считаем, что нужно проектировать систему для её решения. Теперь, когда мы решили проблему масштабирования, приходится возвращаться к нашей патовой ситуации. Как выбрать, какой вариант реализовать? Наша команда вела длительные споры, с уважением друг к другу, но дотошно. Индексы GIN могут быть большими на диске и в памяти, иметь большой оверхед записи. Мы беспокоились о том, что с увеличением индекса он может занимать слишком много места в общих буферах Postgres, потенциально снижая производительность в других частях платформы. У нас не было уверенности в том, что нам не придётся спустя несколько месяцев решать новую, гораздо более тонкую проблему. Фильтры Блума — довольно нишевая тема, мы думали, что код будет сложно понимать и изменять разработчикам, не участвовавшим в исходном проекте. К тому же, нам не хотелось реализовывать, по сути, собственный механизм индексации, ведь для этого предназначены базы данных. В конечном итоге, мы были сильно против мысли о повторной переработке системы и сделали ставку на то, что точно придётся создавать только один раз, пусть это и будет чуть сложнее — фильтр Блума. Заключение Обязательное 30-дневное ограничение в сочетании с фильтрацией Блума привело к огромным изменениям: время отзывов P95 в случае крупных организаций снизилось с 5 секунд до 0,3 секунды. Улучшение примерно в 16 раз! Фильтр Блума уменьшает количество строк в каждой группе, а обязательное ограничение по времени снижает максимальное количество групп. Наша мощная и удобная фильтрация снова стала быстрой, и продолжит такой оставаться даже при появлении новых крупных заказчиков. На сентябрь 2025 года мы потребляли более миллиона алертов в неделю, и это число будет только увеличиваться! Это отличный пример того, как техническое и продуктовое мышление могут идти рука об руку. Мне повезло, что довелось решать эту сложную техническую задачу вместе с невероятно талантливыми разработчиками. Однако очень важным куском пазла также стало понимание наших заказчиков и того, как они пользуются нашим продуктом. Для успешного решения нам понадобилось и то, и другое.