Clasificación rápida y fiable en Datastore

Clasificación: un problema sencillo, pero muy difícil

Tomoaki Suzuki (imagen 1), ingeniero jefe de App Engine en Applibot, ha intentado resolver un problema muy habitual, pero muy difícil, al que se enfrenta cualquier servicio de juegos de gran tamaño: la clasificación.

Imagen 1: Tomoaki Suzuki, ingeniero jefe de App Engine en Applibot, Inc.

Applibot es uno de los principales proveedores de aplicaciones sociales de Japón. La singularidad de la empresa reside en sus amplios conocimientos y experiencia en la creación de servicios de juegos sociales superescalables en Google App Engine, la plataforma como servicio (PaaS) de Google. Aprovechando el potencial de la plataforma, Applibot ha conseguido captar oportunidades de negocio en el mercado de los juegos sociales, no solo en Japón, sino también en Estados Unidos. Applibot puede dar fe de ello. Legend of the Cryptids (imagen 2), uno de sus títulos más importantes, llegó al número 1 en la categoría de juegos de Apple App Store en Norteamérica en octubre del 2012. La serie Legend ha registrado 4,7 millones de descargas. Otro título, Gang Road, llegó al número 1 en el ranking de ventas totales de App Store Japón en diciembre del 2012.

Imagen 2: Legend of the Criptids, el juego número 1 en el App Store de Apple en octubre del 2012.

Estos títulos pudieron escalar sin problemas y gestionar el tráfico, que crecía de forma masiva. Applibot no tuvo que esforzarse para crear clústeres complejos de servidores virtuales o bases de datos fragmentadas. Aprovecharon la potencia de App Engine y consiguieron escalabilidad y disponibilidad de forma eficiente.

Sin embargo, mantener la clasificación de los jugadores actualizada no es un problema fácil de resolver, ni para Tomoaki ni para ningún desarrollador, sobre todo a esta escala. Los requisitos son sencillos:

  • Tu juego tiene cientos de miles de jugadores (¡o más!).
  • Cada vez que un jugador lucha contra enemigos (o realiza otras actividades), su puntuación cambia.
  • Quieres mostrar la clasificación más reciente del jugador en una página de un portal web.

¿Cómo se calcula un rango?

Imagen 3: Cada jugador tiene una puntuación. ¿Cómo calculáis su posición?

Es fácil obtener un rango si no se espera que también sea escalable y rápido. Por ejemplo, puedes ejecutar la siguiente consulta:

SELECT count(key) FROM Players WHERE Score > YourScore

Esta consulta cuenta todos los jugadores que tienen una puntuación superior a la tuya (imagen 4). Pero ¿quieres ejecutar esta consulta para cada solicitud de la página del portal? ¿Cuánto tiempo tardarías si tuvieras un millón de jugadores?

Tomoaki implementó este enfoque al principio, pero tardaba unos segundos en obtener cada respuesta. Este proceso era demasiado lento y caro, y su rendimiento empeoraba progresivamente a medida que aumentaba la escala.

Imagen 4: La forma más sencilla: escanea a todos los jugadores.

Después, Tomoaki intentó mantener los datos de ranking en Memcache. Era rápido, pero no fiable. Las entradas de Memcache se podían eliminar en cualquier momento y, en ocasiones, el propio servicio Memcache no estaba disponible. Con un servicio de ranking que dependía únicamente de los valores de clave en memoria, era difícil mantener la coherencia y la disponibilidad.

Como solución alternativa temporal, Tomoaki decidió reducir el nivel de servicio. En lugar de calcular el ranking de cada solicitud, configuró una tarea programada que analizaba y actualizaba el ranking de cada jugador una vez por hora. De esta forma, las solicitudes de la página del portal podrían obtener el rango del jugador al instante, pero podría tener hasta una hora de antigüedad.

