Modellierung und Algorithmen

Inhalt

• Modellierung
• Algorithmenentwurf
• Die Simulationsumgebung SimLab

Modellierung

Wir gehen davon aus, daß in einer Software-Schicht, die sich über unserem Server befindet, ein Dateisystem liegt. Diese Schicht verteilt die zu speichernden Daten auf die virtuellen Datenblöcke und wandelt eine Anfrage von dem Benutzer in Anfragen auf virtuelle Datenblöcke um (s. Abb 1). Das kann z.B. einfach dadurch realisiert werden, daß man in das Betriebssystem des Benutzers einen Treiber einsetzt, der SCSI Anweisungen statt an eine lokale Festplatte über das Ethernet verschickt. Eine Anfrage, die an den Server gerichtet wird, ist also nichts anderes als eine Anfrage nach einem virtuellen Datenblock. Im Gegensatz zu spezialisierten Datenservern besitzt unser Server also kein Wissen über den Inhalt oder die Zuordnung der einzelnen Datenblöcke. Das stellt jedoch keine große Einschränkung dar, da unsere Strategien, wie wir noch sehen werden, eine sehr gleichmäßige Verteilung der Anfragen über die Festplatten und somit sehr schnelle Bearbeitungszeiten erlauben und z.B. für verschiedene Bearbeitungsklassen verschiedene virtuelle Datenräume verwendet werden könnten.

Die Funktionsweise unseres Datenservers ist also bzgl. der Software-Schicht vergleichbar mit der von RAID-Systemen. Zielsetzung war es jedoch, die effiziente Zusammenarbeit mit wesentlich mehr Festplatten zu erlauben, als dieses mit den zum Antragszeitpunkt bekannten Techniken möglich war. Die angeschlossenen Rechner sollen nicht auf eine Menge von RAID-Systemen zugreifen, sondern unser Datenserver soll den Zugriff auf einen einheitlichen Adreßraum ermöglichen. Um den Anforderungen an die Skalierbarkeit unseres Datenservers gerecht werden zu können, wurde der Datenserver als eingebettetes, paralleles System ausgelegt. Kernkomponente in unserem System ist ein aktiver Routingknoten, der programmierbare und konfigurierbare Einheiten sowie verschiedene Kommunikationsschnittstellen in sich vereinigt. In Abb. 2 ist beispielhaft die Verschaltung von aktiven Routingknoten zu einem Butterfly-Netzwerk der Dimension drei skizziert.
 

Wie in Abb. 2 impliziert wird, besitzt jeder aktive Routingknoten einen Anschluß für die Verbindung zu einem externen Server bzw. einem LAN, einen Anschluß zur Anbindung von Festplatten und eine feste Anzahl von Schnittstellen für die Kommunikation zwischen den aktiven Routern. Die Verschaltung dieser internen Kommunikationsverbindungen ist dabei nicht festgelegt. Wir gehen davon aus, daß nicht jeder Router eine direkte Verbindung zu Festplatten und/oder zu einem externen Server haben muß, d.h. die entsprechenden Verbindungen können auch deaktiviert sein. Das ist z.B. der Fall, wenn die aktiven Router zu einem Butterfly-Netzwerk wie in Abb. 2 zusammengeschaltet sind, bei dem nur am obersten Level Platten und nur am untersten Level externe Server angeschlossen werden. Neben der Spezifikation der Anschlüsse haben wir ein Modell für den aktiven Routingknoten entwickelt, das aus fünf logischen Einheiten besteht: der User-Einheit (U), Scheduling-Einheit (S), Disk-Einheit (D), Routing-Einheit (R) und Topologie-Einheit (T) (siehe Abb. 3).

Im folgenden geben wir eine Übersicht über die Aufgaben dieser logischen Einheiten:

