Hackathon WCC Ensenada 2017 diseño del servidor multithread

El pasado 6 de octubre participé en la 4ta edición del We Can Code Hackathon, organizado por Advancio. Esta es una competencia donde la meta es crear algún producto interesante donde demuestres tus habilidades de programación o electrónica. La competencia toma lugar en un lapso de 24 horas, empiezas a las 5:00 pm del viernes y expones tu producto a las 5:00 pm del sábado. Como podrán imaginar no dormimos ni nos bañamos en ese lapso de tiempo, sólo nos dedicamos a trabajar en nuestra idea.

Este año mis amigos y yo decidimos participar con un video juego multijugador en tiempo real para dispositivos móviles fuertemente inspirado por el estilo de Wario Ware.

Un demo de la funcionalidad del juego.

Tuvimos el honor de ser merecedores del premio de 2do lugar. Esta es la segunda vez que somos premiados en los WCC.

Mi aportación al equipo fue el desarrollo del servidor, el sistema que mantiene a los diferentes jugadores en sincronía y coordina el estado del juego.

El camino a diseñar este sistema me presentó varios desafíos interesantes y me pareció que sería bueno relatar el camino que seguí para llegar a la solución. Si les interesaría saber más sobre las tecnicalidades y el diseño de los minijuegos en sí, estoy seguro que mi amigo Javier Rizzo tendrá un blog al respecto.

Diseño General

Comencemos desde el principio. En cuanto decidimos que haríamos este juego lo primero que hicimos fue hacer un pequeño diagrama con el ciclo de vida de la aplicación.

Una pantalla de inicio donde esperas hasta que todos los demás se conecten, una pantalla donde estas jugando, un scoreboard con las vidas de cada jugador y una pantalla de victoria o de derrota.

Una meta del diseño era hacer que estas transiciones entre las diferentes pantallas fueran realizadas al mismo tiempo entre todos los jugadores.

Para implementar esta funcionalidad se nos ocurrieron 2 estrategias generales:

  1. La implementación que primero se nos ocurrió fue hacer que el cliente simplemente le avise al servidor cuando esté listo para empezar el siguiente juego y de ahí mandar muchísimas peticiones al servidor preguntando “¿ya están todos listos?”. Esta implementación tiene varias desventajas. Consumiría muchos datos al estar mande y mande peticiones. También tendría un retraso considerable causado por tantas peticiones. Suena sencillo, pero no es tan trivial de implementar para el cliente.
  2. La otra forma que eventualmente se nos ocurrió es hacer que cada cliente mande una petición HTTP al servidor avisando que está listo para empezar. El servidor no responde esta petición inmediatamente, sino que espera hasta recibir la petición de todos los jugadores y en ese momento le responde la petición a todos los jugadores al mismo tiempo, el cliente usa esta respuesta como señal de que ya todos están listos y empieza el juego. Esta es la forma por la que optamos implementar el servidor.

Además de que la segunda opción disminuye muchísimo el consumo de datos, la razón más importante de por qué quisimos implementar el servicio de esta manera es que vuelve trivial el código que se tiene que escribir en el lado del cliente. Si usamos peticiones HTTP síncronas, la ejecución del código se detendrá hasta que el servidor responda.

# Este es todo el código que tiene implementar el cliente para que  # todos empiecen al mismo tiempo. 
def main():
inicializar_componentes()
dibujar_pantalla_inicio()
# La ejecución del programa se detendrá hasta que el servidor
# responda.
id_juego = peticion_sincrona("miservidor.com")
empezar_juego(id_juego)

Un ProTip de hackatones

Una de las cosas más difícil de trabajar en hackatones es integrar los sistemas hechos por diferentes personas. Es típico ver a equipos pararse enfrente y presentar su aplicación por partes, primero enseñan la vista… pero no se comunica con el servidor, luego enseñan el servidor y los datos que computa… pero los imprimen en consola, los copian y los pegan en el código de la vista, la vuelven a cargar…

Es terrible tener diferentes partes de tu aplicación funcionando sin poderse comunicar. Nos ha pasado… ya demasiadas veces… Tú sabes de todo el esfuerzo que tu equipo hizo para hacer que cada componente funcione, pero de nada sirve si los jueces no lo pueden ver y no pueden usar lo que hiciste, se siente muy frustrante. Así que, como regla general, diseña la interfaz de tu sistema a prueba de idiotas que no han dormido en 24 horas.

Implementación

Entonces ya sabemos cómo queremos que se comporte la aplicación, ¿con qué la queremos construir?

Node.js

La primera opción y por la cual la mayoría del equipo se inclinaba era usar Node.js. La ventaja de Node.js era que la mayoría de nosotros ha tenido bastante experiencia usando esta tecnología. Yo empuje muy fuerte por no usarla por varias razones. Node es asíncrono pero no concurrente, y corre en un solo thread de ejecución. Esto quiere decir que si bloqueas en uno de tus request handlers tu servidor va a dejar de escuchar las demás peticiones. Lo que iba a pasar es que tendríamos que simular concurrencia utilizando callbacks recursivos en los requests handlers, y solo de imaginarme el callback hell que esto implicaría fue suficiente para buscar otra alternativa.

Python

