Roaring Bitmap: как уместить базу данных в памяти приложения / Хабр

О чем статья
Решаемая бизнес задача
Неожиданные сложности бизнес задачи
Давайте просто посмотрим на данные
Устройство классических битовых массивов
Как решить проблему «распухания» классических битовых массивов
Устройство Roaring Bitmap
Какого результата удалось добиться
Заключение

О чем статья

Привет, Хабр! Меня зовут Глеб Типсин, я являюсь ведущим разработчиком продукта «Кластер Гейты» в SM Lab. Мы развиваем IT‑системы для цифровых сервисов Спортмастера и других бизнесов.

Глеб Типсин

Ведущий разработчик продукта «Кластер Гейты» в SM LAB

Эта статья достаточно объемная, поэтому попробую либо сразу вас заинтересовать, либо вовремя отпугнуть от прочтения.

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

О чем пойдет речь:

Решаемая задача. Для начала мы затронем саму бизнес‑задачу, с которой столкнулась наша команда, и остановимся на ключевых нюансах процесса.
Трудности решения в лоб. Постараюсь объяснить, почему эта на первый взгляд тривиальная задача оказалась крепким орешком, и с какими трудностями можно столкнуться при использовании типовых решений.
Взгляд под другим углом. Перевернём условия игры. Вы увидите, как в погоне за быстрым поиском и минимальной полезной нагрузкой сама природа данных может подтолкнуть к переизобретению битового массива.
«La classique» битовые массивы. Разберем устройство классических битовых массивов на основе слов фиксированной длины, их сильные и слабые стороны, а также поймем, почему они не стали панацеей.
Главный герой — Roaring Bitmap. Разберем ключевую идею этой структуры данных, заглянем к ней под капот и изучим её возможности.
Финал и результаты. В завершение я поделюсь, как мы применили Roaring Bitmap для решения нашей задачи и каких отличных результатов в итоге удалось достичь.

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

Решаемая бизнес задача

СТИ — информационная система, единственная задача которой — проверка доступности товаров при массовых маркетинговых рассылках и рекомендациях на сайте:

Системы потребители оперируют следующими товарными сущностями:

Цветомодель (ЦМ) — товар определенного цвета. Например, коричневые кроксы;
Цветоразамер (ЦР) — это товар определенного цвета и размера. Например, коричневые кроксы 42-го размера.
Артикул — товар определенного цвета, размера, коллекции и других значимых атрибутов. Например, коричневые кроксы 42-го размера коллекции SS26.

Все эти товарные сущности связаны между собой:

Цветомодель является родителем для цветоразмеров и может включать в себя несколько таких сущностей. А цветоразмер, в свою очередь, является родителем для артикулов. Один цветоразмер может включать в себя несколько артикулов.

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

И последний важный нюанс — тип товарной доступности. Система должна поддерживать три типа товарной доступности:

Разобрав разрозненные нюансы бизнес процесса, соберем весь пазл воедино. Товарная доступность «лежит» в разрезе:

геозона;
артикул;
тип доступности.

Рассмотрим пример проверки доступности для 4-х артикулов:

Необходимо проверить доступность каждого артикула по всем геозонам и типам доступности:

Товар доступен, если он доступен хотя бы по одной геозоне и типу доступности:

А системы потребители запрашивают данные в разрезе:

геозон;
цветомоделей или цветоразмеров.

В случае проверки цветомоделей или цветоразмеров — ЦМ или ЦР доступны, если доступен хотя бы один артикул. Т.е. необходимо найти все артикулы по ЦМ или ЦР, а далее проверять доступность каждого артикула.

Неожиданные сложности бизнес задачи

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

На первый взгляд, всё выглядит неплохо. Но главная сложность скрывается в объёме данных, которые нужно обработать в рамках одного запроса. Нам необходимо проверить каждый товар по 3 типам доступности в 15 геозонах. Таким образом, для одного запроса требуется проверить 4500 ключей:

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

