# Hierarchical File System

Sistema de Archivos Jerárquico o Hierarchical File System (HFS) es un sistema de archivos desarrollado por Apple Inc. para su uso en computadores que corren Mac OS. Originalmente diseñado para ser usado en disquetes y discos duros, también es posible encontrarlo en dispositivos de solo-lectura como los CD-ROMs. HFS es el nombre usado por desarrolladores, pero en la documentación de usuarios el formato es referido como estándar Mac Os para diferenciarlo de su sucesor HFS+ el cual es llamado Extendido Mac Os.

## Historia

HFS fue introducido por Apple en septiembre de 1985 para reemplazar el Macintosh File System (Sistema de Archivos Macintosh o MFS), el sistema de archivos original el cual fue introducido un año antes que los Computadores Macintosh. Desarrollado por Patrick Dirks y Bill Bruffey, HFS compartió un número de características del diseño con MFS que no estaban disponibles en otros sistemas de ficheros de aquellos tiempos (tales como FAT de DOS). Los archivos podrían tener bifurcaciones múltiples (normalmente datos y una bifurcación del recurso), lo cual permitió que el código del programa fuese almacenado por separado de recursos tales como iconos que pudiesen necesitar ser localizados. Los archivos fueron referidos con IDs únicas y los nombres del archivo podían tener 255 caracteres de largo (aunque Finder apoyó solamente un máximo de 63 caracteres).
Sin embargo MFS estaba optimizado para ser utilizado en medios de almacenamiento pequeños y lentos como los disquetes, HFS se introdujo para superar algunos de los problemas de rendimiento que llegaron con la introducción de los grandes medios de almacenamiento como los discos duros. La principal preocupación era el tiempo necesario para mostrar el contenido de un directorio. Bajo MFS toda la lista de información de los archivos y directorios era almacenada en un único archivo, que el sistema tenía que buscar para construir una lista de los archivos almacenados en un directorio particular. Esto funcionaba bien con un sistema de pocos cientos de kilobytes de almacenamiento y quizás un centenar de archivos, pero como los sistemas crecieron en megabytes y miles de archivos, el rendimiento decreció rápidamente.
La solución fue reemplazar la estructura de directorios de MFS por una más adecuada a los sistemas de ficheros más grandes. HFS sustituyó la estructura de tabla plana por el archivo de catálogo (Catalog File) que utiliza una estructura de árbol B* que puede realizar búsquedas con gran rapidez, independientemente de su tamaño.
Aunque HFS es un formato de sistema de ficheros Ben propietario, está bien documentado por lo que hay soluciones para acceder a los discos con formato HFS desde la mayoría de los sistemas operativos modernos. En 1998, Apple introdujo HFS+ para abordar la ineficacia en la asignación de espacio en disco en HFS y añadir otras mejoras. HFS es aún soportado por las versiones actuales de Mac OS, pero a partir de Mac OS X un volumen HFS no puede utilizarse para arrancar.

## Diseño

