Inleiding tot Redis-gegevensstructuren:gesorteerde sets

Sorted Set is een van de meest geavanceerde gegevensstructuren in Redis. Gesorteerde set is in wezen een unieke verzameling geordende Redis-reeksen waaraan een numerieke score is gekoppeld. De volgorde is gebaseerd op partituren en de lexicografische volgorde van de string (daarover later meer). De snaren moeten uniek zijn, terwijl de scores kunnen worden herhaald.

Naast lijsten is het de enige bestelde gegevensstructuur in Redis en hebben de voorkeur boven lijsten wanneer toegang tot een deel van de lijst belangrijk is (in tegenstelling tot Lijst die toegang biedt tot de uiteinden van de lijst). Het gemiddelde invoegen, verwijderen en zoeken in gesorteerde sets is O(N), waarbij N het aantal elementen in de set is.

Sorteren

De scores in een gesorteerde set zijn dubbele 64-bits drijvende-kommagetallen in het bereik -(2^) en +(2^) inbegrepen. Gesorteerde sets worden in oplopende volgorde gesorteerd op hun score. Scores kunnen worden bijgewerkt voor bestaande sleutels. Om scorebanden te verbreken, worden snaren in een gesorteerde set lexicografisch oplopende volgorde geordend. In Redis 2.8 is een nieuwe functie geïmplementeerd om deze lexicografische ordening te benutten:lexicografische bereikquery's. Dit heeft fascinerende toepassingen die we later zullen zien.

Opdrachten

Gesorteerde Redis-sets ondersteunen een verscheidenheid aan bewerkingen, van eenvoudige set, get, ledentelling tot complexe lexicografische bereikberekeningen. Er worden ongeveer 25+ bewerkingen ondersteund. We zullen een subset ervan bekijken. Laten we beginnen met de basis:

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

De bovenstaande bewerkingen waren enkele van de basisbewerkingen die mogelijk zijn op een gesorteerde set. De echte waarde van de gesorteerde sets schijnt in het bereik op basis van zoekopdrachten binnen de set. Laten we ze eens bekijken.

# 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

Andere vergelijkbare commando's die verband houden met het bereik zijn ZREMRANGEBYRANK, ZREMRANGEBYSCORE enz.

Er is nog een reeks setquery-commando's die in Redis 2.8 zijn geïntroduceerd:de lexicographic range (*BYLEX)-commando's. Details over hoe intervallen voor deze opdrachten worden gespecificeerd, worden hier gedocumenteerd. De vereiste om deze commando's correct te laten werken, is dat de leden van de gesorteerde set een identieke score moeten hebben. De belangrijkste opdrachten om met lexicografische bereiken te werken zijn ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX en ZLEXCOUNT. Laten we een paar voorbeelden bekijken:

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"

Nog een andere reeks opdrachten voor gesorteerde reeksen zijn de bewerkingen voor het samenvoegen en doorsnijden.

Intern

Gesorteerde sets worden geïmplementeerd als een dubbele gegevensstructuur:het is een combinatie van zowel een hash- als een skip-lijst. Het hash-gedeelte wijst objecten toe aan scores en de skip-lijst wijst scores toe aan objecten. We weten al hoe hashes worden geïmplementeerd in Redis uit onze vorige post. De Skip-lijst zorgt ervoor dat zoekopdrachten snel gaan en de meeste bewerkingen zijn gemiddeld O(log N). De Skip-lijst is geïmplementeerd in het bestand t_zset.c.

Zoals de meeste andere Redis-gegevensstructuren zijn zelfs gesorteerde sets geoptimaliseerd voor grootte wanneer ze klein zijn. Gesorteerde sets worden alleen als hashes opgeslagen totdat ze een bepaalde grootte hebben bereikt. De configuratieparameters die deze grootte bepalen zijn: zset-max-ziplist-entries (standaard 128) en zset-max-ziplist-value (standaard 64).
Grootte schatting:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Toepassingen

Omdat het de geavanceerde gegevensstructuur is die het is, hebben gesorteerde sets verschillende gebruiksscenario's:

1. Het meest voor de hand liggende gebruik is als een scorebord:het bijhouden van een geordende lijst van unieke leden, gesorteerd op hun scores. Voor bijv. een leaderscorebord voor een MMORPG zoals uitgelegd in de officiële Redis-documentatie.
2. Gesorteerde sets met identieke scores worden gebruikt als indexen in Redis. Dit kan variëren van zeer eenvoudige use-cases tot zeer complexe. Redis-documentatie heeft een prachtig artikel over indexeren met behulp van gesorteerde sets.
3. Een speciaal geval van indexeren met behulp van gesorteerde sets is de GEO API voor Redis die werd geïntroduceerd in Redis 3.2.0.
4. Grootte is een overweging bij het gebruik van gesorteerde sets. Gezien de complexe backing-datastructuren zullen gesorteerde sets een relatief grotere geheugenvoetafdruk hebben. Exacte aantallen zijn afhankelijk van de aard van de dataset. Dit StackOverflow-bericht vermeldt een margenummer voor een dataset van behoorlijke omvang.

Aangezien gesorteerde sets redelijk geavanceerde gebruiksscenario's hebben, zullen we dergelijke gebruiksscenario's voor gesorteerde sets in volgende posts bespreken. Laten we voor nu een eenvoudig voorbeeld bekijken.

Gamifieer je MOOC!

In ons vorige bericht over Redis-bitmaps waren wij de ontwikkelaars die een zeer populaire MOOC ondersteunden. De begeleiders besluiten dat ze de cursus willen gamificeren met een scorebord dat de beste studenten volgt die bijdragen aan de communityposts. De studenten met het hoogste aantal geaccepteerde antwoorden op problemen die op de cursuscommunityposts zijn gepost, krijgen elke week een speciale vermelding.
Dit wordt het klassieke gebruiksvoorbeeld voor een op scores gebaseerde volgorde van unieke sleutels, ook wel de Redis-gesorteerde set genoemd. De student-ID's zijn de leden, terwijl de scores het aantal geaccepteerde antwoorden zijn. We kunnen de score bijwerken met ZINCRBY in realtime of in een achtergrondtaak die dagelijks of wekelijks kan worden uitgevoerd. Het is duidelijk dat het bijwerken van scores in realtime vereist is voor onze use-case. Voor eerste invoeging ZADD met een van de nieuwe vlaggen komt goed van pas. Om het scorebord aan de studenten weer te geven, moeten de zoekopdrachten met omgekeerd bereik worden gebruikt (ZREVRANGE enz.)

Voetnoot

Andere berichten in onze reeks Redis-gegevensstructuren:

• Sets
• Hashes
• Bitmaps