Redis
 sql >> Base de données >  >> NoSQL >> Redis

Introduction aux structures de données Redis :ensembles triés

L'ensemble trié fait partie des structures de données les plus avancées de Redis. L'ensemble trié est essentiellement une collection unique de chaînes Redis ordonnées auxquelles est associé un score numérique. L'ordre est basé sur les partitions et l'ordre lexicographique des chaînes (plus à ce sujet plus tard). Les chaînes doivent être uniques tandis que les partitions peuvent être répétées.

Outre les listes, c'est le seul ordonné structure de données dans Redis et sont préférés aux listes lorsque l'accès à n'importe quelle partie de la liste est important (contrairement à la liste qui donne accès aux fins de liste). L'insertion, la suppression et la recherche moyennes de cas dans les ensembles triés sont O(N), où N est le nombre d'éléments dans l'ensemble.

Trier

Les scores d'un ensemble trié sont des nombres à virgule flottante doubles de 64 bits compris entre -(2^) et +(2^). Les ensembles triés sont triés par leur score dans un ordre croissant. Les scores peuvent être mis à jour pour les clés existantes. Pour rompre les liens de score, les chaînes d'un ensemble trié sont classées par ordre lexicographique croissant. Dans Redis 2.8, une nouvelle fonctionnalité a été implémentée pour exploiter cet ordre lexicographique :l'interrogation de plage lexicographique. Cela a des cas d'utilisation fascinants que nous verrons plus tard.

Commandes

Les ensembles triés Redis prennent en charge une variété d'opérations allant du simple ensemble, obtention, nombre de membres aux calculs de plage lexicographiques complexes. Il y a environ 25+ opérations prises en charge. Nous en examinerons un sous-ensemble. Commençons par les plus basiques :

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

Celles-ci sont quelques-unes des opérations de base possibles sur un ensemble trié. La valeur réelle des ensembles triés brille dans sa plage en fonction des requêtes au sein de l'ensemble. Jetons un coup d'œil à eux.

# 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

D'autres commandes similaires liées à la plage sont ZREMRANGEBYRANK, ZREMRANGEBYSCORE etc.

Il existe un autre ensemble de commandes de requête d'ensemble qui ont été introduites dans Redis 2.8 :les commandes de plage lexicographique (*BYLEX). Les détails sur la façon dont les intervalles sont spécifiés pour ces commandes sont documentés ici. Pour que ces commandes fonctionnent correctement, il faut que les membres de l'ensemble trié aient un score identique. Les principales commandes permettant d'utiliser des plages lexicographiques sont ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX et ZLEXCOUNT. Voyons quelques exemples :

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"

Encore un autre ensemble de commandes pour les ensembles triés sont les opérations d'union et d'intersection.

Internes

Les ensembles triés sont implémentés sous la forme d'une structure de données double :il s'agit d'une combinaison d'un hachage et d'une liste de sauts. La partie de hachage mappe les objets aux scores et la liste de saut mappe les scores aux objets. Nous savons déjà comment les hachages sont implémentés dans Redis depuis notre précédent article. La liste de sauts garantit que les recherches sont rapides et que la plupart des opérations sont en moyenne O (log N). La liste de sauts est implémentée dans le fichier t_zset.c.

Comme la plupart des autres structures de données Redis, même les ensembles triés sont optimisés pour la taille lorsqu'ils sont petits. Les ensembles triés sont stockés uniquement sous forme de hachages jusqu'à ce qu'ils atteignent une certaine taille. Les paramètres de configuration contrôlant cette taille sont : zset-max-ziplist-entries (128 par défaut) et zset-max-ziplist-value (par défaut 64).
Estimation de la taille :https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Applications

Étant la structure de données avancée qu'elle est, les ensembles triés ont des cas d'utilisation variés :

  1. Son cas d'utilisation le plus évident est celui d'un tableau de bord :maintenir une liste ordonnée de membres uniques triés en fonction de leurs scores. Par ex. un tableau de bord des leaders pour un MMORPG comme expliqué dans la documentation officielle de Redis.
  2. Les ensembles triés avec des scores identiques sont utilisés comme index dans Redis. Cela peut aller d'un cas d'utilisation très simple à des cas très complexes. La documentation Redis contient un excellent article sur l'indexation à l'aide d'ensembles triés.
  3. Un cas particulier d'indexation à l'aide d'ensembles triés est l'API GEO pour Redis qui a été introduite dans Redis 3.2.0.
  4. La taille est un élément à prendre en compte lors de l'utilisation d'ensembles triés. Compte tenu de la complexité des structures de données de sauvegarde, les ensembles triés auront une empreinte mémoire relativement plus importante. Les nombres exacts dépendront de la nature de l'ensemble de données. Ce message StackOverflow mentionne un nombre approximatif pour un ensemble de données de taille décente.

Étant donné que les ensembles triés ont des cas d'utilisation assez avancés, nous discuterons de ces cas d'utilisation pour les ensembles triés dans les articles suivants. Pour l'instant, voyons un exemple simple.

Gamifiez votre MOOC !

Dans notre article précédent sur les bitmaps Redis, nous étions les développeurs soutenant un MOOC très populaire. Les animateurs décident qu'ils veulent gamifier le cours avec un tableau des leaders qui suit les meilleurs étudiants qui contribuent aux publications de la communauté. Les étudiants avec le plus grand nombre de réponses acceptées aux problèmes publiés sur les publications de la communauté du cours recevront une mention spéciale chaque semaine. Les identifiants étudiants seront les membres tandis que les scores seront le nombre de réponses acceptées. Nous pourrions mettre à jour le score en utilisant ZINCRBY en temps réel ou dans un travail d'arrière-plan qui peut s'exécuter quotidiennement ou hebdomadairement. Évidemment, la mise à jour des scores en temps réel est nécessaire pour notre cas d'utilisation. Pour l'insertion initiale ZADD avec l'un des nouveaux drapeaux sera utile. L'affichage du tableau de bord aux étudiants devra utiliser les requêtes de plage inverse (ZREVRANGE etc.)

Note de bas de page

Autres articles de notre série sur les structures de données Redis :

  • Ensembles
  • Hachages
  • Bitmaps