¿Cómo funcionan los sistemas basados en inodos?

Después de ver como funcionan de forma genérica los sistemas FAT, saltamos a los sistemas de inodos. Estos se han usado tradicionalmente en sistemas UNIX (UFS, ext2), así que tradicionalmente ha existido una cierta rivalidad  en las redes entre FAT e inodos similar a la de Windows/Linux. Lo cierto es que a nivel técnico cada uno tiene fortalezas y debilidades.

Partición

Tomando la base de FAT, una partición de un sistema basado en inodos también contiene un sector de arranque y un superbloque con metadatos. También es necesario un bloque dedicado al directorio raíz presente en el disco. Además es necesario espacio para almacenar todos los inodos y un mapa de bits de espacio libre que en FAT no hacía falta, ya que la propia tabla nos indicaba que bloques del disco estaban libres.

Los inodos

¿Qué es inodo te podrás preguntar? Es una estructura de datos, su nombre proviene de index node y es que los inodos no son más que índices, que almacenan los números de bloque de las diferentes partes del archivo. Además, contienen metadatos como permisos, propietario, tamaño, fecha de modificación, referencias, tipo de fichero (directorio, archivo, enlace duro, enlace blando,…) salvo el nombre del propio archivo, que en ningún sitio del inodo aparece.

Este sistema tiene una ventaja de rendimiento respecto a FAT en cuanto al acceso aleatorio a los archivos, ya que es mucho más rápido de esta forma que con FAT. En FAT para hacer lo mismo tenemos que ir recorriendo la tabla arriba y abajo siguiendo los números de bloque hasta encontrar el bloque deseado.

Normalmente un inodo tiene un tamaño fijo, lo que implica que el índice no se puede alargar hasta el infinito. Esto hace que haya un número limitado de bloques que puede usar un archivo y por ende, que haya un tamaño máximo de archivo que no es muy elevado. Para solventar este problema hay varias soluciones. El enfoque de UFS y de ext2/3/4 consiste en múltiples niveles de indexado progresivo.

Esto significa que los primeros bloques son números de bloque directos pero los siguientes son números de bloque que llevan a tablas de inodo secundarias que ya sí, hacen referencia al archivo real. Más adelante los números de bloque hacen referencias a tablas de inodo secundarias que a su vez llaman a tablas de inodos terciarias.

Esto provoca algo que en principio puede parecer paradójico y es que es más lento leer una zona final de un archivo que una zona del principio, aunque en una lectura secuencial no se nota demasiado.

Otra solución a esto es enlazar los inodos a modo de lista enlazada añadiendo al final de cada inodo un número de inodo al que continuar la lectura de índices.

Localización de los inodos

Los inodos se crean cuando se formatea el disco y permanecen en un estado libre. No se pueden añadir más inodos ni quitar inodos y no puede haber más archivos y directorios que inodos por esta misma razón. Esto es una desventaja respecto a FAT, ya que en FAT puede haber tantos archivos como bloques haya/entradas tenga la tabla. En sistemas de inodos como ext2/3/4 puede ocurrir que no queden inodos libres pero haya todavía bloques libres, dejando todo ese espacio inutilizado (aunque en realidad lo podrían usar los archivos existentes si creciesen).

Los inodos se pueden ubicar de dos formas distintas. Un enfoque consiste en ponerlos al principio del disco todos juntos. Otro enfoque, el que sigue ext3, consiste en dividir el disco en 4 zonas y ubicar inodos en cada inicio de zona. La idea es que los inodos de esa zona usen bloques de esa zona y de esta forma reducir los desplazamientos de las cabezas lectoras del disco (en unidades SSD esto da completamente igual como podréis suponer).

Gestión del espacio libre

Una de las grandes ventajas de FAT era que la tabla podía mantener a la vez un listado de bloques libres, listos para ser usados. Con inodos no tenemos esa facilidad y tenemos que recurrir a otros tipos de estructura. Aquí hay muchos planteamientos siendo el más común el mapa de bits. El mapa de bits es una estructura que se compone de un listado de bits. Cada bit corresponde a un bloque y dependiendo de si el bit es 1 o 0 podemos saber si el bloque está libre u ocupado.

