Teilprojekt A3
From GRK-Wiki
zum übergeordneten Forschungsbereich
Contents |
Management replizierter Daten und Dienste
Die Replizierung von Daten und Diensten ist eine der wichtigsten Methoden zur Erhöhung der Verfügbarkeit und Effizienz in dynamischen Umgebungen wie den selbstorganisierenden Netzen eines Katastrophenmanagementsystems. Dabei treten komplexe Fragestellungen zur Platzierung, Konsistenz und Anzahl der Replikate, zum transparenten Zugriff, zur Attributierung und Suche nach Replikaten durch verteilte Kataloge, sowie zum effizienten Datentransfer auf. Diese Aufgaben erhalten einen zusätzlichen Schwierigkeitsgrad durch die Anforderung der Skalierbarkeit, die eine unabdingbare Eigenschaft in dem betrachteten Anwendungsszenario darstellt. Ein zentraler Aspekt dieses Dissertationsthemas ist die Entwicklung effizienter Methoden für die verteilte Indizierung und für den transparenten Zugriff auf Replikate, wobei wir ein schwaches Konsistenzmodell mit log-basiertem Update [1] unterstellen. Es werden Ansätze aus den P2P-Netzen, wie z. B. verteilte Hash-Tabellen oder Varianten der Skip-Listen übernommen und für spezifische Anforderungen wie komplexe Nachfragen erweitert. Zusätzlich sollen die Verfügbarkeit von Katalogen sowie Lastausgleichsverfahren modelliert und Gütegarantien für den Replikazugriff untersucht werden.
Stand des Wissens
Kernpunkt des Managements von Replikaten ist ein zweistufig ablaufender Dateizugriff. Zunächst werden Replika-Kataloge befragt, auf welchen Rechnern Kopien der gewünschten Datei abgelegt sind. Danach wird versucht, auf diese Kopien zuzugreifen. In den derzeitigen (Grid-) Systemen erfolgt eine Kataloganfrage über hierarchische Dienste wie z. B. RLS [2], die nicht skalieren und nur unzureichend ausfalltolerant sind [3], [4]. Demgegenüber existieren in der Domäne der P2P-Systeme skalierbare und fehlertolerante Lösungen für die verteilte Indizierung und Suche von Replikaten, die man in unstrukturierte [5] und strukturierte [6], [7] Ansätze unterteilt. Der letztere Bereich bietet überwiegend Lösungen an, die auf Basis von verteilten Hash-Tabellen arbeiten. Obwohl wesentlich effizienter als die unstrukturierten Methoden weisen diese Ansätze Einschränkungen in Bezug auf den Grad der Dynamik von zugrunde liegenden Infrastrukturen auf und reduzieren die Flexibilität der Suche. Insbesondere sind Probleme der Verteilungsschemata und eine geeignete Ausdrucksmächtigkeit der Suchanfragen weitgehend ungelöst. Weitere relevante Arbeiten betreffen den Bereich der Adaptivität in verteilten, heterogenen Systemen [8], die in der dynamischen Umgebung des Anwendungsszenarios zur Zuverlässigkeit und Leistung des Replika-Managementsystems beitragen können.
Vorarbeiten der beteiligten Wissenschaftler
In der Arbeitsgruppe Parallele und Verteilte Systeme (A. Reinefeld) sind Modelle entwickelt worden, die die Verfügbarkeiten von Replikaten in dem o. g. zweistufigen Prozess des Replika-Zugriffs beschreiben [9]. Das zugrunde liegende Systemkonzept setzt eine Verteilung der Kataloge als P2P-ähnliche Struktur voraus und berücksichtigt wichtige Architekturparameter, wie z. B. die Knoten- und Katalogzuverlässigkeit, das Konsistenzmodell zwischen Katalogen und die Anzahl der Kataloge sowie Replikaten-Anzahl im System. Im Gegensatz zu anderen Modellen unterscheidet sich dieser Ansatz hinsichtlich einer lokalen und einer globalen Sichtweise auf das System. Während die lokale Sicht von einem sich selbst überwachenden System übernommen werden kann, um eine vorgegebene Mindestverfügbarkeit zu gewährleisten, dient die globale Sicht einem zentralen Systemadministrator, den Bedarf an Replikaten und somit die benötigte Speicherkapazität im Gesamtsystem abschätzen zu können. Ein weiterer Beitrag [10] der Arbeitsgruppe Reinefeld betrifft eine Erweiterung des Konzepts verteilter Hash-Tabellen, mit dem auch Bereichsabfragen und SQL-ähnliche Konstrukte effizient umgesetzt werden können. Dieser Ansatz bietet das Grundgerüst für komplexe Suchanfragen in P2P-Netzen – eines der größten Mankos heutiger verteilter Hash-Tabellen. Auf der praktischen Seite hat die Arbeitsgruppe mit dem „ZIB-DMS“ [4], [11] ein verteiltes Metadaten- und Replika-Managementsystem entwickelt, das den Nutzern einen transparenten Zugriff auf attributierte Dateireplikate ermöglicht. Neben einer verteilten, skalierbaren Indizierung der Replikate und Metadaten ermöglicht das System die Suche nach Kombinationen von Attributwerten, die Vererbung der Attribute sowie virtuelle Verzeichnisse, die von physikalischen Speicherungsstrukturen abstrahieren. M. Malek besitzt langjährige Erfahrungen auf dem Gebiet der Modellierung zuverlässiger Systeme bei IBM und Siemens und betreute Diplomarbeiten und Dissertationen zu dieser Thematik [12], [13], [14], [15].
Geplante Arbeiten
Die geplanten Arbeiten lassen sich in zwei Bereiche untergliedern. Der erste Bereich betrifft die Modellierung der Zuverlässigkeit und die Suche in verteilten Replika-Katalogen. Dabei sollen Aspekte des effizienten Lastausgleichs in Replika-Katalogen, insbesondere im Kontext der dynamischen, selbstorganisierenden Netze des Anwendungsszenarios untersucht werden. Es sind des Weiteren Mechanismen für die effiziente Durchführung komplexer Anfragen zu entwickeln. Das zweite Themengebiet umfasst den transparenten Zugriff auf die Replikate und deren Konsistenzsicherung. Hierzu sind die Zuverlässigkeit zu modellieren und Methoden zum sicheren Auffinden von Replikaten zu untersuchen. Darüber hinaus soll die Platzierung von Replikaten in Abhängigkeit von der Dynamik der zugrunde liegenden Netze unter Einbeziehung der Lokalität untersucht werden.
Referenzen
[1] F. Hupfeld: Log-Structured Storage for Efficient Weakly-Connected Replication. International Conference on Distributed Computing Systems (ICDCS) Workshops, Tokyo, March 2004.
[2] A. Chervenak, E. Deelman at al.: Giggle: A Framework for Constructing Scalable Replica Location Services. Proceedings of Supercomputing 2002 (SC2002), 2002.
[3] A. Iamnitchi, I. Foster: On Fully Decentralized Resource Discovery in Grid Environments. International Workshop on Grid Computing, Denver, Colorado, 2001.
[4] A. Reinefeld, F. Schintke, T. Schütt: Scalable and Self-Optimizing Data Grids. In: Yuen Chung Kwong (ed.), Annual Review of Scalable Computing, vol. 6, Singapore University Press, Chapter 2, pp. 30 - 60, 2004.
[5] I. Clarke, O. Sandberg, B. Wiley, T. Hong. Freenet: Adistributed anonymous information storage and retrieval system. ICSI Workshop on Design Issuesin Anonymity and Unobservability, Berkeley, CA, 2000.
[6] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan: Chord- A scalable peer-to-peer lookup service for Internet applications. ACM SIGCOMM ‘01, San Diego, CA, USA, 2001.
[7] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker: A Scalable Content-Addressable Network. ACM SIGCOMM ‘01, San Diego, CA, USA, 2001.
[8] A. Andrzejak, A. Reinefeld, F. Schintke, T. Schütt: On Adaptability in Grid Systems. Dagstuhl Seminar 04451 “Next Generation Grids”, 2005, to appear in Springer LNCS.
[9] F. Schintke, A. Reinefeld: Modelling Replica Availability in Large Data Grids. Journal of Grid Computing (2), Kluwer Acad. Publisher, 2003.
[10] T. Schütt, F. Schintke, A. Reinefeld: Data Lookup in Peer-to-Peer Systems without Distributed Hash Tables. ZIB Technical Report, Dec. 2004.
[11] A. Reinefeld, F. Schintke: Concepts and Technologies for a Worldwide Grid Infrastructure. Euro-Par 2002 Parallel Processing, Springer LNCS 2400, pp 62-71, 2002.
[12] V. Cherkassky, M. Malek: Reliability and Fail-softness Analysis of Multistage Interconnection Networks. IEEE Transactions on Reliability, R-34 (5), pp. 524-528, December 1985.
[13] V. Cherkassky, M. Malek: Partitioning and Permuting Properties of CC-Banyan Networks. IEEE Transactions on Computers, C-38 (2), pp. 274-278, February 1989.
[14] A. M. Johnson, M. Malek: Survey of Software Tools for Evaluating Reliability, Availability and Serviceability. ACM Computing Surveys, 20 (4), pp. 227-269, December 1988; translated and reprinted in Japanese, Kyoritsu Shuppan Co., Ltd., 1990.
[15] B. L. Menezes, A. M. Johnson, R. M. Jenevein (Jr.), M. Malek, K. H. Yau: Fault Impact and Fault Tolerance in Multiprocessor Interconnection Networks. Quality and Reliability Engineering International, Vol. 8, pp. 485-500, 1992.