En última instancia, Tomoaki buscaba una implementación de ranking persistente, transaccional, rápida y escalable que pudiera aceptar 300 solicitudes de actualización de puntuación por segundo y obtener un ranking para cada jugador en cientos de milisegundos. Para encontrar una solución, Tomoaki recurrió a Kaz Sato, un arquitecto de soluciones (SA) y un gestor técnico de cuentas (TAM) del equipo de Google Cloud Platform asignado a Applibot en virtud de un contrato de asistencia de nivel premium.

Una forma rápida de resolver problemas

Muchos clientes o partners de gran tamaño de Google Cloud Platform, como Applibot, tienen un contrato de asistencia de nivel premium. Con ese contrato de asistencia, además de la asistencia ininterrumpida del equipo de Asistencia al Cliente de Cloud y la asistencia empresarial del equipo de Ventas de Cloud, Google asigna un gestor técnico de cuentas a cada cliente.

El gestor de cuentas técnicas representa al cliente ante el equipo de ingeniería de Google, que es el que crea la infraestructura de nube. Los gestores de cuentas técnicas conocen en detalle el sistema y la arquitectura del cliente. Cuando se produce un caso crítico, utilizan sus conocimientos y su red como representantes de Ingeniería de Google en la empresa para resolver el problema. Los gestores de cuentas técnicas pueden derivar problemas a los arquitectos de soluciones del equipo o a los ingenieros de software del equipo de Cloud Platform. La asistencia de nivel premium es la vía rápida para encontrar una solución con Google Cloud Platform.

Kaz, el gestor de cuentas técnicas que da asistencia a Applibot, sabía que la clasificación era un problema clásico y, al mismo tiempo, difícil de resolver para cualquier servicio distribuido escalable. Empezó a revisar las implementaciones conocidas para la clasificación en Google Cloud Datastore y otros almacenes de datos NoSQL para encontrar una solución que cumpliera los requisitos de Applibot.

Búsqueda de un algoritmo O(log n)

La solución de consulta simple requiere analizar todos los jugadores con una puntuación más alta para contar el rango de un jugador. La complejidad temporal de este algoritmo es O(n), es decir, el tiempo necesario para ejecutar la consulta aumenta proporcionalmente al número de jugadores. En la práctica, esto significa que el algoritmo no se puede escalar. En su lugar, necesitamos un algoritmo O(log n) o más rápido, en el que el tiempo solo aumente de forma logarítmica a medida que crezca el número de jugadores.

Si alguna vez has cursado una asignatura de informática, recordarás que los algoritmos de árbol, como los árboles binarios, los árboles rojo-negro o los árboles B, pueden tener una complejidad temporal de O(log n) para encontrar un elemento. Los algoritmos de árbol también se pueden usar para calcular un valor agregado de un intervalo de elementos, como el recuento, el máximo o el mínimo y la media, manteniendo los valores agregados en cada nodo de rama. Con esta técnica, se puede implementar un algoritmo de clasificación con un rendimiento de O(log n).

Kaz encontró una implementación de código abierto de un algoritmo de clasificación basado en árboles para Datastore, escrita por un ingeniero de Google: la biblioteca de clasificación de Google Code Jam.

Esta biblioteca basada en Python expone dos métodos:

  • SetScore para definir la puntuación de un jugador.
  • FindRank para obtener la posición de una puntuación determinada.

A medida que se crean y actualizan los pares de jugador y puntuación con el método SetScore, la biblioteca de clasificación de Code Jam crea un árbol N-ario1. Por ejemplo, consideremos un árbol terciario que pueda contar el número de jugadores con puntuaciones entre 0 y 80 (figura 5). La biblioteca almacena el nodo raíz, que contiene tres números, como una entidad. Cada número corresponde al número de jugadores con puntuaciones en los subintervalos 0-26, 27-53 y 54-80, respectivamente. El nodo raíz tiene un nodo secundario para cada intervalo, que a su vez contiene tres valores para los jugadores de los subintervalos del subintervalo. La jerarquía necesita cuatro niveles para almacenar el número de jugadores de 81 valores de puntuación diferentes.

Imagen 5: Obtener el rango de una puntuación en un árbol terciario.

