Teilprojekt C1
From GRK-Wiki
zum übergeordneten Forschungsbereich
Contents |
Konzepte, Modelle und Algorithmen zur Behandlung der dynamischen Verfügbarkeit von Ressourcen
Auf Grund der hohen Flexibilität und der Dynamik der verteilten Netzinfrastruktur bedarf es zusätzlicher Konzepte und Strukturen, die eine zuverlässige und von der Anwendung geforderte Verfügbarkeit von Ressourcen sichert. Ist beispielsweise der Ausfall eines Netzknotens oder gar der Fall einer Netzwerkpartitionierung voraussehbar, so sollten entsprechend der durch die Anwendung festgelegten Anforderungen geeignete Maßnahmen möglich sein, die die Verfügbarkeit von Daten und Diensten auch nach diesen Fehlern sicherstellen können. So könnte im skizzierten Falle eine (einfache) Replikation von Daten und Prozessen erfolgen, die aber zu einer ineffizienten Nutzung der sowieso schon beschränkt vorhandenen Möglichkeiten führen würde. Damit ergibt sich die Notwendigkeit, den Trade-off zwischen (statisch oder dynamisch spezifizierten) Ressourcenanforderungen und dem damit verbundenen Aufwand zur Sicherstellung durch geeignete Verfahren in Einklang zu bringen. Dies gilt insbesondere für die Bereitstellung von Daten mit einem – möglicherweise vordefinierten – Verfügbarkeitsgrad, der zu einer mehr oder weniger aufwändigen Replikation führen kann. Welche Bewertungsmaßstäbe und welche Möglichkeiten die vorhandene Netzwerkstruktur mit ihren Eigenschaften bieten, sind Gegenstand der Untersuchungen und Entwicklungen. Darüber hinaus ist sicherzustellen, dass neben den Ressourcen auch die spezifizierten Prozesse auf dem vorhandenen Netzwerk trotz möglicher Veränderung ausgeführt werden können. Dabei ist in diesem Dissertationsvorhaben genau zu untersuchen, welche Art der Veränderungen mit welchem Aufwand einer adaptiven Anpassung verbunden ist. Insbesondere soll durch Ergebnisse dieses Vorhabens deutlich werden, welche vorbeugenden Maßnahmen eine sichere Beendigung der Ausführung mit welchem Aufwand sicherstellen können.
Stand des Wissens
Datenreplikation und Fehlerbehandlung in verteilten Datenbanksystemen sind seit Jahren Gegenstand der Forschung. Hier haben entscheidende Arbeiten im Transaktionenbereich Protokolle der Synchronisation (2-Phasen- und 3-Phasen-Commit-Protokoll) entwickelt [1], [2]. Grundlegende theoretische Betrachtungen haben bereits vor ca. 20 Jahren zu Erkenntnissen im Bereich fehlertoleranter, verteilter Systeme geführt, die unter dem Namen Byzantine Agreement in die Literatur Eingang gefunden haben [3]. Wie die Arbeiten von J.- C. Freytag u. a. schon frühzeitig in diesem Bereich zeigten, ist nicht nur die Datenbank bei Ausfall bzw. Fehlern betroffen, sondern auch die jeweilige Anwendung, die somit ebenfalls einer Fehlererholung unterliegen sollte. Weitere Arbeiten zum file sharing bzw. zum Austausch von Daten (Replikation) zur Sicherung der Verfügbarkeit sind insbesondere mit leistungsfähigeren Netzwerken in den Mittelpunkt der Betrachtungen gerückt [4].
Vorarbeiten der beteiligten Wissenschaftler
J.- C. Freytag arbeitet seit mehr als 20 Jahren im Bereich Anfragebearbeitung und -optimierung für Datenbank- und Informationssysteme [5][6][7]. Relevant für dieses Vorhaben sind insbesondere die in [8] entwickelten Ansätze zur Fehlererholung in Datenbankanwendungen und die in [9] entwickelten flexiblen Kommunikationsebenen für parallele Datenbanksysteme. Wie in [10] gezeigt, ist die Einbeziehung semantischen Wissens für die geplanten Arbeiten ebenfalls von Bedeutung. Ein von A. Reinefeld u. a. entwickeltes analytisches Modell [11] beschreibt, wie viele Replikate erzeugt werden müssen, um das Gesamtsystem bei drohenden Ausfällen funktionsfähig zu halten. Die Entscheidung, wie viele Replikate anzulegen sind, erfolgt auf der Grundlage lokaler Information, was ggf. autonome Regelkreise erfordert, die in [12] beschrieben werden.
Geplante Arbeiten
In diesem Teilprojekt sollen Algorithmen, Bewertungsverfahren und Methoden entwickelt werden, die die von der Anwendung spezifizierten Ressourcen-Anforderungen trotz zugrunde liegender Dynamik des Netzes, die zu topologischen Veränderungen aber auch zu Ausfällen führen kann, zur Verfügung stellt. Dabei sollen sowohl statische als auch dynamische bzw. adaptive Verfahren untersucht und entwickelt werden, die neben Daten als wichtigster Ressource auch Dienste mit in die Betrachtungen einbeziehen. Methoden der Replikation und Caching stehen im Vordergrund des Interesses, wobei aber auch Konsensusverfahren unter Berücksichtigung böswilliger Teilnehmer weiterentwickelt und untersucht werden sollen. Die beschränkte Leistungsfähigkeit bzw. Heterogenität der im Netz vorhandenen Knoten muss bei der Nutzung in der statischen bzw. adaptiven Planung mit berücksichtigt werden.
Referenzen
[1] M. L. Liu, D. Agrawal, A. E. Abbadi: The Performance of Two-phase Commit Protocols in the Presence of Site Failures. In: Proc. of FTCS 1994, pp 234-243, 1994.
[2] D. Skeen: A quorum-based Commit Protocol. In: Proc. of 6th Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 69-80, 1982.
[3] H. Garcia-Molina, F. Pittelli, S. Davidson: Is Byzantine Agreement Useful in a Distributed Database? In Proc. of PODS 1984, pp. 61-69, 1984.
[4] N. Daswani, H. Garcia-Molina, B. Yang: Open Problems in Data-Sharing Peer-to-Peer Systems. ICDT 2003: 1-15, 2003.
[5] J.- C. Freytag, D. Maier, G. Vossen: Query Processing for Advanced Database Systems. In: Selected Contributions from a Workshop on Query Processing in Object-Oriented, Complex-Object and Nested Relation Databases, Morgan Kaufmann, 1994.
[6] D. Asonov, J.- C. Freytag: Almost Optimal Private Information Retrieval. Privacy Enhancing Technologies 2002, pp. 209-223, 2002.
[7] F. Naumann, U. Leser, J.-C. Freytag: Quality-driven Integration of Heterogenous Information Systems. In: Proc. of. VLDB 1999, pp. 447-458, 1999.
[8] J.- C. Freytag, F. Cristian, B. Kähler: Masking System Crashes in Database Application Programs. In: VLDB 1987, pp. 407-416, 1987.
[9] M. Stillger, D. Scheffner, J.-C. Freytag: A Communication Infrastructure for a Distributed RDBMS (Research Note). Euro-Par 2000, pp. 445-450, 2000.
[10] C. Ben Necib, J. - C. Freytag: Using Ontologies for Database Query Reformulation. In: Proc. of ADBIS (Local Proceedings), 2004.
[11] F. Schintke, A. Reinefeld: Modelling Replica Availability in Large Data Grids. Journal of Grid Computing (2), Kluwer Acad. Publisher, 2003.
[12] A. Reinefeld, F. Schintke, T. Schütt: Scalable and Self-Optimizing Data Grids. In: Y. C. Kwong (ed.), Annual Review of Scalable Computing, vol. 6, Singapore University Press, Chapter 2, pp. 30 - 60, 2004.
