Inhalt

Programm
 
Projekt T1
Projekt T2
Projekt L1
Projekt N1
Projekt N2
Projekt LS1
 
Mitarbeiter
 
Veröffentlichungen
 
Projekte für Studenten
 

Links

 

ParaStation

Cluster OS

JavaParty

 

Teilprojekt T1: Intelligente Hochleistungsnetzwerke, schlanke Hochgeschwindigkeitsprotokolle, Betriebssystemerweiterungen (Tichy)


Folienpräsentation bei der Begehung durch die DFG 1999

Folienpräsentation bei der Begehung durch die DFG 2002 (Teil 1)

Folienpräsentation bei der Begehung durch die DFG 2002 (Teil 2)

Siehe auch: Cluster OS

Ausgangssituation

Mit der Lizenzierung der ParaStation2-Software an die Firma ParTec AG erfolgte die Übergabe der Entwicklung der Kommunikations-Software an ParTec während des Berichtszeitraums. Zeitgleich mit den personellen Änderungen wurde "skalierbare Dienste" als neues Thema aufgegriffen. Dieses Thema wurde als Schwerpunkt innerhalb von T1 am 1. November 2000 aufgenommen, um den Horizont unserer Forschung im Bereich der Grundsoftware auf Rechnerbündeln zu erweitern. Ursprünglich als alleinstehendes Projekt gedacht, wurde es bald einer der Ausgangspunkte für unsere Bemühungen, unsere Forschung in Richtung einer einheitlichen Gesamtsicht auf das Rechnerbündel voranzutreiben. Dieser Aspekt wird weiter unten im Detail beschrieben, während hier hauptsächlich auf das Projekt in seiner ursprünglichen Gestalt eingegangen werden soll.

Ergebnisse

ParaStation2, ParaStation3

Die verwendete Kommunikationshardware (Myrinet) wurde seitens des Herstellers erheblich weiterentwickelt. So sind mit der neuesten unterstützten Kartengeneration (Myrinet 2000) Übertragungsraten von bis zu 2Gbit in zwei Richtungen gleichzeitig möglich. Damit wird der maximale Durchsatz des PCI-Busses (64bit, 66MHz) bereits voll ausgeschöpft. In der Folge dieser Weiterentwicklung musste die ParaStation-Kommunikationssoftware entsprechend angepasst werden. Dabei konnten insbesondere neue Fähigkeiten der Karten zur Verbesserung der unprivilegierten Kommunikation ausgenutzt werden. Die Kommunikationssoftware unterstützt nun die auf den Myrinet-Adaptern zum Einsatz kommenden Prozessoren LanAI-7 und LanAI-9.

Gleichzeitig galt es, mit der raschen Entwicklung des Betriebssystem-Kerns von Linux auf den beiden unterstützten Architekturen (Intel x86 und Alpha) Schritt zu halten. Zwar erfolgt die eigentliche Kommunikation nach wie vor -- vereinfacht gesagt -- am Betriebssystem vorbei, um den Kommunikationspfad möglichst kurz zu halten. Dennoch muss gerade in einem modernen Betriebssystem die hardwarenahe Ansteuerung einer Adapterkarte sehr sorgfältig über genau definierte Schnittstellen erfolgen, um die Stabilität des gesamten Systems gewährleisten zu können. Dies betrifft insbesondere Vorgänge zur Initialisierung der Karte, das Aufspielen des auf dem Kartenprozessor ausgeführten Programmcodes oder das Einrichten von Speicher-Zuordnungstabellen für die unprivilegierte Kommunikation. Dabei stellte die 64bit-Architektur der Alpha-Prozessoren eine besondere Hürde dar, da hier zum einen auf korrekte Ausrichtung aller Daten im Hauptspeicher geachtet werden muss und sich zum anderen das Speichermanagement von der Intel-Architektur unterscheidet.

Die neueste Generation der Myrinet-Adapter bietet verschiedenen Techniken zur Unterstützung der unprivilegierten Kommunikation an. Die sogenannte Doorbell-Region ist ein Speicherbereich auf der Karte, in den Daten und Befehle vom Wirtsrechner aus geschrieben werden können. Dabei kann in den virtuellen Speicherbereich jedes Prozesses ein anderer Teil der Doorbell-Region eingeblendet werden. Dies wurde ausgenutzt, um die unprivilegierte Kommunikation mehrprozess- und mehrbenutzerfähig zu gestalten und den gegenseitigen Schutz zu verbessern.

Weiterhin wurde die Möglichkeit geschaffen, die zu kommunizierenden Nutzdaten beim Sender direkt aus dem Speicher der Anwendung in den Speicher der Myrinet-Karte und beim Empfänger aus dem Speicher der Karte direkt wieder in den von der Anwendung bereitgestellten Speicherbereich zu übernehmen. Diese sogenannte Zero-Copy-Technik vermeidet das Kopieren der Nutzdaten in Speicherbereiche des Betriebssystemkernes und eliminiert so einen Engpass moderner Computerarchitekturen, bei denen das Kopieren Speicher->Speicher deutlich langsamer ist als das Kopieren vom Speicher direkt über den PCI-Bus zu einer Adapterkarte per DMA, den viele der heute verfügbaren Netzwerkadapter (und auch die Myrinet-Karten) unterstützen.

Ferner wurde die Definition der Kommunikationsschnittstelle, wie sie sich dem Anwendungsprogramm darstellt (PSPort), grundlegend überarbeitet. Mit Blick auf eine der aktuellen Hauptanwendungen dieser Schnittstelle, nämlich der Implementierung von MPI, wurde eine schlanke Bibliothek für paketorientierte Kommunikation geschaffen, die mit einer geringen Anzahl von Funktionen auskommt und dennoch sehr flexibel ist.

