Introdução às estruturas de dados do Redis:conjuntos ordenados

Além das Listas, é a única ordenada estrutura de dados no Redis e são preferidos às listas quando o acesso a qualquer parte da lista é importante (ao contrário da lista que fornece acesso aos finais da lista). A média de inserção, remoção e busca de casos em conjuntos ordenados é O(N), onde N é o número de elementos no conjunto.

Classificação

As pontuações em um conjunto classificado são números duplos de ponto flutuante de 64 bits no intervalo -(2^) e +(2^) incluídos. Os conjuntos ordenados são ordenados por sua pontuação em ordem crescente. As pontuações podem ser atualizadas para as chaves existentes. Para quebrar os empates de pontuação, as strings em um conjunto classificado são ordenadas lexicograficamente em ordem crescente. No Redis 2.8, um novo recurso foi implementado para explorar essa ordenação lexicográfica:consulta de intervalo lexicográfico. Isso tem casos de uso fascinantes que veremos mais tarde.

Comandos

Os conjuntos ordenados do Redis suportam uma variedade de operações, desde simples definir, obter, contagem de membros até cálculos complexos de intervalo lexicográfico. Existem cerca de 25+ operações suportadas. Veremos um subconjunto deles. Vamos começar pelos básicos:

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

As acima foram algumas das operações básicas possíveis em um conjunto ordenado. O valor real dos conjuntos ordenados brilha em seu intervalo com base nas consultas dentro do conjunto. Vamos dar uma olhada neles.

# 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

Outros comandos semelhantes relacionados ao intervalo são ZREMRANGEBYRANK, ZREMRANGEBYSCORE etc.

Há outro conjunto de comandos set query que foram introduzidos no Redis 2.8:os comandos de intervalo lexicográfico (*BYLEX). Os detalhes de como os intervalos são especificados para esses comandos estão documentados aqui. O requisito para que esses comandos funcionem corretamente é que os membros do conjunto classificado tenham uma pontuação idêntica. Os principais comandos para operar com intervalos lexicográficos são ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX e ZLEXCOUNT. Vejamos alguns exemplos:

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"

Outro conjunto de comandos para conjuntos ordenados são as operações de união e interseção.

Internos

Os conjuntos ordenados são implementados como uma estrutura de dados dupla:é uma combinação de uma lista de hash e de pular. A parte de hash mapeia objetos para pontuações e a lista de pular mapeia pontuações para objetos. Já sabemos como os hashes são implementados no Redis em nosso post anterior. A lista Ignorar garante que as pesquisas sejam rápidas e que a maioria das operações em média seja O(log N). A lista Skip é implementada no arquivo t_zset.c.

Como a maioria das outras estruturas de dados do Redis, mesmo os conjuntos classificados são otimizados para tamanho quando são pequenos. Os conjuntos ordenados são armazenados apenas como hashes até atingirem um determinado tamanho. Os parâmetros de configuração que controlam esse tamanho são: zset-max-ziplist-entries (padrão 128) e zset-max-ziplist-value (padrão 64).
Estimativa de tamanho:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Aplicativos

Sendo a estrutura de dados avançada que é, conjuntos ordenados têm casos de uso variados:

1. Seu caso de uso mais óbvio é como um placar:manter uma lista ordenada de membros únicos classificados por suas pontuações. Por exemplo um placar de líderes para um MMORPG, conforme explicado na documentação oficial do Redis.
2. Conjuntos classificados com pontuações idênticas são usados ​​como índices no Redis. Isso pode variar de casos de uso muito simples a casos realmente complexos. A documentação do Redis tem um artigo maravilhoso sobre indexação usando conjuntos ordenados.
3. Um caso especial de indexação usando conjuntos classificados é a API GEO para Redis que foi introduzida no Redis 3.2.0.
4. Tamanho é uma consideração ao usar conjuntos ordenados. Dadas as complexas estruturas de dados de apoio, os conjuntos classificados terão um espaço de memória relativamente maior. Os números exatos dependerão da natureza do conjunto de dados. Esta postagem do StackOverflow menciona um número aproximado para um conjunto de dados de tamanho decente.

Uma vez que conjuntos ordenados têm casos de uso bastante avançados, discutiremos esses casos de uso para conjuntos ordenados em posts subsequentes. Por enquanto, vejamos um exemplo simples.

Gamifique seu MOOC!

Em nossa postagem anterior sobre bitmaps do Redis, éramos os desenvolvedores que davam suporte a um MOOC muito popular. Os facilitadores decidem que querem gamificar o curso com um quadro de líderes rastreando os melhores alunos que contribuem para as postagens da comunidade. Os alunos com o maior número de respostas aceitas para problemas postados nas postagens da comunidade do curso receberão uma menção especial toda semana.
Este será o caso de uso clássico para uma ordenação baseada em pontuação de chaves exclusivas, também conhecida como conjunto de classificação Redis. Os IDs dos alunos serão os membros, enquanto as pontuações serão o número de respostas aceitas. Podemos atualizar a pontuação usando ZINCRBY em tempo real ou em um trabalho em segundo plano que pode ser executado diariamente ou semanalmente. Obviamente, a atualização de pontuações em tempo real é necessária para nosso caso de uso. Para inserção inicial ZADD com uma das novas bandeiras será útil. A exibição do placar para os alunos precisará utilizar as consultas de intervalo reverso (ZREVRANGE etc)

Nota de rodapé

Outras postagens em nossa série de estruturas de dados Redis:

• Conjuntos
• Hashes
• Bitmaps