Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können kommenden Montag und Dienstag keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted next Monday and Tuesday.)
Type of Publication: | Dissertation |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-15390 |
Author: | Seifert, André |
Year of publication: | 2005 |
Title in another language: | Effiziente und Konsistente Transaktionsverarbeitung in Drahtlosen Datenbroadcastumgebungen |
Summary: |
Die Dissertation stellt zunächst
verschiedene drahtlose Netzwerktypen vor, welche derzeit zur mobilen Datenkommunikation zur Verfügung stehen und zeigt anschließend, daß die Mehrheit heutiger drahtloser Netze über eine Asymmetrie verfügt. Es wird aufgezeigt, daß die hybride Datenkommunikation, welche die traditionelle Pull- und die relativ neue Pushtechnik vereint, eine attraktive Kommunikationsvariante zur Schaffung skalierbarer und flexibler mobiler Datendienste darstellt. Es folgt ein Überblick über die verschiedenen umweltbezogenen und systemimmanenten Einschränkungen, welche mobile Computersysteme ausgesetzt sind und wir schlussfolgern daraufhin, daß es in mobilen Umgebungen wesentlich schwieriger als in traditionellen stationären Datenübertragungsnetzen ist, gute Performanceergebnisse in Verbindung mit starken semantischen Konsistenzgarantien für Transaktionen zu erreichen. Im Anschluß an die Darlegung der praktischen Notwendigkeit und dem zunehmenden Interesse an der Gewährleistung einer zeitnahen und konsistenten Bereitstellung von Masseninformation über mobile Breitband-Broadcastkanäle, schließt sich eine Diskussion über die Herausforderungen und vielfältigen Probleme, welche hiermit verbunden sind, an. In diesem Zusammenhang wird behauptet, daß die momentan vorhandenen Definitionen von Isolationsgraden nicht für die Implementation von Transaktionsprotokollen, welche für Nur-Lese-Transaktionen kreiert werden, geeignet sind, da diese eventuell ungewollte - obwohl korrekte - Datenzugriffe aufgrund nicht vorhandener Datenaktualitätsgarantien erlauben. Um diesem Problem Abhilfe zu schaffen, werden vier neue Isolationsgrade für Nur-Lese-Transaktionen definiert und es werden geeignete Implementierungen dieser Isolationsgrade für hybride Datenkommunikationsnetze präsentiert und deren Performance bestimmt. Um die Antwortzeiten von mobilen Anwendungen zu verkürzen und um eine hohe Skalierbarkeit von hybriden Datenkommunikationssystemen zu erreichen, spielt die Pufferverwaltung der mobilen Klienten (d.h. Endgeräten) eine wesentliche Rolle. Da existierende Pufferverwaltungsstrategien nur eine ungenügende Unterstützung für Mehrversions-Transaktionsprotokolle bieten, stellt diese Arbeit eine neue Pufferersetzungs- und -vorabrufstrategie vor, die den Namen MICP trägt. MICP ist eine hybride Pufferverwaltungsmethode, die sowohl Datenseiten als auch Datenobjekte verwalten kann. Während Datenseiten nach dem traditionellen LRU-Verfahren ersetzt werden, führt das MICP-Verfahren Objektersetzungs- und -vorabrufentscheidungen auf der Basis diverser anderer performance-kritischer Daten durch. Um zu vermeiden, daß nützliche - jedoch nicht-wiederbeschaffbare - Objektversionen mit wiederbeschaffbaren Objektversionen um verfügbare Pufferressourcen konkurrieren müssen, teilt das MICP-Verfahren den vorhandenen Speicherplatz des Klientenpuffers in zwei unterschiedlich große Segmente auf: die sogenannte REC- und NON-REC-Partition. Zur Beurteilung der Effizienz der MICP-Puffermanagementstrategie wurden umfangreiche Simulationsstudien durchgeführt, welche zeigen, daß mobile Klienten, die nicht das MICP-Verfahren zur Pufferverwaltung einsetzen, einen durchschnittlichen Performanceverlust von etwa 19% erleiden. Schließlich widmet sich die Arbeit dem Problem, Serialisierbarkeit von Lese-Schreib-Transaktionen in Verbindung mit guten Antwortzeiten und einer niedrigen Transaktionsabbruchsrate in hybriden drahtlosen Datenkommunikationsnetzen zu erreichen. Um diese Ziele zu verwirklichen, stellt die Arbeit eine Familie von fünf Mehrversions-Transaktionsprotokollen vor, die den Namen MVCC-* trägt. Die einzelnen Protokolle der MVCC-*-Familie unterscheiden sich dabei hinsichtlich der Scheduling-Performance, den Datenaktualitätsgarantien, welche den Leseoperationen der Transaktionen zugesichert werden, sowie der Speicher- und Zeitkomplexität. Es werden die Performanceabweichungen zwischen den einzelnen Protokollen der MVCC-*-Familie quantifiziert und außerdem werden die Performanceergebnisse mit denen, welche für das bekannte Snapshot Isolation Protokoll entstehen, verglichen. Da die MVCC-*-Protokollfamilie für Schedulingentscheidungen nur einfache Lese- und Schreiboperationen zur Laufzeit und keine semantischen Informationen über ihre zugrunde liegenden Transaktionen verwendet, skizziert und evaluiert die Arbeit diverse Möglichkeiten, welche die vorgeschlagenen Transaktionsprotokolle erweitern, um Datenkonflikte zu vermeiden bzw. zu reduzieren. Hierzu gehört u.a. die Spezifikation von alternativen Schreiboperationen für ursprüngliche Änderungsoperationen, die Reduktion der Datengranularität auf welcher die Transaktionskontrolle basiert sowie die Erhöhung der Anzahl der vom System vorgehaltenen Versionen der Datenobjekte. |
Summary in another language: |
In this doctoral thesis, we first
discuss the various wireless network types currently available to provide data communication services and show that the majority of them exhibit asymmetry in the bandwidth capacity, data volume, and service load. We then argue that hybrid data delivery which integrates the traditional pull and the rather novel push techniques is an attractive communication mode to create highly scalable and flexible data services. A brief overview of the environmental and system-immanent constraints of mobile computing systems follows and we reason that providing good system throughput results along with strong semantic guarantees for transactions is more challenging in mobile, portable environments than in conventional fixed networks. In the same vein, we present possible techniques to avoid and reduce the number of data conflicts that may arise and discuss ways to detect and more importantly, to resolve them once identified. After motivating the practical need for timely and consistent data delivery to thousands of information consumers, we discuss the challenges and problems involved in supporting appropriate consistency and currency guarantees to dissemination-based applications. We then argue that current definitions of isolation levels (ILs) are inappropriate for implementations of CC protocols suitable for read-only transactions as they allow unwanted, though consistent, data access patterns due to lack of data currency guarantees. To rectify the problem, we define four new ILs providing various useful data consistency and currency guarantees to read-only transactions and present suitable implementations of the proposed ILs for hybrid data delivery networks. To evaluate the performance trade-offs among the newly defined ILs and protocols, respectively, extensive numerical experiments are done, demonstrating that the Strict Forward BOT View Consistency level and its implementation provides the best possible performance results among the CC protocols studied. To shorten the response times and to achieve high scalability, client caching is one, if not the most fundamental technique in order to achieve these goals. In this thesis, we introduce a novel client cache replacement and prefetching strategy, called MICP, that makes eviction and prefetching decisions sensitive to various performance-critical factors including the objects' access recency and frequency in the recent past, their update likelihood in the near future, their re-acquisition costs, etc. On top of that, MICP is tightly-coupled to the transaction manager in order to obtain and instantly react on information indicating that locally stored non-current object versions have become useless from the CC perspective and can therefore be evicted from the client cache. To prevent that useful, but non-re-cacheable, object versions compete with re-cacheable object versions for available cache resources, MICP logically divides the cache into two variable-sized segments, dubbed REC and NON-REC. To evaluate MICP's cache management efficiency, we report on extensive experiments showing that MICP is able to improve transaction throughput results achieved by state-of-the-art online cache replacement and prefetching policies by about 19% if used for executing read-only transactions. Finally, we consider the challenging problem of providing serializability along with good performance and strong semantic data currency and consistency guarantees to mobile applications issuing read-write transactions. To achieve this goal, we present a suite of five multi-version concurrency control (MVCC) protocols, denoted MVCC-*, that differ from each other in terms of their scheduling performance, data currency guarantees, and space and time complexity. We quantify the performance deviations among the protocols of the MVCC-* suite due to applying different read rules for servicing read requests and, additionally, compare their results with those measured for the well-known Snapshot Isolation scheme. As the MVCC-* suite is based only on analyzing read and write operations at runtime and does not exploit semantic information about their constituent transactions, we outline and partially evaluate (by means of simulation) possibilities of extending the proposed protocols by conflict reducing and avoiding measures such as specifying alternative write operations, reducing the data granularity at which CC is applied, increasing the number of versions managed in the system, etc. Last, but not least, we provide evidence that MICP is superior to LRFU, being the best cache replacement policy known so far, if used to improve the response times of read-write transactions. |
Examination date (for dissertations): | Apr 27, 2005 |
Dissertation note: | Doctoral dissertation, University of Konstanz |
CCS Classification: | H.2.4 |
Subject (DDC): | 004 Computer Science |
Controlled Keywords (GND): | Transaktionsverwaltung, Mobiles Datenbanksystem, Broadcastingverfahren, Caching, Datenaustausch, Ubiquitous computing |
Keywords: | Isolationsgrade, Mobile Computing, Concurrency Control, Client Caching, Broadcasting, Hybrid data delivery, Isolation levels |
Link to License: | In Copyright |
SEIFERT, André, 2005. Efficient and Consistent Transaction Processing in Wireless Data Broadcast Environments [Dissertation]. Konstanz: University of Konstanz
@phdthesis{Seifert2005Effic-6272, title={Efficient and Consistent Transaction Processing in Wireless Data Broadcast Environments}, year={2005}, author={Seifert, André}, address={Konstanz}, school={Universität Konstanz} }
diss_seifert_05_2005.pdf | 316 |