Para determinar la posición de un jugador que tiene una puntuación de 30, la biblioteca solo necesita leer cuatro entidades (los nodos rodeados por la línea discontinua del diagrama) para sumar el número de jugadores que tienen una puntuación superior a 30. Con 22 jugadores a la "derecha" en cuatro entidades, el rango del jugador es el 23.

Del mismo modo, una llamada a SetScore solo tiene que actualizar cuatro entidades. Aunque tengas un gran número de puntuaciones diferentes, el acceso a Datastore solo aumentará a O(log n) y no se verá afectado por el número de jugadores. En la práctica, la biblioteca de clasificación de Code Jam usa 100 (en lugar de 3) como número predeterminado de valores por nodo, por lo que solo se necesita acceder a dos (o tres, si el intervalo de puntuación es superior a 100.000) entidades.

Kaz usó la popular herramienta de pruebas de carga Apache JMeter para realizar una prueba de carga en la biblioteca de clasificación de Code Jam y confirmó que la biblioteca responde rápido. Tanto SetScore como FindRank pueden completar sus tareas en cientos de milisegundos mediante el algoritmo de árbol N-ario, que funciona con una complejidad temporal de O(log n).

La escalabilidad de los límites de actualizaciones simultáneas

Sin embargo, durante las pruebas de carga, Kaz descubrió una limitación crítica en la biblioteca de clasificación de Code Jam. Su escalabilidad en términos de rendimiento de las actualizaciones era bastante baja. Cuando aumentó la carga a tres actualizaciones por segundo, la biblioteca empezó a devolver errores de reintento de transacción. Era evidente que la biblioteca no podía satisfacer el requisito de Applibot de 300 actualizaciones por segundo. Solo podía gestionar aproximadamente el 1% de ese volumen.

¿A qué se debe? El motivo es el coste de mantener la coherencia del árbol. En Datastore, debes usar un grupo de entidades para asegurar una coherencia sólida al actualizar varias entidades en una transacción. Consulta el artículo Equilibrio entre la coherencia sólida y la coherencia final con Google Cloud Datastore. La biblioteca de clasificación de Code Jam usa un solo grupo de entidades para contener todo el árbol y, de esta forma, asegurar la coherencia de los recuentos en los elementos del árbol.

Sin embargo, un grupo de entidades de Datastore tiene una limitación de rendimiento. Datastore solo admite aproximadamente una transacción por segundo en un grupo de entidades. Además, si se modifica el mismo grupo de entidades en transacciones simultáneas, es probable que fallen y deban volver a intentarse. La biblioteca de clasificación de Code Jam es coherente, transaccional y bastante rápida, pero no admite un gran volumen de actualizaciones simultáneas.

Solución del equipo de Datastore: agregación de trabajos

Kaz recordó que un ingeniero de software del equipo de Datastore había mencionado una técnica para obtener un rendimiento mucho mayor que una actualización por segundo en un grupo de entidades. Para ello, se puede agregar un lote de actualizaciones en una sola transacción en lugar de ejecutar cada actualización como una transacción independiente. Sin embargo, como la transacción incluye un gran número de actualizaciones, cada transacción tarda más tiempo, lo que aumenta la posibilidad de que se produzcan conflictos con transacciones simultáneas.

En respuesta a la solicitud de Kaz, el equipo de Datastore empezó a debatir este problema y nos recomendó que usáramos la agregación de trabajos, uno de los patrones de diseño que se usan con Megastore.

Megastore es la capa de almacenamiento subyacente de Datastore y gestiona la coherencia y la transaccionalidad de los grupos de entidades. El límite de una actualización por segundo procede de esa capa. Como Megastore se usa de forma generalizada en varios servicios de Google, los ingenieros han ido recopilando y compartiendo prácticas recomendadas y patrones de diseño en la empresa para crear un sistema escalable y coherente con este almacén de datos NoSQL.

La idea básica de la agregación de trabajos es usar un solo subproceso para procesar un lote de actualizaciones. Como solo hay un subproceso y una transacción abiertos en el grupo de entidades, no se produce ningún error de transacción debido a actualizaciones simultáneas. Puedes encontrar ideas similares en otros productos de almacenamiento, como VoltDb y Redis.