Como veis, los sistemas basados en inodos tienen que mantener varias estructuras de datos de forma paralela. Esto aumenta las probabilidades de inconsistencias en el sistema. Por este motivo, muchos sistemas más avanzados como ext4 mantienen un journal o diario.

Fragmentación

Veamos como se comportan los sistemas de inodos ante los tres tipos de fragmentación. Respecto a la fragmentación interna, que es aquella que sucede cuando asignamos espacio de más a archivos que no necesitan tanto, tiene los mismos valores que FAT, ya que los bloques siguen pudiendo pertenecer únicamente a un archivo. Realmente, para mejorar la fragmentación interna tenemos que saltar a sistemas como XFS o JFS.

La fragmentación externa de los sistemas basados en inodos es la misma que la de FAT, 0, ya que todo se asigna mediante bloques del mismo tamaño.

Respecto a la fragmentación de datos, históricamente las implementaciones como UFS o ext2/3 se han comportado relativamente bien, aunque a nivel teórico nada impide que se comporten igual de mal que FAT, no existen mecanismos preventivos. Ext4 por contra, sí que tiene mecanismos de prevención (delayed allocation).

Directorios y enlaces duros

En los sistemas basados en inodos los directorios son más sencillos que en FAT, ya que no tienen que almacenar los metadatos del archivo en cuestión. En un fichero de directorio simplemente se almacena el nombre y el número de inodo correspondiente.

Aquí surge un concepto muy interesante, el de enlaces duros. Un enlace duro no es más que otra entrada de directorio que apunta a un mismo inodo. Realmente desde el punto de vista del sistema de archivos no existe un fichero original y su enlace. Simplemente dos entradas diferentes apuntando al mismo inodo. ¿Y cómo reacciona esto a los borrados? Imagina la siguiente situación: tengo un fichero y creo un enlace duro. Borro el fichero original y su inodo se libera. Ahora creo otro archivo y reutiliza ese mismo inodo que estaba libre. ¡Ahora el enlace duro apunta a un contenido totalmente distinto sin darse cuenta! Para prevenir esto, los inodos no se liberan hasta que no quede ninguna entrada de directorio apuntando a ellos. Para eso sirve el campo referencias dentro del inodo, para llevar la cuenta de cuántas veces se hace referencia al inodo en el sistema de archivos. Cuando el valor de referencias llega a cero, se puede liberar sin problema.

Conclusiones

Los sistemas basados en inodos son conceptualmente algo más complejos que los basados en FAT. Comparten además limitaciones comunes, usan más espacio de disco, aunque suelen ser más rápidos.

Actualmente existen sistemas basados en inodos mucho más avanzados y complejos que UFS y ext2/3/4 y que mejoran este sistema de forma sustancial. Por ejemplo en XFS los inodos tienen una estructura totalmente distinta donde se indica un bloque de inicio y una longitud en número de bloques contiguos que pertenecen al archivo. Muchos sistemas además usan estructuras de árbol B+ como pueden ser ZFS o Btrfs.

¿Cómo funcionan los sistemas de archivos basados en FAT?

Voy a dedicar unas entradas en el blog a hablar del funcionamiento de los sistemas de archivos, un componente fundamental en la gran mayoría de sistemas informáticos. Voy a empezar con los basados en FAT sin centrarme en ninguno en concreto (FAT16, FAT32, exFAT,…). Intentaré escribir también sobre inodos y mecanismos más raros y avanzados.

En esencia un sistema de archivos es un método ordenado que permite guardar datos sobre un soporte físico para luego poder acceder a ellos. Históricamente ha habido muchos enfoques a este problema: los sistemas más usados usan archivos, directorios y enlaces.

Bloques y sectores: la división del disco

