Fragmentación de un sistema de ficheros

En computación, fragmentación de un sistema de ficheros, muchas veces llamado envejecimiento de un sistema de fichero, es la incapacidad de un sistema de ficheros de colocar datos de manera secuencial (uno al lado del otro), un fenómeno inherente en almacenamiento de respaldo de sistema de ficheros que permiten en el lugar, la modificación de su contenido. Es un caso especial de fragmentación de datos. La fragmentación de un sistema de fichero aumenta el desplazamiento del cabezal o búsquedas, las cuales son conocidas por dificultar el rendimiento. La eliminación de la fragmentación se basa en reorganizar los ficheros y los espacios vacíos en áreas continuas, este proceso es conocido como desfragmentación.

Causa

Cuando un sistema de ficheros es primeramente inicializado en una partición (la partición esta formateada para el sistema de ficheros), la partición contiene una pequeña cantidad de estructuras internas mientras que todo lo demás es un bloque continuo de espacios vacíos.^[1]​ Esto significa que el algoritmo que ubica los datos es completamente libre de colocar los nuevos ficheros en cualquier lugar de la partición. Por un tiempo después de la creación de la partición, los archivos en sistema de ficheros pueden ser ubicados bastante cerca de forma óptima. Cuando el sistema operativo y las aplicaciones son instaladas u otros ficheros son desempacados, ubicando ficheros distintos de manera secuencial, esto también significa que los ficheros relacionados son ubicados relativamente cerca unos de otros.

Sin embargo, cuando son eliminados o truncados archivos escritos en disco, se crean nuevas regiones de espacios vacíos. Cuando se añaden archivos existentes, resulta casi imposible continuar escribiendo exactamente donde el fichero solía terminar, así como ubicar otro fichero en ese espacio — por lo tanto, hay que localizar un nuevo fragmento vacío donde se pueda escribir. Con el transcurso del tiempo se repite una y otra vez el ejemplo anterior, fragmentando cada vez más los espacios vacíos. Al existir pequeñas regiones vacías, se vuelve imposible ubicar nuevos archivos de manera secuencial, y se ve obligado a partir la información en fragmentos. Esto ocurre sobre todo cuando un sistema de ficheros está muy lleno — no existen casi regiones continuas de espacios vacíos.

Note que lo siguiente es una simplificación de otro complicado tema. El método explicado anteriormente ha sido la práctica más común desarrollada por los sistemas de ubicación de ficheros en disco y otros almacenamientos con accesos aleatorios por más de 30 años. Algunos sistemas operativos simplemente no colocan los archivos uno a continuación del otro, mientras otros usan varios métodos para prevenir la fragmentación, pero en general, tarde o temprano, en sistemas donde los ficheros son eliminados o aumentados con frecuencia, aparece la fragmentación. Considere el siguiente escenario:

Un nuevo disco contiene 5 archivos salvados, nombrados A, B, C, D y E, y cada archivo usa 10 bloques de espacio (en este ejemplo el tamaño del bloque no tiene importancia). Como el espacio vacío es continuo, los ficheros son ubicados uno de tras del otro (Ejemplo (1).)

Si el fichero B es eliminado, se crea una nueva región vacía de 10 bloques y el disco se fragmenta. El sistema de ficheros podría desfragmentar el disco inmediatamente después de la eliminación pero esto traería un aumento del rendimiento que podría ser fatal en cualquier momento; pero en general los espacios vacíos simplemente se dejan ahí y se marcan en una tabla como disponibles para usarlos en caso de necesitarlo el sistema^[2]​ (Example (2).)

Ahora, si un nuevo fichero requiere 7 bloques de espacio, puede ser ubicado en los 7 primeros bloques del espacio que contenía el fichero B y los 3 últimos bloques siguen estando disponibles (Ejemplo (3).) Si otro fichero nuevo G es añadido y solamente necesita 3 bloques, este puede ser ubicado entre F y C (Ejemplo (4).)

