Refine
Document Type
- In Proceedings (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (2)
Institute
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.