Btrfs: Una jungla de B-Trees

Este artículo describe la estructura interna de Btrfs, enfocado en su B-Tree y en como ha sido combinado en muchas y variadas formas para llegar a implementar la funcionalidad completa de un sistema de archivos de última generación. El texto es largo, pero bastante completo.

Introducción

Btrfs es un alias de "B-tree filesystem". La referencia a los B-trees podría parecer poco importante, los sistemas de archivos (en adelante SdA) y bases de datos los utilizan desde hace décadas. Pero no es casual que Btrfs tenga ese nombre, su estructura está muy influenciada por este concepto y, en realidad, es la característica que mejor lo define y diferencia de otros SdA, incluso de ZFS.

Siendo más concretos, Btrfs no implementa un B-tree tradicional, ya que son poco apropiados para técnicas de COW y snapshots y requerimientos de escalabilidad. ZFS optó, debido a ello, por una técnica inspirada en el slab. Btrfs no ha ido por el mismo camino, escogió otro a raiz de una conferencia para desarrolladores de SdA Linux celebrada en Febrero del 2007. Allí, un tal Ohad Rodeh, trabajador de IBM en sus laboratorios de I+D en Israel, presentó un nuevo tipo de B-tree optimizado para técnicas de COW y snapshots con escalabilidad y snapshots muy eficientes -tanto en términos de tiempo como de espacio-. De hecho presentó sus algoritmos como una ayuda para aquellos interesados en crear algo equivalente a ZFS/WAFL en Linux. Chris Mason, que había trabajado en Reiserfsv3, tomó nota y e implementó esa técnica, y de ahí el código evolucionó hasta convertirse en Btrfs. Queda claro que para comprender cómo funciona Btrfs hay que comprender cómo funciona su B-tree.

El B-tree: nodos e ítems

Los B-trees utilizados en SdA solamente almacenan datos en las hojas del extremo del árbol, concretamente en los ítems. Cada hoja puede contener varios ítems. El resto de nodos solo se utilizan para crear rutas hacia los ítems. Todos los B-trees se ordenan respecto a una clave, la que el programador decida, en el caso de Btrfs es esta:

struct btrfs_key {
u64 objectid;
u8 type;
u64 offset;
}

El primer campo, objectid, de 64 bits, es un identificador de objecto, único para cada objeto (pero un objeto puede estar compuesto por varios ítems, asi que puede haber varios ítems con el mismo objectid). Luego tenemos type, de 8 bits, que indica el tipo de item, es decir, el tipo de datos que contiene. offset indica una posición dentro del SdA (su uso concreto depende del tipo de ítem).

Tanto los ítems como los nodos tiene esta clave, sin embargo, ya se dijo que los nodos solo crean rutas hacia los ítems, por lo que a la clave solo añaden un puntero de 64 bits que indica dónde se encuentra el siguiente nodo/ítem en la estructura. Los ítems por su parte a la clave añaden alguna cosa más:

struct btrfs_item {
struct btrfs_key key;
u32 offset;
u32 size;
}

La clave tan solo identifica al ítem, no es el ítem en sí. En esta estructura se indica, en offset, la localización del ítem en la hoja del B-Tree, y en size su tamaño. Este offset es distinto del offset de la clave, que indicaba una posición absoluta en el SdA. Así es como se agrupan en una hoja los ítems:

[Struct Item0 | Struct Item1 | Struct Item2 | ... |Item2    |Item1 |Item0          ]

