Trabajo optativo de sistemas operativos avanzados
The C10K problem

Se trata de un ejercicio individual de carácter optativo que permite que el alumno que lo realice pueda obtener hasta 0,5 puntos adicionales en la nota de la asignatura, siempre que la tenga aprobada.

El objetivo de los trabajos optativos que se plantean en la asignatura es que el alumno sea capaz de buscar información sobre un determinado asunto, procesarla adecuadamente y emitir una valoración crítica sobre la misma. Se pretende, de esta forma, complementar el carácter puramente aplicado de las prácticas de la asignatura.

Descripción del trabajo

Este trabajo se centra en estudiar el problema C10K y llegar a conocer las distintas soluciones que se plantean para afrontarlo en el ámbito de los sistemas Linux. Este problema se propuso en 1999 y está vinculado con el diseño de servidores web con muy alta escalabilidad. Evidentemente, con la continua mejora en las prestaciones del hardware, el límite cuantitativo especificado en el enunciado de ese problema ha dejado de tener sentido. Sin embargo, la esencia del problema sigue siendo la misma y su estudio permite adentrarse en las distintas técnicas existentes para el diseño de servicios escalables.

Comenzamos con una primera cuestión: la definición del problema.

  1. Describa brevemente en qué consiste el problema C10K.
Para fijar el contexto donde se ubica este trabajo, se repasan a continuación los pasos básicos que implica el procesamiento de una petición web, suponiendo, por simplicidad, que se trata de una de carácter estático (descarga de un fichero): Cuando se reciben múltiples peticiones, el servidor debe procesar concurrentemente los pasos requeridos por cada una de ellas. Téngase en cuenta que muchos de esos pasos implican operaciones de entrada/salida y, por tanto, pueden conllevar bloqueos (por ejemplo, la espera hasta que llega la petición por el socket conectado, la lectura del disco del fichero o las operaciones de envío por el socket que pueden bloquearse si el buffer de transmisión está lleno).

En el caso que nos ocupa, se pretende servir un número muy elevado de peticiones simultáneas. Para ello, es necesario diseñar una arquitectura para el servidor web que ofrezca buenas prestaciones, aprovechando el paralelismo hardware disponible, y asegure la escalabilidad del servicio, minimizando la cantidad de recursos requeridos para llevar a cabo el procesamiento.

A la hora de abordar el diseño de un servidor web, hay dos arquitecturas básicas: usar un modelo basado en procesos/threads o uno basado en eventos.

  1. Describa brevemente en qué consiste la solución basada en procesos/threads. Identifique un servidor web disponible para Linux que implemente este modelo.
  2. Describa brevemente el fundamento de la solución basada en eventos. Identifique un servidor web disponible para Linux que utilice esta arquitectura.
  3. Explique las ventajas y desventajas de cada modelo teniendo en cuenta dos aspectos: la escalabilidad y la facilidad en el diseño y programación de cada solución.

Arquitectura basada en procesos/threads

Nos centramos en este punto en la solución basada en procesos/threads. Sobre este mismo esquema hay distintas alternativas ortogonales entre sí:
  1. Averigüe qué tipo de alternativas de las anteriormente citadas proporciona el servidor web basado en procesos/threads que identificó en una pregunta previa explicando el modo de operación de cada una.
  2. En caso de que dicho servidor web provea algún esquema que use únicamente procesos, explique en qué caso sería recomendable este modelo aun sabiendo que los threads conllevan mucha menos sobrecarga.
  3. Analice qué puede aportar al diseño de un servidor web escalable el uso de threads de nivel de usuario (concretamente, soluciones híbridas que proyectan M threads de usuario sobre N threads de núcleo, siendo M significativamente mayor que N) frente a los threads de núcleo presentes en las versiones actuales de Linux.
Siguiendo dentro del modelo basado en procesos/threads nos vamos a centrar ahora en la optimización de la propia operación del envío al cliente del recurso solicitado.

El siguiente seudo-código podría representar de forma simplificada el servicio de una petición de un recurso web estático realizada por un proceso/thread del servidor:

	recv(s,...);   // recibe una petición "GET fichero ..."
	f=open(fichero,O_RDONLY);
	fstat(f, &st); // averigua el tamaño
	prepara_cabecera_respuesta(&cabecera); // HTTP/1.1 200 OK...
	send(s, &cabecera,...);
	while ((t=read(f, buf,TAM)) > 0)
		send(s, buf, t);
