Optimierung der Aufgabenverteilung und Jobplanung in verteilten Systemen

Die Planung ist wichtig, wenn es um Big Data und Hochleistungsrechnen geht. In diesem Setup laufen Jobs auf vielen Servern. Jeder Job besteht normalerweise aus vielen Aufgaben, die Zugang zu bestimmten Daten benötigen, die möglicherweise auf verschiedenen Servern gespeichert sind. Zu wissen, wo die Daten gespeichert sind, hilft, die Aufgaben den richtigen Servern zuzuweisen, was entscheidend für die Effizienz ist. Dieses Papier untersucht, wie man Aufgaben am besten den Servern zuweist, besonders wenn Jobs nacheinander eintreffen.

#Problemübersicht

Wenn Jobs online ankommen, bestehen sie aus mehreren unabhängigen Aufgaben. Jede Aufgabe benötigt ein bestimmtes Stück Daten, um daran zu arbeiten, und diese Daten sind in Häppchen auf verschiedene Server verteilt. Ziel ist es, die Zeit zu minimieren, die benötigt wird, um alle Aufgaben eines Jobs abzuschliessen, von dem Moment an, in dem der Job ankommt, bis alle Aufgaben abgeschlossen sind.

Das Planungsproblem hat zwei Hauptteile: das Zuweisen von Aufgaben zu Servern und die Entscheidung über die Reihenfolge, in der die Aufgaben abgeschlossen werden. Die Zuweisung von Aufgaben bedeutet, zu entscheiden, welche Aufgaben an welche Server gehen, während die Umordnung von Jobs bedeutet, die Reihenfolge zu bestimmen, in der die Aufgaben ausgeführt werden.

#Aufgaben-Zuweisung

Die Aufgaben-Zuweisung kann man sich wie das Verbinden zweier Gruppen vorstellen: Aufgaben und Server. Aufgaben, die zusammen bearbeitet werden können, können basierend auf den Servern, die die benötigten Daten haben, gruppiert werden. Ziel ist es, sicherzustellen, dass die Aufgaben so zugewiesen werden, dass die Jobabschlüsse schneller erfolgen.

#Job-Ummodulierung

Die Job-Ummodulierung konzentriert sich darauf, die Reihenfolge zu ändern, in der Aufgaben verarbeitet werden. Durch die Änderung der Reihenfolge der Aufgabenausführung können wir auch die Gesamtabschlusszeiten verbessern. Das wird besonders wichtig, wenn mehrere Aufgaben darauf warten, ausgeführt zu werden.

#Frühere Arbeiten

Frühere Studien haben die Aufgaben-Zuweisung und das Job-Planen separat oder zusammen betrachtet. Einige Methoden haben sich auf die Planung basierend auf geschätzten Abschlusszeiten konzentriert, während andere die Fairness bei der Ressourcenverteilung untersucht haben. Allerdings haben nicht alle die Situation berücksichtigt, in der Daten auf mehreren Servern gespeichert sind, was das Problem zu sehr vereinfacht.

Einige Studien haben die Aufgaben-Zuweisung im Kontext des Netzwerkflusses untersucht, wo die Zuteilung von Aufgaben wie das Lösen eines Maximumflussproblems behandelt wird. Andere Ansätze haben keine tiefgehende Leistungsanalyse ihrer Methoden geliefert.

#Unser Ansatz

Unsere Arbeit beschäftigt sich hauptsächlich mit der Zuweisung von Aufgaben unter Berücksichtigung der Datenlokalität. Das geschieht in Echtzeit, sobald die Jobs ankommen. Wir wollen die Zeit minimieren, die benötigt wird, um die Aufgaben in einem Job abzuschliessen, besonders wenn wir keine vorherige Kenntnis über zukünftige Jobs haben.

#Szenarien

Wir betrachten in unserer Analyse zwei Szenarien:

1. Das erste ist, wenn Aufgaben nach dem Prinzip "Wer zuerst kommt, mahlt zuerst" verarbeitet werden. Hier liegt der Fokus darauf, die Server-Nutzungszeiten so gut wie möglich auszugleichen.
2. Das zweite Szenario erlaubt es, Aufgaben zu priorisieren und umzuordnen, was den Abschluss von Jobs weiter beschleunigen kann.

#Aufgaben-Zuweisung als Problem

Wir modellieren die Herausforderung der Aufgaben-Zuweisung als mathematisches Problem. Wir erstellen einen Graphen mit zwei Mengen von Knoten: eine für Aufgaben und eine für Server. Unser Ziel ist es, die Aufgaben effizient mit den richtigen Servern zu verbinden, wobei wir im Auge behalten, wie beschäftigt jeder Server ist, bevor der neue Job ankommt.

Um herauszufinden, wie man Aufgaben zuweist, betrachten wir, wie lange es dauern würde, alle Aufgaben zu verarbeiten, und finden dann Wege, diese Last über die Server auszugleichen.

#Entwicklung von Algorithmen

Wir führen neue Algorithmen ein, um dieses Problem anzugehen.

1. Optimal Balanced Task Assignment (OBTA) - Dieser Algorithmus schränkt effizient die potenziellen Lösungen ein, um die beste Möglichkeit zu finden, Aufgaben zuzuweisen.

