Not logged in.

Quick Search - Contribution

Contribution Details

Type	Dissertation
Scope	Discipline-based scholarship
Title	Domain-specific scheduling protocols
Organization Unit	Database Technology (Michael Hanspeter Böhlen)
Authors	Christian Tilgner
Supervisors	Michael Hanspeter Böhlen Carl-Christian Kanne
Language	English
Institution	University of Zurich
Faculty	Faculty of Economics, Business Administration and Information Technology
Number of Pages	130
Date	2012
Abstract Text	A database scheduler takes requests from transactions and generates a request order that fulﬁlls 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-speciﬁc 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 ﬂexibility, i.e., the ability to adapt to domain-speciﬁc needs, e.g., relaxed correctness criteria or service-level agreements (SLAs). The traditional approach of outsourcing scheduling to database management systems (DBMSs) is of limited applicability for these systems, because DBMSs provide only a limited amount of predeﬁned consistency levels and limited user scalability. The state of the art is to develop application-speciﬁc schedulers for a given application from scratch which yields ﬁne-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-speciﬁc 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 express traditional and domain-speciﬁc scheduling protocols. We introduce an Oshiya implementation 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 scheduler. Oshiya protocol implementations can be adapted easily to modiﬁed scheduling constraints. We leverage this advantage and develop the Declarative Serializable Snapshot Isolation protocol, a modiﬁed version of the Snapshot Isolation protocol, and prove that it produces serializable histories. We propose the resource acquisition protocol (RAP), a domain-speciﬁc protocol for scheduling transactions that compete for resources that are available in limited quantity, which is a typical usage pattern in booking, reservation, and webshop systems. We prove that RAP is deadlock-free and that it produces fewer aborts due to insufﬁcient resource availability than SI. Our experimental results conﬁrm 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, visualizing, and comparing scheduling protocols developed using Oshiya. ODA supports the simultaneous execution of single- and multi version protocols, breakpoints, backward and forward debugging, as well as the statistical and visual protocol analysis. 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 Dissertation ist es, eine neue Methode zur Entwicklung domänenspeziﬁscher 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. Traditionellerweise übernimmt das Datenbankmanagementsystem das Scheduling. Für diese Systeme ist das jedoch nicht immer möglich, da Datenbankmanagementsysteme nur eine limitierte Anzahl von vordeﬁnierten Konsistenzstufen sowie eine begrenzte Benutzerskalierbarkeit zur Verfügung stellen. Deshalb werden heutzutage anwendungsspeziﬁsche Scheduler von Grund auf neu entwickelt. Das Resultat sind speziﬁsche 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 veriﬁzieren sein. Eine Anpassung dieser Scheduler resultiert in teuren und fehleranfälligen Neuimplementierungen. Für die Entwicklung von domänenspeziﬁschen 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ührungsreihenfolge (Schedule) für die Requests zu generieren. Oshiya erlaubt die deklarative Speziﬁkation von traditionellen und domänenspeziﬁschen 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 modiﬁzierte Version von Snapshot Isolation (SI) namens Declarative Serializable Snapshot Isolation und beweisen, dass dieses Protokoll serialisierbare Schedules generiert. Wir präsentieren das Resource Acquisition Protokoll (RAP), ein domänenspeziﬁsches 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.
Other Identification Number	merlin-id:7925
PDF File	Download from ZORA
Export	BibTeX EP3 XML (ZORA)
Keywords	Information Systems Applications