Nótese que, como se comentó previamente, en la ejecución de ese código puede haber bloqueos tanto en las operaciones de recepción del socket como en la de envío (un envío se bloquea si el buffer interno del socket está lleno), así como en las operaciones de acceso al fichero. No importa: tenemos un flujo de ejecución encargado únicamente de procesar esa petición. El propio sistema operativo se encargará automáticamente del procesado concurrente de las peticiones al realizar su labor habitual de planificación de los procesos/threads entre los procesadores disponibles.

Ese seudocódigo requeriría 2 send incluso para ficheros pequeños (cabecera + datos), lo que conlleva la sobrecarga asociada a esas 2 llamadas al sistema y, sobretodo, la fragmentación de los mensajes.

  1. Explique cómo podrían mitigar este problema las operaciones scatter/gather de Linux.

Por otro lado, en cada iteración del bucle, se producen varias copias entre buffers: la lectura del fichero, al completarse la operación de DMA del disco a la caché del sistema de ficheros, copia los datos de la caché al buffer de usuario (variable buf) y el envío por el socket copia de dicho buffer de usuario a un buffer interno del sistema operativo desde el que la tarjeta de red realiza la transmisión por DMA.

Nos surge en este punto la pregunta: ¿Cómo se podrían eliminar esas copias superfluas, de manera que, siempre que el hardware lo permita, la tarjeta de red tomara los datos directamente del buffer de la caché del sistema de ficheros, logrando el santo grial del zero-copy (aclaración: el uso de un buffer interno no rompe el zero-copy; este término indica que no se produce ninguna copia entre zonas de memoria)? Analicémoslo paso a paso.

Una primera mejora es usar la técnica de proyección de archivos:

	recv(s,...);   // recibe una petición "GET fichero ..."
	f=open(fichero,O_RDONLY);
	fstat(f, &st); // averigua el tamaño
	// proyecta el archivo
	p=mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
	prepara_cabecera_respuesta(&cabecera); // HTTP/1.1 200 OK...
	send(s, &cabecera,...);
	// lo envía con una única llamada
	send(s, p, st.st_size);
  1. En esta solución todavía se produce una copia superflua. Identifique cuál es.
  2. ¿Se podría combinar esta solución con el uso de operaciones scatter-gather identificado en un punto previo?
  3. ¿Por qué en la solución inicial no se puede leer con una única llamada todo el fichero (read(fd, buff, st.st_size)), sobretodo si es muy grande, y enviarlo con un único send, mientras que en este caso sí?
En este segundo paso, llegamos a las llamadas que eliminan esa copia superflua proporcionando zero-copy: sendfile y splice. Empecemos por la primera de ellas.
  1. Explique el modo de operación de la llamada sendfile.
  2. Dado que esta llamada no incluye mecanismos de scatter/gather, no puede evitarse (al menos, hasta el punto que yo sé) el envío por separado de la cabecera de respuesta. Sin embargo, sí se puede intentar minimizar la fragmentación de los paquetes de red. Averigüe qué opción de los sockets TCP puede usarse para conseguirlo.
Sigamos con la segunda:
  1. Explique el modo de operación de la llamada splice.
  2. ¿Cómo podríamos en este caso enviar por el socket la cabecera junto con el fichero sin usar ninguna opción de los sockets TCP?

Arquitectura basada en eventos

Pasemos ahora a los servidores basados en eventos. Dado que en este caso un flujo de ejecución tiene que atender múltiples peticiones, no se puede bloquear ni al usar los sockets, tanto para recibir como para enviar, ni al acceder a los ficheros.

Empecemos tratando la gestión de los sockets. Para resolver el problema de manejar múltiples sockets (tanto el socket por el que llegan las peticiones de conexión como los que ya están conectados) sin bloquearse esperando por uno de ellos, una primera solución, sin aplicación práctica por sus graves deficiencias, sería configurar como no bloqueantes los sockets e ir comprobando (polling) rotatoriamente el estado de los mismos: la existencia de conexiones pendientes en el socket de conexión (accept no bloqueante), la disponibilidad de datos de entrada correspondientes a una petición en los sockets conectados (recv o read no bloqueantes) y la posibilidad de envío sin bloqueo en aquellos sockets conectados por los que está pendiente de enviar una respuesta.

  1. Explique cómo se lleva a cabo en UNIX esa operación de configuración no bloqueante y describa cuál es el problema de esta solución.
