Lastverteilung (Informatik)

mini|Diagramm zur Veranschaulichung der Benutzeranforderungen an ein Elasticsearch-Cluster, das durch einen Load Balancer verteilt wird. (Beispiel für Wikipedia). Mittels Lastverteilung () werden in der Informatik umfangreiche Berechnungen oder große Mengen von Anfragen auf mehrere parallel arbeitende Systeme verteilt mit dem Ziel, ihre gesamte Verarbeitung effizienter zu gestalten.

Sind die einzelnen Prozesse weitgehend unabhängig voneinander, so bietet sich die Architekturform des Computerclusters an, bei dem die Prozesse auf eine gewisse Anzahl gleichartiger Server (Serverfarm) verteilt werden. Häufig findet man diesen Ansatz bei größeren Web-Anwendungen mit vielen Benutzern.

Handelt es sich dagegen um einen einzigen, sehr aufwändigen Prozess, kann versucht werden, die Aufgabe zu splitten und abschließend die Ergebnisse zusammenzuführen, wie beispielsweise bei der Saldenbildung über eine sehr große Anzahl von Buchungen. Für solche Aufgabenstellungen eignen sich Server mit vielen Prozessorkernen besonders gut (Multicore-Architektur mit gemeinsam genutztem Arbeitsspeicher).

Multicore-Architekturen eignen sich auch gut für typische Mischlasten auf einem kleineren Anwendungsserver, wo beispielsweise Betriebssystem, Datenbank, Applikation und Webserver eine Fülle unterschiedlicher und meist kurz laufender Threads hervorbringen. Diese Lasten werden vom Scheduler des Systems auf die verfügbaren Kerne verteilt. Der Scheduler hat keine Kenntnis über die Komplexität der anstehenden Aufgaben, sondern entscheidet aufgrund von Prozess-Priorität, Auslastung und anderen Kenngrößen.

Lastverteilung ist ursprünglich das Ergebnis der Forschung im Bereich der Parallelrechner. Zwei Hauptansätze existieren nebeneinander: statische Algorithmen, die den Zustand der verschiedenen Maschinen nicht berücksichtigen, und dynamische Algorithmen, die öfters allgemeiner und effizienter sind, aber dafür einen anspruchsvollen Informationsaustausch zwischen den verschiedenen Recheneinheiten erfordern, was der Effizienz schaden kann.

Problemübersicht Ein Lastverteilungsalgorithmus versucht immer, ein bestimmtes Problem zu lösen. Unter anderen sollen die Art der zu lösenden Aufgaben, die algorithmische Komplexität, die Hardware-Architektur sowie die Fehlertoleranz berücksichtigt werden. Daher muss ein Kompromiss gefunden werden, um die anwendungsspezifischen Anforderungen bestmöglich zu erfüllen.

Art der Jobs Die Effizienz von Lastverteilungsalgorithmen hängt entscheidend von der Art der Jobs ab. Je mehr Informationen über die Aufgaben zum Zeitpunkt der Entscheidungsfindung verfügbar sind, desto größer ist daher das Optimierungspotenzial.

Größe Eine perfekte Kenntnis der Ausführungszeit jeder der Aufgaben erlaubt es, eine optimale Lastverteilung zu erreichen (siehe den Präfix-Summen-Algorithmus unten). Leider handelt es sich hierbei tatsächlich um einen idealisierten Fall. Die genaue Kenntnis der Ausführungszeit jeder Aufgabe ist eine extrem seltene Situation.

Aus diesem Grund gibt es verschiedene Techniken, um sich eine Vorstellung von den verschiedenen Ausführungszeiten zu machen. Zunächst einmal kann man in dem glücklichen Fall, dass es sich um Aufgaben von relativ homogener Größe handelt, davon ausgehen, dass jede von ihnen ungefähr die durchschnittliche Ausführungszeit erfordert. Wenn die Ausführungszeit hingegen sehr unregelmäßig ist, müssen subtilere Techniken verwendet werden. Eine Technik ist das Hinzufügen einiger Metadaten zu jeder Aufgabe. Abhängig von der bisherigen Ausführungszeit für ähnliche Metadaten können auf der Grundlage von Statistiken Rückschlüsse für eine zukünftige Aufgabe gezogen werden.

Schließlich kann die Anzahl der Aufgaben selbst von einiger Bedeutung sein.

Abhängigkeit In einigen Fällen hängen die Aufgaben voneinander ab. Diese gegenseitigen Abhängigkeitsrelationen können durch einen azyklisch orientierten Grafen veranschaulicht werden. Intuitiv können einige Aufgaben erst beginnen, wenn andere bereits abgeschlossen sind.