Da - neben den immer wichtiger werdenden Anwendungen im Bereich Java und JavaParty, vergl. Teilprojekt T2 - weiterhin viele Anwendungen MPI als Kommunikationsbibliothek erwarten, lag hier ein weiterer Schwerpunkt der Arbeit. Grundlage ist die MPI-Implementierung MPIch der Universität von Chicago und der Mississippi State University. Diese gliedert sich in drei Teile: Ein auf die jeweilige Hardware zugeschnittener Gerätetreiber stellt nur Funktionen zum Senden und Empfangen einzelner Nachrichten zur Verfügung. Darauf baut ein zweiter Teil auf, der Funktionen zur Nachrichtenverwaltung enthält und ein sogenanntes Abstract Device Interface, ADI implementiert. Der dritte Teil schließlich nutzt diese ADI-Funktionen und stellt darauf aufbauend die eigentlichen MPI-Funktionen zur Verfügung. In diesem Konzept wäre zunächst nur die Entwicklung des Gerätetreibers für die Myrinet-Adapter unter ParaStation erforderlich. Das skizzierte Design bedingt, dass die darauf aufsetzende Schicht kaum Wissen über die jeweilige Kommunikationshardware besitzt und deshalb sehr allgemein gehalten ist. Weil nun die Kommunikationsschnittstelle PSPort (s.o.) bereits alle benötigten Funktionen zur Nachrichtenverwaltung enthält und sehr effizient ist, haben wir uns entschieden, statt eines Gerätetreibers direkt die ADI-Schicht zu implementieren.

Wie von den Gutachtern empfohlen, wurde die Weiterentwicklung der ParaStation-Kommunikationssoftware dann abgeschwächt und andere Themen dafür aufgegriffen. Die Mitarbeiter der erfolgreich ausgegründeten ParTec AG wurden in der Technik der unprivilegierten Kommunikation ausgebildet. Ferner stellte sich ParaStation2 als ungeeignet heraus, sowohl Myrinet 2000 als auch nicht-blockierende Kommunikation zu unterstützen. Also musste in Zusammenarbeit mit ParTec ein neues Software-Konzept erarbeitet werden, welches schließlich von ParTec-Mitarbeitern implementiert wurde. Die ebenfalls notwendige Portierung von MPI wurde von einem Universitätsmitarbeiter geleistet. Man sieht, dass selbst ein voll funktionsfähiger Prototyp wie ParaStation2 für einen echten Produkteinsatz nochmals komplett überarbeitet werden musste. ParaStation3 wird nun zusammen mit einer Management-Software von ParTec vermarktet.

Die Transferleistung an ParTec verschlang viel Zeit und Ressourcen. Ferner ist zu beachten, dass aus Wettbewerbsgründen eine Veröffentlichung des neuen Konzeptes nicht gerne gesehen wird. Trotzdem denken wir, dass der Einsatz an dieser Stelle nicht nur wirtschaftlich erfolgreich ist, sondern auch neue Impulse an die Forschergruppe zurücklieferte.

Es hat sich gezeigt, dass die Leistung der in diesem Teilprojekt entwickelten Strategien für effiziente User-Level-Kommunikation auf intelligenten Netzwerkadaptern den hohen Anforderungen gerecht wird, die heute von den Anwendern von Hochleistungs-Parallelrechnern, zum Beispiel für physikalische Simulationen, gestellt werden. Die Leistungserhöhung von ParaStation3 auf ALiCE um 9% ist rein durch Softwareverbesserungen zustande gekommen und hat ALiCE in der TOP 500 Liste kräftig nach vorne geschoben.


Abb. 1: Leistung von MPI Send/Receive auf verschiedenen Plattformen

Skalierbare Dienste

Überblick

Dieses Projekt zielt darauf ab, Rechnerbündel als leistungsfähige Plattform zur Entwicklung skalierbarer Dienstgeber zu verwenden. Diese Arbeit ist Teil der Entwicklung eines Betriebssystems für Rechnerbündel, das dem Anwender eine einheitliche Sicht auf das Rechnerbündel bieten wird. Ein typisches Beispiel ist eine skalierbare Architektur für Rechnerbündel, welche ein Systemverkehrsnetz (System Area Network, SAN, eine sehr schnelle Verbindung wie von ParaStation, GM, VMMC und Unet) einsetzt, um die klassischen Netzwerkfähigkeiten von Rechnerbündeln (d.h. LAN) zu verbessern (vgl. Abb. 2). Die Geschwindigkeit dieser leistungsstarken Verbindungen sowohl in Bezug auf die Latenz wie auch die Bandbreite ähneln eher denen eines Speichersubsystems als denen eines allgemeinen Netzwerkes. Genau diese Eigenschaft ist es, die eine engere Einbindung der verschiedenen Ressourcen des Rechnerbündels ermöglicht und unsere Hoffnung begründet, mehr Geschwindigkeit für zahlreiche Dienste zu erzielen, wenn man das Rechnerbündel aus PCs eher als eine einzelne Rechnereinheit denn als Ansammlung einzelner Maschinen auffasst.


Abb. 2: Systemarchitektur

Unsere Arbeit konzentriert sich auf zwei Richtungen, die beide dasselbe Problem anzugehen streben. Zum einen versuchen wir, effiziente Mechanismen für den Lastausgleich (sowohl im Sinne der CPU-Last wie auch der Anzahl bedienter Anfragen) und kooperatives Caching über das Rechnerbündel verteilt in dem Bestreben zu entwickeln, den Bedürfnissen nach Skalierbarkeit verschiedener Dienste wie Web- oder Datenbankdiensten nachzukommen. Die hauptsächlich ins Auge gefassten Betriebssystem-Module sind der TCP/IP-Stapel und die niederen Schichten des Dateisystems.

