PDF de programación - Evolución de los sistemas de archivos en Linux

Evolución de los

sistemas de archivos

en Linux
Mario Medina C.

Depto. Ing. Eléctrica, UdeC

[email protected]

24-Oct.-2009

2009 Encuentro Linux

Tópicos a tratar

• Sistemas de archivos tradicionales

 El sistema de archivos Ext2

• Sistemas de archivos basados en

bitácoras (journaling)
 El sistema de archivos Ext3

• Sistema de archivos actuales

 El sistema de archivos Ext4
 Otros

24-Oct.-2009

2009 Encuentro Linux

Sistemas de archivos

• Sistemas de archivos ven un medio de

almacenamiento masivo como un vector
de bloques
 Bloques típicamente son de 1, 2 ó 4 KiB
 Datos se almacenan en sectores de 512 bytes

Vector de bloques

0

n-1

24-Oct.-2009

2009 Encuentro Linux

Almacenando un archivo

• Almacenar los datos del archivo y

los metadatos
 Nodo índice contiene índices de los

bloques de datos

 Nombre se almacena en el directorio

Nodo índice

(Nodo-i)
Dueño
Tipo

Tamaño

13 14
20 5

Índice de
bloques

1 11
17 18
6
7

0

1

2

3

4

5

6

7

9 10 11 12 13 14 15 16 17 18 19 20 21

8
Bloques de disco

24-Oct.-2009

2009 Encuentro Linux

Breve historia

• Linus Torvalds
• MINIX
• Andy Tanenbaum

24-Oct.-2009

2009 Encuentro Linux

MINIX y Linux

• MINIX

 Plataforma, guía y fuente de inspiración para

desarrollar Linux

• Linux

 Primera versión del kernel en 1991
 Inicialmente, utilizaba el sistema de archivos

de MINIX
Basado en Berkeley FFS
Simplificado para la enseñanza

24-Oct.-2009

2009 Encuentro Linux

MINIX FS

• Sistema de archivos de tamaño máximo

64 MiB

• Archivos de tamaño máximo 64 MiB
• Directorios tienen tamaño fijo
• Nombres de archivos limitados a 14

caracteres

• Bloques de 1 KiB
• Punteros a bloques de 16 bits

24-Oct.-2009

2009 Encuentro Linux

Sistema de archivos Ext

• Sistema de archivos extendido (Extended

File System)
 Liberado en 1992 para reemplazar MINIX FS
 Sistema de archivos de tamaño máximo 4 TiB
 Archivos de tamaño máximo 2 GiB
 Nombres de archivos de 255 caracteres
 Ineficiente!

Maneja bloques libres y nodos-I como listas

encadenadas

24-Oct.-2009

2009 Encuentro Linux

Sistema de archivos Ext2

• Segundo sistema de archivos extendido

(Extended File System 2)
 Aparece en 1993
 Sistema de archivos de tamaño máximo 4 TiB
 Archivos de tamaño máximo 2 GiB
 Directorios de tamaño variable
 Nombres de archivos de 255 caracteres
 Eficiente y robusto

24-Oct.-2009

2009 Encuentro Linux

Sistema de archivos Ext2

• Divide el disco en n grupos de bloques

 m bloques de datos
 i nodos-i asociados a los archivos en el grupo

Grupo 0 Grupo 1

. . . . . Grupo n - 1

Super
bloque

Descriptores
de grupos

1

bloque

n

bloques

Bitmap
bloques
datos

1

bloque

Bitmap
nodos-i

Tabla de
nodos-i m Bloques de datos

1

bloque

i

bloques

m

bloques

24-Oct.-2009

2009 Encuentro Linux

Contenido de un grupo

• m bloques de datos
• i nodos-i
• Bitmap de bloques libres en el grupo
• Bitmap de nodos-i libres en el grupo
• Copia del superbloque
• Copia de los descriptores de todos los

grupos

24-Oct.-2009

2009 Encuentro Linux

Superbloque

