Redis
 sql >> база данни >  >> NoSQL >> Redis

Въведение в Redis структури от данни:сортирани набори

Сортираният набор е едни от най-модерните структури от данни в Redis. Сортираният набор е по същество уникална колекция от подредени низове на Redis, които имат цифров резултат, свързан с тях. Подреждането се основава на партитури и лексикографския ред на низовете (повече за това по-късно). Низовете трябва да са уникални, докато резултатите може да се повтарят.

Освен списъци, това е единственият поръчан структура на данни в Redis и се предпочитат пред списъци, когато достъпът до която и да е част от списъка е важен (за разлика от списъка, който предоставя достъп до краищата на списъка). Средното вмъкване, премахване и търсене в сортирани набори са O(N), където N е броят на елементите в набора.

Сортиране

Резултатите в сортиран набор са двойни 64-битови числа с плаваща запетая в диапазона -(2^) и +(2^). Сортираните комплекти са сортирани по резултата във възходящ ред. Резултатите могат да бъдат актуализирани за съществуващи ключове. За да се прекъснат резултатните връзки, низовете в сортиран набор се подреждат в лексикографски възходящ ред. В Redis 2.8 беше внедрена нова функция за използване на това лексикографско подреждане:заявка за лексикографски диапазон. Това има завладяващи случаи на употреба, които ще видим по-късно.

Команди

Сортираните набори на Redis поддържат различни операции от просто набор, получаване, брой членове до сложни изчисления на лексикографски обхват. Поддържат се около 25+ операции. Ще разгледаме подмножество от тях. Нека започнем с основните:

# ZADD key [NX|XX] [CH] [INCR] score member [score member ...] Add elements into the set
# O(log(N) where N is the number of elements in the set
# [NX|XX], [CH] & [INCR] available on > 3.0.2
127.0.0.1:6379> zadd scoreboard 999 "anorak"
(integer) 1
# Analogous: use ZREM key member [member ...] to remove members from a sorted set.
# ZCARD key O(1): Cardinality of the set
127.0.0.1:6379> zcard scoreboard
(integer) 1
# Insert multi
127.0.0.1:6379> zadd scoreboard 99 "daito" 99 "shoto" 199 "aech" 299 "art3mis" 399 "parzival"
(integer) 5
# ZSCORE key member. O(1) Returns the score of member in the sorted set at key.
127.0.0.1:6379> zscore scoreboard parzival
"399"
# ZRANK key member O(log(N)) Get the rank of the member.
127.0.0.1:6379> zrank scoreboard anorak
(integer) 5
127.0.0.1:6379> zrank scoreboard shoto
(integer) 1
# ZREVRANK key member O(log(N)) Get the rank of the member with scores ordered high to low
127.0.0.1:6379> zrevrank scoreboard anorak
(integer) 0
127.0.0.1:6379> zrevrank scoreboard shoto
(integer) 4
# ZINCRBY key increment member O(log(N)) Increments the score of member in the sorted set stored at key by increment.
127.0.0.1:6379> zincrby scoreboard 100 parzival
"499"

Тези по-горе бяха някои от основните операции, възможни върху сортиран набор. Истинската стойност на сортираните набори блести в неговия диапазон въз основа на заявки в набора. Нека да ги разгледаме.

# ZRANGE key start stop [WITHSCORES]. O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
# start and stop are inclusive zero based indexes.
127.0.0.1:6379> zrange scoreboard 0 -1 WITHSCORES
 1) "daito"
 2) "99"
 3) "shoto"
 4) "99"
 5) "aech"
 6) "199"
 7) "art3mis"
 8) "299"
 9) "parzival"
10) "499"
11) "anorak"
# 0: 1st member. -1: last member
# Analogous: ZREVRANGE key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange scoreboard 0 -1 WITHSCORES
 1) "anorak"
 2) "999"
 3) "parzival"
 4) "499"
 5) "art3mis"
 6) "299"
 7) "aech"
 8) "199"
 9) "shoto"
10) "99"
11) "daito"
12) "99"
# ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]. O(log(N)+M) Returns all the elements in the sorted set at key with a score between min and max (inclusive)
# Analogous: ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
# 499 <= score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard 499 +inf
1) "parzival"
2) "anorak"
# 499 < score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard (499 +inf
1) "anorak"
# ZCOUNT key min max O(log(N)) Returns the number of elements in the sorted set at key with a score between min and max.
127.0.0.1:6379> zcount scoreboard -inf 499
(integer) 5
127.0.0.1:6379> zcount scoreboard -inf +inf
(integer) 6

Други подобни команди, свързани с диапазона, са ZREMRANGEBYRANK, ZREMRANGEBYSCORE и т.н.

