Привет, это Антон Пионтковский из команды Monium Metrics, и вместе с коллегами мы создаём observability‑платформу для сбора, хранения и анализа телеметрии Yandex Monium. Мы храним миллиарды метрик и обрабатываем 50 гигабайт логов в секунду, а внутри Яндекса с Monium работают 16 тысяч сотрудников.

Чтобы справиться с объёмом метаданных метрик Kubernetes, мы научились фильтровать их по времени. Сначала наивно с помощью линейного сканирования, и потому только для небольшого круга пользователей. Но результат нам так понравился, что мы захотели включить фильтр для всех. Поскольку первоначальный подход нельзя было скейлить, мы использовали специальный — range encoded bit sliced — индекс, и получили ускорение в 6–20 раз, а в удачных случаях — до двух порядков.

Расскажу, как мы дошли до такой жизни, как устроен этот индекс, и что потребовалось сделать, чтобы всё в продакшн‑среде работало быстро.

История копится

В Monium пользователь может собирать телеметрию со своего сервиса в виде метрик. Сервис может быть запущен на нескольких тысячах подов — подходящий размер для нагруженного сервиса в Kubernetes. С каждого пода собирается набор типовых метрик: container_cpu_usage_seconds_total, http_requests_total, и так далее.

Однако поды в Kubernetes короткоживущие. Каждый деплой создаёт новый набор подов с новыми именами: my-app-5b7644f7f6-4hb8s, my-app-7c9f8a4d2b-x8gpr, my-app-9e2c1a8f3d-q7zvr. У активной разработки — два‑три деплоя в обычную неделю, плюс пара хотфиксов в плохую. Каждый релиз добавляет несколько тысяч новых значений метки pod.

При этом количество активных подов не поменялось, это всё те же несколько тысяч. Но метрики хранят не только текущий набор имён, а также и историю по ним. Поэтому в сервисе метаданных через пару недель накапливается полтора‑два десятка тысяч уникальных значений pod — следы каждого деплоя за всё время. И при запросе метрик с именем container_cpu_usage_seconds_total metabase честно возвращает метрики со всеми этими подами, даже если запись в них давно прекратилась. Срабатывает печально известная защита от перегрузки и вы видите ошибку Too many metrics are loaded by selectors.

Лимит на загрузку метрик по селекторам в первую очередь служит для защиты мультитенантной системы. Один пользователь не должен в одном запросе вытащить сотни тысяч временных рядов и заказать на них тяжёлую математику. Иначе это отразится на производительности запросов других пользователей.

Но из описанной ситуации можно выйти, если запастись парой технических решений.

Где живут метрики

Метрика в Monium — это пара: набор лейблов и временной ряд. Лейблы имеют вид container_cpu_usage_seconds_total{pod='my-app-5b7644f7f6-4hb8s', container='app'}, а временной ряд — это точки, отсортированные по времени измерения.

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

• Сервис метаданных (metabase) держит лейблы и адресацию: где конкретный временной ряд найти в сервисе данных. Адрес — пара (stockpile_shard_id, stockpile_shard_local_id). Дополнительно хранится created_at_seconds — время создания метрики. Единица хранения — шард: лейблы могут повторяться только если шард отличается. Эти шарды видно в интерфейсе Monium.

• Сервис данных (stockpile) возвращает временные ряды по паре адресов из metabase. Шарды в нём тоже есть, но они служат балансировке нагрузки, а не логическому делению. Их в интерфейсе не видно.

Поэтому любой запрос за метриками композитный: сначала metabase отвечает метаданными по селектору из запроса, затем stockpile временными рядами.

Обратный индекс на лейблах

Большая часть запросов в metabase — это фильтрация по лейблам. Например, метрика подходит под селектор container_cpu_usage_seconds_total{pod=~'my-app-.*'} если у неё name = container_cpu_usage_seconds_total И pod соответствует регулярному выражению. По сути это фасетный булев поиск. Чтобы отвечать на такие запросы быстро, в metabase реализован обратный индекс на битовых масках.

