mysql - software - Ranking con millones de entradas.

mysql rank

Question

Estoy trabajando en un servidor para un juego en línea que debería poder manejar a millones de jugadores. Ahora el juego necesita tablas de clasificación y quiere poder mostrar la posición actual de un jugador y posiblemente otros jugadores cerca de la posición actual de los jugadores, así como las posiciones de los amigos de los jugadores.

Ahora he hecho esto anteriormente en MySQL y sé cómo es técnicamente posible, sin embargo, pensé que, dado que esta es una práctica común para muchos juegos en línea, ¿deben existir bibliotecas o bases de datos especialmente para este propósito?

¿Alguien puede aconsejarme qué base de datos es la mejor para este tipo de consultas y posiblemente cualquier biblioteca preexistente que ya haga mucho de este trabajo? Un servicio de terceros con acceso a API también estaría bien.

Espero obtener un buen consejo, gracias!

Editar:

Para aclarar, necesito una base de datos que pueda contener millones de entradas (hasta ahora MySQL es buena para eso) con la que puedo obtener fácilmente resultados clasificados. Por ejemplo, si obtengo una fila específica de la tabla de "tablas de clasificación", necesito saber qué rango tiene esa fila. Esta consulta debe ser inferior a 500 ms, independientemente del tamaño de la base de datos.

Alternativamente, una forma de actualizar la tabla con la información de clasificación actual estaría bien por mucho tiempo, ya que esta consulta de actualización no bloquea toda la tabla y la consulta de actualización se ejecuta en menos de 30 segundos.

¡Cualquier idea sobre qué base de datos / mecanismo o servicio de terceros usar será muy apreciada!

Answer 1

He leído recientemente un artículo sobre cómo resolver este tipo de problema con Redis. Aún podría usar MySQL como su tienda básica, pero almacenaría en caché los resultados sin clasificar en Redis y actualizaría las clasificaciones en tiempo real. El enlace se puede encontrar aquí . El último tercio del artículo trata sobre los tipos con clave, como los que tendrías con una lista de clasificación.

Answer 2

La búsqueda de un solo disco es de aproximadamente 15 ms, tal vez un poco menos con los discos de nivel de servidor. Un tiempo de respuesta de menos de 500 ms lo limita a aproximadamente 30 accesos de disco aleatorios. Eso no es mucho.

En mi pequeña computadora portátil, tengo una base de datos de desarrollo con

root@localhost [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb      |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)

y un disco de portátil lento. He creado una tabla de puntuación con

root@localhost [kris]> show create table score/G
*************************** 1. row ***************************
       Table: score