El espacio entre paréntesis representa una hoja del árbol. Como se ve, las estructuras que describen los ítems (struct btrfs_item) se agrupan al principio del bloque, y el item de verdad, cuyo tamaño varía dependiendo del tipo de objeto, se encuentra al final, esa localización es la que indica el offset de la estructura btrfs_item. Esta organización responde a motivos de eficiencia. Un detalle curioso es que en el caso de archivos pequeños, los ítems correspondientes al archivo almacenan los datos directamente en el ítem (idea derivada del "tail packaging del reiser v3), permitiendo así un acceso rápido a archivos pequeños.

Esta es una descripción quizás más detallada de lo necesario. Como resumen, lo único que hay que tener presente por encima de todo es que se trata de un B-Tree cuyos ítems se identifican con un identificador de objeto objectid de 64 bits y cuyo formato es especificado por el campo type.

Btrfs utiliza este B-Tree para almacenar todo tipo de cosas en forma de ítems: inodos, atributos extendidos, directorios, snapshots...cada elemento con un objectid independiente y un type que indique lo que son. Esto simplifica la implementación del SdA, pues cualquier operación termina siendo una búsqueda, inserción, modificación o eliminación de ítems de un B-Tree. El código se encuentra en el archivo fs/btrfs/ctree.c, y se encarga de hacer todas las modificaciones de bajo nivel, de rebalancear el árbol cuando es necesario, de aplicar COW, etc, todo automáticamente, sin que las otras capas del SdA tengan que preocuparse de ello.

Un bosque de B-trees: Root B-Tree

Una vez que se conoce el B-Tree, entender el funcionamiento de Btrfs es relativamente simple, solo hay que comprender las ramificaciones y combinaciones de sus conceptos básicos.

Todo SdA tiene un superbloque, es la primera estructura que se lee y la que describe las ubicaciones de todas las demás. Es tambien la única que tiene una localización fija en el disco, todas las demás pueden estar en cualquier parte. El superbloque tiene el formato de la estructura struct btrfs_super_block, que no se muestra aquí debido a su extensión. De sus campos destacaremos csum, que al igual que el csum de struct btrfs_header sirve para detectar corrupción. Y los mas importantes: root y chunk_root, de 64 bits, que indican la localización de dos B-Trees.

¿Dos B-Trees? Si, Btrfs tiene varios. De hecho, el B-Tree root es en realidad la raiz de raices, un árbol que almacena punteros a otros árboles. Actua, por así decirlo, como una especie de directorio de B-Trees.

Una gran ayuda para entender más visualmente Btrfs es la herramienta btrfs-debug-tree, que muestra la estructura del árbol. En el caso de Root tree la salida de btrfs-debug-tree correspondiente es:

root tree
leaf 29364224 items 9 free space 2349 generation 7 owner 1
fs uuid 56650d3d-a7bf-463c-a59f-fc87a454d47e
chunk uuid e7457d2d-b783-4cb1-9f43-aa4843ab02fd
  item 0 key (EXTENT_TREE ROOT_ITEM 0) itemoff 3756 itemsize 239
      root data bytenr 29368320 level 0 dirid 0 refs 1
  item 1 key (DEV_TREE ROOT_ITEM 0) itemoff 3517 itemsize 239
      root data bytenr 29372416 level 0 dirid 0 refs 1

En la primera línea se indica que es el Root tree, la segunda indica el comienzo de una hoja, el número total de ítems que contiene y el espacio libre que le queda para albergar más, y otros datos irrelevantes. La tercera y la cuarta indican las UUIDs del SdA y del Chunk tree (hablaremos de él más adelante). Tras ellos, los ítems. Los datos de la clave son los que están entre paréntesis, y a continuación de éste, el tamaño del ítem y su offset dentro de la hoja. Centrándonos en la clave, presentada en formato (objectid, type, offset), vemos que ambos ítems son de tipo ROOT_ITEM (un tipo de ítems que almacenan información sobre la ubicación de otros B-Trees), y sus objectid indican el tipo de árbol, Extent tree y Device tree respectivamente. Esos objectids presentados en forma de constantes pertenecen a unos rangos reservados. El offset, como vemos, no se utiliza. En la segunda línea de cada item, vemos el texto "root data bytenr", que quiere decir "byte donde se encuentra el inicio del B-Tree". El resto de datos se pueden obviar.

Device Tree

Btrfs no utiliza todo el espacio de un dispositivo tras añadirlo al SdA, sino que utiliza una parte y, según va requiriéndolo, recurre al resto. El Device tree, escogido a propósito del ejemplo anterior, sirve para almacenar información sobre qué partes del dispositivo están siendo utilizadas. Por razones que veremos más adelante, este espacio utilizado no se describe como un solo rango, se divide en varios rangos más pequeños, uno trás de otro. Estos son los ítems.

device tree key (DEV_TREE ROOT_ITEM 0)
leaf 29372416 items 7 free space 3484 generation 5 owner 4
fs uuid 56650d3d-a7bf-463c-a59f-fc87a454d47e
chunk uuid e7457d2d-b783-4cb1-9f43-aa4843ab02fd
  item 0 key (1 DEV_EXTENT 0) itemoff 3947 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 0 length 4194304
  item 1 key (1 DEV_EXTENT 4194304) itemoff 3899 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 4194304 length 8388608
  item 2 key (1 DEV_EXTENT 12582912) itemoff 3851 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 12582912 length 8388608

Los ítems tienen claves con el type DEV_EXTENT (alias de "extent de dispositivo", o sea, rango continuo de bloques en un dispositivo). Su objectid es el identificador de dispositivo al que se hace referencia, que es 1 para el primer dispositivo. Este extraño uso del objectid clarifica cómo usa Btrfs sus diversos B-Trees: Cada uno se utiliza de una forma distinta, o más bien, cada árbol utiliza solo unos tipos concretos de ítems relacionados con su función. El offset indica la parte del disco que se quiere describir, y en los datos del item se indica el tamaño que abarcará esa parte (length), además de repetirse el offset(chunk offset). La primera línea tras cada ítem puede pasarse por alto.

Chunk Tree

El Chunk tree ya se mencionó antes, era aquel cuya posición está especificada en el campo chunk_root del superbloque. Su función es traducir entre el direccionamiento lógico del SdA y el direccionamiento físico del disco. Esto es necesario y se hace en todos los SdA: consideremos un SdA creado en una partición que se encuentra en la mitad del disco, su byte cero podría ser el byte 100.000.000 del disco. En Btrfs esa diferenciación es aun más necesaria, ya que un SdA se expande a varios discos simultaneamente, cada uno con su propio direccionamiento físico.

Es debido a esta función de traducción de direcciones lógicas a físicas que la ubicación del Chunk tree se encuentre en el propio superbloque: para encontrar la ubicación física del Root tree es necesario leer primero el Chunk tree. ¿Y la dirección del propio Chunk tree? Tambien se expresa en direcciones lógicas, asi que el superbloque duplica en su estructura una pequeña parte de información para poder encontrarlo.

Decíamos que el Chunk tree mantiene esas equivalencias lógico<->físicas no en forma de un solo gran rango, sino dividido en trozos (chunks, en inglés). Esos chunks suelen tener entre 256MB y varios GB. ¿De dónde se saca información sobre las direcciones físicas de los dispositivos? Del Device tree, naturalmente. Ya dijimos que ese B-Tree tampoco se definía en un solo gran rango, sino en varios. Y es que el principio y el final de los chunks coinciden exactamente con el principio y fin de los rangos del Device Tree. Un chunk es, por tanto, la representación lógica de una porción de disco.

En este árbol los ítems tienen el type CHUNK_ITEM, que indica que es un ítem con información sobre un chunk. El objectid siempre se asigna al valor de FIRST_CHUNK_TREE (se podría decir que en este caso no se utiliza). El offset indica la dirección lógica inicial del rango con el que se pretende tener una equivalencia física. En el ítem se indica el dispositivo donde éste se encuentra y el comienzo de su dirección física.

FS Tree

Este B-Tree se encarga de almacenar lo que se definiría tradicionalmente como metadatos: Nombres de los archivos y de los directorios, los inodos, información de los atributos extendidos, extents; se trata de la concepción más cercana que la gente tiene del interior de un SdA.

Los ítems de este árbol son algo complejos y de muchos tipos. En Unix, como es sabido, cada archivo tiene su correspondiente inodo, en el FS tree cada archivo tiene varios items, todos con el objectid de su inodo: uno del tipo INODE_ITEM que describe el tamaño y los permisos de acceso de ese archivo, otro de tipo INODE_REF que describe el nombre y número de inodo del directorio en el que se halla, otro EXTENT_DATA que describe la ubicación de los datos del archivo, en el caso de tenerlos. Los directorios, por su parte, tienen tambien varios ítems con el objectid de su inodo, uno de tipo INODE_ITEM, otro de tipo INODE_REF y, por cada archivo que haya dentro del directorio, dos items, uno del tipo DIR_ITEM y otro del tipo DIR_INDEX, ambos conteniendo el nombre y número de inodo de cada archivo correspondiente (la razón de que haya dos ítems por cada archivo se debe a la deficiencia de ciertas APIs de Unix, otros SdA han tenido que hacer cosas similares)

Los items del tipo EXTENT_DATA son los que informan de la ubicación de los datos de los archivos, es decir extents. Contienen en su interior la dirección lógica donde empiezan los datos del archivo, la extensión del extent, si el extent está comprimido, etc.

Extent Allocation Tree

Este es una especie de gestor de espacio libre de Btrfs. Es equivalente a los free space map de otros SdA. En realidad el nombre correcto de este árbol debería ser "used space tree", guarda información sobre las partes de los chunks que están usadas usadas. Se podría decir que su nombre despista un poco.

Este árbol no se toca para nada cuando se leen archivos. El proceso de lectura de un archivo consiste en buscar el archivo en el FS tree, y los ítems indicarán la dirección del disco en la que se encuentran los datos. Btrfs entonces solo tiene que mirar al Chunk tree para saber en qué dispositivo y en qué dirección física tiene que empezar a leer. Solo cuando se añaden, modifican o borran datos es necesario marcar en el Extent tree las partes de espacio que se van a usar, o a liberar las que estaban usadas.

Aparte de esa información, en éste árbol se forman una especie de "grupos de bloques" lógicos, que hacen referencia a grandes extents lógicos de los chunks. El objeto de estos "grupos de bloques" es subdividir el espacio disponible en partes que pueden ser dedicadas a los datos o a los metadatos. Esto se utiliza para poder agrupar separar los datos y los metadatos en chunks distintos.

Checksum tree

Este es el último B-tree. Como su nombre indica, almacena los checksums. Cada item, de type EXTENT_CSUM, contiene el número del byte de cada extent y su checksum.

Subvolúmenes y snapshots

Antes de hablar de estos conceptos, hay que definirlos y diferenciarlos. El snapshot es bien conocido, se trata de una copia idéntica del SdA en el momento en que se toma y que se mantiene inalterado con el tiempo. El subvolumen es un concepto menos conocido: se trata de una especie de nuevo SdA, pero un SdA nuevo de acuerdo con la gestión el espacio en forma de pool. Es decir, no un SdA literalmente aparte, sino uno obtenido del pool.

Un subvolumen vacío no tiene nada dentro, solo los directorios "." y "..". Puede montarse en cualquier directorio. De hecho, existe un subvolumen en todo SdA nuevo llamado "default", que es el que se crea y usa por defecto. Un subvolumen puede tener configurado un límite de espacio, de modo que puede utilizarse como un sustituto de las tradicionales quotas, creando en /home un subvolumen para cada usuario con un límite de espacio determinado.

Sin embargo, internamente subvolúmenes y snapshots son la misma cosa: un FS tree. Uno por cada subvolumen o snapshot. Se diferencian en que el subvolumen es un FS tree vacío, sin archivos ni directorios, mientras que el snapshot tiene ya un montón de archivos y directorios. En realidad los snapshots inicialmente comparten su FS tree con el subvolumen en que se toma, solo se deja una "marca" en nodos e ítems afectados, de modo que cuando cualquiera intente hacer una modificación de su FS tree compartido, el mecanismo COW duplicará las partes modificadas del B-Tree. Puesto que hasta que no sean modificados los ítems que hacen referencia a extents son los mismos para ámbos árboles, los extents que contienen los datos de los archivos se comparten inicialmente, con lo que todo nuevo snapshot comparte todos sus extents de datos y no ocupa prácticamente nada de espacio adicional, solo cuando se modifica un archivo se crea un nuevo extent al que apunta el FS tree que lo haya modificado.

La lista de todos los snapshots y subvolúmenes del SdA se almacena en la raiz de raices, el Root tree. Se almacenan como directorios: literalmente. Cada snapshot o subvolumen tiene un nombre, y en el Root tree se almacena un item de tipo directorio con el nombre e información para encontrar la raiz del FS tree correspondiente.

Mirroring y stripping: regreso al Chunk Tree

El lector sagaz tal vez se haya dado cuenta de hasta ahora no se han mencionado nada sobre la replicación de datos entre varios dispositivos de almacenamiento, ni sobre la capacidad de reescribir, a partir de una réplica, un bloque cuyo checksum erroneo indique corrupción.

Todo se hace en el Chunk tree. Cada item de ese árbol almacenaba equivalencias entre un rango físico de un disco y uno lógico del SdA. Lo que no se mencionó entonces es que cada chunk, además de almacenar información del rango del dispositivo al que quiere representar lógicamente, puede tambien almacenar información sobre más de un dispositivo, e indicar si se quiere que sobre ellos se haga mirroring (copia exacta de los datos) o stripping ("repartir", o dividir los datos del chunk en varios dispositivos).

Esto significa que toda la cuestión de mirroring y stripping se hace a nivel de chunk, cada uno se puede configurar independientemente. Este sistema es muy flexible. Ya dijimos que cada chunk se puede dedicar, por medio del Extent tree, a almacenar solo datos o metadatos. Así es que se pueden configurar los chunks de metadatos con mirroring y los de datos con stripping, por ejemplo. De hecho, esta es la configuración que se utiliza por defecto, se replican los metadatos -esto ocurre incluso dentro de un SdA compuesto por un solo dispositivo- para que las estructuras más importantes del SdA estén salvaguardadas, y los datos se reparten entre varios dispositivos, de haber varios disponibles.

Back references

Esto no tiene nada que ver con B-Trees, pero de todos modos es muy interesante, porque es una característica única de Btrfs. Se trata de una idea extraida de chunkfs, un proyecto creado para resolver la "reparabilidad" de los SdA actuales y que propone una serie de ideas que permitirían crear lo que ellos llaman un SdA "diseñado para ser reparado". Btrfs incorpora buena parte de esas ideas (el nombre "chunk" probablemente derive de chunkfs) , y una de ellas son las "back references", o referencias inversas.

Un ítem de un Fs tree apunta al extent del Extent tree donde se guardan sus datos. Una referencia inversa sería un puntero del extent hacia el ítem del FS tree que lo apuntó. Mantener estas referencias tiene cierto coste, por eso pueden desactivarse, pero aun así se activan por defecto.

Es una información muy preciada que aunque parezca algo paranoica, puede ser muy útil: desde servir para encontrar el ítem que apuntaba a un extent tras descubrirse que éste está corrupto, a poder escanear el disco en busca de extents y poder identificar los que forman parte de un solo archivo fijándose en que los que tienen una misma referencia inversa. Tambien permite reducir el tamaño del SdA, de una forma sencilla, segura y rápida, algo que los SdA tradicionales suelen implementar tarde y mal (por ejemplo, ZFS aun no lo soporta).

Resumiendo...

Se puede sopesar ahora hasta que punto es acertado que el nombre "Btrfs" sea un alias de "B-Tree filesystem". En otros SdA, se crean unas estructuras de datos y se utilizan B-Trees para organizar alguna o algunas de ellas. En Btrfs es al reves, el B-Tree es la estructura de datos fundamental, todas las demás se implementan sobre él. Cada árbol listado en este texto es una especie de instancia del B-Tree modelo.

Toda esta maraña de árboles -más bien jungla- quizás parezca compleja. Incluso podría ser que este texto diera a algunas personas la sensación de que un B-Tree es una estructura demasiado pesada y complicada, y quizás les lleve a pensar que podría haberse ganado en simplicidad no utilizándo tanto árbol excepto en los casos verdaderamente necesarios. Si es así, me temo que mi escritura no es capaz de reflejar la sencillez y limpieza del diseño de Btrfs, en realidad un B-Tree es algo liviano, y es bastante rápido incluso cuando contiene muchos items. Juega a su favor el hecho de que esté preparado para ser escalable en máquinas multicore; diseñar un SdA con las estructuras de datos aptas para ser escalables sería más complicado. La utilización de un B-Tree común que ya ha resuelto esos problemas libra a los programadores de gran parte (pero no todo) ese trabajo.

En cuanto a complejidad, en realidad es sorprendente lo fácil que es comprender todo el diseño a partir de unos pocos conceptos. Una vez que se tienen en la cabeza, cualquiera puede lanzarse a leer gran parte del código y entenderlo sin muchas complicaciones. Hay que hacer notar la limpieza con la que se abstraen ciertos conceptos de otras capas y estructuras. Como comparación, ZFS tambien tiene diferentes niveles bien separados, pero en las estructuras esa diferencia no es tan radical; por ejemplo la estructura encargada de apuntar a un objeto (blockptr_t) contiene el checksum y tres campos de 32+64 bits cada uno en los que se almacena el identificador de dispositivo+desplazamiento de tres copias alternativas, para recurrir a ellas en caso de corrupción. En Btrfs esa información se mantiene separada en el Chunk tree (y una sola vez, no duplicada en cada puntero) y en el Checksum tree , ambos relacionados con los extents del Extent tree por simples rangos de bytes. Podrían añadirse nuevos B-Trees para vaya-a-saber-usted-qué sin que el código ni las estructuras existentes notaran cambio alguno.

En definitiva, Btrfs es un sistema de archivos moderno, con fundaciones muy sólidas y conceptos renovadores que lo harán durar muchos años. Por sus capacidades está muy preparado para sustituir al veterano (pero aun enérgico) Ext4, en cuanto alcance la categoría de estable. Pero tambien sustituirá a reiserfs (v3 o v4), XFS y JFS, lo cual centrará sobre él una mayor atención colectiva de la que Ext4 tiene hoy, que es mucha. En estos momentos su estado de desarrollo podría considerarse como de las últimas versiones alpha; las distros ya empiezan a ofrecer opción experimental en las instalaciones nuevas. Es de suponer que la versión 1.0 vea la luz en la primera parte del año que viene y que pase a usarse como SdA por defecto en las distros a lo largo del 2011.

(Notas: -todo lo referente al Extent Tree y parte del FS Tree han sido revisados desde su redacción original debido a un error conceptual, -se ha eliminado la información sobre la cabecera de cada bloque del btree, no viene mucho a cuento, -se ha simplificado la explicación del B-Tree, -la explicación de los ítems de cada árbol se ha reescrito para ser más visual)