Unter der Annahme, dass die erforderliche Zeit für jede der Aufgaben im Voraus bekannt ist, muss eine optimale Ausführungsreihenfolge zur Minimierung der Gesamtausführungszeit führen. Obwohl dies ein NP-schweres Problem ist und daher schwer genau zu lösen sein kann, gibt es Scheduling-Algorithmen, die ehrenhafte Aufgabenverteilungen erzeugen.

Spaltbarkeit Ein weiteres Merkmal der Jobs, das einen großen Einfluss auf das Design des Lastverteilungsalgorithmus hat, ist ihre Fähigkeit, während der Ausführung in Teilaufgaben aufgeteilt zu werden. Der „Work-Stealing“ Algorithmus, den wir später vorstellen werden, nutzt diese Besonderheit.

Statische und Dynamische Algorithmen

Statische Algorithmen Ein Lastverteilungsalgorithmus wird als „statisch“ bezeichnet, wenn er den Zustand des Systems bei der Aufgabenverteilung nicht berücksichtigt. Unter Systemzustand verstehen wir hier die Auslastung (und manchmal sogar Überlastung) bestimmter Prozessoren. Stattdessen werden im Vorfeld Annahmen über das Gesamtsystem getroffen, wie z. B. die Ankunftszeiten und der Ressourcenbedarf der eingehenden Aufgaben. Darüber hinaus sind die Anzahl der Prozessoren, ihre jeweilige Leistung und Kommunikationsgeschwindigkeit bekannt. Es geht also darum, Aufgaben mit den Prozessoren so zu verbinden, dass eine bestimmte Leistungsfunktion minimiert wird. Der Trick liegt in der Gestaltung dieser Leistungsfunktion.

Die Techniken sind immer um einen Router herum zentralisiert, der die Lasten verteilt und die Optimierung der Funktion gewährleistet. Diese Minimierung kann Informationen in Bezug auf die zu verteilenden Aufgaben berücksichtigen und eine erwartete Ausführungszeit ableiten.

Der Vorteil von statischen Algorithmen ist, dass sie leicht zu implementieren und bei relativ regelmäßigen Aufgaben (wie der Verarbeitung von HTTP-Anfragen einer Website) äußerst effizient sind. Es gibt jedoch immer noch statistische Varianz in der Aufgabenverteilung, die zu einer Überlastung einiger Recheneinheiten führen kann.

Dynamische Algorithmen Im Gegensatz zu statischen Lastverteilungsalgorithmen berücksichtigen dynamische Algorithmen die aktuelle Last jeder der Recheneinheiten (auch Knoten genannt) im System. Bei diesem Ansatz können Aufgaben dynamisch von einem überlasteten Knoten zu einem unterlasteten Knoten verschoben werden, um eine schnellere Verarbeitung zu erhalten. Obwohl diese Algorithmen viel komplizierter zu entwerfen sind, können sie hervorragende Ergebnisse liefern, insbesondere wenn die Ausführungszeit von einer Aufgabe zur anderen stark variiert.

Beim dynamischen Lastverteilung kann die Architektur modularer sein, da es nicht zwingend erforderlich ist, einen speziellen Knoten für die Arbeitsverteilung zu haben. Wenn Aufgaben einem Prozessor entsprechend seinem Zustand zu einem bestimmten Zeitpunkt eindeutig zugeordnet werden, sprechen wir von einer eindeutigen Zuordnung. Wenn andererseits die Aufgaben entsprechend dem Zustand des Systems und seiner Entwicklung permanent neu verteilt werden können, spricht man von dynamischer Zuweisung. Offensichtlich ist ein Lastverteilungsalgorithmus, der zu viel Kommunikation erfordert, um seine Entscheidungen zu treffen, nicht wünschenswert, auf die Gefahr hin, die Lösung des Gesamtproblems zu verlangsamen. Der schlimmste Fall ist ein Ping-Pong-Spiel zwischen den Prozessoren, das zu einer unbegrenzten Blockierung der Lösung führt.

Hardware-Architektur

Heterogene Maschinen Parallele Rechner Infrastrukturen bestehen oft aus Einheiten unterschiedlicher Rechenleistung, die bei der Lastverteilung berücksichtigt werden sollten.

Beispielsweise können Einheiten mit geringerer Leistung Anfragen erhalten, die einen geringeren Berechnungsaufwand erfordern, oder, im Falle homogener oder unbekannter Anfragegrößen, weniger Anfragen erhalten als größere Einheiten.