Zum anderen sind wir daran interessiert, einen performanten Ausgleich zwischen den offenbar gegensätzlichen Zielen des Lastausgleichs der Anfragen und dem Erreichen einer hohen Datenlokalität zu finden. Der Schlüssel unserer Forschung, die eine skalierbare Infrastruktur zur lokalitätsbewussten Verteilung von Anfragen aufbaut, liegt darin, das Zuordnen (Scheduling) von Verbindungen mit der Puffer-Cache-Affinität zu verbinden.

Entwurfsvoraussetzungen

Beim augenblicklichen Stand unseres Forschungsvorhaben wird die zentrale Fragestellung nach einer Infrastruktur lastausgeglichener kooperativer Puffer-Caches durch einen aus drei Phasen bestehenden Algorithmus zur Anfrageverteilung ausgedrückt, der im Kontext eines verteilten Dienstgebers abläuft, der auf einem Rechnerbündel basiert und eine einzige IP-Adresse für all seine Rechnerknoten verwendet. Es gibt zwei Typen von Maschinen im Rechnerbündel: Frontend-Maschinen, die als einfache Verbindungs-Router Verwendung finden, und Backend-Maschinen, die die Anfragen eigentlich bedienen.

Die Anfrage-Verteilung basiert auf zwei Mechanismen: halbgenerische TCP-Verbindungen und netzwerkgebundene Dateien. Halbgenerische TCP-Verbindungen sind jene Verbindungen, bei denen ein Endpunkt an eine für mehrere Dienstgeber-Maschinen gemeinsame generische IP-Adresse geknüpft ist, die sogenannte Backend-Maschinen, und die von einem physikalischen Dienstgeber zum nächsten migrieren können. Netzwerkgebundene Dateien sind Dateien, die entweder unbearbeitet ausgeliefert werden oder Ergebnis einer Berechnung des Dienstgebers als Antwort auf eine Dienstanfrage sind. Die tatsächliche Platzierung ihrer Daten ist ausschlaggebend für die Gesamtgeschwindigkeit des verteilten Dienstgebers. Der Mechanismus der halbgenerischen TCP-Verbindungen spielt eine entscheidende Rolle für die Zuordnung von Verbindungen, während die netzwerkgebundenen Dateien die Cache-Affinität der ausgegebenen Aufgaben herausstellen sollen, um die über das Netzwerk geschickten Anfragen zu bedienen.

Der Algorithmus zur Anfrageverteilung
Phase 1

Die erste Phase der Verteilung ist blind (uninformiert) und wird auf der sogenannten Frontend-Maschine durchgeführt, die als Verbindungs-Router agiert. Dabei handelt es sich um eine einfache Rundumverteilung, die die Anfragen gleichmäßig zu verteilen versucht. Die Verteilung ist absichtlich einfach gehalten, um die Frontend-Maschine nicht zu überlasten (da sie nichts weiter als ein Verbindungs-Router sein soll). Es kann viele solcher Verbindungs-Router geben -- ein entscheidender Faktor für die Skalierbarkeit.

Phase 2

Die zweite Phase der Verteilung findet auf den Backend-Maschinen statt, wenn das eingehende Ereignis einer Verbindungsanfrage eine Überprüfung der TCP- und CPU-Last auf dieser Maschine auslöst. Falls die Maschine hochbelastet ist, wird das eingehende SYN-Paket zu einer weniger belasteten Maschine umgeleitet. Der zu zahlende Preis für diese zusätzliche Wegstrecke errechnet sich aus der SAN-Latenz für ein SYN-Paket, amortisiert sich aber über die Kosten der gesamten Verbindungsaktivität gerechnet, so dass es als vernachlässigbar angesehen werden kann, da es nur ein einziges Mal beim Aufbau der Verbindung geschieht. Die Entscheidung, die Zuweisung der TCP-Verbindung wiederum auf Backend-Ebene abzuwickeln, erfolgt ebenfalls im Bestreben, die Frontend-Maschinen so leichtbelastet wie möglich zu halten, da ihre Aufgabe hauptsächlich darin besteht, eine Schnittstelle zwischen den Backend-Maschinen und der Außenwelt zu schaffen. Darüber hinaus ergibt sich diese Wahl wie von selbst, da die Backend-Maschinen untereinander kooperieren und daher über jene Informationen verfügen, die ihnen erlauben, einen besseren Rechnerknoten für die Bedienung der Anfrage auszuwählen. Andernfalls hätte man die Frontend-Maschine über die "Last" verschiedener Backend-Maschinen zu informieren. Diese Informationen sind jedoch unter den Backend-Maschinen sowieso schon bekannt, da sie miteinander diese Art der Informationen austauschen.

Phase 3

Die dritte Phase der Anfrageverteilung findet auf den Backend-Maschinen statt, die die eingehende Verbindung bereits angenommen haben (d.h. ihre "Last" ist akzeptabel), sei es als Ergebnis einer Frontend-Umleitung oder als Resultat einer Backend-Umleitung. Hier wird das Protokoll der Anwendungsebene (z.B. HTTP) ganz gewöhnlich bis zu dem Punkt umgesetzt, an dem die Anwendung (z.B. der Web-Dienstgeber) eine Datei zur Beantwortung einer Anfrage öffnet. Zu diesem Zeitpunkt überprüft die dritte Phase des Protokolls zur Anfrageverteilung, ob die Datei irgendwo im Rechnerbündel in einem Puffer-Cache im Hauptspeicher zwischengespeichert ist oder nicht. Unter Abwägung der verschiedenen Kosten -- Einlagern der Datenblöcke in den lokalen Puffer-Cache und Last der Maschine, auf der dieser Cache sitzt (falls es eine solche Maschine gibt) -- wird eine Entscheidung getroffen: entweder wird die Datei beim Öffnen lokal in den Speicher frühzeitig geladen, um spätere Leseoperationen ausführen zu können, oder die Verbindung wird zu der Backend-Maschine migriert, die die Datei im Cache bereits zwischengespeichert hat.

