Redis

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

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

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

Основы Redis

Redis представляет собой "хранилище структур данных", написанное на языке C. Он полностью размещается в оперативной памяти и обрабатывает запросы в одном потоке, что обеспечивает высокую скорость работы и позволяет легко описывать его поведение.

Redis часто используют как хранилище строк в форме ключ-значение (key-value store), но есть и другие структуры данных поддерживаемые Redis:

• Хеш-таблицы (Objects/Dictionaries)
• Списки (Lists)
• Множества (Sets)
• Сортированные множества (очереди с приоритетами, Sorted Sets)
• Фильтры Блума (Bloom Filters; вероятностный тест на принадлежность множеству; допускаются ложноположительные срабатывания)
• Геопространственные индексы (Geospatial Indices)
• Временные ряды (Time Series)

Кроме простых структур данных, Redis также поддерживает разные схемы взаимодействия, такие как публикация-подписка (Pub/Sub) и потоки (Streams). Эти механизмы частично заменяют более сложные архитектуры вроде Apache Kafka или сервисы Amazon Web Services SNS (Simple Notification Service)/SQS (Simple Queue Service). В основе Redis лежит модель хранения ключ-значение. Ключами являются строки, а значениями могут выступать любые типы данных, поддерживаемые Redis: бинарные данные и строки, множества, списки, хеши, отсортированные множества и прочие. Все объекты в Redis имеют уникальный ключ.

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

Команды

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

SET foo 1
GET foo     # возвращает 1
INCR foo    # возвращает 2
XADD mystream * name Sara surname OConnor # Добавление элемента в stream

Полный список команд легко освоить, если группировать их по структурам данных. Например, множества Redis поддерживают простые операции, такие как добавление элемента в множество (SADD), получение количества элементов или кардинальности (SCARD, количество элементов множества), перечисление этих элементов (SMEMBERS) и проверка существования (SISMEMBER) - ведут себя так же, как их аналоги в обычном языке программирования.

Конфигурации инфраструктуры

Redis может функционировать как одиночный узел (Single Node), в режиме высокой доступности (HA - High Availability) или как кластер (Cluster). Одиночный узел - самый простой вариант, все ключи и данные хранятся в памяти одной машины. В режиме высокой доступности есть главный узел - Main (поддерживает операции записи) и одна или несколько реплик (только операции чтения), при этом все пространство ключей хранится на Main и асинхронно пересылается на реплики. Когда Redis работает в режиме кластера, то все пространство ключей разбивается на шарды (или "хеш-слоты", где "хеш-слот" это определенная часть пространства ключей, как простой пример - ключи с номерами 201-400). Клиенты кэшируют набор "хеш-слотов", которые сопоставляют ключи определенным узлам. Таким образом, клиенты могут напрямую подключаться к узлу, содержащему запрашиваемые ими данные.

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

По сравнению с большинством баз данных, кластеры Redis удивительным образом просты (и, следовательно, имеют довольно серьезные ограничения в том, что они могут сделать). Вместо решения проблем масштабируемости за вас, Redis предоставляет набор некоторых базовых примитивов, с помощью которых вы сможете решить эти проблемы самостоятельно. К примеру, за редким исключением, Redis ожидает, что все данные для заданного запроса будут находиться на одном узле!

Способ структурирования ключей определяет то, как масштабируется Redis: структуру ключей следует подстраивать под сценарии использования.

Производительность

Redis невероятно быстр. Redis способен обрабатывать порядка 100 тысяч операций записи в секунду, а время чтения часто измеряется микросекундами (< 1 ms). Такой уровень производительности позволяет реализовать некоторые антипаттерны, недопустимые для других систем управления базами данных. Например, отправка 100 SQL-запросов для формирования списка элементов с использованием реляционной базы данных - плохая идея, лучше составить единый SQL-запрос, возвращающий все необходимые данные. С Redis же, накладные расходы на выполнение аналогичной операции относительно невелики - хотя было бы идеально избежать ее вовсе, такая операция вполне выполнима.

Возможности

Рассмотрим сценарии, для решения которых можно использовать Redis.

Redis как кэш