• User-Einheit: Diese Einheit regelt die Kommunikation mit den Benutzern (wie z.B. den Empfang und die Auslieferung von Blockanfragen). Weiterhin bestimmt sie, ob eine Anfrage zugelassen wird. Die Zulassung muß prinzipiell sicherstellen, daß der Datenserver im ausfallfreien Lauf nicht instabil werden kann. Eine zugelassene Anfrage wird an die Scheduling-Einheit weitergeleitet; nicht zugelassene Anfragen werden gelöscht.

 
• Scheduling-Einheit: Ein Aufgabengebiet dieser Einheit ist die globale Datenverwaltung. D.h. sie legt fest, von welchen Disk-Einheiten welche Datenblöcke zu verwalten sind. Desweiteren ist sie für die gleichmäßige Verteilung der Anfragen auf die Festplatten zuständig. Die Scheduling-Einheit entscheidet, ob Anfragen an die Disk-Einheit, die Router-Einheit oder die User-Einheit weiterzugeben sind, während die anderen drei Einheiten nur ausführende Instanzen sind.

 
• Disk-Einheit: Diese regelt die Kommunikation mit den Festplatten und die lokale Datenverwaltung. D.h. sie legt fest, in welchem Block welcher der angeschlossenen Festplatten die von der Scheduling-Einheit zugewiesenen Blöcke des virtuellen Datenraums zu finden sind.

 
• Routing-Einheit: Diese Einheit ist für die Kommunikation entlang der internen Verbindungen, die die aktiven Router miteinander verbinden, zuständig. Sie bestimmt, wie Konflikte zwischen Paketen, die zur gleichen Zeit die gleiche Verbindung benutzen wollen, aufzulösen sind.

 
• Topologie-Einheit: Diese ist für den Aufbau und das Finden von Wegen innerhalb des durch die aktiven Router gebildeten Netzwerks zuständig. Sie teilt der Routing-Einheit mit, welche Verbindung ein empfangenes Paket als nächste zu überqueren hat.

Algorithmenentwurf

Um eine hohe Effizienz der internen Datenflüsse bei gleichzeitiger hoher Auslastbarkeit des Datenservers sicherzustellen, sind effiziente Algorithmen für mehrere Problemklassen zu finden. Zum einen benötigen wir adaptive, fehlertolerante Datenverwaltungsstrategien, d.h. Strategien für die Abbildung der Datenblöcke des virtuellen Datenraums auf die Festplatten. Weiterhin benötigen wir Schedulingstrategien, die die Anfragen gleichmäßig über die Festplatten verteilen. Zusätzlich müssen effiziente Routingalgorithmen entwickelt werden. Ein Routingalgorithmus setzt sich aus einer Wegewahlstrategie und einer Switchingstrategie zusammen. Die Wegewahlstrategie legt fest, welchen Weg ein Paket durch das interne Routingnetzwerk zu nehmen hat, und die Switchingstrategie bestimmt, in welcher Reihenfolge die Pakete entlang dieser Wege geschickt werden sollen. Alle diese Strategien müssen natürlich grundsätzlich sicherstellen, daß die Speicherkapazität und die Schreib-/Leseleistung der Festplatten, die Bandbreite der Kommunikationsverbindungen und die Speicherkapazität interner Puffer nicht überschritten werden.

SimLab, ein Simulationssystem zur Untersuchung eingebetteter Datenserver

Auf der Grundlage der oben angegebenen Modellierung des Systems und seiner Komponenten wurde mit der Entwicklung von abgestuften Einzelmodellen für die Hardware- und Software-Entwicklung begonnen. Dabei war es notwendig, realitätsnahe Modelle zu entwickeln und in eine geeignete Simulationsumgebung zu integrieren. Unsere Anforderung an diese Modelle war, daß sie sicherstellen müssen, daß Verfahren, die sich in der Simulation als beste herausgestellt haben, dies auch sind, wenn sie in unserem Prototypen verwendet werden. Nach der Analyse verfügbarer Simulationsumgebungen haben wir uns zu der Entwicklung einer eigenen Umgebung, genannt SimLab, entschlossen. Grundlage für unsere Entscheidung war dabei die Tatsache, daß entweder nur Simulationsumgebungen für Teilaspekte unseres Servermodells verfügbar waren (wie z.B. von Festplatten, RAID-Systemen oder Routingnetzwerken) oder die Simulationsumgebung nicht unserer Philosophie und unseren Anforderungen entsprach.