Hace poco hice mi proyecto final de redes usando python y me acordé que es muy fácil correr un servidor http multithread donde cada request handler corre en su propio thread. Las ventajas de python son muchas:

  • Si usas Linux es muy probable que ya tengas instalada la versión más nueva. Esto hace que tu ambiente en tu laptop y en tu servidor remoto sea el mismo. No tienes que perder tiempo en estar tratando de que todas las computadoras tengan instalada la misma version del lenguaje de programación.
  • No necesitas de archivos de configuración, manejadores de paquetes, o instalar librerías externas. La librería de python ya te viene con un servidor web multithreaded y herramientas para manejar la concurrencia.
  • Todo el código te cabe en un archivo, nuestra implementación terminó en 157 líneas, pero con una limpiadita, yo creo que lo podríamos dejar en 100.

Concurrencia

En una aplicación multithread cada thread se ejecuta independientemente de los demás, pero todos comparten las mismas variables. Un cambio a una variable en un thread será visible a los demás threads.

Tengo que admitir que uno de los motivos por los cuales empujé tan duro por implementar el servicio con threads es que he estado leyendo este libro.

Yo creo que a lo mucho llevo unas 30 páginas, pero aprendí lo suficiente de concurrencia para ser peligroso.

Así que sabía que lo que estábamos tratando de hacer se podía hacer de una manera sencilla con concurrencia, solo íbamos a tener que usar unos locks para proteger el estado global de race conditions.

Race conditions

Probablemente ya hayan oído que la concurrencia es difícil, pero, ¿se han preguntado por qué?

En el siguiente ejemplo imaginen que el servidor inicia un nuevo thread para cada petición de los clientes y corre la siguiente función:

# Variables globales
MAX_PLAYERS = 4
current_players = 0
# Esta funcion implementa la funcionalidad de esperar a que los 4
# jugadores se registren para empezar el juego.
def http_get_register_handler(request, response):
current_players += 1
while current_players < MAX_PLAYERS:
pass # loop infinito
response.send(generate_next_game())
return

Trata de analizar la función por un minuto, ¿puedes identificar el race condition que hará que aunque 4 personas se registren el juego no empezará?


Si lo encontraste, felicidades, te debo una cerveza cuando te vea. El problema radica en la línea current_players += 1. Esta operación nos cabe en una linea de python pero son 3 operaciones para tu procesador.

  1. Leer current_players
  2. Incrementarlo en uno
  3. Escribir este valor a la variable current_players

El problema está en que un thread puede interrumpir a otro en cualquier momento. Si tienes varios threads corriendo en un procesador single core, el sistema operativo puede interrumpir tu ejecución en cualquier momento y podría pasar la siguiente situación.

Como A está trabajando con un valor obsoleto después de que el sistema operativo continúa su ejecución, va a escribir un valor obsoleto. Es decir, la variable solo se va a incrementar una vez a pesar de la función se llamó dos veces, lo que hará que nuestro servidor espere para siempre.

En un procesador multi core puede pasar el mismo problema si el caché tiene un valor viejo.

Locks

Entonces, ¿qué hacer para resolver este problema?

Ya establecimos que si varios threads intentan incrementar current players al mismo tiempo el juego se va a atorar. Tenemos que asegurarnos que esto no pueda pasar.

Para lograr esto usaremos un Lock. Un Lock es la primitiva de concurrencia básica. Un lock es como la caracola del señor de las moscas, quien tenía la caracola era quien tenía la palabra. Aquí quien adquiere el lock puede ejecutar el código dentro del lock, los demás threads tendrán que esperar a que sea liberado para que sea su turno de adquirirlo y poder ejecutar ese pedazo de código. Así nos aseguramos que dos threads nunca puedan interrumpir esta operación que previamente vimos nos causaría problemas.

MAX_PLAYERS = 4
current_players = 0
# El lock que usaremos
lock = threading.Lock()
def http_get_register_handler(request, response):
# Usamos el lock para proteger las mutaciones concurrentes al
# estado global
lock.acquire()
current_players += 1
lock.release()
while current_players < MAX_PLAYERS:
pass # loop infinito
response.send(generate_next_game())
return

¡Listo! ya tenemos código seguro. El código que muestro arriba se parece mucho a la primera versión que hice del servidor como prueba de concepto. Que código tan bonito y elegante.

Advertencia

No todo es bonito y hermoso con threads, cuando las cosas van mal es terrible y es casi imposible debuggear. El que tu código se pueda estar ejecutando en diferentes lugares y que el estado de tu aplicación se esté modificando en diferentes sitios al mismo tiempo hace muy difícil hacer un modelo mental de cómo funciona tu aplicación.

Ya concurrencia terminó por mordernos y casi impide que lográramos terminar. Cerca del final de la competencia cuando empezamos a integrar todos los sistemas nos dimos cuenta que mi código tenía errores de concurrencia . Me tomó más de una hora entender qué estaba pasando y creía que no iba a poder arreglarlo a tiempo.

Cuando intentaba debuggear con prints, los mensajes en consola se veían así: log: currelog: current_playelog: current_players = 3rs = 2nt_players = 1

Ya no tengo más que decir, si llegaron hasta aquí les agradezco por haber leído. Este es mi primer blog y se aceptan sugerencias.

Sólo me queda agradecer a Advancio y a We Can Code por organizar este evento. Ya son 4 años que compito y estoy muy convencido que participar en estas competencias me ha ayudado a ser mejor programador.

Un abrazo a mi equipo.