Sin embargo, el patrón de agregación de trabajos tiene un inconveniente: solo usa un subproceso para agregar todas las actualizaciones, lo que limita la velocidad a la que puede enviar las actualizaciones a Datastore. Por lo tanto, era importante determinar si Job Aggregation podía cumplir el requisito de Applibot de 300 actualizaciones por segundo.

Agregación de trabajos por cola de extracción

Siguiendo los consejos del equipo de Datastore, Kaz escribió un código de prueba de concepto que combina el patrón de agregación de trabajos con la biblioteca de clasificación de Code Jam. La prueba de concepto tiene los siguientes componentes:

  • Frontend acepta las solicitudes SetScore de los usuarios y las añade como tareas a una cola de extracción.
  • Cola de extracción: recibe y almacena las solicitudes de actualización de SetScore del frontend.
  • Backend: ejecuta un bucle infinito con un solo subproceso que extrae las solicitudes de actualización de la cola y las ejecuta con la biblioteca de clasificación de Code Jam.

La prueba de concepto crea una cola de extracción, que es un tipo de cola de tareas de App Engine que permite a los desarrolladores implementar uno o varios trabajadores que consuman las tareas añadidas a la cola. La instancia de backend tiene un solo subproceso en un bucle infinito que sigue extrayendo tantas tareas como sea posible (hasta 1000) de la cola. El hilo transfiere cada solicitud de actualización a la biblioteca de clasificación de Code Jam, que las ejecuta como un lote en una sola transacción. La transacción puede estar abierta durante un segundo o más, pero, como hay un solo subproceso que controla la biblioteca y Datastore, no hay contención ni problemas de modificación simultánea.

La instancia de backend se define como un módulo, una función de App Engine que permite a los desarrolladores definir una instancia de aplicación con varias características. En esta prueba de concepto, la instancia de backend se define como una instancia de escalado manual. Solo se ejecuta una instancia de este tipo en un momento dado.

Kaz probó la carga de la prueba de concepto con JMeter. Confirmó que la prueba de concepto podía procesar 200 solicitudes SetScore por segundo, con lotes de entre 500 y 600 actualizaciones por transacción. La agregación de empleos funciona

Partición de colas para un rendimiento estable

Pero Kaz pronto se dio cuenta de que había otro problema. Mientras seguía ejecutando la prueba durante varios minutos, observó que el rendimiento de la cola de extracción fluctuaba de vez en cuando (figura 6). En concreto, cuando siguió añadiendo solicitudes a la cola con 200 tareas por segundo durante varios minutos, la cola dejó de pasar tareas al backend de repente y la latencia de cada tarea aumentó considerablemente.

Imagen 6: Fluctuación del rendimiento de la cola de extracción.

Kaz consultó al equipo de Task Queue para saber por qué ocurría esto. Según el equipo de colas de tareas, este es un comportamiento conocido de la implementación actual de colas de extracción, que depende de Bigtable como capa de persistencia. Cuando una tablet de Bigtable crece demasiado, se divide en varias tablets. Mientras la tablet se está dividiendo, las tareas no se entregan, lo que provoca la fluctuación del rendimiento cuando la cola recibe tareas a un ritmo elevado. El equipo de colas de tareas está trabajando para mejorar estas características de rendimiento.

Michael Tang, arquitecto de soluciones, recomendó una solución alternativa que utiliza la fragmentación de colas. En lugar de usar solo una cola, sugirió distribuir la carga en varias colas. Cada cola se puede almacenar en un servidor de tablets de Bigtable diferente para minimizar el efecto de una división de tablets y mantener una alta tasa de procesamiento de tareas. Mientras una cola procesa una división, las demás siguen funcionando y la fragmentación reduce la carga de cada cola, por lo que la división de una tablet se produce con menos frecuencia.

El bucle de la instancia de backend mejorada ejecuta el siguiente algoritmo:

  1. Concede SetScore tareas de 10 colas.
  2. Llama al método SetScores con las tareas.
  3. Elimina las tareas alquiladas de las colas.