Наиболее распространенный сценарий развертывания Redis - использование его в качестве кэша. В таком сценарии корневые ключи и значения Redis соответствуют ключам и значениям нашего кэша. Redis легко распределяет эту хеш-карту по всем узлам нашего кластера, позволяя нам масштабироваться практически без усилий - если нам потребуется больше емкости, мы просто добавляем узлы в кластер.

Например, вы можете кэшировать продукт под ключом product:123, значение которого хранится либо как JSON, либо как Redis Hash, содержащий поля вроде name, price и inventoryAmount.

При использовании Redis в качестве кэша вы часто будете применять время жизни (TTL) для каждого ключа. Redis гарантирует, что значение ключа никогда не будет прочитано после истечения срока его действия, а срок действия используется для принятия решений о том, какие элементы исключить из хранилища, поддерживая размер кэша управляемым даже в тех случаях, когда вы пытаетесь закэшировать больше объектов, чем позволяет память.

Использование Redis не решает одну из наиболее важных проблем, с которыми сталкиваются системы кэширования: проблему "горячих ключей", хотя Redis неуникален в этом аспекте по сравнению с альтернативами, такими как Memcached или другими масштабируемыми базами данных типа DynamoDB.

Redis для распределенной блокировки (Distributed Lock)

Еще одно распространенное применение Redis - использование его для распределенных блокировок. Иногда в нашей системе имеются данные, целостность которых необходимо поддерживать во время обновления (например, при проектировании Ticketmaster), или же нам нужно убедиться, что одновременно операцию не выполняют сразу несколько пользователей (например, при проектировании Uber).

Очень простая распределенная блокировка с таймаутом может использовать атомарный инкремент (INCR) вместе с временем жизни (TTL). Это фактически общий счетчик. Когда мы хотим попытаться захватить блокировку, выполняем команду INCR. Если ответ равен 1 (то есть мы были первыми, кто попытался захватить блокировку, значит, она принадлежит нам!), продолжаем работу. Если ответ больше 1 (то есть кто-то другой успел раньше), ждем и пробуем снова позже. После завершения работы с блокировкой можем удалить ключ командой DEL, чтобы другие процессы могли воспользоваться блокировкой немедленно.

Более продвинутые блокировки в Redis могут использовать алгоритм Redlock совместно с фенсинг-токенами (fencing tokens), если вам требуется надежное решение.

Redis для рейтинговых таблиц (Leaderboards)

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

Допустим, в задаче поиска постов нам нужно находить посты, содержащие данное ключевое слово (например, "банки"), которые получили наибольшее количество лайков ("Сегодня банки повышают процентные ставки... @ 500 лайков").

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

ZADD banks_posts 500 "SomeId1" # Добавить пост про процентные ставки
ZADD banks_posts 1 "SomeId2" # Добавить другой пост
ZREMRANGEBYRANK banks_posts 0 -6 # Удалить все посты кроме 5 топовых

Redis для ограничения запросов (Rate Limiter)

Redis позволяет реализовывать широкий спектр алгоритмов ограничения скорости запросов. Один из распространенных алгоритмов - фиксированное окно (Fixed Window), гарантирующий, что число запросов не превышает величину N за определенный промежуток времени W.

Реализация подобного алгоритма в Redis проста. Когда приходит запрос, мы увеличиваем значение ключа нашего лимита с помощью команды INCR и проверяем полученный ответ. Если ответ больше N, ждем. Если меньше N, можем продолжить обработку. Затем применяем команду EXPIRE к нашему ключу, чтобы спустя временной интервал W значение сбрасывалось.

Если вам нужен алгоритм скользящего окна (Sliding Window), вы можете хранить метки времени в упорядоченном множестве для каждого ключа и удалять устаревшие записи перед подсчетом (обычно эту логику реализуют при помощи Lua скрипта исполняемого в Redis, чтобы сохранить атомарность операций).

Redis для поиска по близости гео позиции

Redis изначально поддерживает геопространственные индексы с такими операциями, как GEOADD и GEOSEARCH.

Основные команды достаточно просты:

# Добавить "member" в индекс по ключу "key"
GEOADD key longitude latitude member

# Поиск в индексе по ключу "key" в заданнай позиции и с данным радиусом
GEOSEARCH key FROMLONLAT longitude latitude BYRADIUS radius unit

