Set
Предпосылки: String, хеш-таблица.
← List | Sorted Set →
Вопрос принадлежности
Проверка прав. Запрос приходит, приложение проверяет: есть ли у user:42 роль “admin”? Если роли хранятся в LIST — ответ требует полного обхода: O(n). При одном запросе это незаметно. При миллионах запросов в секунду O(n) превращается из микросекунд в миллисекунды и становится узким местом. SET отвечает на тот же вопрос за O(1) — одна операция хеширования вместо обхода.
Добавление, проверка, удаление
SADD user:42:roles "admin" "editor" "viewer" -- добавить элементы
SADD user:42:roles "admin" -- дубликат игнорируется → 0
SISMEMBER user:42:roles "admin" -- есть ли элемент? → 1
SREM user:42:roles "viewer" -- удалить элемент
SCARD user:42:roles -- количество элементов → 2SISMEMBER — O(1). SADD возвращает количество реально добавленных элементов (дубликаты не считаются). SRANDMEMBER key 2 возвращает два случайных элемента без удаления — полезно для выборки (например, случайная рекомендация). SPOP делает то же, но удаляет выбранный элемент.
Проверка одного элемента полезна, но настоящая сила множеств — сравнение групп.
Операции между множествами
Два пользователя, у каждого — список интересов. Что общего? Кого читает первый, но не второй? Кого читает хотя бы один?
SADD user:1:interests "ruby" "python" "go"
SADD user:2:interests "python" "java" "go"
SINTER user:1:interests user:2:interests -- пересечение → {"python", "go"}
SUNION user:1:interests user:2:interests -- объединение → {"ruby", "python", "go", "java"}
SDIFF user:1:interests user:2:interests -- разность → {"ruby"}Все вычисления происходят на стороне сервера — клиент получает готовый результат. У каждой операции есть вариант *STORE, сохраняющий результат в новый ключ: SINTERSTORE common user:1:interests user:2:interests. Это полезно, когда результат нужно переиспользовать или когда множества большие и повторное вычисление дорого.
Сложность SINTER — O(N × M), где N — размер наименьшего множества, M — количество множеств. Redis начинает с самого маленького множества и проверяет каждый его элемент в остальных. Общие друзья у двух пользователей с 10 000 друзей каждый: Redis обходит 10 000 элементов меньшего множества и проверяет каждый в большем за O(1). Вся операция — порядка 10 000 проверок, ответ за микросекунды. Но SUNION на тех же множествах должен обойти оба — 20 000 элементов.
Компактные кодировки: listpack и intset
При малых размерах SET Redis хранит данные компактнее, чем в полноценной хеш-таблице. Выбор кодировки зависит от содержимого.
intset используется, когда все элементы — целые числа. Вместо хеш-таблицы с отдельным выделением памяти на каждый элемент, SET хранит числа в отсортированном массиве (src/intset.c). Числа записаны в минимально достаточном формате: 16, 32 или 64 бита на элемент, выбирая размер по максимальному значению. 500 user_id в intset — порядка 4 КБ. Та же коллекция в hashtable — порядка 40 КБ: каждый элемент требует отдельного выделения памяти, указателя, заголовка аллокатора.
Поиск в intset — бинарный (O(log n)), а не O(1) как в хеш-таблице. Вставка — O(n) из-за сдвига массива. Но при малых размерах intset быстрее hashtable, потому что данные лежат в непрерывной памяти и процессор читает их из кеша, а не перескакивает по разбросанным по heap указателям.
listpack (Redis 7.2+) используется для небольших множеств со строковыми элементами — по тому же принципу, что и в Hash и Sorted Set. Элементы хранятся последовательно в одном блоке памяти без указателей. Пороги переключения: set-max-listpack-entries (по умолчанию 128) и set-max-listpack-value (по умолчанию 64 байта).
Redis автоматически переключает SET из intset или listpack в hashtable, когда содержимое или размер выходят за пороги. Обратная конвертация не происходит.
См. также
- Права доступа на SET в Rails — SISMEMBER, SUNION, SINTER, SDIFF
Sources
- Redis Documentation: Sets. https://redis.io/docs/data-types/sets/
- Redis source:
src/intset.c,src/t_set.c
← List | Sorted Set →