27 de junio de 2010

Linux y la fragmentación: "delayed allocation"

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

El anterior post tenía ejemplos de fragmentación de archivos en Ext4. Hay que recalcar que eran ejemplos muy muy simples, que en el mundo real ocurren cosas muchas más complejos como que haya una actualización de seguridad mientras algún programa hace otra cosa. Había afirmado que este post detallaría los algoritmos de asignación de bloques de Ext4, pero en su lugar tratará sobre la técnica "delayed allocation" (asignación retardada), que es quien se encarga de llamar a esos algoritmos y por tanto condiciona su funcionamiento.


En los sistemas de archivos sin asignación retardada, cuando una aplicación llama a write(), como parte de esa llamada se asignan los bloques para los datos. Aunque los datos no se vayan a escribir al disco en ese preciso momento y vayan a permanecer hasta decenas de segundos en el cache, aunque durante ese tiempo los bloques asignados no sean escritos, se asignarán igualmente. Este sistema puede provocar fragmentación, dado que en muchos casos se necesitan múltiples llamadas a write() para escribir enteramente un archivo. Se llamará, por tanto, al asignador de bloques en todas esas escrituras. Y, ¿cómo puede el asignador predecir todas las escrituras que se van a hacer, cómo predecir que un archivo va a llegar a los 2 GB cuando recibe el encargo de asignar los bloques para del primer mega? Simplemente no puede.

La técnica de asignación retardada, utilizada en sorprendentemente pocos sistemas de archivos (concretamente: en Ext4, XFS, ZFS, Btrfs y HFS+; su escaso uso se debe a haber sido considerada como peligrosa durante mucho tiempo), retrasa la asignación de los bloques hasta el momento en el que el caché se sincroniza al disco. Las llamadas a write() no provocan ninguna asignación de bloques, quienes las provocan son las rutinas de la VM cuando decide que es hora de sincronizar el caché. Este sistema permite que la escritura al disco de ese archivo se haga de una sola vez. El asignador de bloques sabe el tamaño total a asignar, tiene más información, por lo tanto puede tomar decisiones de asignación más inteligentes. En Ext4 existe una forma muy gráfica de ilustrar el funcionamiento de este mecanismo con ayuda, cómo no, del comando filefrag:

----------------------------------------------------------------
$ # Creamos un archivo de 4KB sin sincronizarlo inmediatamente al disco
$ dd if=/dev/zero of=prueba bs=1K count=4
[salida de dd]
$ filefrag -v prueba
Filesystem type is: ef53
File size of prueba is 4096 (1 block, blocksize 4096) 
 ext logical physical expected length flags
   0      0        0              1 unknown,delalloc,eof
prueba: 1 extent found
----------------------------------------------------------------


Como vemos, filefrag no muestra la ubicación lógica ni física del archivo, la muestra como "unknow, delalloc". Es decir, que no se sabe, y que está en estado de asignación retardada: La ubicación simplemente no existe aun, está aun pendiente de realizarse. Sin embargo, si ordenamos sincronizar inmediatamente después el caché con el disco...

----------------------------------------------------------------
$ sync
$ filefrag -v prueba
Filesystem type is: ef53
File size of prueba is 4096 (1 block, blocksize 4096)
ext logical physical expected length flags
  0      0    36681               1  eof
prueba: 1 extent found
----------------------------------------------------------------

Como se ve, ya se ha asignado su bloque (igualmente se hubiera escrito al disco si dejamos pasar el tiempo).


Este sistema es muy bonito. Sin embargo, sería un error afirmar que es una receta para la infalibidad contra la fragmentación, ya que la sincronización del caché al disco se hace cuando a la VM le de la gana...y el comportamiento de la VM es muy, muy variable. En situaciones de poca memoria, una de las primeras cosas que hace es solicitar la sincronización del caché con el disco. Dada una situación extrema de escasez de memoria, se dará el caso de que nada más enviar una llamada write() la VM ordenará la sincronización del caché y provocará una asignación de bloques casi inmediatamente, aproximándose al comportamiento de sistemas de archivos sin asignación retardada.

Una prueba empírica: en el primer ejemplo del post anterior se escribían dos archivos de 10GB en paralelo, los parámetros de dd eran "bs=512M count=20", lo cual hacía que cada dd ocupara en memoria 512MB. El resultado fue de 164 y 155 extents en cada archivo. Repitiendo la prueba pero con parámetros "bs=1G count=10" hace que los dos procesos dd ocupen 2GB, lo cual aumenta la presión de memoria en mi sistema y provoca mayores llamadas de sincronización de la VM. Resultado, 305-311 extents por archivo, con mayor entrecruce de ambos archivos en el disco.

Por lo tanto, se observa como la fragmentación del sistema de archivos puede variar con algo tan trivial como la presión de memoria del sistema (y noten que muy a menudo se hacen benchmarks sin intentar reproducir este tipo de condiciones), y cómo es poco prudente afirmar la ausencia de fragmentación en Linux. Todo esto viene a girar alrededor de un concepto ya afirmado en el primer post: Todos los archivos se enfrentan a GBs y GBs de espacio libre, y la decisión de colocar un archivo en un lado u otro depende muy en gran medida de la implementación.

El próximo post tratará -esta vez si- sobre los algoritmos de asignación de bloques de Ext4.

8 comentarios:

  1. Anónimo10:29 p. m.

    ¿No se supone que la llamada al sistema fallocate() sirve precisamente para informar mejor al sistema de archivos de la cantidad de datos que vamos a escribir?

    Un saludo, y espero ansioso la próxima entrada

    ResponderEliminar
  2. Felicidades por la calidad de tus posts! sorprentdente leer cosas así en español. Gracias.

    ResponderEliminar
  3. Anónimo5:02 a. m.

    muy interesante tronco ... keep writing like this !!!

    ResponderEliminar
  4. Anónimo : fallocate lo que hace es reservar el espacio en disco para un archivo del que se conoce su tamaño de antemano. De esta forma el asignador de bloques tratara de darnos los bloques de la mejor manera posible, esto es idealmente, de forma consecutiva.
    En otros sistemas de archivo en los que no existe esta llamada de "pre-reserva de espacio" se hace la "chapuza" de escribir el tamaño total del archivo con ceros y luego ir pisando con los datos reales esos ceros. La eficiencia y el "desgaste" de disco de ambas formas es la misma que hay entre borrar un archivo de forma lógica (solo referencia) o física (referencia y datos físicos sobreescritos con 0s).

    ResponderEliminar
  5. Excelente estudio sobre el tema... por suerte todavía queda alguien que no se limita a repetir y repetir lo repetido.... Gracias por los orgasmos que me has proporcionado....

    ResponderEliminar
  6. Anónimo: fallocate() existe, de hecho, precisamente porque los algoritmos de asignación no son capaces de hacer milagros.

    ResponderEliminar
  7. Muy bien explicado, por favor sigue.

    ResponderEliminar
  8. Anónimo4:25 a. m.

    No se si venga al caso, pero el nuevo sistema al que te refieres para hacer la prueba. Supongo que fue un HD completo con una sola y única partición para todo el disco, porque de ser de otro modo pienso que puede alterar los resultados. Porque si se hace particiones dentro el disco duro con alguna "herramienta" ¿que tan contiguo hace la partición? A nivel lógico si esta contiguo, pero a nivel lógico no. Entonces allá entra lo que comento. A decir esto solo involucra fragmentación externa. Hay que incluir también la fragmentación interna y a nivel de archivos. Un total de iteraciones y vueltas solo para acceder a la tan preciada información. saludos

    ResponderEliminar