Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 11.AFS (Andrew File System) e GFS (Google File System)


Andrew File System

File System distribuito, compatibile con NFS.

  • Il sistema di filing nei server è NFS-based.

L’obiettivo principale è la scalabilità.

  • AFS è stato progettato per garantire livelli di prestazioni accettabili anche in presenza di un vasto numero di applicazioni clienti.

La strategia chiave per conseguire la scalabilità è il meccanismo di caching lato client:
I server inviano ai client l’intero contenuto di una directory (whole-file serving).

  • Se le dimensioni sono maggiori di 64 KB, sono suddivisi in chunk (di 64 KB).

La cache lato client è di tipo permanente (non volatile), su disco, allo scopo di sopravvivere ai reboot dei client (whole-file caching).

Assunzioni

Il progetto di AFS nasce dopo un’attenta osservazione sui workload tipici di un filesystem UNIX [Satyanarayanan’81, Ousterhout’85, Floyd 1986].
I file di un FS sono di piccole dimensioni (circa l’80% non supera i 64 KB).
Le operazioni di lettura sono molto più frequenti di quelle di scrittura (circa 6 volte più numerose).
L’accesso sequenziale è molto più frequente dell’accesso diretto.
La maggior parte dei file condivisi sono modificati solo da un stesso utente.
Gli accessi ad un file mostrano interessanti caratteristiche di località sia temporale sia spaziale.

Principi di funzionamento

Un processo utente invoca un “open” per un file (che non risiede nella cache) nello spazio condiviso.
Viene contattato il server che contiene il file, il quale provvede ad inviare una copia dello stesso al processo richiedente.
La copia del file viene memorizzata sul disco del client.
La system call open, invocata dal client, restituirà un file descriptor (convenzionale) della copia locale.
Tutti gli accessi eseguiti dall’applicazione client saranno effettuati sulla copia locale del file.
Quando il processo invoca una close:

  • la copia locale viene comunque mantenuta dal client
  • se la copia del file è stata alterata, viene inviata al server per eseguire l’update (anche dei metadati).

Osservazioni

La cache può avere lunghi periodi di validità in caso di file che non sono alterati frequentemente oppure che sono alterati solo da un medesimo utente.
Dato il basso costo della memoria di massa, si può pensare di predisporre cache permanenti di dimensioni elevate (≈102 MByte). Ciò consente alle applicazioni client di operare su copie di file contenute nel file system locale.

Osservazioni

Ci sono classi di file per le quali le assunzioni di AFS non valgono. Ad esempio:

  • per file di grosse dimensioni;
  • quando ci sono molte operazioni di scrittura;
  • nel caso di frequenza elevata di operazioni in conflitto su un blocco.

→ DATABASE
Tali classi di file sono state esplicitamente escluse dai progettisti di AFS.

Modello architetturale


Modello architetturale

Distizione tra macchine client e macchine server data da due componenti software distinti.

  • Vice: software lato server che presentano ai client uno spazio di nomi condivisi in forma di gerarchia omogenea e con trasparenza di locazione.
  • Venus: processo utente che viene eseguito su ogni client.

System call

AFS utilizza un versione modificata del kernel di UNIX.
Le modifiche consistono in un modulo kernel per l’intercettazione delle system call di I/O.
Le system call intercettate sono poi inoltrate al processo Venus.


Spazio dei nomi

I file possono essere locali o condivisi.
I file locali sono tipicamente i file temporanei e quelli essenziali per lo start-up.
I file condivisi sono mantenuti dal server.
Gli altri file sono collegati allo spazio condiviso tramite link simbolici.


Spazio dei nomi

I file sono raggruppati in volumi che compongono lo spazio dei nomi condivisi.
I volumi di Andrew sono solitamente più piccoli di quelli del file system NFS: solitamente un volume contiene i file di un unico utente.
Un file o una directory sono identificati nello spazio dei nomi condiviso da un identificatore di basso livello chiamato fid

<VolumeNumber, FileHandle, Uniquifier>

I Vice accettano richieste solo in termini di fid, pertanto i Venus devono utilizzare lookup prima di effettuare una richiesta ai server.

Implementazione delle system call


Mobilità dei volumi

Le informazioni sulla locazione sono conservate in un database locazione-volume, del quale esiste una replica su ogni server.
Quando un volume viene inviato da un server ad un altro, nel server originale rimane temporaneamente l’informazione relativa alla spedizione per cui non è necessario aggiornare il database della locazione in modo sincrono.
Durante la fase di trasferimento il server di origine continua a gestire gli aggiornamenti del volume, che in seguito vengono spediti al nuovo server.

Caching

AFS utilizza una schema per il controllo della consistenza di tipo asincrono, basato su callback (distribuite):
Quando Vice fornisce una copia di un file a Venus, esso allega al file una callback promise, cioè un token generato dal server che viene utilizzato per notificare ai processi Venus la modifica di un file da parte di altri client.
Le callback promise possono assumere due stati:

  1. valid: il file è valido;
  2. cancelled: il file è invalidato, pertanto bisognerà accedere al server per prelevarne una copia aggiornata.

Caching