Falls keine Maschine die Datei gerade im Cache hält, wird sie vom Heim dieser Datei geholt. Das Heim einer Datei bezeichnet die Maschine, auf der die physikalische Platte liegt, auf der die Datei gespeichert ist. Alle Zugriffe auf entfernte Dateien durchlaufen den von uns entwickelten Treiber für entfernte Platten. Dieser Treiber erlaubt die Verwendung kooperativer Puffer-Caches für das lokale Dateisystem.

Software-Entwicklung

Es wurden vier ladbare Kernmodule für Linux im Umfang von in etwa 5000 Zeilen Betriebssystemkern-Code entwickelt, um den verschiedenen Teilen des oben genannten Algorithmus Rechnung zu tragen.

Innerhalb des Moduls zum Lastausgleich wurde die erste Phase des Algorithmus zur Anfrageverteilung bereits implementiert und getestet. Der Verbindungs-Router agiert im wesentlichen als ein Netzwerkswitch der Ebene 2, der das ARP-Modul im Betriebssystemkern modifiziert, um eine Rundumverteilung der Anfragen zu ermöglichen, die auf die einzige, nach außen sichtbare IP-Adresse des "virtuellen" Dienstgebers zielen. Die zweite Phase des oben beschriebenen Algorithmus ist ebenfalls implementiert und funktioniert. Diese Phase stützt sich hauptsächlich auf die Fähigkeit, eine eingehende Anfrage von einer Backend-Maschine zu einer anderen zu migrieren. Die Migration eines bestehenden Verbindungsendpunktes ist Teil der dritten Phase des Algorithmus und kann auch aus Gründen der Datenlokalität oder des Lastausgleiches ausgelöst werden und funktioniert ebenfalls.

Der Mechanismus für kooperatives Caching ist hauptsächlich auf einer eigens entwickelten Schnittstelle eines Treibers für entfernte Platten implementiert. Sie ermöglicht die Speicherung von Datenblöcken der entfernten Platte im lokalen Puffer-Cache, indem die Blöcke über schnelle Verbindungen gesendet werden. Dies wiederum ermöglicht das Speichern der Datenblöcke einer einzigen physikalischen Platte in den kooperativen Caches verteilt über das Rechnerbündel. Unser Entwurf folgt der dienstgeberlosen oder Peer-to-Peer-Philosophie, um einen höheren Grad der Skalierbarkeit zu garantieren. Darüber hinaus nutzt die Implementierung den als bottom-half handling bezeichneten Mechanismus der Software-Unterbrechungen unter Linux. Deswegen folgt die Auslieferung der Datenblöcke von Platte einem ereignisgesteuerten Entwurf. Mit dieser Vorgehensweise wird, wie sich gezeigt hat, die beste Performanz erzielt.

Die gegenwärtige Performanz des Treibers für entfernte Platten stellt die Vorteile des kooperativen Caching unter Beweis. Einen bereits im Cache gespeicherten Datenblock der Größe 4kB von einem entfernten Puffer-Cache zu holen, kostet in etwa 350Μ auf unseren Systemen im Vergleich zu etwa 13 ms beim Lesen (ohne Cache) von der lokalen Platte. Jenseits der zeitlichen Performanz gibt es aber auch noch den Aspekt des Speicherplatzes: es ist nicht notwendig, Dateien auf jedem Knoten des Rechnerbündels zu replizieren, um sie für die Bedienung von Anfragen verfügbar zu machen.

Querbezüge zu anderen Teilprojekten

Die zwei hauptsächlichen, mit dem Projekt "Skalierbare Dienste" verknüpften Kern-Module -- das Modul für kooperatives Caching und das Lastausgleichs-Modul -- können als eigenberechtigte Bestandteile eines Betriebssystems für Rechnerbündel betrachtet werden und daher von allgemeinem Nutzen sein. Dabei beabsichtigten wir von Anfang an, die Auswirkungen des kooperativen Caching auf unser paralleles Dateisystem Clusterfile zu untersuchen. Weitere Details zu einer möglichen Zusammenarbeit finden sich weiter unten.

Fazit und Erfahrungen

Die mit dem Übergang der Entwicklung der Kommunikations-Software an ParTec und dem Aufgreifen der vorstehend beschriebenen neuen Themen begonnene Umorientierung erfordert eine neue Gesamtstrategie für T1. Nach unserem derzeitigem Planungshorizont wird uns dies in Richtung eines Betriebssystems für Rechnerbündel führen, für welches wir eine Gesamtkonzeption im Begriff zu entwickeln sind (siehe weiter unten).

Bezüglich des Projektes "Skalierbare Dienste" konnten wir die gesteckten Ziele bezgl. des kooperativen Caching erreichen. Auch die dynamische Verlagerung des Endpunktes einer TCP-Verbindung konnten wir verwirklichen.

Die unmittelbaren Aussichten des Projektes "Skalierbare Dienste" sind eng mit dem Erfolg der Anfrageverteilung geknüpft. Dies läuft letztlich auf die Auswertung der Performanz für einen spezifischen Dienst (wie z.B. Web-Dienstgeber) hinaus, aber auch darauf, nach einer performanten Abwägung zwischen Lastausgleich und Datenlokalität zu suchen. Langfristig wird das Ziel sein, das Potenzial der von uns entwickelten Software-Module in größerem Kontext auf einem Rechnerbündel-Betriebssystem zu untersuchen, etwa zur Beschleunigung des verteilten/parallelen Dateisystems.

Ziele und Arbeitsprogramm

