TU Darmstadt / ULB / TUprints

High Data Availability and Consistency for Distributed Hash Tables Deployed in Dynamic Peer-to-peer Communities

Kneević, Predrag (2007)
High Data Availability and Consistency for Distributed Hash Tables Deployed in Dynamic Peer-to-peer Communities.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
knezevic_thesis.pdf
Copyright Information: In Copyright.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: High Data Availability and Consistency for Distributed Hash Tables Deployed in Dynamic Peer-to-peer Communities
Language: English
Referees: Aberer, Prof. Dr. Karl ; Buchmann, Prof. Dr. Alejandro ; Steinmetz, Prof. Dr.- Ralf
Advisors: Neuhold, Prof. Dr. Erich J.
Date: 27 July 2007
Place of Publication: Darmstadt
Date of oral examination: 10 July 2007
Abstract:

Decentralized and peer-to-peer computing, as a subset of distributed computing, are seen as enabling technologies for future Internet applications. However, many of them require some sort of data management. Apart from currently popular P2P file-sharing, there are already application scenarios that need data management similar to existing distributed data management, but being deployable in highly dynamic environments. Due to frequent changes of the peer availability, an essential issue in peer-to-peer data management is to keep data highly available and consistent with a very high probability. Usually, data are replicated at creation, hoping that at least one replica is available when needed. However, due to unpredictable behavior of peers, their availability varies and the number of configured replicas might not guarantee the intended data availability. Instead of fixing the number of replicas, the requested guarantees should be achieved by adapting the number of replicas at run-time in an autonomous way. This thesis presents a decentralized and self-adaptable replication protocol that is able to guarantee high data availability and consistency fully transparently in a dynamic Distributed Hash Table. The proposed solution is generic and can be applied on the top of any DHT implementation that supports common DHT API. The protocol can detect a change in the peer availability and the replication factor will be adjusted according to the new settings, keeping or recovering the requested guarantees. The protocol is based on two important assumptions: (1) ability to build and manage a decentralized replica directory and (2) ability to measure precisely the actual peer availability in the system. The replica directory is built on top of the DHT by using a key generation schema and wrapping replicas with additional system information such as version and replica ordinal number. The way in which replicas are managed in the DHT helps us to define a measurement technique for estimating peer availability. Peers cannot be checked directly, due to the fact that the common DHT API does not reveal any details about the underlying DHT topology. The peer availability is computed based on the measured the availability of replicas. With the help of confidence interval theory, it is possible to determine the sufficient number of probes that produces results with an acceptable error. Finally, two variants of the protocol are defined: one that assumes that data are immutable, and another one without such a limitation. A theoretical model is developed to determine the sufficient number of replicas needed to deliver the pre-configured guarantees. If a peer detects that the current availability of peers and the replication factor are not sufficient for maintaining the guarantees, the sufficient replication factor will be determined according to the measured availability of peers. Knowing the previous and new replication factor, the peer is able to insert into the DHT additional replicas of data managed in its local storage. On the other hand, if the number of replicas is higher than needed, the peer will remove unnecessary replicas from its storage, reducing the storage overhead. Replication makes the consistency of data harder to maintain. Every logical update is translated into a set of replica updates. Due to the dynamic nature of the DHT, many replicas can be unavailable at the time when an application issues an update request. Such conditions force the usage of some weak-consistency models that updates all available replicas and synchronizes all the others eventually when they become online again. Until this is achieved, none of guarantees about the consistency of the accessed data cannot be given. The proposed protocol implements a weak-consistency mechanism that, unlike the others, is able to provide an arbitrary high probabilistic guarantees about the consistency of available data before all replicas are synchronized. This is done by updating the available and inserting the new version of all offline replicas. As soon as a replica becomes available again, it is informed about missing updates, and is merged with the new version. Such approach ensures that at least one consistent replica is available with a high probability when data are requested. The approach presented was evaluated by using a custom-made simulator. The requested availability and consistency levels are fully guaranteed in the DHT with a stable or increasing peer availability. During churns (periods when the peer availability decreases), the guarantees are maintained only in cases when the dynamic of churns is low (the peer availability decreases slowly). Faster changes cannot be compensated fully, but eventually, after the system stabilizes enough replicas will be generated, and the guarantees will be recovered.

Alternative Abstract:
Alternative AbstractLanguage

