Introduktion till Redis Data Structures:Sorterade uppsättningar

Sorterad uppsättning är några av de mest avancerade datastrukturerna i Redis. Sorterad uppsättning är i grunden en unik samling ordnade Redis-strängar som har en numerisk poäng kopplad till dem. Ordningen baseras på partitur och strängens lexikografiska ordning (mer om detta senare). Strängarna måste vara unika medan noterna kan upprepas.

Förutom listor är det den enda beställda datastruktur i Redis och föredras framför listor när åtkomst till någon del av listan är viktig (till skillnad från List som ger tillgång till listslut). Den genomsnittliga caseinsättning, borttagning och sökning i sorterade uppsättningar är O(N), där N är antalet element i uppsättningen.

Sortering

Poängen i en sorterad uppsättning är dubbla 64-bitars flyttal i intervallet -(2^) och +(2^) inkluderade. Sorterade uppsättningar sorteras efter deras poäng i stigande ordning. Poäng kan uppdateras för befintliga nycklar. För att bryta partiturband, ordnas strängar i en sorterad uppsättning lexikografiskt stigande. I Redis 2.8 implementerades en ny funktion för att utnyttja denna lexikografiska ordning:lexikografisk intervallfråga. Detta har fascinerande användningsfall som vi kommer att se senare.

Kommandon

Redis sorterade uppsättningar stöder en mängd olika operationer från enkel set, get, medlemsantal till komplexa lexikografiska intervallberäkningar. Det finns cirka 25+ operationer som stöds. Vi kommer att titta på en delmängd av dem. Låt oss börja med de grundläggande:

# 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 ovan var några av de grundläggande operationerna som är möjliga på en sorterad uppsättning. Det verkliga värdet av de sorterade uppsättningarna lyser i dess intervall baserat på frågor inom uppsättningen. Låt oss ta en titt på dem.

# 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

Andra liknande intervallrelaterade kommandon är ZREMRANGEBYRANK, ZREMRANGEBYSCORE etc.

Det finns en annan uppsättning uppsättningsfrågekommandon som introducerades i Redis 2.8:kommandona för lexikografiskt intervall (*BYLEX). Detaljer om hur intervall specificeras för dessa kommandon dokumenteras här. Kravet för att dessa kommandon ska fungera korrekt är att medlemmarna i den sorterade uppsättningen ska ha samma poäng. De viktigaste kommandona för att arbeta med lexikografiska intervall är ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX och ZLEXCOUNT. Låt oss se ett par exempel:

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"

Ännu en uppsättning kommandon för sorterade uppsättningar är unions- och korsningsoperationerna.

Internt

Sorterade uppsättningar implementeras som en dubbel datastruktur:Det är en kombination av både en hash- och överhoppningslista. Hash-delen mappar objekt till poäng och överhoppningslistan mappar poäng till objekt. Vi vet redan hur hashar implementeras i Redis från vårt tidigare inlägg. Överhoppningslistan säkerställer att sökningar är snabba och de flesta operationer i genomsnitt är O(log N). Överhoppningslistan implementeras i filen t_zset.c.

Liksom de flesta andra Redis-datastrukturer är även sorterade uppsättningar optimerade för storlek när de är små. Sorterade uppsättningar lagras endast som hash tills de växer till en viss storlek. Konfigurationsparametrarna som styr denna storlek är: zset-max-ziplist-entries (standard 128) och zset-max-ziplist-value (standard 64).
Storleksuppskattning:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Applikationer

Eftersom den är den avancerade datastrukturen har sorterade uppsättningar olika användningsfall:

Dess mest uppenbara användningsfall är som en resultattavla:upprätthålla en ordnad lista över unika medlemmar sorterade efter deras poäng. För t.ex. en resultattavla för en MMORPG som förklaras i den officiella Redis-dokumentationen.
Sorterade uppsättningar med identiska poäng används som index i Redis. Detta kan sträcka sig från mycket enkla användningsfall till riktigt komplexa. Redis dokumentation har en underbar artikel om indexering med hjälp av sorterade uppsättningar.
Ett specialfall av indexering med hjälp av sorterade uppsättningar är GEO API för Redis som introducerades i Redis 3.2.0.
Storlek är ett övervägande när man använder sorterade uppsättningar. Med tanke på de komplexa stöddatastrukturerna kommer sorterade uppsättningar att ha ett relativt större minnesfotavtryck. Exakta siffror beror på datamängden. Det här StackOverflow-inlägget nämner ett kulnummer för en datamängd av anständig storlek.

Eftersom sorterade uppsättningar har ganska avancerade användningsfall kommer vi att diskutera sådana användningsfall för sorterade uppsättningar i efterföljande inlägg. Låt oss nu se ett enkelt exempel.

Gamifiera din MOOC!

I vårt tidigare inlägg om Redis bitmappar var vi utvecklarna som stödde en mycket populär MOOC. Handledaren bestämmer sig för att de vill gamifiera kursen med en ledartavla som spårar de bästa eleverna som bidrar till community-inläggen. Eleverna med det högsta antalet accepterade svar på problem som publicerats på kursens community-inlägg kommer att få ett speciellt omnämnande varje vecka.
Detta kommer att vara det klassiska användningsfallet för en poängbaserad beställning av unika nycklar, alias Redis sorterade set. Studentlegitimationerna kommer att vara medlemmarna medan poängen kommer att vara antalet accepterade svar. Vi kanske uppdaterar poängen med ZINCRBY i realtid eller i ett bakgrundsjobb som kan köras dagligen eller veckovis. Uppenbarligen krävs uppdatering av poäng i realtid för vårt användningsfall. För initial infogning ZADD med en av de nya flaggorna kommer väl till pass. Att visa resultattavlan för eleverna måste använda de omvända intervallfrågorna (ZREVRANGE etc)

Fotnot

Andra inlägg i vår Redis-datastrukturserie:

Set
Hashar
Bitmappar