Rechnerbündel werden in jüngster Zeit in Anbetracht ihres Leistungspotenzials als Rechnerplattform immer beliebter. Abgesehen von der Errichtung schneller nachrichtengekoppelter Systeme und auf virtuellen Speicher abgebildeter Netzwerkkarten wurde bislang allerdings nur wenig getan, um Rechnerbündel im Sinne einer einzigen Recheneinheit nutzen zu können. Die meisten der als Gesamtsicht (engl. Single System Image) bezeichneten Implementierungen stellen nichts anderes als einen Ansatz auf Benutzerebene dar und basieren somit auf von klassischen Betriebssystemen angebotenen Diensten. Mag diese Lösung für manchen Anwender noch akzeptabel erscheinen, so empfinden wir sie zumindest unter dem Gesichtspunkt der Zuverlässigkeit, Geschwindigkeit und Skalierbarkeit als unbefriedigend. Diese Einschätzung basiert hauptsächlich auf der Beobachtung, dass eine weit engere Koppelung der Rechner innerhalb des Bündels zu einer besseren Performanz führen kann als bei einem verhältnismäßig lose gekoppelten Verbund einzelner Maschinen. Die damit verbundene engere Zusammenarbeit der Ressourcen des Rechnerbündels läuft auf den Entwurf und die Implementierung von Teilen eines verteilten Betriebssystems hinaus. Diese Teile werden als Kernmodule des Linux-Betriebssystems implementiert werden.

Einen wichtigen Teil dieser Software-Architektur bildet die hochperformante ParaStation-Kommunikations-Software für Myrinet. Auf der Basis ihrer Leistung in Bezug auf Latenz und Bandbreite hoffen wir, eine engere und effizientere Kooperation zwischen den Knoten des Rechnerbündels erzielen zu können. Die "entfernten" Ressourcen des Rechnerbündels (d.h. diejenigen, die sich nicht im lokalen Knoten befinden) werden auf jedem Knoten in einer Software-Schicht virtualisiert, die wir allgemein als VRL (Virtual Resource Layer) bezeichnen wollen. Sie profitiert unmittelbar von der Geschwindigkeit der ParaStation. Als ein Beispiel für eine virtualisierte Ressource haben wir bereits, wie weiter oben beschrieben, einen Treiber für Zugriffe auf entfernte Plattenspeicher entwickelt, der in dem Projekt "Skalierbare Dienste" Anwendung findet. Weitere Beispiele für virtualisierte Ressourcen sind virtuelle Netzanschlüsse (d.h. lokale Stellvertreter für entfernte Netzwerkkarten, benötigt für Migration von TCP/IP-Endpunkten) oder RDMA-Geräte (Remote DMA), die mittels des ParaStation-Treibers den direkten Zugriff auf entfernten Speicher zulassen. All diese Treiber für virtuelle Ressourcen sehen einen im Vergleich mit einer einfachen Kommunikationsinfrastruktur höheren Abstraktionsgrad im Umgang mit den Ressourcen des Rechnerbündels vor. Die darauf aufbauenden Schichten der Gesamtarchitektur können aus diesem höheren Abstraktionsgrad ihren jeweiligen Nutzen ziehen. Beispielsweise verwendet das Modul für kooperatives Caching, welches im Rahmen des Projektes "Skalierbare Dienste" entwickelt wurde, den Treiber für entfernten Plattenspeicher für den Zugriff auf Datenblöcke. Auf höherer Ebene kann ein lokalitätsbewusstes Modul für die Verteilung von Anfragen an Netzwerkdienste, welches die Fähigkeiten eines Moduls für den Lastausgleich mit denen eines Moduls für kooperatives Caching verbindet, Unterstützung für den Aufbau skalierbarer Dienste auf dem Rechnerbündel gewährleisten. Mehr noch, auch ein verteiltes oder paralleles Dateisystem wie Clusterfile kann seinerseits von den Diensten des Moduls für kooperatives Caching oder des lokalitätsbewussten Moduls zur Verteilung profitieren. All dies sind typische Beispiele skalierbarer Dienste eines Rechnerbündel-Betriebssystems für den Endbenutzer. Im Zuge der Weiterentwicklung unseres Entwurfs sehen wir als weitere mögliche Forschungszweige die Entwicklung von Mechanismen für Checkpointing und Prozessmigration, journalisierende parallele/verteilte Dateisysteme und fehlertolerante Dienste. Einige von ihnen sollen unter der Förderung von RESH entwickelt werden, andere werden aus externer Förderung bestritten werden.

Projektziele und Arbeitsprogramm

Für den Zeitraum von April 2002 bis März 2004 sehen wir die folgenden Forschungsschwerpunkte:

Teilziel A: Skalierbare Dienste