En el paso 1, cada cola proporciona hasta 1000 tareas, y cada tarea contiene el nombre de un jugador y una puntuación. Después de agregar todos los pares de jugador y puntuación en un diccionario, en el paso 2 se pasa el lote de actualizaciones al método SetScores de la biblioteca de clasificación de Code Jam, que abre una transacción para almacenarlos en Datastore. Si no se ha producido ningún error al ejecutar el método, en el paso 3 se eliminan las tareas arrendadas de las colas.

Si se produce un error o un cierre inesperado del bucle o de la instancia de backend, las tareas de actualización permanecen en las colas de tareas para que se puedan procesar cuando se reinicie la instancia. En un sistema de producción, puede que tengas otro backend que actúe como un watchdog en modo de espera, listo para tomar el control si falla la primera instancia.

Solución propuesta: 300 actualizaciones por segundo de forma continuada2

En la figura 7 se muestra el resultado de la prueba de carga de la implementación final de la prueba de concepto con la fragmentación de colas. Minimiza de forma eficaz las fluctuaciones del rendimiento en las colas y puede mantener 300 actualizaciones por segundo durante varias horas. Con una carga habitual, cada actualización se aplica a Datastore en cuestión de segundos después de recibir la solicitud.

Imagen 7: Gráfico de rendimiento de la solución

Esta solución cumple todos los requisitos originales de Applibot:

  • Escalable para gestionar decenas de miles de jugadores.
  • Persistente y coherente, ya que todas las actualizaciones se ejecutan en transacciones de Datastore.
  • Es lo suficientemente rápido como para gestionar 300 actualizaciones por segundo.

Con los resultados de las pruebas de carga y el código de la prueba de concepto, Kaz presentó la solución a Tomoaki y a otros ingenieros de Applibot. Tomoaki tiene previsto incorporar la solución a su sistema de producción, espera reducir la latencia de actualización de la información de la clasificación de una hora a unos segundos y quiere mejorar drásticamente la experiencia de usuario.

Resumen del árbol de clasificación con agregación de empleo

La solución propuesta tiene varias ventajas y un inconveniente:

Ventajas:

  • Rápida: la llamada FindRank tarda unos cientos de milisegundos o menos.
  • Rápido: SetScore solo envía una tarea, que el backend procesa en unos segundos.
  • Consistencia fuerte y persistencia en Datastore.
  • Las clasificaciones son precisas.
  • Se puede adaptar a cualquier número de jugadores.

Desventaja:

  • El rendimiento tiene una limitación (aproximadamente 300 actualizaciones por segundo con la implementación actual).

Como esta solución usa el patrón de agregación de trabajos, se basa en un solo subproceso para agregar todas las actualizaciones. Se necesita más trabajo o complejidad para alcanzar un rendimiento superior a 300 actualizaciones por segundo con la potencia de CPU actual de las instancias de App Engine y el rendimiento de Datastore.

Solución más escalable con árbol fragmentado

Si necesitas una frecuencia de actualización aún mayor, es posible que tengas que fragmentar el árbol de clasificación. Crearías varias implementaciones del sistema anterior: un conjunto de colas, cada una de las cuales controlaría un módulo backend que actualizaría su propio árbol de clasificación.

Por lo general, no es necesario ni se espera que coordines los árboles. En el caso más sencillo, cada actualización de SetScore se envía aleatoriamente a una cola. Con tres árboles de este tipo, cada uno con su propio grupo de entidades de Datastore y servidor backend, el rendimiento de las actualizaciones sería tres veces mayor. La contrapartida es que FindRank debe consultar cada árbol de clasificación para obtener la clasificación de una puntuación y, a continuación, sumar la clasificación de cada árbol para encontrar la clasificación real, lo que llevará un poco más de tiempo. El tiempo de consulta de FindRank se puede reducir considerablemente si las entidades se almacenan en Memcache.

Es similar al conocido método de usar contadores fragmentados: cada contador se incrementa de forma independiente y la suma total se calcula solo cuando el cliente lo necesita.