Esta parte es común a muchos sistemas de archivos, tanto FAT como inodos, como otros. A nivel físico los dipositivos están divididos. En el caso del disco duro, el dispositivo de almacenamiento más común, los discos se dividen en sectores de N bytes, según parámetros de la fabricación. Estos sectores cuentan con código de control de errores incorporado y todo ello es manejado por la controladora de disco que opera ajena al sistema operativo. Los sistemas de archivos dividen a su vez el disco en bloques. Es importante dejar claro que bloque no es igual a sector. El bloque es una división que hace el sistema de archivos y los sectores los hace la controladora de disco. Usualmente un bloque equivale a varios sectores, aunque la equivalencia real depende del sistema de archivos en concreto.

Algunos bloques especiales: boot y superbloque y raíz

Antes de entrar en el mecanismo específico de FAT es necesario comentar que en un disco existirán dos bloques de vital importancia ajenos a FAT. El primero es el bloque de boot o arranque (también llamado MBR). Normalmente situado en el sector 0 del disco duro, contiene código para iniciar el sistema operativo. El superbloque suele ser el bloque siguiente, contiene metadatos del sistema de archivos (por ejemplo, puede decir que usamos FAT con bloques de 32KiB, etc). Además en FAT es necesario que exista un fichero siempre, el fichero del directorio raíz.

Directorios

Los directorios o carpetas son archivos como otros cualquiera, solamente que en sus metadatos se indica que es un directorio y no un fichero corriente. Los ficheros de directorios son los encargados de almacenar los metadatos de los ficheros (paras saber si son ficheros, otros directorios, su fecha de modificación, propietario y tamaño entre otros) que se encuentran en el directorio así como una referencia al bloque.

Un fichero en FAT

Vamos al asunto. Supongamos que en un determinado bloque N tenemos un fichero. Este bloque es de 64 KiB. Si un fichero ocupa menos de 64 KiB, perfecto, todos los datos entran en el bloque. Simplemente ajustamos los metadatos de tamaño con el valor correcto y el resto del espacio que queda en el bloque queda inutilizado.

Este espacio perdido se denomina fragmentación interna y dependiendo de los datos que se almacenen en un disco duro, el porcentaje de pérdida puede ser mayor o menor. Evidentemente si tenemos bloques muy grandes y ficheros muy pequeños perderemos mucho espacio debido a la fragmentación interna. Tener bloques muy pequeños y ficheros muy grandes también es problemático pero por otros motivos.

Tipos de fragmentación

En un sistema de archivos existen 3 tipos de fragmentación: interna, externa y de datos. La interna se refiere al espacio perdido en bloques asignados a ficheros que no están llenos por completo. La externa se refiere al espacio que perdemos por no tener un espacio libre contiguo lo suficientemente grande como para guardar el fichero allí. Ningún sistema FAT o de inodos tiene fragmentación externa al usar todos bloques de tamaño predefinido. Por último la fragmentación de datos, o fragmentación a secas, se refiere a que los bloques asignados estén contiguos o no. Esto tiene implicaciones a nivel de rendimiento pero no al número de bytes que se vuelven inútiles como los otros dos tipos de fragmentación.

¿Pero qué pasa si el contenido de nuestro fichero no puede entrar en el tamaño de bloque? Aquí viene la gracia de FAT, la File-Allocation-Table. La FAT es una tabla compuesta por entradas que indican el siguiente bloque del archivo. La tabla está indexada por bloque y además de indicar cuál es el siguiente bloque del archivo también indica si el archivo acaba ahí o si ese bloque está libre y puede usarse para un archivo nuevo.

En la foto el archivo /home/user/hola.txt tiene una longitud menor al tamaño de bloque. Así que miramos en la FAT la entrada 150 y efectivamente comprobamos que no hay bloque siguiente ya que es un End-of-File.

Pongamos un ejemplo con un archivo largo. Cada celda de la tabla correspondiente al índice del bloque actual indica el siguiente bloque a leer. Estos bloques pueden estar en cualquier parte. Si en un disco duro muchos ficheros tienen los bloques muy dispersos, se dice que necesita ser desfragmentado.

Conclusiones

FAT es muy rápido si la tabla FAT consigue ser cargada en memoria, ya que obtener los datos necesarios de ella será muy rápido. Desgraciadamente, dependiendo del tamaño del disco duro y del tamaño de los bloques, esta tabla puede ocupar mucho y ser impráctico.