Dados los déficits de esta solución, los sistemas operativos ofrecen otros mecanismos para lograr gestionar simultáneamente los sockets involucrados en la provisión de un servicio web concurrente siguiente esta arquitectura basada en procesos/thread. En un sistema Linux, se presentan, al menos, tres posibilidades: select, poll y epoll.
  1. Describa la solución basada en select explicando el modo de operación de la misma. Identifique qué limitaciones, en lo que refiere a la escalabilidad, presenta esta solución.
  2. Describa la solución basada en poll explicando el modo de operación de la misma. Identifique qué limitaciones, en lo que refiere a la escalabilidad, presenta esta solución. Compare esta solución con la basada en select identificando las ventajas y desventajas de cada una de ellas.
  3. Describa la solución basada en epoll mostrando el modo de operación de la misma y explicando cómo mejora los problemas de escalabilidad de las dos soluciones previas. Explique el concepto de notificación de eventos level-triggered versus edge-triggered usado por epoll mostrando las ventajas de cada tipo de notificación. ¿Qué modelo (level-triggered o edge-triggered) proporcionan select y poll?
Una vez analizado el problema de la gestión simultánea de múltiples sockets, a continuación, nos centramos en la problemática asociada al manejo de los ficheros: dado que en esta solución se usa un único flujo de ejecución, ¿cómo evitar que éste se quede bloqueado mientras se lee el fichero solicitado?

Dado que en UNIX no tiene ningún efecto configurar como no bloqueante el acceso a un fichero regular y que ninguna de las tres llamadas especificadas trata con descriptores asociados a ficheros regulares, una posible solución es el uso de operaciones de entrada/salida asíncrona, no disponibles en Linux de forma nativa para sockets pero sí para ficheros regulares.

  1. Linux proporciona dos implementaciones independientes de operaciones asíncrona: POSIX AIO y la implementación nativa. Describa el modo de operación de ambas implementaciones y argumente cuál es la más adecuada para incorporar en una arquitectura de servidor web basada en eventos.
Con los mecanismos descritos hasta el momento (operaciones asíncronas sobre ficheros y select, poll o epoll), parece que ya tenemos los fundamentos para construir una solución basada en eventos que podría tener un modo de operación como el siguiente: Esta solución es factible en los sistemas BSD que disponen del mecanismo kqueue que permite gestionar de forma integrada ambos tipos de eventos (a saber, la disponibilidad de un socket y la finalización de una operación asíncrona). En Linux, sin embargo, las llamadas select, poll o epoll no lo permiten, no existiendo, en principio, un mecanismo similar.
  1. Compare los mecanismos epoll de Linux y kqueue de BSD resaltando las ventajas de este último. Curiosamente, el mecanismo de BSD, además de mucho más rico, es más antiguo por lo que ha habido muchas voces en la comunidad que han sugerido que se debería haber incorporado como tal a Linux en vez de reinventar la rueda.
  2. Investigue al respecto en el mundo Linux e intente buscar qué tipo de soluciones se plantean para afrontar esta problemática.
Un par de preguntas finales sobre los servidores basados en eventos:
  1. ¿Cómo se puede aprovechar el paralelismo que ofrece el hardware del sistema (por ejemplo, un sistema multicore) en este tipo de soluciones basadas en eventos?
  2. Encuentre alguna biblioteca C multiplataforma que proporcione entrada/salida escalable basándose en las técnicas analizadas en las cuestiones previas.

Recapitulación

Para finalizar el trabajo y, por tanto, una vez estudiado en profundidad este tema, vamos a revisar de forma crítica la opinión de los detractores de los threads y la de aquellos que no son partidarios de las soluciones basadas en eventos.
  1. Explique brevemente cuál son los argumentos en contra de los threads vertidos en este documento: Why Threads Are A Bad Idea (for most purposes).
  2. Explique brevemente cuál son los argumentos en contra de los eventos esgrimidos en este documento: Why Events Are A Bad Idea (for high-concurrency servers).
  3. Exprese su opinión al respecto de esta polémica.

Entrega del trabajo

El plazo de entrega del trabajo es el 8 de mayo de 2019.

La entrega se realiza en triqui ejecutando el mandato:

    entrega.soa C10K.2019
	
Este mandato realizará la recolección del fichero memoria.pdf del directorio ~/DATSI/SOA/C10K.2019 en el cual habrá incluido las respuestas a las cuestiones planteadas en este trabajo así como las referencias que haya usado durante el desarrollo del mismo.