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.

Linux y la fragmentación: provocando fragmentación en Ext4

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

El anterior post defendiendo la existencia de fragmentación bajo Linux fue recibido con escepticismo. Para ser justos, la excesiva longitud del anterior post llevó a no extenderlo más de lo necesario. En este post, mostraremos un par de casos triviales en los que se puede observar fragmentación en sistemas Linux usando Ext4.

En primer lugar, una prueba muy simple, escribir dos archivos grandes a la vez. Se lanzan en paralelo dos procesos dd que crearán sendos archivos de 10 GB. Para que no haya dudas, la prueba se hace en un sistema de archivos recién formateado (nota: dd parece ocupar la memoria especificada en bs, es decir, en este test los dos procesos dd ocupan 1GB de RAM)

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

# for i in `seq 2`; do (dd if=/dev/zero of=prueba-$i bs=512M count=20 &); done

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

Una vez terminados de crear los archivos, se examina la fragmentación....

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

# filefrag prueba*

prueba-1: 164 extents found
prueba-2: 155 extents found
----------------------------------------------------------------

Antes de continuar, aclarar que el tamaño máximo de un extent en Ext4 es de 128 MB. Eso quiere decir que dada una asignación de bloques perfecta, un archivo de 10 GB ocuparía 80 extents contiguos. Sin embargo, los archivos recién creados han necesitado el doble (en otros sistemas o con diferentes parámetros de dd puede haber muchos menos o muchos más, y tiene su explicación).

No suena nada bien, y los detalles pueden revisarse comprobando la ubicación y límites de cada extent con filefrag prueba* -v (cuya extensa salida no pondré aquí). En mi caso hay varios extents de tamaño máximo, 32768 bloques -128 MB-, pero también varios de 4096 -16 MB- y alguno incluso con menos, varios de 20 y pico mil, 16 mil, 12 mil...en definitiva: irregular. Si cotejamos datos de la columna "physical" de ambos archivos, el problema es más evidente: los extents de los dos archivos se van entrecruzando. Por ejemplo, el primer extent de archivo-1, el primero de archivo-2, y el segundo extent de archivo-1, van uno detrás de otro.

Y esto es con dos archivos. Imagínense 5 ó 10. O más. Y no estamos hablando de casos extravagantes y sacados de contexto, sino simplemente de copiar archivos.

Hay que ser justos y señalar que esto no es un problema de rendimiento en equipos comunes, ya que una cosa es fragmentarse en pedacitos de pocos KB por todo el disco, y otra hacerlo en pedazos de 128 ó incluso 16 MB, esta fragmentación probablemente ni siquiera se note en benchmaks. Sin embargo, no sirve de excusa para ignorarla. En equipos donde se requieran sistemas de almacenamiento profesionales es de imaginar que Ext4 no de la talla (por esta razón existen empresas con sistemas de archivo e incluso SOs propietarios especializados exclusivamente en optimizar casos como estos). Pero tampoco hay que irse por las nubes, bastaría con copiar dos archivos grandes a la vez a través de una interfaz gráfica para reproducir este problema.

Pero hay otros ejemplos simples. ¿Qué tal, por ejemplo, un archivo vacío al que se añaden 4KB (1 bloque) 200 veces, simulando una especie de archivo de log que va creciendo? En un sistema de archivos Ext4 nuevamente formateado desde cero, por supuesto. Cabría esperar que simplemente se añadieran los 200 bloques uno detrás de otro, ¿verdad?