• Contiene información de todo el sistema

 Número total de nodos-i
 Tamaño total en bloques
 Tamaño del bloque (1, 2 ó 4 KiB)
 Tamaño del nodo-i (128 bytes)
 Número total de bloques libres
 Número total de nodos-i libres
 Número de bloques y nodos-i por grupo
 Contador de operaciones de montaje

24-Oct.-2009

2009 Encuentro Linux

Descriptor de grupo

• Cada grupo tiene su propio descriptor
• Replicado en cada grupo (n copias)

 Número de bloque del bitmap de bloques de

datos

 Número de bloque del bitmap de nodos-i
 Número de bloque del primer bloque de datos
 Contador de bloques de datos libres
 Contador de nodos-i libres
 Número de directorios en el grupo

24-Oct.-2009

2009 Encuentro Linux

Nodo-i

• 128 bytes de longitud

 Tipo del archivo (archivo, directorio, socket,

enlace, etc.)

 Tamaño del archivo en bytes
 Tamano del archivo en bloques
 Dueño del archivo
 3 marcas de tiempo

Fecha y hora de creación
Fecha y hora de última modificación
Fecha y hora de último acceso

24-Oct.-2009

2009 Encuentro Linux

Punteros en nodo-i

• 12 punteros directos

 Contienen número del bloque de datos

• Puntero a tabla de primer nivel
 Tabla contiene punteros directos

• Puntero a tabla de segundo nivel

 Tabla de punteros a tablas de primer nivel

• Puntero a tabla de tercer nivel

 Tabla de punteros a tablas de segundo nivel

24-Oct.-2009

2009 Encuentro Linux

Direccionamiento de bloques

24-Oct.-2009

2009 Encuentro Linux

Direccionamiento de bloques

• Para bloques de 4 KiB y punteros de 32 bits
 12 punteros directos a bloques de datos: 48 KiB
 Puntero a tabla de primer nivel: 4 MiB

Ocupa un bloque de datos

 Puntero a tabla de segundo nivel: 4 GiB
 Puntero a tabla de tercer nivel: 4 TiB

• Máximo tamaño de un archivo
 4 TiB + 4 GiB + 4 MiB + 48 KiB

24-Oct.-2009

2009 Encuentro Linux

Directorios

• Archivo especial
• Estructura de datos contiene

 Número del nodo-I
 Tamaño de esta estructura de datos
 Longitud del nombre

Máximo 255 caracteres

 Tipo del archivo
 Nombre del archivo

24-Oct.-2009

2009 Encuentro Linux

Estructura de un directorio

• En el ejemplo, archivo oldfile está borrado

 Nodo-i es 0

24-Oct.-2009

2009 Encuentro Linux

Límites de Ext2

• Bloques por grupo
32 Ki
• Bytes por grupo
128 MiB
• Nodos-i por grupo
32 Ki
• Número máximo de grupos
128 Ki
• Tamaño máximo de un disco
16 TiB
• Bloques por archivo
2 Gi
• Tamaño máximo de un archivo 4 TiB

• Suponiendo bloques de 4 KiB

24-Oct.-2009

2009 Encuentro Linux

Problemas de Ext2

• Directorios son listas encadenadas

 Parche a Ext2 en 2002 implementa directorios
como árboles Htree (opción dir_index)
Similar a árboles B+

 Árboles de altura constante (1 ó 2 niveles)
 Factor de fanout alto
 Función de dispersión (hash) aplicada al

nombre del archivo

 Compatible con lista de Ext2 rev. 0

24-Oct.-2009

2009 Encuentro Linux

Árboles Htree

24-Oct.-2009

2009 Encuentro Linux

Superbloques ralos

• Copia del superbloque en todos los grupos
• Modificaciones deben actualizar todas las

copias
 Ineficiente!

• Ext2 revisión 1 agrega opción
sparse_super
 Copias del superbloque y los descriptores de
grupo se almacenan sólo en los grupos 0, 1, y
potencias de 3, 5, y 7

24-Oct.-2009

2009 Encuentro Linux

Soporte para archivos

grandes

• Ext2 rev. 0 limita tamaño máximo de un

archivo a 2 GiB
 Límite fue sobrepasado por evolución de los