Каждой паре (label, value) соответствует битовая маска, в которой бит на позиции i равен 1, если у метрики с порядковым номером i есть этот лейбл с этим значением. Порядковый номер метрики называется rid (record index). Мы используем порядковый номер метрики внутри шарда, который каждый раз назначаем сами во время выполнения приложения. Такой подход позволяет нам держать значения внутри битовых масок максимально плотно друг к другу, что улучшает сжатие.

Запрос container_cpu_usage_seconds_total{pod=p1} сводится к битовому AND масок name=container_cpu_usage_seconds_total и pod=p1. Запрос container_cpu_usage_seconds_total{pod=~'my-app-.*'} — к OR всех масок pod по подходящим значениям, потом AND с маской name=container_cpu_usage_seconds_total.

Дальше будем называть такую структуру просто «обратный индекс».

Старый мир: человекочитаемые имена хостов

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

Отсюда было принято несколько решений в архитектуре metabase:

• Метаданные хранятся плоско: внутри шарда нет часовых или дневных сегментов, всё лежит сплошняком в базе, в памяти для амортизации обновлений используется LSM‑подобная структура. По сути, что‑то вроде write‑through cache.

• Обратный индекс живёт в памяти как часть LSM‑подобной структуры. На каждом уровне он свой, перестраивается при изменении уровня. Самый верхний уровень — небольшой и горячий, перестроение там дёшево и происходит при добавлении новых метрик. Самый нижний — большой, перестраивается редко (только при переполнении предыдущих), стоимость перестроения амортизируется.

• В памяти лежит хеш‑таблица «лейблы → rid» — основа для построения обратного индекса. Набор лейблов {host='pod5', name=cpu}: 10 распадается в две маски, в каждой из которых устанавливается бит с номером 10.

Это работало хорошо, пока к нам не пришёл Kubernetes.

Как K8s ломает индекс

Предположение «лейблы стабильны» сломалось. Поды живут десятками часов или меньше, а не месяцами. Кардинальность растёт линейно во времени независимо от того, сколько подов сейчас активно. С точки зрения metabase каждый новый под — это сотни новых записей с новым значением pod. Обратный индекс по лейблам ничего про время не знает: запрос за pod=* честно возвращает все исторически встречавшиеся значения.

У других систем на этот случай есть ответ. У Prometheus данные нарезаны на двухчасовые сегменты, у VictoriaMetrics — на дневные индексы. Любой селектор по умолчанию ограничен теми сегментами, которые пересекаются с интервалом запроса. Так как у нас сегментов нет, то нужен был другой механизм отсечения по времени, который бы не потребовал полной переделки системы.

Наивный фикс: last_point_seconds

Первое, что мы сделали, добавили в metabase поле last_point_seconds для каждой метрики. Это время записи последней точки в метрику. Вместе с created_at_seconds оно описывает временной интервал, в течение которого метрика «жила». Метрика подходит под запрос с интервалом [from, to], если её отрезок пересекается с интервалом запроса:

created_at_seconds ≤ to  AND  last_point_seconds ≥ from

Зачем это нужно? Запрос container_cpu_usage_seconds_total{pod='my-app-...'} за последний час должен возвращать только те поды, которые жили в этот час. Поды от вчерашнего деплоя в ответ попадать не должны — их last_point_seconds остался в прошлом.

Со включённым фильтром обратный индекс находит все метрики с подходящими лейблами, а потом линейным сканом по результирующему списку отбрасываются те, чьи отрезки не пересекают окно запроса.

Чтобы держать last_point_seconds актуальным, его надо периодически обновлять. Однако, сервис для ingestion — coremon — использует metabase только один раз: когда он не знает, по какому адресу ((stockpile_shard_id, stockpile_shard_local_id)) писать метрику. После того, как coremon разрезолвит метрику, metabase больше не участвует в записи и не получает время последней точки. Чтобы не нагружать stockpile, metabase опрашивает его батчами раз в четыре часа: для каждой метрики приходит свежее значение last_point_seconds. При этом на случай недоступности stockpile закладывается половина этого интервала, что в совокупности «продлевает» метрику на шесть часов. Это происходит только для метрик, которые имеют время записи последней точки близко к запрашиваемому интервалу: если метрика не записывалась уже давно, то считается, что за это время батч‑запрос успешно завершился, и такому времени можно верить.