Por ejemplo, con tres árboles, FindRank(865) podría encontrar los tres rangos 124, 183 y 156, lo que indica que cada árbol contiene el número respectivo de puntuaciones superiores a 865. El número total calculado de puntuaciones superiores a 865 es 124 + 183 + 156 = 463.

Este enfoque no funciona con todos los tipos de algoritmos distribuidos, pero, como la clasificación es fundamentalmente un problema de recuento conmutativo, debería funcionar con problemas de clasificación de gran volumen.

Soluciones más escalables con enfoques aproximados

Si tu aplicación requiere escalabilidad más que precisión en las clasificaciones y puede tolerar un cierto nivel de imprecisión o aproximación, puedes elegir enfoques estocásticos como los siguientes:

Todos estos enfoques aproximados son variantes de una misma idea: ¿cómo se comprime el almacenamiento de la información de clasificación permitiendo una cierta degradación de la precisión de la clasificación?

Contenedores con consulta global es una solución alternativa propuesta por el equipo de Datastore y Alex Amies, un gestor de cuentas técnicas. Alex implementó una prueba de concepto basada en la idea del equipo de Datastore y llevó a cabo un análisis de rendimiento exhaustivo. Demostró que Buckets with Global Query es una solución de clasificación escalable con una degradación mínima de la precisión de la clasificación y que podría ser adecuada para aplicaciones que requieran un mayor rendimiento que la biblioteca de clasificación de Code Jam. Consulta el apéndice para ver una descripción detallada y los resultados de las pruebas.

El método de recuento con pérdidas y Frugal Streaming son los llamados algoritmos online y algoritmos de streaming, en los que puedes usar un almacenamiento en memoria muy pequeño para calcular una estimación estocástica de los mejores jugadores a partir de un flujo de pares de jugador-puntuación. Estos algoritmos serían adecuados para aplicaciones que requieren una latencia muy baja y un ancho de banda muy alto, como miles de actualizaciones por segundo, con una precisión y una cobertura de los resultados de ranking más limitadas. Por ejemplo, si quieres tener un panel de control en tiempo real que muestre las 100 palabras clave más escritas en un flujo de una red social, estos algoritmos te ayudarán.

Conclusión

La clasificación es un problema clásico, pero difícil de resolver si necesitas que el algoritmo sea escalable, coherente y rápido. En este artículo, hemos descrito cómo los gestores de cuentas técnicas de Google trabajaron estrechamente con el cliente y los equipos de ingeniería de Google para abordar el reto y proporcionar una solución que pudiera reducir la latencia de actualización de la clasificación de una hora a unos segundos. Los patrones de diseño descubiertos en el proceso (agregación de trabajos y partición de colas) también se podrían aplicar a problemas habituales en otros diseños de sistemas basados en Datastore que requieran cientos de actualizaciones por segundo con una coherencia sólida.

Notas

  1. La biblioteca de clasificación de Code Jam toma un parámetro llamado "factor de ramificación" que especifica cuántas puntuaciones tendrá cada entidad. De forma predeterminada, la biblioteca usa 100 como parámetro. En este caso, las puntuaciones comprendidas entre 0 y 9999 se almacenarán en 100 entidades como elementos secundarios del nodo raíz. Si necesitas gestionar una gama más amplia de puntuaciones, puedes cambiar el factor de ramificación a un valor más alto para optimizar el número de accesos a entidades.
  2. Las cifras de rendimiento que se describen en este artículo son valores de muestra de referencia y no garantizan el rendimiento absoluto de App Engine, Datastore u otros servicios.

Apéndice: Contenedores con la solución de consulta global

Como se ha mencionado en la sección Cómo obtener una clasificación, es caro consultar la base de datos para cada solicitud de clasificación. Este método alternativo obtiene periódicamente el recuento de todas las puntuaciones, calcula la clasificación de las puntuaciones seleccionadas y proporciona esos puntos de datos para calcular las clasificaciones de jugadores concretos. El intervalo total de puntuaciones se divide en "grupos". Cada grupo se caracteriza por un subintervalo de puntuaciones y el número de jugadores con puntuaciones en ese intervalo. A partir de esos datos, se puede encontrar una aproximación del rango de cualquier puntuación. Estos contenedores son similares al nodo de nivel superior del árbol de clasificación, pero, en lugar de descender a nodos más detallados, este algoritmo solo interpola dentro de un contenedor.

