blk-mq: la arquitectura multi-cola

Durante veinte años el block layer tuvo una cola por dispositivo protegida por un cerrojo, y funcionó porque el cuello de botella era el disco rotacional, no el software: daba igual que el encolado fuera lento si el cabezal tardaba milisegundos. Entonces llegaron los NVMe capaces de un millón de operaciones por segundo y los servidores de sesenta y cuatro núcleos, y ese cerrojo único se volvió el enemigo: todos los núcleos peleándose por la misma línea de cache, rebotándola de socket en socket, gastando más ciclos en coordinarse que en trabajar. blk-mq es la reescritura que resolvió eso partiendo la cola en dos capas y dando a cada CPU la suya. Es la arquitectura sobre la que corre hoy toda la E/S de bloques de Linux.

El pecado de la cola única

El modelo antiguo —hoy llamado single-queue y borrado del kernel en la versión 5.0— tenía una request_queue con una lista de peticiones y un queue_lock. Cada CPU que quería encolar una bio, fusionarla o sacar la siguiente para el driver tenía que tomar ese mismo cerrojo. Con un núcleo y un disco lento, invisible. Con muchos núcleos y un SSD rápido, catástrofe: la línea de cache que contiene el cerrojo viaja constantemente entre los cachés L1 de todos los núcleos —el fenómeno de cacheline bouncing—, y el sistema pasa más tiempo sincronizando el acceso a la cola que sirviendo E/S.

/* el patologico modelo antiguo, conceptualmente */
spin_lock_irq(q->queue_lock);   /* TODAS las CPUs pelean por este cerrojo */
list_add_tail(&rq->queuelist, &q->queue_head);
spin_unlock_irq(q->queue_lock);
/* con 64 nucleos y 1 millon de IOPS, este cerrojo es el sistema entero */

El problema no era el algoritmo sino la geometría: un único punto de serialización por el que ha de pasar toda la E/S no puede escalar con el número de núcleos, por muy fino que sea el cerrojo. La única salida es que las CPUs dejen de compartir el punto de encuentro.

Dos capas de colas: staging por-CPU y despacho por-hardware

blk-mq (multi-queue, fusionado en 2013 y hoy el único camino) parte la cola en dos niveles. El primero son las colas software de staging, struct blk_mq_ctx, una por CPU. Cuando un hilo emite una bio, se encola en la cola de su propia CPU, sin tocar ninguna estructura compartida con las demás: el encolado deja de tener contención porque cada núcleo tiene su buzón.

El segundo nivel son las colas de despacho de hardware, struct blk_mq_hw_ctx —abreviado hctx—, que se corresponden con las colas de envío reales del dispositivo. Un NVMe moderno expone muchas colas hardware, idealmente una por CPU, cada una con su propio vector de interrupción MSI-X. El hctx es el puente entre el software y una de esas colas físicas.

/* el driver declara cuantas colas hardware tiene el dispositivo */
struct blk_mq_tag_set set = {
	.ops         = &mi_mq_ops,
	.nr_hw_queues = num_possible_cpus(),  /* NVMe: una cola por CPU */
	.queue_depth = 1024,                  /* comandos en vuelo por cola */
	.cmd_size    = sizeof(struct mi_cmd), /* datos privados por peticion */
	.numa_node   = NUMA_NO_NODE,
	.flags       = BLK_MQ_F_SHOULD_MERGE,
};

Entre ambas capas hay un mapa: cada cola software (cada CPU) se asigna a una cola hardware. Si hay tantas hctx como CPUs, el mapa es uno a uno y la E/S de cada núcleo vuela por su propio carril de principio a fin. Si hay menos colas hardware que CPUs —un SATA con una sola cola—, varias ctx comparten una hctx, y solo ahí, en el último tramo, reaparece algo de coordinación. La clave es que la contención se ha empujado lo más abajo y lo más tarde posible.

flowchart TD
C0[CPU 0] --> X0[ctx 0 cola software]
C1[CPU 1] --> X1[ctx 1 cola software]
C2[CPU 2] --> X2[ctx 2 cola software]
C3[CPU 3] --> X3[ctx 3 cola software]
X0 --> H0[hctx 0 cola hardware]
X1 --> H0
X2 --> H1[hctx 1 cola hardware]
X3 --> H1
H0 --> DEV[Dispositivo con colas MSI-X propias]
H1 --> DEV
style X0 fill:#89b4fa,color:#11111b
style X1 fill:#89b4fa,color:#11111b
style X2 fill:#89b4fa,color:#11111b
style X3 fill:#89b4fa,color:#11111b
style DEV fill:#a6e3a1,color:#11111b

Tags: un billete que es a la vez índice de comando

Cada petición en vuelo necesita un identificador, y blk-mq lo resuelve con un mecanismo que mata dos pájaros: el tag. El blk_mq_tag_set posee un mapa de bits escalable —un sbitmap, diseñado para que muchos núcleos reserven bits sin pelearse por una sola palabra— del tamaño de queue_depth. Sacar una petición reserva un bit libre; ese número es el tag, y a la vez es el índice del slot de comando en el hardware.

/* el tag reservado indexa directamente el descriptor del hardware */
struct request *rq = blk_mq_alloc_request(q, REQ_OP_READ, 0);
u32 tag = rq->tag;                       /* del sbitmap, unico y en vuelo */
struct nvme_command *cmd = &nvmeq->sq[tag];  /* el tag ES el slot */

La elegancia es doble. Primero, el sbitmap reparte los bits por CPU para que reservar un tag casi nunca toque una línea de cache compartida. Segundo, como el tag es el índice del comando, cuando el hardware completa y devuelve “terminó el comando tag”, el driver localiza la petición original en tiempo constante, sin buscar en ninguna lista. El tag es billete de entrada y localizador de salida en un solo número.

Por qué esto era inevitable

blk-mq no fue una optimización oportunista sino una necesidad estructural. El almacenamiento cruzó, en pocos años, de decenas de IOPS (disco) a millones (NVMe), y simultáneamente el recuento de núcleos por servidor se disparó. Cuando el hardware deja de ser el cuello de botella, el software se convierte en él, y un diseño con un punto único de serialización no tiene rescate incremental: hay que rehacer la geometría. El mérito de blk-mq es haber alineado la estructura del software con la del hardware —muchas colas arriba, muchas colas abajo, un carril por núcleo cuando se puede— de modo que añadir núcleos añada rendimiento en vez de contención.