Gemeinsamer und verteilter Speicher Parallelrechner werden oft in zwei große Kategorien unterteilt: solche, bei denen sich alle Prozessoren einen einzigen gemeinsamen Speicher teilen, auf dem sie parallel lesen und schreiben (PRAM-Modell), und solche, bei denen jede Recheneinheit über einen eigenen Speicher verfügt (Modell des verteilten Speichers) und Informationen durch Nachrichten mit den anderen Einheiten austauscht.

Bei Computern mit gemeinsamem Speicher verlangsamt die Verwaltung von Schreibkonflikten die individuelle Ausführungsgeschwindigkeit jeder einzelnen Recheneinheit erheblich. Sie können jedoch gut parallel arbeiten. Umgekehrt kann beim Nachrichtenaustausch jeder der Prozessoren mit voller Geschwindigkeit arbeiten. Andererseits sind beim Nachrichtenaustausch alle Prozessoren gezwungen, auf den Beginn der Kommunikationsphase durch die langsamsten Prozessoren zu warten.

In der Realität fallen nur wenige Systeme in genau eine der Kategorien. Im Allgemeinen verfügen die Prozessoren jeweils über einen internen Speicher, um die für die nächsten Berechnungen benötigten Daten zu speichern, und sind in aufeinanderfolgenden Clustern organisiert. Häufig werden diese Verarbeitungselemente dann durch verteilten Speicher und Nachrichtenaustausch koordiniert. Daher sollte der Lastverteilungsalgorithmus eindeutig an eine parallele Architektur angepasst werden. Andernfalls besteht die Gefahr, dass die Effizienz der parallelen Problemlösung stark beeinträchtigt wird.

Hierarchie Zur Anpassung an den oben dargestellten Hardware Strukturen gibt es zwei Hauptkategorien von Lastverteilungsalgorithmen. Einerseits werden die Aufgaben von einem „Master“ zugewiesen und von „Arbeitern“ ausgeführt (Master-Slave-Modell), die den Master über die Entwicklung ihrer Arbeit auf dem Laufenden halten. Der Master kann dann für die Zuweisung (und Neuzuweisung) der Arbeitslast verantwortlich sein, wenn der Algorithmus dynamisch (mit dynamischer Zuweisung) ist. Die Literatur spricht von der „Meister-Arbeiter“-Architektur. Umgekehrt kann die Steuerung auf die verschiedenen Knoten verteilt werden. Der Lastverteilungsalgorithmus wird dann auf jedem von ihnen ausgeführt, und die Verantwortung für die Zuweisung von Jobs (sowie gegebenenfalls für die Neuzuweisung und Aufteilung) wird geteilt. Die letztere Kategorie setzt einen dynamischen Lastverteilungsalgorithmus voraus.

Auch hier gilt: Da das Design jedes Lastverteilungsalgorithmus einzigartig ist, muss die vorherige Unterscheidung eingeschränkt werden. So ist auch eine Zwischenstrategie möglich, z. B. mit „Master“-Knoten für jeden Sub-Cluster, die ihrerseits einem globalen „Master“ unterliegen. Es gibt auch Organisationen mit mehreren Ebenen, mit einem Wechsel zwischen Master-Slave- und verteilten Kontrollstrategien. Letztere Strategien werden schnell komplex und sind selten anzutreffen. Entwickler bevorzugen leichter kontrollierbare Algorithmen.

Skalierbarkeit Im Rahmen von Algorithmen, die sehr langfristig laufen (Server, Cloud …), entwickelt sich die Computerarchitektur im Laufe der Zeit weiter. Es ist jedoch vorzuziehen, nicht jedes Mal einen neuen Algorithmus entwerfen zu müssen.

Ein weiterer wichtiger Parameter eines Lastverteilungsalgorithmus ist daher seine Fähigkeit, sich an eine sich entwickelnde Hardware-Architektur anzupassen. Das nennt man die Skalierbarkeit des Algorithmus. Ein Algorithmus soll auch für einen Eingabeparameter skalierbar sein, wenn seine Leistung relativ unabhängig von der Größe dieses Parameters bleibt.

Wenn der Algorithmus in der Lage ist, sich an eine unterschiedliche Anzahl von Prozessoren anzupassen, die Anzahl der Prozessoren jedoch vor der Ausführung festgelegt werden muss, wird er als „formbar“ () bezeichnet. Wenn der Algorithmus andererseits in der Lage ist, mit einer schwankenden Anzahl von Prozessoren während seiner Ausführung umzugehen, gilt der Algorithmus als „schmiedbar“ (). Die meisten Lastverteilungsalgorithmen sind zumindest formbar.

Fehlertoleranz