Quando Vice aggiorna un file, notifica tutti i client ai quali aveva inviato la callback promise per quel file.
Il client che riceve la notifica, imposta la propria callbackpromise a cancelled.
Quando Venus apre un file, controlla se il file è presente in cache:
Se è presente, Venus controlla la callback promise:

  • Se è valid, la copia in cache può essere usata
  • Se è cancelled, bisogna richiedere un aggiornamento della copia locale

Altrimenti, Venus richiede una copia.

Caching


Modello dei guasti ed azioni di ripristino

Venus Failure: L’azione di ripristino consiste in un reboot.
Al momento del ripristino, però, Venus invaliderà tutte le entry della sua cache (durante il periodo di maintainance potrebbe aver perso delle callback).
A seguito del suo ripristino, Venus invierà una serie di richieste di validazione della cache ai vari server. Le richieste contengono il timestamp, lato client, dell’ultima modifica.
Due tipi di risposta possono essere ottenute:

  1. valid: il server comunica ai client che il timestamp è valido;
  2. cancelled: il timestamp non è aggiornato. In tal caso le entry sono marcate come “cancelled”. Il file sarà aggiornato solo alla successiva richiesta di accesso.

Modello dei guasti ed azioni di ripristino

Link Failure: vengono rilevati con tecniche basate su timeout.
Le callback devono essere rinnovate periodicamente (con un tempo T dell’ordine di qualche minuto).
Prima di effettuare un open su un file, il processo Venus accerta che la callback sia stata rinnovata dal server nell’ultimo periodo. In caso negativo, ne richiede il rinnovo al server.

Consistenza

La verifica della consistenza viene fatta solo all’atto dell’apertura di un file.
Le modifiche sono notificate a tutti i client solo all’atto della chiusura di un file.
Se più client operano in concorrenza sullo stesso file, solo le modifiche derivanti dall’ultima close avranno effetto, mentre le altre saranno perse (senza alcuna segnalazione di errore).
Il controllo della concorrenza deve essere implementato separatamente, se richiesto:
Per questo motivo, Vice offre delle primitive per effettuare il “lock” e la “unlock” di un file o directory.

Interfaccia Vice

Operazioni quali Rename, MakeDir, ecc., non sono mostrate

Operazioni quali Rename, MakeDir, ecc., non sono mostrate


Considerazioni finali

Studi sperimentatli hanno dimostrato che sotto le ipotesi e i workload descritti, AFS è in grado di conseguire ottimi livelli di scalabilità.
Il meccanismo asincrono, basato su callback, è stato adottato per minimizzare l’overhead dei messaggi su rete: la comunicazione tra server e client avviene solo a fronte di effettive modifiche.
Tale meccanismo richiede comunque la memorizzazione di informazioni di stato (i server devono sapere a quali client hanno inviato la callback promise).

Google File System

File System Distribuito scalabile per applicazioni distribuite data-intensive.
Buoni livelli di fault tolerance e performance anche se in esecuzione su commodity hardware economico.

Sviluppato (ed utilizzato) da Google.

Motivazioni e assunzioni

Condivide con i precedenti DFS obiettivi come performance, scalabilità, affidabilità.
La progettazione è stata guidata anche da altre assunzioni.
Component failures are the norm rather than the exception” – vengono utilizzate migliaia di macchine economiche e derivate da altri utilizzi: necessità di monitoraggio, error detection, fault tolerance, recovery automatico.
File di grosse dimensioni (Multi-GB), ciascuno contenente molti oggetti di applicazioni (miliardi di file di pochi KB): necessità di rivedere e operazioni di I/O e dimensioni dei blocchi.
Molti file sono modificati con delle appending piuttosto che con sovrascrittura; inoltre, tali operazioni sono effettuate concorrentemente da più client
performance ed atomicità devono essere basata su tale funzione.

Motivazioni e assunzioni

La progettazione congiunta di applicazioni e file system consente di migliorare la flessibilità.
Il carico consiste principalmente di due tipi di letture: large streaming reads e small random reads: le operazioni dovrebbero essere effettuate scorrendo il file di continuo, piuttosto che con spostamenti in direzioni opposte.
Molte applicazioni effettuano operazioni su grosse mole di dati ad alta frequenza e in poche hanno requisiti stringenti relativamente ai tempi delle singole operazioni di lettura/scrittura: una larghezza di banda grande è più importante di una bassa latenza.

Interfaccia

Semplice ma non rispetta lo standard POSIX.
Supporta operazioni comuni quali create, delete, open, close, read, write.
Inoltre offre le operazioni di

  • snapshot: copia “basso costo” di un file o di una directory
  • record append: consente a più client di effettuare append su un file in maniera concorrente e garantendo l’atomicità.

Architettura

L’architettura prevede:

  • un master
  • client multipli
  • chunckserver multipli.

Su una macchina possono esserci sia chunckserver che client.

I file sono divisi in chunk di dimensione fissa.
Ogni chunk è identificato da un chunk handle (64 bit) assegnato dal master quando il chunk è creato.
Ciascun chunk è replicato (tre volte per default) per ragioni di affidabilità.

