sql >> Base de Datos >  >> NoSQL >> Redis

Introducción a las estructuras de datos de Redis:conjuntos ordenados

Sorted Set es una de las estructuras de datos más avanzadas de Redis. El conjunto ordenado es esencialmente una colección única de cadenas Redis ordenadas que tienen una puntuación numérica asociada. El orden se basa en las puntuaciones y el orden lexicográfico de las cadenas (más sobre esto más adelante). Las cadenas deben ser únicas, mientras que las puntuaciones pueden repetirse.

Además de Listas, es el único ordenado estructura de datos en Redis y se prefieren a las Listas cuando el acceso a cualquier parte de la lista es importante (a diferencia de la Lista que brinda acceso a los extremos de la lista). La inserción, eliminación y búsqueda promedio de casos en conjuntos ordenados son O(N), donde N es el número de elementos en el conjunto.

Clasificación

Las puntuaciones en un conjunto ordenado son números dobles de punto flotante de 64 bits en el rango -(2^) y +(2^) incluidos. Los conjuntos ordenados se ordenan por su puntuación en orden ascendente. Las puntuaciones se pueden actualizar para las claves existentes. Para desempatar las puntuaciones, las cadenas de un conjunto ordenado se ordenan lexicográficamente en orden ascendente. En Redis 2.8, se implementó una nueva característica para explotar este ordenamiento lexicográfico:consulta de rango lexicográfico. Esto tiene casos de uso fascinantes que veremos más adelante.

Comandos

Los conjuntos ordenados de Redis admiten una variedad de operaciones, desde conjuntos simples, obtención, recuento de miembros hasta cálculos complejos de rango lexicográfico. Hay alrededor de 25+ operaciones compatibles. Veremos un subconjunto de ellos. Comencemos con los 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"

Las anteriores son algunas de las operaciones básicas posibles en un conjunto ordenado. El valor real de los conjuntos ordenados brilla en su rango en función de las consultas dentro del conjunto. Echemos un vistazo a ellos.

# 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

Otros comandos relacionados con rangos similares son ZREMRANGEBYRANK, ZREMRANGEBYSCORE, etc.

Hay otro conjunto de comandos de consulta establecidos que se introdujeron en Redis 2.8:los comandos de rango lexicográfico (*BYLEX). Los detalles de cómo se especifican los intervalos para estos comandos se documentan aquí. El requisito para que estos comandos funcionen correctamente es que los miembros del conjunto ordenado tengan una puntuación idéntica. Los principales comandos para operar con rangos lexicográficos son ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX y ZLEXCOUNT. Veamos un par de ejemplos:

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"

Otro conjunto de comandos para conjuntos ordenados son las operaciones de unión e intersección.

Internos

Los conjuntos ordenados se implementan como una estructura de datos dual:es una combinación de hash y lista de omisión. La parte hash asigna objetos a puntajes y la lista de saltos asigna puntajes a objetos. Ya sabemos cómo se implementan los hash en Redis por nuestra publicación anterior. La lista Omitir asegura que las búsquedas sean rápidas y que la mayoría de las operaciones en promedios sean O (log N). La lista de omisión se implementa en el archivo t_zset.c.

Al igual que la mayoría de las otras estructuras de datos de Redis, incluso los conjuntos ordenados están optimizados para el tamaño cuando son pequeños. Los conjuntos ordenados se almacenan solo como hashes hasta que crecen hasta cierto tamaño. Los parámetros de configuración que controlan este tamaño son: zset-max-ziplist-entries (predeterminado 128) y zset-max-ziplist-value (64 por defecto).
Estimación del tamaño:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- configurado en redis

Aplicaciones

Siendo la estructura de datos avanzada que es, los conjuntos ordenados tienen varios casos de uso:

  1. Su caso de uso más obvio es como marcador:mantener una lista ordenada de miembros únicos ordenados por sus puntajes. Por ej. un marcador de líderes para un MMORPG como se explica en la documentación oficial de Redis.
  2. Los conjuntos ordenados con puntajes idénticos se usan como índices en Redis. Esto puede variar desde casos de uso muy simples hasta casos realmente complejos. La documentación de Redis tiene un maravilloso artículo sobre la indexación mediante conjuntos ordenados.
  3. Un caso especial de indexación mediante conjuntos ordenados es la API GEO para Redis que se introdujo en Redis 3.2.0.
  4. El tamaño es una consideración cuando se usan conjuntos ordenados. Dadas las complejas estructuras de datos de respaldo, los conjuntos ordenados tendrán una huella de memoria relativamente mayor. Los números exactos dependerán de la naturaleza del conjunto de datos. Esta publicación de StackOverflow menciona un número aproximado para un conjunto de datos de tamaño decente.

Dado que los conjuntos ordenados tienen casos de uso bastante avanzados, discutiremos tales casos de uso para conjuntos ordenados en publicaciones posteriores. Por ahora, veamos un ejemplo simple.

¡Gamifica tu MOOC!

En nuestra publicación anterior sobre mapas de bits de Redis, éramos los desarrolladores que respaldaban un MOOC muy popular. Los facilitadores deciden que quieren gamificar el curso con una tabla de clasificación que rastrea a los mejores estudiantes que contribuyen a las publicaciones de la comunidad. Los estudiantes con el mayor número de respuestas aceptadas a los problemas publicados en las publicaciones de la comunidad del curso recibirán una mención especial cada semana.
Este será el caso de uso clásico para un orden basado en puntaje de claves únicas, también conocido como el conjunto ordenado de Redis. Las identificaciones de los estudiantes serán los miembros, mientras que las puntuaciones serán el número de respuestas aceptadas. Podríamos actualizar la puntuación usando ZINCRBY en tiempo real o en un trabajo de fondo que puede ejecutarse diariamente o semanalmente. Obviamente, se requiere actualizar las puntuaciones en tiempo real para nuestro caso de uso. Para inserción inicial ZADD con una de las nuevas banderas te vendrá bien. Mostrar el marcador a los estudiantes deberá utilizar las consultas de rango inverso (ZREVRANGE etc.)

Nota al pie

Otras publicaciones en nuestra serie de estructuras de datos de Redis:

  • Conjuntos
  • Hashes
  • Mapas de bits