El sistema de ficheros jerárquico divide un volumen en bloques lógicos de 512 bytes. Estos bloques lógicos están agrupados juntos en bloques de asignación (allocation blocks) que pueden contener uno o más bloques lógicos dependiendo del tamaño total del volumen. HFS usa un valor de dirección de 16 bits para los bloques de asignación, limitando el número de bloques de asignación a 65.536.
Hay cinco estructuras que conforman un volumen HFS:
* Bloques lógicos 0 y 1 del volumen son los bloques de arranque, que contienen la información de inicio del sistema. Por ejemplo, el nombre del archivo de sistema y de shell (por lo general el Finder) que se cargan al iniciar.
* Bloque lógico 2 contiene el directorio MDB (Master Directory Block). Este define una amplia variedad de datos sobre el volumen en sí, por ejemplo la fecha y timestamp de cuando se creó el volumen, la localización de las otras estructuras de volumen, como el volumen del mapa de bits o el tamaño de las estructuras lógicas como los bloques de asignación. También existe un duplicado del MDB llamado Alternate MDB ubicado en el extremo opuesto del volumen en el penúltimo bloque lógico. Este se destina principalmente para uso de utilidades de disco y es solo actualizado cuando el Catalog File o el Extents Overflow File aumentan de tamaño.
* Bloque lógico 3 es el bloque de inicio del volumen del mapa de bits (Volume Bitmap), que mantiene un registro de los bloques de asignación que están en uso y de los que están libres. Cada bloque de asignación en el volumen es representado por un bit en el mapa: si el bit está activado el bloque está en uso; si está desactivado el bloque está libre para ser utilizado. Dado que el Volume Bitmap debe tener un bit para representar cada bloque de asignación, su tamaño se determina por el tamaño del volumen.
* El Extent Overflow File (Archivo de desbordamiento) es un árbol B* que contiene extensiones que registran que bloques de asignación están asignados a que archivos, una vez que las tres extensiones iniciales del Catalog File están usadas. Las versiones posteriores también añaden la capacidad de que el Extent Overflow File registre los bloques defectuosos, para evitar que el sistema de ficheros intente asignar un bloque defectuoso a un archivo.
* El Catalog File es otro árbol B* que contiene registros para todos los archivos y directorios almacenados en el volumen. Almacena cuatro tipos de registros. Cada fichero consiste en un File Thread Record y un File Record mientras que cada directorio consiste en un Directory Thread Record y un Directory Record. Los archivos y directorios en el Archivo de catálogo están identificados por un único CNID (Catalog Node ID).
** Un File Thread Record almacena sólo el nombre del fichero y el CNID de su directorio padre.
** Un File Record almacena diversidad de metadatos sobre el fichero incluyendo su CNID, el tamaño del fichero, tres timestamps (cuando se creó el fichero, la última modificación y cuando se realizó la última copia de seguridad), el primer fichero extendido de los datos y los recursos y punteros al primer dato del archivo y registros de recursos extendidos en el Extent Overflow File. El File Record también almacena dos campos de 16 Bytes que son usados por el Finder para almacenar atributos sobre el archivo incluyendo cosas como su código de creación, el tipo de código, si la ventana del fichero debería aparecer y su localización sin la ventana.
** Un Directory Thread Record almacena sólo el nombre del directorio y el CNID de su directorio padre.
** Un Directory Record almacena datos como el número de ficheros almacenados en el directorio, el CNID del directorio, tres marcas de tiempo (momento de creación, última modificación y último back up). Como el File Record, también almacena dos campos de 16 Bytes para usar por el Finder. Estos elementos almacenados como la anchura y altura y las coordenadas x e y para la ventana usada para mostrar los contenidos del directorio el modo del display (vista con iconos, vista en forma de lista, etc) de la ventana y la posición de la barra de desplazamiento de la ventana.

## Problemas

El Catalog File, que almacena todos los registros de archivos y directorios en una estructura de datos sencilla, resulta un problema de rendimiento cuando el sistema permite multitarea, solo un programa puede escribir en esta estructura a la vez, esto significa que muchos programas deben estar esperando en cola hasta que el primer programa libera el sistema. También es un problema serio de fiabilidad dañar este archivo ya que puede destruir el sistema de ficheros entero. Esto contrasta con otros sistemas de ficheros que almacenan registros de directorios y archivos en estructuras separadas (como el sistema de archivos FAT de Microsoft o el Sistema de Archivos Unix, UFS), donde tener estructuras distribuidas en todo el disco significa que dañar un directorio no es en general fatal y, posiblemente, los datos pueden ser reconstruidos con los datos de las partes no dañada.
Además, el límite de 65.535 bloques de asignación da lugar a archivos que tienen un tamaño “mínimo” equivalente a 1/65.535 del tamaño del disco. Por lo tanto, cualquier volumen, no importa su tamaño, solo puede almacenar un máximo de 65.535 archivos. Sin embargo, a cualquier archivo se le podría asignar más espacio del que necesita realmente, hasta el tamaño del bloque de asignación. Cuando los discos eran pequeños, esto no importaba mucho, porque el tamaño los bloques de asignación individuales era muy pequeño, pero como los discos empezaron a superar la marca de 1 GB, la menor cantidad de espacio que puede ocupar un archivo (un solo bloque de asignación) se convirtió en excesivamente grande, perdiendo importantes cantidades de espacio en disco. Por ejemplo, en un disco de 1 GB, el tamaño de los bloques de asignación bajo HFS es 16 KB, por lo que un archivo de 1 Byte ocuparía 16 KB de espacio de disco. Este problema fue menor para los usuarios que tenían grandes archivos en un menor volumen, porque ocupan mucho menos espacio que si residieran en una gran partición. El mismo problema existe en el sistema de archivos FAT16.