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 2025 ExpyDoc