[zurück] [vorwärts]
2. Disk Arrays

2.1 Datenpartitionierung

Files, die in einem Disk Array gespeichert werden, müssen - um die Parallelität des Input und Outputs zu ermöglichen - zunächst in einzelne Teile aufgespalten werden, bevor sie auf die Platten des Arrays verteilt werden kann. Diese Partitionierung kann auf zwei verschiedene Arten erfolgen [1]:

Im ersten Punkt jedoch betrachtet man das abzuspeichernde oder zu lesende File losgelöst von seinem Inhalt als eine einfache Bytefolge. Diese wird dann im einfachsten Fall in gleichgroße Bereiche aufgeteilt (regelmäßige Partitionierung [1]) und auf alle Platten des Disk Arrays verteilt. Die Auswahl der Platte könnte sich z.B. als der ganzzahlige der Division von der Nummer des aktuellen Bytebereiches und der Anzahl der Platte im Disk Array ergeben [1]. Dieses Verfahren wird oftmals auch als Striping bezeichnet, da sich auf den Platten ein Streifenmuster bestehend aus den einzelnen Bytebereichen ergibt.
Entscheidend für die Performance eines Disk-Arrays ist hierbei die richtige Wahl der Größe der Bytebereiche, in die das File aufgeteilt wird. Diese Größe wird auch als Striping Granulat oder Striping-Unit [1] bezeichnet und hängt in seiner "Körnigkeit" auch von den Anforderungen der im System laufenden Anwendungen ab [4]. Hier kann man unterscheiden zwischen Byte-Striping, bei welchem als Granulatgröße 1 Byte gewählt wird (also landen zwei benachbarte Bytes auf zwei verschiedenen Platte) und Block-Striping, bei welchem als Granulat mehrere Bytes gewählt werden. Im Beispiel (Abb. [1]) sind Byte-Striping und Block-Striping (Blockgröße 4 Kb) gegenübergestellt. Die einzelnen Bereiche einer Datei sollten dabei nach Möglichkeit physisch zusammenhängend auf einer Platte plaziert werden. Eine wichtige Rolle bei der Wahl der Platte spielt dabei auch der Aspekt der Lastbalancierung.
Da die Performance eines Disk Arrays von der Größe des Striping Granulats stark abhängt, stellen Methoden zur adäquaten Wahl des Granulats einen umfangreichen Aspekt in der wissenschaftlichen Literatur dar. Gerade wenn die I/O-Leistung eines Systems durch Zugriffsparallelität verbessert werden soll, müßten die R Bytes einer Datei über eine Anzahl P von Platten verteilt werden, also bräuchte man ein maximales Striping-Granulat von R/P [1]. Je mehr Zugriffsparallelität man aber erreichen will, sprich man will das File über mehr Platten verteilen, arbeitet also mit einem wachsenden P, desto kleiner wird zwar auch des Granulat, dafür steigt aber der Aufwand eine I/O-Auftrages beträchtlich, da mehr Platten involviert sind und mehr Filepartitionen gesucht werden müssen. Hier ist also ein Weg gefragt, der gute Zugriffsparallelität bei akzeptablem Aufwand gewährleistet.
Zum einen ist zu beachten, daß ein kleines Granulat neben der Verbesserung der Zugriffsparallelität auch eine Erhöhung der Bewegungen der Schreib-Lese-Köpfe der Platten zur Folge hat. Hinzu kommt die Rotationsverzögerung der Platten. Ruft man sich wieder ins Gedächtnis, daß wir es bei einem Disk Array mit einer im Grunde genommen beliebigen Sammlung von Platten zu tun haben, die parallel gelesen werden sollen, wird klar, daß die Zeiten für die Schreib-Lese-Kopf-Bewegungen und die Rotationsverzögerung immer von der langsamsten Platte abhängen (Formeln dazu in [1]). Also darf das Striping-Granulat nicht so klein gewählt werden, daß der Performancezuwachs durch die Zugriffsparallelität bereits in den Zeiten für den Plattenzugriff wieder versandet. Bei heutigen Platten ist dies der Fall, wenn bei einem Plattenzugriff 30 bis 50 KByte auf einmal gelesen oder geschrieben werden [1]).
Eine weitere Beschränkung nach Unten findet das Striping-Granulat, wenn das System auch eine gute Performance bei der in der Einleitung erwähnten Auftragsparallelität gewährleisten soll. Ein zu kleines Granulat würde viele Platten beschäftigen und somit andere Aufträge blockieren; für eine optimale Datentransferrate muß auch hier wieder der Mittelweg gefunden werden. Wie die Abbildung [1

zeigt, wächst die Plattenbelegungszeit eines I/O-Auftrages, also die Summe der Zeiten, die jede einzelne beteiligte Platte benötigt, um den Auftrag zu erledigen (Zeit zur Positionierung des Schreib-Lese-Kopfes und die Zeit zum Datentransfer), dadurch an, daß sogenannte unproduktive Zeiten, also die bereits oben erwähnte Rotationsverzögerung und die Positionierungszeiten, bei jeder beteiligten Platte auftreten und sich somit summieren. Diese Zeiten könnten aber für die Abarbeitung andere I/O-Aufträge genutzt werden.
Neben diesen technischen Aspekten der Wahl des Striping-Granulats muß auch - wie oben erwähnt - die Anforderungen der auf dem System laufenden Anwendungen beachtet werden. Zum einen sind dies die durchschnittliche Größe eines I/O-Auftrages seitens der Anwendung. Zum anderen muß beachtet werden, welche Anforderungen an den Datendurchsatz und die Antwortzeit gestellt werden. Diese Anforderungen müssen zusammen mit den hardwaretechnischen Voraussetzungen des Disk Arrays (Positionierungszeiten, Transferraten, Rotationszeiten) bei der Wahl des Striping-Granulats berücksichtigt werden. Einige Beispiele [1]:

2.2 Datenallokation
 
Ein mit der Partitionierung eng verbundenes Problem, aber doch von ihr unabhängig, ist die Allokation - sprich die Verteilung - der Datenpartitionen auf den vorhandenen Festplatten. Ist das Striping-Granulat so groß, daß jedes File über alle Festplatten verteilt wird, ist dessen Lösung trivial. Ist dies jedoch nicht der Fall, muß man in Hinblick auf eine ausgeglichene Lastverteilung von allen Platten im Disk Array eine Verteilungsfunktion finden, die eben verhindert, daß sich bei I/O-Operationen vor manchen Platten Auftragsschlangen bilden und andere de facto im Leerlauf sind.
Um eine solche Funktion zu entwickeln, muß zunächst ein Maß für die Auslastung einer Platte eingeführt werden. Dieses muß sowohl die Zugriffshäufigkeiten als auch die durchschnittliche Größe von I/O-Aufträgen repräsentieren, kann also nur statistisch gewonnen werden. Ein solche Maß ist die Hitze einer Dateipartition [1,5]. Sie bildet sich aus der Summe der Zugriffshäufigkeiten aller Blöcke einer Dateipartition, welche man über einen hinreichend großen Zeitraum mit stabilen Lastverhalten mißt (also 1 Tag oder 1 Woche). Diese Definition beinhaltet sowohl die Zugriffshäufigkeiten als auch die Größe der I/O-Aufträge, denn große Aufträge, die auf mehrere Blöcke zugreifen, werden auch mehrfach gezählt. Addiert man nun jede Hitze einer Dateipartition, die sich auf einer Platte befinden, so erhält man ein brauchbares Maß für die Auslastung der betrachteten Platte.
Eine einfache Möglichkeit zur Datenallokation ist die Round-Robin-Allokation [1,5]. Dabei werden die vorhandenen Platten in festgelegter Reihenfolge zyklisch zur Allokation einer Dateipartition herangezogen; ein eigentlicher "Hitzeausgleich" erfolgt nicht. Vielmehr wird davon ausgegangen, daß bei einer genügend kleinen Partitionierung und einer zahlenmäßigen Gleichverteilung der Partitionen auf jeder Platte im Disk Array die Hitzeunterschiede einzelner Dateipartitionen gesamt gesehen nicht mehr sonderlich ins Gewicht fallen. Gibt es jedoch wenige Partitionen, die sehr heiß sind, und viele sehr kalte Partitionen, so kommt es zu einem Ungleichgewicht in der Lastbalancierung der Platten im Disk Array. Darum müssen andere Methoden zur Lastbalancierung herhalten.

2.3 Methoden zur Lastbalancierung
 
Ein einfaches Verfahren ist das sog. Greedy-Verfahren [1]. Es setzt voraus, daß jede Datei in nicht mehr Partitionen geteilt wurde, als Platten im Disk Array vorhanden sind. Zu Beginn des Algorithmus besitzen alle Platten die Gesamthitze Null. Stichpunktartig sieht der Algorithmus wie folgt aus:

  1. Sortierung. Alle Dateipartitionen werden nach ihrem Hitzewert sortiert, und zwar so, daß die heißeste Partition zu erst in der Liste steht.
  2. Abarbeitung der sortierten Liste. Zunächst wird die Platte mit der geringsten Gesamthitze gesucht und die aktuelle Partition dort alloziert, sofern genügend Platz vorhanden ist und auf dieser Platte noch keine andere Partition derselben Datei vorhanden ist. Sind diese Bedingungen nicht erfüllt, kann man auch die letzte gegebenenfalls weglassen. Nach der Allokation auf einer Platte wird die Hitze der Partition zur Gesamthitze der Platte hinzuaddiert (vgl. Definition der Hitze einer Platte).
Nachteil des Verfahrens ist sein doch recht statisch Charakter, der einem laufenden System i.d.R. nicht gerecht werden kann. Zum einen können in einem System Datei gelöscht und neue erstellt werden, über deren Hitze man nur Schätzungen abgeben kann; dafür ist das Greedy-Verfahren insofern noch nutzbar, als daß neue Dateien auf den Platten mit der geringsten Hitze alloziert werden. Zum anderen können aber auch vorhandene Dateien anwachsen oder schrumpfen, so daß neue Dateipartitionen verteilt werden müssen. In bezug auf die Hitze dieser Partitionen kann man auch nur davon ausgehen, daß diese ungefähr gleich ist mit der Hitze der bisher existierenden Partitionen der Datei, sofern sich die durchschnittliche I/O-Auftragsgröße nicht geändert hat. Auch dann ist das Greedy-Verfahren durchaus noch brauchbar, wenn man die Bedingung beachtet, daß auf keiner Platte zwei Partitionen einer Datei liegen sollen; auch so gelangt man zu einer einfachen Lastbalancierung. Allerdings kann sich auch die Hitze einer Datei bzw. derer Partitionen dynamisch ändern. Dann müssen Partitionen evtl. von einer sehr heißen Platte auf eine kühlerer umgelagert werden. Man spricht hier auch von Disk-Cooling [4,5].
Der Disk-Cooling-Algorithmus läuft sozusagen als Hintergrundprozeß im System und überprüft in bestimmten Abständen, ob es überhaupt nötig ist, ein kostenintensives Disk-Cooling vorzunehmen. Dazu sucht er die Platte mit der größten Hitze und vergleicht diesen Hitzewert mit dem vorgegebenen "Grenzwert", ab welchem ein Disk-Cooling die verursachten Kosten rechtfertigt. Der eigentliche Algorithmus läuft dann in drei Schritten ab [4]:
  1. Schritt: Alle Extensionen eines Files auf einer Platte werden durchlaufen. Eine Extension eines Files ist die Zusammenfassung aller seiner Partitionen, die sich auf derselben Platte befinden. Der Durchlauf erfolgt in der Reihenfolge der absteigenden Temperatur der Extensionen. Die Temperatur einer Extension ist das Verhältnis seiner Temperatur zu seiner Größe und somit auch ein guter Indikator für das Kosten-Leistungs-Verhältnis bei der evtl. Reallokation im Zuge des Disk-Cooling (je heißer eine Extension, desto eher lohnt sich eine Verlagerung auf eine kühlere Platte).
  2. Schritt: Für die aktuelle Extension werden nun alle Platten (in aufsteigender Ordnung nach deren Hitzewerten) durchlaufen. Es wird überprüft, ob die aktuelle Platte schon eine Extension des Files enthält, von dem auch die aktuell zu überprüfende Extension stammt, und ob noch genügend Platz auf dieser Platte vorhanden ist, um die aktuelle Extension aufzunehmen. Ist beides erfüllt, wird diese Platte als Ziel für die Reallokation festgehalten.
  3. Schritt: Es wird überprüft, ob sich vor der zu kühlenden Platte eine Warteschlange von I/O-Aufträgen befindet. Ist dies der Fall, wird auf das Disk-Cooling verzichtet, denn die Lese- und Schreiboperationen der Reallokation der Extension würde im Endeffekt durch die Blockierung dieser I/O-Aufträge den Performancegewinn schwächen oder gar zunichte machen. Ist keine Warteschlange vorhanden, wird die Hitze der zu kühlenden Platte - gesenkt um die Hitze der zu reallokierenden Extension - und die Hitze der Zielplatte - entsprechend erhöht - vorausberechnet. Zeigt ein Vergleich dieser Werte, daß die Hitze der Zielplatte nun nicht über der Hitze der zu kühlenden Platte liegt, wird die eigentliche Reallokation durchgeführt und die neuen Hitzewerte der Platten eingetragen.
Somit wird der Algorithmus zwar öfter gestartet, führt aber nur in wenigen Fällen wirklich zur Reallokation von Extensionen, und zwar nur dann, wenn das Kosten-Leistungsverhältnis akzeptable ist und das gesamte System nicht durch das Disk-Cooling einer - in diesem Falle fast widersinnigen - Mehrbelastung ausgesetzt ist.

2.4 Fehlerkorrrekturmechanismen
 
Die Benutzung von Disk Array birgt ein weiteres Problem in sich; dadurch, daß viele Platten vorhanden sind, kommt es natürlich auch zu mehr Plattenfehlern, die, wenn sie z.B. eine Partition einer Datei zerstören und somit die gesamte Datei unbrauchbar machen, zu schweren (und relativ häufigen) Datenverlusten führen kann. Eine teure Lösung des Problems wäre, die Fehlersicherheit der Platten zu erhöhen, man kann Fehler aber auch nie völlig ausschließen, darum ist es besser, Methoden zu entwickeln, mit denen man zerstörte Daten wiedergewinnen kann. Ist die Zeit für die Wiedergewinnung relativ kurz, kann man immer noch von einer hohen Verfügbarkeit [2] der Daten ausgehen. Maße für die Verfügbarkeit sind u.a.:

Diese Werte gelten zunächst für die einzelnen Platten eines Disk-Arrays. Betrachtet man das gesamte Array, so interessiert vor allem der Erwartungswert für die Zeit, bis zu der ein finaler Datenverlust auftritt. Diese Mean Time To Data Loss ist der Quotient aus der MTTF und der Anzahl der Platten im Disk-Array (bei einem Disk-Array ohne die im Folgenden beschriebenen Fehlertoleranzen). Ein Beispiel [2]: Bei einem Disk Array mit 100 Platten und einer MTTF von 50.000 Stunden pro Platte (~ 4 Jahre) beträgt die MTTDL gut 2 Wochen. Ein so häufiger Datenverlust ist natürlich inakzeptabel, den nach Möglichkeit möchte man Datenverlust vollkommen vermeiden. Akzeptable Werte dafür beginnen nach Schätzungen aus der Praxis bei einer MTTDL von mindestens 10 Jahren oder mehr.
Natürlich kann die Fehlerkorrektur vollständig der jeweiligen Anwendung - also der Software - überlassen werden. Disk Arrays selbst arbeiten mit zwei verschiedenen Methoden, um aufgetretene Fehler zu korrigieren: zum einen nutzen sie Error- Correcting-Codes (ECCs), die mit den Daten gespeichert werden oder sie greifen zum anderen auf die Möglichkeit der Replikation von Datenblöcken zurück. Es ist offensichtlich, daß hier Redundanzen bezüglich der Daten selbst gefordert sind. Außerdem ist Voraussetzung, daß für ausgefallene Platten im Disk Array ausreichend Ersatzplatten zur Verfügung stehen, auf denen die Daten wiederhergestellt werden können.
Eine einfache Möglichkeit zu Errechnung eines Error-Correcting-Codes ist die sog. Parity-Methode [2]. Sie beruht auf einer Exklusiven-Oder-Verknüpfung (XOR) einer Bit-Sequenz (Parity Granulat) von einer Platte im Disk-Array mit einer Bit-Sequenz gleicher Länge von den anderen Platten des Arrays. So entstehen Folgen von Parity Bits, die auf einer separaten Platte (Parity Platte) gespeichert werden. Ist das Parity Granulat ein Block, können Blöcke einer ausgefallenen Platte einfach dadurch rekonstruiert werden, in dem alle anderen Blöcke, aus denen der betroffene Parity Block konstruiert wurde, mit diesem wiederum durch eine XOR-Funktion verknüpft werden. Dies ist aufgrund der Assoziativität und Kommutativität der XOR-Funktion und deren Eigenschaft, daß (x XOR y) XOR y = x ist, möglich. Diese einfache Methode besitzt weitere Vorteile: Allerdings stößt Parity-Methode an ihre Grenzen, wenn zwei Platten gleichzeitig ausfallen oder eine anderer Platte bei der Rekonstruktion einer Platte ausfällt. Für obiges Beispiel ergibt sich für ein Disk Arrays welches mit der Parity-Methode arbeitet, eine MTTDL von 172 Jahren [2]. Will man diese noch weiter erhöhen und gleichzeitig die Korrektur von Mehrfachfehlern verbessern, so muß man einen Parity Block nicht über das Gesamte Disk-Array bilden, so man gruppiert die Platten in sog. Parity-Gruppen und berechnet für jede Gruppe einen eigenen Parity Block. Dafür werden natürlich mehr Parity Platten benötigt, oder der Parity Block wird selbst wieder partitioniert und auf den Platten der jeweiligen Parity-Gruppe verteilt [2].
Wie bereits erwähnt, kann man Fehlertoleranz auch durch Replikation erhalten. Eine einfache Methode ist hier das Prinzip der Spiegelplatten (Mirror-Disks), bei denen das Replikat eines Blocks immer an derselben Adresse auf der Spiegelplatte liegt, die beiden Platten also identisch sind. So erreicht man bei einer angenommenen MTTF von 50.000 Stunden und einer MTTR von 3 Stunden eine MTTDL von fast 50.000 Jahren für ein solches Paar von Spiegelplatten. Diese könnte man noch erhöhen, in dem man das Plattenduo durch eine weitere Platte ergänzt. Ein weiterer Vorteil ist, daß bei einer Veränderung auf einer Platte - wie bei der Parity-Methode - keine weiteren Leseoperationen anfallen, sondern nur der veränderte Block auf beide Platten geschrieben wird. Im Fehlerfalle geschieht die Rekonstruktion durch einfaches Kopieren der Blöcke von einer Platte auf die andere.

Erstellt: 02.01.1998
Zuletzt geändert: 02.01.1998
Autor: Gerrit Gragert