1. Ingeniería

Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Tema 4: Sistemas Operativos Distribuidos
Sistemas de Ficheros
Enrique Soriano
LS, GSYC
5 de noviembre de 2014
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
(cc) 2014 Grupo de Sistemas y Comunicaciones.
Algunos derechos reservados. Este trabajo se entrega bajo la licencia Creative Commons Reconocimiento NoComercial - SinObraDerivada (by-nc-nd). Para obtener la licencia completa, v´
ease
http://creativecommons.org/licenses/by-sa/2.1/es. Tambi´
en puede solicitarse a Creative Commons, 559 Nathan
Abbott Way, Stanford, California 94305, USA. Las im´
agenes de terceros conservan su propia licencia.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sistemas de ficheros locales
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ficheros
• Tradicionalmente: datos que persisten tras la ejecuci´
on del
proceso y/o del sistema (excepci´
on: ramfs), y que son
compartidos por distintos procesos y/o sistemas.
• Requisitos:
•
•
•
•
Gran tama˜
no
Durabilidad
Acceso concurrente
Protecci´
on
• M´
as general: es una interfaz. P. ej. puede representar un
dispositivo.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ficheros de datos
• Estructura: fichero simple (UNIX), Resource Forks (Mac)...
• Nombre: ¿extensi´
on?
• ¿Tipos?
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ficheros: Estructura Interna
• Bloque f´ısico → determinado por el HW (sector).
Tradicionalmente de 512 bytes, algunos fabricantes est´an
pasando a 4 Kb.
• Bloque l´
ogico → determinado por el sistema de ficheros.
• Si no coinciden, empaquetamos.
• Siempre hay fragmentaci´
on interna en los bloques.
• ¿Tama˜
no? compromiso entre:
↑ tama˜
no de bloque ⇒ ↑ fragmentaci´on
↑ tama˜
no de bloque ⇒ ↑ tasa de transferencia
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos
Acceso al disco:
• Secuencial: se accede registro a registro (contiguos).
Antiguo (cintas magn´eticas).
• Aleatorio: se accede a cualquier registro inmediatamente.
Los HD permiten este acceso.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos
• Direccionamiento de bloques: CHS, LBA.
• As´ı eran:
9/17/12
Imagen: Public Domain, Wikipedia
upload.wikimedia.org/wikipedia/commons/0/02/Cylinder_Head_Sector.svg
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos
• Algoritmo de planificaci´
on de disco: c´
omo organiza el SO las
operaciones de entrada/salida.
• El algoritmo depende totalmente del tipo de disco que usemos.
• Los cl´
asicos:
• FIFO: es justo, no altera el orden de las operaciones. Lento en
discos mec´anicos.
• Shortests Seek First: no es justo, puede provocar hambruna,
desordena operaciones.
• SCAN (Ascensor): compromiso justicia/eficiencia, no provoca
hambruna, desordena operaciones.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos: RAID
• RAID: Redundant Array of Inexpensibe Disks.
• Es un caso de virtualizaci´
on de almacenamiento.
• Pueden estar implementados por HW o por el SO.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos: RAID 0
• Striping (interleaving) por bloques.
• Sin redundancia.
• Bloques contiguos se escriben en paralelo.
9/17/12
upload.wikimedia.org/wikipedia/commons/9/9b/RAID_0.svg
RAID 0
Imagen: (cc) from Wikipedia
A1
A3
A5
A7
A2
A4
A6
A8
Disk 0
Disk 1
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos: RAID 1
• Mirror.
• Distintas lecturas en paralelo.
9/17/12
upload.wikimedia.org/wikipedia/commons/b/b7/RAID_1.svg
RAID 1
Imagen: (cc) from Wikipedia
A1
A2
A3
A4
A1
A2
A3
A4
Disk 0
Disk 1
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos: RAID 4
• Striping (interleaving) por bloques.
• Dedica un disco entero para la paridad.
• Se soporta el fallo de un disco.
9/17/12
upload.wikimedia.org/wikipedia/commons/a/ad/RAID_4.svg
RAID 4
Imagen: (cc) Wikipedia
A1
B1
C1
D1
A2
B2
C2
D2
A3
B3
C3
D3
Ap
Bp
Cp
Dp
Disk 0
Disk 1
Disk 2
Disk 3
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Discos: RAID 5
•
•
•
•
Striping (interleaving) por bloques.
La paridad est´a distribuida por los discos.
Se soporta el fallo de un disco.
File:RAID
5.svg
Soluciona
el cuello
de botella de RAID 4.
From Wikipedia, the free encyclopedia
9/17/12
File:RAID 5.svg -‐‑ Wikipedia, the free encyclopedia
No higher resolution available.
RAID_5.svg ​(SVG file, nominally 675 × 500 pixels, file size: 26 KB)
Imagen: (cc) Wikipedia
This image rendered as PNG in other sizes: 200px, 500px, 1000px, 2000px.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
SAN
• SAN (Storage Area Network): proporciona almacenamiento de
bloques a trav´es de la red.
• Es un disco en red, no es un sistema de ficheros en red.
• Ejemplos: iSCSI, ATA over Ethernet (AoE), HyperSCSI.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Particiones PC ()
Esquema tradicional de los PC (se est´a abandonando):
• MBR: Primer bloque del disco (512 bytes).
• Cargador primario: 440 bytes.
• Tabla de particiones primarias: 4 entradas de 16 bytes.
• Arrancable/no arrancable.
• Direcci´
on del primer bloque (CHS).
• Tipo de partici´
on (ntfs, linux, linux swap, plan9, ...).
• Direcci´
on del u
´ltimo bloque (CHS).
• Direcci´
on del primer bloque (LBA).
• N´
umero de bloques de la partici´
on.
• Direcciones de 32 bits: como mucho discos de 2TB.
• Partici´
on l´ogica: partici´
on dentro de una partici´on primaria
extendida.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Particiones UEFI
GUID Partition Table (GPT) :
• Usa direcciones y tama˜
nos de 64 bits.
• Primer bloque (LBA 0): legacy MBR.
• Segundo bloque (LBA 1): GPT header, con punteros para:
• Array de bloques con la tabla de particiones (empieza en LBA
2). El array tiene un tama˜
no m´ınimo de 16 Kb
independientemente del tama˜
no del sector f´ısico. Las entradas
en la tabla (128 bytes) continenen: tipo de particion, LBA del
primer bloque, LBA del u
´ltimo bloque, atributos (read-only,
oculta, etc.), nombre de particion...
• Copia de la cabecera.
• El primer bloque usable.
• ...
• El cargador est´
a en una partici´
on de tipo ESP (EFI System
Partition, que es una FAT).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sistemas de Ficheros
• Invenci´
on del SO para ofrecernos ficheros.
• Se puede implementar de distintas formas: asignaci´
on
continua, enlazada, enlazada con tabla, indexada...
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): contigua
• Un fichero ocupa una serie de bloques contiguos en disco.
• Acceso a disco r´
apido (secuencial).
• Rendimiento alto: un acceso para conseguir un dato
cualquiera → la entrada de directorio contiene la direcci´on de
inicio y la longitud del fichero.
• Problema: si hay asignaci´
on din´amica → fragmentaci´on
externa.
• Problema: hay que saber el tama˜
no m´aximo del fichero
cuando se crea.
• Compactaci´
on.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): enlazada
• Un fichero es una lista enlazada de bloques.
• Se tienen punteros al primer y al u
´ltimo bloque.
• Datos por bloque = tama˜
no de bloque - tama˜
no de estructura.
• Ventajas:
• No hay fragmentaci´
on externa.
• Tama˜
nos no limitados por huecos.
• Problemas:
• Acceso aleatorio ineficaz.
• Necesitamos estructura de metadatos en cada bloque para el
enlace.
¿qu´e pasa si se pierde una estructura?
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): enlazada de clusters
• Cluster: agrupaci´
on de bloques contiguos (e.g. 32 Kb).
• No se desperdicia tanto (1 estructura para n bloques).
• B´
usqueda m´as r´apida (menos saltos).
• Aumenta la fragmentaci´
on interna.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): enlazada con tabla
Tabla FAT:
• La tabla FAT reside en memoria.
• Una entrada por cluster.
• El ´ındice de la tabla es el n´
umero de cluster.
• La entrada de directorio tiene la referencia a la entrada primer
cluster.
• La entrada del cluster actual referencia la entrada del
siguiente cluster.
• Mejora del acceso aleatorio: no hay que leer los clusters del
fichero para conseguir la direcci´
on del cluster N.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): enlazada con tabla
FAT
0
0
1
-1
2
0
3
0
4
9
5
0
6
0
7
0
8
0
9
11
10
0
11
1
12
0
...
n
0
MYFILE.txt
First: 4
clusters:
4
9
11
1
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on enlazada con tabla: FAT
• Tabla FAT en memoria principal → no puede ser muy grande
→ clusters grandes → fragmentaci´
on interna.
• El acceso aleatorio es m´
as r´apido que en lista enlazada normal.
• ¿Y si se estropea la tabla FAT?
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ejemplo: FAT32
Reserved
sectors
Fat
Region
Data Region
• El sector 0 de la partici´
on es el boot sector (tambi´en
est´a duplicado en el sector 6). Contiene c´
odigo del cargador e
informaci´on sobre el sistema de ficheros:
•
•
•
•
•
No de sectores, 4 bytes (Max. tam. de disco: 2 Tb)
Etiqueta del volumen.
No de copias de la tabla FAT.
Primer cluster del ra´ız.
...
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ejemplo: FAT32
• Entrada de directorio (32 bytes):
•
•
•
•
•
•
•
•
Nombre del archivo, 8 Bytes.
Extensi´
on del archivo, 3 Bytes.
Atributos del archivo, 1 Byte.
Reservado, 10 Bytes.
Hora de la u
´ltima modificaci´
on, 2 bytes.
Fecha de la u
´ltima modificaci´
on, 2 bytes.
Primer cluster del archivo, 4 bytes.
Tama˜
no del archivo, 4 bytes.
• Clusters de 32 Kb, 64 sectores.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): indexada
• Idea: se indexan los bloques de datos del fichero en un bloque
de indirecci´on.
• Bloque de indirecci´
on grande → desperdicio.
• Bloque de indirecci´
on peque˜
no → no soporta ficheros grandes.
• Para un acceso a datos, siempre son dos accesos a disco.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio (FS): indexada multinivel
• Por niveles. P. ej. indirecci´
on doble:
• Los bloques de ´ındice de 1er nivel apuntan a bloques de ´ındice
de 2o nivel.
• Los bloques de ´ındice de 2o nivel apuntan a bloques de datos.
• Ejemplo: bloques de 4Kb con punteros de 4 bytes.
• Problema: Para los ficheros peque˜
nos, desperdiciamos.
• Problema: Para un acceso a datos, n accesos a disco.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Asignaci´on de espacio: indexada con esquema combinado
• Algunos bloques directos de datos.
• Algunos bloques de indirecci´
on simple.
• Algunos bloques de indirecci´
on doble.
• ...
• Nos quedamos con lo mejor de cada m´
etodo anterior.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Ficheros en UNIX: I-NODOS
Asignaci´on indexada con esquema combinado:
I-NODE
Data
Metadata
(size, mode, etc.)
Data
Data
...
Direct
Blocks
Data
Data
Direct
Blocks
Data
...
Single
Indirect
Double
Indirect
Data
Data
...
Single
Indirect
Triple
Indirect
...
...
...
Direct
Blocks
...
Data
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX: Partici´on
Boot
Block
Super
Block
I-Node vector
Data
• Bloque de arranque (boot block): c´
odigo de arranque del
sistema.
• Superbloque: tama˜
no del volumen, n´
umero de bloques libres,
lista de bloques libres, tama˜
no del vector de i-nodos, siguiente
i-nodo libre, cierres...
• Vector de i-nodos: representaci´
on de los ficheros.
• Bloques de datos.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX: I-NODOS
• Cada fichero/directorio tiene un i-nodo asociado, definido por
un n´
umero de i-nodo. El directorio ra´ız siempre tiene el
n´
umero de i-nodo 2.
• La estructura se localiza en el vector indexando por el n´
umero
de i-nodo.
• La estructura contiene:
• permisos
• tiempos
• acceso a datos (atime)
• modificaci´
on de los datos (mtime)
• modificaci´
on del i-nodo (ctime)
• tama˜
no
• due˜
no
• tipo
• n´
umero de bloques
• contador de referencias (links)
• No contiene el nombre de fichero.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX: I-NODOS
• Un directorio relaciona un nombre con un i-nodo, en una
entrada.
• Tiene:
• Su propio i-nodo
• Bloques de datos con la lista de entradas
• Entre las entradas, tiene la entrada de . (su i-nodo) y ..
(i-nodo del padre).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX: I-NODOS
/home/joe/test.txt
ROOT
2
2
3
5
DATA BLOCK
321
.
..
usr
home
5
2
7
9
...
I-NODE 5
DATA BLOCK
239
.
..
joe
jane
...
7
5
12
.
..
test.txt
...
I-NODE 7
METADATA
METADATA
direct-block
321
direct-block
239
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX: I-NODOS
• Enlaces duros: es otro nombre para el fichero, la entrada de
directorio apunta al mismo i-nodo que el antiguo nombre.
• Enlaces simb´
olicos: es un fichero cuyos datos contienen la ruta
al fichero enlazado → pueden romperse.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Implementaci´on de directorios
• Lineal
• Pro: simple.
• Contra: b´
usqueda lineal.
• Lineal ordenada
• Pro: b´
usqueda binaria.
• Contra: complica creaci´
on y borrado.
• Tabla hash con desbordamiento
• Pro: mucho m´
as r´apida que lineal.
• Contra: m´
as complejidad.
´
• Arboles
(e.g. b+ en NTFS, JFS...) ...
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Gesti´on de espacio libre
• Bitmap: r´
apido. Inconveniente: puede ser demasiado grande
como para tenerlo entero en memoria .P. ej. para 2TB de
bloques → mapa de 512 MB.
• Lista enlazada de bloques libres: ineficiente si buscamos
varios, pero por lo general s´
olo se busca uno libre.
• Agrupaciones: el primer nodo en la lista no est´
a vac´ıo; tiene
enlaces a n bloques libres, los n-1 primeros vac´ıos, el u
´ltimo
con n m´as. Ventaja: se pueden encontrar r´apidamente las
direcciones de n bloques libres.
• Cuenta: guarda en una lista el bloque libre y el n´
umero de
bloques contiguos libres que le siguen.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Espacio de nombres
• Se “camina” (walk) por la ruta, resolviendo cada parte.
• Se pueden “pegar” ´
arboles a nuestro espacio de nombres:
mount.
• Unix: un espacio de nombres para el sistema (comando mount
para listarlo).
• Plan 9: es controlable, puede haber un espacio de nombres
por proceso (comando ns para listarlo). Linux y otros han
adoptado esta idea.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Espacio de nombres
% 9fs marmita
/
386
...
usr
n
bin
marmita
/
FICHERO MONTADO
386
usr
bin
...
PUNTO DE MONTAJE
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Im´agenes de disco
• Un fichero que tiene dentro la estructura completa (sector por
sector) de un disco duro, CD-ROM (ISO 9660), floppy, etc.
• Utilidad: clonar sistemas, backups, crear CD/DVD, descargar
discos, m´aquinas virtuales, etc.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Im´agenes de disco
• Ejemplo en Linux: crear y usar una imagen de floppy:
~$
~$
~$
~$
~$
~$
~$
~$
~$
~$
~$
~$
# creo un fichero de 1,44 MB con ceros
dd if=/dev/zero of=/tmp/f bs=512 count=2880
# formateo la imagen de floppy con VFAT
mkfs.vfat -v -c /tmp/f
# monto en el punto de montaje /mnt/floppy
mount -o loop /tmp/f -t vfat /mnt/floppy
# creo un fichero en el floppy
touch /mnt/floppy/afile
# ver el espacio de nombres
mount
# desmontar el volumen
umount /mnt/floppy
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Uniones
• Consiste en unir varios directorios en uno.
• Utilidades: compartir c´
odigo fuente, agrupar binarios (/bin),
reunir ficheros para crear un backup (CD,DVD,...),
distribuciones live, etc.
• Idea de Plan 9. UnionFS y Aufs en UNIX.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Uniones
• Ejemplo en Plan 9: crear una uni´
on de tres directorios en el
directorio $home/union
term %
term %
term %
term %
term %
bind -bc /tmp/a $home/union
bind -bc /tmp/b $home/union
# en $home/union vemos los ficheros de
# /tmp/b, /tmp/a, y $/home/union, en ese orden
ls $home/union
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Mecanismo: Proyecci´on en memoria
• mmap: mapea un fichero en memoria para poder acceder a los
datos del fichero como si fuese un buffer, sin usar read ni
write.
• El fichero se trae poco a poco → paginaci´
on por demanda.
• Llamadas al sistema: mmap y munmap en UNIX.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
FS de Plan 9: fossil + venti
• Venti es un servidor de bloques en espacio de usuario,
identificados por su hash SHA-1 (20 bytes).
• Venti nunca borra los bloques.
• Fossil es un sistema de ficheros en espacio de usuario, que
puede usar bloques del disco y bloques de venti.
• Fossil tiene snapshots ef´ımeros y permanentes.
• Para crear un snapshot permanente, archiva los bloques en
venti.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
FS en espacio de usuario en UNIX
• VFS (Virtual File System): interfaz com´
un con el kernel para
todos los FS.
• FUSE: m´
odulo del kernel para implementar sistemas de
ficheros en espacio de usuario que se puedan integrar con VFS.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
FS en espacio de usuario en UNIX
Userspace
App
App
App
FS
Kernel
VFS
UFS
EXT3
FUSE
VFAT
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Cache
• El kernel mantiene una cache en RAM para los bloques.
• Es muy eficiente. P. ej. La buffer cache de 4.4BSD evita el
85 % de los accesos a disco/red para conseguir bloques.
• En ocasiones es recomendable salt´
arsela (e.g. modo O DIRECT
de open en Linux).
• Cuando el sistema se est´
a quedando sin marcos de p´agina, se
suele sacrificar espacio de la cache.
• El comando y llamada al sistema sync de UNIX sincroniza la
cache con el disco y actualiza el superbloque. Se ejecuta
peri´odicamente.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Cache
Tipos de cache (en general):
• Escrituras:
• S´ıncrona (write-trough): evita problemas de coherencia.
• As´ıncrona (delayed write-back): incrementa el rendimiento.
• Para accesos secuenciales:
• Read-ahead.
• Free-behind.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Fallos
• Perder la integridad de los metadatos (estructuras del FS) es
peor que perder datos.
• ¿Usamos una cache write-back para los datos y/o los
metadatos?
• Al crear un fichero, ¿creamos antes el i-nodo o la entrada en
el directorio?
• Al borrar un fichero, ¿liberamos antes el i-nodo o su entrada
en el directorio?
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Fallos
Despu´es de un fallo:
• Hay programas para reparar el sistema de ficheros, e.g. fsck
en UNIX.
• Hay que recorrer los bloques de los ficheros para detectar
errores, e.g.:
• Un bloque est´
a asignado a un fichero y en la lista de bloques
libres a la vez.
• Un bloque en dos ficheros a la vez.
• Esto es caro.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Journaling
Ideas b´asicas:
•
•
•
•
Las operaciones se escriben en un journal (en disco) de forma at´
omica.
Una vez escritas en el journal las operaciones est´
an comprometidas.
En alg´
un momento las operaciones se aplicar´
an en el FS.
Si el sistema falla, al rearrancar se aplican todas las operaciones pendientes en el
journal (si las hay) para recuperar la coherencia.
• Desventaja: hay que escribir los datos dos veces en el disco (pero en el journal
es secuencial).
• Normalmente se hace journaling s´olo de los metadatos.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Soft Updates
Ideas b´asicas:
•
•
•
•
La escritura de los metadatos es as´ıncrona (write-back).
El usuario siempre ve la versi´
on m´
as reciente (en cache).
En el disco siempre hay una versi´
on coherente.
Se establecen dependencias entre las escrituras de metadatos, que marcan el
orden al que van al disco, e.g.:
• Nunca se referencia una estructura no inicializada.
• Nunca se reusa una estructura sin borrar todas las referencias a la misma.
• No se borra un puntero antiguo hasta que el nuevo est´a puesto (e.g.
renombrado de un fichero).
• Tras un fallo, se puede montar el volumen inmediatamente.
• Es complicado de implementar, mantener y ampliar.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Soft Updates
Ejemplo de situaci´on de rollback, dependencia c´ıclica:
• Las entradas de directorio de /A/B y de /A/C est´
an en el
mismo bloque X.
• Los inodos de /A/B y de /A/C est´
an en el mismo bloque Y.
• Se quieren hacer las siguientes operaciones:
1. Crear fichero /A/B, operaciones en orden:
1.1 Actualizar i-nodo.
1.2 Meter entrada de directorio.
2. Borrar fichero /A/C, operaciones en orden:
2.1 Borrar entrada de directorio.
2.2 Marcar i-nodo como libre.
• Y no puede escribirse antes que X, ni X antes que Y.
• Hay que deshacer una operaci´
on, escribir los bloques,
rehacerla, y escribir de nuevo los bloques.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sistemas de ficheros distribuidos
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sistemas de ficheros en red
• Permite compartir ficheros a trav´
es de la red siguiendo un
esquema cliente/servidor.
• El cliente y el servidor deben hablar un protocolo de sistema
de ficheros.
• Protocolos: NFS, CIFS/SMB, WebDAV, 9P, AFP, ...
• NAS (Network-Attached Storage): HW especializado en servir
un FS en red, con RAID, etc.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sistemas de ficheros en red
• Stateless
• Sencillo.
• Operaciones autocontenidas.
• Los handles que da el servidor tienen que ser u
´nicos (eg. fs id
+ inodo + versi´
on).
• No requiere recuperaci´
on tras un fallo.
• El servidor se puede reemplazar.
• Stateful
• Sesiones / estado permanente.
• El servidor puede olvidar los handles despu´
es de una sesi´on.
• Fallo del servidor → recuperar del estado o abortar.
• ¿Cache coherente? ¿Locking ? ¿Callbacks? ¿Read-ahead?
¿DMEXCL? ¿DMAPPEND?
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Sem´anticas de compartici´on de ficheros
Las m´as comunes:
• Sem´
antica UNIX (Strong Consistency).
• Sem´
antica de sesi´
on.
• Ficheros inmutables.
• Transacciones.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
NFS
• Varias versiones diferentes.
• Hasta NFSv3 era stateless:
• File handles opacos, elegidos por el servidor.
• No hay open ni close.
• Problemas con locking, coherencia de cache, etc.
• NFSv4: stateful, RPCs compuestas, etc.
• Muy complejo:
ACCESS, BACKCHANNEL CTL, BIND CONN TO SESSION, CLOSE, COMMIT, CREATE, CREATE SESSION,
DELEGPURGE, DELEGRETURN, DESTROY CLIENTID, DESTROY SESSION, EXCHANGE ID, FREE STATEID,
GETATTR, GETDEVICEINFO, GETDEVICELIST, GETFH, GET DIR DELEGATION, LAYOUTCOMMIT, LAYOUTGET,
LAYOUTRETURN, LINK, LOCK, LOCKT, LOCKU, LOOKUP, LOOKUPP, NVERIFY, OPEN, OPENATTR,
OPEN CONFIRM, OPEN DOWNGRADE, PUTFH, PUTPUBFH, PUTROOTFH, READ, READDIR, READLINK,
RECLAIM COMPLETE, RELEASE LOCKOWNER, REMOVE, RENAME, RENEW, RESTOREFH, SAVEFH, SECINFO,
SECINFO NO NAME, SEQUENCE, SETATTR, SET CLIENTID, SET CLIENTID CONFIRM, SET SSV,
TEST STATEID, VERIFY, WANT DELEGATION, WRITE...
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
UNIX + NFS
Client
File Server
Userspace
App
App
Userspace
App
App
App
system calls
system calls
Kernel
Kernel
VFS
UFS
EXT3
VFS
VFAT
App
NFS
client
NFS
RPC
UFS
network
NFS
server
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P
• Stateful: el servidor mantiene el estado de la conexi´
on.
• Stateful: posibilita la exportaci´
on de ficheros sint´eticos.
• Sencillo: s´
olo 13 RPCs.
• Totalmente integrado con el SO: el kernel de Plan 9 es un
multiplexor de 9P.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P
Userspace
FS
FS
App
Userspace
FS
system calls
Kernel
9P
#M
mount
driver
9P 9P*
...
9P*
#p
proc
9P
9P*: Within the kernel, 9P is
implemented by procedure
calls to the various kernel device
drivers.
Kernel
9P*
...
#c
cons
FS
network
9P
9P
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P: RPCs
• size[4] Tversion tag[2] msize[4] version[s]
size[4] Rversion tag[2] msize[4] version[s]
Acuerda la versi´
on del protocolo y comienza una nueva sesi´
on.
• size[4] Tauth tag[2] afid[4] uname[s] aname[s]
size[4] Rauth tag[2] aqid[13]
Autenticaci´
on (externa a trav´
es de P9SK1).
• size[4] Rerror tag[2] ename[s]
Error para todos los tipos de peticiones.
• size[4] Tflush tag[2] oldtag[2]
size[4] Rflush tag[2]
Aborta la petici´
on identificada con oldtag.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P: RPCs
• size[4] Tattach tag[2] fid[4] afid[4] uname[s] aname[s]
size[4] Rattach tag[2] qid[13]
El cliente se ata al ra´ız del sistema de ficheros. A partir de este momento se
referir´
aa´
el con el FID. El servidor responde con un identificador u
´nico para el
ra´ız QID (versi´
on, tipo y path).
• size[4] Twalk tag[2] fid[4] newfid[4] nwname[2] nwname*(wname[s])
size[4] Rwalk tag[2] nwqid[2] nwqid*(wqid[13])
Resuelve un path, que ser´
a referido con el FID newfid. Si no se pueden
atravesar todos los nombres, newfid ser´
a fid. El servidor devuelve la lista de
QIDs de los nombres que se han podido atravesar.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P: RPCs
• size[4] Topen tag[2] fid[4] mode[1]
size[4] Ropen tag[2] qid[13] iounit[4]
• size[4] Tcreate tag[2] fid[4] name[s] perm[4] mode[1]
size[4] Rcreate tag[2] qid[13] iounit[4]
• size[4] Tread tag[2] fid[4] offset[8] count[4]
size[4] Rread tag[2] count[4] data[count]
• size[4] Twrite tag[2] fid[4] offset[8] count[4] data[count]
size[4] Rwrite tag[2] count[4]
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P: RPCs
• size[4] Tremove tag[2] fid[4]
size[4] Rremove tag[2]
• size[4] Tstat tag[2] fid[4]
size[4] Rstat tag[2] stat[n]
• size[4] Twstat tag[2] fid[4] stat[n]
size[4] Rwstat tag[2]
• size[4] Tclunk tag[2] fid[4]
size[4] Rclunk tag[2]
Cierra el fichero representado por ese FID, ya no ser´
a referido m´
as.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
9P: RPCs
a new fid (16 in the figure), which st
of the fid mentioned (15 in the figure)
this request walks that new fid to a p
its original position in the server’s fil
case, fid 16 points to the file /a/b/c w
once the walk transaction completes.
a stat request asks the server for meta
entry) for the file identified by the fid
client issues a clunk request when it n
to use a particular fid, to let the serv
it and release any resource used on it
The part in the figure below the l
corresponds to a client reading a file
request defines a new fid (16 again) a
the file of interest, /a/b/c in this c
open transaction opens the fid for the
in the request (not shown). After rece
the client issues read requests (and th
with data) for the offsets and number o
Usually, the series of read transaction
by a last one, which is used by the s
the client that there is no more data
the offset requested; this is the end-of
At this point, the client probably clos
a clunk transaction releases (and clos
Figure 1: Styx dialog between a client (left) and a
server (rigth).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
FS distribuidos en cluster
• Los bloques de los ficheros est´
an distribuidos.
• Finalidad: file striping.
• Ejemplo: Google FS.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
• Tolera fallos de los servidores.
• Optimizado para append y lecturas.
• Escalabilidad: miles de nodos por cluster, petabytes de datos.
• Sacrifican latencia por throughput.
• Coherencia relajada: las r´
eplicas pueden diferir en ciertas
partes. Las aplicaciones deben lidiar con esto.
• Ficheros partidos en chunks de 64Mb (con checksum).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Imagen: (CC) Wikipedia
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Master:
´
• ¿Unico
punto de fallo?
• Shadow Masters.
• ¿Cuello de botella? No, s´
olo mantiene el control, no hace
I/O, ni coordina modificaciones en los chunks (mutaci´on).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Master:
• Almacena s´olo los metadatos: todo en memoria, log en disco para asegurar
coherencia.
• Las actualizaciones de metadatos son at´omicas.
• Controla el espacio de nombres.
• Hace polling para localizar los chunks, rebalancear y controlar ca´ıdas de
chunk-servers.
•
•
•
•
•
•
Crea nuevos chunks.
Ordena la replicaci´
on de chunks en chunk-servers (3+).
Controla los leases de las r´
eplicas primarias.
Controla los locks sobre ficheros/directorios.
Realiza la recolecci´
on de basura.
No coordina las mutaciones (un write en un chunk).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Cliente:
• No tienen cache de datos.
• Tiene cache (con tiempo de caducidad) de metadatos
(chunk-handles, etc.).
• Suele resolver distintos chunks a la vez.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Mutaci´on: Write (poco usada)
1. El cliente pide al Master la lista de r´
eplicas y el primario.
2. El Master elige un primario si no hay. El primario adquiere un lease. El
cliente cachea la respuesta del Master para futuras peticiones. Esos
datos pueden caducar.
3. El cliente env´ıa los datos a todas las r´
eplicas. Las r´
eplicas guardan los
datos en sus buffers.
4. El cliente env´ıa una petici´
on write al primario.
5. El primario serializa las distintas mutaciones que recibe y las aplica al
chunk. Va enviando la secuencia al resto de r´
eplicas.
6. Cada r´
eplica aplica las modificaciones en el orden que dicta el primario.
Al aplicar un cambio, notifica al primario.
7. Tras recibir las notificaciones de las r´
eplicas para el write, se responde
al cliente. Si hay error en las r´
eplicas, el cliente puede reintentar (desde
el paso 3 o desde el paso 1). Despu´
es del fallo habr´
a zonas de la r´
eplica
fallida incoherentes → sem´
antica relajada (weak).
Image extracted from the original
GFS paper (SOSP 2003).
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Caso: Google FS
Mutaci´on: Atomic Record Append (muy usada)
1. El cliente env´ıa los datos del append a todas las r´
eplicas.
2. El cliente ordena el atomic-append al primario.
3. El primario comprueba si se desborda el u
´ltimo chunk.
• Si se desborda, se rellena con un hueco el chunk y se le indica al cliente
que la operaci´
on se debe realizar en el siguiente chunk (el Master lo
crear´
a) → Fragmentaci´
on interna. El tama˜
no de un append est´
a limitado
para evitar mucha fragmentaci´
on (1/4 de tama˜
no de chunk).
• Si no se desborda, se serializa la escritura en el chunk como en un write.
4. Si falla alguna r´
eplica secundaria,se repite la operaci´
on append
• El offset se avanza de todas formas en las r´eplicas que fallaron: todos los
chunks tienen el mismo tama˜
no).
• Los datos del append aparecen repetidos en las r´eplicas que no fallaron →
sem´
antica at-least-once.
Sistemas de ficheros locales
Sistemas de ficheros distribuidos
Bibliograf´ıa
•
•
•
•
•
•
A. S. Tanenbaum. Operating Systems, design and implementaiton. Pearson Prentice Hill.
A. S. Tanenbaum. Distributed Systems. Pearson Prentice Hill.
A. S. Tanenbaum. Modern Operating Systems. Pearson Prentice Hill.
A. Silberschatz. Operating Systems. Wiley.
Plan 9 User Manual, Section 5, Introduction (man 5 0intro).
S. Ghemawat, H. Gobioff, S. Leung. The Google File System. SOSP 2003.