Die für die Zukunft geplanten Arbeiten im Bereich der Entwicklung skalierbarer Dienste für Rechnerbündel umfasst die folgenden Unterthemen:

  • Leistungs-Analyse eines spezifischen Dienstes

    Mit dem nahendem Abschluss der Testphase und Fehlerbereinigung der aktuellen Arbeiten beabsichtigen wir, mit der Auswertung der Leistung eines Web-Dienstgebers auf der von uns entwickelten Rechnerbündel-Infrastruktur fortzufahren. Die Auswertung wird sich auf Skalierbarkeit und Antwortzeit konzentrieren. Zum Messen der Geschwindigkeit werden wir einerseits Zugriffsmuster auf Webseiten (auch synthetische) und andererseits Benchmarks heranziehen. Wir haben vor, unmodifizierte Software (beispielsweise Apache) als Web-Dienstgeber zu verwenden, um somit das verteilte Wesen des "virtuellen" Dienstgebers mit einer einzigen IP-Adresse zu verbergen. Die Ergebnisse dieser Auswertung werden letztlich einige der Richtungen bestimmen, die wir im Rahmen unserer zukünftigen Forschungsschwerpunkte verfolgen werden, sobald die Zugriffsmuster und Benchmarks mögliche Schwächen unseres ersten Entwurfs aufdecken. Desweiteren erwarten wir von den Ergebnissen, unsere weitere Forschung über die Abwägung zwischen Lastausgleich und Datenlokalität von Web-Dokumenten voranzutreiben.

  • Abwägungen zwischen Lastausgleich und Datenlokalität

    Wir beabsichtigen zu untersuchen, wie sich ein Gleichgewicht zwischen Lastausgleich der Anfragen einerseits und kooperativem Caching von angefragten Dokumenten andererseits einstellen lässt, da diese beiden Ziele offenbar einander zuwiderlaufen: bei bloßer Beachtung des Lastausgleichs wird die mit den Transaktionen verknüpfte Datenlokalität gering sein; bei ausschließlicher Berücksichtigung der Datenlokalität kann die Performanz aufgrund mangelnden Lastausgleichs schlechter werden. Wir werden insbesondere Strategien untersuchen, mit denen sich ein vernünftiger Lastausgleich erzielen lässt, ohne dabei deutliche Einbußen im Hinblick auf die Datenlokalität hinnehmen zu müssen. Dies erfordert zunächst eine genauere Betrachtung der Verbesserungen, die durch die Infrastruktur des kooperativen Caching ins Spiel gebracht werden. Hierbei müssen Fragen zum zusätzlichen Aufwand beantwortet werden, der dem Wirtsrechner aufgebürdet wird, indem Datenblöcke durch die lokalen Caches hin und her bewegt werden.

    Solche Fragen schließen die Identifizierung desjenigen Punktes ein, bei dem die Kommunikations-Infrastruktur der Myrinet-Hardware zum Flaschenhals wird. Auch stellt sich die Frage, wie durch eine besondere Strategie zur Platzierung von Caches für Einzelblöcke (Blöcke, die gerade in einem einzigen der lokalen Caches des Rechnerbündels gespeichert sind) diesen Flaschenhals der Kommunikationsverbindung hinausgeschoben werden kann. Wenn man über solche Strategien spricht, muss man sich nicht nur die Einschätzung der Performanz wohlbekannter Caching-Protokolle in diesem Kontext vor Augen halten, sondern auch die Entwicklung neuer Protokolle in Betracht ziehen, die besser zu unseren Absichten passen. Als nächstes wird zu untersuchen sein, wie sich diese Caching-Strategien auf den Lastausgleich der Anfragen auswirken und welche von ihnen sich somit am besten eignet. Beispielsweise mögen kurzlebige Verbindungen eine Entscheidung zur Migration einer Verbindung bevorzugen (d.h. zulassen, dass ein Dokument irgendwo in einem Cache gehalten wird), während sich langlebige Verbindungen (z.B. persistente HTTP-Verbindungen) möglicherweise auf das frühzeitige Laden (prefetching) von Dateien zum lokalen Cache verlassen, um von der Datenlokalität zu profitieren. In ähnlicher Weise mögen dynamisch erzeugte Dokumente in der Tat auf zuvor bereits im Cache gespeicherte Ergebnisse angewiesen sein, um eine bessere Antwortzeit zu erreichen. Andauernde Beschlagnahme derjenigen Maschine, die diese Ergebnisse in ihrem Cache speichert, kann zu schwerwiegendem Ungleichgewicht der Systemlast dieser Maschine führen. Dies liegt zum einen daran, dass alle anderen Maschinen, die ursprünglich eine Anfrage nach solchen dynamischen Dokumenten erhielten, nunmehr ihre Verbindung zu dieser Maschine migrieren. Diese Maschine wird dann schnell überlastet werden. Darüberhinaus ist die Entscheidung der anderen Maschinen zur Migration Vergeudung von Rechenzeit. Tatsächlich wäre es interessant in Erfahrung zu bringen, ob es einen allgemeinen Rahmen gibt, der konsistente Entscheidungen darüber zu fällen erlaubt, wann die Migration einer Verbindung dem frühzeitigen Laden einer Datei vorzuziehen ist.

  • Implementierung eines Konsistenzprotokolls für das Modul für kooperatives Caching

    Möchte man mehrfache Kopien derselben Speicherseite zulassen, wirft dies das zusätzliche Problem auf, diese Kopien konsistent zu halten. Wir verwenden hier den Begriff der Konsistenz, wie er in verteilten Betriebssystemen verwendet wird.

    Momentan fehlt der Schicht für kooperatives Caching jedoch noch ein Konsistenzprotokoll. Zum einen liegt der Grund hierfür darin, dass die bisherige Arbeit am kooperativen Caching nur Lesezugriffe berücksichtigte. Daher gab es keinen Bedarf für Konsistenz, und das einzige wichtige Ziel bestand darin, Dateiblöcke so weit wie möglich im Haupt-Speicher zu halten.

    Zum anderen verbringt in unserem Falle die von uns angestrebte Anwendung, ein Web-Dienstgeber, die meiste Zeit mit dem Lesen von Dokumenten. Aus diesen Gründen haben wir bislang das Problem der Konsistenz aufgeschoben. Die Problematik der Konsistenz ist jedoch insofern wichtig, als wir dem Modul für kooperatives Caching eine Schlüsselrolle in unserem verteilten Dateisystem zukommen lassen werden, welches wir gerne auf unserem Rechnerbündel aufbauen möchten. Deswegen haben wir vor, das Ziel, konsistente Schreibzugriffe in unsere Schicht für kooperatives Caching zu implementieren, in Angriff zu nehmen. Tatsächlich existieren bereits Schreibfähigkeiten in dieser Schicht, es gibt aber gegenwärtig keine Konsistenzgarantien. Genauer gesagt, rühren die Inkonsistenzen in unserem Entwurf von den verschiedenen Caches her, die in den klassischen, nicht-verteilten Betriebssystemen Anwendung finden, wie Verzeichnis-Cache, inode-Cache und so fort.

Teilziel B: Vervollständigung der Schicht virtueller Ressourcen