Это означает, что в любой момент времени last_point_seconds в metabase может быть устаревшим — с момента обновления времени последней записи метрика могла писаться без остановки, но metabase об этом ещё не знает. Чтобы не потерять метрики, в которых запись продолжается, при фильтрации мы расширяем last_point_seconds вправо на интервал обновления:

last_point_seconds + 6h ≥ from

Это даёт ложноположительные включения: метрики, в которых запись на самом деле прекратилась четыре часа назад, попадают в ответ как «может быть ещё пишется». Это безопасный компромисс — лучше вернуть чуть больше метрик, чем потерять действительно активную запись.

Ещё одно допущение: мы считаем, что между created_at_seconds  и last_point_seconds запись идёт непрерывно. Если в метрике были долгие паузы, фильтр их не различает. Это позволяет удерживать индексные структуры приемлемого размера.

---

Фильтр закрыл главный кейс — известные запросы пользователей, которые пользуются Kubernetes. Но включить такой фильтр на всех мы не смогли.

Во‑первых, он работал полным сканированием данных — после ответа обратного индекса нужно было пройти по списку найденных метрик и для каждой проверить пересечение отрезка с окном. На широких запросах вроде подсказок значений лейблов, где found set мог быть весь шард, такой проход уже сам по себе становился узким местом.

Во‑вторых, мы не могли точно отвечать на вопрос «сколько метрик найдено». Когда пользователь запрашивает первые 100 метрик с лимитом, мы должны вернуть top-100. Из‑за линейного сканирования мы могли набрать сами 100 метрик быстро, но не могли посчитать общую кардинальность ответа без прохода по всему списку.

Нам была нужна структура, которая отвечает на «попадает ли метрика в окно» за время, не зависящее от размера found set.

Enter the Range Bitmap

Наш обратный индекс всегда использовал Roaring Bitmap для компактного представления битовых масок в памяти и быстрой работы с ними. Подход Roaring Bitmap основан на том, что всё множество значений разбивается на диапазоны, по старшим 16 битам числа. После этого, в нижних 16 битах бакета выбирается наиболее подходящая для них структура хранения:

• array для разреженных значений, если их не более 4096;

• run для последовательностей;

• bitmap для остальных случаев (65_536 значений).

Для быстрого поиска контейнеров в long‑версии Roaring Bitmap используется структура под названием Adaptive Radix Tree (ART), для int‑версии используется обычный массив и бинарный поиск.

В Java‑версии Roaring есть интересный класс под названием RangeBitmap. Он предназначен для индексирования значений типа long. При этом rid индексируется неявно — каким по счёту был добавлен очередной long, к такому rid он и относится. К индексированным значениям можно задавать запросы вида gte, eq, lte. Результатом такой операции является Roaring Bitmap. Поэтому если индексировать last_point и created_at в том же порядке, в каком они добавляются в обратный индекс, то можно просто пересечь ответ RangeBitmap с обычным поисковым результатом, и таким образом добавить в систему фильтр по временному диапазону.

RangeBitmap — иммутабельная структура. При добавлении нового значения нужно перестроить индекс целиком. Из‑за существующей LSM‑подобной структуры метаданных метрик это не составило проблем. Новые метрики попадают на верхний уровень, периодически уровни сливаются. На каждом уровне свой RangeBitmap. Верхний — маленький, перестроение происходит часто, но оно дешёвое из‑за размера уровня. Нижний — большой, но его перестроение редкое, лишь при слияниях. Запросы выполняются независимо по всем уровням, а затем итоговый ответ объединяется.

На каждом уровне нашей LSM‑подобной структуры стало уже по три индекса: обратный индекс для поиска по фасетам, к которому теперь добавились индексы по created_at_seconds и last_point_seconds, основанные на RangeBitmap. Мы просто выполняли три независимых запроса и делали AND между их результирующими битовыми масками. Оказалось, что в продакшн‑среде это работало чудовищно. Некоторое усилия во время расследования причин были потрачены даже в направлении SIMD: профиль подсказывал, что битовые операции внутри RangeBitmap можно попробовать ускорить векторными инструкциями, и всё должно бы заработать. К сожалению, Vector API не дал никакого прироста.