При нагрузке в 6000 запросов в секунду мы получаем своего рода highload на «минималках». При таком RPS для стабильной работы системы каждый отдельный запрос, как правило, должен быть достаточно лёгким — то есть нагрузка на БД должна быть ближе к классическому OLTP‑сценарию. Однако из‑за немалого объёма проверяемых данных запросы получаются достаточно «тяжёлыми» для этой концепции. И вот тут мы сталкиваемся с дилеммой: как проверить массив данных за очень короткое время и при этом сделать так, чтобы один запрос не потреблял слишком много ресурсов БД?

Мы проводили ряд экспериментов на Oracle Exadata и получили следующие результаты:

Одиночный SQL‑запрос с ключами (tuple) в предикате in выполняется очень долго. Нагрузочное тестирование провалилось на сотнях RPS.
Одиночный SQL‑запрос с передачей ключей в json_table вместо большого предиката inи последующим join с таблицами дал ускорение в несколько раз. Данный подход дал практически 2000 RPS и время ответа по 99-му перцентилю в диапазоне 250–300 мс. Однако есть единичные запросы, которые отвалились по timeout.

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

Мы сделали вывод, что одним из немногих оставшихся вариантов оптимизации является дробление одного SQL‑запроса на несколько «маленьких» параллельных запросов к БД и объединение результатов в памяти приложения. Но такой подход увеличит количество обращений к БД в несколько раз.

Дополнительная проблема в том, что запросы получаются «размашистыми» и могут создавать дополнительное давление на буферный кэш, из‑за чего часть запросов в итоге может отваливаться по timeout. В идеале в таком сценарии достаточно большой буферный кэш мог бы существенно помочь, вплоть до размера, сопоставимого с объёмом рабочих данных.

Исследование этой проблемы требует глубокого анализа с экспериментами и бенчмарками. Поэтому пока я остановлюсь на достигнутом — подробный разбор причин и внутренней механики выходит за рамки этой статьи.

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

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

Давайте просто посмотрим на данные

В реальных системах товаров может быть миллионы, но для примера рассмотрим 4 товара с последовательными идентификаторами 1, 2, 3 и 4. В качестве типа данных выберем 64-битные числа:

Какие структуры данных мы можем использовать для хранения и поиска доступных товаров? Начнем с самого очевидного подхода и будем хранить идентификаторы в обычном массиве:

Обычный массив для хранения доступности товаров

Для хранения четырех доступных товаров потребуется массив из 4 чисел, которые будут составлять 32 байта полезной нагрузки. Поиск товара потребует перебора всех элементов, то есть займет по времени.

Идентификаторы можно хранить в отсортированном массиве или множестве, тогда поиск удастся ускорить до по времени:

Множество для хранения доступности товаров

А что, если не хранить идентификаторы товаров в явном виде, а записывать лишь признак того, что товар доступен? В таком случае достаточно бинарного признака — 1 или 0, true или false. Сам идентификатор товара можно «зашить» в индексы массива, а в качестве бинарного признака выбрать 8-битные числа:

Массив признаков доступности товаров (идентификатор товара зашит в конкретный индекс массива)

В таком варианте поиск элемента сводится к обращению по индексу за константное время . Для четырех товаров потребуется массив из пяти 8-битных чисел, где элемент с индексом 0 останется нулевым.

Можно пойти еще дальше и рассмотреть полученный массив нулей и единиц как двоичное представление. Таким образом, признаки доступности товаров можно «зашить» прямо в биты одного целого числа:

Массив признаков доступности товаров (идентификатор товара зашит в конкретный бит числа)

Итого для четырех товаров потребуется массив из одного 8-битного числа, а доступ к информации сводится к побитовым операциям, выполняемым за константное время . Одного байта достаточно, чтобы хранить информацию о наличии до восьми товаров — а в нашем примере и вовсе только о четырёх.

Сравнение всех рассмотренных вариантов:

№	Вариант	Тип данных	Временная сложность поиска	Полезная нагрузка
1	Массив с идентификаторами товаров	64-битные числа		32 байт
2	Множество с идентификаторами товаров	64-битные числа		32 байт
3	Массив признаков доступности товаров (идентификатор товара зашит в конкретный индекс массива)	8-битные числа		5 байт
4	Массив признаков доступности товаров (идентификатор товара зашит в конкретный бит числа)	8-битные числа		1 байт

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

