WIXLIB

AusgabeMichael KuhnWissenschaftliches RechnenFachbereich InformatikUniversität Hamburg2018-04-13Michael KuhnDateisysteme1 / 52

ystemeext4Object StoresDatenstrukturenLeistungsbewertungAusblick und Zusammenfassung2 QuellenMichael KuhnDateisysteme2 / 52

iothekenParalleles verteiltes dung: E/A-Schichten und orthogonale ThemenMichael KuhnDateisysteme3 / 52

ngÜblicherweise Dateien und VerzeichnisseHierarchische OrganisationAndere Ansätze: TaggingVerwaltung von Daten und MetadatenBlockallokationZugriffsrechte, Zeitstempel etc.Dateisysteme nutzen ein darunter liegendes SpeichergerätOder einen SpeicherverbundLogical Volume Manager (LVM) und/oder mdadm unter LinuxMichael KuhnDateisysteme4 / 52

DateisystemeQuellenDateisystemeBeispieleLinux: tmpfs, ext4, XFS, btrfs, ZFSWindows: FAT, exFAT, NTFSOS X: HFS , APFSUniversal: ISO9660, UDFMichael KuhnDateisysteme5 / 52

DateisystemeQuellenDateisystemeBeispiele.Netzwerk: NFS, AFS, SambaKryptographisch: EncFS, eCryptfsParallel verteilt: GPFS, LustrePseudo: sysfs, procSetzen häufig auf darunterliegenden Dateisystemen aufMichael KuhnDateisysteme6 / 52

nfragen werden über E/A-Schnittstellen realisiertWeiterleitung an das DateisystemUnterschiedliche AbstraktionsebenenLow-Level-FunktionalitätPOSIX, MPI-IOHigh-Level-FunktionalitätHDF, NetCDF, ADIOSMichael KuhnDateisysteme7 / 52

