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?
FĂŒr den Plattenvergleich gerne genutzt: I/O Rate:
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