La obtención de la posición por parte de los usuarios del frontend se ha desacoplado del cálculo de la posición en los segmentos del backend para minimizar el tiempo necesario para encontrar una posición. Cuando se solicita el rango de un jugador, se busca el contenedor adecuado en función de su puntuación. El segmento incluye un límite de rango superior y un recuento de los jugadores que pertenecen a él. Se usa la interpolación lineal en los contenedores para estimar la clasificación de los jugadores en los contenedores. En nuestras pruebas, hemos podido obtener la clasificación de un jugador en menos de 400 milisegundos de forma constante para un viaje de ida y vuelta HTTP completo. El coste del método FindRank no depende del número de jugadores de la población.

Calcular la posición de una puntuación determinada

Imagen 8: Distribución de las puntuaciones en contenedores.

Se registran el recuento y el rango más alto (es decir, el rango más alto posible en este contenedor) de cada contenedor. En el caso de las puntuaciones que se encuentran entre los límites inferior y superior de un contenedor, usamos la interpolación lineal para estimar el rango. Por ejemplo, si el jugador tiene una puntuación de 60, buscamos el intervalo [50, 74] y usamos el recuento (número de jugadores o puntuaciones del intervalo) (42) y el rango más alto (5) para calcular el rango del jugador con esta fórmula:

    rank = 5  + (74 - 60)*42/(74 - 50) =  30

Calcular el recuento y el intervalo de cada contenedor

En segundo plano, mediante un trabajo cron o una cola de tareas, se calculan y se guardan los recuentos de cada contenedor iterando sobre todos los contenedores. A esto lo llamamos consulta global, ya que calcula los parámetros necesarios para estimar las clasificaciones examinando las puntuaciones de todos los jugadores. A continuación se muestra un código de Python de ejemplo para hacerlo por las puntuaciones del intervalo [low_score, high_score] de cada contenedor.

next_upper_rank = 1
for b in buckets:
  count = GetCountInRange(b.low_score, b.high_score)
  b.count = count
  b.upper_rank = next_upper_rank
  b.put()
  next_upper_rank += count

El método GetCountInRange() cuenta a cada jugador con puntuaciones dentro del intervalo cubierto por el segmento. Como Datastore mantiene un índice ordenado de las puntuaciones de los jugadores, este recuento se puede calcular de forma eficiente.

Cuando necesitamos encontrar la posición de un jugador concreto, podemos usar el código que se muestra a continuación.

b = GetBucketByScore(score)
rank = RankInBucket(b, score)
return rank + b.upper_rank - 1

El método GetBucketByScore(score) obtiene el contenedor que contiene la puntuación proporcionada. El método RankInBucket() realiza una estimación del rango dentro del contenedor. El rango del jugador es la suma del rango más alto del grupo y el rango dentro del grupo específico que incluye la puntuación del jugador. Tenemos que restar 1 al resultado porque el rango más alto del primer segmento será 1, y el rango del mejor jugador de un segmento específico también será 1.

Los segmentos se almacenan tanto en Datastore como en Memcache. Para calcular el rango, lee los contenedores de Memcache (o Datastore, si Memcache no tiene los datos). En nuestra propia implementación de este algoritmo, hemos usado la biblioteca de cliente NDB de Python, que usa Memcache para almacenar en caché los datos almacenados en Datastore.

Como los contenedores (u otros métodos) se usan para representar los datos de forma compacta, las clasificaciones que se obtienen no son exactas. Los puestos de un contenedor se aproximan mediante interpolación lineal. Se podrían usar otros métodos de interpolación más precisos para obtener una mejor aproximación dentro del contenedor, como una fórmula de regresión.

Coste

