bitmap-and-bitfield

Bitmap и Bitfield

Предпосылки: String, побитовые операции.

← HyperLogLog | Sub →

Отслеживание миллионов бинарных состояний

DAU-счётчик (DAU — daily active users, количество уникальных пользователей за день). 10 миллионов пользователей, нужно знать: сколько были активны сегодня? SET хранит каждый user_id как строку — при 10 миллионах это сотни мегабайт. Bitmap представляет те же данные как массив бит: один пользователь — один бит. 10 000 000 бит = 1.25 МБ. Экономия памяти впечатляет, но настоящий выигрыш — не в хранении. Побитовые операции позволяют вычислять retention, churn и когорты за миллисекунды, без загрузки данных на клиент.

Один бит на пользователя

Bitmap в Redis — не отдельный тип данных, а способ работать с отдельными битами внутри STRING. Строка — последовательность байт, команды SETBIT/GETBIT обращаются к конкретному биту по позиции (offset). Redis автоматически расширяет строку, если offset выходит за текущий размер:

SETBIT daily:2025-01-15 1234 1      -- пользователь 1234 был активен
SETBIT daily:2025-01-15 5678 1      -- пользователь 5678 был активен
GETBIT daily:2025-01-15 1234        -- → 1
GETBIT daily:2025-01-15 9999        -- → 0 (не был)
 
BITCOUNT daily:2025-01-15           -- количество установленных бит = DAU за этот день

Один bitmap отвечает на вопрос «был ли user X активен сегодня?». Но бизнес-вопросы охватывают несколько дней: кто вернулся завтра? Какой охват за неделю? Сколько ушло?

Операции между bitmap’ами

BITOP применяет побитовые операции к нескольким bitmap’ам на стороне сервера:

-- retention: кто был активен и 15-го, и 16-го января
BITOP AND active:both daily:2025-01-15 daily:2025-01-16
BITCOUNT active:both
 
-- охват: кто был активен хотя бы в один из дней
BITOP OR active:any daily:2025-01-15 daily:2025-01-16
BITCOUNT active:any
 
-- churn: кто был 15-го, но не 16-го
BITOP NOT active:not:16 daily:2025-01-16
BITOP AND active:churn daily:2025-01-15 active:not:16
BITCOUNT active:churn

Конкретный пример: 15 января DAU = 5 000 000, 16 января DAU = 4 800 000. BITOP AND между этими днями даёт 3 900 000 — это retained users. Разница 5 000 000 − 3 900 000 = 1 100 000 — это churn за один день. Вся операция выполняется за миллисекунды — Redis обрабатывает bitmap побайтово, используя процессорные операции AND/OR/NOT на целых словах.

BITOP выполняется за O(n), где n — длина самой длинной строки в байтах. Результат записывается в новый ключ.

BITPOS key 1 — позиция первого установленного бита (первый активный пользователь). BITPOS key 0 — первый нулевой бит. Это полезно для поиска свободных слотов: в системе с числовыми ID BITPOS free_slots 0 находит первый свободный ID за O(n) байт.

Когда bitmap расточителен

Bitmap предполагает плотные последовательные ID. Если идентификаторы — UUID или большие разреженные числа, большинство бит останутся нулевыми, а bitmap будет расходовать память на пустоту. Если из 10 миллионов возможных позиций активны только 100 000 — bitmap тратит 1.25 МБ, а SET из 100 000 элементов — порядка 6 МБ. Bitmap всё ещё выигрывает, но разрыв сократился.

Порог: если активно менее 1/8 пространства ID (менее 12.5% заполненности), bitmap тратит больше памяти в расчёте на активный элемент, чем альтернативы. Для подсчёта уникальных без точности до элемента — HyperLogLog (12 КБ независимо от кардинальности). Для точного учёта при разреженных ID — SET.

BITFIELD: упаковка чисел в биты

Не всё бинарно. Иногда нужен 8-битный уровень или 16-битный счётчик, с той же плотностью хранения. BITFIELD (Redis 3.2+) позволяет хранить и обновлять несколько целых чисел разной разрядности в одной строке, обращаясь к ним по битовому смещению.

Конкретный сценарий: онлайн-игра хранит level (u8, 0–255) и score (u16, 0–65535) для каждого игрока. Два отдельных STRING-ключа — это 140 байт overhead на игрока. BITFIELD упаковывает оба значения в 3 байта (8 + 16 бит) внутри одного ключа:

BITFIELD player:123 SET u8 0 42            -- level = 42 (биты 0–7)
BITFIELD player:123 SET u16 8 1500         -- score = 1500 (биты 8–23)
BITFIELD player:123 GET u8 0               -- → 42
BITFIELD player:123 INCRBY u16 8 100       -- score += 100 → 1600

BITFIELD поддерживает контроль переполнения через OVERFLOW:

BITFIELD player:123 OVERFLOW SAT INCRBY u8 0 300
-- SAT (saturation): при переполнении остаётся на максимуме (255 для u8)
-- WRAP (по умолчанию): 255 + 1 = 0 (циклическое переполнение)
-- FAIL: отклонить операцию при переполнении и вернуть nil

SAT полезен для счётчиков, которые не должны обнуляться (уровень персонажа). WRAP — для циклических счётчиков (угол поворота). FAIL — когда переполнение означает ошибку логики.

См. также

• DAU и retention на Bitmap в Rails — SETBIT/GETBIT, BITOP AND/OR, BITFIELD

Sources

• Redis Documentation: Bitmaps. https://redis.io/docs/data-types/bitmaps/
• Redis Documentation: Bitfields. https://redis.io/docs/data-types/bitfields/
• Redis source: src/bitops.c

---

← HyperLogLog | Sub →