16 Einführung in Parallele DBS
16.1 Speedup und Scaleup
Speedup ist ein allgemeines Maß zur Bestimmung, in welchem Umfang die Leistungsfähigkeit von Computersystemen durch eine bestimmte Optimierung verbessert wird [HP90]. Üblicherweise wird Speedup mit Hinblick auf die Verkürzung von Antwortzeiten verwendet. Mit dem Antwortzeit-Speedup kann insbesondere die Effektivität einer Intra-Transaktionsparallelisierung bestimmt werden, indem festgestellt wird, in welchem Maß sich die Antwortzeit einer bestimmten Transaktion bzw. Operation durch Parallelisierung verbessert hat. Dabei gilt:
Abb. 16-1 zeigt, welche Verlaufsformen für den Antwortzeit-Speedup unterschieden werden können. Idealerweise wird bei n Prozessoren ein Speedup-Wert von n erzielt. Bei einem linearen Antwortzeit-Speedup kann die Antwortzeit auch proportional zur Prozessoranzahl verbessert werden, jedoch i.a. auf einem geringeren Niveau[68]. Typischerweise läßt sich jedoch die Antwortzeit nur bis zu einer bestimmten Prozessoranzahl verkürzen. Eine weitere Erhöhung der Prozessorzahl führt dann ggf. zu einer Reduzierung des Speedups, also einer Zunahme der Antwortzeit.
Abb. 16-1: Idealer, linearer und typischer Antwortzeit-Speedup
Die suboptimale Speedup-Entwicklung basiert auf mehreren Ursachen. Zunächst ist der maximal mögliche Speedup durch den Anteil einer Transaktion bzw. Operation begrenzt, der überhaupt parallelisierbar ist (begrenzte inhärente Parallelität). Besteht zum Beispiel die Antwortzeit einer Transaktion nur zu 5% aus nicht-parallelisierbaren (sequentiellen) Verarbeitungsanteilen, so ist der maximal möglich Speedup auf 20 beschränkt, unabhängig davon, wieviele Prozessoren eingesetzt werden. Diesen Zusammenhang verdeutlicht Amdahls Gesetz, welches den Speedup berechnet, wenn nur ein bestimmter Antwortzeitanteil durch eine Optimierung verkürzt werden kann [HP90]:
Desweiteren sind es vor allem folgende Faktoren, die den Antwortzeit-Speedup und damit die Skalierbarkeit einer Anwendung beeinträchtigen können [DG92]:
- Startup- und Terminierungskosten
Das Starten und Beenden mehrerer Teiloperationen in verschiedenen Prozessen/ Rechnern verursacht einen Overhead, der mit dem Parallelitätsgrad zunimmt. Da umgekehrt die pro Teiloperation zu verrichtende Nutzarbeit (z.B. Anzahl zu verarbeitender Sätze) sinkt, vermindert sich der relative Gewinn einer Parallelisierung mit wachsendem Parallelitätsgrad.
- Interferenz
Die Erhöhung der Prozeßanzahl führt zu verstärkten Wartezeiten auf gemeinsam benutzten Systemressourcen. Vor allem der durch die Parallelisierung eingeführte Kommunikations-Overhead kann sich negativ bemerkbar machen, insbesondere im Mehrbenutzerbetrieb (Inter-Transaktionsparallelität). Neben Wartezeiten auf physischen Ressourcen (CPU, Hauptspeicher, Platten, etc.) kann es auch verstärkt zu Sperrkonflikten zwischen unabhängigen Transaktionen kommen.
- Skew (Varianz der Ausführungszeiten)
Die langsamste Teiloperation bestimmt die Bearbeitungszeit einer parallelisierten Operation. Varianzen in den Ausführungszeiten, z.B. aufgrund ungleichmäßiger Daten- oder Lastverteilung oder Sperrkonflikten, führen daher zu Speedup-Einbußen. Das Skew-Problem nimmt i.a. auch mit wachsendem Parallelitätsgrad (Rechneranzahl) zu und beschränkt daher die Skalierbarkeit.
Der Speedup bestimmt den Einfluß der Prozessoranzahl auf eine konstante Problemgröße, nämlich die Ausführung einer bestimmten Transaktion bzw. Operation auf einer Datenbank fester Größe. Dagegen soll bei der Scaleup-Metrik die Problemgröße, hier die DB-Größe, linear mit der Prozessoranzahl erhöht werden [DG92]. Dabei kann zwischen Antwortzeit- und Durchsatz-Scaleup unterschieden werden. Der Antwortzeit-Scaleup (batch scaleup) bestimmt die Antwortzeitveränderung bei Einsatz von n Rechnern und n-facher Datenbankgröße verglichen mit dem 1-Rechner-Fall. Dabei soll im Mehrrechnerfall trotz des höheren Datenvolumens aufgrund der Parallelisierung einer Operation möglichst die gleiche Antwortzeit wie bei einem Rechner erreicht werden (Antwortzeit-Scaleup = 1). Der Durchsatz-Scaleup bestimmt das Verhältnis zwischen der Transaktionsrate auf n Rechnern (auf einer n-fach großen Datenbank) gegenüber der Transaktionsrate auf einem Rechner. Dabei sollte idealerweise der Scaleup-Wert n erreicht werden (lineares Durchsatzwachstum). In OLTP-Benchmarks des TPC (Transaction Processing Performance Council) wird die Skalierungsregel für die DB-Größe bei der Bestimmung der Transaktionsraten verlangt [Gr93].
[68] In bestimmten Fällen ist jedoch ein super-linearer Speedup erreichbar, wobei die Antwortzeit bei n Prozessoren um mehr als den Faktor n verbessert wird. Dies ist z.B. durch E/A-Einsparungen möglich, die darauf basieren, daß die Gesamt- Hauptspeicherkapazität mit der Prozessorzahl wächst, während die DB-Größe gleich bleibt.