Устройство классических битовых массивов

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

В памяти компьютера биты не хранятся по одному: они упаковываются в слова фиксированной длины. Процессоры общего назначения обычно оперируют словами длиной 32 или 64 бита. На практике битовые массивы реализуются как массивы целых чисел — чаще всего 64-битных:

Концептуальный алгоритм установки бита в классическом битовом массиве с размером слова в 64-бит выглядит следующим образом:

Алгоритм установки бита в битовом массиве

Определение индекса слова , в котором хранится искомый бит : $wordIndex = \frac{bitNumber}{64}$ ;
Проверка существование слова в массиве ;
1. Если слово существует, то переход к пункту 3;
2. Если слова не существует, то расширение массива до нулями;
Определение индекса бита в искомом слове $bitIndex = bitNumber\ \%\ 64$ ;
Установка бита в позиции : $words[wordIndex] = words[wordIndex]\ ||\ (1 << bitIndex)$ .

Таким образом, выставляется нужный бит, не затрагивая все остальные.

Для демонстрации алгоритма установки битов обратимся к ранее рассмотренному примеру с товарами, но теперь идентификаторы приблизим к реальности (но все равно оставим красивыми):

Пример товаров для демонстрации работы классического битового массива

Установим бит для первого товара «Кроксы» с идентификатором 1:

Пример установки товара "Кроксы" в классическом битовом массиве — Пример установки товара «Кроксы» в классическом битовом массиве

После установки бита для товара «Кроксы» — массив из одного слова 2:

Результат установки одного товара в классическом битовом массиве

Теперь перейдем к следующему товару «Кроссовки» с идентификатором 10 и установим его в битовом массиве:

Пример установки товара "Кроссовки" в классическом битовом массиве — Пример установки товара «Кроссовки» в классическом битовом массиве

После установки бита для товара «Кроссовки» с идентификатором 10 — массив из одного слова 1026:

Результат установки 2-х товаров в классическом битовом массиве

Перейдем к следующему товару «Кепка» с идентификатором 100 и установим его в битовом массиве:

Пример установки товара "Кепка" в классическом битовом массиве — Пример установки товара «Кепка» в классическом битовом массиве

После установки бита для товара «Кепка» с идентификатором 100 размер массива увеличился до двух слов, в котором установлено три товара:

Результат установки 3-х товаров в классическом битовом массиве

Теперь перейдем к последнему товару «Носки» с идентификатором 1000 и установим его в битовом массиве:

Пример установки товара "Носки" в классическом битовом массиве — Пример установки товара «Носки» в классическом битовом массиве

После установки всех товаров в битовом массиве получена следующая картина:

Результат установки 4-х товаров в классическом битовом массиве

Последняя установка бита для товара «Носки» привела к сильному расширению битового массива — с двух слов до 16. Для хранения информации о доступности четырех товаров потребовалось 16 слов, причем 13 слов равны 0.

Другими словами, требуется 1024 бита (64 бита × 16 слов), что выглядит весьма расточительно для четырех товаров.

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

Ранее рассматривался пример, в котором идентификаторы товаров располагались плотно друг за другом (1, 2, 3, 4). В этом случае всю необходимую информацию можно было уместить в одном 64-битном слове:

Сравнение размеров битовых массивов для разреженных и плотных данных

В случае разреженных данных всю необходимую информацию выгоднее хранить в явном виде, например в массиве или множестве:

Сравнение размеров структур данных для разреженных данных

Используя массив или множество для хранения самих идентификаторов, логический объём хранения удалось сократить с 1024 бит до 256 бит — то есть в 4 раза.

Иными словами, традиционные битовые массивы эффективны для плотных множеств и неэффективны для разреженных.

Как решить проблему «распухания» классических битовых массивов

Самое простое и очевидное решение — выполнить искусственное уплотнение данных. Возьмем предыдущий пример с идентификаторами товаров и нормализуем их:

После нормализации данных получим следующий результат:

