Effiziente Reparatur von Repliken in Distributed Hash Tables

Please always quote using this URN: urn:nbn:de:0297-zib-42275
  • Eine distributed hash Table (DHT) stellt eine über multiple Rechner strukturiert verteilte Tabelle von Schlüssel-Wert-Paaren dar. Ein verteiltes System unterliegt zumeist einer Teilnehmerdynamik in Form von ausfallenden oder beitretenden Knoten, wodurch Daten verloren gehen können. Zur Sicherstellung der Verfügbarkeit aller Schlüssel-Wert-Paare ist Redundanz notwendig. Die Einführung einer Redundanzschicht erhöht die Verfügbarkeit der Daten erheblich auf Kosten einer verringerten Leistungsfähigkeit. Der Fokus dieser Arbeit liegt im Erhalt der Redundanz, was die Regeneration verlorener Kopien sowie eine Aktualisierung veralteter Kopien umfasst. Die Regeneration verlorener Kopien ist notwendig um die Verfügbarkeit langfristig zu sichern. Die Aktualisierung ist optional und verbessert die Leselatenz in geografisch weit verteilten Systemen. Die vorgestellte Lösung besteht aus drei Komponenten. Der Set Reconciliation Dienst ermöglicht den effizienten Vergleich zweier Knoten zur Identifikation verlorener und veralteter Kopien. Der Aktualisierungsdienst synchronisiert die verglichenen Knoten durch die Übertragung der Differenzen. Die dritte Komponente ist ein Anti-Entropie Protokoll, dass die Auswahl eines jeden Knotens als Synchronisationspartner sicherstellt. Das Ziel dieser Arbeit liegt in dem Vergleich dreier Set Reconciliation Algorithmen, deren Eignung und Leistungsfähigkeit für die Erkennung verlorener und veralteter Kopien evaluiert werden soll. Ausgewählt wurden der Bloom Filter, der Merkle-Tree sowie deren Kombination der Approximate Reconciliation Tree. Die Evaluation zeigte, dass der Merkle-Tree die höchste Genauigkeit besitzt und spätestens nach einer initiierten Synchronisation eines jeden Knotens zur vollständigen Synchronität in der DHT führt. Der Bloom Filter besitzt bei der Erkennung verlorener Repliken nur die halbe Genauigkeit gegenüber veralteten Repliken, wodurch die Konvergenzgeschwindigkeit dementsprechend geringer ist gegenüber dem Merkle-Tree. Dafür sind die Übertragungskosten des Bloom Filter um bis zu 80% geringer als beim Merkle-Tree und weisen kaum nennenswerte Spitzen auf. Die Übertragungskosten des Merkle-Tree sind abhängig von der Anzahl der Differenzen, sodass bei einer Differenz von Null nur eine Signatur mit weniger als einem kByte übertragen werden muss. Ist die Differenz größer, steigen die Kosten je nach Bucket-Größe an. Der Approximate Reconciliation Tree ist ein als Bloom Filter codierter Merkle-Tree, der je nach Parameterkonstellation die Eigenschaften einer der beiden Strukturen aufweist. Die Bloom Filter ähnlichen Konfigurationen bieten keinen Vorteil, wohingegen die Merkle-Tree ähnlichen nur zwei Mitteilungsrunden benötigen bei einer leichten Genauigkeitsverringerung gegenüber dem Merkle-Tree.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Maik Lange
Document Type:Master's Thesis
Granting Institution:Humboldt-Universität zu Berlin
Date of final exam:2012/09/27
Publishing Institution:Zuse Institute Berlin (ZIB)
Year of first publication:2012
Licence (German):License LogoCreative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung

$Rev: 13581 $