El mecanismo FAT como vemos es simple pero efectivo. Dispone de una fragmentación interna limitada y carece de fragmentación externa. Un inconveniente es que FAT cuando busca un archivo necesita empezar siempre desde el directorio raíz. Esto implica accesos cada vez más lentos a medida que vayamos haciendo carpetas, aunque con sistemas de caché se puede reducir.

El esquema FAT tampoco impone restricciones propiamente dichas al número archivos de un sistema ni a su tamaño. Sin embargo en la práctica suelen existir límites.

Edito: He explicado mejor que significa la fragmentación y sus tipos

Bindings entre Rust y C/C++ con bindgen

Rust es un lenguaje con muchas posibilidades pero existe mucho código ya escrito en librerías de C y C++. Código que ha llevado mucho tiempo, que ha sido probado en miles de escenarios, software maduro y que no compensa reescribir. Afortunadamente podemos reutilizar ese código en nuestras aplicaciones Rust a través de bindings. Los bindings no son más que trozos de código que sirven de pegamento entre lenguajes. Esto es algo que se ha podido hacer desde siempre pero dependiendo de la librería podía llegar a ser muy tedioso. Afortunadamente tenemos bindgen, un programa que permite generar estos bindings de forma automática analizando el código de la librería de C o C++.

En este post veremos como usar SQLite desde Rust usando bindgen.

Instalando bindgen

En primer lugar necesitamos tener instalado Clang 3.9 o superior. En Ubuntu o Debian necesitamos estos paquetes:

Para el resto de plataformas puedes descargar el binario desde la página de descargas de LLVM.

Bindgen permite dos modos de uso: línea de comandos o desde el código Rust. El más habitual es desde código Rust pero antes veremos el modo en línea de comandos.

Modo línea de comandos

Para bindings sencillos podemos usar el modo línea de comandos. Instalamos binden con Cargo:

Su uso es muy sencillo:

Simplemente indicamos el fichero de cabecera que queremos traducir y su correspondiente fichero de salida en Rust. Este fichero será el pegamento. Vamos a crear un programa que use este pegamento:

Como se puede apreciar, las llamadas al módulo de pegamento de hacen desde un bloque unsafe ya que se van a usar punteros al estilo C, de forma insegura. Hace tiempo escribí sobre ello así que voy a saltarme esa parte.

Compilamos enlazando de forma manual libsqlite3 de la siguiente forma:

Si todo va bien, compilará aunque con numerosos warnings. En principio no son importantes.

Ahora si ejecutamos el programa resultante debería crear una base de datos nueva con una tabla contacts y los datos insertados.

¡Hemos conseguido llamar a una librería de C desde Rust y no hemos escrito ningún binding!

Build.rs

El sistema anterior funciona, pero no es lo más práctico, además no usa Cargo que es el sistema estándar de construcción de programas y crates un Rust. Lo habitual es dejar este proceso automatizado en el fichero build.rs que se ejecuta con Cargo.

Lo primero es añadir la siguiente línea al fichero Cargo.toml:

El siguiente paso consiste en crear un archivo cabecera de C que a su vez haga referencia a todos los archivos de cabecera que necesitamos. En el caso de SQLite es bastante simple.

Y lo llamamos wrapper.h

Ahora viene lo interesante. Dentro de build.rs creamos un programa que gracias a la API de bindgen haga lo mismo que la línea de comandos.

El archivo build.rs debe estar en la misma carpeta que Cargo.toml para que funcione.

Finalmente para hacer accesible nuestros bindings creamos un módulo llamado sqlite.rs con el siguiente contenido.

Lo único que hace es desactivar unos warnings molestos e incluir el texto de bindings.rs al completo.

Una vez hecho esto podemos usar desde el programa principal la librería de la misma forma que hemos visto antes.

Ahora podríamos usar estos bindings directamente en nuestro programa o rustizarlos (darles una capa segura alrededor e idiomática) y subirlo a Crates.io.

El código del post está en GitHub