discos magnéticos

• Ext2 rev.1 agrega opción large_file
 Permite utilizar archivos de tamaño hasta 4

TiB

 Este límite está siendo sobrepasado hoy en

día.

24-Oct.-2009

2009 Encuentro Linux

Tamaño máximo de un grupo

• Bitmap de bloques libres debe caber en un

bloque
 Si bloque es 4 KiB, bitmap describe a lo más

32 Ki bloques

 Cada grupo de bloques puede almacenar a lo

más 128 MiB de datos

24-Oct.-2009

2009 Encuentro Linux

Número fijo de nodos-i

• Número de nodos-i por grupo se define al
momento de crear el sistema de archivos
 Tamaño de nodo-i: 128 bytes
 32 nodos-i en un bloque de 4 KiB
 Debe haber un nodo-i por cada bloque de

datos
32 Ki bloques fi

32 Ki nodos-i

 Máximo 4 MiB dedicados a almacenar nodos-i

24-Oct.-2009

2009 Encuentro Linux

Metadatos en Ext2

• Ext2 mantiene 6 tipos de metadatos

 Superbloques
 Descriptores de grupo
 Nodos-i
 Tablas de punteros de primer, segundo y

tercer nivel

 Bitmaps de bloques libres
 Bitmaps de nodos-i libres

24-Oct.-2009

2009 Encuentro Linux

Actualizando metadatos

Si un archivo crece de 3 a 5 bloques, actualizar
• Superbloque y todas sus copias

 Actualizar contador de total de bloques libres

• Descriptor del grupo y todas sus copias

 Actualizar contador de bloques libres en el grupo

• Grupo

 Actualizar bitmap de bloques libres

• Nodo-i del archivo

 Actualizar tamaño, bloques usados, punteros a

bloques, tablas de punteros, etc.

24-Oct.-2009

2009 Encuentro Linux

Metadatos en memoria

• Información crítica del sistema de archivos
se lee a memoria al momento del montaje
• Memoria RAM no puede almacenar todas

las estructuras de datos

• Qué hacer?

 Guardar datos en cache!

24-Oct.-2009

2009 Encuentro Linux

Metadatos en memoria

• Superbloque y descriptores

 Siempre en memoria

• Nodos-i

 En buffer cache
• Bloques de datos
 En buffer cache

• Bitmaps de bloques y de nodos-i libres

 En cola FIFO en memoria

24-Oct.-2009

2009 Encuentro Linux

Consistencia de metadatos

• Metadatos se almacenan en memoria
 Mayor desempeño por acceso rápido a

metadatos frecuentemente usados
• Copias en disco son actualizadas
periódicamente por el proceso sync
 Escribe superbloques, nodos-i, bitmaps

modificados desde memoria al disco

• Qué pasa si hay un problema?
 Inconsistencia en los metadatos!

24-Oct.-2009

2009 Encuentro Linux

Reparación usando fsck

• fsck asegura consistencia del sistema de
archivos
 Corrige errores en metadatos
 Debe revisar todo el sistema de archivos
• Tiempo de ejecución proporcional al

tamaño del disco
 Puede demorar muchísimo para discos

grandes

• Solución: journaling

24-Oct.-2009

2009 Encuentro Linux

Tercer sistema de archivos

extendido (Ext3)

• Compatible con Ext2

 Partición Ext3 puede ser montada como

partición Ext2

 Conversión in situ entre Ext2 y Ext3 posible
 Bitácora almacenada como archivo
/.journal
 Bitácora se escribe al disco con mayor

frecuencia que sync de Ext2

 Volumen de datos a escribir es menor

24-Oct.-2009

2009 Encuentro Linux

La bitácora o journal

• Estructura de datos almacenada en disco

 Bitácora registra cambios a realizar a los

metadatos

 Después se realizan los cambios a los datos
 Luego, se marcan los cambios como

realizados en la bitácora (commit)

• Restauración de consistencia

 Revisar últimas modificaciones a la bitácora
 Tiempo de ejecución proporcional al tamaño

de la bitácora