Date post: | 22-Jan-2018 |
Category: |
Education |
Upload: | luca-vitale |
View: | 83 times |
Download: | 2 times |
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
The Design and Implementation of aLog-Structured File System
Gioele Ciaparrone, Luca Vitale
Sistemi Operativi Avanzati A.A. 2015/2016Corso di Laurea Magistrale in Informatica
Prof. Giuseppe Cattaneo
29 Aprile 2016
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 1 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Overview
1 IntroduzioneAutoriContesto storicoDefinizione del problema
2 Log-structured file systemIntroduzioneGestione dello spazio liberoCrash recovery
3 Analisi delle prestazioniSistema utilizzato per i benchmarkRisultati
4 Conclusioni
5 Riferimenti
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 2 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Autori
Mendel Rosenblum
1992: Ph.D. in CS all’University ofCalifornia, Berkeley
1998: Cofondatore di VMware
Attualmente professore a Stanford neidipartimenti di Computer Science edElectrical Engineering
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 3 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Autori
John Ousterhout
1980: Ph.D. in CS alla Carnagie MellonUniversity
1994-1998: sviluppatore del linguaggioTcl alla Sun Mycrosystems
Attualmente professore di CS allaStanford University e chairman diElectric Cloud Inc.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 4 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Contesto storico
Breve storia dei file system
1968 – George 3 [6]
1980 – FAT12 [4]
1984 – FAT16 [4], Berkeley Fast File System [9]
1992 – Sprite Log-structured File System (LFS) [10]
1993 – NTFS [8], ext2 [1]
1996 – FAT32 [4]
2001 – ext3 [2]
2006 – ext4 [3]
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 5 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Cos’è un file system
File system
Un file system è l’insieme delle strutture dati necessarie per lamemorizzazione, l’organizzazione gerarchica, lamanipolazione, la navigazione, l’accesso e la lettura dei dati.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 6 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Problema
Miglioramento velocità CPU vs. latenza accesso al disco
Le applicazioni tenderanno ad essere più I/O bound
Fondamentale ottimizzare l’utilizzo del disco
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 7 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Design di un file system
Il design di un file system è guidato da due forze fondamentali:
Tecnologia
Workload
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 8 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Tecnologia
Tre componenti tecnologiche determinano l’efficienza di un filesystem:
Velocità della CPU
Capacità e latenza della RAM
Bandwidth e tempo di accesso al disco
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 9 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Workload
Due tipologie di workload:
Ufficio: accessi casuali a tanti piccoli file
Supercomputing: accesso sequenziale a grandi file
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 10 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Definizione del problema
Problemi dei file system tradizionali
Dati sparsi sul disco
In UNIX FFS 5 seek per creare un file
Utilizzato solo 5% della bandwidth
Operazione di write sincrona
Scrittura di tanti piccoli file rallentata
Soluzione: Sprite LFS
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 11 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Introduzione
Sprite LFS
Log-structured file system
È un file system in cui dati e metadati vengono scrittisequenzialmente in un buffer circolare, chiamato log.
Ogni sequenza di cambiamenti viene bufferizzata in cachee poi scritta sequenzialmente sul log (disco)
Miglioramento delle performance in scrittura
Si evitano sincronizzazioni
Una sola seek per ogni svuotamento della cache
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 12 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Introduzione
Lettura di un file I
La lettura di un file non richiede accesso sequenziale al log
Per individuare i blocchi di un file si usa l’inode
inode
È una struttura dati sul file system che archivia e descriveattributi base di file e directory, tra cui anche la posizione deiblocchi di dati che li compongono.
L’inode utilizzato da Sprite LFS ha la stessa struttura diquello di Unix FFS
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 13 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Introduzione
Lettura di un file II
Ad ogni file (o directory) è associato un inode
A differenza di Unix, gli inode non sono in posizioni fisse
Si usa quindi un’inode map, che mantiene gli indirizzi fisicidegli inode per ogni file
I blocchi dell’inode map sono scritti nel log e il loro indirizzoè salvato in una regione fissa del disco
L’inode map viene mantenuta in cache, evitando frequentiaccessi al disco
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 14 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Introduzione
Esempio: creazione di due file
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 15 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Problema dello spazio libero
Il problema principale di un log-structured file system èquello di mantenere grandi sezioni contigue di spaziolibero su disco
Esistono due opzioni per gestire la frammentazione dellospazio libero:
Threading
Copying
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 16 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Threading e copying I
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 17 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Threading e copying II
Lo svantaggio del threading è che serve più di una seekper scrivere dati nel log
Non è più veloce di un file system tradizionale
Lo svantaggio del copying è che la copiatura dei blocchi didati può richiedere molto tempo
Sprite LFS sceglie quindi una combinazione di threading ecopying
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 18 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Threading e copying III
Il disco viene diviso in grandi sezioni di grandezza fissachiamate segmenti
I dati vengono scritti sequenzialmente dall’inizio alla fine diogni segmento
Prima di poter riscrivere dati in un segmento, i dati livedevono essere ricopiati fuori da esso
Il threading viene effettuato a livello dei segmenti
Segmenti abbastanza grandi da sfruttare la larghezza dibanda del disco
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 19 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Meccanismo di pulitura dei segmenti I
Pulitura dei segmenti
È il processo di copia di blocchi di dati live all’esterno di unsegmento.
L’obiettivo è quello di aumentare il numero di segmentivuoti
Sprite LFS non utilizza bitmap o liste per tener traccia deiblocchi liberi
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 20 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Meccanismo di pulitura dei segmenti II
Processo composto da tre fasi:
Lettura di un certo numero di segmenti
Identificazione dei blocchi di dati live
Riscrittura dei dati live in un numero minore di segmenti
I segmenti letti vengono quindi marcati come puliti epossono essere utilizzati per la scrittura di nuovi dati
Per identificare i dati live in ogni segmento viene scritto unsegment summary block , che indica per ogni blocco delsegmento l’id del file a cui appartiene, il numero del bloccoe la versione del file
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 21 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Politiche di pulitura I
1 Quando eseguire la pulitura dei segmenti?
2 Quanti segmenti pulire ogni volta?
3 Quali segmenti pulire?
4 Come raggruppare i blocchi di dati live quando vengonoricopiati?
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 22 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Politiche di pulitura II
Le scelte 1 e 2 non hanno influenzato particolarmente leprestazioni del sistema
Le scelte 3 e 4 si sono rivelate fondamentali
Per confrontare le prestazioni è stato introdotto il concettodi write cost , che ci dà un’informazione sulla bandwidthdel disco effettivamente utilizzata per scrivere nuovi dati
write cost =total bytes read and written
new data written
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 23 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Politiche di pulitura III
Se per ogni scrittura si effettuasse una pulitura deisegmenti, avremmo un write cost pari a 2/(1 − u)
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 24 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Obiettivo
Per migliorare le performance del sistema è necessarioottenere una distribuzione bimodale della frazione di datilive dei segmenti
Molti segmenti quasi pieni e molti segmenti quasi vuoti
Per ottenere questa distribuzione vediamo come sceglierei segmenti da pulire e come raggruppare i dati live ricopiati
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 25 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Simulazione del sistema I
Sono state simulate le prestazioni del sistema modellandoun file system con tanti file da 4KB ciascuno
Sono stati modificati i file seguendo due pattern diversi:
Uniforme – stessa probabilità di modifica di ogni file
Hot-and-cold – 90% dei file modificati il 10% delle volte e ilrestante 10% modificato il 90% delle volte (località)
Scelta greedy dei segmenti da pulire: i più vuoti
I dati live sono stati ricopiati nello stesso ordine nel casouniforme e ordinati per età nel caso hot-and-cold
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 26 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Simulazione del sistema II
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 27 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Problema della scelta greedy
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 28 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Soluzione: cost-benefit policy
I segmenti con dati modificati raramente (cold) tendono amantenere molto spazio libero per molto tempo
La soluzione è dare più peso allo spazio libero deisegmenti cold
Politica cost-benefit:
benefitcost
=free space generated ∗ age of data
cost=
(1 − u) ∗ age1 + u
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 29 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Effetti della cost-benefit policy I
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 30 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Gestione dello spazio libero
Effetti della cost-benefit policy II
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 31 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Crash recovery
Crash recovery
Nei file system tradizionali in caso di crash del sistema ènecessario effettuare una scansione di tutto il file systemper risolvere le inconsistenze
Nei LFS è facile determinare la posizione delle ultimeoperazioni effettuate sul disco: recovery più veloce
Sprite LFS utilizza due strumenti per la recovery:
Checkpoint
Roll-forward
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 32 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Crash recovery
Checkpoint I
Checkpoint
È la posizione nel log fino alla quale tutte le strutture dati del filesystem sono consistenti e complete.
Dopo aver scritto i dati sul disco, viene aggiornata lacheckpoint region, salvata in una posizione fissa deldisco
La checkpoint region contiene i dati che permettono diverificare la consistenza del sistema (tra cui data eposizione dell’ultima operazione effettuata)
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 33 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Crash recovery
Checkpoint II
Sprite LFS effettua checkpoint a intervalli periodici equando il file system viene smontato
La lunghezza degli intervalli influenza l’overhead discrittura e la quantità di dati da recuperare in caso di crash
Lunghi intervalli: meno overhead, ma più tempo per larecovery
Brevi intervalli: più overhead, ma minor costo di recovery
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 34 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Crash recovery
Roll-forward
Invece di scartare tutte le modifiche effettuate dopo l’ultimocheckpoint, possiamo cercare di recuperare i dati
Sprite LFS scansiona quindi i dati dopo l’ultimo checkpoint(roll-forward)
Utilizza quindi i dati presenti nei segment summary blockper tentare di ripristinare quante più informazioni possibili
Per garantire la consistenza delle directory, utilizza undirectory operation log, che salva le modifiche effettuatealle directory prima di riscrivere gli inode
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 35 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Sistema utilizzato per i benchmark
Implementazione di Sprite LFS
L’implementazione di Sprite LFS non è risultata piùcomplicata dei file system tradizionali come Unix FFS
La versione utilizzata per i test non implementava ilroll-forward
Intervallo tra i checkpoint di 30 secondi
Nell’uso di tutti i giorni gli utenti non hanno percepitodifferenze con Unix FFS, probabilmente perché lemacchine non erano abbastanza veloci da essereI/O-bound
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 36 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Sistema utilizzato per i benchmark
Sistema utilizzato I
Benchmark eseguiti su Sun 4/260
CPU con IU Fujitsu SF9010 e FPUWeitek 1164/1165, 16.67 MHz
32 MB RAM
HDD: Wren IV, bandwidth 1.3 MB/s,latenza 17.5 ms, 300 MB
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 37 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Sistema utilizzato per i benchmark
Sistema utilizzato II
Confronto tra Sprite LFS e SunOS 4.0.3
Blocchi da 8 KB su SunOS, da 4 KB su Sprite LFS consegmenti da 1 MB
Multiutente
Caso ottimo: nessuna pulitura dei segmenti durante ibenchmark
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 38 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Risultati
Performance su file piccoli
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 39 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Risultati
Performance su file grandi
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 40 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Risultati
Simulazione con overhead di pulitura I
Per valutare l’overhead causato dalla pulitura dei segmenti,è stato effettuato un test su un sistema reale per unperiodo di 4 mesi
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 41 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Risultati
Simulazione con overhead di pulitura II
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 42 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Risultati
Performance di crash recovery
Usato un sistema con intervallo di checkpoint infinito e chenon salvava le modifiche alle directory
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 43 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Conclusioni I
Il principio fondamentale di un log-structured file system èquello di scrivere i nuovi dati in cache, per poi scriverli sudisco in un’unica grande operazione di I/O
Massimizzazione della bandwidth usata per scrivere datinuovi
È possibile ottenere bassi costi di overhead di pulitura conla cost-benefit policy
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 44 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Conclusioni II
Performance migliori dei file system esistenti su piccoli file
Performance simili o migliori su grandi file tranne in pochicasi (lettura sequenziale di file scritti random)
Sistema più CPU-bound: miglioramento delle performancecon l’aumento delle prestazioni delle CPU
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 45 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
I log-structured file system oggi I
L’idea del log viene sfruttata attualmente nei journalingfile system [5]
NTFS, ext3+, UFS dal 2004
Tuttavia il log mantiene solo le modifiche al file system, manon include i blocchi di dati
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 46 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
I log-structured file system oggi II
I log-structured file system sono utili su device che hannoun numero limitato di scritture in ogni locazione perchédiminuiscono il numero di scritture eseguite nella stessalocazione [7]
UDF (dischi ottici)
LogFS, YAFFS, F2FS (memorie flash)
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 47 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Riferimenti I
Ext2.https://en.wikipedia.org/wiki/Ext2.Accessed: 2016-04-22.
Ext3.https://en.wikipedia.org/wiki/Ext3.Accessed: 2016-04-22.
Ext4.https://en.wikipedia.org/wiki/Ext4.Accessed: 2016-04-22.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 48 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Riferimenti II
File Allocation Table.https:
//en.wikipedia.org/wiki/File_Allocation_Table.Accessed: 2016-04-22.
Journaling.https://it.wikipedia.org/wiki/Journaling.Accessed: 2016-04-27.
List of default file systems.https://en.wikipedia.org/wiki/List_of_default_
file_systems.Accessed: 2016-04-22.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 49 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Riferimenti III
List of log-structured file systems.https://en.wikipedia.org/wiki/List_of_
log-structured_file_systems.Accessed: 2016-04-27.
NTFS.https://en.wikipedia.org/wiki/NTFS.Accessed: 2016-04-22.
M. K. McCusick, W. N. Joy, S. J. Leffler, and R. S. Fabry.A Fast File System for UNIX.1984.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 50 / 51
Introduzione Log-structured file system Analisi delle prestazioni Conclusioni Riferimenti
Riferimenti IV
Mendel Rosenblum and John Ousterhout.The design and implementation of a log-structured filesystem.1992.
Università degli Studi di Salerno Log-Structured File System 29 Aprile 2016 51 / 51