X
  • ZFS
    May 28, 2008

Mapas espaciales

Guest Author


Cada sistema de archivos debe registrar rigurosamenten dos cosas básicas: la ubicación de los datos y la ubicación del espacio libre.

En principio, no parece estrictamente necesario saber dónde está el espacio libre: cada bloque está libre o asignado, de modo que el espacio libre se puede calcular si suponemos que todo es espacio libre al que se le va restando cada asignación. Para calcular el espacio asignado basta recorrer el sistema de archivos desde la raíz; todo bloque que no se pueda encontrar al atravesar el espacio desde la raíz es, por definición, libre.

En la práctica, esta forma de localizar espacio libre sería insufrible porque cualquier sistema de archivos de un cierto tamaño tardaría una eternidad en averiguarlo. Para agilizar la asignación y liberación de bloques, el sistema de archivos necesita un método eficaz que le permita controlar la cantidad de espacio libre. En esta entrega examinaremos los métodos más comunes, las razones que dificultan su escalabilidad y los nuevos enfoques que se divisan para ZFS.

Mapas de bits

La forma más frecuente de representar el espacio libre es mediante un mapa de bits, o lo que es igual, una matriz de bits en la que el enésimo bit indica si el enésimo bloque está asignado o libre. El gasto general de un mapa de bits es bastante bajo: 1 bit por bloque. Para un bloque de tamaño 4 K, serían 1/(4096\*8) = 0,003% (el 8 viene de 8 bits por byte).

Para un sistema de archivos de 1 GB, el mapa de bits es de 32 KB -- algo que encaja fácilmente en memoria y que se pueden escanear rápidamente para liberar espacio en disco. Para un sistema de archivos de 1 TB, el mapa de bits es de 32 MB -- todavía se puede encajar bien en memoria, pero ya no es tan pequeño ni tan rápido de escanear. Para un sistema de archivos de 1 PB, el mapa de bits es de 32 GB y, sencillamente, eso ya es algo que no cabe en la memoria de la mayoría de máquinas, además de que para escanear el mapa de bits haría falta leerlo desde el disco... y eso sí que resulta mucho más lento aún.

Está claro que esto no es escalable en absoluto.

Una solución aparentemente fácil podría ser dividir el mapa de bits en trozos pequeños y seguir la pista del número de bits de cada trozo. Por ejemplo, para un sistema de archivos de 1 PB con bloques de 4 K, se podría dividir el espacio libre en un millón de mapas de bits de 32 KB cada uno. La información resumida (el millón de enteros indicando la cantidad del espacio de cada mapa de bits) cabe en la memoria y eso hace que sea fácil encontrar un mapa de bits con espacio libre y que sea rápido escanear el mapa de bits.

Pero sigue habiendo un problema fundamental: el mapa de bits debe actualizarse no sólo cada vez que se asigna un nuevo bloque, sino también cada vez que se libera un bloque antiguo. El sistema de archivos controla la ubicación de todas las asignaciones (decide en qué bloques se colocan los datos), pero no tiene ningún control sobre la ubicación de los libres. Algo tan simple como 'rm -rf' puede hacer que se liberen bloques por todo el disco. Con nuestro sistema de archivos de 1 PB del ejemplo, en el peor de los casos, la supresión de 4 GB de datos (un millón de bloques de 4 K) supondría leer cada mapa de bits del millón, modificarlo y escribirlo de nuevo. Total, dos millones de E/S en el disco para liberar apenas 4 GB -- es poco razonable, incluso en el peor de los casos de comportamiento.

Más que ningún otro factor, esta es la razón de que los mapas de bits no sean escalables: por lo general, el espacio se libera aleatoriamente y los mapas de bits que no encajan en memoria ofrecen un comportamiento patológico cuando se accede a ellos de forma aleatoria.

Árboles B