Битовый массив уменьшился в 16 раз — с 16 слов до 1. При этом необходимо хранить маппинг нормализации, который будет занимать минимум 512 бит в памяти. С учетом размера маппинга данные все равно выгодно хранить в явном виде (массивы/множества).

Однако такой трюк может дать хорошие результаты, когда необходимо хранить много битовых массивов с одним глобальным маппингом.

Устройство Roaring Bitmap

Ключевая идея

Говоря про Roaring Bitmap нельзя не упомянуть одного из автора этой структуры данных — Daniel Lemire.

Daniel Lemire

Профессор компьютерных наук в университете Université du Québec (TÉLUQ)

Согласно Stanford Elsevier ranking 2025 года Daniel Lemire входит в топ-2% самых цитируемых учёных мира, а на GitHub — в топ-1000 самых популярных разработчиков. Является соавтором научных работ, которые впоследствии превращались в open‑source инженерные решения, двигающие IT‑индустрию вперед. Одни из самых известных его работ:

simdjson — библиотека для парсинга JSON со скоростью несколько гигабайт в секунду;
simdutf — библиотека для работы с Unicode и Base64 со скоростью несколько миллиардов символов в секунду;
ada — библиотека для парсинга url адресов со скоростью несколько миллионов в секунду;
внес значительный вклад в область сжатия битовых массивов — от различных RLE подходов до Roaring Bitmap.

Roaring Bitmap — структура данных, которая стремится в себе сочетать высокую скорость выполнения операций и минимальное потребление памяти как у классических битовых массивов в идеальных условиях. Другими словами, это быстрая и компактная структура данных, предоставляющая интерфейс обычного битового массива.

Основная идея — разбиение множества беззнаковых 32-битных чисел на непересекающиеся подмножества фиксированной длины $2^{16}$ .

Все элементы в рамках каждого подмножества имеют одинаковые 16 старших бит:

№	Старшие 16 бит	Начало диапазона	Конец диапазона
1	0000 0000 0000 0000	0	65 535
2	0000 0000 0000 0001	65 536	131 071
3	0000 0000 0000 0010	131 072	196 608
..	..	..	..
65 536	1111 1111 1111 1111	4 294 901 760	4 294 967 295

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

Иными словами, исходное 32-битное число разбивается на две части:

16 старших бит, которые определяют, в какой контейнер будет помещено число. Другими словами, это ключ;
16 младших бит, которые и являются полезной нагрузкой внутри контейнера.

Для лучшего понимания, снова обратимся к примеру с товарами. Для товара «Кроксы», который имеет идентификатор 1, получаем следующее:

16 старших бит — 0×0000 или 0. Будет выбран контейнер, который хранит все элементы, у которых 16 старших бит равно 0;
16 младших бит — 0×0001 или 1. Непосредственно данное число и будет храниться в контейнере.

Ключевая идея Roaring Bitmap на примере (кроксы)

Для товара «Кроссовки», который имеет идентификатор 100_000 картина немного иная:

16 старших бит — 0×0001 или 1. Будет выбран контейнер, который хранит все элементы, у которых 16 старших бит равно 1;
16 младших бит — 0×1000_0110_1010_0000 или 34 464 в десятичном представлении. Непосредственно данное число и будет храниться в контейнере.

Ключевая идея Roaring Bitmap на примере (кроссовки)

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

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

Array container — это отсортированный динамический массив беззнаковых 16-битных чисел, используемый для хранения потенциально разреженных множеств. Максимальная вместимость такого контейнера составляет 4096 элементов. При этом максимальный объём памяти, занимаемый данными, равен 65 536 битам (4096 × 16) или 8 КБ. Поскольку элементы в массиве хранятся в отсортированном виде, для проверки наличия значения используется бинарный поиск.

Bitmap container — это классический битовый массив, реализованный на основе 64-битных машинных слов. Для покрытия полного диапазона из $2^{16}$ возможных значений используется 1024 слова по 64 бита каждое. Таким образом, данный тип контейнера занимает фиксированный объём памяти — 65 536 бит (1024 слов × 64 бит) или 8 КБ. Поскольку контейнер представляет собой обычный битовый массив, операции проверки наличия элемента и модификации множества сводятся к простым битовым операциям, что обеспечивает очень быстрый доступ к данным.

