Linux y la fragmentación: el asignador de bloques de Ext4

(Nota: Este post es el cuarto y último de una serie de varios artículos sobre la fragmentación. Se recomienda leer la serie completa: 1, 2 y 3).

Continua la serie de artículos sobre la fragmentación en sistemas de archivo Linux. Este nuevo post trata sobre las novedades que incorporó Ext4 a su asignador de bloques. La información está sacada de este documento, y se puede también encontrar en un gran comentario al principio del archivo fs/ext4/mballoc.c.

El sistema de asignación de bloques es en gran medida el corazón de todo sistema de archivos, y los algoritmos utilizados tienen una gran importancia. Se trata de uno de esos puntos clave cuyos mecanismos siempre deben estar bien aceitados. No solo se les exige evitar la fragmentación, temática de esta serie de posts, también se les pide ser endiabladamente rápidos y muy escalables.


Una de las técnicas de organización del espacio que la mayoría de sistemas de archivos utilizan es subdividir el espacio disponible en partes de varios cientos de MB, de ese modo el sistema de archivos puede operar en varias subdivisiones a la vez casi independientemente. En el caso de Ext4, esa subdivisión se llama "grupo de bloques", y tiene un tamaño de 128 MB. Cada grupo de bloques tiene una serie de bloques dedicados a tareas especiales: hay unos en los que se almacenan los inodos (y cuya cantidad es estática y determinada por mkfs, razón por la que Ext4 no puede variar el número de inodos dinámicamente); también hay un bloque que se emplea en almacenar un mapa de bits que indica los bloques libres y los utilizados, y otro mapa de bits utilizado para indicar qué inodos están siendo utilizados. Cuando se va a iniciar una operación en un archivo, la decisión de asignación de bloques comienza, en principio, en el grupo de bloques al que pertenece el inodo del archivo, el cual suele asignarse en el grupo de bloques en el que está el inodo del directorio.

Ext4 dispone de dos espacios de preasignación principales a partir de los cuales se asignan bloques en un grupo de bloques: preasignación de CPU y preasignación de inodo. Las preasignaciones son rangos de bloques que no están siendo utilizados, pero están reservados y, en principio, no serán utilizados por nadie más. Si el archivo va a tener un tamaño menor a 16 bloques (64 KB), se utiliza el primer espacio de preasignación, si no, el segundo. De no poder atender la petición de asignación del espacio de preasignación, se procede a buscar espacio libre en un sistema de asignación "buddy" que contiene el resto del espacio que no está u ocupado o en las preasignaciones.