Si más tarde F aumenta, como el espacio que le sigue está ocupado por G, tiene 3 opciones: (1) añadir un nuevo bloque en cualquier lugar e indicar que F tiene una segunda ubicación, (2) mover los archivos a otro sitio para que F pueda tener todos sus datos de manera secuencial; o (3) mover el archivo F a una región más grande para que todos sus datos estén continuos. La segunda opción es casi impracticable por razones de rendimiento, al igual que en la tercera cuando el fichero es muy extenso. Por lo que la práctica usual es simplemente crear una regiónen otro sitio y asociarla con la vieja (Ejemplo (5).)

Los datos añadidos al final del fichero F formarían parte de la misma región. Pero si fueran tantos datos que no caben en ningún espacio, entonces se tendría que crear otra región, y así sucesivamente. Eventualmente el sistema de ficheros tendrá segmentos libres en muchos lugares y algunos ficheros tendrán que ser esparcidos por muchas regiones. Consecuentemente, el tiempo de acceso a esos ficheros será demasiado largo.

Para resumir, los factores que causan o que facilitan la fragmentación son:

• poco espacio libre.
• muchas eliminaciones, truncamientos o extensiones de ficheros.
• abuso de ficheros esparcidos.

Consecuencias de rendimiento

La fragmentación del sistema de ficheros está proyectada a convertirse en una problemática mayor con el hardware novedoso debido al incremento de la disparidad entre la velocidad de los accesos secuenciales y las rotaciones latentes (y a un tiempo de búsqueda inferior), el grado de consumo del disco duro,^[3]​ en donde los sistemas de ficheros son usualmente ubicados. Así, la fragmentación se ha convertido en un problema importante en las recientes investigaciones y diseños de sistemas de ficheros. La eliminación de la fragmentación no solo depende del formato en disco del sistema de ficheros, sino también de la implementación.^[4]​

En los estándar de comparación de un sistema de ficheros sencillo, el factor de fragmentación es usualmente omitida, debido a lo complicado de modelarla. Mejor dicho, para simplificar la comparación, los estándares de comparación de los sistemas de ficheros usualmente corren sobre un sistema de ficheros vacío, y naturalmente los resultados pueden variar considerablemente con los patrones de acceso en tiempo real.^[5]​

La fragmentación de los sistemas de ficheros tiene un menor impacto a causa del rendimiento de los dispositivos de estados sólidos, ya que el tiempo de búsqueda no está involucrado con el dispositivo de rotación, por otra parte, las operaciones no secuenciales E/S adicionales influyen en el rendimiento del sistema, y muchas arquitecturas de sistemas de ficheros consumen recursos internos adicionales cuando hay presencia de la fragmentación.^{[cita requerida]}

Tipos de fragmentación

La fragmentación puede ocurrir en diferentes niveles:

• Fragmentación dentro de ficheros individuales y sus metadatos.
• Fragmentación de espacios libres, haciendo más complicado poner los nuevos archivos contiguamente.
• La disminución de las referencias locales entre ficheros separados y a la vez relacionados.

Fragmentación de ficheros

La fragmentación individual de ficheros ocurre cuando un solo fichero ha sido picado en diferentes pedazos (llamados extensiones en un sistema de ficheros basado en regiones). Aunque el sistema de ficheros del disco intente mantener ficheros individuales contiguos, esto se convierte en casi imposible sin afectar de manera significante el rendimiento. El chequeo de los sistemas de ficheros y las herramientas de desfragmentación solamente tienen en cuenta para la fragmentación de ficheros sus estadísticas de porcentajes de fragmentación.

Fragmentación de espacios libres

La fragmentación de los espacios libres (disponibles) ocurre cuando existen muchas áreas sin usar del sistema de ficheros donde nuevos archivos o metadatos pueden ser escritos. La fragmentación de espacios libres no deseada es causada generalmente debido a eliminaciones o truncamientos de archivos, por otra parte, el sistema de ficheros puede intencionalmente insertar fragmentos ("burbujas") de espacios libres para facilitar la ampliación de los ficheros cercanos (vea cómo prevenir la fragmentación abajo).