Run container — это массив упакованных пар беззнаковых 16-битных чисел. Каждая пара описывает непрерывную последовательность значений: первый элемент задаёт начальное значение диапазона, а второй — длину последовательности. Таким образом, данный тип контейнера использует подход RLE (Run‑Length Encoding):

В рамках данной статьи Run container далее рассматриваться не будет, поскольку он не используется Roaring Bitmap по умолчанию.

Таким образом, Roaring Bitmap использует два основных типа контейнера: Array container для хранения разреженных множеств и Bitmap container для хранения плотных множеств. Порог в 4096 элементов гарантирует, что на уровне контейнеров на каждое целое число расходуется не более 16 бит:

в Array Container используется ровно 16 бит на число;
в Bitmap Container используется менее 16 бит на число.

Когда размер Array Container становится более 4096 элементов, то он автоматически конвертируется в Bitmap Container фиксированного размера. И наоборот — когда кардинальность Bitmap Container становится 4096, то он конвертируется обратно в Array Container.

Ни один контейнер Roaring Bitmap не превышает 8 КБ по объёму данных. Благодаря этому несколько контейнеров могут одновременно помещаться в L1-кэш большинства современных процессоров, что положительно сказывается на производительности.

Теперь Roaring Bitmap можно представить следующим образом:

Абстрактное представление структуры данных Roaring Bitmap

На первом плане два массива:

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

Доступ к данным всегда начинается с массива ключей: по ним определяется индекс, с помощью которого затем извлекается соответствующий контейнер. Простыми словами, эта пара массивов представляет собой концепцию «ключ‑значение».

Контейнеры, в свою очередь, имеют тип, который определяет способ хранения и алгоритм поиска. Независимо от типа контейнера, для хранения и поиска будут использоваться 16 младших бит исходного числа или $x\ mod\ 2^{16}$ , где — исходное число:

в Array container производится бинарный поиск $x\ mod\ 2^{16}$ ;
в Bitmap container производится поиск значения бита в позиции $x\ mod\ 2^{16}$ .

Алгоритм поиска элемента в Roaring Bitmap

Возвращаясь к примеру с товарами, заполненный Roaring Bitmap будет выглядеть следующим образом:

Пример заполненного Roaring Bitmap двумя товарами

А поиск товара «Кроссовки» с идентификатором 100_000 будет схематично выглядеть так:

Пример поиска кроссовок в Roaring Bitmap

Конвертация контейнеров

Каждый контейнер Roaring Bitmap отслеживают свою кардинальность, и при достижении порога автоматически преобразуется из одного типа в другой. Когда размер Array Container становится более 4096 элементов, то он автоматически конвертируется в Bitmap Container. И наоборот — когда кардинальность Bitmap Container опускается до 4096, то он конвертируется обратно в Array Container.

Алгоритм конвертации Array container в Bitmap container тривиален — необходимо выполнить итерацию по всем элементам массива с установкой битов в позициях, соответствующих значениям самих элементов.

В качестве примера преобразуем Array Container, состоящий из двух элементов, в Bitmap Container:

Конвертация Array container в Bitmap container

Алгоритм конвертации Bitmap Container в Array Container немного сложнее. Для этого выполняется итерация по всем словам битового массива: пока слово не равно нулю, определяются индексы установленных битов с учетом индекса рассматриваемого слова. Индекс каждого установленного бита интерпретируется как искомое значение и добавляется в результирующий массив. После обработки бит сбрасывается. После обработки всех установленных битов слово становится равным нулю. Таким образом, обрабатываются все слова битового массива.

Снова обратимся к примеру — конвертируем Bitmap Container, состоящий из одного слова, в Array Container:

Конвертация Bitmap container в Array container

Логические операции

В Roaring Bitmap реализованы базовые логические операции — объединение (bitwise OR) и пересечение (bitwise AND):