Die Implementierung der Simulationsumgebung erfolgte in der Programmiersprache C++ auf Basis der von der Universität Saarbrücken entwickelten Klassenbibliothek LEDA. Die Umgebung wurde so aufgebaut, daß eine einfache Integration von neuen Objekten und Algorithmen in die Umgebung gewährleistet werden kann. In seiner jetzigen Form beinhaltet SimLab bereits eine Reihe von präzisen Modellen für die einzelnen Komponenten des Systems, die in vielen Punkten parametrisierbar sind. D.h. eine Anpassung an sich ändernde Hardwarebedingungen kann in vielen Fällen ohne Eingriffe in den Quelltext des Programms durchgeführt werden.

Die aktiven Routingknoten wurden in SimLab so abgebildet, daß jede logische Einheit des Routingknotens einer Klasse mit den entsprechenden, flexibel einstellbaren Soft- und Hardwareeigenschaften entspricht. Über Ableitungen von diesen Klassen wurden verschiedene Strategien für die einzelnen logischen Einheiten implementiert. Zusätzlich zu den Klassen für die logischen Einheiten gibt es Klassen, die das Benutzerverhalten simulieren, und Klassen, die einzelne Festplatten bis hin zu Festplatten-Feldern mit Caches möglichst realitätsnah simulieren. (Für die Festplatten haben wir z.B. die Leistungsparameter einer Seagate Barracuda verwendet.) Desweiteren sind Klassen für statistische Ausgaben implementiert worden. Die Verschaltung der aktiven Router untereinander und mit externen Benutzern oder Festplatten kann flexibel gehandhabt werden. Verfügbare Optionen für die Topologie sind z.B. das Gitter, das Butterfly, das DeBruijn Netzwerk, der Hypercube oder Expandernetzwerke. Diese stellen abgeleitete Klassen einer allgemeinen Architekturklasse dar.

SimLab ist in eine Werkzeugumgebung eingebunden, die es dem Benutzer z.B. ermöglicht, eigene Netzwerktopologien zu spezifizieren, Simulationsparameter aufzusetzen, und die Simulationsergebnisse auszuwerten. Die Konfiguration der Umgebung erfolgt über die Eingabe von Textdateien, in denen die Einstellungen für die einzelnen Module von SimLab enthalten sind. Jede der Dateien kann dabei auf verschiedenene Art und Weise erzeugt werden. Um einen einfachen Einstieg in die vielfältigen Möglichkeiten von SimLab sicherzustellen, haben wir eine graphische Benutzeroberfläche entwickelt, die als Java-Applet betriebssystemunabhängig verwendet werden kann. Um alle Möglichkeiten der Simulationsumgebung auszunutzen, kann zusätzlich eine direkte Eingabe erfolgen, es können aber auch über Skript-Dateien gezielt Ketten von Simulationsläufen gestartet werden.

Die Ausgabe unserer Simulationsumgebung erfolgt wiederum als Textdatei. SimLab protokolliert in diesen Dateien z.B. die Auslastung einzelner Platten und einzelner Kommunikationsverbindungen des internen Netzwerkes, den Anteil der Zeit, den die Platten mit dem Lesen und mit dem Suchen von Datenblöcken verbringen, und Statistiken über die Anzahl der Pakete, welche zu einem bestimmten Zeitpunkt in einem aktiven Router warten. Die Nachbearbeitung der Ausgaben erfolgt duch ein Statistik-Werkzeug, das die gewünschten Informationen extrahiert und aufbereitet. Es werden dabei Schnittstellen zu Matlab, Latex und HTML angeboten.

Die sequentielle Version von SimLab kann auf jeder Workstation ausgeführt werden, die über einen C/C++ Compiler und die LEDA-Bibliothek verfügt. Zusätzlich haben wir von Beginn an die Entwicklung von SimLab so ausgelegt, daß keine zentralen Instanzen vorhanden sind und so eine Parallelisierbarkeit von SimLab möglich ist. Hierzu müssen nur die sequentiellen Initialisierungs- und die Kommunikationsroutinen gegen parallele Routinen ausgewechselt werden. Neben dem Geschwindigkeitsgewinn einer parallelen Version ist der höhere zur Verfügung stehende Speicherplatz ein Hauptargument für eine Parallelisierung. Im Rahmen dieses Projektes haben wir eine erste Portierung von SimLab nach PVM durchgeführt und haben damit begonnen, eine Umsetzung für MPI und den SCI Cluster des PC² zu erstellen.

Navigationshilfe: