Einheit 11: Harddisks & Dateisysteme

Lernziele und Kompetenzen

Den Aufbau von Hard Disk Drives und RAID-Systemen kennen lernen und die Prinzipien bei der Ansteuerung durch das Betriebssystem verstehen.

Datenpersistenz

  • Hard Disk Drives (dt. Festplatten sind die seit Jahrzehnten am weit verbreitetsten Art Daten zu speichern.

  • Dateisysteme hĂ€ngen dabei stark von den darunterliegenden GerĂ€ten ab

    • Wie speichern moderne Hard Disks ĂŒberhaupt Daten ab?

    • Wie sieht das Interface hierfĂŒr aus?

    • Wie sind die Daten konkret angeordnet und wie wird darauf zugegriffen?

    • Wie lĂ€sst sich mit „Disk Scheduling“ die Leistung verbessern?

    • Welche Konsequenz hat der Wandel von klassischen Festplatten hin zu Solid State Disks (Abk. SSD)?

Das Interface

Der Aufbau ist im Grundprinzip immer Àhnlich

  • Das Laufwerk besteht aus einer Anzahl von sog. Sektoren (i.d.R. in Form von 512-Byte Blöcken)

  • Jeder Block kann individuell gelesen und geschrieben werden

  • Alle Sektoren sind nummeriert 0 bis 𝑛−1 (bei 𝑛 Sektoren)

  • Multi-Sektor-Operationen sing möglich (und gĂ€ngig)

  • Viele Dateisysteme lesen 4KB oder mehr auf einmal

  • Atomare Schreiboperationen sind nur auf 512-Byte Blöcke zugesichert

Torn Write

Was bedeutet atomare Schreiboperationen sind nur auf 512-Byte Blöcken zugesichert?

Nur die ersten drei Blöcke wurden geschrieben, obwohl der Stromausfall erst sehr spÀt bei der Schreiboperation von Block 4 aufgetreten ist.

Inoffizielle Annahmen ĂŒber Disks

  • Annahmen, die von vielen Clients getroffen werden (unwritten contract):

    • Auf zwei nahe beieinander liegende Blöcke kann schneller zugegriffen werden, als auf weit entfernt liegende

    • Der Zugriff auf fortlaufende Böcke (engl. sequential read/write) ist der schnellste Zugriff ĂŒberhaupt und gewöhnlich schneller als der wahlfreie Zugriff (engl. random access)

    Angenommen, Sie schreiben einen Treiber fĂŒr (konventionelle) Festplatten unter diesen Annahmen und morgen tauscht jemand die Festplatten gegen Solid State Disks aus, was passiert dann?

Festplattengemoetrie

Grundlegende Geometrie

  • Eine oder mehrere Scheiben (engl. platter), jede mit je zwei Seiten

  • Magnetische OberflĂ€che aus Eisenoxid - oder Kobalt-Deckschicht (engl. surface)

  • Achse bzw. Spindle (engl. spindle)

  • Schreib-/Lesekopf (engl. disk-head)

  • Arm mittels dem der Schreib-/Lesekopf positioniert wird (engl. disk arm)

  • Daten sind in konzentrischen Kreisen (engl.tracks) angeordnet

  • Umdrehung wird in RPM (rotations per minute) gemessen.

  • Typische Werte heutzutage von 7.200 bis 15.000 RPM

  • Interessant wird die Umdrehungszeit, bei 10.000 RPM sind dies ca. 6ms

Vereinfachte Festplatte

  • Einige (vereinfachende) Annahmen

    • Ein Track

    • Track besteht aus 12 Sektoren bzw. Blöcken (Sektoren)

    • Jeder Block besteht aus 512 Byte

    • Die Scheibe dreht sich gegen der Uhrzeiger Sinn

Rotationa Delay

  • Rotational Delay oder auch Rotational Latency – Zeit bis sich der gesuchte Sektor unter dem Schreib-Lese-Kopf befindet

  • Eine vollstĂ€ndige Umdrehung dauert 𝑅

  • Suchen wir Sektor 0 und starten bei Sektor 6, ist das Delay 𝑅/2

  • Der Worst-Case wĂ€re im Beispiel zuvor ein Start bei 5, hier wird fast eine ganze Rotation benötigt und das Delay betrĂ€gt somit fast 𝑅

Seek Time

  • In Wirklichkeit besitzen HDDs sehr viele Tracks und der Schreib-/Lesekopf muss permanent ausgerichtet werden

    • Hier: Kopf ĂŒber dem innersten Track muss zum Ă€ußersten bewegt werden (engl. seek):

    • Rotation und Seek sind mit die teuersten Operationen einer Festplatte

    • Seeking besteht aus vier Phasen:

      • Beschleunigung (engl. acceleration)

      • Schub bei voller Geschwindigkeit (engl. coasting)

      • Abbremsung (engl. deceleration)

      • Einschwingzeit (engl. settling time) mit 0,5 bis 2ms

Transfer und andere unwichtige Dinge

Erst wenn der Kopf korrekt positioniert ist (stellen Sie sich vor, er wĂ€re nur ungefĂ€hr auf dem richtigen TrackđŸ€Šâ€â™‚ïž) findet der Transfer (engl.transfer) statt.

Um dass sequentielle Lesen zu ermöglichen, nutzen manche Disks ein sog. Spurversatz (engl. trackskew) an, damit keine Latenz nach dem Neupositionieren entsteht, wenn die Daten auf einem anderen Sektor weitergefĂŒhrt werden.

Außen befinden sich mehr Sektoren (Physik rulez!), daher werden Platten oft in Zonen (engl. multi-zoned disks). Äußere Zonen besitzen dann mehr Sektoren als innere.

Schreib-/Lesecache zur Performance-Steigerung. Beim Schreiben kann sofort nach dem Cachen bestÀtigt werden (engl. writeback) oder erst nach dem Schreiben auf Platte (engl. writethrough).

I/O Zeiten

Wie setzt sich nun die Zeit fĂŒr einen I/O-Zugriff zusammen?

TI/O=Tseek+Trotation+TtransferT_{I/O}=T_{seek} +T_{rotation}+T_{transfer}

FĂŒr den Plattenvergleich gerne genutzt: I/O Rate:

RI/O=SizetransferTI/OR_{I/O} = {\frac{Size_{transfer}}{T_{I/O}}}

Disk Scheduling

  • Aufgrund der hohen Kosten fĂŒr Disk Zugriffe entscheidet der Disk Scheduler ĂŒber die Zugriffe:

    • Anders als bei Prozessen kann man bei Plattenzugriffen die Dauer gut berechnen

    • Auf Basis von Seek-Zeiten und der Rotation Delay kann der kĂŒrzeste Job gefunden werden

Shortest Seek Time First (SSTF)

  • Anordnung der Jobs nach Track – die Anfrage mit dem am nĂ€chst gelegenen Track wird zuerst gewĂ€hlt

  • Problem: Die Disk Geometrie ist dem Betriebssystem nicht bekannt

  • Anstelle dessen kann der nĂ€chst gelegen Block verwendet werden (nearest-block-first, Abk. NBF)

  • Problem 2: Starvation– Bei einem fortlaufenden Strom von Anfragen auf z.B. die inneren Tracks wĂŒrden Anfragen auf die Ă€ußeren ignoriert

  • Wie kann dieses Problem gelöst werden?

SCAN

  • Anfragen werden von den Ă€ußeren zu den inneren Tracks und wieder zurĂŒck etc. abgearbeitet (engl. sweep)

C-SCAN (Circular SCAN)

  • Anstelle in beiden Richtungen werden Anfragen immer von den Ă€ußeren Tracks abgearbeitet

  • Fairer gegenĂŒber den Ă€ußeren und inneren Tracks, da reines SCAN zweimal die mittleren Tracks trifft

  • Allerdings werden SCAN/C-SCAN nicht annĂ€hernd einem SJF-Ansatz gerecht

Shortest Positioning Time First (SPTF)

  • Ausgangspunkt s. vorherige Abbildung

  • Sollte nun Track 8 oder 16 zuerst gewĂ€hlt werden?

  • AbhĂ€ngig von Seek-Zeit und Rotation-Delay

  • Löst eigentlich unsere vorherigen Probleme

  • Problem: Das Betriebssystem kennt meist nicht die Track-Grenzen nicht und weiß nicht wo sich der Schreib-Lese-Kopf gerade befindet

  • Daher wird SPFT meist innerhalb des Drives selbst implementiert

manchmal auch: Shortest Access Time First (SATF)

Weiter Herausforderungen

  • FrĂŒher wurde das gesamte Scheduling im Betriebssystem realisiert – frĂŒher waren die Disks „einfacher“ gebaut.

  • Heute besitzen Festplatten einen komplexen Scheduler auf dem Disk Controller, der exakte Daten ĂŒber die internen Positionen hat.

  • Das Betriebssystem schickt die Requests an die Disk, die es am geeignetsten hĂ€lt und die Disk kĂŒmmert sich um den Rest.

  • I/O Merging: Requests, die nahe aneinander liegende Sektoren betreffen, sollten möglichst zusammengefasst werden, da dies den Overhead fĂŒr das Betriebssystem reduziert.

  • Wie lange soll der Scheduler warten, bis eine I/O-Anfrage abgearbeitet wird? Es könnte ja noch eine „bessere“ Anfrage kommen, so dass die Disk effizienter genutzt werden kann.

RAID-Systeme

Festplatten gehören zu den langsamsten Komponenten in einem Rechner. Wenn eine Festplatte ausfĂ€llt, sind die persistierten Daten verloren. Außer Sie haben ein Backup, aber das ist hier nicht der Punkt, wicht hier ist jedoch: RAID ist kein Backup!

ZunĂ€chst die Frage: Wie kann ein großes, schnelles und zuverlĂ€ssiges Speichersystem geschaffen werden?

  • Von außen betrachtet sieht ein RAID wie eine Festplatte aus.

  • Intern ist ein RAID jedoch ein höchst komplexes System mit zahlreichen Vorteilen:

    • Performance, Speicherplatz (KapazitĂ€t) und ZuverlĂ€ssigkeit

    • RAID-Systeme verkraften außerdem den Ausfall einzelner Festplatten

Interface

FĂŒr das Dateisystem sieht ein RAI- System aus wie eine einzelne Festplatte (warum es das nicht ist klĂ€ren wir spĂ€ter).

  • Bei einem Request durch das Betriebssystem, muss das RAID ermitteln auf welche Disk (bzw. abhĂ€ngig vom RAID Level, auf welche Disks) zugegriffen werden muss.

  • Da die Daten auf mehrere Disks verteilt sind, mĂŒssen mehrere physikalische I/O-Zugriffe pro logischen I/O-Zugriff stattfinden

RAID Charakteristika

Auf Basis welcher Kriterien können RAID-Systeme evaluiert werden?

KapazitÀt

  • Wie viel effektiver Speicherplatz ist verfĂŒgbar, wenn 𝑁 Disks mit đ” Blöcken verwendet werden? Ohne Redundanz sind dies đ‘â‹…đ”

  • Wenn zwei Kopien vorgehalten werden (engl. mirroring) wĂ€ren dies (đ‘â‹…đ”)∕2

  • Verschiedene RAID-Level liegen irgendwo dazwischen

ZuverlÀssigkeit

  • Zur Vereinfachung gehen wir derzeit von einem einzigen Fehlermodell aus: Eine Disk fĂ€llt komplett aus, einem sog. Fail-Stop.

  • Des weiteren gehen wir davon aus, dass der RAID-Controller dies auch direkt feststellen kann.

    • Wie viele Disks können ausfallen, so dass das jeweilige RAID-Design immer noch funktionsfĂ€hig ist?

Es gibt natĂŒrlich noch mehr FehlerfĂ€lle, die wir spĂ€ter betrachten!

Performance

  • Die Performance ist nicht ganz einfach zu bestimmen:

    • HĂ€ngt vom jeweiligen Workload ab

    • Wie hoch ist die Schreibe- oder Lesegeschwindigkeit?

    • Wie wir vorher gelernt haben, hĂ€ngt dies auch von den eingesetzten Disks ab

RAID Level

RAID Level 0

  • Keine Redundanz

  • Mehrere Disks werden genutzt, um die KapazitĂ€t zu erhöhen (engl.striping)

  • Einfachste Form: Blöcke werden ĂŒber die Disks verteilt

  • Werden Blöcke nun sequentiell gelesen, kann dies parallelisiert werden!

Stripes

Blöcke in der gleichen Reihe werden Stripes genannt.

Chunk Size

  • Besser: Mehrere Blöcke auf einer Disk

  • Hier: Zwei 4-KB Blöcke bevor zur nĂ€chsten Disk gesprungen wird

  • Performance Auswirkung:

    • Kleine Chunk Sizes: Dateien werden ĂŒber viele Disks verteilt

    • Große Chunk Sizes: Intra-File ParallelitĂ€t wird reduziert

    • Richtige GrĂ¶ĂŸe: schwer zu bestimmen bzw. „it depends“

RAID-0 Analyse

KapazitÀt

  • Bei 𝑁 Disk mit je đ” Blöcken liefert RAID-0 ein perfektes Ergebnis: đ‘â‹…đ”

ZuverlÀssigkeit

  • Perfekt, was die Ausfallwahrscheinlichkeit angeht: Bei einem Fehler sind die Daten futsch!

Performance

  • Bei einem Zugriff auf einen einzelnen Block: Vergleichbar mit einzelner Disk

  • Bei sequentiellen Zugriffen: Volle ParallelitĂ€t

  • Bei wahlfreien Zugriffen 𝑁⋅𝑅 MB/s mit

𝑅=(đŽđ‘šđ‘œđ‘ąđ‘›đ‘Ąđ‘œđ‘“đ·đ‘Žđ‘Ąđ‘Ž)/(𝑇𝑖𝑚𝑒𝑡𝑜𝐮𝑐𝑐𝑒𝑠𝑠)𝑅=(đŽđ‘šđ‘œđ‘ąđ‘›đ‘Ąđ‘œđ‘“đ·đ‘Žđ‘Ąđ‘Ž)/(𝑇𝑖𝑚𝑒𝑡𝑜𝐮𝑐𝑐𝑒𝑠𝑠)

FĂŒr eine detaillierte Berechnung sei hier auf OSTEP Kapitel 38.4 verwiesen

RAID Level 1

Mirroring

  • Jeder Block wird im System auf eine andere Disk kopiert (bzw. gespiegelt)

  • Hier: RAID-10 bzw. RAID 1+0, nutzt gespiegelte Paare von Disk

  • Alternativ: RAID-01 bzw. RAID 0+1, besteht aus zwei RAID-0 Arrays, die gespiegelt sind

KapazitÀt

  • Es wird nur die HĂ€lfte der KapazitĂ€t genutzt: (đ‘â‹…đ”)∕2 und somit teuer

ZuverlÀssigkeit

  • Ausfall einer Diks wird verkraftet, im vorherigen Fall können sogar Konstellationen von Disks ausfallen (z.B. Disk 0 und 2), darauf sollte man aber nicht wetten

Performance

  • Einzelne Leseoperation vergleichbar mit einer einzelnen Disk

  • FĂŒr einen Schreibzugriff mĂŒssen jedoch zwei (parallele) physikalische Schreiboperationen durchgefĂŒhrt werden, im Worst-Case muss auf den langsamsten Schreibprozess gewartet werden (z.B. aufgrund von Rotation Delay)

  • Sequentielle Schreib- und Leseoperationen dauern (𝑁/2⋅𝑆) MB/s mit 𝑆=(đŽđ‘šđ‘œđ‘ąđ‘›đ‘Ąđ‘œđ‘“đ·đ‘Žđ‘Ąđ‘Ž)/(𝑇𝑖𝑚𝑒𝑡𝑜𝐮𝑐𝑐𝑒𝑠𝑠) bzw. die HĂ€lfte des Höchstdurchsatzes

  • Wahlfreie Leseoperationen sind mit 𝑁⋅𝑅 MB/s die beste Operation fĂŒr RAID-1, wogegen wahlfreie Schreiboperationen mit 𝑁/2⋅𝑅 MB/s weniger geeignet sind, da zwei physikalische Schreiboperationen simultan durchgefĂŒhrt werden mĂŒssen.

FĂŒr eine detaillierte Berechnung sei auch hier auf OSTEP Kapitel 38.4 verwiesen

RAID Level 4

  • Nutzung eines sog ParitĂ€tsbits

  • Benötigt weniger Speicherplatz als gespiegelte RAIDs, jedoch auf Kosten der Performance

  • Mittels der XOR-Funktion wird das ParitĂ€tsbit berechnet

Parity-Bit

  • Invariante

  • Pro Zeile gerade Anzahl von 1en, einschl. des ParitĂ€tsbits

  • RAID muss dies sicherstellen

  • Beim Ausfall einer Zeile C (s.o.) kann diese wiederhergestellt werden

    • Wie? XOR auf die verbleibenden Spalten ausfĂŒhren

  • Aber bei Blöcken?

  • Bitweises XOR auf den ganzen Block (z.B. 4 KB)

KapazitÀt

  • 1 Disk fĂŒr ParitĂ€ten ergibt eine GesamtkapazitĂ€t (𝑁−1)â‹…đ”

ZuverlÀssigkeit

  • RAID-1 erlaubt den Ausfall einer Disk

Performance

  • Sequentielle Leseoperationen können alle Disks (ohne die ParitĂ€tsdisk) nutzen und liefern so einen Maximaldurchsatz von (𝑁−1)⋅𝑆 MB/s

  • Bei einem sog. Full Stripe Write wird ein gesamter Stripe auf einmal beschrieben und der ParitĂ€tsblock kann direkt mit berechnet werden, alle Schreiboperationen können parallel stattfinden (effizienteste Schreiboperation im RAID-4)

  • Die effektive Bandbreite bei sequentiellen Schreiboperationen ist dabei (𝑁−1)⋅𝑆 MB/s

  • Wahlfreie Leseoperationen liegen bei (𝑁−1)⋅𝑅 MB/s

  • Beim Schreiben eines einzelnen Blocks muss das ParitĂ€tsbit des Stripes neu berechnet werden

Variante 1: Additive Parity

  • Alle bestehenden Blöcke (parallel) lesen und mit dem neune Block XOR

  • Neu berechneter ParitĂ€tsblock und neuer Block können parallel geschrieben werden

Variante 2: Subtractive Parity

  • Alter Wert wird gelesen, ist dieser mit dem neuen Wert identisch muss das ParitĂ€tsbit nicht geĂ€ndert werden, falls doch, muss das ParitĂ€tsbit umgedreht werden

  • Bei ganzen Blöcken (z.B. 4 KB) wie in RAID-4 sind dies 4096 mal 8 Bit.

  • Der Einsatz des jeweiligen Verfahrens hĂ€ngt also wieder davon ab („it depends“)

Auf jeden Fall wird die ParitÀtsdisk zum Flaschenhals

RAID Level 5

  • Grundlegend gleich zu RAID-4, jedoch mit den ParitĂ€tsblöcken ĂŒber die versch. Disks verteilt (engl. rotating parity)

  • Flaschenhals wird somit beseitigt

RAID-5 Analyse

  • Die meisten Werte sind identisch zu RAID-4

  • Wahlfreie Leseoperationen sind etwas besser, da alle Disks genutzt werden können

  • Wahlfreie Schreiboperationen verbessern sich signifikant, da Requests nun parallel ausgefĂŒhrt werden können.

Übungsaufgaen

Einfache XOR Berechnung

Gegeben sind zwei BinÀrzahlen: 1010 und 1100. Berechnen Sie das Ergebnis der XOR-Operation zwischen diesen beiden Zahlen.

1 XOR 1 = 0 0 XOR 1 = 1 1 XOR 0 = 1 0 XOR 0 = 0

Die gesuchte BinĂ€rzahl ist demnach 0110. In diesem Fall handelt es sich um gerade ParitĂ€t (auch als “even parity” bezeichnet). Die XOR-Operation zwischen den beiden BinĂ€rzahlen 1010 und 1100 ergibt die BinĂ€rzahl 0110, die eine gerade Anzahl von Einsen enthĂ€lt. Daher ist dies ein Beispiel fĂŒr gerade ParitĂ€t.

XOR Berechnung mit mehreren Datenblöcken

  • Disk 1 =1111

  • Disk 2 =1110

  • Disk 3 =1100

  • Disk 4 =1000

Die Berechnung des ersten Bits jedes Datenblocks ergibt folgende Berechnung

1 XOR 1 XOR 1 XOR 1

= ((1 XOR 1) XOR 1) XOR 1

= (0 XOR 1) XOR 1

= 1 XOR 1n

= 0

Die Berechnung des zweiten Bits jedes Datenblocks ergibt folgende Berechnung

1 XOR 1 XOR 1 XOR 0

= ((1 XOR 1) XOR 1) XOR 0

= (0 XOR 1) XOR 0

= 1 XOR 0

= 1

Die Berechnung des dritten Bits jedes Datenblocks ergibt folgende Berechnung

1 XOR 1 XOR 0 XOR 0

= ((1 XOR 1) XOR 0) XOR 0

= (0 XOR 0) XOR 0

= 0 XOR 0

= 0

Die Berechnung des letzten Bits jedes Datenblocks ergibt folgende Berechnung

1 XOR 0 XOR 0 XOR 0

= ((1 XOR 0) XOR 0) XOR 0

= (1 XOR 0) XOR 0

= 1 XOR 0

= 1

Die Berechnung ergibt demnach folgenden ParitÀtsblock:

Disk 5 = 0101

Last updated