Antes de seguir leyendo abre este enlace en otra ventana y sube el volumen. Bien, podemos continuar.

 pokemon go

Si a estas alturas tengo que explicarte de qué va este fenómeno de masas es que probablemente has pasado las últimas semanas encerrado en un bote de mayonesa. Tan solo en USA alcanzó 25 millones de usuarios y probablemente se recordará como el momento fundacional de un subgénero, tal y como pasó con Angry Birds.

En cualquier caso la mecánica del juego presenta al usuario un mapa real con una serie de puntos, llamadas pokeparadas, a los que tiene que desplazarse físicamente para poder recoger objetos o capturar pokémon. Desplazarse. Moverse. Caminar. Un concepto extrañamente similar al de hacer ejercicio. Para jugones. Sorprendente.

También pueden aparecer pokémon en otros puntos inesperados, y existe la posibilidad de quedar en unos lugares señalados como gimnasios con otros jugadores para que los pokémon que hemos recogido peleen entre ellos.

La infraestructura de Pokémon Go está basada en el cloud, así que nos ha parecido un ejercicio divertido explicar cómo puedes montar una arquitectura que soporte los requerimientos del juego y este número de usuarios simultáneos. Niantic (la empresa que hay detrás del producto) utiliza la plataforma de Google pero yo tengo mucha más experiencia con AWS, así que voy a elegir esta última para el ejercicio.

 pokemon go

Capítulo I: El mapa de Pokémon Go

Obteniendo información geográfica

Vamos a trabajar sobre el mundo real por lo que necesitamos datos de cartografía. Podemos conseguirlos en el proyecto OSM.

El fichero incluye una representación de buena parte del planeta en forma de grafo: una serie de nodos (puntos sobre la superficie) que en ocasiones se pueden agrupar formando caminos y que se clasifican mediante el uso de tags.

Tenemos que determinar las pokeparadas y para ello analizaremos el fichero que hemos descargado. Según el formato que usemos vamos a necesitar procesar hasta 1TB de información así que mejor paralelizamos la ejecución de esta parte desde el principio. El objetivo es recorrer los datos del fichero localizando los llamados POI (points of interest) mediante los tags asociados y guardar sus posiciones como pokeparadas.

La forma más eficiente de llevarlo a cabo es subir el fichero a S3: es un servicio de almacenamiento especialmente fiable. Por ejemplo, si subes diez millones de ficheros en él, al cabo de diez mil años se habría perdido de media uno. De media. Y no tienes 10.000 años.

Una vez tengamos los datos subidos, programamos un pequeño MapReduce que vaya leyendo elemento por elemento para detectar aquellos cuyos tags indican que son interesantes y emitimos sus coordenadas como resultado.

EMR es un servicio que nos proporciona un cluster Hadoop gestionado. Utilizando spot instances ejecutaremos nuestro pequeño programita simultáneamente en un buen número de máquinas. Por ejemplo, ahora mismo podemos lanzar 40 m3.xlarge con un descuento del 80% en la región de Virginia y pedirle a EMR que se encargue de distribuir el trabajo, reintentar los errores, reponer los nodos defectuosos, etc. En unos minutos deberíamos tener el trabajo completado.

pokeparada

 

Soportando centenares de miles de queries por segundo

¿Dónde guardamos las pokeparadas? Incluso si tenemos en cuenta todo el planeta el volumen de información no es especialmente alto, podría gestionarlo cualquier base de datos tradicional. Pero hay una característica que es crítica: el throughput, es decir, la cantidad de peticiones simultáneas que podemos atender y que puede superar los centenares de miles de lecturas por segundo. Y la escalabilidad de nuestro sistema es crítica, así que vamos a descartar una base de datos relacional.

Elegimos DynamoDB. Es una base de datos gestionada con lo que no es necesario que te preocupes por su mantenimiento o alta disponibilidad. Su característica más importante es que puede ser tan rápida como necesites, solo depende de cuánto quieras pagar por ella. A cambio no podemos seguir pensando en términos clásicos relacionales pero esto en nuestro caso no es un problema.

Cuando modelas datos con DynamoDB tienes que tener en cuenta que en las consultas siempre debes indicar una clave de partición, es decir, que para recuperar información tienes que utilizar como mínimo una condición de igualdad sobre un campo. Si lo haces, recuperar todos los datos que contengan el mismo valor de esa clave es muy eficiente. Tenemos que ser astutos y conseguir que todas las pokeparadas que se encuentren cerca se puedan obtener en el menor número de operaciones posibles, y para eso tienes que saber un poquito más de lo habitual sobre sistemas de coordenadas.

En general nos hemos acostumbrado a utilizar latitud y longitud para indicar un lugar en el planeta, y en realidad la mayoría de nosotros no hemos dedicado mucho tiempo a preguntarnos a qué se refieren esos dos números. Simplemente tenemos una vaga noción sobre que la latitud es 0 en el ecuador y alcanza +90 o -90 grados conforme te acercas a los polos, mientras que la longitud toma una línea arbitraria que pasa por Greenwich como origen y va desde -180 a +180. Si queremos montar un clon de Pokémon Go, tenemos que aprender algo más sobre esto.

