Redis
 sql >> Database >  >> NoSQL >> Redis

Introduzione alle strutture dati Redis:insiemi ordinati

Il set ordinato è alcune delle strutture di dati più avanzate in Redis. Il set ordinato è essenzialmente una raccolta univoca di stringhe Redis ordinate a cui è associato un punteggio numerico. L'ordinamento si basa sui punteggi e sull'ordine lessicografico delle stringhe (ne parleremo più avanti). Le stringhe devono essere univoche mentre le partiture potrebbero essere ripetute.

Oltre agli elenchi, è l'unico ordinato struttura dei dati in Redis e sono preferiti agli elenchi quando l'accesso a qualsiasi parte dell'elenco è importante (a differenza di List che fornisce l'accesso alle estremità dell'elenco). L'inserimento, la rimozione e la ricerca di casi medi negli insiemi ordinati sono O(N), dove N è il numero di elementi nell'insieme.

Ordinamento

I punteggi in un set ordinato sono numeri a virgola mobile a 64 bit nell'intervallo -(2^) e +(2^) inclusi. I set ordinati vengono ordinati in base al punteggio in ordine crescente. I punteggi possono essere aggiornati per le chiavi esistenti. Per rompere i pareggi di punteggio, le stringhe in un insieme ordinato vengono ordinate lessicograficamente in ordine crescente. In Redis 2.8 è stata implementata una nuova funzionalità per sfruttare questo ordinamento lessicografico:interrogazione dell'intervallo lessicografico. Questo ha affascinanti casi d'uso che vedremo più avanti.

Comandi

Gli insiemi ordinati Redis supportano una varietà di operazioni da semplici set, get, conteggio dei membri a complessi calcoli di intervalli lessicografici. Sono supportate circa 25+ operazioni. Ne esamineremo un sottoinsieme. Cominciamo con quelli di base:

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

Quelle sopra erano alcune delle operazioni di base possibili su un set ordinato. Il valore reale dei set ordinati brilla nel suo intervallo in base alle query all'interno del set. Diamo un'occhiata a loro.

# 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

Altri comandi simili relativi all'intervallo sono ZREMRANGEBYRANK, ZREMRANGEBYSCORE ecc.

C'è un'altra serie di comandi di query imposta che sono stati introdotti in Redis 2.8:i comandi dell'intervallo lessicografico (*BYLEX). I dettagli su come vengono specificati gli intervalli per questi comandi sono documentati qui. Il requisito per il corretto funzionamento di questi comandi è che i membri dell'insieme ordinato abbiano un punteggio identico. I comandi principali per operare con gli intervalli lessicografici sono ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX e ZLEXCOUNT. Vediamo un paio di esempi:

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"

Ancora un altro insieme di comandi per gli insiemi ordinati sono le operazioni di unione e intersezione.

Interni

Gli insiemi ordinati sono implementati come una doppia struttura di dati:è una combinazione di hash e skip list. La parte hash associa gli oggetti ai punteggi e l'elenco di salto associa i punteggi agli oggetti. Sappiamo già come vengono implementati gli hash in Redis dal nostro post precedente. L'elenco Ignora assicura che le ricerche siano veloci e che la maggior parte delle operazioni in media siano O(log N). La Skip list è implementata nel file t_zset.c.

Come la maggior parte delle altre strutture dati Redis, anche gli insiemi ordinati sono ottimizzati per dimensioni quando sono piccoli. I set ordinati vengono archiviati solo come hash finché non raggiungono una certa dimensione. I parametri di configurazione che controllano questa dimensione sono: zset-max-ziplist-entries (predefinito 128) e zset-max-ziplist-value (predefinito 64).
Stima delle dimensioni:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- impostato in redis

Applicazioni

Essendo la struttura di dati avanzata che è, gli insiemi ordinati hanno vari casi d'uso:

  1. Il suo caso d'uso più ovvio è come tabellone segnapunti:mantenere un elenco ordinato di membri univoci ordinati in base ai loro punteggi. Per es. un tabellone di valutazione leader per un MMORPG come spiegato nella documentazione ufficiale di Redis.
  2. I set ordinati con punteggi identici vengono utilizzati come indici in Redis. Questo può variare da casi d'uso molto semplici a casi davvero complessi. La documentazione di Redis contiene un articolo meraviglioso sull'indicizzazione tramite set ordinati.
  3. Un caso speciale di indicizzazione tramite set ordinati è l'API GEO per Redis che è stata introdotta in Redis 3.2.0.
  4. La dimensione è una considerazione quando si usano gli insiemi ordinati. Data la complessa struttura dei dati di supporto, i set ordinati avranno un footprint di memoria relativamente maggiore. I numeri esatti dipenderanno dalla natura del set di dati. Questo post di StackOverflow menziona un numero di ballpark per un set di dati di dimensioni decenti.

Dato che gli insiemi ordinati hanno casi d'uso abbastanza avanzati, discuteremo di tali casi d'uso per gli insiemi ordinati nei post successivi. Per ora, vediamo un semplice esempio.

Gamify il tuo MOOC!

Nel nostro precedente post sulle bitmap Redis, eravamo gli sviluppatori a supportare un MOOC molto popolare. I facilitatori decidono di voler ludicizzare il corso con una classifica che tiene traccia dei migliori studenti che contribuiscono ai post della community. Gli studenti con il maggior numero di risposte accettate ai problemi pubblicati nei post della community del corso riceveranno una menzione speciale ogni settimana.
Questo sarà il classico caso d'uso per un ordinamento basato sul punteggio di chiavi univoche, noto anche come set ordinato Redis. Le tessere studentesche saranno i membri mentre i punteggi saranno il numero di risposte accettate. Potremmo aggiornare il punteggio usando ZINCRBY in tempo reale o in un lavoro in background che può essere eseguito giornalmente o settimanalmente. Ovviamente per il nostro caso d'uso è necessario aggiornare i punteggi in tempo reale. Per l'inserimento iniziale ZADD con una delle nuove bandiere tornerà utile. La visualizzazione del tabellone segnapunti agli studenti dovrà utilizzare le query di intervallo inverso (ZREVRANGE ecc)

Nota a piè di pagina

Altri post nella nostra serie di strutture dati Redis:

  • Set
  • Hash
  • Bitmap