Ayuda a la ciencia desde tu casa con BOINC

El invento de los ordenadores se lo debemos a los científicos, que buscando maneras de acelerar sus cálculos decidieron crear máquinas que los automatizaban. A partir de esos desarrollos la informática se ha diversificado en muchas más ramas, sin embargo la necesidad de procesar grandes cantidades de datos sigue siendo de vital importancia para la investigación en física, química, medicina y demás ramas de la ciencia.

El ENIAC, uno de los primeros ordenadores construidos

Este tipo de cálculos se realizan normalmente en supercomputadoras en clúster que trabajan en paralelo. Sin embargo en muchas ocasiones, nada impide que cada nodo esté separado kilómetros de distancia. Ahí nace el proyecto BOINC (siglas de Berkeley Open Infrastructure for Network Computing). BOINC es un sistema de computación distribuida en Grid. Esto quiere decir que el cómputo necesario para un proyecto se divide en paquetes. Cada paquete se manda a un ordenador que forma parte de la red. Cada ordenador se encarga de procesarlo. Cuando los cálculos han finalizado, los envía al servidor central que le entrega a su vez al ordenador un paquete con cómputos nuevos por realizar.

De todos los sistemas de computación distribuida en Grid, BOINC es sin duda el más popular. La potencia de cálculo de BOINC es de media 23 petaflops, algo lejos del mayor supercomputador (Sunway TaihuLight, de China, con 93 petaflops) pero superior a muchos supercomptadores como MareNostrum, el mayor supercomputador de España y que tiene 11 petaflops.

Supercomputador Mare Nostrum 4

Cualquier ordenador del mundo puede colaborar con la red BOINC aportando su potencia a la red y calculando datos muy importantes para las investigaciones científicas.

¿Cómo puedo usar BOINC y ayudar?

Es muy sencillo. BOINC dispone de versiones para Windows, Mac, Linux y Android, así como versiones optimizadas con CUDA (Nvidia), OpenCL y existen versiones de terceros para Solaris, HP-UX, FreeBSD y otros sistemas.

El primer paso es descargar BOINC desde https://boinc.berkeley.edu/ . Si estás en Android puedes ir directamente a Google Play y descargar BOINC desde allí.

El cliente BOINC se divide en dos partes: una que se dedica a calcular y otra que es una interfaz de usuario que nos permite controlar la parte que calcula (BOINC Manager). La ventaja de esto es que son programas independientes y no hace falta tener la interfaz de usuario abierta para seguir calculando.

Proyectos

Lo primero que tenemos que hacer nada más abrir el BOINC Manager es registrarnos en un proyecto para que nos empiece a mandar tareas.

Algunos de los más populares son:

  • SETI@Home. Es el proyecto que busca vida extreterrestre por el universo analizando las señales de radiotelescopios como el de Arecibo. Fue uno de los primeros proyectos de BOINC y uno de los más populares.
  • Rosetta@Home: Este proyecto busca nuevos tipos de proteínas así como su aplicación en enfermedades como la malaria y el alzheimer,.
  • Einstein@Home: Este proyecto busca detectar ondas gravitacionales desde los datos recogidos de observatorios como LIGO.
  • PrimeGrid: Busca nuevos números primos, esenciales en campos como la de la criptografía.
  • ClimatePrediction: Busca modelos climáticos mejorados que permitan mejorar nuestra capacidad de predicción del clima
  • MilkyWay@Home: Investiga modelos tridimensionales sobre nuestra galaxia, la vía láctea
  • LHC@Home: Tareas relacionadas con la investigación en física de partículas con datos generados por el LHC.
  • Asteroids@Home: Amplía nuestro conocimiento sobre los billones de asteroides que hay en el universo, analizando los que podemos ver

Para registrarnos indicamos nuestro correo y nuestra contraseña y automáticamente todo empezará a funcionar. ¡No hay que hacer nada más! BOINC se encargará de todo automáticamente.

Desde la interfaz podemos parar los cálculos en cualquier momento pulsando Suspend o Pausar.

BOINC Credits

