| Autor(en): |
Felix Hupfeld |
Titel: |
Causal weak-consistency replication – a systems approach |
| Gutachter: |
Alexander Reinefeld; Jens-Peter Redlich; Marc Shapiro |
| Erscheinungsdatum: |
03.06.2009 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-100100235)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
Schwach-konsistente Replikation, Optimistische Replikation, eventual consistency, Gossip, kausale Konsistenz |
| Schlagwörter (eng): |
weak-consistency replication, optimistic replication, eventual consistency, gossip |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Lizenz: |
|
| Zitationshinweis: |
Hupfeld, Felix:
Causal weak-consistency replication – a systems approach;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 03.06.2009, urn:nbn:de:kobv:11-100100235
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| Replikation kann helfen, in einem verteilten System die Fehlertoleranz und Datensicherheit zu verbessern. In Systemen, die über Weitverkehrsnetze kommunizieren oder mobile Endgeräte einschließen, muß das Replikationssystem mit großen Kommunikationslatenzen umgehen können. Deshalb werden in solchen Systemen in der Regel nur asynchrone Replikationsalgorithmen mit schwach-konsistenter Änderungssemantik eingesetzt, da diese die lokale Annahme von Änderungen der Daten und deren Koordinierung mit anderen Replikaten entkoppeln und somit ein schnelles Antwortverhalten bieten können.
Diese Dissertation stellt einen Ansatz für die Entwicklung schwach-konsistenter Replikationssysteme mit erweiterten kausalen Konsistenzgarantien vor und weist nach, daß auf seiner Grundlage effiziente Replikationssysteme konstruiert werden können. Dazu werden Mechanismen, Algorithmen und Protokolle vorgestellt, die Änderungen an replizierten Daten aufzeichnen und verteilen und dabei Kausalitätsbeziehungen erhalten. Kern ist ein Änderungsprotokoll, das sowohl als grundlegende Datenstruktur der verteilten Algorithmen agiert, als auch für die Konsistenz der lokalen Daten nach Systemabstürzen sorgt.
Die kausalen Garantien werden mit Hilfe von zwei Algorithmen erweitet, die gleichzeitige Änderungen konsistent handhaben. Beide Algorithmen basieren auf der Beobachtung, daß die Divergenz der Replikate durch unkoordinierte, gleichzeitige Änderungen nicht unbedingt als Inkonsistenz gesehen werden muß, sondern auch als das Erzeugen verschiedener Versionen der Daten modelliert werden kann. Distributed Consistent Branching (DCB) erzeugt diese alternativen Versionen der Daten konsistent auf allen Replikaten; Distributed Consistent Cutting (DCC) wählt eine der Versionen konsistent aus.
Die vorgestellten Algorithmen und Protokolle wurden in einer Datenbankimplementierung validiert. Mehrere Experimente zeigen ihre Einsetzbarkeit und helfen, ihr Verhalten unter verschiedenen Bedingungen einzuschätzen. |
| Abstract (eng): |
| Data replication techniques introduce redundancy into a distributed system architecture that can help solve several of its persistent problems. In wide area or mobile systems, a replication system must be able to deal with the presence of unreliable, high-latency links. Only asynchronous replication algorithms with weak-consistency guarantees can be deployed in these environments, as these algorithms decouple the local acceptance of changes to the replicated data from coordination with remote replicas.
This dissertation proposes a framework for building weak-consistency replication systems that provides the application developer with causal consistency guarantees and mechanisms for handling concurrency. By presenting an integrated set of mechanisms, algorithms and protocols for capturing and disseminating changes to the replicated data, we show that causal consistency and concurrency handling can be implemented in an efficient and versatile manner. The framework is founded on log of changes, which both acts the core data structure for its distributed algorithms and protocols and serves as the database log that ensures the consistency of the local data replica.
The causal consistency guarantees are complemented with two distributed algorithms that handle concurrent operations. Both algorithms are based on the observation that uncoordinated concurrent operations introduce a divergence of state in a replication system that can be modeled as the creation of version branches. Distributed Consistent Branching (DCB) recreates these branches on all participating processes in a consistent manner. Distributed Consistent Cutting (DCC) selects one of the possible branches in a consistent and application-controllable manner and enforces a total causal order for all its operations.
The contributed algorithms and protocols were validated in an database system implementation, and several experiments assess the behavior of these algorithms and protocols under varying conditions. |
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
  | | | | | | | | | | | | | | | | | | | | | | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Feb
13 | Mar
13 | Apr
13 | May
13 |
| Monat | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Feb
13 | Mar
13 | Apr
13 | May
13 | | Startseite | 3 | 3 | | 4 | 1 | 3 | | | | | 1 | 2 | 1 | | | | | 2 | 2 | 2 | 6 | 1 | | PDF | 22 | 22 | 41 | 19 | 24 | 30 | 33 | 22 | 17 | 24 | 27 | 89 | 55 | 18 | 36 | 57 | 30 | 25 | 38 | 32 | 32 | 36 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 31 (1.41 pro Monat)
- PDF – 729 (33.14 pro Monat)
|
