Spawn & Merge - Eine Programmierabstraktion zur deterministischen Synchronisation verteilter Systeme

Boelmann, Christopher

Bestehende Ansätze zur deterministischen Ausführung führen alle Codebereiche einer Anwendung voll-deterministisch aus, was mit hohen Performancekosten und einem Verlust der Skalierbarkeit einhergeht. In dieser Arbeit wird ein Programmiermodell entwickelt, das eine skalierbare deterministische Ausführung einer verteilten Anwendung mit geringeren Performancekosten (gegenüber vollem Determinismus) ermöglicht. Dazu wird das Konzept des Determinismus auf Applikationsebene eingeführt, das im Gegensatz zu vollem Determinismus die deterministische Ausführung auf diejenigen Codebereiche beschränkt, deren nebenläufige Ausführung einen Einfluss auf das deterministische Ergebnis hat. Das darauf aufbauende Spawn & Merge Programmiermodell ermöglicht die automatisierte Entscheidung, ob die Ausführungsreihenfolge zweier Codebereiche für ein deterministisches Ergebnis beibehalten werden muss. Die Evaluation eines Prototyps für Spawn & Merge in Verteilten Systemen zeigt, dass verteilte Spawn & Merge Anwendungen, die einen hohen parallelisierbaren Anteil haben, effizient skalieren können (bis zu 100% der maximal erreichbaren Beschleunigung), während eine deterministische Ausführung der Anwendungslogik garantiert wird. Dem Performancegewinn stehen die Kosten für die Mechanismen gegenüber, die den Determinismus der Anwendung ermöglichen und sich aus den Kosten für die intern verwendete Operational Transformation (OT) und den eingeführten Wartebedingungen zusammensetzen. Der Großteil der potenziellen Wartebedingungen wird durch ein internes dynamisches Scheduling der parallel ausgeführten Anteile der Anwendung verhindert. Die verbleibenden Wartebedingungen wurden durch ein angepasstes OT-System, das eine effiziente deterministische Zusammenführung in beliebiger Reihenfolge ermöglicht, weiter reduziert. Die Höhe der OT-Kosten ergibt sich aus der Anwendung und kann einen Großteil der Ausführungszeit einnehmen (im Worst Case bis zu 97,5% in den durchgeführten Messungen), wenn viele Modifikationen an geteilten Datenstrukturen durchgeführt und häufig zu parallel ausgeführten Anteilen der Anwendung synchronisiert werden. Das liegt an der Berechnungskomplexität O(n^2) der verwendeten OT-Systeme. Die OT-Kosten sind allerdings für eine Anwendung konstant (für feste Eingabedaten). Somit sinkt der Anteil der OT-Kosten an der Gesamtlaufzeit bei steigender Parallelität. Die Eignung von Spawn & Merge für eine Anwendung ist somit abhängig vom parallelisierbaren Anteil, der Anzahl durchgeführter Modifikationen an geteilten Datenstrukturen und der Häufigkeit von Synchronisationen innerhalb der Anwendung.

Existing approaches for deterministic execution run all code sections in a fully deterministic manner, resulting in high performance costs and a loss of scalability. In this thesis we develop a programming model for a scalable deterministic execution of distributed applications, which introduces less performance costs than fully deterministic systems. We introduce the concept of Application-level Determinism, which, in contrast to full determinism, limits the deterministic execution to code sections that potentially influence the deterministic result of the application when executed concurrently. Based on this concept, the Spawn & Merge programming model automates the decision whether the execution of two code segments must be kept in order to maintain a deterministic result. The evaluation of a prototype of Spawn & Merge for distributed systems shows that applications with a high share of parallelizable code can scale efficiently (achieve up to 100% of maximum speedup possible) and guarantee the deterministic and reproducible execution of the application logic. The performance gain competes with the costs for the determinism-enforcing mechanisms used by Spawn & Merge: Operational Transformation (OT) and waiting conditions introduced. The majority of potential waiting conditions is automatically dealt with by internal dynamic scheduling of the parallel parts of the application. The remaining waiting conditions are further reduced by introducing a modified OT system that allows for an efficient deterministic merge in any given order. The costs for OT depend on the application and can take up most of the execution time (up to a worst case of 97,5% in the performed measurements) when many modifications of shared data structures are performed and when there is a high amount of synchronization between the parts of the application that are executed in parallel. This is due to the computational complexity of O(n^2) for the OT systems used. However, these costs for OT are constant for an application for a given input. Thus, the share of OT on the overall application runtime reduces with rising parallelism. Therefore, the feasibility of Spawn & Merge for an application depends on the parallelizable share of the application, the amount of performed modifications of shared data structures, and the amount of internal synchronizations.

Share and cite

Citation style:

Boelmann, Christopher: Spawn & Merge - Eine Programmierabstraktion zur deterministischen Synchronisation verteilter Systeme. 2018.

Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:

Export