Header

UZH-Logo

Maintenance Infos

Domain-specific scheduling protocols


Tilgner, Christian. Domain-specific scheduling protocols. 2012, University of Zurich, Faculty of Economics.

Abstract

1





A database scheduler takes requests from transactions and generates a request order that fulfills the constraints of a scheduling protocol, e.g., correctness criteria. The goal of this thesis is to provide a new method for the development of domain-specific protocols for scheduling database requests. Scheduling concurrent requests is an ubiquitous problem in modern server systems based on, e.g., Web Services that handle large numbers of concurrent requests. These systems require user scalability, performance predictability, and flexibility, i.e., the ability to adapt to domain-specific needs, e.g., relaxed correctness criteria or service-level agreements (SLAs). The traditional ap- proach of outsourcing scheduling to database management systems (DBMSs) is of limited ap- plicability for these systems, because DBMSs provide only a limited amount of predefined con- sistency levels and limited user scalability. The state of the art is to develop application-specific schedulers for a given application from scratch which yields fine-tuned schedulers satisfying the application’s scheduling constraints, albeit at a great cost and with long development times. Imperative implementations of schedulers can be complex, hard to verify, and adapting such schedulers results in expensive and error-prone re-implementations. The solution we propose for the development of domain-specific scheduling protocols is a generic scheduling model called Oshiya. The main idea of this model is to treat requests as data and employ database query processing techniques to produce request schedules. Oshiya can ex- press traditional and domain-specific scheduling protocols. We introduce an Oshiya implementa- tion of the traditional strong two-phase locking protocol and leverage the conciseness of Oshiya protocol implementations to prove its correctness. Our experiments show that for large numbers of concurrent requests our approach provides a better performance than a native database sched- uler. Oshiya protocol implementations can be adapted easily to modified scheduling constraints. We leverage this advantage and develop the Declarative Serializable Snapshot Isolation proto- col, a modified version of the Snapshot Isolation protocol, and prove that it produces serializable histories. We propose the resource acquisition protocol (RAP), a domain-specific protocol for scheduling transactions that compete for resources that are available in limited quantity, which is a typical usage pattern in booking, reservation, and web shop systems. We prove that RAP is deadlock-free and that it produces less aborts due to insufficient resource availability than SI. Our experimental results confirm that RAP performs better than SS2PL and SI with respect to aborts and throughput. We present the Oshiya Debugger and Analyzer (ODA), a novel system for debugging, vi- sualizing, and comparing scheduling protocols developed using Oshiya. ODA supports the si- multaneous execution of single- and multiversion protocols, breakpoints, backward and forward debugging, as well as the statistical and visual protocol analysis. 3