Dispersión de ficheros

La segmentación de ficheros, también conocida como fragmentación de ficheros relacionados, o fragmentación nivel-aplicación (fichero), significa a la ausencia local de referencias (dentro del medio de almacenado) entre los ficheros relacionados (vea secuencia de ficheros para más detalles). A diferencia de los dos tipos anteriores de fragmentación, la dispersión de ficheros es un concepto mucho más ambiguo, en gran medida a que depende del patrón de acceso de una aplicación específica. Esto también hace muy complicado una medida objetiva o una estimación adecuada. Sin embargo, de manera dudosa, es el tipo más crítico de fragmentación, algunos estudios han encontrado que los mayores archivos accedidos frecuentementetienden a ser menor comparado con lacantidad de datos disponibles por segundo del disco.^[6]​

Para evitar la fragmentación de los archivos relacionados y mejorar el lugar de las referencias (en este caso llamado contigüidad de ficheros), se han tenido que hacer suposiciones sobre la operación de las aplicaciones. Una suposición que se hace con mucha frecuencia es la que vale la pena mantener los archivos pequeños juntos en un solo directorio, y ponerlos en el orden natural del sistema de ficheros. Aunque esta es una suposición bastante razonable, hay veces que no puede mantenerse. Por ejemplo, una aplicación puede leer muchos archivos diferentes, a lo mejor en diferentes directorios, en el mismo orden en que fueron escritos. De esa manera, un sistema de ficheros que ordena simplemente todas las escrituras sucesivamente, debe puede funcionar más rápido la aplicación dada.

Técnicas para mitigar la fragmentación

Muchas técnicas han sido desarrolladas para combatir la fragmentación. Usualmente pueden ser clasificadas en dos categorías: preventivas y retroactivas. Debido a la dificultad de la predicción en los accesos estás técnicas, la mayoría de las veces, una heurística natural que puede disminuir el rendimiento bajo volúmenes de trabajo inesperados.

Prevención de la fragmentación

Las técnicas preventivas tratan de mantener la fragmentación lo menor posible al tiempo que los datos están siendo escritos en disco. Se basa en la adición de datos a un fragmento existente ubicado en cualquier lugar posible, en vez de ubicar nuevos bloques a un nuevo fragmento.

Muchos de los sistemas de ficheros intentan preubicar largos trozos, o trozos de diferentes fragmentos de espacios vacíos. Esto permite la fragmentación de ficheros cuando muchos archivos están siendo añadidos concurrentemente, permitiendo un trenzado excesivo.^[4]​

Si el tamaño final de un archivo sujeto a modificaciones es conocido, el almacenamiento para todo el fichero tiene que ser pre asignado. Por ejemplo, el intercambio de ficheros de Microsoft Windows (archivo de paginación) es ajustado dinámicamente por debajo de una aplicación normal, y muchas veces se fragmenta bastante. Esto puede ser prevenido especificando un archivo de paginación con las mismos tamaños (mínimos y máximos), pre asignando efectivamente el archivo entero. BitTorrent otras aplicaciones de intercambio punto a punto limitan la fragmentación pre asignando el espacio completo necesitado por el fichero cuando es iniciada la descarga.^[7]​

Una técnica relativamente reciente se basa en la asignación retardada en XFS, HFS+^[8]​ y ZFS; Cuando un sistema de ficheros está escribiendo, los bloques del sistema son reservados, pero las ubicaciones de algunos ficheros específicos no son colocadas en el momento.Más tarde, cuando un sistema de ficheros está forzado a mezclar cambios como resultado de la presión de la memoria o de una transacción realizada, el asignador tendrá mucho más conocimiento acerca de las características de los ficheros. Muchos sistemas de ficheros que aprovechan esto tratan de colocar ficheros de manera contigua en un solo directorio. Asumiendo que las lecturas múltiples desde un solo directorio son comunes, se mejora el lugar de las referencias.^[9]​ Reiser4 también ordena el diseño de los archivos de acuerdo a una tabla de hash del directorio, para que cuando los ficheros están siendo accedidos en el orden natural del sistema de ficheros (como manda el readdir), sean leídos siempre de manera secuencial.^[10]​