Master

Il master conserva i metadata del file system (namespace, mappatura tra file e chunk, mappatura tra chunk e chunckserver).
Si occupa del controllo dello stato dei chunkserver, di garbage collection e della migrazione dei chunk.
Per ogni chunk sono memorizzati 64 Byte: non sono persistenti, il master interroga periodicamente i chunkserver con dei messaggi HertBeat anche per sapere chi conserva i chunk.
Ciò elimina il problema di sincronizzare master e chunkserver in seguito ad eventi su questi ultimi (spostamenti, riavvii, fallimenti, …).

Master

Si prevede la presenza di un solo master così da semplificare il design e il placement dei chunk:

  • tuttavia, bisogna ridurre l’accesso al master per evitare che sia un collo di bottiglia
  • talvolta si utilizzano degli shadow masters che consentono solo operazioni di lettura per evitare il single point of failure.

Master

Il master si occupa anche della creazione di un Operation Log che contiene informazioni relative alle variazioni dei metadata:

  • è l’unica informazione persistente sui metdata ed è fondamentale per avere il tempo logico del sistema (in quanto consente di definire l’ordine con cui sono avvenute operazioni concorrenti)
  • è memorizzato su diverse macchine attraverso operazioni di checkpointing del master: tali operazioni sono effettuate in modo da non ritardare altre operazioni in corso (il master crea un nuovo log mentre un thread si occupa del trasferimento del precedente).

Client

Le API del file system sono fornite ai client per la comunicazione con il master ed i chunckserver.
La comunicazione con il master è effettuata solo per ottenere metadata relativi ai chunk

  • caching dei metadata da parte del client
  • in seguito la comunicazione è diretta con il chunkserver.

Architettura


Dimensione dei chunk

I chunk hanno una dimensione di 64 MB, maggiore della dimensione di un blocco in un tipico file system.

Vantaggi

  • Riduce l’interazione dei client con il master (non occorre richiedere informazioni su molti chunk per effettuare operazioni su un file).
  • I client possono effettuare più operazioni su un solo chunk diminuendo l’overhead della rete.
  • Riduce la quantità di metadati che il master deve memorizzare.

Svantaggi
Se un file è composto di un solo chunk, i chunkserver che lo memorizzano possono diventare hot spots (si può ovviare consentendo la lettura da altri client).

Modello di consistenza

Una regione di un file si dice consistent se tutti i client vedranno sempre gli stessi dati, indipendentemente dalla replica a cui accedono.
Una regione di un file è defined in seguito ad una mutazione del file stesso se è consistente e i client vedranno cosa ha scritto la mutazione nella sua interezza.

Mutazioni

Le mutazioni possono essere operazioni di write o di append.
Viene utilizzato un meccanismo basato su lease per rendere le mutazioni consistenti tra le varie repliche.

Il master fornisce un lease ad una prima replica detta primary.
Tale replica effettua le mutazioni richieste concorrentemente sul chunk in maniera sequenziale.
Tutte le altre repliche seguono lo stesso ordine per mutare il chunk: l’ordine globale delle mutazioni è definito dall’ordine con cui sono forniti i lease alle repliche da parte del master e, in ciascun lease, dai numeri seriali assegnati alle varie operazioni di mutazione richieste dai client dalla primary replica.

Mutazioni – write

  1. Chiede al master chi ha il lease; se non lo ha nessuno il master sceglie una primary replica.
  2. Il master fornisce le identità della replica primaria e delle secondarie.
  3. Il client passa i dati alle repliche in qualsiasi ordine (disaccoppiamento del flusso dati dal flusso di controllo).
  4. Dopo che tutte le repliche confermano la ricezione dei dati, il client invia una richiesta di scrittura alla replica primaria. Tale replica assegna dei numeri seriali alle varie mutazioni richieste dai client.
  5. La replica primaria inoltra la richiesta di scrittura alle altre repliche. Queste seguiranno l’ordine determinato dalla replica primaria.
  6. Le repliche secondarie notificano il completamento delle operazioni alla replica primaria.
  7. La replica primaria comunica il termine delle operazioni al client.

Fault tolerance

Replicazione dei chunk.
Log diagnostici dei server.
Master replication:

  • lo stato del master è replicato (meccanismi di logging e checkpointing)
  • Shadow master per accessi in lettura in caso di fallimento del master

Integrità dei dati

  • I chunkserver utilizzano checksum per rilevare corruzione sui dati; ogni chunk è suddiviso in blocchi di 64 KB, ciascuno con una checksum a 32 bit.

Garbage collection

Il problema della garbage collection distribuita può essere facilmente risolto in GFS:

  • tutti i riferimenti ai chunk sono nella tabella che mappa file e chunk nel master
  • le repliche sono file in particolari directory dei chunkserver
  • quindi, una qualsiasi replica che non è nota al master è “garbage”.

Prestazioni

Il read rate arriva all’80% del limite imposto dalla rete.
Buone prestazioni anche nelle operazioni di mutazione.
Writes are slower than we would like”.
Ma non è un problema in pratica poiché aumenta la latenza ma non inficia la larghezza di banda.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion