TU Darmstadt / ULB / TUprints

Holistic Runtime Scheduling for the Distributed Computing Landscape

Blöcher, Marcel (2021):
Holistic Runtime Scheduling for the Distributed Computing Landscape. (Publisher's Version)
Darmstadt, Technische Universität Darmstadt,
DOI: 10.26083/tuprints-00018576,
[Ph.D. Thesis]

[img]
Preview
Text
2021-Bloecher_Holistic_Runtime_Scheduling.pdf
Available under CC-BY-NC-ND 4.0 International - Creative Commons, Attribution Non-commerical, No-derivatives.

Download (7MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Holistic Runtime Scheduling for the Distributed Computing Landscape
Language: English
Abstract:

Internet services have become an indispensable part of our lives, with billions of users on a daily basis. Example use cases include services for real-time communication and collaborative editing of documents. Furthermore, there are many hidden—nonetheless omnipresent—use cases like cashier systems and sensors of industry facilities. Users expect to use Internet services at any time at low cost with the desired service quality despite potential load spikes a service might face. A straightforward strategy to provide services with high availability is to allocate dedicated resources for each service. In turn, this strategy is likely to lead to over-provisioning and increased operating expenses, which contradicts offering services at a low price. A solution to this problem is to leverage resource scheduling to share the underlying resources among many different workloads and services. Sharing the underlying resources is a key enabler to offer highly scalable services while keeping operating expenses of each service low. A wide range of resource scheduling systems for the distributed computing landscape has been proposed in the past, covering the application and infrastructure levels. Application-level scheduling focuses on problems such as given a set of resources, configuring an application to reach high throughput and good service quality. Many application-level resource scheduling systems lack support for runtime scheduling, often due to slow or unsuitable algorithms. Without runtime scheduling, resource scheduling must run in advance for many scenarios and, at best, repeats periodically to update scheduling decisions. This is likely to result in inefficient resource usage. In contrast to application-level scheduling, infrastructure-level scheduling is about orchestrating resources and serving resource requests of various applications, aiming at high resource utilization. Infrastructure-level scheduling leverages generic resource abstractions, e.g., containers and virtual machines, to fulfill these properties. These abstractions make assumptions (e.g., homogeneity, linear resource consumption) to simplify management, but ignore the fact that current distributed computing systems have been evolving in the post-Moore’s law era and many of these assumptions need to be revised. In particular, the recent trend of new programmable networking devices, ushering in a new area of in-network computing (INC), overtaxes the generic abstractions of compute containers running on servers. The ever-growing demand for Internet services in general and increasingly heterogeneous resources combined with the highly varying demand in particular, require runtime solutions for holistic resource scheduling, covering both the application and infrastructure levels. This dissertation presents four novel solutions to holistic runtime scheduling for the distributed computing landscape. Two solutions cover the application and two the infrastructure levels. We start with an analysis of the field of resource scheduling for the distributed computing landscape and classify involved systems, resources, and abstractions. Based on this, we present a classification of INC which helps to understand the design space of INC resource scheduling. Next, we discuss two scenarios at the application level and demonstrate how runtime scheduling improves resource efficiency. As a first scenario, we consider big data aggregation systems and present ROME, a middleware system to reduce the total aggregation time. ROME automatically analyzes at runtime the involved aggregation function’s data stream and optimizes each node’s responsibilities in the aggregation plan. ROME reduces total aggregation time even compared with manually fine-tuned systems. The second scenario discusses resource scheduling of distributed service function chains. We present STEAM, the first distributed runtime scheduler for this problem, that operates at packet-level granularity without requiring a priori information of traffic estimates and a global view of the systems. Compared with non-runtime solutions to this problem, STEAM achieves better service quality when using the same resources and reduces the amount of resources required to serve the same load. For the data center infrastructure level, we present two mutually exclusive solutions. Our first solution is IncSched, a system that retrofits existing data center resource schedulers for INC. Based on the proposed classification of INC, IncSched presents a new resource model, translates resource requests to be compliant with the plugged retrofitted scheduler, and holds the logic for managing INC resources. IncSched makes existing resource schedulers compatible with INC for the first time, contributing to a broad acceptance of INC. For a holistic integration of INC in data center resource scheduling, we propose HIRE, a full-fledged resource scheduling solution for INC. HIRE extends the resource model of IncSched for automatic augmentation of resource alternatives and incorporates non-linearity property of INC resource usage. HIRE is the first scheduler that combines all server and INC resources in the same scheduling problem to attribute interdependencies on data center level. These novelties make HIRE more successful in satisfying resource requests with INC, finding better placements concerning locality, and reducing tail latencies. We evaluate all solutions using extensive simulations, and for some also using system prototypes and integrated benchmarks. In summary, this dissertation proposes four novel solutions for holistic runtime resource scheduling. The contributions foster the importance of runtime resource scheduling for more efficient resource usage. Our contributions to holistic resource scheduling make shared INC available on a data center level for the first time.

Alternative Abstract:
Alternative AbstractLanguage

Internetdienste sind zu einem unverzichtbaren Bestandteil unseres Lebens geworden. Milliarden von Benutzern nutzen täglich Internetdienste, zum Beispiel zur Echtzeit-Kommunikation mit Video und kollaborativen Arbeit an Dokumenten. Darüber hinaus gibt es auch viele allgegenwärtige—teils versteckte—Internetdienste wie Kassensysteme für Restaurants und Sensoren in Industrieanlagen. Von Internetdiensten wird erwartet, dass diese stets in gewünschter Qualität verfügbar sind, auch bei hohem Nutzeraufkommen, und zu niedrigen Kosten genutzt werden können. Eine direkte Herangehensweise, um hohe Erreichbarkeit sicherzustellen, besteht in der Bereitstellung dedizierter Infrastruktur für jeden Dienst. Dieser Lösungsansatz führt wiederum sehr wahrscheinlich zu Überkapazität und ist mit dem Ziel niedriger Kosten praktisch schwer vereinbar. Eine alternative Lösung besteht darin, die zugrunde liegende Infrastruktur mittels Ressourcenplanung unter vielen verschiedenen Diensten zu teilen. Durch die gemeinsame Nutzung der Ressourcen wird es möglich, Dienste hochgradig skalierbar anzubieten, bei gleichzeitig niedrigen Betriebskosten für jeden einzelnen Dienst. Eine breite Palette an Systemen zur Ressourcenplanung ist bereits in der verteilten Rechenlandschaft im Einsatz, sowohl auf Anwendungsebene als auch auf Infrastrukturebene. Die Systeme zur Ressourcenplanung haben das Ziel eine hohe Ressourcenauslastung bei gleichzeitig guter Servicequalität zu erreichen. Um diese Eigenschaften erreichen zu können und zur Gewährleistung einer breiten Einsetzbarkeit, basieren solche Systeme zu großen Teilen auf generischen Ressourcenabstraktionen, wie virtuelle Maschinen oder Container. Generische Ressourcenabstraktionen greifen auf Annahmen zurück, wie zum Beispiel Ressourcenhomogenität oder lineare Ressourcennutzung, die die Planung vereinfachen, jedoch für die jüngsten Entwicklungen verteilter Systeme in der nach-Mooreschen Ära überarbeitet werden müssen. Insbesondere der jüngste Trend zu programmierbaren Netzwerkgeräten, die eine neue Ära des “in-network computing” (INC) einläuten, passt nicht mehr zur generischen Abstraktion von Containern, die auf Servern ausgeführt werden. Darüber hinaus fehlt für viele solcher Ressourcenplaner die Möglichkeit zur dynamischen Planung zur Laufzeit, da die zugrunde liegenden Algorithmen zu hohe Laufzeiten aufweisen oder nicht für einen dynamischen Ansatz konzipiert wurden. Ohne dynamische Planung muss für viele Szenarien die Ressourcenplanung vorab ausgeführt werden und kann bestenfalls in regelmäßigen Zeitabständen Korrekturen vornehmen, was letztendlich zu ineffizienter Nutzung der Ressourcen führt. Die ständig steigende Nachfrage nach Internetdiensten im Allgemeinen, und die zunehmende Hardware-Heterogenität kombiniert mit der Unbeständigkeit der Anwendungslast im Speziellen, erfordern dynamische Lösungen zur ganzheitlichen Ressourcenplanung, sowohl auf Anwendungsebene als auch auf Infrastrukturebene. In dieser Dissertation werden vier neue Lösungen vorgestellt, um eine ganzheitliche dynamische Ressourcenplanung für die verteilte Rechenlandschaft zu realisieren. Zwei davon auf Anwendungsebene sowie zwei auf Infrastrukturebene. Zunächst wird das Forschungsfeld der Ressourcenplanung für die verteilte Rechenlandschaft eingegrenzt, indem die beteiligten Systeme, Ressourcen, Bedarfe und Abstraktionen analysiert und klassifiziert werden. Aufbauend darauf wird eine Klassifizierung für INC vorgestellt um den Entwurfsraum für die Ressourcenplanung zu erschließen. Die Lösungen auf Anwendungsebene zeigen für zwei Szenarien, wie dynamische Ressourcenplanung zu einer effizienteren Nutzung der Ressourcen beitragen kann. Als erstes Szenario betrachten wir Big Data Aggregationssysteme und stellen das System ROME vor. ROME analysiert automatisch den Datenstrom und berechnet zur aktuellen Umgebung die optimale Zusammenschaltung der verfügbaren Ressourcen, mit dem Ziel, die Aggregation frühestmöglich abzuschließen. ROME zeigt selbst gegen manuell eingestellte Systeme ein besseres Laufzeitverhalten. Das zweite Szenario diskutiert die Ressourcenplanung von verteilten Funktionsketten. Wir präsentieren STEAM, der erste verteilte Ressourcenplaner für dieses Problem, der die Planung auf Paketebene während der Laufzeit durchführen kann, ohne globales Wissen und Vorabinformationen zur aufkommen Last zu benötigen. Im Gegensatz zu bisherigen Arbeiten erzielt STEAM bessere Servicequalität bei gleichen Ressourcen, bzw. reduziert die benötigten Ressourcen bei gleicher Nutzerlast. Auf Infrastrukturebene werden zwei alternative Lösungen präsentiert. Zunächst wird IncSched vorgestellt, ein System welches bestehende Rechenzentren-Ressourcenplaner für INC nachrüstet. Aufbauend auf der vorgestellten INC Klassifikation, führt IncSched ein neues Ressourcenmodell ein, übersetzt dieses für bestehende Ressourcenplaner und kapselt die Logik zur Verwaltung von INC. Dadurch werden existierende Ressourcenplaner erstmals kompatibel zu INC, was auf breiter Basis die Zugänglichkeit zu INC in Rechenzentren positiv beeinflussen wird. Um INC noch besser in die Ressourcenplanung integrieren zu können, wird als letztes HIRE vorgestellt, ein eigenständiger Rechenzentren-Ressourcenplaner. HIRE erweitert das Ressourcenmodell von IncSched um automatisch alternative Ressourcen spezifizieren zu können, bildet die Nichtlinearität von INC-Ressourcen ab und berücksichtigt die wechselseitigen Abhängigkeiten zwischen Servern und INC. Durch diese Neuerungen bedient HIRE im Vergleich zu IncSchedLösungen mehr Anwendungen mit INC, reduziert die maximale Wartezeit, und trifft darüber hinaus noch qualitativ bessere Entscheidungen zur Auswahl der Ressourcen um Lokalität zu berücksichtigen. Alle vier Lösungen werden in umfangreichen Simulationen, zum Teil auch mittels Prototypen sowie integrierter Benchmarks, evaluiert. Zusammenfassend präsentiert diese Dissertation vier neue Lösungen die zur ganzheitlichen dynamischen Ressourcenplanung der verteilten Rechenlandschaft beitragen. Damit zeigen wir die Relevanz dynamischer Ressourcenplanung und wie mittels ganzheitlicher Ressourcenplanung gemeinsam genutztes INC auf Rechenzentrumsebene zugänglich wird.

German
Place of Publication: Darmstadt
Collation: xiii, 200 Seiten
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Distributed Systems Programming
Date Deposited: 18 Jun 2021 10:15
Last Modified: 18 Jun 2021 10:15
DOI: 10.26083/tuprints-00018576
URN: urn:nbn:de:tuda-tuprints-185766
Referees: Mühlhäuser, Prof. Dr. Max ; Eugster, Prof. Dr. Patrick ; Wang, Prof. Dr. Lin
Refereed: 17 March 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/18576
Export:
Actions (login required)
View Item View Item