En recompensa a nuestro trabajo se nos dan BOINC Credits. La cantidad de BOINC Credits es proporcional a los gigaflops que hayamos aportado. Estos créditos no sirven realmente para nada. Únicamente para fardar ante tus amigos. Y es que hay gente realmente picada y existen equipos de gente que se unen para superar a otros equipos. Los BOINC Credits también sirven para realizar benchmarks de los ordenadores. Puedes consultar tus BOINC Credits desde BOINC Manager o desde webs externas como BOINC Stats.

Mis estadísticas en BOINC

Fabric, automatiza tareas en remoto

En la medida de lo posible tenemos que automatizar todo lo posible. No solo reducimos tiempo sino que reducimos errores, y a la vez, estamos documentando un proceso. Muchas de estas ideas ya las dejé claras en ¡Haz scripts! Sin embargo, hay situaciones donde es más complicada esta situación, como por ejemplo, trabajar con máquinas remotas. Aquí entra Fabric en acción, una librería para Python que permite automatizar procesos en remoto a través de SSH.

Originalmente Fabric, compatible únicamente con Python 2, funcionaba a través de unos archivos llamados Fabfile que se ejecutaban con el comando fab. Este mecanismo ha sido transformado por completo en Fabric 2, que ha salido hace nada. Yo ya he hecho la transición y puedo decir que el nuevo sistema, más enfocado a ser una librería sin más, es mucho más práctico y útil que el anterior.

Instalando Fabric

Voy a usar Pipenv, que es la manera recomendada de gestionar proyectos en Python actualmente.

Y accedemos al virtualenv con:

Conexiones

El elemento fundamental de Fabric a partir de la versión 2 son las conexiones. Estos objetos representan la conexión con otra máquina y podemos:

  • ejecutar comandos en el shell de la otra máquina, run, sudo.
  • descargar archivos desde la máquina remota a local, get
  • subir archivos de local a remoto, put
  • hacer forwarding, forward_local, forward_remote.

Para iniciar una conexión necesitamos la dirección de la máquina y alguna manera de identificarnos. En todo el tema de la autenticación Fabric delega el trabajo en Paramiko, que soporta gran variedad de opciones, incluida la opción de usar gateways.

Vamos a mostrar un ejemplo, en este caso, de autenticación con contraseña:

El objeto creado con Connection ya lo podemos usar. Habitualmente no es necesario cerrar la conexión aunque en casos extremos puede ser necesario, una manera es llamando a close, otra es con un bloque with.

Tareas

Una vez que ya tenemos la conexión podemos pasárselo a diferentes funciones, cada una con una tarea distinta. Veamos algunos ejemplos.

Actualizar con apt

Los comandos que necesiten sudo pueden necesitar una pseudo-terminal para preguntar la contraseña (si es que la piden, no todos los servidores SSH piden contraseña al hacer sudo). En ese caso añadimos, pty=True.

 

Backup de Mysql/Mariadb y cifrado con gpg

Requiere que MySQL/MariaDB esté configurado con la opción de autenticación POSIX (modo por defecto en el último Ubuntu)

Como véis, usar Fabric es muy sencillo, ya que apenas se diferencia de un script local.

Si queremos obtener el resultado del comando, podemos simplemente asignar a una variable la evaluación de los comandos run/sudo.

Grupos

Fabric es muy potente, pero en cuanto tengamos muchas máquinas vamos a hacer muchas veces las mismas tareas. Podemos usar un simple bucle for, pero Fabric nos trae una abstracción llamada Group. Básicamente podemos juntar conexiones en un único grupo y este ejecutas las acciones que pidamos. Existen dos tipos de grupo, SerialGroup, que ejecuta las operaciones secuencialmente y ThreadGroup que las ejecuta en paralelo.

O si tienes ya objetos de conexión creados:

Con esto ya deberías saber lo básico para manejar Fabric, una fantástica librería para la automatización en remoto. Yo la uso para este blog y otras webs. Existen alternativas como Ansible, aunque a mí nunca me ha terminado de gustar su manera de hacer las cosas, que requiere mucho más aprendizaje.