Команда поиска выполняется за время O(N + log(M)), где N - количество элементов внутри указанного радиуса, а M - количество элементов внутри всего гео индекса.

Почему тут присутствуют обе величины N и M? Геопространственные команды Redis используют гео-хеши (Geohash) для индексации данных. Эти гео-хеши позволяют быстро извлекать кандидатов в границах прямоугольников, выровненных по сетке. Но такие границы квадратные и приблизительные. Во втором проходе кандидаты окончательно фильтруются - остаются только те объекты, которые находятся внутри заданного радиуса.

Redis как хранилище событий (Event Sourcing)

Потоки Redis представляют собой неизменяемые (append-only) журналы, аналогичные топикам Kafka. Основная идея потоков Redis заключается в том, что мы хотим надежно добавлять элементы в журнал, а затем иметь распределенный механизм чтения элементов из этих журналов. Redis решает эту задачу с помощью потоков (команда XADD) и групп потребителей (команды XREADGROUP и XCLAIM).

Простым примером является очередь заданий. Мы хотим добавлять задания в очередь и затем обработать их. В какой-то момент один из наших рабочих процессов может завершиться неудачей, и в таких ситуациях желательно повторно обработать задание после обнаружения отказа. Используя потоки Redis, мы добавляем задания в очередь с помощью команды XADD, и прикрепляем группу потребителей к потоку для наших рабочих процессов. Эта группа потребителей сохраняет ссылку на обработанные элементы потока и, в случае отказа рабочего процесса, обеспечивает возможность новому рабочему процессу захватить (с помощью команды XCLAIM) и заново обработать задание.

Redis для обработки сообщений (Pub/Sub)

Redis поддерживает паттерн публикации-подписки (Pub/Sub), позволяющий передавать сообщения множеству подписчиков в режиме реального времени. Это полезно для построения чат-систем, систем уведомления, или любых ситуаций, где требуется отделить производителей сообщений от потребителей. Более подробно мы обсудим это в разделе шаблона Обновления в реальном времени (Realime Updates).

Основные команды просты:

# Отправляет сообщение всем подписчикам в канале 'channel' (префикс S от слова Sharded)
SPUBLISH channel message

# Ожидает сообщений в канале 'channel'
SSUBSCRIBE channel

Клиенты Pub/Sub используют одно соединение с каждым узлом кластера (а не отдельное соединение на каждый канал). Обычно это означает, что количество соединений равно количеству узлов вашего кластера. Это также значит, что вам не потребуется миллионы соединений даже при наличии миллионов каналов!

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

Недостатки и пути их исправления

Проблема горячих ключей (Hot-Key)

Если нагрузка неравномерно распределена по ключам в нашем кластере Redis, мы можем столкнуться с проблемой, называемой "проблемой горячего ключа". Чтобы проиллюстрировать это, представим, что мы используем Redis для кэширования информации о товарах в интернет-магазине. У нас много товаров, поэтому мы масштабировали кластер до 100 узлов, и товары равномерно распределены между ними. Пока все хорошо. Теперь предположим, что однажды возникает всплеск интереса к одному конкретному товару настолько большой, что объем обращений к этому товару сравнялся с объемом обращений ко всем остальным товарам.

Теперь нагрузка на один сервер значительно выше, чем на остальные. Если мы заранее не обеспечили избыточность ресурсов (то есть использовали лишь небольшую долю имеющегося CPU на каждом узле), этот сервер начнет давать сбои.

Существует множество потенциальных решений этой проблемы, каждое из которых имеет свои преимущества и недостатки:

• Можно добавить внутренний кэш (in-memory cache) в наших клиентах, чтобы они делали меньше запросов к Redis
• Можно сохранять одни и те же данные в нескольких ключах и рандомизировать запросы, чтобы они распределялись по всему кластеру
• Можно создать дополнительные реплики для чтения и динамически масштабировать их в зависимости от нагрузки

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

Заключение

Redis - мощный, универсальный и простой инструмент, который будет полезен на System Design интервью. Простые структуры данных Redis позволяют ясно рассуждать о компромиссах при масштабировании и углубляться в обсуждение с интервьюером, не нуждаясь в глубоком знании внутренних механизмов Redis.