Как видно на схеме с кругами Эйлера, операции могут влиять на размер результирующего множества:

операция пересечения может сужать множество возможных результатов;
операция объединения может расширять множество возможных результатов.

Таким образом, размер результирующего множества может влиять на тип контейнера, куда этот результат будет записан. В Roaring Bitmap размеры множеств‑контейнеров следующие:

Кардинальность контейнеров в Roaring Bitmap

И всего возможно три случая логических операций между контейнерами:

Учитывая свойства AND/OR и кардинальность множеств‑контейнеров, можно точно определить тип результирующего контейнера в некоторых случаях:

Bitmap Container OR Bitmap Container — результат всегда Bitmap Container;
Bitmap Container OR Array Container — результат всегда Bitmap Container;
Bitmap Container AND Array Container — результат всегда Array Container;
Array Container AND Array Container — результат всегда Array Container.

Bitmap container vs Bitmap container

Для случая Bitmap container AND Bitmap container сперва необходимо определить тип результирующего контейнера: для это необходимо проитерироваться по всем 1024 словам, применить AND к каждой паре слов и рассчитать кардинальность каждого промежуточного результата. В процессе суммируются кардинальности всех полученных слов и получается финальная мощность :

если $C \leq 4096$ , то необходимо проитерироваться по всем 1024 словам, выполнить логическое AND между парой слов — индексы установленных битов промежуточного слова записать в результирующий Array container (см. алгоритм конвертации Bitmap container в Array container);
если $С \gt 4096$ , то необходимо проитерироваться по всем 1024 словам, выполнить логическое AND между парой слов и записать результат в Bitmap container.

Кардинальность слова можно вычислить мгновенно: инструкция POPCNT выполняет это за один такт.

Для случая Bitmap container OR Bitmap container необходимо выполнить итерацию по всем 1024 словам битовых массивов, применяя логическое OR к паре слов и суммируя кардинальность каждого полученного слова. Все промежуточные слова записываются в новый Bitmap container.

Bitmap container vs Array container

Операция Bitmap container AND Array container всегда возвращает Array container. Необходимо проитерироваться по всем элементом Array container и проверить существование каждого элемента в Bitmap container. Если элемент существует, то он добавляется в результирующий Array container.

Операция Bitmap container OR Array container всегда возвращает Bitmap container. Для этого создается копия исходного Bitmap container, после чего выполняется итерация по всем элементам Array container с установкой соответствующих битов в копии битового массива.

Array container vs Array container

Операция Array container AND Array container всегда возвращает Array container. Вначале сравниваются размеры двух контейнеров — если размер большего контейнера превышает меньший более чем в 64 раза, то применяется алгоритм galloping intersection, который использует экспоненциальный поиск для минимизации количества сравнений. Иначе применяется классический алгоритм слияния двух отсортированных массивов.

Операция Array container AND Array container состоит из нескольких этапов. Вначале вычисляется приближенная верхняя граница результирующей кардинальности путем простого суммирования кардинальностей двух контейнеров:

Если $C \leq 4096$ , то слияние двух отсортированных массивов в Array container;
Если $C \gt 4096$ , то необходимо честно рассчитать результирующую кардинальность — создается Bitmap container, в котором устанавливаются биты, соответствующие элементам обоих Array container:
- Если $С_1 \leq 4096$ , то конвертация полученного Bitmap container в Array container;
- Если $С_1 \gt 4096$ , то результат уже полученный Bitmap container.

А что насчет 64-битных чисел?

Одна из последних реализаций построена вокруг следующей идеи:

Ключевая идея Roaring Bitmap для 64-битных чисел

В отличие от 32-битной версии длина ключа стала в несколько раз больше — 48 старших бит исходного элемента. Это позволяет переиспользовать контейнеры из 32-битной версии для хранения оставшихся 16 младших бит.

Если в 32-битной версии для хранения ключей и контейнеров используются два массива, то 64-битная реализация базируется на структуре данных ART (Adaptive Radix Tree).

Где используется

Многие известные проекты выбирают Roaring Bitmap в качестве сжатых битовых массивов:

