Потоки Redis как чистая структура данных

в 18:02, , рубрики: csv, listpack, redis, Streams, потоки, Программирование, структура данных

Новая структура данных Redis 5 под названием «потоки» (streams) вызвала живой интерес в сообществе. Как-нибудь я поговорю с теми, кто использует потоки в продакшне, и напишу об этом. Но сейчас хочу рассмотреть немного другую тему. Мне начинает казаться, что многие представляют потоки неким сюрреалистичным инструментом для решения ужасно трудных задач. Действительно, эта структура данных *также* осуществляет обмен сообщениями, но будет невероятным упрощением считать, что функциональность Redis Streams ограничена только этим.

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

Потоки — это CSV на стероидах

Если хотите записать ряд структурированных элементов данных и думаете, что БД будет здесь излишеством, можете просто открыть файл в режиме append only и записать каждую строку как CSV (Comma Separated Value):

(open data.csv in append only)
time=1553096724033,cpu_temp=23.4,load=2.3
time=1553096725029,cpu_temp=23.2,load=2.1

Выглядит просто. Люди делали это давным-давно и до сих пор делают: это надёжный шаблон, если знать, что к чему. Но какой будет эквивалент в памяти? В памяти становится возможной гораздо более продвинутая обработка данных, и автоматически снимаются многие ограничения файлов CSV, такие как:

  1. Трудно (неэффективно) выполнять запросы диапазона.
  2. Слишком много избыточной информации: в каждой записи почти одинаковое время, а поля дублируются. В то же время удаление данных сделает формат менее гибким, если я хочу переключиться на другой набор полей.
  3. Смещения элементов — это просто смещение байтов в файле: если мы изменим структуру файла, смещение станет неправильным, поэтому здесь нет реальной концепции первичного идентификатора. Записи по сути невозможно представить как-то однозначно.
  4. Не имея возможности сбора мусора и не переписывая лог нельзя удалить записи, а только пометить их как невалидные. Переписывание логов обычно отстой по нескольким причинам, желательно его избегать.

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

Введение в потоки (можете пропустить, если уже знакомы с основами)

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

> XADD mystream * cpu-temp 23.4 load 2.3
"1553097561402-0"
> XADD mystream * cpu-temp 23.2 load 2.1
"1553097568315-0"

Как видно из примера, команда XADD автоматически генерирует и возвращает идентификатор записи, который монотонно увеличивается и состоит из двух частей: <time>-<counter>. Время в миллисекундах, а счётчик увеличивается для записей с одинаковым временем.

Итак, первая новая абстракция для идеи CSV-файла в режиме append only заключается в использовании звёздочки в качестве аргумента ID для XADD: так мы бесплатно получаем с сервера идентификатор записи. Этот идентификатор полезен не только для указания на определённый элемент в потоке, он также связан со временем добавления записи в поток. Фактически, с помощью XRANGE можно выполнять запросы диапазона или извлекать отдельные элементы:

> XRANGE mystream 1553097561402-0 1553097561402-0
1) 1) "1553097561402-0"
   2) 1) "cpu-temp"
      2) "23.4"
      3) "load"
      4) "2.3"

В этом случае я использовал одинаковый ID для начала и конца диапазона, чтобы идентифицировать один элемент. Однако я могу использовать любой диапазон и аргумент COUNT для ограничения количества результатов. Точно так же нет необходимости указывать для диапазона полные идентификаторы, я могу просто использовать только unix-время, чтобы получить элементы в заданном диапазоне времени:

> XRANGE mystream 1553097560000 1553097570000
1) 1) "1553097561402-0"
   2) 1) "cpu-temp"
      2) "23.4"
      3) "load"
      4) "2.3"
2) 1) "1553097568315-0"
   2) 1) "cpu-temp"
      2) "23.2"
      3) "load"
      4) "2.1"

На данный момент нет необходимости показывать вам другие возможности API, для этого есть документация. Пока давайте просто сосредоточимся на этом шаблоне использования: XADD для добавления, XRANGE (а также XREAD) для извлечения диапазонов (в зависимости от того, что вы хотите сделать), и давайте посмотрим, почему потоки настолько мощны, чтобы называть их структурой данных.

