Update: https://github.com/soywiz/smrr-server

Hace relativamente poco me he enfrentado al problema de tener que montar un ranking masivo en tiempo real. El problema es el siguiente: tenemos un conjunto de usuarios con una puntuación asociada y queremos obtener su posición en una lista ordenada por esa puntuación. Nos interesa también poder hacer paginado y acceder a los usuarios dada una posición de una forma óptima.

Inicialmente pensé en una query similar a esta:

SELECT COUNT(*) FROM user WHERE score>(SELECT score FROM user WHERE id=USER_ID) ORDER BY score DESC;

Parecía una buena forma. La subquery es constante y si se coloca un índice en score, pensaba que el asunto sería instantáneo. Sin embargo en el momento en que pensé esa query no tuve en cuenta un detalle muy importante: en los árboles binarios de búsqueda normales para contar los elementos hay que recorrerse el iterador completo. Por lo que esa query tenía tiempo lineal. Si pides un elemento al principio, será rápido, pero si pides un elemento al final en una tabla de 10 millones de registros, vas a ver cómo se tira la vida. Y al fin y al cabo, los índices en las bases de datos acaban siendo eso: árboles binarios. Tiempo de inserción, borrado y búsqueda logarítmicos. Pero para calcular cantidades de rangos tiempo lineal.

Una forma de solucionar el problema de la posición en el ranking es añadir una columna a la tabla que indique la posición en el ranking. Y periódicamente ordenar la tabla entera por ranking y actualizar dicha columna. Eso podría ser suficiente si nos conformásemos con un ranking actualizado cada X tiempo. Yo necesitaba un ranking en tiempo real que fuese MUY rápido.


Descartando ya el uso de bases de datos, empecé a pensar en estructuras de datos para montar esto. Me interesaba un árbol binario de búsqueda que se comportase muy bien tanto en el mejor como en el peor de los casos. Así que opté por un RedBlackTree que se encarga de mantener el árbol balanceado. Partiendo de esta estructura básica, me interesaba poder obtener la posición en la lista ordenada de un nodo en como mucho tiempo logarítmico. Y también obtener un nodo a partir de su posición.

Se me ocurrió lo siguiente (nótese que es fácil que esto ya esté inventado, pero como no sé cómo se llama voy a usar la terminología que he usado mientras lo planteaba):

Por cada nodo, además de mantener una referencia al padre, al hijo menor, al hijo mayor, el valor y el color de los RedBlackTree añado dos atributos más: número de hijos menores y número de hijos mayores.

Modificaciones en el algoritmo:

Inserción:

  • Cada vez que se inserta un elemento será una hoja, su número de hijos tanto a la izquierda como a la derecha empiezan siendo 0.
  • Se actualiza toda la ascendencia añadiendo un +1 al lado correspondiente en función de donde provenga el hijo.

Borrado:

  • Cuando se borra un elemento, se eliminan todos los hijos y se resta a la ascendencia el número de hijos a la izquierda y a la derecha sumados en el lado correspondiente en función de donde provenga el hijo.

Rotaciones. En los árboles balanceados hay dos operaciones adicionales para rebalancear el árbol (rotación a la izquierda y rotación a la derecha):

  • En la rotación a la izquierda: el conteo de hijos mayores del nodo actual se define como el conteo de hijos menores del nodo de la derecha. El conteo de hijos menores del nodo de la derecha se define como la suma de los hijos menores y mayores del nodo actual + 1.
  • En la rotación a la derecha: el conteo de hijos menores del nodo actual se define como el conteo de hijos mayores del nodo de la izquierda. El conteo de hijos mayores del nodo de la izquierda se define como la suma de los hijos menores y mayores del nodo actual + 1.

Con estas modificaciones mantenemos actualizados los datos de conteos de hijos.

Nuevas operaciones:

Obtener posición de nodo en la lista ordenada. Obtener un nodo a partir de una posición:

Hay dos formas para obtener el número de nodos menores que uno determinado. Recorriéndose el árbol desde el nodo a comprobar, o recorriéndose el árbol desde el nodo raíz hasta el nodo que nos interese. De ambas formas podemos conseguir un tiempo logarítmico (dependiendo de la altura del árbol, que al estar balanceado y por las propiedades de los RedBlack podría ser como máximo 2 * log(N) siendo N el número de elementos.

Para obtener el número de elementos menores de un nodo cualquiera empezando por el nodo raíz recorriéndolo hacia abajo:

  • Empezando por el nodo raíz que en la implementación que he usado era un nodo dummy con un vínculo al primer elemento como hijo menor. Nos guardamos en una variable el conteo de elementos de todo el set que será la posición del elemento en la lista ordenada, que en este caso es el conteo de hijos menores del nodo raíz, pero que podría ser la suma del conteo de hijos menores y mayores + 1 si el nodo raíz fuese el primer nodo del árbol.
  • Si nos vamos hacia el nodo de la izquierda:
  • A la posición en la lista ordenada temporal se resta el número de hijos mayores + 1 del nodo de la izquierda.
  • Si nos vamos hacia el nodo de la derecha:
  • A la posición en la lista ordenada temporal se suma el número de hijos menores + 1 del nodo de la derecha.
  • En cuanto encontremos el nodo que nos interesa encontrar, terminamos y devolvemos la posición calculada. Se puede tratar de buscar el nodo tanto por posición como por orden. Si la posición o el orden es menor, se va hacia la izquierda, si la posición o el orden es mayor, se va hacia la derecha.

Para obtener el número de elementos menores de un nodo cualquiera empezando por dicho nodo recorriéndolo hacia arriba:

  • Recorriendo hacia arriba desde el nodo actual, se suma a un conteo de hijos que empieza siendo 0, el número de hijos menores + 1 siempre y cuando el nodo iterado sea menor o igual al nodo del que intentamos contar.

Operaciones derivadas:

  • Para obtener el número de elementos de un rango dado un nodo inicial y un nodo final basta con restar la posición del nodo final a la posición del nodo inicial.
  • A partir de un rango hacer un “skip” de una cantidad concreta de posiciones. Crear un nuevo rango localizando el nodo que hay en la posición del nodo inicial + número de elementos a saltar (ambas cosas se calculan con las dos operaciones que hemos visto).
  • A partir de un rango hacer un “limit” de una cantidad concreta de elementos. Aunque basta con parar la iteración al obtener los elementos deseados sin empeorar el rendimiento, se puede obtener el rango ya delimitado haciendo una operación similar al skip, pero recalculando el nodo final.

En la implementación de esta modificación me he basado en la implementación del RedBlackTree incluida en phobos, la librería estándar del lenguaje D: http://digitalmars.com/d/2.0/phobos/std_container.html

Para ver cómo se ha implementado:

Aquí el código fuente con un ejemplo comparando tiempos de conteo lineales sin los stats y logarítmicos con lo que acabo de exponer aquí hecho en D:

http://code.google.com/p/dutils/source/browse/trunk/rbtree_with_stats/rbtree_with_stats.d?spec=svn132&r=132

Propuesta de modificación del RedBlackTree de D para incluir de forma opcional mediante templates estas características:

http://d.puremagic.com/issues/show_bug.cgi?id=6133