Има друг набор от команди за заявка за набор, които бяха въведени в Redis 2.8:командите за лексикографски диапазон (*BYLEX). Подробности за това как се определят интервалите за тези команди са документирани тук. Изискването за правилното функциониране на тези команди е членовете на сортирания набор да имат идентичен резултат. Основните команди за работа с лексикографски диапазони са ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX и ZLEXCOUNT. Нека видим няколко примера:

127.0.0.1:6379> zadd lexscores 0 dd 0 aa 0 ccc 0 aaa 0 bb 0 d 
(integer) 6
# Once inserted, lexicographic sorting for free!
127.0.0.1:6379> zrange lexscores 0 -1
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
5) "d"
6) "dd"
# ZRANGEBYLEX key min max [LIMIT offset count]. O(log(N)+M). min max specify range. LIMIT is like limit in SQL.
# min: exclude a max: exclude c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a (c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include ccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [ccc
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
# min: exclude aa max: include cccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa [ccc
1) "aaa"
2) "bb"
3) "ccc"
# min: exclude aa max: upto all
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa +
1) "aaa"
2) "bb"
3) "ccc"
4) "d"
5) "dd"

Още друг набор от команди за сортирани множества са операциите за обединяване и пресичане.

Вътрешни елементи

Сортираните набори се изпълняват като двойна структура от данни:Това е комбинация от хеш и списък за пропускане. Хеш-частта съпоставя обекти с резултати, а списъкът за прескачане картографира резултати към обекти. Вече знаем как се внедряват хешовете в Redis от предишната ни публикация. Списъкът за пропускане гарантира, че търсенията са бързи и повечето операции средно са O(log N). Списъкът за пропускане е внедрен във файл t_zset.c.

Както повечето други структури от данни на Redis, дори и сортираните набори са оптимизирани за размер, когато са малки. Сортираните набори се съхраняват само като хешове, докато нараснат до определен размер. Конфигурационните параметри, контролиращи този размер, са: zset-max-ziplist-entries (по подразбиране 128) и zset-max-ziplist-value (по подразбиране 64).
Оценка на размера:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Приложения

Поради разширената структура от данни, сортираните набори имат различни случаи на употреба:

  1. Най-очевидният случай на употреба е като табло:поддържане на подреден списък с уникални членове, сортирани по техните резултати. За напр. табло за лидери за MMORPG, както е обяснено в официалната документация на Redis.
  2. Сортираните набори с еднакви резултати се използват като индекси в Redis. Това може да варира от много прости случаи на използване до наистина сложни. Документацията на Redis има прекрасна статия за индексирането с помощта на сортирани набори.
  3. Специален случай на индексиране с помощта на сортирани набори е GEO API за Redis, който беше въведен в Redis 3.2.0.
  4. Размерът се взема предвид при използване на сортирани набори. Като се имат предвид сложните поддържащи структури от данни, сортираните набори ще имат относително по-голям отпечатък на паметта. Точните числа ще зависят от естеството на набора от данни. Тази публикация в StackOverflow споменава базов номер за набор от данни с приличен размер.

Тъй като сортираните набори имат доста напреднали случаи на употреба, ние ще обсъдим такива случаи на употреба за сортирани набори в следващите публикации. Засега нека видим прост пример.

Геймифицирайте своя MOOC!

В предишната ни публикация за растерните изображения на Redis ние бяхме разработчиците, поддържащи много популярен MOOC. Фасилитаторите решават, че искат да геймифицират курса с табло за лидери, проследяващо най-добрите ученици, които допринасят за публикациите в общността. Студентите с най-голям брой приети отговори на проблеми, публикувани в публикациите на общността на курса, ще получават специално споменаване всяка седмица.
Това ще бъде класическият случай на използване за подреждане на уникални ключове, базирано на резултат, известен още като сортирания комплект Redis. Студентските идентификатори ще бъдат членовете, а резултатите ще бъдат броят на приетите отговори. Може да актуализираме резултата с помощта на ZINCRBY в реално време или във фонова работа, която може да се изпълнява ежедневно или седмично. Очевидно е необходимо актуализиране на резултатите в реално време за нашия случай на използване. За първоначално вмъкване ZADD с едно от новите знамена ще дойде по-удобно. Показването на таблото на учениците ще трябва да използва заявки за обратен диапазон (ZREVRANGE и др.)

Бележка под линия

Други публикации в нашата серия от структури от данни на Redis:

  • Набори
  • Хешове
  • Растрови изображения

  1. Redis
    2.   
  2. MongoDB
    3.   
  3. Memcached
    4.   
  4. HBase
    5.   
  5. CouchDB

  1. Изтичането на RedisTemplate не работи

  2. Docker Redis Connection отказа

  3. Спасяване:Връзката е отказана - Не може да се свърже с Redis на localhost:6379

  4. Memcache v/s redis за поддържане на постоянни сесии?

  5. Bull опашка:Когато дадена задача не успее, как да спрете опашката да обработва оставащите задания?