Добиться улучшения получилось после очередного перечитывания API: к RangeBitmap есть способ приложить сужающий контекст — внешнюю битовую маску, ограничивающую множество rid, для которых нужен ответ. Если контекст уже маленький (например, обратный индекс по pod оставил пять метрик), то и ответ считается только для них.

Передали так: использовали результат от обратного индекса как контекст для last_point, а его результат — как контекст для created_at. Этот подход работает до сих пор и обеспечивает фильтрацию по времени в продакшне. Он основан на интуиции, что last_point кластеризуется сильнее, чем created_at, что должно сделать индекс по нему более производительным.

Благодаря этому фильтр по времени был запущен в подсказках значений, где раньше был запрещён из‑за потенциально широкого found set. А затем и в алертах, где лимит на загрузку метрик ещё жёстче, чем в интерактивных запросах: алерты — фоновая активность, выполняется часто и легко нагружает систему широким селектором.

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

Как устроен range-индекс

Открытый вопрос 

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

Возьмём восемь любых метрик. Для каждой смотрим только одно поле — last_point_seconds. Даты записи последней точки лежат в окне получаса. В виде секунд от эпохи это что‑то вроде 1746636234, 1746637543, 1746636000 — десятизначные числа. Каждое значение требует 31 бит хранения. При том, что вся реальная вариативность укладывается в полчаса, меньше двух тысяч секунд.

Естественно вынести минимум в метаданные индекса и работать с разностями Δ = x − min. Минимум в этом наборе — 11:00:00. После вычитания получаем диапазон [0, 1876], что укладывается в ⌈log₂(1876 + 1)⌉ = 11 разрядов.

То есть запрос вида «всё, что записано после 11:16:40» можно превратить в Δ > 1000. То есть ожидаемый ответ: {1, 4, 5, 6} — те rid, у которых Δ больше 1000. Цель — получить эту битовую маску из индекса, без обращения к данным.

Equality encoding

Битовые индексы классифицируются по смыслу установленного бита. Equality encoding значит, что в битовой маске для значения v бит на позиции i равен 1, если Δ_i = v. В примере все восемь значений уникальны, значит — нужно восемь битовых масок, при этом в каждой маске установлен только один бит.

Запрос Δ = 1543 — это один лукап в индексе и одна маска. Запрос Δ ∈ {234, 1289} — два лукапа и OR двух масок. А вот запрос Δ > 1000 сложнее: нужно перебрать все значения, для которых это так — {1289, 1543, 1620, 1876} — и сделать OR по их битовым маскам.

Сложность range‑запроса линейна по кардинальности значений в диапазоне. Если бы мы индексировали last_point_seconds с секундной точностью, в окне запроса шириной в час оказалось бы 3600 значений; OR по такому количеству масок — это уже не индекс, а ещё один способ линейного сканирования.

Range encoding

Поменяем смысл бита. Раньше бит на позиции i в битовой маске для значения v означал «у строки i значение равно v». Сделаем так: пусть теперь бит означает «у строки i значение меньше или равно v».

Для нашего набора это выглядит так:

Чем выше порог, тем больше rid ему удовлетворяет, и тем больше единиц в маске. Это и называется range encoding: кодируется не значение, а полуинтервал (−∞, v].

Range‑запрос теперь обрабатывается одним лукапом. Δ ≤ 1000: бинарным поиском находим в индексе наибольшее v ≤ 1000, получаем v = 947, берём его битовую маску 10110001 — готово. Запрос Δ > 1000 — это инверсия: NOT(10110001) = 01001110, что и есть ожидаемый ответ {1, 4, 5, 6}.

Чтение значительно ускорилось. Но битовых масок всё ещё столько же, сколько уникальных значений. Для секундного last_point в шарде с десятками миллионов метрик это десятки тысяч масок на индекс. Такой индекс очень нетривиален в построении: каждый локальный минимум требует обновления масок для всех значений, которые больше него.

Чтобы это исправить, надо поменять подход к схеме хранения значения в индексе.

Bucketing как тривиальный вариант с потерей точности

