List

Предпосылки: String, связный список.

← Hash | Set →

Проблема polling’а

Воркер проверяет очередь каждые 100 миллисекунд. Очередь пуста 99% времени. За сутки — 864 000 бесполезных запросов: CPU тратится на отправку команды, Redis тратится на пустой ответ, сеть передаёт nil. Умножить на десять воркеров — почти 9 миллионов пустых циклов в сутки. LIST с BRPOP убирает всё это: воркер спит, пока не придёт работа.

Push и pop: очередь в двух командах

LIST — упорядоченная последовательность элементов, оптимизированная для работы с концами. Продюсер кладёт элемент с одного конца, консьюмер забирает с другого:

LPUSH queue:emails "job1"              -- вставить в начало (левый конец)
LPUSH queue:emails "job2" "job3"       -- несколько за один вызов
RPUSH queue:emails "job4"              -- вставить в конец (правый конец)
 
RPOP queue:emails                      -- забрать с правого конца → "job1"
LPOP queue:emails                      -- забрать с левого конца → "job3"

LPUSH + RPOP — классическая FIFO-очередь: элементы входят слева, выходят справа в порядке добавления. LPUSH + LPOP — стек (LIFO). Вставка и извлечение с обоих концов — O(1).

LRANGE позволяет прочитать элементы без удаления:

LRANGE queue:emails 0 -1              -- все элементы
LRANGE queue:emails 0 9               -- первые 10
LLEN queue:emails                     -- длина списка

Но если очередь пуста, RPOP возвращает nil — и воркеру приходится спрашивать снова. Отсюда проблема polling’а.

BRPOP: блокирующее ожидание

BRPOP решает проблему фундаментально. Вместо цикла «спросить → nil → подождать → спросить снова» воркер вызывает BRPOP queue 0 (таймаут 0 — ждать бесконечно). Redis регистрирует соединение в списке ожидающих. Когда другой клиент выполняет LPUSH queue item, Redis находит первого ожидающего и отдаёт ему элемент напрямую. Ни одного пустого ответа, ни одного лишнего цикла.

BRPOP queue:emails 5                  -- ждать до 5 секунд
-- если элемент появится за 5 секунд → вернуть его
-- иначе → nil

BRPOP принимает несколько ключей: BRPOP q:high q:medium q:low 0. Redis проверяет ключи слева направо. Если в момент вызова несколько списков непусты, Redis заберёт элемент из первого непустого — q:high проверяется раньше q:low. Если все списки пусты, воркер ждёт: как только в любом из них появится элемент, Redis отдаст его. Это простейшие приоритетные очереди без дополнительных структур данных.

Ограниченный рост: capped list

Очередь без ограничений рано или поздно съест всю память. Лента активности, последние N логов, история запросов — все эти сценарии требуют фиксированного размера. LPUSH + LTRIM поддерживают его:

LPUSH user:123:activity '{"action":"login","at":"2025-01-15T10:00:00Z"}'
LTRIM user:123:activity 0 99          -- оставить только последние 100

Две команды выполняются за микросекунды. Для строгой атомарности можно обернуть в EXEC или pipeline. Результат — лента активности с постоянным потреблением памяти: 101-й элемент никогда не существует.

Цена случайного доступа

O(1) на концах — сильная сторона LIST. Но доступ к середине — другая история. LINDEX n требует последовательного обхода от ближайшего конца до позиции n — это O(n). LINSERT ищет опорный элемент тем же обходом. LRANGE start stop проходит S элементов до начала диапазона, затем читает stop-start+1 элемент.

На практике это означает: LIST идеален для операций с концами (очередь, стек, лента). Если нужен доступ по произвольному рангу или score — Sorted Set даёт O(log n) на все эти операции. Если нужна уникальность элементов — Set.

Внутри: quicklist

Как Redis обеспечивает O(1) на обоих концах и при этом экономит память? Через компромисс между двусвязным списком и компактным массивом.

Quicklist (src/quicklist.c) — двусвязный список, где каждый узел содержит не один элемент, а listpack — компактный блок из нескольких элементов, записанных последовательно без указателей. Listpack внутри узла экономит память (элементы лежат рядом, процессор читает их из кеша), а связи между узлами дают O(1) вставку в голову и хвост. Размер блока в каждом узле контролируется параметром list-max-listpack-size (по умолчанию -2, что означает до 8 КБ на узел).

Голова и хвост quicklist — точки с наибольшей активностью (push, pop). Узлы в середине читаются редко, и Redis может сжать их для экономии памяти. Параметр list-compress-depth задаёт, сколько узлов с каждого конца оставить несжатыми. При значении 1 несжатыми остаются по одному узлу с каждого конца, все остальные сжимаются алгоритмом LZF (быстрый алгоритм сжатия с низким потреблением CPU). На длинных списках (тысячи элементов) это сокращает потребление памяти в разы, не влияя на производительность типичных операций с концами.

См. также

• Очередь email на LIST в Rails — LPUSH/BRPOP
• Ограниченный лог активности на LIST в Rails — LPUSH/LTRIM, capped list

Sources

• Redis Documentation: Lists. https://redis.io/docs/data-types/lists/
• Redis source: src/quicklist.c, src/quicklist.h

---

← Hash | Set →