Eliminación de la fragmentación

Las técnicas retroactivas intentan reducir la fragmentación, o por lo menos los efectos negativos de la fragmentación después de haber ocurrido. Muchos sistemas de ficheros proveen herramientas de desfragmentación, las cuales intentan reordenar los fragmentos de los ficheros, y a veces también disminuyen su dispersión (mejorando su contigüidad o el lugar de las referencias) manteniendo los ficheros más pequeños en directorios, o en árboles de directorios, o incluso con secuencias de ficheros cercanos unos de otros.

El sistema de ficheros HFS+ desfragmenta de manera transparente ficheros menores que 20MiB y los rompe en 8 o más fragmentos, cuando el archivo se está abriendo.^[11]​

El ahora obsoleto Commodore Amiga Sistema de Fichero Inteligente (SFS por sus siglas en inglés) desfragmenta mientras el sistema de ficheros esta en uso. El proceso de desfragmentación es completamente apátrida (aparte del lugar donde está funcionando), para que no pueda ser detenido ni arrancado de manera instantánea. Durante la desfragmentación de los datos, la integridad de los metadatos y los datos normales es garantizada.

Véase también

• Fragmentación
• Desfragmentación
• Sistema de ficheros
• Anexo:Programas de desfragmentación
• Cercanía de referencias

Referencias

1. Some file systems, such as NTFS and ext2+, might preallocate empty contiguous regions for special purposes.
2. The practice of leaving the space occupied by deleted files largely undisturbed is why undelete programs were able to work; they simply recovered the file whose name had been deleted from the directory, but whose contents were still on disk.
3. Dr. Mark H. Kryder (3 de abril de 2006). «Future Storage Technologies: A Look Beyond the Horizon» (PDF). Seagate Technology. Archivado desde el original el 17 de julio de 2006. Consultado el 14 de diciembre de 2006. 
4. L. W. McVoy, S. R. Kleiman (1991 winter). «Extent-like Performance from a UNIX File System». Proceedings of USENIX winter '91. Dallas, Texas: Sun Microsystems, Inc. pp. pages 33-43. Consultado el 14 de diciembre de 2006. 
5. Keith Arnold Smith (2001-01). Workload-Specific File System Benchmarks (PDF). Harvard University. Archivado desde el original el 17 de noviembre de 2004. Consultado el 14 de diciembre de 2006. 
6. John R. Douceur, William J. Bolosky (1999-06). «A Large-Scale Study of File-System Contents». ACM SIGMETRICS Performance Evaluation Review (Microsoft Research) 27 (1): 59-70. doi:10.1145/301453.301480. 
7. Jeff Layton (29 de marzo de 2009). From ext3 to ext4: An Interview with Theodore Ts'o. Linux Magazine. Archivado desde el original el 27 de mayo de 2015. Consultado el 20 de diciembre de 2012. 
8. Amit Singh (2004-05). «Fragmentation in HFS Plus Volumes». Mac OS X Internals. Archivado desde el original el 12 de mayo de 2015. Consultado el 20 de diciembre de 2012. 
9. Adam Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, Geoff Peck (1996-01). «Scalability in the XFS File System». Proceedings of the USENIX 1996 Annual Technical Conference. San Diego, California: Silicon Graphics. Consultado el 14 de diciembre de 2006. 
10. Hans Reiser (6 de febrero de 2006). «The Reiser4 Filesystem» (Google Video). A lecture given by the author, Hans Reiser. Archivado desde el original el 19 de mayo de 2011. Consultado el 14 de diciembre de 2006. 
11. Amit Singh (19 de junio de 2006). «The HFS Plus File System». Mac OS X Internals: A Systems Approach. Addison Wesley. ISBN 0-321-27854-2. 

• Datos: Q4089244