Первая часть находится здесь.
А вторая здесь.
Данная статья содержит следующие темы:
- временные последовательности на сортированных множествах;
- временные последовательности на лексикографически сортированных множествах;
- временные последовательности на битовых полях;
- базовый паттерн ограничения пропускной способности;
- фильтр Блума;
- счётчик;
- паттерн подсчёта битов;
- HyperLogLog;
- Lua-скрипты.
Данные временных последовательностей
Данные временных последовательностей, или данные с естественным временным порядком, могут быть смоделированы в Redis несколькими способами в зависимости от самих данных и желаемого вами способа доступа к ним. Мы рассмотрим несколько таких паттернов:
- временные последовательности на сортированных множествах;
- временные последовательности на лексикографически сортированных множествах;
- временные последовательности на битовых полях;
Временные последовательности на сортированных множествах
Временные последовательности на сортированных множествах (zsets) типичный способ моделирования временной последовательности в Redis. Сортированные множества состоят из уникальных объектов, счета (scores) которых хранятся под одним ключом. Использование этого типа данных для сортированных множеств означает, что счёт ведёт себя как своего рода указатель времени (зачастую это отметка времени с точностью до миллисекунды), а элемент записываемые данные. Единственная выгода заключается в том, что, поскольку это форма множества, допускаются только уникальные элементы, и попытка записать временные последовательности с одинаковыми значениями лишь обновит счёт. Чтобы проиллюстрировать эту проблему возьмём следующий пример периодической записи температуры:
Временная метка | Температура, C |
---|---|
1586697976001 | 21 |
1586697977001 | 22 |
1586697978001 | 21 |
Если просто добавить их в сортированное множество, используя ZADD, можно потерять некоторые значения:
АНТИ-ПАТТЕРН
> ZADD temperature 1586697976001 21(integer) 1> ZADD temperature 1586697977001 22(integer) 1> ZADD temperature 1586697978001 21(integer) 0> ZRANGEBYSCORE temperature -inf +inf WITHSCORES1) "22"2) "1586697977001"3) "21"4) "1586697978001"
Обратите внимание, что третий вызов ZADD возвращает 0, что говорит о том, что новый элемент не был добавлен ко множеству. Затем в ZRANGEBYSCORE мы видим, что в сортированном множестве лишь две записи. Почему? Потому что первая и третья делят один и тот же объект, и мы просто обновили счёт у этого объекта. Есть несколько способов обхода этой проблемы. Один из них включить какие-то случайные данные с достаточным разбросом, обеспечив тем самым уникальность.
Для начала создадим псевдослучайное вещественное число от 0 до 1 не включительно, затем добавим его к нашей временной метке. В нашем примере мы оставим его в десятичной форме для читабельности (в реальности разумней будет просто конвертировать в 8-байтовую строку для экономии пространства).
> ZADD temperature2 1586697976001 21:1586697976001.2583(integer) 1> ZADD temperature2 1586697977001 22:1586697977001.941678(integer) 1> ZADD temperature2 1586697978001 21:1586697978001.732015(integer) 1> ZRANGEBYSCORE temperature2 -inf +inf WITHSCORES1) "21:1586697976001.2583"2) "1511533205001"3) "22:1586697977001.941678"4) "1586697977001"5) "21:1586697978001.732015"6) "1586697978001"
Как видите, все ZADD вернули 1, обозначая успешное добавление, и ZRANGEBYSCORE вернул все значения. Это рабочий метод, однако, это не очень эффективно из-за траты байтов для обеспечения уникальности, что добавляет накладных расходов хранилищу. В большинстве случаев уникальность будет просто отметаться вашим приложением. Следует отметить, что добавление уникальности не потребуется, если ваши данные будут уже уникальными (например, данные, включающие UUID).
С этим методом у вас есть доступ ко всем методам сортированных множеств для анализа и управления:
- ZRANGEBYSCORE позволяет получить определённый срез между двумя временными метками (ZREVRANGEBYSCORE вернёт срез в убывающем порядке);
- ZREMRANGEBYSCORE позволяет удалить определённые диапазон временных меток;
- ZCOUNT количество элементов между диапазоном временных меток;
- ZINTERSTORE позволяет получить пересечение двух порций данных и сохранить это под новым ключом;
- ZUNIONSTORE позволяет получить объединение двух порций данных и тоже сохранить это под новым ключом. Можно также это использовать для дубликации сортированного множества.
ZINTERSTORE и ZUNIONSTORE операции, работающие с несколькими ключами. При работе с разделяемым окружением нужно быть осторожным, проверять, что ваш новый ключ окажется в том же сегменте, иначе эти команды приведут к ошибке.
Временные последовательности на лексикографически сортированных множествах
Другой способ работы с временными последовательностями использование лексикографических свойств сортированных множеств, чтобы хранить временную метку и значение. Если вы ещё не знакомы с этим, то самое время прочитать этот раздел.
При этом методе мы храним всё с тем же самым счётом и кодируем сначала временную метку, затем добавляем значение в качестве элемента. Возьмём пример:
> ZADD lex-temperature 0 1589392163001:21(integer) 1> ZADD lex-temperature 0 1589392164001:22(integer) 1> ZADD lex-temperature 0 1589392165001:21(integer) 1> ZRANGE lex-temperature 0 -11) "1589392163001:21"2) "1589392164001:22"3) "1589392165001:21"
В этих трёх вызовах ZADD временная метка отделена от значения двоеточием, и мы можем увидеть, что каждый раз возвращается 1, что означает, что все три были добавлены. В ZRANGE мы видим сохранённый порядок. Почему? В сортированных множествах, если счёт одинаков, результаты с тем же счётом упорядочены бинарной сортировкой. Так как временные метки в данный период имеют то же количество цифр, все будут отсортированы правильно (если ваши временные метки находятся до 2002 или после 2285, вам понадобятся ещё цифры для заполнения).
Чтобы получить диапазон значений из этого типа, используйте команду ZRANGEBYLEX:
> ZRANGEBYLEX lex-temperature (1511533200001 +1) "1589392163001:21"2) "1589392164001:22"3) "1589392165001:21"
Второй аргумент имеет префикс (, указывающий на исключительность значения (включительность обозначается [). На практике такой формат делает включительность и исключительность нерелевантной, так как за временной меткой всегда будут следовать дополнительные данные. Третий аргумент + указывает на неограниченность верхней границы.
Попытаемся получить дату между 1589392160001 и 1589392165001 включительно:
> ZRANGEBYLEX lex-temperature [1589392160001 [15893921650011) "1589392163001:21"2) "1589392164001:22"
Почему данные по временной метке 1589392165001 не попали в выборку, несмотря на включительный префикс? Хочется верить, что Redis как-то понимает, что это временная метка. На деле же Redis просто видит бинарную сортировку. В бинарной сортировке 1589392165001:21 больше, чем 1589392165001 включительно или исключительно. Корректный способ включить это в верхнюю границу добавить 1 миллисекунду к нужной верхней границе и использовать исключительность:
> ZRANGEBYLEX lex-temperature [1589392160001 (15893921650021) "1589392163001:21"2) "1589392164001:22"3) "1589392165001:21"
У временных последовательностей с лексикографически сортированными множествами есть похожий набор полезных команд, как у временных последовательностей с просто сортированными множествами:
- ZRANGEBYLEX / ZREVRANGEBYLEX получает диапазон значений по возрастанию или убыванию;
- ZREMRANGEBYLEX удаляет конкретный сортированный диапазон значений;
- ZLEXCOUNT получает количество элементов в сортированном диапазоне значений.
ZINTERSTORE и ZUNIONSTORE можно использовать на лексикографически сортированных множествах, однако есть риск потери данных, поскольку дублирующиеся комбинации временных меток и значений не будут дублироваться в возвращаемом результате.
Вы можете задаться вопросом, зачем выбирать сортированные множества с временными метками вместо кодирования лексикографически сортированных множеств. Как правило лучше работать с лексикографически сортированными множествами для временных последовательностей если значения не будут всегда уникальными, временные метки будут более эффективны.
Временные последовательности на битовых полях
Redis может эффективно хранить временные последовательности в битовых полях. Для этого нужно сначала выбрать произвольную точку отсчёта и числовой формат. Возьмём пример с измерением температуры.
Предположим, мы хотим брать температуру каждую минуту, и точкой отсчёта мы сделаем полночь каждого дня. Мы измеряем температуру в помещении в градусах Цельсия. Можно структурировать данные следующим образом:
- 0 минута = байт 0;
- температура записывается в 8-битное беззнаковое число (0-255).
За день наберётся данных примерно на 1.44 кб. Записать температуру можно командой BITFIELD:
> BITFIELD bit-ts SET u8 #0 221) (integer) 0
В этом случае по ключу bit-ts в беззнаковое 8-битное число (u8) в полночь (#0) записывается значение температуры 22.
Битовые поля не ограничены беззнаковыми 8-битными значениями. Обратите внимание на знак решётки перед смещением (offset). Он означает, что будет происходить выравнивание по выбранному типу. Например, если вы укажете "#79" это будет означать 79й байт, 79 79й бит (см. справку по BITFIELD).
Смещение может быть выровнено по типу сохранённого числа, начиная от 0. Например, если мы хотим записать 1 a.m, учитывая нулевые слоты, мы используем смещение #59 или смещение #719 для полудня.
> BITFIELD bit-ts SET u8 #59 23 SET u8 #719 251) (integer) 02) (integer) 0
Пример также показывает, что BITFIELD вариативен, т.е. можно работать с несколькими значениями в одном вызове.
Добавим ещё несколько значений:
> BITFIELD bit-ts SET u8 #60 21 SET u8 #61 201) (integer) 02) (integer) 0
И теперь извлечём:
> BITFIELD bit-ts GET u8 #59 GET u8 #60 GET u8 #611) (integer) 232) (integer) 213) (integer) 20
Сигнатура битовой подкоманды GET похожа на сигнатуру SET с той лишь разницей, что она не принимает третьим аргументом значение. Нормально, когда мы знаем все индексы, которые надо получить, но иногда нам нужен диапазон значений, и обозначать каждый байт по отдельности будет слишком напряжно. Мы можем использовать команду GETRANGE. В нормальной ситуации она используется для получения байтов из строки, но BITFIELDы просто другой способ адресации тех же данных.
> GETRANGE bit-ts 59 61"\x17\x15\x14"
Команда вернула байты с 59 по 61 в шестнадцатеричном виде (23, 21 и 20 в десятичной. Клиентские языки обрабатывают двоичные данные лучше, чем redis-cli, и обычно могут получить специфичный для языка массив байтов.
В нашем примере мы использовали байты 0, 59-61 и 719. Что будет, если мы запросим байты, которые ещё не заданы?
> BITFIELD bit-ts GET u8 #401) (integer) 0> BITFIELD bit-ts GET u8 #7501) (integer) 0> GETRANGE bit-ts 30 50"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
Redis отдаёт незаданные байты как 0. Это может вызвать затруднения при работе с данными временных последовательностей логике приложения нужно отличать 0 и неустановленное значение. Возможны округления и пропуски значений 0, особенно при использовании целых чисел со знаком, поскольку это может быть допустимым значением в середине вашего диапазона.
Реальная длина временной последовательности на самом деле зависит от последнего байта. В примере последний сохранённый байт 719, поэтому длина данных 720 байтов.
> STRLEN bit-ts(integer) 720
Временные последовательности основанные на BITFIELD мощный и компактный паттерн для хранения числовых или двоичных данных. Однако, это решение не покрывает всех вариантов использования, и его использование должно быть тщательно обдумано на соответствие вашим потребностям.
Базовый паттерн ограничения пропускной способности
Создать ограничитель пропускной способности с Redis легко, благодаря наличию команд INCR и EXPIRE. Идея в том, что вы хотите ограничивать запросы к определённому сервису в заданный промежуток времени. Допустим, у нас есть сервис, в котором пользователи идентифицируются по ключу API. В сервисе действует ограничение на 20 запросов в минуту. Для реализации этого мы хотим создавать каждую минуту ключ Redis на ключ API. Чтобы не захламлять базу данных, время действия ключа устанавливаем также в 1 минуту.
Ключ API zA21X31, жирный шрифт лимит достигнут:
Ключ Redis | zA21X31:0 | zA21X31:1 | zA21X31:2 | zA21X31:3 | zA21X31:4 |
Значение | 3 | 8 | 20 | 2 | 20 |
Истекает в | 12:02 | 12:03 | 12:04 | 12:05 | 12:06 |
Время | 12:00 | 12:01 | 12:02 | 12:03 | 12:04 |
Ключ составляется из ключа API и номера минуты через двоеточие. Так как время действия ключей всегда истекает, нам достаточно использовать только номера минут с наступлением нового часа можно быть уверенным, что других 59 ключей уже нет (они истекли 59 минут назад).
Рассмотрим, как это работает:
-
> GET [ключ API]:[номер минуты]
- Если результат меньше 20 или не установлен, переходим к шагу 4, иначе к шагу 3;
- Вывести сообщение об ошибке, закрыть соединение и завершить;
-
> MULTIOK> INCR [user-api-key]:[current minute number]QUEUED> EXPIRE [user-api-key]:[current minute number] 59QUEUED> EXECOK
- Продолжить выполнение программы.
Два ключевых момента:
- INCR на несуществующем ключе всегда будет 1;
- EXPIRE находится внутри транзакции MULTI вместе с INCR, что означает, что это будет одна атомарная операция.
Худший сценарий если по какой-то очень странной и маловероятной причине сервер Redis умирает между INCR и EXPIRE. При восстановлении данных либо из AOF, либо из in-memory реплики, INCR не будет восстановлен, так как транзакция не была выполнена.
При использовании этого паттерна возможна ситуация, когда у одного пользователя окажется два ключа: один, который используется в настоящий момент, и другой, время действия которого истекает в эту минуту. Тем не менее паттерн очень эффективен.
Фильтр Блума
Фильтр Блума интересная вероятностная структура данных, которую можно использовать, чтобы проверить, не был ли элемент добавлен ранее. Здесь намеренно такая формулировка.
Вероятностность в том, что может быть только ложноположительное срабатывание, но не ложноотрицательное. Фильтр Блума предоставляет намного более компактный и быстрый способ проверить наличие, чем сохранять все элементы во множество и вызовать SISMEMBER.
Фильтр Блума работает, пропуская элемент через функцию быстрого хэширования, отбирая из него биты и устанавливая их в 1 и 0 через определённый интервал в битовом поле. Чтобы проверить наличие в фильтре, отбираются одинаковые биты. У многих элементов могут быть биты, которые перекрываются, но, так как хэш-функция создаёт уникальные идентификаторы, если один бит из хэша всё ещё равен 0, тогда мы знаем, что он не был добавлен ранее.
Фильтр используется в Redis много лет как клиентская библиотека, которая использует GETBIT и SETBIT для работы с битовыми полями. К счастью, с версии Redis 4.0 доступен модуль ReBloom, который избавляет от создания собственной реализацию фильтра Блума.
Хороший вариант использования для этого фильтра проверка, было ли уже использовано имя пользователя. На малых размерах данных проблем нет, но по мере роста сервиса запросы к базе данных могут дорого стоить. Это легко исправить с ReBloom.
Добавим несколько имён для теста:
> BF.ADD usernames funnyfred(integer) 1> BF.ADD usernames fredisfunny(integer) 1> BF.ADD usernames fred(integer) 1> BF.ADD usernames funfred(integer) 1
Теперь протестируем фильтр Блума:
> BF.EXISTS usernames fred(integer) 1> BF.EXISTS usernames fred_is_funny(integer) 0
Как и ожидалось, fred_is_funny вернул 0. Это означает, что такое имя не было использовано. Хотя нельзя сказать наверняка, поскольку биты могут просто перекрыться между несколькими элементами. В основном шанс ложноположительного срабатывания низкий, но не равен 0. По мере заполнения фильтра Блума шанс возрастает, но можно настроить частоту ошибок и начальный размер (по умолчанию 0.01 и 100 соответственно).
Счётчик
Счётчик в Redis можно реализовать несколькими способами. Наиболее очевидный INCR со товарищи (INCRBY, INCRBYFLOAT, HINCRBY, HINCRBYFLOAT, ZINCRBY), применение которым можно найти, просто прочтя документацию. Менее очевидные использование BITCOUNT и PFADD.
Паттерн подсчёта битов
BITCOUNT считает число битов, установленных в 1 в битовом поле по ключу. Это можно использовать для подсчёта серии активностей в течение произвольного периода времени (наподобие паттерну временных последовательностей на битовых полях). Процесс заключается в выборе момента времени, и каждый бит представляет единицу периода. Каждый раз, когда в течение этого периода совершается действие, запускаем SETBIT на расстоянии в 1 единицу от последней точки.
12:00 | 12:02 | 12:03 | 12:04 |
---|---|---|---|
|
|
|
|
[точка отсчёта] | Действие | Действие | Действие |
Вычислить, в какие минуты с 12:00 по 12:30 происходила активность, можно так:
> BITCOUNT btct 0 30(integer) 3
В целом, этот паттерн отвечает на вопрос Как часто?, а не Сколько раз?. Например, пользователь мог быть активным 20 раз в течение одной минуты, но это засчитается как 1.
Реальным преимуществом этого шаблона является то, что он обеспечивает минимально возможный счёт в течение определённого периода времени, поскольку биты являются самыми элементарными строительными блоками хранения. Это буквально наименьшее (несжатое) хранилище для подсчета.
HyperLogLog
Подсчёт уникальных элементов может оказаться непростым. Обычно это означает сохранение каждого уникального элемента, а затем вызов этой информации каким-то образом. В Redis это можно сделать, используя множество и одну команду, однако, и занимаемый объём, и временная сложность этого будут очень велики. HyperLogLog предоставляет вероятностную альтернативу.
HyperLogLog внутренне похож на фильтр Блума, также подаёт элементы через некриптографическую хэш-функцию и устанавливает биты в битовом поле. Но, в отличие от фильтра Блума, HyperLogLog хранит счётчик элементов, который инкрементируется, когда добавляется новый элемент, не добавленный ранее. Это даёт низкий уровень ошибок при подсчёте уникальных элементов в множестве. HyperLogLog встроен прямо в Redis.
Существует 3 команды HyperLogLog в Redis: PFADD, PFCOUNT и PFMERGE. Допустим, мы создаём веб-сканер и хотим подсчитывать количество уникальных URL страниц, просмотренных в течение дня. Для каждой страницы запустим следующую команду:
> PFADD crawled:20200613 "http://www.google.com/"(integer) 1> PFADD crawled:20200613 "http://www.redislabs.com/"(integer) 1> PFADD crawled:20200613 "http://www.redis.io/"(integer) 1> PFADD crawled:20200614 "http://www.redisearch.io/"(integer) 1> PFADD crawled:20200614 "http://www.redis.io/"(integer) 1
Каждый ключ выше индексируется по дням. Посмотреть, сколько страниц было просмотрено 13.06.2020, можно так:
> PFCOUNT crawled:20200613(integer) 3
Для просмотра количества страниц за 13.06.2020 и 14.06.2020, используем команду PFMERGE, чтобы создать новый ключ со значением, объединяющим два счётчика. Обратите внимание, что, так как www.redis.io хранится в обоих множествах, подсчитан он будет единожды:
> PFMERGE crawled:20200613-14 crawled:20200613 crawled:20200614OK> PFCOUNT crawled:20200613-14(integer) 4
Это операция может работать с несколькими ключами, поэтому будьте осторожны в разделённом окружении, дабы ключи оказались на одном шарде.
Lua-скрипты
Redis может делать изумительные вещи просто из redis-cli и ещё больше между Redis и вашим языком программирования. Но иногда может потребоваться поведение, которого нельзя получить в клиент-серверной архитектуре из-за вопросов эффективности или безопасности логику нужно выполнить в слое базы данных. В таких случаях на помощь приходит Lua. Lua работает в Redis как скриптовый язык. С ним можно выполнять код в Redis, без затрат на транспорт до и от клиента.
Тестовый пример добавление значения к хэш-полю. В то время как Redis может легко добавлять значение к строковому ключу при помощи APPEND, нет команды для добавления значения к хэш-полю. Можно попытаться получить это, извлекая значение клиентом, добавляя новую строку к значению и сбросывая хэш-поля, но это плохая идея. Так как это неатомарно, есть вероятность, что пока вы добавляете значение, другой клиент может изменить его раньше, и тогда вы перезапишете новое значение.
# | Клиент 1 | Клиент 2 |
---|---|---|
1 |
[возвращается hello] |
|
2 | [добавляет world к hello] |
|
3 |
|
|
4 |
|
Как можно видеть на строке 2, обновление будет утеряно. Можно использовать Lua-скрипты, чтобы обойти эту проблему и убрать расходы на отправку/получение значений с клиента.
В любом текстовом редакторе создадим скрипт и назовём это happened.lua:
local original = redis.call('HGET',KEYS[1],ARGV[1])return redis.call('HSET',KEYS[1], ARGV[1], original .. ARGV[2])
В первой строке создаём локальную переменную original, в которую сохраним текущее значение ключа хэша из первого переданного аргумента, а поле является первым неключевым аргументом. Важно понимать, что Lua-скрипты во время выполнения делают различия между ключами и неключевыми аргументами.
На второй строке вызывается HSET для того же ключа и поля, затем объединяем оригинальное значение со вторым неключевым аргументом. Это возвращается обратно в Redis, поэтому мы сохраним оригинальное возвращаемое значение HSET.
Непосредственное выполнение Lua-скриптов командой EVAL может быть запутанным и неэффективным. В Redis есть встроенный кэш скриптов, который позволяет предзагрузить скрипт, затем обратиться к нему по SHA1-хэшу из основного скрипта. Загрузить этот скрипт из командной строки можно с помощью cat и redis-cli. Обратите внимание, если ваш скрипт будет отличаться хотя бы на один символ, у него будет совсем другой хэш.
$ redis-cli -a yourRedisPassword SCRIPT LOAD "$(cat ./happend.lua)""d30c7f6d0c23fcfe6d4630b11f4e3db4cb2db099"
Сейчас можно использовать EVALSHA, чтобы вызвать скрипт и сделать добавление:
> HSET mynewhash greeting "Hello"(integer) 1> EVALSHA d30c7f6d0c23fcfe6d4630b11f4e3db4cb2db099 1 mynewhash greeting " world"(integer) 0> HGET mynewhash greeting"Hello world"
Первый аргумент команды EVALSHA хэш скрипта, созданного SCRIPT LOAD. Второй аргумент количество ключей. В нашем случае ключ один. Третий аргумент ключ, над которым выполняем действие. И наконец четвёртый значение, которое добавляем к полю.
Поскольку добавление происходит внутри Lua-скрипта, сценарий выше прервётся, так как Lua-скрипты выполняются синхронно и атомарно.
Хоть Lua может быть очень полезным при решении проблем, использовать его нужно осторожно. Скрипт блокирует сервер и может привести к не отвечающей базе данных. В ситуациях с шардингом скрипты пытаются сохранить все операции на одном сервере, чтобы избежать перекрёстных ошибок.
На этом раздел Redis Best Practices заканчивается. Не бойтесь пробовать и экспериментировать, Redis очень богата на функциональность. Оставляйте в комментариях свои интересные варианты использования.
Надеюсь, описанные техники помогут вам если и не напрямую, то хотя бы наведением на верный путь к решению задач!