fdnbrvrv open("/path/to/file", O RDWR O CREAT O TRUNC, S IRUSR S IWUSR);write(fd, data, sting 1: E/A über Low-Level-FunktionenInitialer Zugriff über PfadDanach über File Descriptor (bis auf einige Ausnahmen)Funktionen befinden sich in der libcDiese führt System Calls durchMichael KuhnDateisysteme8 / 52

DateisystemeQuellenDateisystemeE/A-Operationen.Mit open können auch Dateien erstellt werdenViele mögliche Flags und Modiwrite liefert die Anzahl der geschriebenen Bytes zurückMuss nicht notwendigerweise der übergebenen Größe entsprechen(Fehlerbehandlung!)write verändert intern den Dateizeiger (alternativ: pwrite)Alle Funktionen liefern einen RückgabewertBei Fehlern sollte errno überprüft werdenMichael KuhnDateisysteme9 / 52

DateisystemeQuellenDateisystemeVFSVirtual File System (Switch)Zentrale Dateisystemkomponente im KernelStandardisiertes Interface für alle Dateisysteme (POSIX)Gibt Dateisystemstruktur und -schnittstelle größtenteils vorLeitet Anfragen der Anwendungen weiterBasierend auf dem MountpointErmöglicht die Unterstützung unterschiedlichster DateisystemeAnwendungen bleiben durch POSIX trotzdem portabelMichael KuhnDateisysteme10 / 52

DateisystemeQuellenDateisystemeVFS. . . [3]mmap(anonymous Applications (Processes)VFSdirect I/O(O DIRECT)block based FSext2 ext3 ext4xfs btrfs ifsiso9660 gfs ocfs.Network FSNFS codasmbfs.cephpseudo FSproc sysfspipefs futexfs.usbfsspecialpurpose FStmpfs ramfsPageCachedevtmpfsnetworkstackableBIOs (Block I/O)optionalstruct biodevices on top of “normal”block devicesLVMdrbddevice mapper mdraiddm-cryptdm-mirror.dm-cache dm-thinbcacheBIOs (Block I/O)-sector on disksector cntbio vec cntbio vec indexbio vec listThe Linux Storage Stack Diagramhttp://www.thomas-krenn.com/en/wiki/Linux Storage Stack DiagramCreated by Werner Fischer and Georg SchönbergerLicense: CC-BY-SA 3.0, see ael KuhnDateisysteme11 / 52

DateisystemeQuellenDateisystemeVFS. . . [3]Virtual Hostmmap(anonymous Applications (Processes)vfs writev, vfs readv, .tcm vhostsbp targetISCSIUSBFireWireversion 3.17, 2014-10-17outlines the Linux storage stack as of Kernel version 3.17tcm usb gadgetFibre Channelover Ethernettcm fctcm qla2xxxiscsi target modFibre ChannelThe Linux Storage Stack DiagramLIOVFSdirect I/O(O DIRECT)target core modNetwork FSNFS codablock based FSext2 ext3 ext4xfs btrfs ifsiso9660 gfs ocfs.target core filetarget core iblocksmbfsspecialpurpose FSpseudo FSproc sysfs.pipefs futexfs.cephusbfstarget core pscsiPageCachetmpfs ramfsdevtmpfsnetworkoptionalstackableBIOs (Block I/O)struct bio- sector on disk- sector cnt- bio vec cnt- bio vec index- bio vec listBIOs (Block I/O)devices on top of “normal”block devicesLVMdrbddevice mapper IOsBIOsBlock LayerI/O Schedulerblkmqmaps bios to requestsmulti queuenoop.cfqhooked in device drivers(they hook in like stackeddevices uest-baseddevice mapper targetsdm-multipathHardwareDispatchQueuesBIObased DriversRequestbased DriversRequestbased Drivers/dev/vd*/dev/nullb*/dev/rssd*SCSI Mid Layernull blk/dev/rbd*SCSI upper level drivers/dev/sda /dev/sdb .virtio blksysfs(transport rt Classesnvmescsi transport fcskdnetworkscsi transport sasSCSI low level driversscsi transport .libatamegaraid sasahci ata piix .qla2xxxlpfcaacraidvirtio scsiiscsi tcpmpt3sas.vmw pvscsinetworkHDDSSDvirtio a-virtualizedSCSILSI 12GbsSAS HBAMicronPCIe SIPhysical devicesThe Linux Storage Stack Diagramhttp://www.thomas-krenn.com/en/wiki/Linux Storage Stack DiagramCreated by Werner Fischer and Georg SchönbergerLicense: CC-BY-SA 3.0, see ael KuhnDateisysteme12 / 52

nterscheidung in Benutzer- und SystemsichtBenutzer sehen Dateien und VerzeichnisseDas System kennt zusätzlich InodesRelevant für stat etc.InodesEnhalten MetadatenEigentliche Basisobjekte des DateisystemsJeder Datei und jedem Verzeichnis ist ein Inode zugeordnetÜblicherweise eindeutige IDsMichael KuhnDateisysteme13 / 52

DateienEnthalten Daten in Form eines Byte-ArraysKönnen gelesen/geschrieben werden (explizit)Können in den Speicher gemappt werden (implizit)VerzeichnisseEnthalten Dateien und VerzeichnisseZur Organisation des NamensraumesMichael KuhnDateisysteme14 / 52

DateisystemeQuellenDateisystemeDateien12nb pwrite(fd, data, sizeof(data), 42);nb pread(fd, data, sizeof(data), 42);Listing 2: Expliziter Zugriffpwrite und pread verhalten sich wie write bzw. readExplizite Angabe des Offsets und damit threadsicherZugriff über File DescriptorKann von mehreren Threads parallel genutzt werdenMichael KuhnDateisysteme15 / 52

DateisystemeQuellenDateisystemeDateien. . .1234char* pt mmap(NULL, FILE SIZE, PROT READ PROT WRITE, MAP SHARED, fd, 0);memcpy(pt 42, data, sizeof(data));memcpy(data, pt 42, sizeof(data));munmap(pt, FILE SIZE);Listing 3: Impliziter Zugriffmmap erlaubt es eine Datei in den Speicher einzublendenDatei beginnt an Adresse ptVerschiedene Sichtbarkeitseinstellungen (shared vs. private)Zugriff wie auf andere SpeicherobjekteZ. B. via memcpy oder direkte ZuweisungMichael KuhnDateisysteme16 / 52

DateisystemeQuellenDateisystemeDateien. . .Beide Zugriffsarten haben jeweils Vor- und NachteileBeide Modi profitieren vom Caching durch das BetriebssystemExpliziter ZugriffVorteile: genaue Kontrolle über E/ANachteile: separate Puffer notwendig, Kopiervorgänge zwischen Kernel- und UserspaceImpliziter ZugriffVorteile: keine separaten Puffer notwendig, effiziente E/A durch das Betriebssystem,keine unnötigen KopiervorgängeNachteile: keine genaue Kontrolle, kompliziertere Fehlerbehandlung (Signale)Michael KuhnDateisysteme17 / 52

2.12Name.\0.\0.hello\0world\0Abbildung: ext4-Verzeichniseintrag [1]Traditionell lineares ArrayLangsam, da über das komplette Array iteriert werden mussHeutzutage eher BaumstrukturenDeutlich komplexer, dafür geringere ZugriffszeitenName wird nicht im Inode gespeichertMehrere Namen können auf denselben Inode zeigenMichael KuhnDateisysteme18 / 52

DateisystemeQuellenDateisystemeInodesFeldgröße2 Bytes2 Bytes4 Bytes4 Bytes4 Bytes4 Bytes4 Bytes2 Bytes2 Bytes.60 Bytes.4 Bytes100 öschzeitGruppen-IDLinkzahl.Blockzeiger, Extent-Baum oder Inline-Daten.VersionsnummerFreier SpeicherAbbildung: ext4-Inode (256 Bytes) [1]Michael KuhnDateisysteme19 / 52

DateisystemeQuellenDateisystemeInodes. . .Kompliziert durch RückwärtskompatibilitätOn-Disk-Format kann nur schwer geändert werdenViele Felder sind aus Kompatibilitätsgründen aufgeteiltZeitstempel: 4 Bytes für Sekunden seit 1970, 4 Bytes für NanosekundenauflösungGröße: Obere und untere 4 BytesFelder mehrfach überladenBlockzeiger, Extent-Baum oder Inline-Daten (falls Datei kleiner als 60 Bytes)100 Bytes am Inode-Ende für erweiterte AttributeMichael KuhnDateisysteme20 / 52

DateisystemeQuellenDateisystemeInodes. . .12345678910111213 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 bar641174641174 rm foo ls -l bar-rw-r--r--. 1 u g 0 19. Apr18:48 foo18:48 bar18:48 foo18:48 barListing 4: Inode vs. DateiMichael KuhnDateisysteme21 / 52

Syntaxopen, close, creatread, write, lseekchmod, chown, statlink, unlinkSemantikSpezifiziert auch wie sich E/A-Operationen verhalten sollenwrite: “POSIX requires that a read(2) which can be proved to occur after a write() hasreturned returns the new data. Note that not all filesystems are POSIX conforming.”Michael KuhnDateisysteme22 / 52

DateisystemeQuellenext4ext4Standard-Dateisystem in vielen Linux-DistributionenEingeführt 2006, stabil 2008Vorgänger: ext, ext2, ext3Statische Festlegung diverser Parameter bei nelles DateisystemDaten werden direkt geändert (kein Copy on Write)Keine Prüfsummen für DatenKeine SchnappschüsseMichael KuhnDateisysteme23 / 52

DateisystemeQuellenext4extErstes Dateisystem speziell für LinuxNutzte als erstes Dateisystem die VFS-SchichtInspiriert vom Unix File System (UFS)Beseitigte Beschränkungen des MINIX-DateisystemsDateigrößen bis 2 GBDateinamen bis 255 ZeichenMichael KuhnDateisysteme24 / 52

DateisystemeQuellenext4ext2Separate Zeitstempel für Zugriff und Inode-/DatenänderungDatenstrukturen für zukünftige Erweiterungen ausgelegtTestumgebung für neue VFS-FunktionenAccess Control Lists (ACLs)Erweiterte AttributeMichael KuhnDateisysteme25 / 52

DateisystemeQuellenext4ext3JournalingErklärung folgt späterDateisystemvergrößerung zur LaufzeitNützlich für LVM-UmgebungenH-Baum für größere VerzeichnisseVerkürzt die Suchzeiten im VerzeichnisMichael KuhnDateisysteme26 / 52

DateisystemeQuellenext4ext4Größere Dateisysteme, Dateien und VerzeichnisseExtentsPreallokation, verzögerte Allokation und verbesserte MultiblockallokationJournal-PrüfsummenSchnellere terstützung für TRIMMichael KuhnDateisysteme27 / 52

DateisystemeQuellenext4ext4. . .InhaltPadding (Blockgruppe 0)SuperblockGruppenbeschreibungReservierte ten-BlöckeGröße1.024 Bytes1 Blockn Blöckem Blöcke1 Block1 Blockk Blöckel BlöckeAbbildung: ext4-Blockgruppe [1]Das Speichergerät ist in mehrere Blockgruppen unterteiltFlexible Blockgruppen fassen mehrere Blockgruppen zusammenMichael KuhnDateisysteme28 / 52

DateisystemeQuellenext4ext4. . röße (Extents)Dateigröße (Blöcke)1 KiB26423216 ZiB4 TiB16 GiB2 KiB26423232 ZiB8 TiB256 GiB4 KiB26423264 ZiB16 TiB4 TiB64 KiB2642321 YiB256 TiB256 PiBAbbildung: ext4-Limits im 64-Bit-Modus [1]Standardgröße ist 4 KiB (und offizielles Maximum)Sollte nicht größer als Seitengröße gewählt werdenMichael KuhnDateisysteme29 / 52

DateisystemeQuellenext4AllokationBlockbasiertViele Blöcke gleicher Größe (üblicherweise 4 KiB)Zeiger auf Blöcke im InodeDirekt, indirekt, doppelt indirekt, dreifach indirektHoher Overhead bei großen DateienBeispiel: 1 TiB große Datei benötigt 268.435.456 ZeigerBeschränkt maximale DateigrößeMichael KuhnDateisysteme30 / 52

DateisystemeQuellenext4Allokation. [2]Michael KuhnDateisysteme31 / 52

ige möglichst große ExtentsVier Extents können im Inode gespeichert werdenMehr in einer Baumstruktur und zusätzlichen BlöckenZeiger auf Startblock und LängeMaximale Länge: 32.768 BlöckeEntspricht 128 MiB bei einer Blockgröße von 4 KiBErmöglicht größere DateienMichael KuhnDateisysteme32 / 52

ersuche zusammenhängende Blöcke zu allokierenVersuche Blöcke in derselben Blockgruppe zu allokierenMultiblockallokationSpekulativ 8 KiB bei Dateierzeugung allokierenVerzögerte AllokationBlöcke werden erst allokiert, wenn auf das Speichergerät geschrieben werden mussMichael KuhnDateisysteme33 / 52