En particular está bastante claro que a un usuario solo debemos enviarle los datos correspondientes a la zona del planeta en la que se encuentra. Una forma práctica de solucionar esto es dividir el planeta en pequeños trocitos de (pongamos) un kilómetro cuadrado. Determinamos qué trocitos necesita el usuario para visualizar su mapa según la posición en la que se encuentra y enviaremos solo esta información.

Conseguir esto con lat/lon es muy complicado: un grado de longitud ni siquiera representa la misma distancia a lo largo de todo el planeta porque mientras más te acercas a los polos más cerca está la línea de un meridiano de la siguiente.

Pero existen muchas otras maneras de dar coordenadas (las distintas proyecciones del planeta) y convertir entre ellas es fácil. Una de muy popular se llama UTM y usándola es trivial dar un nombre a cada uno de los pequeños trocitos de los que hablábamos.

Por ejemplo, las coordenadas en WGS84 de Plaza Catalunya en Barcelona son “41.3866, 2.17" que se convierten en “31T 4582014 430605" para UTM. El cuadrado de un kilómetro de lado que le corresponde se puede identificar por “31T 4582 430" simplemente eliminando dígitos al final de cada número.

Así que nuestra tabla en DynamoDB quedaría así:

string cuadradoUtm;
number numero;
number latitude;
number longitude;
number tipo;

Cuando el usuario se encuentra en la plaza podemos recuperar todas las pokeparadas indicando su cuadrado (y quizá algún cuadrado adyacente si se encuentra en el borde). Eficiente. Siguiente tema.

Tenemos que saber qué pokémon y objetos hay en ellas, claro. Idealmente podríamos añadir estos datos en cada parada dentro del propio registro (item, en terminología DynamoDB) pero esto implica que cada cierto tiempo habría que actualizarlas todas. Esta operación es muy costosa en este tipo de base de datos así que vamos a optar por una alternativa más sofisticada.

¿Ves ese atributo tipo que hemos añadido? Si has jugado al Dungeons & Dragons recordarás las tablas de eventos: listas de sucesos interesantes que pueden ocurrirte cuando llegas a un lugar. En el juego de rol se elegía uno tirando un dado pero en este caso queremos que todos los jugadores que pasen por el mismo sitio encuentren al mismo bicho. Para explicar mejor este punto, aquí tienes el primer trocito de una tabla así:

Número Contenido
0 Growlithe
1 Alakazam
2 Cámara
3 Mew
4 Hiperpoción
etc. etc.

Es decir, si tiramos un dado y sale un 4 entonces hemos encontrado una hiperpoción. Pero necesitamos ser más deterministas y para ello podemos aprovecharnos de que el reloj de los teléfonos está habitualmente sincronizado con el de nuestros servidores.

Tomamos la hora como epoch time, la transformamos aplicando MD5 para generar un número pseudorandom y usamos ese número para elegir el contenido de la pokeparada.

Por ejemplo, ahora mismo son las 11:36:48 del 4/8/2016. Reducimos la precisión a la hora (para que no cambie el resultado a cada segundo) y nos quedan las 11:00. El epoch time correspondiente es el 1470308400 y el MD5 de este número es ca1955b07f828f4727d27994100b41a0. Nos quedamos con la última cifra, que es 0, tanto en decimal como en hexadecimal. Miramos en nuestra supuesta tabla de eventos y vemos que aparece un Growlithe.

Personalmente llenaría toda esa tabla de Growlithe, para que saliese siempre el mismo: nunca hay suficientes. En general si quieres que en ese tipo de pokeparada aparezcan más pokémon del mismo tipo solo tienes que repetir su valor en distintos slots de la tabla de eventos.

Obviamente cuando un usuario interactúe de cualquier manera (por ejemplo, capturando a nuestro Grow) hay que comprobar la coherencia entre los datos que envía y el estado de la pokeparada en ese momento o estaremos abriendo la puerta a los tramposos, hackers, listillos y demás gente divertida que pulula por internet. Probablemente ese grupo te incluya a ti, no nos engañemos.

pokemon go

Dibujando mapas

¡Bien! Casi tenemos listo el tema de los mapas, excepto la parte en que se refiere a dibujarlos. Pero amigos y amigas, vamos a subcontratarla: afortunadamente para nosotros osmbuildings es capaz de dibujar mapas 3D basados en el mismo dataset que hemos utilizado para generar las pokeparadas así que nos podemos ahorrar el trabajo.

Sirviendo los datos

Nada especialmente novedoso aquí: el usuario utiliza R53 para recuperar la dirección de un ELB que reparte sus peticiones entre la flota gestionada por un autoscaling group que cuida de las instancias EC2, encargadas de implementar el API de acceso a la información atacando nuestro DynamoDB.

Próximamente

En el siguiente capítulo veremos cómo podemos gestionar el inmenso flujo de datos que puede llegar a generar una aplicación de este estilo, en tiempo real. No te lo pierdas.

TAGS: aws, AWS Lambda, Pokemon Go

speech-bubble-13-icon Created with Sketch.
Comentarios

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*
*