Ein Datenbankscheduler hat die Aufgabe, für Anfragen (Requests) von Transaktionen eine Aus- führungsreihenfolge zu erstellen, welche die Bedingungen des verwendeten Protokolls wie z.B. Korrektheitskriterien erfüllt. Dieser Prozess wird Scheduling genannt. Das Ziel dieser Disserta- tion ist es, eine neue Methode zur Entwicklung domänenspezifischer Scheduling-Protokolle für Datenbankanfragen zu entwickeln. Das Scheduling von gleichzeitigen Requests ist ein vorherrschendes Problem in modernen (Web)Server-Systemen, welche viele gleichzeitige Requests verarbeiten müssen. Traditioneller- weise übernimmt das Datenbankmanagementsystem das Scheduling. Für diese Systeme ist das jedoch nicht immer möglich, da Datenbankmanagementsysteme nur eine limitierte Anzahl von vordefinierten Konsistenzstufen sowie eine begrenzte Benutzerskalierbarkeit zur Verfügung stellen. Deshalb werden heutzutage anwendungsspezifische Scheduler von Grund auf neu ent- wickelt. Das Resultat sind spezifische Scheduler, die die Bedingungen der Anwendung erfüllen. Jedoch ist dies mit hohen Kosten und langen Entwicklungszeiten verbunden. Diese imperativen Scheduler-Implementierungen können zudem komplex und schwer zu verifizieren sein. Eine Anpassung dieser Scheduler resultiert in teuren und fehleranfälligen Neuimplementierungen. Für die Entwicklung von domänenspezifischen Protokollen präsentieren wir ein generisches Scheduling-Modell namens Oshiya. Die Grundidee dieses Modells ist es, Requests als Daten zu behandeln und die Datenbankanfrageverarbeitung zu verwenden, um eine Ausführungsreihen- folge (Schedule) für die Requests zu generieren. Oshiya erlaubt die deklarative Spezifikation von traditionellen und domänenspezifischen Protokollen. Wir stellen eine Oshiya-Implementierung des strengen Zwei-Phasen-Sperr-Protokolls (SS2PL) vor und beweisen dessen Korrektheit. Wie wir experimentell zeigen hat unser Ansatz bei vielen gleichzeitigen Requests eine bessere Perfor- mance als ein nativer Datenbank-Scheduler. Oshiya-Protokollimplementierungen können leicht an geänderte Bedingungen angepasst werden. Wir entwickeln eine modifizierte Version von Snapshot Isolation (SI) namens Declarative Serializable Snapshot Isolation und beweisen, dass dieses Protokoll serialisierbare Schedules generiert. Wir präsentieren das Resource Acquisi- tion Protokoll (RAP), ein domänenspezifisches Protokoll für das Scheduling von Transaktionen welche um Resourcen mit begrenzter Verfügbarkeit konkurrieren. Dies ist ein typisches Zu- griffsmuster in Buchungs-, Reservations- und Webshop-Systemen. Wir beweisen, dass RAP Deadlocks vermeidet und weniger Aborts wegen zu geringer Verfügbarkeit erzeugt als Snap- shot Isolation. Unsere Experimente bestätigen, dass RAP weniger Aborts und einen höheren Durchsatz als SS2PL und SI produziert. Wir präsentieren den Oshiya Debugger und Analyzer (ODA), ein neuartiges System mit dem sich Oshiya-Protokollimplementierungen debuggen, visualisieren und vergleichen lassen. ODA unterstützt die simultane Ausführung von Einzel- und Multiversionsprotokollen, Breakpoints, vorwärts und rückwärts Debugging sowie eine statistische und visuelle Protokollanalyse.

Abstract

1





A database scheduler takes requests from transactions and generates a request order that fulfills the constraints of a scheduling protocol, e.g., correctness criteria. The goal of this thesis is to provide a new method for the development of domain-specific protocols for scheduling database requests. Scheduling concurrent requests is an ubiquitous problem in modern server systems based on, e.g., Web Services that handle large numbers of concurrent requests. These systems require user scalability, performance predictability, and flexibility, i.e., the ability to adapt to domain-specific needs, e.g., relaxed correctness criteria or service-level agreements (SLAs). The traditional ap- proach of outsourcing scheduling to database management systems (DBMSs) is of limited ap- plicability for these systems, because DBMSs provide only a limited amount of predefined con- sistency levels and limited user scalability. The state of the art is to develop application-specific schedulers for a given application from scratch which yields fine-tuned schedulers satisfying the application’s scheduling constraints, albeit at a great cost and with long development times. Imperative implementations of schedulers can be complex, hard to verify, and adapting such schedulers results in expensive and error-prone re-implementations. The solution we propose for the development of domain-specific scheduling protocols is a generic scheduling model called Oshiya. The main idea of this model is to treat requests as data and employ database query processing techniques to produce request schedules. Oshiya can ex- press traditional and domain-specific scheduling protocols. We introduce an Oshiya implementa- tion of the traditional strong two-phase locking protocol and leverage the conciseness of Oshiya protocol implementations to prove its correctness. Our experiments show that for large numbers of concurrent requests our approach provides a better performance than a native database sched- uler. Oshiya protocol implementations can be adapted easily to modified scheduling constraints. We leverage this advantage and develop the Declarative Serializable Snapshot Isolation proto- col, a modified version of the Snapshot Isolation protocol, and prove that it produces serializable histories. We propose the resource acquisition protocol (RAP), a domain-specific protocol for scheduling transactions that compete for resources that are available in limited quantity, which is a typical usage pattern in booking, reservation, and web shop systems. We prove that RAP is deadlock-free and that it produces less aborts due to insufficient resource availability than SI. Our experimental results confirm that RAP performs better than SS2PL and SI with respect to aborts and throughput. We present the Oshiya Debugger and Analyzer (ODA), a novel system for debugging, vi- sualizing, and comparing scheduling protocols developed using Oshiya. ODA supports the si- multaneous execution of single- and multiversion protocols, breakpoints, backward and forward debugging, as well as the statistical and visual protocol analysis. 3