2. Water-Filling Algorithm (WF) - Dies ist eine ungefähre Methode, die Aufgaben gruppenweise den Servern zuweist. Ziel ist es, die Nutzungszeiten der Server ausgewogen zu halten.

3. Replica-Deletion (RD) - Diese Heuristik entfernt unnötige Aufgaben-Duplikate von Servern, um die Last ausgewogen zu halten, während die Aufgaben dennoch effektiv zugewiesen werden.

#Job-Ummodulierung-Algorithmen

Wir schauen uns auch eine erweiterte Version unserer Algorithmen an, die eine Job-Ummodulierung erlaubt. Diese Methode nutzt eine Strategie, die ähnlich ist wie die Priorisierung von Aufgaben, basierend darauf, wie schnell sie abgeschlossen werden können. Wenn ein neuer Job eingeht, schätzen wir die verbleibende Zeit, um die laufenden Jobs abzuschliessen, und ordnen sie entsprechend um. Diese Methode hilft, die durchschnittlichen Abschlusszeiten noch weiter zu minimieren.

#Experimentelles Setup

Um unsere Algorithmen zu testen, verwendeten wir reale Daten aus einem Job-Trace-Datensatz. Diese Daten umfassten viele Jobs und Aufgaben, wodurch wir beobachten konnten, wie sich verschiedene Algorithmen unter verschiedenen Bedingungen verhalten.

#Erfolgsmetriken

Wir massen die Leistung unserer Algorithmen anhand von zwei Hauptfaktoren:

• Durchschnittliche Jobabschlusszeit, die angibt, wie schnell Jobs abgeschlossen werden.
• Rechenaufwand, der zeigt, wie viel Rechenleistung und Zeit jeder Algorithmus benötigt.

#Simulations-Ergebnisse

Wir führten Simulationen durch, um zu vergleichen, wie gut unsere Algorithmen bei verschiedenen Systemlasten funktionierten. Hier sind einige wichtige Erkenntnisse:

• Effizienzgewinne: Der OBTA-Algorithmus zeigte signifikante Effizienzverbesserungen im Vergleich zu traditionellen Methoden.

• Leistung von WF: Der WF-Algorithmus war fast so effektiv wie OBTA, arbeitete jedoch mit viel geringerem Aufwand, was ihn praktisch für grössere Arbeitslasten machte.

• Vergleich von RD: Der RD-Algorithmus übertraf oft die Leistung von WF, benötigte jedoch mehr Rechenressourcen, was unseren Erwartungen entspricht.

• Vorteile der Job-Ummodulierung: Die Job-Ummodulierungsalgorithmen zeigten Robustheit gegenüber ungleichen Datenverteilungen. Sie konnten die Abschlusszeiten bei Jobs niedrig halten, selbst wenn die Verfügbarkeit von Daten ungleichmässig war.

• Geschwindigkeit von OCWF-ACC: Diese Version des Algorithmus verbesserte sich erheblich im Vergleich zu ihrem Vorgänger, indem sie die benötigte Zeit und Ressourcen zur Berechnung der Job-Reihenfolge reduzierte.

#Auswirkungen der Serveranzahl und -kapazitäten

Durch Simulationen fanden wir heraus, dass eine höhere Verfügbarkeit von Servern dazu neigt, die Abschlusszeiten zu reduzieren. Das liegt daran, dass mehr Server eine bessere Verteilung der Aufgaben ermöglichen, was zu einer ausgewogeneren Arbeitslast führt. Ebenso führte eine Erhöhung der Server-Verarbeitungskapazität ebenfalls zu kürzeren Abschlusszeiten für Jobs.

#Verwandte Arbeiten in der Planung

Die Job-Planung war in verschiedenen Bereichen ein Fokus und adressierte sowohl theoretische als auch praktische Aspekte. Viele Algorithmen wurden entwickelt, die darauf abzielen, Effizienz, Fairness und Ressourcenzuteilung je nach Situation zu balancieren.

Mehrere Arbeiten haben verwandte Themen diskutiert, wie das Optimieren der Ressourcenzuteilung in verteilten Job-Ausführungseinstellungen. Andere haben untersucht, wie man Fairness erreichen und unnötige Datenbewegungen während der Verarbeitung minimieren kann.

#Fazit

In unserer Studie haben wir die Herausforderung der Aufgaben-Zuweisung und Job-Planung in verteilten Rechensystemen untersucht. Wir haben dieses Problem mathematisch formuliert und mehrere Algorithmen entwickelt, um Effizienz und Leistung zu verbessern. Anhand von realen Daten-Traces haben wir unsere Methoden validiert und signifikante Verbesserungen bei der Minimierung von Abschlusszeiten für Jobs bei gleichzeitig niedrigem Rechenaufwand demonstriert. Die Ergebnisse zeigen, dass sowohl die Aufgaben-Zuweisung als auch die Fähigkeit, Jobs umzuordnen, entscheidende Rollen bei der Optimierung der Leistung in verteilten Umgebungen spielen.

Zukünftige Arbeiten könnten darin bestehen, diese Algorithmen an verschiedene Rechenszenarien anzupassen und deren Flexibilität innerhalb sich ständig ändernder Job-Ausführungsdynamiken zu verbessern.