Вместо маски на каждое уникальное значение можно объединить значения в bucket'ы фиксированной ширины: [0, 100), [100, 200),..., [1800, 1900) — 19 масок вместо ~2000.

Для запроса Δ > 1000 индекс отдаст «все rid из bucket'ов 1000–1099, 1100–1199,...» — без точной локализации внутри bucket'а. Каждый rid из ответа всё равно потребует сверки с данными: попадает ли его настоящее значение под > 1000. Из‑за группировки такой индекс перестаёт быть «покрывающим».

Для last_point с секундной точностью и запросов на минуты/часы такая точности может приводить к значительному росту ложноположительных ответов.

Bit‑slicing

Число 1289 — это 1·10³ + 2·10² + 8·10¹ + 9·10⁰. Значение восстанавливается из этого набора однозначно, значит — для запоминания значения достаточно запомнить его разряды.

В индексе на каждый разряд заводим 10 битовых масок — по одной на каждую цифру 0–9. Маска «в разряде сотен стоит цифра 2» собирает все rid'ы, у которых сотни равны 2 (значения 200–299, 1200–1299,...). Запись 1289 ставит ровно один бит в каждый из четырёх разрядов: тысячи → 1, сотни → 2, десятки → 8, единицы → 9.

Для значений [0, 9999]: 4 разряда × 10 цифр = 40 масок независимо от того, сколько уникальных значений реально встречается в данных. Range encoding линейно по кардинальности — для секундного last_point в шарде с десятками миллионов метрик это десятки тысяч масок. Bit‑slicing разрывает эту связь: число масок зависит только от диапазона, не от кардинальности.

Идея обобщается на любое основание b: digit_count × b масок. Чем больше b, тем больше масок на разряд, но самих разрядов меньше.

Для двоичной системы счисления b = 2 каждый разряд это бит, и в нём всего две возможные цифры — 0 и 1. Для значений [0, 1876] нужно ⌈log₂(1877)⌉ = 11 разрядов и 11 × 2 = 22 маски. Так last_point в окне получаса с секундной точностью укладывается в 22 битовые маски вне зависимости от того, сколько уникальных секунд встретилось. В bit‑sliced индексе хранится по маске на каждую пару (разряд, цифра). Вставка значения 1289 — это записать по биту в каждую из 11 масок разрядов, в зависимости от того, какая цифра стоит в соответствующем разряде. Никакого «прохода по всем бо́льшим значениям», как в range encoding.

Однако такой индекс — это пока что equality encoding на уровне каждого разряда: бит маски значит «цифра в разряде равна c». Range‑запрос всё ещё потребовал бы OR'а нескольких масок (для разряда k запрос digit_k ≤ 5 это OR пяти масок). Чтобы получить точный быстрый range — совместим bit‑slicing с range encoding.

Алгоритм выполнения запроса к range‑индексу

Как понять, какое из чисел 1289 = 10100001001 и 1620 = 11001010100 больше? Идём от старшего бита: 1 = 1, 0 < 1. На втором же разряде вопрос решён: 1620 > 1289.

Двоичное представление неотрицательных целых bit‑comparable: лексикографическое сравнение битов от старшего к младшему даёт тот же порядок, что и численное сравнение.

Однако в индексе нужно сравнить не два числа, а порог с серией значений. Здесь ранний выход невозможен: у разных значений «решающий разряд» (тот, где они впервые отличаются от порога) расположен в разных позициях. Чтобы получить корректный ответ для всех значений, нужно дочитать все разряды полностью.

Раз сравнение значения с порогом — это поразрядная процедура, её можно собрать из побитовых операций. Направление обхода тоже изменится: для пары чисел старший разряд расхождения сразу даёт ответ, поэтому шли сверху. В индексе же ответ — это битовая маска rid'ов, удовлетворяющих ≤ T, и строим её снизу вверх: на каждом шаге очередной разряд порога либо подтверждает уже накопленный по младшим разрядам ответ, либо ужесточает его, а равенство в старших разрядах решается в самом конце.

Для работы алгоритму потребуется промежуточная битовая маска — state. После обработки разрядов 0..k бит в state для rid'а означает «по младшим разрядам значение этого rid'а уже ≤ T или пока неотличимо от T, окончательный вердикт зависит от старших разрядов». После прохода по всем разрядам state будет представлять собой ответ. state инициализируется единицами во всех возможных rid.

