Introduktion til Redis-datastrukturer:Sorterede sæt

Sorteret sæt er nogle af de mest avancerede datastrukturer i Redis. Sorteret sæt er i bund og grund en unik samling af ordnede Redis-strenge, der har en numerisk score tilknyttet. Ordningen er baseret på partiturer og strengens leksikografiske rækkefølge (mere om dette senere). Strengene skal være unikke, mens noderne kan gentages.

Udover lister er det den eneste ordnede datastruktur i Redis og foretrækkes frem for Lister, når adgang til enhver del af listen er vigtig (i modsætning til List, som giver adgang til ender af listen). Den gennemsnitlige sagsindsættelse, fjernelse og søgning i sorterede sæt er O(N), hvor N er antallet af elementer i sættet.

Sortering

Scorerne i et sorteret sæt er dobbelte 64-bit flydende komma-tal i området -(2^) og +(2^) inkluderet. Sorterede sæt sorteres efter deres score i stigende rækkefølge. Resultaterne kan opdateres for eksisterende nøgler. For at bryde nodebånd, er strenge i et sorteret sæt ordnet leksikografisk stigende rækkefølge. I Redis 2.8 blev en ny funktion implementeret for at udnytte denne leksikografiske rækkefølge:leksikografisk rækkeviddeforespørgsel. Dette har fascinerende use cases, som vi vil se senere.

Kommandoer

Redis sorterede sæt understøtter en række operationer fra simpelt sæt, get, medlemsantal til komplekse leksikografiske rækkeviddeberegninger. Der er omkring 25+ operationer understøttet. Vi vil se på en delmængde af dem. Lad os starte med de grundlæggende:

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

Ovenstående var nogle af de grundlæggende handlinger, der var mulige på et sorteret sæt. Den reelle værdi af de sorterede sæt skinner i dets område baseret på forespørgsler i sættet. Lad os tage et kig 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

Andre lignende områderelaterede kommandoer er ZREMRANGEBYRANK, ZREMRANGEBYSCORE osv.

Der er et andet sæt sæt forespørgselskommandoer, der blev introduceret i Redis 2.8:kommandoerne leksikografisk område (*BYLEX). Detaljer om, hvordan intervaller er angivet for disse kommandoer, er dokumenteret her. Kravet for, at disse kommandoer fungerer korrekt, er, at medlemmerne af det sorterede sæt skal have en identisk score. De vigtigste kommandoer til at arbejde med leksikografiske områder er ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX og ZLEXCOUNT. Lad os se et par eksempler:

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"

Endnu et andet sæt kommandoer til sorterede sæt er unions- og skæringsoperationerne.

Internal

Sorterede sæt er implementeret som en dobbelt datastruktur:Det er en kombination af både en hash- og springliste. Hash-delen kortlægger objekter til scoringer, og overspringslisten kortlægger point til objekter. Vi ved allerede, hvordan hashes implementeres i Redis fra vores tidligere indlæg. Overspringslisten sikrer, at søgninger er hurtige, og de fleste operationer i gennemsnit er O(log N). Overspringslisten er implementeret i filen t_zset.c.

Som de fleste andre Redis-datastrukturer er selv Sorterede sæt optimeret til størrelse, når de er små. Sorterede sæt gemmes kun som hashes, indtil de vokser til en vis størrelse. Konfigurationsparametrene, der styrer denne størrelse, er: zset-max-ziplist-entries (standard 128) og zset-max-ziplist-value (standard 64).
Størrelsesvurdering:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Applikationer

Da den er den avancerede datastruktur, den er, har sorterede sæt forskellige anvendelsesmuligheder:

1. Den mest oplagte anvendelse er som en resultattavle:opretholdelse af en ordnet liste over unikke medlemmer sorteret efter deres resultater. For f.eks. en lederresultattavle for en MMORPG som forklaret i den officielle Redis-dokumentation.
2. Sorterede sæt med identiske scorer bruges som indeks i Redis. Dette kan spænde fra meget simple use case til virkelig komplekse. Redis dokumentation har en vidunderlig artikel om indeksering ved hjælp af sorterede sæt.
3. Et særligt tilfælde af indeksering ved hjælp af sorterede sæt er GEO API for Redis, der blev introduceret i Redis 3.2.0.
4. Størrelse er en overvejelse, når du bruger sorterede sæt. I betragtning af de komplekse datastrukturer vil sorterede sæt have et relativt større hukommelsesfodaftryk. Præcise tal vil afhænge af arten af ​​datasættet. Dette StackOverflow-indlæg nævner et ballpark-nummer for et datasæt af anstændig størrelse.

Da sorterede sæt har ret avancerede use cases, vil vi diskutere sådanne use cases for sorterede sæt i efterfølgende indlæg. Lad os nu se et simpelt eksempel.

Gamify din MOOC!

I vores tidligere indlæg om Redis bitmaps var vi udviklerne, der understøttede en meget populær MOOC. Facilitatorerne beslutter, at de vil gamify kurset med en ledertavle, der sporer de bedste elever, der bidrager til fællesskabsposterne. De studerende med det højeste antal accepterede svar på problemer, der er opslået på kursets community-indlæg, vil modtage en særlig omtale hver uge.
Dette vil være den klassiske brugssag for en scorebaseret bestilling af unikke nøgler aka Redis-sorterede sæt. Studenter-id'erne vil være medlemmerne, mens scoringerne vil være antallet af accepterede svar. Vi opdaterer muligvis partituret ved hjælp af ZINCRBY i realtid eller i et baggrundsjob, der kan køre dagligt eller ugentligt. Det er klart, at opdatering af scores i realtid er påkrævet for vores use case. Til første indsættelse ZADD med et af de nye flag vil komme godt med. Visning af resultattavlen for eleverne skal bruge forespørgslerne i omvendt rækkevidde (ZREVRANGE osv.)

Fodnote

Andre indlæg i vores Redis-datastrukturserie:

• Sæt
• Hashes
• Bitmaps