Die Schicht virtueller Ressourcen (Virtual Resource Layer, VRL) versucht, eine einheitliche Sicht auf die Ressourcen des gesamten Rechnerbündels zu schaffen. Hierdurch entsteht eine Abstraktion von der Kommunikationsinfrastruktur: statt sich mit einem nachrichtengekoppelten System abgeben zu müssen, können die höheren Softwareschichten mit Prozessgruppen, Dateiblöcken, Speicherseiten, Netzwerkverbindungen usw. arbeiten.

Ein erster Schritt ist der Bau eines koordinierten Prozessabwicklers (engl. gang scheduler). Diese Komponente sorgt dafür, dass alle Prozesse einer parallelen Anwendung gleichzeitig auf ihren Prozessoren aktiv werden und so durch die andernfalls notwendige Prozessumschaltung nicht gebremst werden. Frühe Arbeiten zu diesem Thema stammen von Ousterhout und anderen und enthalten Vorschläge für Multiprozessoren. Bei Rechnerbündeln hat man bislang wegen des Kommunikationsaufwandes eine Technik gewählt, die Prozesswechselentscheidungen aufgrund einer lokalen Sicht der Kommunikationsaktivitäten trifft. Leider sind die Ergebnisse bei hoher Last enttäuschend, so dass wir eine global koordinierten Prozessabwickler anstreben werden. Dieser soll mit Hilfe eines globalen Abwicklungsplanes und ausreichend genau synchronisierter Uhren die Prozesse von Prozessgruppen gleichzeitig aktivieren.

Der nächste Schritt ist die Verwirklichung von lokalen Stellvertretern entfernter Ressourcen. Beispielsweise kann beim kooperativen Caching ein Rechnerknoten einen Einzelblock in einem Puffer-Cache speichern. Ein Einzelblock ist die im gesamten Rechnerbündel einzige, eindeutige Kopie in einem Cache eines Dateiblocks einer der Platten des Rechnerbündels. Wenn dieser Einzelblock aus dem Cache verdrängt werden soll, möchte man gerne eine Kopie in irgendeinem anderen Cache des Rechnerbündels anlegen, denn es ist deutlich schneller, den Block von solch einem Cache zu bekommen, als ihn erneut von der Platte laden zu müssen. In diesem Kontext speichert einer der Puffer des Treibers für entfernte Platten den Einzelblock, und dieser Treiber wird zum neuen "Heim" des Blocks. Künftig müssen daher jegliche Algorithmen zur Verwaltung verteilter Ressourcen (z.B. Konsistenzprotokolle) den Treiber für entfernte Platten ins Spiel bringen.

Zur Zeit besteht die Schicht virtueller Ressourcen aus einem einzigen Modul: dem Treiber für entfernte Platten. Es sind jedoch mindestens zwei weitere solche virtualisierten Ressourcen in Planung: der RDMA-Treiber und die Virtuelle Netzwerkkarte.

Ein RDMA-Treiber ermöglicht direkte Speicher-zu-Speicher-Übertragung zwischen zwei verschiedenen Knoten des Rechnerbündels auf Basis von Hochleistungsnetzwerken. Im Gegensatz zum Treiber für entfernte Platten, der Datenblöcke referenziert (mittels Knotennummer, inode und Blocknummer), arbeitet ein RDMA-Treiber unmittelbar auf virtuellen Speicheradressen. Die Treiberschnittstelle muss seitenorientierte Operationen unterstützen, denn wir beabsichtigen die Entwicklung einer verteilten Version auf den Speicher abgebildeter Dateien (mmap). Diese Version wird sich des kooperativen Caching bewusst sein. Denkbar ist auch die Verwendung des Treibers im Kontext von Checkpointing (für Checkpointing für virtuellen Speicher) oder im Umfeld eines Systems mit gemeinsamen verteilten Speicher (DSM).

Die Idee virtueller Netzwerkkarten rührt von unserer gegenwärtigen Arbeit im Bereich der skalierbaren Dienstgeber her. Unser gegenwärtiges Schema für die Migration von Verbindungen verwendet nämlich bislang einen ``hartverdrahteten'' und unflexiblen Mechanismus. Die Fähigkeit, lokal auf eine entfernte Netzwerkkarte zuzugreifen, würde uns für die Migration einen deutlich saubereren Entwurf ermöglichen. Dieses Konzept ist letztendlich nicht weit von den wohlbekannten Durchtunnelungstechniken der Netzwerktechnik entfernt.

Teilziel C: Verteiltes Dateisystem

Ein weiteres interessantes Forschungsfeld sehen wir in der Untersuchung, wie ein verteiltes Dateisystem von der übrigen Infrastruktur des Rechnerbündel-Betriebssystems profitieren kann. Klassische verteilte Dateisystem wie NFS sind zustandslos und können die Puffer-Caches in einem Cluster nicht ausnutzen. Wir erwarten, dass die verbesserten Fähigkeiten der Infrastruktur sich positiv auf das Gesamtsystem auswirken werden und beabsichtigen, dies im Kontext der Arbeit am parallelen Dateisystem Clusterfile zu untersuchen, welches ebenfalls in unserer Gruppe an der Universität Karlsruhe entwickelt wird.

Abgrenzung zu parallelen Dateisystemen

Clusterfile ist ein paralleles Dateisystem. d.h., jede einzelne Datei ist potenziell auf mehrere Rechner im Bündel verteilt und kann daher echt parallel angesprochen werden. Auf den ersten Blick erscheint ein verteiltes Dateisystem als ein Spezialfall eines parallelen Dateisystems. Verteilte Dateisysteme sind allerdings zumeist auf nicht-parallele Anwendungen zugeschnitten, die weit weniger restriktive Anforderungen stellen; ihr Entwurf unterscheidet sich daher in der Regel recht deutlich vom dem paralleler Dateisysteme. Beispielsweise sind die Konsistenzanforderungen eines parallelen Dateisystems deutlich strikter als jene, die viele nicht-parallele, allgemeine Anwendungen erfordern. Dies belegen einschlägige Studien über Zugriffsmuster, nach denen der gemeinsame schreibende Zugriff auf Dateien bei nicht-parallelen Anwendungen selten, bei parallelen Anwendungen dagegen häufig erfolgt.