La razón por la que existen dos espacios de preasignación es para evitar que los archivos creados en una presignación no se entrometa en las del otro. Los archivos pequeños en un mismo directorio (por ejemplo, /etc/*) se benefician de estar ubicados uno a continuación del otro, los archivos grandes de asignaciones grandes y continuas. El sistema de preasignación de inodos (archivos grandes) también tiene, aparte de la preasignación, un sistema de "reservas" para casos en los que múltiples archivos se escribien simultáneamente.


Existe una forma muy curiosa de probar este sistema de preasignaciones, un ejemplo que curiosamente apareció en el segundo post de esta serie: la prueba del archivo al que se le añadía un bloque (4KB) en 200 ocasiones consecutivas, y que resultaba tener una fragmentación notable:


----------------------------------------------------------------
["oflag=append conv=notrunc" son ambos necesarios para que se vayan añadiendo datos al archivo, "conv=fsync" sincroniza el archivo a disco para asegurarse de que no se queda en RAM]
# for i in `seq 200`; do dd if=/dev/zero of=prueba bs=4K count=1 oflag=append conv=notrunc,fsync; done
[Un montón de datos de salida de dd]
----------------------------------------------------------------

Este archivo esta bastante fragmentado a pesar de ser un test simple y estar el sistema de archivos de pruebas completamente vacío. Echando un ojo a la salida detallada de filefrag, se puede intentar adivinar las causas de este comportamiento:

----------------------------------------------------------------
# filefrag -v prueba
Filesystem type is: ef53
File size of prueba is 819200 (200 blocks, blocksize 4096)
 ext logical physical expected length flags
   0       0    34304               3
   1       3    34816    34306      1
   2       4    34307    34816      3
   3       7    34817    34309      1
   4       8    34310    34817      2
   5      10    34818    34311      1
   6      11    34312    34818      1
   7      12    34819    34312      1
   8      13    34313    34819      2
   9      15    34820    34314      1
  10      16    33808    34820    184 eof
prueba: 11 extents found
----------------------------------------------------------------

2 pequeños extents de 3 bloques, 2 de 2 bloques, 6 de 1 bloque...y luego uno grande de 184 bloques. ¿Por qué esa distribución tan absurda de los bloques? Si sumamos todos los extents pequeños -todos menos el de 184 bloques- obtenemos exactamente 16 bloques (64 KB). Precisamente el límite mencionado entre el espacio de preasignación para archivos pequeños y el de archivos grandes. ¿Que ha ocurrido? Parece ser que mientras el archivo era menor de 16 bloques, Ext4 le asignó espacio de la preasignación para archivos pequeños; una vez que creció más allá de ese tamaño se le asignaron bloques de espacio de preasignación para archivos grandes, que colocó los 184 bloques restantes contiguos, uno detrás de otro...


¿Por qué, sin embargo, se han creado tantos fragmentos pequeños en la preasignación de CPU, optimizada para archivos pequeños? El problema es que la preasignación de CPU, llamada "per-CPU" en su idioma original, contiene en si mismo varias preasignaciones, una para cada CPU. Esta técnica per-CPU es muy común en el kernel Linux, se tratan de arrays de variables, una para cada procesador del sistema, para que cada CPU pueda operar en su variable sin interferir con las demás. En el caso de la preasignación de CPU de Ext4, más que por cuestiones de escalabilidad el objetivo es que las asignaciones de un mismo proceso -que se ejecuta en una CPU determinada- estén físicamente juntas. El comando tar, por ejemplo, podría desempaquetar un conjunto de archivos pequeños, y al ejecutarse tar en una misma CPU, los desempaquetaría en el espacio de preasignación de esa CPU.

¿Qué ha ocurrido entonces en el ejemplo anterior del archivo? Pues que mi sistema tiene 2 CPUs, y el proceso dd se ha ejecutado cada vez en una de las CPUs, de modo que en cada añadidura de 4KB se utilizaba el espacio de preasignación de cada CPU. Cuando, por casualidad, dd se ha ejecutado en la misma CPU dos o tres veces seguidas, ha logrado crear pequeños extents de 2 ó 3 bloques, pero cuando había alternancia entre las CPUs utilizadas era necesario empezar un nuevo extent discontiguo respecto al anterior. Y hay un modo muy simple de confirmar esta teoría, que es forzar la ejecución de dd en una CPU determinada, utilizando taskset(1):

----------------------------------------------------------------
# for i in `seq 200`; do taskset -c 1 dd if=/dev/zero of=prueba bs=4K count=1 oflag=append conv=notrunc,fsync; done
[Un montón de datos de salida de dd]

# filefrag -v prueba
Filesystem type is: ef53
File size of prueba is 819200 (200 blocks, blocksize 4096)
 ext logical physical expected length flags
   0       0    34304              16
   1      16    33808    34319    184 eof
prueba: 2 extents found

----------------------------------------------------------------

Esta vez dd ha accedido en todas las ocasiones al mismo espacio de preasignación de CPU, y por consiguiente ha ubicado los 16 primeros bloques contiguos.

Para terminar el post, ¿por qué, podría preguntarse alguien, hay un límite entre ambas preasignaciones para archivos pequeños y grandes que está fijado 16 bloques, por qué ese número? Ese valor es, en realidad, configurable, y se puede cambiar en el archivo /sys/fs/ext4/DISPOSITIVO/mb_stream_req. Y con esto se descubre ese desconocido directorio, que como se puede comprobar, contiene otros archivos de configuración, varios de ellos parámetros para tunear el comportamiento del asignador de bloques (y documentados en Documentation/ABI/testing/sysfs-fs-ext4). La disponibilidad de tales parámetros demuestra que la asignación de bloques es un tema muy complejo, que puede necesitar atención en casos especiales o susceptible a optimizaciones para una carga determinada. Espero que todo esto demuestre que el tópico de que Linux no sufre fragmentación es muy opinable y depende de multitud de factores (y eso que ni siquiera se ha mencionado la necesidad actual de que los diferentes archivos de una misma aplicación estén contiguos), de ahí que la disponibilidad de e4defrag es necesaria y bienvenida.