Dezentralisierte Systeme und peer-to-peer (P2P) Computing werden als technologische Voraussetzungen zukünftiger Internetanwendungen gesehen. Obwohl sich die Infrastrukturen unterscheiden, sind die Aufgaben der Anwendungen gleich oder ähnlich zu denjenigen Anwendungen, die den klassischen Client/Server-Ansatz benutzen: Bearbeitung und Speicherung von Daten. Abgesehen vom derzeitig populären P2P File-sharing gibt es viele Anwendungsszenarios, die eine Datenverwaltung benötigen, die ähnlich zu einer verteilten Datenverwaltung ist. Gleichzeitig muss sie aber in hoch-dynamischen Umgebungen funktionieren. Das größte Problem der P2P-Datenverwaltung ist die Gewährleistung und Konsistenzhaltung der Daten. Üblicherweise werden Daten bei der Erstellung repliziert und man hofft, dass mindestens eine der Repliken verfügbar ist, wenn sie gebraucht wird. Aufgrund unvorhersehbaren Verhalten der Peers garantiert die konfigurierte Anzahl der Repliken oft nicht die gewünschte Datenverfügbarkeit. Statt einer vordefinierten Anzahl von Repliken sollte sich die Anzahl der Repliken während der Laufzeit voll-autonom an die aktuelle Peerverfügbarkeit anpassen. Diese Doktorarbeit präsentiert ein dezentralisiertes und selbst-adaptives Replikationsprotokoll, das voll-transparent eine hohe Datenverfügbarkeit und -konsistenz mittels einer dynamischen verteilten Hash-Tabelle (DHT -- Distributed Hash Tables auf Englisch) garantiert. Die Lösung ist voll generisch und auf alle DHT-Implementierungen anwendbar, die DHT API bieten. Wenn sich die Peerverfügbarkeit ändert, dann muss das Protokoll in der Lage sein, dies festzustellen. Auf Basis der aktuellen Werte wird der Replikationsfaktor verändert, um die gewünschte Verfügbarkeit und Konsistenz zu behalten. Das Replikationsprotokoll basiert auf zwei wichtigen Aufnahmen: (1) ein Vermögen um ein dezentralisiertes Replikenverzeichnis aufzubauen und zu pflegen, und (2) ein Vermögen um genau die aktuelle Peerverfügbarkeit im System zu messen. Das Replikenverzeichnis benutzt die verteilte Hash-Tabelle als Basis und generiert mit der Hilfe einer definierten Funktion Schlüssel. Repliken sind mit zusätzlichen Systeminformationen wie ihre Version und Ordnungszahl unter den Schlüsseln gespeichert. Der Ansatz macht ermöglicht es, später eine Messmethode für die Peerverfügbarkeit zu definieren. Weil das gemeine DHT API keine Information über die Systemtopologie publiziert, ist es nicht möglich die Verfügbarkeit von den Peers direkt zu prüfen. Stattdessen prüft die vorgeschlagene Messmethode die Verfügbarkeit der Repliken. Es ist möglich mit der Hilfe der Konfidenzintervalltheorie zu berechnen, wie viele Proben ausreichen, dass die Messgebnisse einen niedrigen Fehler haben. Schließlich werden zwei Varianten des Protokolls definiert: Die erste nimmt an, dass Daten unveränderlich bleiben. Die zweite erlaubt, dass Daten während der Laufzeit modifiziert werden dürfen. Um festzulegen wie viele Repliken für gewisse konfigurierte Garantien gebraucht werden, wird ein analytisches Modell entwickelt. Wenn ein Peer feststellt, dass die aktuelle Peerverfügbarkeit und die Anzahl der Repliken nicht die gewünschte Garantien liefern, wird ein neuer Replikationsfaktor berechnet. Jetzt weiß der Peer, wie viele zusätzliche Repliken der Daten eingefügt werden sollen. Andererseits löschen Peers unnötige Repliken aus ihren Speichern, wenn die gleichen Garantien mit weniger Repliken auch erreicht werden. Datenreplikation erschwert die Erhaltung der Datenkonsistenz. Jede logische Datenaktualisierung wird in der Aktualisierung von mehreren Repliken übersetzt. Viele dieser Repliken können nicht zu jedem Zeitpunkt gefunden werden, da Peers, bei denen die Repliken gespeichert sind, nicht verfügbar sein können. Solche Bedingungen erlauben nur, dass die Daten eine schwache Konsistenz haben, bis alle Repliken aktualisiert sind. Vor der Aktualisierung kann keine Aussage über die Konsistenz der gefunden Daten gemacht werden. Das Replikationsprotokoll dieser Arbeit implementiert ein schwach-konsistentes Modell, aber mit einem Unterschied zu den bestehenden: Es bietet eine hohe Wahrscheinlichkeit, dass die gefundenen Daten, die vor allen Repliken aktualisiert werden, konsistent sind. So etwas ist möglich, wenn alle verfügbaren Repliken aktualisiert werden und dazu eine neue Version aller Offline-Repliken eingefügt werden. Sobald diese Repliken wieder online sind, werden über verpassende Updates informiert werden, werden die alten und neuen Versionen vereinigt. Deswegen garantiert das Protokoll mit einer hohen Wahrscheinlichkeit, dass mindestens eine konsistente Replik verfügbar ist. Der Ansatz wird mit Hilfe eines selbst-entwickeltes Simulators evaluiert. Die Ergebnisse zeigen, dass die Datenverfügbarkeit und -konsistenz voll-garantiert sind, wenn die Peerverfügbarkeit stabil oder ansteigend ist. Bei absteigender Verfügbarkeit, werden die Garantien nur bei langsamen Änderungen voll gepflegt. Bei schneller Senkung der Peerverfügbarkeit fallen die Garantien für einen gewissen Zeitabschnitt, aber nach der Stabilisierung des Systems werden wieder genug Repliken generiert, um die gewünschte Datenverfügbarkeit und -konsistenz wieder zu bekommen.

German
Uncontrolled Keywords: decentralized, peer-to-peer, data management, replication, data availability, data consistency, distributed hash table, dht
Alternative keywords:
Alternative keywordsLanguage
decentralized, peer-to-peer, data management, replication, data availability, data consistency, distributed hash table, dhtEnglish
URN: urn:nbn:de:tuda-tuprints-8547
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:53
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/854
PPN:
Export:
Actions (login required)
View Item View Item