El coste de encontrar un rango y actualizar la puntuación de un jugador es O(1), es decir, independiente del número de jugadores.

El coste de la tarea de consulta global es O(Players) * frecuencia de actualización de la caché.

El coste de calcular los datos del segmento en el trabajo de backend también está relacionado con el número de segmentos, ya que se realiza una consulta de recuento para cada segmento. La consulta count se optimiza para usar una consulta de solo claves, pero, aun así, se debe recuperar la lista completa de claves.

Ventajas

Este método es muy rápido tanto para actualizar la puntuación de un jugador como para encontrar el puesto de una puntuación. Aunque los resultados se basan en un trabajo en segundo plano, si la puntuación de un jugador cambia, el rango mostrará inmediatamente un cambio en la dirección adecuada. Esto se debe a la interpolación utilizada en el segmento.

Como el cálculo del rango más alto de un contenedor se realiza en segundo plano con una tarea programada, las puntuaciones del jugador se pueden actualizar sin necesidad de mantener sincronizados los datos del contenedor. Por lo tanto, el rendimiento de la actualización de las puntuaciones de los jugadores no está limitado por este enfoque.

Inconvenientes

Hay que tener en cuenta el tiempo necesario para contar las puntuaciones de todos los jugadores, calcular las clasificaciones globales y actualizar los contenedores. En nuestras pruebas, con una población de diez millones de jugadores, el tiempo fue de 8 minutos y 34 segundos para nuestro sistema de prueba en App Engine. Este proceso es más rápido que las horas que se tardaría en calcular la clasificación de cada jugador, pero la contrapartida es la aproximación de las puntuaciones de cada contenedor. Por el contrario, el algoritmo de árbol calcula los "intervalos de contenedor" (el nodo superior del árbol) de forma incremental cada pocos segundos, pero tiene una mayor complejidad de implementación y un rendimiento limitado.

En todos los casos, el tiempo de FindRank también depende de la rapidez con la que se recuperen los datos (nodos de árbol o de contenedor) de Memcache. Si los datos se expulsan de Memcache, se deben volver a obtener de Datastore y almacenar en caché para las solicitudes FindRank posteriores.

Precisión

La precisión del método de los contenedores depende del número de contenedores, del rango del jugador y de la distribución de las puntuaciones. En la figura 9 se muestran los resultados de nuestro estudio sobre la precisión de las estimaciones de rango con diferentes números de contenedores.

Imagen 9: variación de la precisión en función del número de contenedores.

Las pruebas se realizaron con una población de 10.000 jugadores con puntuaciones distribuidas de forma uniforme en el intervalo [0-9999]. El error relativo es de aproximadamente el 1% incluso con solo 5 contenedores.

La precisión disminuye en el caso de los jugadores con una clasificación alta, principalmente porque la ley de los grandes números no se aplica cuando solo se tienen en cuenta las puntuaciones más altas. En muchos casos, puede ser recomendable usar un algoritmo más preciso para mantener las clasificaciones de los 1000 o 2000 jugadores con las puntuaciones más altas. El problema se reduce considerablemente, ya que hay menos jugadores a los que hacer un seguimiento y la tasa agregada de actualizaciones es menor.

En la prueba anterior, el uso de números aleatorios distribuidos uniformemente, donde la función de distribución acumulada es lineal, favorece el uso de la interpolación lineal en el segmento, pero la interpolación en los segmentos funciona bien con cualquier distribución densa de puntuaciones. En la figura 10 se muestra el rango estimado y el real de una distribución de puntuaciones aproximadamente normal.

Imagen 10: Clasificación estimada con distribución normal

En este experimento, se usó una población de 100 jugadores para probar la precisión con un conjunto de datos pequeño. Cada puntuación se ha generado calculando la media de cuatro números aleatorios entre 0 y 100, lo que se aproxima a una distribución normal de las puntuaciones. El ranking estimado se ha calculado mediante el método de consulta global con interpolación lineal en 10 segmentos. Se puede observar que los resultados son muy buenos incluso en conjuntos de datos muy pequeños y distribuciones no uniformes.