epoll: la multiplexación O(1) de Linux

Bajo nginx, Redis, HAProxy y el libuv que mueve a Node.js late la misma estructura de datos del kernel de Linux: epoll. No es un poll más rápido, es un cambio de modelo. En vez de preguntarle al kernel en cada llamada “de estos diez mil, ¿cuáles están listos?” —y que él lo averigüe recorriéndolos—, le declaras tu interés una sola vez y dejas que la disponibilidad fluya hacia ti según ocurre. El coste deja de escalar con el tamaño de lo que vigilas y pasa a escalar con el ritmo de lo que pasa, que es la única forma honesta de cobrar por eventos.

epoll_create1 y epoll_ctl: declarar el interés una vez

epoll_create1 devuelve un descriptor que representa un objeto vivo dentro del kernel, un struct eventpoll. A partir de ahí, epoll_ctl añade, modifica o quita descriptores de ese conjunto con las órdenes EPOLL_CTL_ADD, EPOLL_CTL_MOD y EPOLL_CTL_DEL. Cada fd se registra una sola vez y permanece en el conjunto hasta que lo quitas.

struct epoll_event {
	__u32     events;   /* EPOLLIN, EPOLLOUT, EPOLLET, EPOLLONESHOT... */
	epoll_data_t data;  /* union: ptr, fd, u32, u64: te lo devuelven tal cual */
};

/* crear el conjunto y registrar el socket de escucha UNA vez */
int epfd = epoll_create1(EPOLL_CLOEXEC);

struct epoll_event ev = {
	.events   = EPOLLIN,
	.data.ptr = &conn_escucha,   /* adjunta tu objeto: lo recuperas sin buscarlo */
};
epoll_ctl(epfd, EPOLL_CTL_ADD, lfd, &ev);

El campo data es una unión que el kernel te devuelve intacta en cada evento. Guardar ahí data.ptr con el puntero a tu estructura de conexión es la práctica canónica: cuando el fd se activa, recibes directamente el objeto, sin traducir un número de descriptor a través de una tabla hash.

epoll_wait: recoger solo los listos

epoll_wait bloquea hasta que alguno de los fds registrados esté listo y llena tu array únicamente con esos eventos, hasta un máximo de maxevents. Su coste es proporcional al número de listos, no al tamaño del conjunto: ahí muere el muro O(n).

/* bucle de eventos completo: el esqueleto de todo servidor epoll */
struct epoll_event eventos[MAX_EVENTOS];

for (;;) {
	int n = epoll_wait(epfd, eventos, MAX_EVENTOS, -1);  /* solo devuelve los listos */

	for (int i = 0; i < n; i++) {
		struct conn *c = eventos[i].data.ptr;    /* tu objeto, sin busqueda */

		if (c->fd == lfd) {
			/* nueva conexion: accept no bloqueante y alta en el conjunto */
			int cfd = accept4(lfd, NULL, NULL, SOCK_NONBLOCK | SOCK_CLOEXEC);
			struct conn *nc = conn_nueva(cfd);
			struct epoll_event nev = { .events = EPOLLIN, .data.ptr = nc };
			epoll_ctl(epfd, EPOLL_CTL_ADD, cfd, &nev);
		} else if (eventos[i].events & EPOLLIN) {
			atender_lectura(c);
		}
	}
}

Un solo hilo, un solo bucle, y todo el trabajo concentrado en los descriptores que de verdad tienen algo que decir. Añadir la conexión número diez mil no encarece ni un ápice la atención de las otras: el registro con EPOLL_CTL_ADD es una operación puntual, no un peaje que se repita en cada vuelta.

El parámetro maxevents acota cuántos listos recoges por llamada. Si hay más listos que ese tope, los sobrantes no se pierden: permanecen en la lista de listos del kernel y salen en la siguiente vuelta, y epoll los rota para que ningún descriptor quede postergado sin fin. Dimensionar bien el array —ni tan pequeño que multiplique las llamadas, ni tan grande que dispare la latencia de la primera atención— es un ajuste real de todo servidor bajo carga.

Por dentro: árbol de interés, lista de listos y el callback

La eficiencia no es magia, es una elección de estructuras de datos en fs/eventpoll.c. El struct eventpoll guarda dos colecciones. El árbol rojinegro (rbr) contiene un struct epitem por cada descriptor registrado: es el conjunto de interés persistente, que sobrevive entre llamadas. La lista de listos (rdllist) contiene solo los epitems cuyo fd está disponible ahora mismo.

La pieza clave es qué ocurre al registrar. Cuando epoll_ctl añade un fd, instala en la cola de espera de ese archivo un callback, ep_poll_callback. A partir de ahí, epoll no vuelve a interrogar el descriptor: espera a que el propio fd lo avise. Cuando llegan datos al socket, el despertar de su cola de espera dispara ep_poll_callback, que enlaza el epitem en la lista de listos y despierta a quien duerme en epoll_wait.

/* fs/eventpoll.c, esencia de ep_poll_callback: se dispara al llegar el dato */
static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)
{
	struct epitem *epi = ep_item_from_wait(wait);
	struct eventpoll *ep = epi->ep;

	list_add_tail(&epi->rdllink, &ep->rdllist);  /* el fd listo entra en la lista */
	wake_up(&ep->wq);                            /* despierta a epoll_wait */
	return 1;
}

epoll_wait no recorre nada: transfiere la lista de listos a tu array y regresa. Ningún descriptor inactivo se toca jamás. Ese es el sentido exacto del O(1) por evento: el trabajo sucede en el flanco de disponibilidad, empujado por el callback desde el fd, en lugar de ser arrastrado por un barrido desde el usuario.

flowchart LR
CTL[epoll_ctl ADD] --> RB[arbol rojinegro de epitems]
RB -->|instala callback| WQ[cola de espera del socket]
WQ -->|llega dato y dispara ep_poll_callback| RD[lista de listos]
RD --> WAIT[epoll_wait copia solo los listos]