alle News

Beiträge zur dynamischen Lastbalancierung in parallelen Datenbanksystemen

Diese Arbeit untersucht ausgewählte Problemstellungen der dynamischen Lastbalancierung in parallelen Datenbanksystemen (PDBS). Betrachtet wird die möglichst gleichmäßige Verteilung von Arbeitslasten zur Laufzeit komplexer analytischer Anfragen. Das Hauptproblem besteht in der eingeschränkten Vorhersagbarkeit sogenannter Skew-Effekte, die verschiedene Arten von Lastungleichgewichten beschreiben und deren Bekämpfung der Schlüssel zur gleichmäßigen Verteilung und effizienten Abarbeitung von Arbeitslasten ist. In der Arbeit werden sowohl empirische als auch analytische Untersuchungsmethoden angewandt. Der Schwerpunkt der Untersuchung liegt dabei auf sogenannten Shared-Disk-Systemen, die sich durch eine gemeinsame Plattenspeicheranbindung auszeichnen; diese Architekturen haben in früheren Forschungen vergleichsweise wenig Beachtung gefunden. Über die eigentliche Lastverteilung hinaus betrachtet die Arbeit ausgewählte Aspekte der dynamischen Allokation von Zwischenergebnissen komplexer Anfragen. Nach einer allgemeinen Einführung sowie der Positionsbestimmung der Arbeit innerhalb des Sachgebiets wird zunächst eine theoretische Analyse der Begriffe Skew und Lastbalancierung vorgenommen. Sowohl für die zahlreichen existierenden Lastbalancierungsverfahren als auch für die Vielfalt unterschiedlicher Skew-Effekte wird jeweils eine Klassifikation entwickelt. Die Gegenüberstellung beider Begriffswelten ermöglicht grundsätzliche Aussagen über die Eignung verschiedener Lastverteilungsansätze zur Bekämpfung bestimmter Skew-Formen. Unter anderem wird festgestellt, daß hochdynamische, laufzeitbasierte Balancierungsansätze nicht nur zu einer gleichmäßigeren Lastverteilung führen, sondern dabei sogar eine geringere Komplexität als typische statische Verfahren besitzen. Auf dieser Grundlage wird für die empirischen Untersuchungen ein neuer Lastbalancierungsansatz entwickelt: Das sogenannte bedarfsorientierte Scheduling (On-demand Scheduling, ODS) weist eine wesentlich höhere Dynamik auf als die derzeit vorherrschenden prädiktiven Algorithmen. Es verzichtet auf eine umfassende Vorausplanung von Anfragen und macht statt dessen die tatsächliche Verarbeitungsgeschwindigkeit zur Grundlage der Lastverteilung. Zum Vergleich des neuen Ansatzes mit einem herkömmlichen Verfahren wird ein Simulationssystem für PDBS verwendet, in dem neue Datenallokations- und Lastbalancierungsmethoden implementiert, erprobt und bewertet werden können. Für die Anwendung von ODS zur parallelen Join-Verarbeitung belegt es signifikante Vorteile vor allem im Mehrbenutzerbetrieb. Hier eignen sich bedarfsorientierte Verfahren wesentlich besser zur Korrektur unerwarteter Lastungleichgewichte als prädiktive oder reaktive Ansätze. ODS wird daher zur Basis weiterer Entwicklungen gemacht. Als Ergänzung der Join-Verarbeitung wird ein allgemeines Allokationsschema für Zwischenergebnisse umfangreicher mehrstufiger Anfragen vorgeschlagen. Mittels einer mathematischen Analyse wird dazu ein optimaler Verteilgrad bestimmt, mit dem ein möglichst konfliktarmer Zugriff auf die Daten möglich wird. Wichtigstes Ergebnis dieser Untersuchung ist die Feststellung, daß selbst solche Datenmengen, die auf einem einzelnen Prozessorknoten weiterverarbeitet werden, über mehrere Plattenspeicher verteilt werden sollten. Der Nutzen des parallelen Lesezugriffs übersteigt in allen realistischen Fällen die Belastung durch vermehrte Plattenzugriffskonflikte. Die letzte Studie überträgt das bedarfsorientierte Scheduling aus klassischen relationalen DBS in eine Data-Warehouse-Umgebung. Aufbauend auf einer ebenfalls neuentwickelten Allokationsmethode werden mehrere Varianten des ODS-Verfahrens an verschiedenen Anfragetypen simulativ erprobt. Hierbei wird eine Strategie ermittelt, die für alle Lastarten nahezu optimale Resultate liefert, indem sie die Balancierung von Prozessor- und Plattenauslastungen gegeneinander abwägt. Damit erübrigt sich eine aufwendige und fehleranfällige Analyse des Lastprofils zur Auswahl eines optimalen Spezialverfahrens. Das Risiko extrem hoher Antwortzeiten für falsch klassifizierte Anfragen wird ohne nennenswerte Leistungsverluste vermieden. Die in der Arbeit präsentierten Lösungsansätze lassen sich auf zahlreiche unterschiedliche Systemarchitekturen, Datenmodelle und Arbeitslasten verallgemeinern.

Teilen auf