Redis
 sql >> Datenbank >  >> NoSQL >> Redis

Einführung in Redis-Datenstrukturen:Sortierte Sätze

Sorted Set ist eine der fortschrittlichsten Datenstrukturen in Redis. Ein sortierter Satz ist im Wesentlichen eine eindeutige Sammlung geordneter Redis-Strings, denen eine numerische Punktzahl zugeordnet ist. Die Reihenfolge basiert auf Partituren und der lexikografischen Reihenfolge der Saiten (dazu später mehr). Die Zeichenfolgen müssen eindeutig sein, während die Partituren wiederholt werden können.

Neben Listen ist es das einzige geordnete Datenstruktur in Redis und werden Listen vorgezogen, wenn der Zugriff auf einen beliebigen Teil der Liste wichtig ist (im Gegensatz zu Listen, die Zugriff auf die Enden der Liste bieten). Das durchschnittliche Einfügen, Entfernen und Suchen von Fällen in sortierten Mengen ist O(N), wobei N die Anzahl der Elemente in der Menge ist.

Sortierung

Die Punktzahlen in einem sortierten Satz sind doppelte 64-Bit-Gleitkommazahlen im Bereich -(2^) und +(2^) enthalten. Sortierte Sätze werden nach ihrer Punktzahl in aufsteigender Reihenfolge sortiert. Scores können für vorhandene Schlüssel aktualisiert werden. Um Partiturbindungen zu lösen, werden Saiten in einem sortierten Satz in lexikografisch aufsteigender Reihenfolge geordnet. In Redis 2.8 wurde eine neue Funktion implementiert, um diese lexikografische Reihenfolge auszunutzen:lexikografische Bereichsabfrage. Dies hat faszinierende Anwendungsfälle, die wir später sehen werden.

Befehle

Sortierte Redis-Sets unterstützen eine Vielzahl von Operationen, von einfachen Set-, Get-, Member-Count- bis hin zu komplexen lexikografischen Bereichsberechnungen. Es werden etwa 25+ Operationen unterstützt. Wir werden uns eine Teilmenge davon ansehen. Beginnen wir mit den grundlegenden:

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

Die obigen waren einige der grundlegenden Operationen, die auf einem sortierten Satz möglich sind. Der wahre Wert der sortierten Mengen leuchtet in ihrem Bereich basierend auf Abfragen innerhalb der Menge. Werfen wir einen Blick darauf.

# 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 ähnliche bereichsbezogene Befehle sind ZREMRANGEBYRANK, ZREMRANGEBYSCORE usw.

Es gibt eine weitere Gruppe von Set-Query-Befehlen, die in Redis 2.8 eingeführt wurden:die Befehle für den lexikografischen Bereich (*BYLEX). Einzelheiten dazu, wie Intervalle für diese Befehle angegeben werden, sind hier dokumentiert. Voraussetzung für die korrekte Funktion dieser Befehle ist, dass die Mitglieder des sortierten Satzes eine identische Punktzahl haben. Die wichtigsten Befehle zum Arbeiten mit lexikografischen Bereichen sind ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX und ZLEXCOUNT. Sehen wir uns ein paar Beispiele an:

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"

Ein weiterer Satz von Befehlen für sortierte Mengen sind die Vereinigungs- und Schnittmengenoperationen.

Interna

Sortierte Mengen werden als duale Datenstruktur implementiert:Es ist eine Kombination aus Hash und Skip-Liste. Der Hash-Teil ordnet Objekte Scores zu und die Skip-Liste ordnet Scores Objekten zu. Wie Hashes in Redis implementiert werden, wissen wir bereits aus unserem vorherigen Beitrag. Die Skip-Liste stellt sicher, dass Suchvorgänge schnell sind und die meisten Operationen im Durchschnitt O(log N) sind. Die Skip-Liste ist in der Datei t_zset.c implementiert.

Wie die meisten anderen Redis-Datenstrukturen sind auch sortierte Sätze auf Größe optimiert, wenn sie klein sind. Sortierte Sätze werden nur als Hashes gespeichert, bis sie eine bestimmte Größe erreicht haben. Die Konfigurationsparameter, die diese Größe steuern, sind: zset-max-ziplist-entries (Standard 128) und zset-max-ziplist-value (Standard 64).
Größenschätzung:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Anwendungen

Als fortgeschrittene Datenstruktur haben sortierte Mengen verschiedene Anwendungsfälle:

  1. Der offensichtlichste Anwendungsfall ist die Verwendung als Scoreboard:Pflege einer geordneten Liste eindeutiger Mitglieder, sortiert nach ihren Scores. Für z.B. ein Leader-Scoreboard für ein MMORPG, wie in der offiziellen Redis-Dokumentation erklärt.
  2. Sortierte Sätze mit identischen Punktzahlen werden als Indizes in Redis verwendet. Dies kann von sehr einfachen bis hin zu sehr komplexen Anwendungsfällen reichen. Die Redis-Dokumentation enthält einen wunderbaren Artikel über die Indizierung mit sortierten Sätzen.
  3. Ein Sonderfall der Indizierung mit sortierten Sätzen ist die GEO-API für Redis, die in Redis 3.2.0 eingeführt wurde.
  4. Größe ist eine Überlegung, wenn sortierte Sätze verwendet werden. Angesichts der komplexen Hintergrunddatenstrukturen haben sortierte Sätze einen relativ größeren Speicherbedarf. Genaue Zahlen hängen von der Art des Datensatzes ab. Dieser StackOverflow-Beitrag erwähnt eine ungefähre Zahl für einen anständig großen Datensatz.

Da sortierte Mengen ziemlich fortgeschrittene Anwendungsfälle haben, werden wir solche Anwendungsfälle für sortierte Mengen in späteren Beiträgen diskutieren. Sehen wir uns zunächst ein einfaches Beispiel an.

Gamifizieren Sie Ihren MOOC!

In unserem vorherigen Beitrag zu Redis-Bitmaps waren wir die Entwickler, die ein sehr beliebtes MOOC unterstützten. Die Moderatoren entscheiden, dass sie den Kurs mit einer Bestenliste gamifizieren möchten, die die besten Studenten verfolgt, die zu den Community-Beiträgen beitragen. Die Schüler mit der höchsten Anzahl akzeptierter Antworten auf Probleme, die in den Beiträgen der Kursgemeinschaft gepostet wurden, erhalten jede Woche eine besondere Erwähnung.
Dies wird der klassische Anwendungsfall für eine punktzahlbasierte Reihenfolge eindeutiger Schlüssel sein, auch bekannt als das sortierte Redis-Set. Die Schülerausweise sind die Mitglieder, während die Punktzahlen die Anzahl der akzeptierten Antworten darstellen. Wir könnten die Punktzahl mit ZINCRBY aktualisieren in Echtzeit oder in einem Hintergrundjob, der täglich oder wöchentlich ausgeführt werden kann. Offensichtlich ist für unseren Anwendungsfall die Aktualisierung von Ergebnissen in Echtzeit erforderlich. Zum erstmaligen Einfügen ZADD mit einer der neuen Flaggen wird sich als nützlich erweisen. Um den Schülern die Anzeigetafel anzuzeigen, müssen die umgekehrten Bereichsabfragen verwendet werden (ZREVRANGE usw.)

Fußnote

Andere Posts in unserer Reihe Redis-Datenstrukturen:

  • Sätze
  • Hashes
  • Bitmaps