Идём по разрядам порога от младшего к старшему. Пусть в разряде k у порога стоит T_k, у значения — x_k. Разберём оба случая.

T_k = 1. Подходят оба x_k. При x_k = 0 значение в разряде k уже строго меньше порога — rid обязан попасть в state. При x_k = 1 разряд k совпал с порогом, и решение откладывается на старшие — оставляем то, что в state уже было.

Это эквивалентно: state := state OR («бит k равен 0»).

T_k = 0. При x_k = 1 значение в разряде k строго больше порога — rid должен быть удалён из state на этом шаге (если в каком‑то старшем разряде порог окажется больше значения, OR вернёт его обратно). При x_k = 0 разряд k совпал с порогом — оставляем то, что в state уже было.

Это эквивалентно: state := state AND («бит k равен 0»).

Применим range encoding не ко всему значению, а к каждому разряду отдельно: для разряда k нам нужны маски вида «цифра в разряде k ≤ d», где d это цифра разряда. В base-2 у разряда всего две возможные цифры: 0 и 1. Маска «цифра ≤ 1» тривиальна для всех строк, а потому не хранится. Маска «цифра ≤ 0» — это в точности «цифра = 0», то есть «бит k равен 0».

Таким образом range‑encoded bit‑sliced index — это n битовых масок (где n — число разрядов), и каждая из них является инверсией соответствующего бита значений, что значит «бит k равен 0». Поэтому для разряда k индекс в base-2 хранит только одну битовую маску — назовём её слайсом разряда k.

Несколько свойств видно сразу:

• Строка для Δ = 0 (rid 2) состоит из одних единиц: все биты значения равны 0, инверсия каждого даёт 1. Самое маленькое значение — самая «полная» строка.

• Строка для Δ = 1876 (rid 4, максимум) содержит больше всего нулей.

• NULL невозможен. rid — это неявный номер строки в сегменте, а не самостоятельный ключ. Отсутствие значения нечем обозначить. Иногда для этого вводят отдельную битовую маску «not‑null».

Минимум и максимум хранятся в метаданных индекса. Минимум вычитается из порога перед запросом. Максимум определяет, сколько слайсов нужно построить — больше старших разрядов держать не имеет смысла. А также попытка добавить значение больше, чем максимум приводит к ошибке: для него просто не зарезервирован слайс.

Прогон алгоритма

В описанной выше схеме мы начинаем с state = all-1 («по пустому множеству разрядов значение неотличимо от порога») и применяем OR/AND для всех разрядов подряд, включая нулевой. Но можно применить несколько оптимизаций.

Поблочная обработка. Битовая маска в RoaringBitmap уже разделена на контейнеры по 2¹⁶ позиций, поэтому алгоритм идёт блок за блоком, а буфер state существует только для текущего блока. Таким образом становится доступной одна из главных оптимизаций — сужающего контекст.

Особый случай для младшего разряда порога.

• T₀ = 0: state := all-1 AND s0 = s0. То есть результат шага — это просто копия слайса s0.

• T₀ = 1: state := all-1 OR s0 = all-1. Слайс s0 в результат не влияет вообще, поэтому его можно пропустить.

Запрос: Δ > 1000. Применим два преобразования. Первое — индекс умеет отвечать только на ≤, тогда как в запросе >, поэтому посчитаем Δ ≤ 1000 и инвертируем. Второе — из порога необходимо вычесть минимум, взятый из метаданных индекса.

Для иллюстрации работы сужающего контекста, выключим rid 0–3 (чтобы выключить блок целиком), а также 5,6 (чтобы показать, что этого недостаточно для пропуска блока). Итоговый контекст — 00001001, активны только биты 4 и 7.

Порог T = 1000 = 0b01111101000 имеет 11 слайсов. Для демонстрации каждый блок состоит всего лишь из 4 строк.

Блок 0 (rid 0–3) — пропускается. Контекст блока — 0000, пересечений быть не может.

Блок 1 (rid 4–7) — обрабатывается.