Ein Datenbankscheduler hat die Aufgabe, für Anfragen (Requests) von Transaktionen eine Aus- führungsreihenfolge zu erstellen, welche die Bedingungen des verwendeten Protokolls wie z.B. Korrektheitskriterien erfüllt. Dieser Prozess wird Scheduling genannt. Das Ziel dieser Disserta- tion ist es, eine neue Methode zur Entwicklung domänenspezifischer Scheduling-Protokolle für Datenbankanfragen zu entwickeln. Das Scheduling von gleichzeitigen Requests ist ein vorherrschendes Problem in modernen (Web)Server-Systemen, welche viele gleichzeitige Requests verarbeiten müssen. Traditioneller- weise übernimmt das Datenbankmanagementsystem das Scheduling. Für diese Systeme ist das jedoch nicht immer möglich, da Datenbankmanagementsysteme nur eine limitierte Anzahl von vordefinierten Konsistenzstufen sowie eine begrenzte Benutzerskalierbarkeit zur Verfügung stellen. Deshalb werden heutzutage anwendungsspezifische Scheduler von Grund auf neu ent- wickelt. Das Resultat sind spezifische Scheduler, die die Bedingungen der Anwendung erfüllen. Jedoch ist dies mit hohen Kosten und langen Entwicklungszeiten verbunden. Diese imperativen Scheduler-Implementierungen können zudem komplex und schwer zu verifizieren sein. Eine Anpassung dieser Scheduler resultiert in teuren und fehleranfälligen Neuimplementierungen. Für die Entwicklung von domänenspezifischen Protokollen präsentieren wir ein generisches Scheduling-Modell namens Oshiya. Die Grundidee dieses Modells ist es, Requests als Daten zu behandeln und die Datenbankanfrageverarbeitung zu verwenden, um eine Ausführungsreihen- folge (Schedule) für die Requests zu generieren. Oshiya erlaubt die deklarative Spezifikation von traditionellen und domänenspezifischen Protokollen. Wir stellen eine Oshiya-Implementierung des strengen Zwei-Phasen-Sperr-Protokolls (SS2PL) vor und beweisen dessen Korrektheit. Wie wir experimentell zeigen hat unser Ansatz bei vielen gleichzeitigen Requests eine bessere Perfor- mance als ein nativer Datenbank-Scheduler. Oshiya-Protokollimplementierungen können leicht an geänderte Bedingungen angepasst werden. Wir entwickeln eine modifizierte Version von Snapshot Isolation (SI) namens Declarative Serializable Snapshot Isolation und beweisen, dass dieses Protokoll serialisierbare Schedules generiert. Wir präsentieren das Resource Acquisi- tion Protokoll (RAP), ein domänenspezifisches Protokoll für das Scheduling von Transaktionen welche um Resourcen mit begrenzter Verfügbarkeit konkurrieren. Dies ist ein typisches Zu- griffsmuster in Buchungs-, Reservations- und Webshop-Systemen. Wir beweisen, dass RAP Deadlocks vermeidet und weniger Aborts wegen zu geringer Verfügbarkeit erzeugt als Snap- shot Isolation. Unsere Experimente bestätigen, dass RAP weniger Aborts und einen höheren Durchsatz als SS2PL und SI produziert. Wir präsentieren den Oshiya Debugger und Analyzer (ODA), ein neuartiges System mit dem sich Oshiya-Protokollimplementierungen debuggen, visualisieren und vergleichen lassen. ODA unterstützt die simultane Ausführung von Einzel- und Multiversionsprotokollen, Breakpoints, vorwärts und rückwärts Debugging sowie eine statistische und visuelle Protokollanalyse.

Statistics

Downloads

993 downloads since deposited on 28 Jan 2013
85 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation (monographical)
Referees:Böhlen Michael, Kanne Carl-Christian
Communities & Collections:UZH Dissertations
Dewey Decimal Classification:000 Computer science, knowledge & systems
Uncontrolled Keywords:Information Systems Applications
Language:English
Place of Publication:Zurich
Date:2012
Deposited On:28 Jan 2013 13:19
Last Modified:17 Sep 2019 14:31
Number of Pages:130
OA Status:Green
Related URLs:https://www.recherche-portal.ch/primo-explore/fulldisplay?docid=ebi01_prod007586732&context=L&vid=ZAD&search_scope=default_scope&tab=default_tab&lang=de_DE (Library Catalogue)
Other Identification Number:merlin-id:7925

Download

Download PDF  'Domain-specific scheduling protocols'.
Preview
Filetype: PDF
Size: 1MB