Dateisysteme
Quellen
Dateisysteme
Hochleistungs-Ein-/Ausgabe
Michael Kuhn
Wissenschaftliches Rechnen
Fachbereich Informatik
Universität Hamburg
2015-04-20
Michael Kuhn
Dateisysteme
1 / 50
Dateisysteme
Quellen
1 Dateisysteme
Orientierung
Dateisysteme
ext4
Object Stores
Datenstrukturen
Leistungsbewertung
Ausblick und Zusammenfassung
2 Quellen
Michael Kuhn
Dateisysteme
2 / 50
Dateisysteme
Quellen
Orientierung
E/A-Schichten
Anwendung
Bibliotheken
Paralleles verteiltes Dateisystem
Dateisystem
Speichergerät/-verbund
Abbildung: E/A-Schichten
Michael Kuhn
Dateisysteme
3 / 50
Dateisysteme
Quellen
Dateisysteme
Aufgabe
Strukturierung
Üblicherweise Dateien und Verzeichnisse
Hierarchische Organisation
Andere Ansätze: Tagging
Verwaltung von Daten und Metadaten
Blockallokation
Zugriffsrechte, Zeitstempel etc.
Dateisysteme nutzen ein darunter liegendes Speichergerät
Oder einen Speicherverbund
Logical Volume Manager (LVM) und/oder mdadm
Michael Kuhn
Dateisysteme
4 / 50
Dateisysteme
Quellen
Dateisysteme
Beispiele
Linux: ext4, XFS, . . .
Windows: FAT, exFAT, NTFS
OS X: HFS+
Universal: ISO9660, . . .
Michael Kuhn
Dateisysteme
5 / 50
Dateisysteme
Quellen
Dateisysteme
Beispiele. . .
Netzwerk: NFS, AFS, Samba
Kryptographisch: EncFS, eCryptfs
Parallel verteilt: GPFS, Lustre, . . .
Pseudo: procfs, . . .
Setzen häufig auf darunterliegenden Dateisystemen auf
Michael Kuhn
Dateisysteme
6 / 50
Dateisysteme
Quellen
Dateisysteme
E/A-Operationen
1 fd = open("/path/to/file", O_RDWR | O_CREAT |
,→ O_TRUNC, S_IRUSR | S_IWUSR);
2 nb = write(fd, data, sizeof(data));
3 rv = close(fd);
4 rv = unlink("/path/to/file");
Listing 1: E/A über Low-Level-Funktionen
Initialer Zugriff über Pfad
Danach über File Descriptor (FD)
Michael Kuhn
Dateisysteme
7 / 50
Dateisysteme
Quellen
Dateisysteme
VFS
Virtual File System (Switch)
Zentrale Dateisystemkomponente im Kernel
Standardisiertes Interface für alle Dateisysteme (POSIX)
Gibt Dateisystemstruktur größtenteils vor
Leitet Anfragen der Anwendungen weiter
Basierend auf dem Mountpoint
Michael Kuhn
Dateisysteme
8 / 50
Dateisysteme
Quellen
Dateisysteme
VFS. . .
mmap
(anonymous pages)
malloc
...
chmod(2)
stat(2)
open(2)
write(2)
read(2)
Applications (Processes)
VFS
direct I/O
(O_DIRECT)
block based FS
ext2 ext3 ext4
xfs btrfs ifs
iso9660 gfs ocfs
...
Network FS
NFS coda
smbfs
...
ceph
pseudo FS
proc sysfs
pipefs futexfs
...
usbfs
special
purpose FS
tmpfs ramfs
Page
Cache
devtmpfs
network
stackable
BIOs (Block I/O)
optional
struct bio
BIOs (Block I/O)
devices on top of “normal”
block devices
LVM
drbd
device mapper mdraid
dm-crypt
dm-mirror
...
dm-cache dm-thin
bcache
-
sector on disk
sector cnt
bio_vec cnt
bio_vec index
bio_vec list
The Linux Storage Stack Diagram
http://www.thomas-krenn.com/en/wiki/Linux_Storage_Stack_Diagram
Created by Werner Fischer and Georg Schönberger
License: CC-BY-SA 3.0, see http://creativecommons.org/licenses/by-sa/3.0/
Abbildung: Virtual File System [3]
Michael Kuhn
Dateisysteme
9 / 50
Dateisysteme
Quellen
Dateisysteme
VFS. . .
Virtual Host
malloc
...
stat(2)
chmod(2)
read(2)
vfs_writev, vfs_readv, ...
open(2)
write(2)
ISCSI
mmap
(anonymous pages)
Applications (Processes)
LIO
tcm_vhost
tcm_usb_gadget
USB
FireWire
Fibre Channel
over Ethernet
tcm_fc
version 3.17, 2014-10-17
outlines the Linux storage stack as of Kernel version 3.17
sbp_target
tcm_qla2xxx
iscsi_target_mod
Fibre Channel
The Linux Storage Stack Diagram
VFS
Network FS
NFS coda
block based FS
ext2 ext3 ext4
xfs btrfs ifs
iso9660 gfs ocfs
...
direct I/O
(O_DIRECT)
target_core_mod
target_core_file
target_core_iblock
...
smbfs
special
purpose FS
pseudo FS
proc sysfs
pipefs futexfs
...
ceph
usbfs
target_core_pscsi
Page
Cache
tmpfs ramfs
devtmpfs
network
optional
stackable
BIOs (Block I/O)
struct bio
- sector on disk
- sector cnt
- bio_vec cnt
- bio_vec index
- bio_vec list
BIOs (Block I/O)
devices on top of “normal”
block devices
LVM
drbd
device mapper mdraid
dm-mirror
...
bcache
dm-crypt
dm-cache
dm-thin
BIOs
BIOs
BIOs
Block Layer
I/O Scheduler
blkmq
maps bios to requests
multi queue
noop
...
cfq
hooked in device drivers
(they hook in like stacked
devices do)
Software
Queues
deadline
Hardware
Dispatch
Queue
...
request-based
device mapper targets
dm-multipath
Hardware
Dispatch
Queues
BIO
based Drivers
Request
based Drivers
Request
based Drivers
/dev/vd*
/dev/nullb*
/dev/rssd*
SCSI Mid Layer
null_blk
/dev/rbd*
SCSI upper level drivers
/dev/sda /dev/sdb ...
virtio_blk
sysfs
(transport attributes)
mtip32xx
/dev/nvme#n#
/dev/skd*
rbd
Transport Classes
nvme
scsi_transport_fc
skd
network
scsi_transport_sas
SCSI low level drivers
scsi_transport_...
libata
megaraid_sas
ahci ata_piix ...
qla2xxx
virtio_scsi
iscsi_tcp
lpfc
aacraid
mpt3sas
...
vmw_pvscsi
network
HDD
SSD
virtio_pci
DVD
drive
LSI
RAID
Qlogic
HBA
Adaptec
RAID
Emulex
HBA
para-virtualized
SCSI
LSI 12Gbs
SAS HBA
Micron
PCIe Card
nvme
device
stec
device
VMware's
para-virtualized
SCSI
Physical devices
The Linux Storage Stack Diagram
http://www.thomas-krenn.com/en/wiki/Linux_Storage_Stack_Diagram
Created by Werner Fischer and Georg Schönberger
License: CC-BY-SA 3.0, see http://creativecommons.org/licenses/by-sa/3.0/
Abbildung: E/A-Stack in Linux 3.17 [3]
Michael Kuhn
Dateisysteme
10 / 50
Dateisysteme
Quellen
Dateisysteme
Dateisystemobjekte
Dateien
Enthalten Daten in Form eines Byte-Arrays
Können gelesen/geschrieben werden (explizit)
Können in den Speicher gemappt werden (implizit)
Verzeichnisse
Enthalten Dateien und Verzeichnisse
Zur Organisation des Namensraumes
Michael Kuhn
Dateisysteme
11 / 50
Dateisysteme
Quellen
Dateisysteme
Dateisystemobjekte. . .
Inodes
Enhalten Metadaten
Eigentliche Basisobjekte des Dateisystems
Üblicherweise eindeutige IDs
Michael Kuhn
Dateisysteme
12 / 50
Dateisysteme
Quellen
Dateisysteme
Dateien
1 nb = pwrite(fd, data, sizeof(data), 42);
2 nb = pread(fd, data, sizeof(data), 42);
Listing 2: Expliziter Zugriff
pwrite und pread verhalten sich wie write bzw. read
Explizite Angabe des Offsets
Zugriff über File Descriptor
Michael Kuhn
Dateisysteme
13 / 50
Dateisysteme
Quellen
Dateisysteme
Dateien. . .
1 char* pt = mmap(NULL, FILE_SIZE, PROT_READ |
,→ PROT_WRITE, MAP_SHARED, fd, 0);
2 memcpy(pt + 42, data, sizeof(data));
3 memcpy(data, pt + 42, sizeof(data));
4 munmap(pt, sizeof(data));
Listing 3: Impliziter Zugriff
mmap erlaubt es eine Datei in den Speicher einzublenden
Datei beginnt an Adresse pt
Zugriff wie auf andere Speicherobjekte
Z.B. via memcpy oder direkte Zuweisung
Michael Kuhn
Dateisysteme
14 / 50
Dateisysteme
Quellen
Dateisysteme
Verzeichnisse
Inode
Größe
Namenslänge
Dateityp
Name
23
24
10
11
..
.
2
3
2
2
.\0
..\0
14
14
6
6
..
.
42
43
..
.
..
.
1
2
..
.
hello\0
world\0
Abbildung: ext4-Verzeichniseintrag [1]
Traditionell lineares Array
Langsam, da über das komplette Array iteriert werden muss
Heutzutage eher Baumstrukturen
Michael Kuhn
Dateisysteme
15 / 50
Dateisysteme
Quellen
Dateisysteme
Inodes
Feldgröße
Inhalt
2 Bytes
2 Bytes
4 Bytes
4 Bytes
4 Bytes
4 Bytes
4 Bytes
2 Bytes
2 Bytes
..
.
60 Bytes
..
.
4 Bytes
100 Bytes
Berechtigungen
Benutzer-ID
Dateigröße
Zugriffszeit
Inode-Änderungszeit
Datenänderungszeit
Löschzeit
Gruppen-ID
Linkzahl
..
.
Blockzeiger, Extent-Baum oder Inline-Daten
..
.
Versionsnummer
Freier Speicher
Abbildung: ext4-Inode (256 Bytes) [1]
Michael Kuhn
Dateisysteme
16 / 50
Dateisysteme
Quellen
Dateisysteme
Inodes. . .
Kompliziert durch Rückwärtskompatibilität
Viele Felder sind aufgeteilt
Zeitstempel: 4 Bytes für Sekunden seit 1970, 4 Bytes für
Nanosekundenauflösung
Größe: Obere und untere 4 Bytes
Felder mehrfach überladen
Blockzeiger, Extent-Baum oder Inline-Daten (falls Datei
kleiner als 60 Bytes)
100 Bytes am Inode-Ende für erweiterte Attribute
Michael Kuhn
Dateisysteme
17 / 50
Dateisysteme
Quellen
Dateisysteme
Inodes. . .
1
2
3
4
5
6
7
8
9
10
11
12
13
$ touch foo
$ ls -l foo
-rw-r--r--. 1 u g 0 19. Apr
$ ln foo bar
$ ls -l foo bar
-rw-r--r--. 2 u g 0 19. Apr
-rw-r--r--. 2 u g 0 19. Apr
$ stat --format=%i foo bar
641174
641174
$ rm foo
$ ls -l bar
-rw-r--r--. 1 u g 0 19. Apr
18:48 foo
18:48 bar
18:48 foo
18:48 bar
Listing 4: Inode vs. Datei
Michael Kuhn
Dateisysteme
18 / 50
Dateisysteme
Quellen
Dateisysteme
POSIX-Schnittstelle
open, close, creat
read, write, lseek
chmod, chown, stat
link, unlink
...
Michael Kuhn
Dateisysteme
19 / 50
Dateisysteme
Quellen
ext4
ext4
Standard-Dateisystem in vielen Linux-Distributionen
Eingeführt 2006, stabil 2008
Vorgänger: ext, ext2, ext3
Statische Festlegung bei Dateisystemerzeugung
Inode-Zahl
Blockgröße
Michael Kuhn
Dateisysteme
20 / 50
Dateisysteme
Quellen
ext4
ext
Erstes Dateisystem speziell für Linux
Nutzte als erstes Dateisystem die VFS-Schicht
Inspiriert vom Unix File System (UFS)
Beseitigte Beschränkungen des MINIX-Dateisystems
Dateigrößen bis 2 GB
Dateinamen bis 255 Zeichen
Michael Kuhn
Dateisysteme
21 / 50
Dateisysteme
Quellen
ext4
ext2
Separate Zeitstempel für Zugriff und
Inode-/Datenänderung
Datenstrukturen für zukünftige Erweiterungen ausgelegt
Testumgebung für neue VFS-Funktionen
Access Control Lists (ACLs)
Erweiterte Attribute
Michael Kuhn
Dateisysteme
22 / 50
Dateisysteme
Quellen
ext4
ext3
Journaling
Dateisystemvergrößerung zur Laufzeit
H-Baum für größere Verzeichnisse
Michael Kuhn
Dateisysteme
23 / 50
Dateisysteme
Quellen
ext4
ext4
Größere Dateisysteme, Dateien und Verzeichnisse
Extents
Preallokation, verzögerte Allokation und verbesserte
Multiblockallokation
Journal-Prüfsummen
Schnellere Dateisystemüberprüfung
Nanosekunden-Zeitstempel
Unterstützung für TRIM
Michael Kuhn
Dateisysteme
24 / 50
Dateisysteme
Quellen
ext4
ext4. . .
Inhalt
Padding (Blockgruppe 0)
Superblock
Gruppenbeschreibung
Reservierte GDT-Blöcke
Daten-Bitmap
Inode-Bitmap
Inode-Tabelle
Daten-Blöcke
Größe
1.024 Bytes
1 Block
n Blöcke
m Blöcke
1 Block
1 Block
k Blöcke
l Blöcke
Abbildung: ext4-Blockgruppe [1]
Michael Kuhn
Dateisysteme
25 / 50
Dateisysteme
Quellen
ext4
ext4. . .
Blockgröße
Blöcke
Inodes
Dateisystemgröße
Dateigröße (Extents)
Dateigröße (Blöcke)
1 KiB
264
232
16 ZiB
4 TiB
16 GiB
2 KiB
264
232
32 ZiB
8 TiB
256 GiB
4 KiB
264
232
64 ZiB
16 TiB
4 TiB
64 KiB
264
232
1 YiB
256 TiB
256 PiB
Abbildung: ext4-Limits im 64-Bit-Modus [1]
Michael Kuhn
Dateisysteme
26 / 50
Dateisysteme
Quellen
ext4
Allokation
Blockbasiert
Viele Blöcke gleicher Größe (üblicherweise 4 KiB)
Zeiger auf Blöcke
Direkt, indirekt, doppelt indirekt, dreifach indirekt
Michael Kuhn
Dateisysteme
27 / 50
Dateisysteme
Quellen
ext4
Allokation. . .
Abbildung: Block-Zeiger [2]
Michael Kuhn
Dateisysteme
28 / 50
Dateisysteme
Quellen
ext4
Allokation. . .
Extentbasiert
Wenige möglichst große Extents
Vier Extents können im Inode gespeichert werden
Mehr in einer Baumstruktur und zusätzlichen Blöcken
Zeiger auf Startblock und Länge
Maximale Länge: 32.768 Blöcke
Entspricht 128 MiB bei einer Blockgröße von 4 KiB
Michael Kuhn
Dateisysteme
29 / 50
Dateisysteme
Quellen
ext4
Allokation. . .
Blockallokation
Versuche zusammenhängende Blöcke zu allokieren
Versuche Blöcke in derselben Blockgruppe zu allokieren
Multiblockallokation und verzögerte Allokation
Spekulativ 8 KiB bei Dateierzeugung allokieren
Allokation wird erst durchgeführt, wenn Blöcke auf das
Speichergerät geschrieben werden müssen
Michael Kuhn
Dateisysteme
30 / 50
Dateisysteme
Quellen
ext4
Allokation. . .
Dateien und Verzeichnisse
Blöcke möglichst in der Blockgruppe des Inodes allokieren
Dateien möglichst in der Blockgruppe des Verzeichnisses
allokieren
Michael Kuhn
Dateisysteme
31 / 50
Dateisysteme
Quellen
ext4
Sparse-Dateien und Preallokation
Sparse-Dateien: Dateien mit „Löchern“
Z.B. mit lseek oder truncate
Effiziente Speicherung von Dateien mit vielen 0-Bytes
1
2
3
4
5
$ truncate --size=1G dummy
$ ls -lh dummy
-rw-r--r--. 1 u g 1,0G 18. Apr 23:49 dummy
$ du -h dummy
0 dummy
Listing 5: Erzeugung einer Sparse-Datei
Michael Kuhn
Dateisysteme
32 / 50
Dateisysteme
Quellen
ext4
Sparse-Dateien und Preallokation. . .
Preallokation: Speicher vorallokieren
Mit fallocate bzw. posix_fallocate
Verhindert Fragmentierung bei vielen Dateivergrößerungen
1
2
3
4
5
$ fallocate --length $((1024 * 1024 * 1024)) dummy
$ ls -lh dummy
-rw-r--r--. 1 u g 1,0G 19. Apr 19:14 dummy
$ du -h dummy
1,1G dummy
Listing 6: Preallokation einer Datei
Michael Kuhn
Dateisysteme
33 / 50
Dateisysteme
Quellen
ext4
Journaling
Journaling zur Sicherung der Konsistenz des Dateisystems
Dateisystemoperationen benötigen mehrere Schritte
Z.B. das Löschen einer Datei
Entfernen des Verzeichniseintrags
Freigeben des Inodes
3 Freigeben der Datenblöcke
1
2
Problematisch im Fall eines Absturzes
Michael Kuhn
Dateisysteme
34 / 50
Dateisysteme
Quellen
ext4
Journaling. . .
Geplante Änderungen werden ins Journal eingetragen
Entfernen wenn Operation vollständig durchgeführt
Bei der anschließenden Dateisystemüberprüfung
Änderungen wiederholen oder
Änderungen verwerfen
Unterschiedliche Modi
Metadaten-Journaling und volles Journaling
Michael Kuhn
Dateisysteme
35 / 50
Dateisysteme
Quellen
ext4
Journaling. . .
Journal: Alle Änderungen werden ins Journal geschrieben
Ordered: Metadaten werden ins Journal geschrieben
Daten vor Metadaten
Problematisch mit verzögerter Allokation
Writeback: Metadaten werden ins Journal geschrieben
Reihenfolge beliebig
Michael Kuhn
Dateisysteme
36 / 50
Dateisysteme
Quellen
Object Stores
Funktionen
„Dateisystem light“
Dünne Abstraktionsschicht über Speichergeräten
Objektbasierter Zugriff auf Daten
Nur Grundoperationen
Erstellen, Öffnen, Schließen, Lesen, Schreiben
Manchmal Object Sets
Können benutzt werden um verwandte Objekte zu
gruppieren
Michael Kuhn
Dateisysteme
37 / 50
Dateisysteme
Quellen
Object Stores
Funktionen. . .
Üblicherweise keine Pfade
Zugriff über eindeutige IDs
Kein Overhead durch Pfadauflösung
Block-/Extent-Allokation
Auf unterschiedlichen Abstraktionsebenen verfügbar
Cloudspeicher, Festplatte
Michael Kuhn
Dateisysteme
38 / 50
Dateisysteme
Quellen
Object Stores
Schichtung
Object Stores können als Unterbau für Dateisysteme
genutzt werden
Erlaubt Konzentration auf Dateisystemfunktionalität
Speicherverwaltung durch separate Schicht
Bei lokalen Dateisystemen nicht sinnvoll
Funktionalität größtenteils durch POSIX vorgegeben
Hauptunterschied ist Blockallokation
Sehr sinnvoll für parallele verteilte Dateisysteme
Kein redundanter Dateisystem-Overhead
Michael Kuhn
Dateisysteme
39 / 50
Dateisysteme
Quellen
Datenstrukturen
B-Baum vs. B+-Baum
7 16
1
2
5
6
9 12
18 21
Abbildung: B-Baum [4]
7 16
1
2
5
6
7
9 12
16 18 21
Abbildung: B+-Baum [4]
Michael Kuhn
Dateisysteme
40 / 50
Dateisysteme
Quellen
Datenstrukturen
B-Baum vs. B+-Baum. . .
B-Baum
Verallgemeinerter Binärbaum
Optimiert für Systeme, die große Blöcke lesen/schreiben
Zeiger und Daten gemischt
B+-Baum
Daten nur in Blättern
Vorteilhaft für Caching, da einfacher alle Knoten zu cachen
Benutzt in NTFS, XFS, . . .
Michael Kuhn
Dateisysteme
41 / 50
Dateisysteme
Quellen
Datenstrukturen
H-Baum
Basiert auf B-Baum
Andere Behandlung von Hash-Kollisionen
Benutzt in ext3 und ext4
Michael Kuhn
Dateisysteme
42 / 50
Dateisysteme
Quellen
Leistungsbewertung
Leistungsbewertung
Dateisystemleistung ist schwierig zu bewerten
Viele unterschiedliche Faktoren
Daten- vs. Metadatenleistung
Leistung unterschiedlicher Funktionen
Leistung für spezifische Anforderungen messen
Datensicherheit kostet üblicherweise Leistung
Volles Journaling, Prüfsummen etc.
Michael Kuhn
Dateisysteme
43 / 50
Dateisysteme
Quellen
Leistungsbewertung
Kernel- vs. Userspace
Dateisysteme üblicherweise direkt im Kernel implementiert
Hoher Wartungsaufwand
Alternative: Filesystem in Userspace (FUSE)
Besteht aus Kernelmodul und Bibliothek
Entwicklung von Dateisystemen als normale Prozesse
Michael Kuhn
Dateisysteme
44 / 50
Dateisysteme
Quellen
Leistungsbewertung
Kernel- vs. Userspace. . .
./hello /tmp/fuse
ls -l /tmp/fuse
libfuse
glibc
glibc
Userspace
Kernel
FUSE
NFS
VFS
Ext3
...
Abbildung: FUSE [5]
Umleitung in Userspace durch VFS und FUSE-Modul
Geringere Leistung durch Kontextwechsel
Michael Kuhn
Dateisysteme
45 / 50
Dateisysteme
Quellen
Ausblick und Zusammenfassung
Ausblick
Moderne Dateisysteme integrieren zusätzliche Funktionen
Volumenverwaltung, Prüfsummen, Schnappschüsse, . . .
Basis für parallele verteilte Dateisysteme
Object Stores besser geeignet
Michael Kuhn
Dateisysteme
46 / 50
Dateisysteme
Quellen
Ausblick und Zusammenfassung
Zusammenfassung
Dateisysteme organisieren Daten und Metadaten
Üblicherweise standardisierte Schnittstelle
Hauptobjekte sind Dateien und Verzeichnisse
Inodes speichern Metadaten
Neue Techniken zur Effizienzsteigerung
Journaling um Konsistenz sicherzustellen
Speicherallokation mit Hilfe von Extents
Baumstrukturen für skalierbaren Zugriff
Michael Kuhn
Dateisysteme
47 / 50
Dateisysteme
Quellen
1 Dateisysteme
Orientierung
Dateisysteme
ext4
Object Stores
Datenstrukturen
Leistungsbewertung
Ausblick und Zusammenfassung
2 Quellen
Michael Kuhn
Dateisysteme
48 / 50
Dateisysteme
Quellen
Quellen I
[1] djwong. Ext4 Disk Layout. https://ext4.wiki.kernel.
org/index.php/Ext4_Disk_Layout.
[2] Hal Pomeranz. Understanding Indirect Blocks in Unix File
Systems. http:
//digital-forensics.sans.org/blog/2008/12/24/
understanding-indirect-blocks-in-unix-file-systems.
[3] Werner Fischer and Georg Schönberger. Linux Storage Stack
Diagramm. https://www.thomas-krenn.com/de/wiki/
Linux_Storage_Stack_Diagramm.
[4] Wikipedia. B-tree.
http://en.wikipedia.org/wiki/B-tree.
Michael Kuhn
Dateisysteme
49 / 50
Dateisysteme
Quellen
Quellen II
[5] Wikipedia. Filesystem in Userspace. http:
//en.wikipedia.org/wiki/Filesystem_in_Userspace.
Michael Kuhn
Dateisysteme
50 / 50
© Copyright 2024 ExpyDoc