• Инициализация буфера. Младший бит порога T₀ = 0, поэтому буфер блока обнуляется в 0000. (Если бы T₀ = 1, буфер заполнился бы единицами, а слайс s0 не читался бы.)

• Слайс s0 (T₀ = 0, OR). Слайс хранит инвертированные биты значений: 1,1,0,1. После OR: 0000 | 1101 = 1101.

• Слайсы s1, s2 (T₁ = T₂ = 0, AND). Удаляют строки, у которых бит значения равен 1, то есть значение в этом разряде уже больше порога. После s1: 1101 & 1111 = 1101. После s2: 1101 & 0010 = 0000. Все четыре строки временно «выключены».

• Слайс s3 (T₃ = 1, OR). Возвращает в выборку строки, у которых бит s3 равен 0 (то есть в этом разряде значение точно меньше порога): 0000 | 1100 = 1100.

• Слайсы s4…s9 — чередование AND и OR по битам 0,1,1,1,1,1 порога. Буфер постепенно «сходится»: 1100 → 0000 → 1011 → 1011 → 1111 → 1111 → 1111.

• Слайс s10 (T₁₀ = 0, AND). Фильтрация по старшему разряду: 1111 & 0001 = 0001. Это ответ на Δ ≤ 1000 внутри блока — только rid 7 (значение 812).

• NOT блока (превращение ≤ в >): 0001 → 1110. Это rid {4, 5, 6}, значения 1876, 1620, 1289 строго больше 1000.

• AND с контекстом блока 1001: 1110 & 1001 = 1000. Остаётся только rid 4.

Итог. Битовая маска — 00001000, единственная строка rid 4 со значением 1876 > 1000. rid 7 был в контексте, но 812 не проходит порог; rid 5 и 6 проходят порог, но не входят в контекст.

Стоимость. Прочитано 11 слайсов (только блок 1) вместо 22 — экономия ровно половины работы за счёт пропуска блока 0. Чем длиннее индекс и реже контекст, тем заметнее этот эффект.

Важно также, что NOT и AND с контекстом применяются поблочно, а не один раз в конце. Это позволяет не материализовать битовую маску результата и работать с каждым блоком как с независимым контейнером Roaring Bitmap.

Раз обработка идёт блок за блоком, имеет смысл смотреть, что в этих блоках есть. Если есть внешняя «сужающая» битовая маска — например, ответ обратного индекса по pod = 'my-app-...' — её можно передать в RangeBitmap как контекст. На каждом блоке алгоритм проверяет: пересекается ли блок контекста хотя бы одним битом со слайсом. Если нет — блок целиком пропускается, никаких операций не выполняется.

Когда мы строили три отдельные битовые маски (обратный индекс, range‑индекс по created_at, range‑индекс по last_point) и потом пересекали их обычным AND, каждый из range‑индексов честно прогонял весь свой алгоритм по всем блокам. Передача ответа обратного индекса в качестве контекста меняет картину. Работа выполняется только в тех блоках, где обратный индекс что‑то нашёл. Затем то же самое для второго range‑индекса, который получает результат запроса от первого индекса как свой контекст.

Интерактив! Самостоятельно попробовать, как себя ведут разные значения порога на исходных данных можно здесь.

Бенчмарк подходов

• linear scan — для каждой метрики в отдельности проверяется пересечение с окном запроса,

• range bitmap — обращение в два индекса, сужающий контекст даёт только запрос к индексу по last_point.

Время для метрик генерируется случайно, но с одинаковым seed. Linux, Intel Xeon Gold 6338. Среднее время на вызов, в микросекундах.

Линейный скан проигрывает не просто потому, что он O(N). На «узком окне поверх длинной истории» он проигрывает из‑за промахов branch predictor.

Флеймграф на основе бенчмарков MIDDLE_DAY и ALL для linearScan.

JFR‑профиль показывает, что при запросе одного дня внутри пятилетней истории на 10M метрик ≈40% семплов застряли во фрейме бенчмарка linearScan, а не в заинлайненном теле проверки testLinear. На полном диапазоне branch predictor всегда угадывает правильно.

