Продвинутые структуры: HyperLogLog, Bitmaps, Streams Stack

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

Как посчитать миллионы уникальных посетителей, потратив 12 КБ памяти вместо гигабайтов? HyperLogLog отвечает: пожертвуй точностью ради памяти.

Redis предлагает структуры за пределами строк, списков и множеств. Они «вероятностные» или «битовые» — жертвуют точностью или универсальностью ради колоссальной экономии памяти. Плюс модули Redis Stack расширяют возможности.

HyperLogLog: подсчёт уникальных

Чтобы посчитать число уникальных элементов (уникальные посетители, уникальные IP), обычное множество хранило бы каждый элемент — это много памяти. HyperLogLog оценивает количество уникальных с погрешностью около 0.81%, занимая всего ~12 КБ независимо от объёма.

PFADD visitors "user1" "user2" "user3"
(integer) 1
PFCOUNT visitors        # приблизительная оценка уникальных
(integer) 3
PFMERGE all v1 v2       # объединить несколько HLL

Bitmaps: флаги и присутствие

Bitmap — это строка, рассматриваемая как массив битов. Идеально для компактного хранения «да/нет» по миллионам ID: заходил ли пользователь сегодня, прочитано ли уведомление.

SETBIT online:2025-06-22 42 1   # пользователь 42 был онлайн
GETBIT online:2025-06-22 42     # 1
BITCOUNT online:2025-06-22      # сколько всего было онлайн

Миллион пользователей в bitmap — это всего ~125 КБ.

   Сравнение по памяти на подсчёт уникальных

   Множество (Set):   точно, но ~N * размер_элемента
                      10 млн IP -> сотни МБ

   HyperLogLog:       ~0.81% погрешности, ~12 КБ
                      10 млн IP -> 12 КБ (!)

   Bitmap (флаги):    1 бит на ID
                      10 млн флагов -> ~1.2 МБ

Redis Stack: модули

Redis Stack (а в новых версиях — ядро Redis) добавляет мощные модули:

• RedisJSON — хранение и частичное изменение JSON-документов нативно, без сериализации всей строки.
• RediSearch — полнотекстовый поиск и вторичные индексы поверх Redis, включая векторный поиск для AI.
• RedisBloom — вероятностные структуры: Bloom-фильтр (проверка «точно нет в множестве»), Cuckoo, Count-Min Sketch, Top-K.
• RedisTimeSeries — эффективное хранение временных рядов с агрегациями.

Демонстрация: приближённый счётчик уникальных на Python

Покажем идею вероятностного подсчёта: точное множество против оценки. Принцип HLL сложнее, но суть «жертвуем точностью ради памяти» видна так:

import hashlib

# Точный подсчёт: храним все элементы (как Set) — много памяти
exact = set()

# Приближённый: храним только "максимальное число ведущих нулей хеша"
# Это упрощённая идея HyperLogLog
max_zeros = [0]

def add(item):
    exact.add(item)
    h = int(hashlib.md5(item.encode()).hexdigest(), 16)
    # считаем ведущие нули в бинарном представлении
    binary = bin(h)[2:].zfill(128)
    zeros = len(binary) - len(binary.lstrip('0'))
    max_zeros[0] = max(max_zeros[0], zeros)

# Добавляем 1000 уникальных и 1000 дубликатов
for i in range(1000):
    add(f"user-{i}")
for i in range(1000):
    add(f"user-{i}")   # дубликаты не меняют оценку уникальных

estimate = 2 ** max_zeros[0]   # грубая оценка по идее HLL
print("Точное число уникальных (Set):", len(exact))
print("Приближённая оценка (идея HLL):", estimate)
print(f"Память Set: хранит {len(exact)} элементов")
print("Память HLL: фиксированная (~12 КБ), не зависит от числа элементов")
print("\nРеальный HyperLogLog даёт ~0.81% погрешности, а не такую грубую.")

Точное множество растёт с числом элементов, а вероятностная оценка занимает фиксированную память. В этом весь смысл HyperLogLog для гигантских объёмов.

Как работает под капотом

HyperLogLog основан на наблюдении: в случайных хешах вероятность встретить хеш с N ведущими нулями связана с числом уникальных элементов. Усредняя такие наблюдения по множеству «регистров», HLL оценивает кардинальность с фиксированной памятью. Bitmap — это просто строка, где команды SETBIT/BITCOUNT работают на уровне отдельных битов. Bloom-фильтр из RedisBloom использует несколько хеш-функций и битовый массив, давая «точно нет» или «возможно есть».

Частые ошибки

• Ждать точности от HyperLogLog. Это оценка с погрешностью; для точного счёта нужен Set.
• Bitmap по разреженным ID. Если ID огромные и редкие, bitmap раздуется; тогда лучше Set или HLL.
• Считать модули доступными везде. RedisJSON/Search есть в Redis Stack/новом ядре, но не в любой старой сборке.

Best practices

• Для подсчёта уникальных при огромных объёмах — HyperLogLog (память фиксирована).
• Для миллионов булевых флагов — Bitmaps (1 бит на флаг).
• Для документов, поиска и вероятностных проверок — модули Redis Stack.

Итог: HyperLogLog считает уникальные за ~12 КБ ценой 0.81% погрешности. Bitmaps хранят миллионы флагов в килобайтах. Модули Redis Stack (JSON, Search, Bloom, TimeSeries) расширяют Redis до документной БД, поисковика и хранилища временных рядов.