Entwurfsprobleme

Ein wichtiger Schritt eines Rechnerbündels in Richtung auf ein Single System Image besteht in der Schicht für kooperatives Caching. Unter Verwendung des von uns entwickelten einheitlichen Puffer-Cache hoffen wir, einen großen Performanz-Gewinn für solche Anwendungen zu erzielen, die auf eine Datei lesend zugreifen (beispielsweise beim Laden ausführbarer Dateien oder bei Web-Dienstgebern, wie bereits beschrieben). Diese Erwartung basiert auf der Tatsache, dass in einem Hochgeschwindigkeitsnetzwerk der Zugriff auf einen Dateiblock von einem entfernten Rechnerknoten aus deutlich schneller als das Lesen vom lokalen Plattenspeicher ist. Nichtsdestotrotz beabsichtigen wir genauso die Auswirkungen (speziell bei Schreibzugriffen) der Strategien zum kooperativen Caching auf die Geschwindigkeit eines parallelen Dateisystems zu untersuchen.

Ein weiteres Schlüsselproblem für den Entwurf besteht darin, welche Architektur wir für verteiltes Rechnen verwenden. Was den Treiber für entfernte Plattenspeicher betrifft, beabsichtigen wir unseren Entwurf eines verteilten Dateisystems beizubehalten, welches der dienstgeberlosen Philosophie (xFS) treu bleibt. Bei diesem Modell handeln die Parteien, die an der Kommunikation beteiligt sind, auf der Basis eines Peer-to-Peer-Protokolles, anstatt dem Dienstgeber-Dienstnehmer-Paradigma zu folgen. Dies hat sich als geeignet für das Erreichen einer besseren Performanz im Sinne von Skalierbarkeit und Verfügbarkeit und einer einfacheren Programmierung erwiesen. Derzeit verwendet Clusterfile noch eine Dienstgeber/Dienstnehmer-Architektur.

Mit dieser Betrachtungsweise des Rechnerbündels aus den zwei Blickwinkeln der Verteilung und des Parallelismus vor Augen planen wir eine gleichzeitige Entwicklung der beiden Typen von Systemen zu verfolgen. Zwar gibt es erhebliche Unterschiede in der Datenanordnung und den Strategien für den Datenzugriff zwischen den beiden Typen. Dennoch glauben wir, dass ein verteiltes Dateisystem nicht nur aus der vereinheitlichten Infrastruktur des Rechnerbündels, sondern auch aus den Erfahrungen mit dem Projekt Clusterfile einen Vorteil ziehen kann.

Teilziel D: Explizite Kontrolle der Ressourcen des Rechnerbündels

Einige der oben genannten Forschungsthemen unterstellen zu einem gewissen Grade die Fähigkeit der Anwendungen, ihre eigenen Strategien zu formulieren und den Betriebssystemkern anzuweisen, sich entsprechend zu verhalten. Wir bezeichnen dies als explizite Kontrolle der Ressourcen eines Rechnerbündels, wenngleich diese Mechanismen Teil von Systemen sind, die in der Betriebssystemliteratur unter der Bezeichnung erweiterbarer Kerne geläufig sind. Sowohl beim Projekt der skalierbaren Dienste wie auch dem eines verteilten/parallelen Dateisystems sollen diese Fähigkeiten dem Rechnerbündel-Betriebssystem hinzugefügt werden, wenngleich keiner dieser Pläne die Entwicklung eines erweiterbaren verteilten Betriebssystems vorsieht. Nichtsdestoweniger ist, wie man dem nachfolgenden Beispiel entnehmen kann, diese Fähigkeit erforderlich.

Laut wissenschaftlicher Studien über parallele Anwendungen ist beispielsweise in einem parallelen Dateisystem die Übereinstimmung zwischen Dateizugriffsmustern und physikalischer Datenanordnung auf den Platten entscheidend für E/A-Parallelismus und -Skalierbarkeit. Die explizite Kontrolle der Datenanordnung auf den Platten durch die Anwendung mag zu einer besseren Übereinstimmung führen und daher die Performanz erhöhen. Andererseits könnte ein Web-Dienstgeber, der sich der Datenlokalität bewusst ist, genauso gut den Kern anweisen, seine eigenen Strategien für kooperatives Caching anzuwenden und somit die Strategien des parallelen Dateisystems beeinflussen. Dies würde die Koexistenz zweier verschiedener Strategien für kooperatives Caching bedeuten, die für sich genommen konsistent und voneinander isoliert sind.

Vorläufig gehen beide Projekte an das Problem mit selbstgeschneiderten Ansätzen heran; ein sauberer Entwurf eines Betriebssystems jedoch erfordert ein spezialisiertes Modul, das mit diesen Problemen umgeht.

Arbeitsprogrammübersicht

Im Überblick ergibt sich die folgende Zusammenstellung über den erwarteten personellen Aufwand zur Erreichung der genannten Teilziele:

Teilziel geschätzte
Personen-Jahre
A Skalierbare Dienstgeber 1,50
B Vervollständigung der Schicht virtueller Ressourcen 1,00
C Verteilte/parallele Dateisysteme 1,00
D Explizite Kontrolle der Ressourcen 0,50

 Gesamt Teilprojekt T1
 

4,00

Page design & maintenance: Matthias Gimbel, Bernhard Haumacher, and Jürgen Reuter.
Last change Fri 07 May 2004 08:44:14 PM CEST.