С точки зрения разработки есть нативные реализации, например для Java и GO, или обертки вокруг библиотеки на C, например для Python. Помимо библиотеки для популярных языков программирования Roaring Bitmap можно встретить в виде модуля для Redis или расширения для PostgreSQL.

Альтернативы Roaring Bitmap

Все известные на сегодняшний день альтернативы Roaring Bitmap строятся вокруг базовой идеи RLE и являются продолжением подхода Oracle BBC (Byte‑aligned Bitmap Compression). К наиболее известным форматам относятся:

WAH (Word‑Aligned Hybrid);
Concise (Compressed “n” Composable Integer Set);
EWAH (Enhanced Word‑Aligned Hybrid).

Интересный факт: Daniel Lemire является соавтором формата EWAH.

Какого результата удалось добиться

СТИ состоит из двух модулей:

ETL (Extract Transform Load) — модуль, который получает и обновляет товарную доступность из мастер системы. Данные о товарной доступности дублируются во внутренней реляционной БД;
API — модуль, который отвечает на запросы внешних систем. Вся информация о товарной доступности хранится в памяти приложения.

Данные во внутренней реляционной БД распределены по трем таблицам в зависимости от типа товарной доступности:

Модуль ETL поддерживает актуальное состояние данных с задержкой в пять минут.

В момент рождения (деплоя/редеплоя) модуля API он подписывается на топики Kafka для чтения будущих инкрементов и полностью загружает всю товарную доступность в оперативную память:

Компонентная схема в момент рождения модуля API

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

Полная загрузка данных в оперативную память занимает примерно 5–10 минут. После этого модуль API готов принимать запросы от внешних систем и читать инкременты от модуля ETL:

Компонентная схема при номинальной работе модуля API

Данные хранятся в кастомной обертке над ConcurrentHashMap, в которой в качестве ключа используется обычный data class, состоящий из двух полей: геозона и тип доступности. Значением же служит Roaring Bitmap, хранящий доступность товаров:

Концептуальный способ хранения товарной доступности в памяти приложения

Объём сырых данных в БД составляет 44 ГБ без учёта индексов. Однако после загрузки в оперативную память приложения они сжимаются всего до 2.5 ГБ:

Ниже приведены ключевые метрики модуля API за случайно выбранный промежуток времени, в течение которого проходила массовая маркентиговая рассылка. Утилизация Heap:

Утилизация Heap в режиме номинальной работы модуля API

Суммарное количество запросов в секунду в разрезе методов:

Нагрузка в основном идет по двум методам:

api/v1/mcm;
api/v2/availability/_search‑by‑mcm.

Обозначенные методы проверяют доступность в разрезе цветомоделей, что увеличивает количество проверяемых данных. Средний RPS держится в районе 4000–4200.

Время ответа по перцентилям в разрезе методов:

Пиковое значение по 99-перцентилю составляет 5.58 миллисекунд, что с огромным запасом укладывается в нефункциональные требования (200 мс).

Утилизация CPU по 3-м репликам:

Средняя утилизация CPU во время массовой маркетинговой рассылки составляет примерно 55–60%. Эта нагрузка складывается не только из внешних запросов, но и из чтения инкрементов, объем которых может достигать миллионы измененных артикулов.

Модуль API развернут в K8s со следующими ресурсными квотами:

CPU
- requests: 2
- limits: 4
RAM
- requests: 4Gi
- limits: 8Gi

Физическое железо:

Intel Xeon Gold 6254

Ключевой технологический стек:

Spring Boot 2.7.x
- Spring WebFlux + Kotlin coroutines
- Reactor Kafka
Azul JDK 17 + Kotlin 1.7.x

Заключение

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

Однако такое решение требует жёсткого контроля за потреблением RAM и наличия «хрустального шара» — чёткого понимания того, как объём данных может измениться в будущем и как это повлияет на потребление памяти через битовые массивы.

Если статья была Вам полезна, буду рад вопросам и комментариям. Спасибо, что были со мной до конца!

Roaring Bitmap: как уместить базу данных в памяти приложения

Оглавление