Úvod do datových struktur Redis:Seřazené sady

Sorted Set jsou některé z nejpokročilejších datových struktur v Redis. Seřazená sada je v podstatě jedinečná sbírka uspořádaných řetězců Redis, ke kterým je přiřazeno číselné skóre. Řazení je založeno na skóre a lexikografickém pořadí řetězců (více o tom později). Řetězce musí být jedinečné, zatímco skóre se může opakovat.

Kromě seznamů je to jediný objednaný datovou strukturu v Redis a jsou upřednostňovány před seznamy, když je důležitý přístup k jakékoli části seznamu (na rozdíl od seznamu, který poskytuje přístup ke koncům seznamu). Průměrné vkládání, odstraňování a vyhledávání malých a velkých písmen v seřazených sadách je O(N), kde N je počet prvků v sadě.

Řazení

Skóre v seřazené sadě jsou dvojitá 64bitová čísla s pohyblivou řádovou čárkou v rozsahu -(2^) a +(2^) včetně. Seřazené sady jsou seřazeny podle skóre ve vzestupném pořadí. Skóre lze aktualizovat pro stávající klíče. Aby bylo možné přerušit skóre skóre, řetězce v seřazené sadě jsou seřazeny lexikograficky vzestupně. V Redis 2.8 byla implementována nová funkce pro využití tohoto lexikografického řazení:dotazování na lexikografický rozsah. To má fascinující případy použití, které uvidíme později.

Příkazy

Seřazené sady Redis podporují různé operace od jednoduchých množin, získání, počtu členů až po složité výpočty lexikografických rozsahů. Je podporováno asi 25+ operací. Podíváme se na jejich podmnožinu. Začněme těmi základními:

# 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"

Ty výše uvedené byly některé ze základních operací, které byly možné na setříděné sadě. Skutečná hodnota setříděných sad svítí v jejím rozsahu na základě dotazů v sadě. Pojďme se na ně podívat.

# 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

Další podobné příkazy související s rozsahem jsou ZREMRANGEBYRANK, ZREMRANGEBYSCORE atd.

Existuje další sada příkazů sady dotazů, které byly zavedeny v Redis 2.8:příkazy lexikografický rozsah (*BYLEX). Podrobnosti o tom, jak jsou pro tyto příkazy specifikovány intervaly, jsou zdokumentovány zde. Požadavek na správné fungování těchto příkazů je, že členové seřazené sady by měli mít identické skóre. Hlavní příkazy pro práci s lexikografickými rozsahy jsou ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX a ZLEXCOUNT. Podívejme se na několik příkladů:

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"

Další sadou příkazů pro seřazené sady jsou operace sjednocení a průnik.

Interní informace

Seřazené sady jsou implementovány jako duální datová struktura:Jedná se o kombinaci jak hash, tak seznamu přeskočení. Část hash mapuje objekty na skóre a seznam přeskočení mapuje skóre na objekty. Jak jsou hashe implementovány v Redis, již víme z našeho předchozího příspěvku. Seznam přeskočení zajišťuje, že vyhledávání je rychlé a většina operací je v průměru O(log N). Seznam přeskočení je implementován v souboru t_zset.c.

Stejně jako většina ostatních datových struktur Redis jsou i Sorted sady optimalizovány pro velikost, když jsou malé. Seřazené sady jsou uloženy pouze jako hash, dokud nedosáhnou určité velikosti. Konfigurační parametry řídící tuto velikost jsou: zset-max-ziplist-entries (výchozí 128) a zset-max-ziplist-value (výchozí 64).
Odhad velikosti:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Aplikace

Sorted sets, protože se jedná o pokročilou datovou strukturu, mají různé případy použití:

1. Nejzřejmější případ použití je jako výsledková tabulka:udržování uspořádaného seznamu jedinečných členů seřazených podle jejich skóre. Pro např. výsledková tabulka pro MMORPG, jak je vysvětleno v oficiální dokumentaci Redis.
2. Seřazené sady s identickým skóre se v Redis používají jako indexy. To se může pohybovat od velmi jednoduchých případů použití až po skutečně složité. Dokumentace Redis obsahuje skvělý článek o indexování pomocí tříděných sad.
3. Speciálním případem indexování pomocí tříděných sad je GEO API pro Redis, které bylo představeno v Redis 3.2.0.
4. Při použití setříděných sad je třeba vzít v úvahu velikost. Vzhledem ke komplexním podpůrným datovým strukturám budou mít tříděné sady relativně větší paměťovou stopu. Přesná čísla budou záviset na povaze souboru dat. Tento příspěvek StackOverflow zmiňuje číslo pro slušně velký soubor dat.

Protože setříděné sady mají poměrně pokročilé případy použití, probereme takové případy použití pro tříděné sady v následujících příspěvcích. Nyní se podívejme na jednoduchý příklad.

Gamifikujte svůj MOOC!

V našem předchozím příspěvku o bitmapách Redis jsme byli vývojáři podporující velmi populární MOOC. Facilitátoři se rozhodnou, že chtějí kurz gamifikovat pomocí žebříčku sledujícího nejlepší studenty přispívající do příspěvků komunity. Studenti s nejvyšším počtem přijatých odpovědí na problémy zveřejněné v příspěvcích komunity kurzu obdrží každý týden zvláštní zmínku.
Toto bude klasický případ použití pro řazení jedinečných klíčů na základě skóre alias sady tříděných podle Redis. ID studentů budou členy, zatímco skóre bude počet přijatých odpovědí. Skóre můžeme aktualizovat pomocí ZINCRBY v reálném čase nebo v úloze na pozadí, která může běžet denně nebo týdně. Pro náš případ použití je samozřejmě vyžadována aktualizace skóre v reálném čase. Pro počáteční vložení ZADD s jednou z nových vlajek přijde vhod. Při zobrazení výsledkové tabulky studentům bude nutné využít dotazy na obrácený rozsah (ZREVRANGE atd.)

Poznámka pod čarou

Další příspěvky v naší sérii datových struktur Redis:

• Sady
• Hashes
• Bitmapy