Otro modo frecuente de representar el espacio libre es con un árbol B de inserciones. Una inserción es una región contigua de espacio libre descrita mediante dos enteros: desviación y longitud. El árbol B ordena las inserciones por desviación para lograr una asignación eficaz del espacio contiguo. Desafortunadamente, los árboles B de inserciones sufren la misma patología que los mapas de bits cuando deben enfrentarse a liberaciones aleatorias.

¿Qué hacer entonces?

Liberaciones diferidas

Una forma de mitigar la patología de las liberaciones aleatorias consiste en aplazar la actualización de los mapas de bits o los árboles B, y mantener una lista de los bloques liberados recientemente. Cuando la lista alcanza un tamaño determinado, se puede ordenar, en memoria, y liberarse luego en los mapas de bits o árboles B subyacentes cuya ubicación sea algo mejor. No es ideal, pero ayuda.

¿Y si llegamos más lejos?

Mapas espaciales: listas de registros estructurados libres

Recordemos que los sistemas de archivos con registros estructurados plantearon esta pregunta hace tiempo: ¿y si, en lugar de devolver periódicamente un registro de transacciones al sistema de archivos hacemos que el registro de transacciones sea el sistema de archivos?

Bueno, esta misma pregunta podría aplicarse a nuestra lista de liberaciones diferidas: ¿y si en lugar de devolver la lista a un mapa de bits o un árbol B hacemos que la lista de liberaciones diferidas sea la representación del espacio libre?

Esto es precisamente lo que hace ZFS, divide el espacio de cada dispositivo virtual en varios cientos de regiones llamadas metaslabs. Cada metaslab lleva asociado un mapa espacial en el que se describe el espacio libre que contiene. El mapa espacial no es sino un registro de asignaciones y espacios libres ordenados por tiempo, que libera espacio aleatoriamente con la misma eficacia que si lo hiciera de forma secuencial; la razón es que, sea cual sea la inserción que libera, la representa en el disco añadiendo la inserción (un par de enteros) al objeto de mapa espacial -- y estos añadidos son perfectamente localizables. De igual modo, las asignaciones se representan en el disco como inserciones añadidas al objeto de mapa espacial (por supuesto, con un conjunto de bits que las identifica como una asignación, no como espacio libre).

Cuando ZFS decide asignar bloques a un determinado metaslab, primero lee el mapa espacial del metaslab en el disco y reproduce las asignaciones y los espacios libres en un árbol AVL de memoria con el espacio libre ordenado por el número de desviación. El resultado es una representación compacta del espacio libre que admite la asignacion eficaz de espacios contiguos. ZFS aprovecha también la ocasión para condensar el mapa espacial: si hay muchos pares de asignación libres para cancelar, ZFS sustituye el mapa espacial del disco por una versión más pequeña en memoria.

Los mapas espaciales tienen algunas propiedades bastante curiosas:

  • No es necesario inicializarlos: un mapa espacial sin entradas indica que no hay asignaciones ni espacios libres, por lo que todo es espacio libre.

  • Son escalables: los mapas espaciales sólo añaden, y sólo el último bloque del objeto de mapa espacial necesita estar en memoria para poder garantizar un rendimiento excelente sin importar la cantidad de espacio que gestionen.

  • No tienen patologías: los mapas espaciales son capaces de actualizar el espacio eficazmente al margen de cualquier patrón de asignaciones y liberaciones.

  • Son igualmente eficaces en la localización de espacio libre, tanto si el lugar de almacenamiento está lleno como vacío (a diferencia de los mapas de bits que tardan más en escanear a medida que se va ocupando el espacio).

Por último, señalar que cuando un mapa espacial se llena por completo aparece representado por una única inserción. Es decir, los mapas espaciales poseen la atractiva propiedad de que a medida que su capacidad de almacenamiento se aproxima al 100%, comienzan a evaporarse y permiten aprovechar hasta la última gota de espacio disponible.

Be the first to comment

Comments ( 0 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.Captcha