Если хотите узнать больше о потоках и API, обязательно почитайте учебник.

Теннисисты

Несколько дней назад мы с другом, который начал изучать Redis, моделировали приложение для отслеживания местных теннисных кортов, игроков и матчей. Способ моделирования игроков совершенно очевиден, игрок — это небольшой объект, поэтому нам нужен только хеш с ключами типа player:<id>. Дальше вы сразу поймёте, что нужен способ отслеживать игры в конкретных теннисных клубах. Если player:1 и player:2 сыграли между собой и player:1 выиграл, мы можем отправить в поток следующую запись:

> XADD club:1234.matches * player-a 1 player-b 2 winner 1
"1553254144387-0"

Такая простая операция даёт нам:

  1. Уникальный идентификатор матча: ID в потоке.
  2. Нет необходимости создавать объект для идентификации матча.
  3. Бесплатные запросы диапазона для постраничного просмотра матчей или просмотра матчей на определённую дату и время.

До появления потоков нам бы пришлось создавать сортированный набор по времени: элементами сортированного набора будут идентификаторы матчей, которые сохраняются в другом ключе в качестве хеш-значения. Это не только больше работы, но и больше памяти. Гораздо, гораздо больше памяти (см. ниже).

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

Память

Приведённый выше пример использования — это не просто более цельный шаблон программирования. Расход памяти в потоках настолько отличается от старого подхода с сортированным набором + хеш для каждого объекта, что теперь начинают работать некоторые вещи, которые раньше вообще было невозможно реализовать.

Вот статистика по объёму памяти для хранения миллиона матчей в конфигурации, представленной ранее:

Сортированный набор + хеш = 220 МБ (242 RSS)
Потоки                    = 16,8 МБ (18.11 RSS)

Разница больше, чем на порядок (а именно, в 13 раз). Это означает возможность работать с задачами, которые раньше были слишком дорогостоящими для выполнения в памяти. Теперь они вполне жизнеспособны. Магия заключается в представлении потоков Redis: макроузлы могут содержать несколько элементов, которые очень компактно закодированы в структуре данных под названием listpack. Эта структура позаботится, например, о кодировании целых чисел в двоичной форме, даже если они являются семантически строками. Кроме того, мы применяем дельта-компрессию и сжимаем одинаковые поля. Тем не менее, сохраняется возможность искать по ID или времени, потому что такие макроузлы связаны в базисном дереве, которое также разработано с оптимизацией по памяти. Всё вместе это объясняет экономное использование памяти, но интересная часть заключается в том, что семантически пользователь не видит никаких деталей реализации, делающих потоки настолько эффективными.

Теперь давайте посчитаем. Если я могу хранить 1 миллион записей примерно в 18 МБ памяти, то я могу хранить 10 миллионов в 180 МБ и 100 миллионов в 1,8 ГБ. Всего с 18 ГБ памяти у меня может быть 1 миллиард элементов.

Временные ряды

Важно отметить, что пример выше с теннисными матчами семантически *очень отличается* от использования потоков Redis для временных рядов. Да, логически мы всё ещё регистрируем какое-то событие, но есть фундаментальное различие. В первом случае мы ведём лог и создаём записи для рендеринга объектов. А во временных рядах просто измеряем нечто происходящее снаружи, что на самом деле не представляет объект. Вы можете сказать, что это различие тривиально, но это не так. Важно понять идею, что потоки Redis можно использовать для создания небольших объектов с общим порядком и присвоения идентификаторов таким объектам.

Но даже самый простой вариант использования временных рядов, очевидно, это огромный прорыв, потому что до появления потоков Redis был практически бессилен тут что-либо сделать. Характеристики памяти и гибкость потоков, а также возможность ограничения capped-потоков (см. параметры XADD) — очень важные инструменты в руках разработчика.

Выводы

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

Автор: m1rko

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js