Introducción
La idea de este blog post surge por las dudas de colegas al comentarles sobre las facilidades que provee Go en el manejo de concurrencia.
Era necesario pensar cómo identificar las unidades de ejecución en golang como también los límites en cuanto a la capacidad de concurrencia de las goroutines
¿Qué son en esencia las Goroutines ?
Se podría decir que las goroutines son las unidades básicas de ejecución, o sea la función principal de un programa en Go es una goroutine la cual es controlada por el runtime machine de Go, el cual, entre varias funciones, se encarga de ser el garbage collector y el scheduler de estas goroutines.
Las goroutines no son un concepto nuevo en las tecnologías que manejan concurrencia y paralelismo de operaciones, dan una mayor agilidad ante los context switch de threads que realiza el sistema operativo, puntualmente se busca una mayor agilidad en cuanto al manejo de:
- Puntero a la TCB (Thread control block)
- Guardar registros de propósito general
- Metadata de threads
Esto motivó a desarrollar algoritmos que manejan concurrencia dentro de threads , quitando la gestión al sistema operativo y manejar una política de cambio de contexto más adecuada ante tareas concurrentes. De aquí nacen las coroutines o fibers , ideas pilares en el diseño de goroutines
Pasando en limpio, las coroutines son unidades de secuencia de cómputo manejadas por un runtime machine. Este tipo de rutinas tiene la propiedad llamada nonpreemptive: una vez que son ejecutadas, no son pausadas mediante algún mecanismo de context switch, o yield().
Un poco de teoría detrás de un runtime machine
El runtime machine se encarga de gestionar las coroutines que se ejecutarán sobre los threads y la cantidad de threads que utilizará el proceso. Este mecanismo está implementado en base a un algoritmo llamado M:N scheduler, el cual mapea M coroutines en N threads manejados por el sistema operativo.
A su vez, el modelo de organización que siguen las corrutinas, que en nuestro caso son las conocidas goroutines, es mediante el llamado fork-join model.
Recordar lo mencionado anteriormente, las gorutines son nonpreemptive y este no es un dato menor. En caso de que se mapee las goroutines a un thread, se suspenderá la ejecución de la goroutine padre hasta que la goroutine hija termine su ejecución, secuencializando en tiempo la ejecución. También se debe notar la alta dependencia que tienen las goroutines, en caso de que se puedan distribuir en threads separados, el thread padre quedará bloqueado en el punto del join hasta que la goroutine hija no finalice, o sea, no hay mecanismos de detach.
Ya teniendo más claro la idea de cómo se gestionan entre ellos las goroutines, la siguiente pregunta sería, ¿Cómo se gestiona esta interacción?
Bueno, este mecanismo es viejo y conocido en la virtual machine de java y no es descabellado pensar que se siga la misma estrategia en la runtime machine de Go. Dicho algoritmo es el conocido work stealing strategy.
El algoritmo work stealing strategy se basa en la regla fair scheduling, el cual, en principio distribuye equitativamente las M corrutinas en los N threads, aunque a lo largo de la ejecución esta estrategia debe adaptarse al modelo fork-join antes mencionado, donde una goroutine puede quedar bloqueada, por diferentes motivos (espera de un join, una operación de I/O, …)
La clave de esta estrategia es: un thread que se encuentra en estado de espera debido a que atendió a una goroutines bloqueada, roba tarea a un thread elegido al azar.
Viéndolo gráficamente, supongamos que tenemos tareas a ser ejecutadas por 3 threads, donde una de las tareas G1 presenta dependencia de la tarea G4 debido a un fork, la cual en principio es colocada en el mismo thread de ejecución.
Debido a que los demás threads quedarán desocupados, el próximo thread al ser ejecutado, Th2, tratará de robar tarea al azar. Supongamos que quiera hacerlo con Th3, este también se encuentra desocupado, pero no pasará lo mismo cuando elija a Th1, a este sí le podrá robar tareas a ejecutar, pudiendo resolverse la dependencia de ejecución.
¡Ya basta de teoría! Vayamos a algo práctico
Bueno, creo que es suficiente de teoría, incluso queda por parte del lector profundizar en los temas mencionados, pero
¿Esto en que nos afecta al momento de pensar en una solución eficiente escrita en Go?
Vayamos a un caso en concreto, un simple algoritmo quicksort desarrollado por nosotros:
Escrito de 2 formas diferentes, una utilizando recursividad y la otra lanzando goroutines.
Y una pequeña función que produzca un array a ordenar:
Ahora generaremos un conjunto de arrays a ordenar, digamos 50, para un caso ejecutemos secuencialmente por cada array a ordenar, para el otro caso lanzamos una gorutine por cada array a ordenar.
Ejecutando los siguientes benchmarks:
Obtenemos los siguientes resultados:
En una arquitectura i5 que soporta 8 threads en paralelo, vemos que la estrategia de lanzar una goroutine por cada iteración de ciclo for resultó ser más rápida que la opción secuencial, casi 4 veces en promedio y en tan solo un set de 50 array a ordenar. La tendencia es que si la cantidad de iteraciones a realizar aumenta, la ventaja será mayor.
En conclusión, si tuviésemos la oportunidad de lanzar un spawn de threads para resolver tareas en paralelo, se generaría en principio un consumo excesivo de memoria sumado a la alta sobrecarga de trabajo en sistema operativo para crear los threads y manejar context switch, para dicho problema existe el patrón thread pool. Sin embargo, el runtime de golang nos permite despreocuparse de muchas políticas de paralelización que pueden llegar a degradar el sistema en general, resolviendo de forma eficiente con poco overhead de procesamiento y consumo de memoria.