----------------------------------------------------------------
["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]
# filefrag prueba
prueba: 9 extents found
----------------------------------------------------------------

Si echamos un ojo a los datos de filefrag prueba -v, resulta que los 200 bloques están divididos en un extent con 184 bloques, otro con 7, dos con 2, y cinco con 1, y los extents no son contiguos entre ellos. Fragmentación discriminada y absurda (tengo una teoría razonable que explique este absurdo comportamiento, pero tendrá que esperar a un artículo posterior).

En definitiva, como se puede ver la fragmentación en Linux ocurre. Probablemente se podrían buscar más casos, algunos de ellos retorcidos como variar el tamaño de los archivos asignados con truncate(1) o archivos "sparse"...pero estos casos son simples y demuestran que no hace falta romperse la cabeza para encontrar fragmentación en Linux. Si quieren encontrar fragmentación en sus propios sistemas, prueben a buscar con filefrag por su $HOME. Sugiero empezar por este:

# filefrag ~/.mozilla/firefox/*.default/*.sqlite


Los archivos places.sqlite, cookies.sqlite, formhistory.sqlite y urlhistory3.sqlite, que corresponden a las bases de datos sqlite que utiliza Firefox en versiones modernas, seguramente estén divididos en varios fragmentos si su perfil de Firefox lleva funcionando un tiempo. Cosas como esta, entre otras, son las que hacen que nada más arrancar Firefox y se trata de introducir una url, la AwesomeBar tarde un poco más en leer el disco y reaccionar. Si son administradores de bases de datos, los archivos de la base de datos pueden tener cierta fragmentación acumulada. /var (las bases de datos de paquetes dpkg/rpm en particular) también son buenos candidatos. ¿A que ahora los desfragmentadores no parecen una idea tan estúpida? (un modo cutre y fácil de imitarlos es copiar el archivo fragmentado en otro y mover el archivo copiado al original)

El próximo post será sobre el funcionamiento de los algoritmos de asignación de bloques de Ext4. Ya puestos, por qué no hacer de esto una serie...

Linux y la fragmentación: si, ocurre

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

El tópico de que Linux no necesita desfragmentación ha vuelto renacer. Suele hacerlo periódicamente, aunque por desgracia eso no lo haga más cierto. Ese argumento de que los sistemas de archivos en Linux no se fragmentan o que lo hace tan poco que apenas se nota, y que en NTFS en cambio lo hacen una barbaridad, nunca va acompañado, si se fijan, de una explicación. Eso es porque no la hay.

Creo que el origen del mito es visual. Windows tiene un desfragmentador de serie que muestra (mostraba) un bonito gráfico donde se ve el estado y progreso de la fragmentación, la cual deja de ser un concepto abstracto para volverse algo real, que se puede percibir mediante los sentidos. Oh, mira cuanta fragmentación. En una instalación Linux típica no hay ningún desfragmentador y mucho menos con gráficos, y al no verse nada es como que no existe (o se obtiene la cifra media de fragmentos/archivo, que es una bonita manera de ocultar la realidad con estadísticas): Oh, no tenemos fragmentación. Pero aunque no la veamos, existe. Hubo un tiempo en el que un servidor de ustedes muy de vez en cuando movía todo su sistema de una partición a otra del disco duro (cp -a), y la disminución del tiempo de inicio del sistema y del tiempo que transcurre entre KDM/GDM y la aparición del escritorio se podían medir en el reloj y en el menor carraspeo del disco duro. Apostaría a que la acertada decisión de eliminar la parte visual del desfragmentador en Windows Vista/7 se debe a la falsa sensación de conocimiento que mucha gente creía tener con las imágenes visuales.

Hay un par de cosas respecto a este asunto de la fragmentación que la mayoría de la gente (y en este blog, gente = frikis/geeks) desconoce de los sistemas de archivos. La primera es que los sistemas de archivos tienen muchas partes en común. El asignador de bloques para los datos, en particular -responsable de la fragmentación-, es un asignatura bastante común a todos, por no mencionar esos oscuros rincones en los que el sistema de archivos se funde de manera ambigua con la gestión de memoria.

En segundo lugar, una cosa es el formato físico del sistema de archivos, y otra su implementación. Una buena implementación puede incluso tapar los defectos de un sistema de archivos antiguo, y hacerlo mejor que uno nuevecito con una mala implementación. En Linux hay ejemplos muy próximos en los dos sentidos. Ext3/4 son sistemas de archivos viejos, desfasados, a diferencia de, por ejemplo, NTFS, que es claramente más moderno. Sin embargo la implementación de Ext4 es sobresaliente, capaz de competir con NTFS sin problemas e incluso con XFS en algunos puntos. En cambio Reiserfs v3 tiene un diseño muy nuevo, pero su implementación deja bastante que desear, por eso las empresas se pasaron a Ext4. Y algo con tanto prestigio como ZFS en todo su esplendor tuvo, nada más ser publicado y antes de mejorarlo, un algoritmo de asignación de bloques que se podía resumir con la frase "aquí te pillo, aquí te mato".

Uniendo los dos párrafos anteriores, se puede obtener la conclusión de que tomar decisiones de asignación de bloques que creen o no fragmentación en la disposición de los datos en el disco duro depende en gran medida de la implementación.

En principio, en teoría cualquier sistema de archivos puede hacer magníficas decisiones de asignación de bloques en lo que se refiere a fragmentación (otra cosa es el rendimiento y otros factores). Un buen ejemplo para comprenderlo es el caso de dos procesos escribiendo datos simultáneamente a dos archivos diferentes. Un asignador de bloques simple entrecruzará a lo largo del disco duro los datos de ambos archivos: primero un trozo del primer proceso, luego otro del segundo, posteriormente otro trozo del primero, etc, causando una fragmentación masiva. En cambio, un buen sistema debería detectar esta situación y tratar, por lo menos, de que los trozos que se entremezclen sean de un gran tamaño. Este tipo de heurísticas no dependen del formato del disco, y aunque cierto es que la facilidad para implementarlas esté influida por otros aspectos del sistema de archivos, a base de empeño un buen programador con muy poco respeto por la humanidad podría hacer maravillas hasta con FAT.

Resumiendo: Toda discusión sobre la fragmentación debería estar razonada en base a los algoritmos de asignación de bloques, que son quienes causan o evitan esa fragmentación. Los de Windows/NTFS no se conocen ni se conocerán nunca en detalle, pero los de Linux si que se conocen (aunque en todo google solo existan un par de referencias). Sin embargo, nunca los he visto expuestos en una discusión (no, esto no es suficiente), en cambio de Windows siempre se supone que no tienen absolutamente ni una sola línea de código dedicada a evitar la fragmentación, lo cual es una presunción (veo la imagen del desfragmentador, luego creo saber) demasiado atrevida. Sirva de ejemplo de desconocimiento de este tema que a pesar de que Ext4 incorpora varios cambios para evitar diferentes tipos de fragmentación, en tiempos del reinado del Ext3, que carece de esos cambios (y por tanto se fragmenta más), se afirmaba de todos modos que Linux no sufría fragmentación. O, peor aun, se afirma que los sistemas de archivos Unix previenen la fragmentación basándose en...¿exactamente qué hechos? (es más, ZFS y Btrfs se fragmentan una auténtica barbaridad por virtud de las técnicas COW).

Echen en Linux un ojo a la herramienta filefrag, como curiosidad yo tengo una ISO de un DVD en un Ext4 bajada con wget que está dividida en mil y pico extents. Y un SVG de 1.2 MB con 8 (un caso muy raro), y varias películas divididas en cientos cada una. Fragmentación pura y dura bajo un kernel 2.6.35-rc3 (eso si, si obtenemos la cifra media de fragmentos/archivo, los miles de archivos menores de 4KB rebajarán la media y harán que parezca que no pasa nada). Y no todo es culpa del sistema de archivos, no es casualidad que POSIX tenga la función fallocate(), es una prueba de que existen casos en los que un asignador de bloques no pueden predecir el futuro. Además, hay que tener en cuenta la fragmentación entre diferentes archivos, un tipo de fragmentación muy importante para el rápido inicio del sistema y de las aplicaciones y que prácticamente requiere un desfragmentador. No es casualidad que XFS, Ext4, y Btrfs tengan desfragmentadores, simplemente se necesitan (para Btrfs puede llegar a convertirse en un requisito).

Por supuesto, si usted quiere puede vivir sin desfragmentador, e incluso las distros Linux podrían no usarlo bajo la regla de que casi nunca hace falta, pero por esa regla de tres también Windows podría eliminarlo basándose en esa lógica. Lo acertado de Microsoft en este campo es que en vez de negar el problema y pretender que no existe, han proporcionado una herramienta para arreglarlo (también es bonito lo que hace OS X, defragmentar automáticamente un archivo al abrirlo si detecta que está fragmentado). Es como el caso de "no-tenemos-fsck-porque-nuestro-sistema-de-archivos-no-lo-necesita", puedes negar que necesitas un fsck todo lo que quieras, pero el mundo real es muy puñetero y aparecen usuarios necesitándolo. Lo mismo para los desfragmentadores.

Este tema es muy amplio (y se podría hablar de las mejoras de algoritmos que usa Ext4 y tal, y casos que no cubren), pero definitivamente no será en esta entrada, que ya es lo suficientemente larga...

Fusion, la posible venganza de AMD

Por si ustedes se han metido debajo de las piedras, hoy AMD ha mostrado al público por primera vez AMD Fusion, una mezcla de CPU + GPU, que AMD ha dado en nombrar APU (si, APU). Y esto tiene su cosa, porque el equivalente de Intel, Larrabee está más muerto que vivo, y esto puede cambiar las tornas en la eterna lucha por la dominancia entre ambas compañías.

Efectivamente, quizás no lo sepan (no se ha hablado mucho del tema), pero Larrabee, ese nombre tantas veces repetido (en este blog se le dedicaron un par de apasionados posts), ha sido -por decirlo de un modo amable- reseteado. Tal como predijeron los de Nvidia, hacer una GPU es muy diferente de hacer una CPU, e Intel no tenía experiencia y se iba a pegar. Y se la ha pegado. Como solución de emergencia, andan juntado una CPU tradicional con un chip integrados de los suyos, que sería útil si no fuera porque tienen un rendimiento mediocre. Si las operaciones en GPUs empiezan a extenderse en el software nadie va a conformarse con un chip diseñado para mostrar un escritorio Windows, Office, DVDs y juegos 3D muy simples.

AMD Fusion es diferente, es una CPU verdaderamente integrada con una GPU, hasta el punto de que comparten componentes. Las alternativas tradicionales requieren que la comunicación entre CPU y GPU se haga a través de los buses típicos (PCIE, interconexión de procesadores hypertransport), con la consiguiente latencia y consumo de energía. La GPU de un Fusion en cambio comparte el controlador de memoria con la CPU. AMD dice que la GPU usará unas partes de la memoria central, la CPU otras, y que las transferencias entre ambas son muy rápidas, sin molestias de los variados buses. No hay razones para creer que no sea así, y es de imaginar que AMD Fusion rendirá magníficos números.

AMD parece creer -o al menos lo cree el departamento de marketing que ha escrito los documentos que estoy leyendo- que la Ley de Moore se continuará cumpliendo en el futuro....con ayuda de sus APUs, es decir, no sólo añadiendo cores, o añadiendo transistores a las CPUs tradicionales, sino con GPUs. Creen que los programadores van a utilizar, vía OpenCL, masivamente los "cálculos vectoriales" SIMD, y que las APUs van a formar parte cotidiana de nuestro futuro. Los gráficos se verán beneficiados sin duda, de hecho a día de hoy no se puede tener una interfaz moderna sin ayuda de una GPU. ¿Se imaginan una pantalla táctil sin los efectos gráficos al moverse en una lista, en una web, cambiar de pantalla, etc? Hay un apartado especial para los dispositivos móviles, ya que la óptima integración permite alargar la vida de las baterías sin renunciar al rendimiento.

Todo esto es muy bonito leído así, claro. ¿Pero qué tiene esta historia de la venganza del título y de la horrible frase inicial? Pues mis elucubraciones sobre un posible retorno de AMD al liderazgo en el campo de los procesadores, perdido desde que Intel pateó al Opteron.

La compra de ATI fue considerada un gran fracaso, AMD perdió una barbaridad de millones en la operación y puso a la compañía en una posición parecida a la de Sun antes de ser engullida por Oracle. Pero si la compra fracasó desde el punto de vista financiero, la ventaja que están sacando de aquello es el liderazgo en la fusión entre GPU + CPU. Intel acaba de volver a la posición de salida, y es imposible que alcance al equipo de ATI en varios años. Nvidia hace fantásticas GPUs, y para ser competitivos han diseñado su propio SoC ARM, pero ellos no diseñan los procesadores ARMs ni tienen la gente necesaria para integrar ambos como puede hacerlo AMD....esto quiere decir que AMD no tiene ningún rival cercano en este campo, si no media una compra de Nvidia por parte de Intel. ¿Estamos ante el regreso de AMD? El tiempo lo dirá, pero al menos las cartas parecen tenerlas.

(Nota: Tambien hoy SGI anuncia que está disponible sus equipos Altix UltraViolet, de los que ya se habló en este blog hace tiempo y que están relacionados con este tema)