Create Table: CREATE TABLE `score` (
  `player_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `score` int(11) NOT NULL,
  PRIMARY KEY (`player_id`),
  KEY `score` (`score`)
) ENGINE=InnoDB AUTO_INCREMENT=2490316 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

con puntuaciones enteras aleatorias y valores de player_id secuenciales. Tenemos

root@localhost [kris]> select count(*)/1000/1000 as mrows from score/G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)

La base de datos mantiene el par (score, player_id) en orden de score en el score índice, ya que los datos en un índice InnoDB se almacenan en un BTREE, y el puntero de fila (puntero de datos) es el valor clave principal, por lo que la definición KEY (score) termina siendo KEY(score, player_id) internamente. Podemos probar que mirando el plan de consulta para una recuperación de puntaje:

root@localhost [kris]> explain select * from score where score = 17/G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: score
         type: ref
possible_keys: score
          key: score
      key_len: 4
          ref: const
         rows: 29
        Extra: Using index
1 row in set (0.00 sec)

Como puede ver, la key: score se usa con el Using index , lo que significa que no es necesario acceder a los datos.

La consulta de clasificación para una constante player_id dada toma exactamente 500 ms en mi computadora portátil:

root@localhost [kris]>  select p.*, count(*) as rank 
    from score as p join score as s on p.score < s.score 
   where p.player_id = 479269/G
*************************** 1. row ***************************
player_id: 479269
    score: 99901
     rank: 2074
1 row in set (0.50 sec)

Con más memoria y en una caja más rápida, puede ser más rápido, pero sigue siendo una operación comparativamente costosa, porque el plan apesta:

root@localhost [kris]> explain select p.*, count(*) as rank from score as p join score as s on p.score < s.score where p.player_id = 479269;
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref   | rows    | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
|  1 | SIMPLE      | p     | const | PRIMARY,score | PRIMARY | 4       | const |       1 |                          |
|  1 | SIMPLE      | s     | index | score         | score   | 4       | NULL  | 2097979 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
2 rows in set (0.00 sec)

Como puede ver, la segunda tabla del plan es una exploración de índice, por lo que la consulta se ralentiza linealmente con el número de jugadores.

Si desea una tabla de clasificación completa, debe dejar de lado la cláusula where, y luego obtendrá dos escaneos y tiempos de ejecución cuadráticos. Así que este plan implota completamente.

Hora de ir de procedimiento aquí:

root@localhost [kris]> set @count = 0; 
    select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ;
...
|   2353218 | 99901 | 2075 |
|   2279992 | 99901 | 2076 |
|   2264334 | 99901 | 2077 |
|   2239927 | 99901 | 2078 |
|   2158161 | 99901 | 2079 |
|   2076159 | 99901 | 2080 |
|   2027538 | 99901 | 2081 |
|   1908971 | 99901 | 2082 |
|   1887127 | 99901 | 2083 |
|   1848119 | 99901 | 2084 |
|   1692727 | 99901 | 2085 |
|   1658223 | 99901 | 2086 |
|   1581427 | 99901 | 2087 |
|   1469315 | 99901 | 2088 |
|   1466122 | 99901 | 2089 |
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
...

Debido a que este es un plan de procedimiento, es inestable:

• No puedes usar LIMIT, porque eso desplazará el contador. En su lugar tienes que descargar todos estos datos.
• Realmente no se puede ordenar. Esta cláusula ORDER BY funciona porque no se ordena, sino que utiliza un índice. Tan pronto como vea el using filesort , los valores del contador se dispararán.

Sin embargo, es la solución más cercana a lo que una base de datos NoSQL (leer: de procedimiento) hará como un plan de ejecución.

Podemos estabilizar el NoSQL dentro de una subconsulta y luego cortar la parte que nos interesa, sin embargo:

root@localhost [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where player_id = 479269;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|    479269 | 99901 | 2094 |
+-----------+-------+------+
1 row in set (0.00 sec)

root@localhost [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where rank between 2090 and 2100;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
+-----------+-------+------+
8 rows in set (0.01 sec)

La subconsulta materializará el conjunto de resultados anterior como una tabla ad-hoc llamada t, a la que luego podemos acceder en la consulta externa. Debido a que es una tabla ad-hoc, en MySQL no tendrá índice. Esto limita lo que es posible de manera eficiente en la consulta externa.

Tenga en cuenta cómo ambas consultas satisfacen su restricción de tiempo, sin embargo. Aquí está el plan:

root@localhost [kris]> set @count = 0; explain select * from ( select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ) as t where rank between 2090 and 2100/G
Query OK, 0 rows affected (0.00 sec)

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: <derived2>
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2097
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DERIVED
        table: score
         type: range
possible_keys: score
          key: score
      key_len: 4
          ref: NULL
         rows: 3750
        Extra: Using where; Using index
2 rows in set (0.00 sec)

Sin embargo, ambos componentes de la consulta (la consulta interna, DERIVED y la restricción BETWEEN externa) se volverán más lentos para los jugadores mal clasificados, y luego violarán tus restricciones de tiempo.

root@localhost [kris]> set @count = 0; select * from ( select *, @count := @count + 1 as rank from score where score >= 0 order by score desc ) as t;
...
2097152 rows in set (3.56 sec)

El tiempo de ejecución para el enfoque descriptivo es estable (depende solo del tamaño de la tabla):

root@localhost [kris]> select p.*, count(*) as rank 
   from score as p join score as s on p.score < s.score 
   where p.player_id = 1134026;
+-----------+-------+---------+
| player_id | score | rank    |
+-----------+-------+---------+
|   1134026 |     0 | 2097135 |
+-----------+-------+---------+
1 row in set (0.53 sec)

Tu llamada.

Answer 3

Ordenar millones de entradas puede parecer mucho trabajo, pero claramente no lo es. La clasificación de 10 ^ 6 entradas completamente aleatorias toma aproximadamente 3 segundos en mi computadora (solo una EeePC más antigua con una CPU Atom (primera generación, creo), 1.6GHz).

Y con un buen algoritmo de clasificación, la clasificación tiene O (n * log (n)) en el peor de los casos, por lo que no importa si tiene 10 ^ 9 o más entradas. Y la mayoría de las veces, la lista de clasificación ya estará casi ordenada (de una clasificación anterior), lo que dará como resultado un tiempo de ejecución que es más probable que sea O (n).

Entonces, deja de preocuparte por eso! El único problema real es que la mayoría de los DBMS no pueden acceder directamente a la entrada número 1000. Por lo tanto, una consulta como SELECT ... LIMIT 1000, 5 tendrá que consultar al menos 1005 entradas y omitir las primeras 1000. Pero la solución aquí es simplemente demasiado. Simplemente almacene el rank como una columna redundante de cada fila, agregue un índice y cámbielo cada 15 minutos (o cada 5 minutos, 30 minutos, 1 hora, o lo que sea más adecuado para su aplicación). Con eso, todas las consultas por rango son simplemente búsquedas de índice secundarias (sobre O (log (N))) que son extremadamente rápidas y solo tomarán unos milisegundos por consulta (la red aquí es el cuello de botella, no la base de datos).

PD: Comentaste en otra respuesta que no puedes almacenar en caché las entradas ordenadas porque son demasiado grandes para tu memoria. Suponiendo que solo almacene en caché las tuplas con dos enteros de 64 bits (¡32 bits también sería más que suficiente!), Necesitaría menos de 8 MB de memoria para almacenar 10 ^ 6 entradas. ¿Estás seguro de que no tienes suficiente RAM para eso?

Por lo tanto, no intente optimizar algo que claramente no es un cuello de botella (todavía) ...

Answer 4

Puede almacenar de forma redundante el rango de cada jugador en la tabla de jugadores para que no tenga que realizar ninguna operación de combinación. Cada vez que se vuelven a calcular las tablas de clasificación, las tablas de los jugadores también deben actualizarse.

Answer 5

Puedo pensar en dos maneras de abordar este problema:

Primer acercamiento: Actualización en lotes:

• Ordena las puntuaciones, obtén el ranking.
• Divide a los jugadores por rangos en lotes como player0-player999, player1000-player1999, etc.
• Para cada lote, elimine las entradas en la tabla existente que entren en conflicto con los nuevos datos. Esto significa eliminar las entradas existentes que pertenecen a jugadores en el lote actual o que se encuentran actualmente en el rango de rangos que se están actualizando en el lote actual. Luego, carga los datos de clasificación para el lote en la base de datos y salta al siguiente lote después de, por ejemplo, 0.1s.

Segundo enfoque: Nueva mesa

• Crea (o trunca) una nueva tabla al igual que tu tabla de clasificación existente.
• Calcula el nuevo ranking e inserta tus datos.
• Intercambia las mesas (luego de bloquearlas preferentemente). Esto debería tomar menos de un segundo.

Answer 6

Sé que esta es una vieja pregunta, pero disfruto mirando tales problemas. Dada la proporción de datos -> velocidad de consulta requerida, se pueden usar algunos trucos no tradicionales que requieren más trabajo de codificación pero que realmente pueden aumentar el rendimiento de la consulta.

Cubos de puntuación

Para empezar, debemos hacer un seguimiento de los puntajes con cubos. Queremos que la lista de categorías (¡qué gran nombre!) Sea lo suficientemente pequeña como para guardarla fácilmente en la memoria, y lo suficientemente grande como para que las categorías no sean afectadas (en términos relativos) con frecuencia. Eso nos proporciona una mayor concurrencia para evitar problemas de bloqueo.

Tendrá que decidir cómo dividir esos compartimientos en función de su carga, pero creo que desea centrarse en tener tantos compartimientos como pueda, que encajarán fácilmente en la memoria y se agregarán rápidamente.

Para acomodar esto, mi tabla score_buckets tendrá la siguiente estructura:

minscore, maxscore, usercount; PK(minscore, maxscore)

Tabla de usuario

Debemos rastrear a nuestros usuarios, y probablemente lo haremos con:

userid, score, timestamp
#(etc., etc. that we don''t care about for this part of the problem)

Para iterar eficientemente sobre esto para obtener un conteo por puntaje, necesitamos un índice en el puntaje. La marca de tiempo es solo algo que tiré para romper el empate en mi ejemplo para tener un pedido definitivo. Si no lo necesita, deshágase de él: utiliza espacio y eso afectará el tiempo de consulta. En este momento: índice (puntaje, marca de tiempo).

Inserción / Actualización / Eliminación de usuarios y sus puntuaciones

Agregar disparadores a la tabla de usuario. En la inserción:

update score_buckets sb
    set sb.usercount = sb.usercount + 1
    where sb.minscore <= NEW.score
    and sb.maxscore >= NEW.score

En la actualización

update score_buckets sb
    set sb.usercount = sb.usercount - 1
    where sb.minscore <= OLD.score
    and sb.maxscore >= OLD.score
update score_buckets sb
    set sb.usercount = sb.usercount + 1
    where sb.minscore <= NEW.score
    and sb.maxscore >= NEW.score

En la eliminación

update score_buckets sb
    set sb.usercount = sb.usercount - 1
    where sb.minscore <= OLD.score
    and sb.maxscore >= OLD.score

Rango determinante

$usersBefore = select sum(usercount)
    from score_buckets
    where maxscore < $userscore;
$countFrom = select max(maxscore)
    from score_buckets
    where maxscore < $userscore;
$rank = select count(*) from user
    where score > $countFrom
    and score <= $userscore
    and timestamp <= $userTimestamp

Notas de cierre

Realice puntos de referencia con varios números de cubos, duplicándolos o reduciéndolos a la mitad cada vez. Puede escribir rápidamente un script de duplicación / reducción a la mitad para permitirle cargar esto. Más cubos hacen menos escaneo del índice de puntuación de usuario y menos contención de bloqueo / transacción al actualizar las puntuaciones. Más cubos consume más memoria. Para elegir un número para comenzar, use 10,000 cubos. Idealmente, sus cubos cubrirán el rango completo de puntuaciones y cada compartimiento tendrá aproximadamente el mismo número de usuarios contados en él. Si puntúa el gráfico de distribución siguiendo una curva de algún tipo, haga que su distribución de cubeta siga esa curva.

La teoría de esto está relacionada con una lista de salto de dos niveles.