В случае RangeBitmap таких ветвлений нет. Однако есть свои постоянные расходы, поэтому эвристика вида «если поисковый результат вернул метрик меньше, чем 10_000, выполним линейное сканирование» имеет смысл.

Bit-sliced индекс не знает свой словарь

Из-за трансформации способа хранения (bit-slicing) индекс больше не хранит словарь — у него нет «таблицы уникальных Δ» вроде той, которая была у equality-encoding. Внутри только слайсы разрядов. На вопрос «какие ключи вообще встречаются» индекс ответить не может. Если нужен «список последних 100 созданных метрик», то API для его получения просто не существует.

Однако проиндексированные минимум и максимум доступны в метаданных. Используя их, можно идти шагами от максимума вниз: сначала запросить диапазон [max − step, max], получить rid, добавить в ответ. Если набралось меньше лимита — следующий диапазон [max − 2·step, max − step], и так далее. На каждом шаге внутри диапазона порядок rid произвольный, но между шагами — отсортирован по убыванию Δ. Если шаг подобран так, что в нём ожидаются десятки rid, лимит набирается за несколько range-запросов.

Именно так и работает страница «последние созданные метрики» в нашем UI: range‑запрос по created_at_seconds идёт чанками вниз от максимальной индексированной даты создания метрики.

Возможное расширение подхода на другие системы

Посмотрим на трейсинг, где каждый спан описывает один шаг запроса. На дежурстве прилетает алерт: p99 основной ручки вырос до сотен миллисекунд, хотя в норме занимает десятки. Чтобы найти проблемные спаны, нужен запрос вида:

SELECT traceId, spanId, operationName
FROM spans
WHERE duration > 250ms
  AND timestamp BETWEEN '02:00' AND '03:00'

Найти спаны нужного часа относительно просто — данные в таких системах обычно уже нарезаны на сегменты по времени. Однако, внутри сегмента данные физически отсортированы по traceId: трейс — это коллекция спанов, и для просмотра трейса целиком читать их хочется подряд. Колокация по traceId обеспечивает быстрое чтение всего трейса по идентификатору — это основной паттерн доступа.

RangeBitmap может стать естественным ответом для такой задачи. Range‑запрос duration > 250ms возвращает битовую маску rid в физическом порядке сегмента — то есть сохраняет колокацию по traceId. Фильтры по service и error строятся как обратные индексы, и финальный ответ — это AND трёх масок. Дешёвая операция, на выходе rid отсортированы так же, как лежат данные.

Выводы

Использование RangeBitmap позволило нам с минимальными изменениями адаптировать Monium Metrics к высокой частоте изменения метаданных Kubernetes. При этом решение не является серебряной пулей, и требует от системы дополнительной подготовки:

• расходы на перестроение RangeBitmap должны быть амортизированы. Мы это делаем с помощью LSM‑подобных структур;

• получать данные для этого перестроения может быть не бесплатно, поэтому нужно уметь батчевать их загрузку и модифицировать запросы к RangeBitmap, пока батч обрабатывается. Мы искусственно расширяем диапазон запроса, чтобы не нужно было перестраивать индекс слишком часто;

• хотя RangeBitmap и справляется лучше линейного сканирования, он не сможет победить бинарный поиск, если данные возможно отсортировать

• в случае необходимости обработки небольшого количества данных; накладные расходы на RangeBitmap могут быть больше, чем на линейное сканирование.

Сочетание этих подходов и возможность использовать обратный индекс в качестве сужающего контекста позволяет нам выдерживать 650–850 тысяч запросов в секунду к метаданным, каждый из которых несёт в себе информацию о временном диапазоне

Ссылки

• Chan, C. Y., & Ioannidis, Y. E. (1998). Bitmap index design and evaluation. SIGMOD. pdf

• Startin, R. (2022). RangeBitmap: How range indexes work in Apache Pinot. richardstartin.github.io

• Apache Pinot Range Index Design Doc. doc

• RoaringBitmap library

• Engineering Fast Indexes for Big Data Applications: Spark Summit East talk by Daniel Lemire, p1

• Engineering Fast Indexes for Big Data Applications: Spark Summit East talk by Daniel Lemire, p2

• Bitmap indexes. Marko Kevac, Badoo