Distributed hash tables Flashcards
Was ist ein DHT (Distributed Hash Table) ?
Ein DHT verteilt (Key, Value) Paare über mehrere Computer (buckets) die überall auf der Welt verteilt sein können. Wenn ein User einer eine Key eingibt, benutzt das System eine Hashfunktion um den Value zum Key zu finden, welcher auf einem der Computer gespeichert ist. Der Hash identifiziert dabei den Computer (bucket). Dabei müss nicht jeder Comupter jeden anderen kennen aber alle müssen irgendwie erreichbar sein.
Welche Funktionen hat ein DHT interface?
- lookup(key) -> value
- insert(key, value)
- delete(key)
Welche zwei Probeleme haben DHTs und wie können sie gelöst werden
- Problem 1: Mit einer Modulo Hash Funktion verändert jeder Knoten virtuell seine Position beim hinzufügen und lösen von Knoten
- Lösung 1: Wir benutzen ein Konsistenten Hash. Dabei haben wir einen festen Hashraum. Alle Hashwerte fallen in diesen Raum und der key geht zum Knoten der am nächsten an der ID dran ist
- Problem 2: alle Knoten müssen bekannt sein
- Lösung 2: Jeder Knoten kennt nur ein paar “Nachbarn” und Nachricht wird über mehrere Knoten weitergleitet
Was ist ein Chord?
Ein Chord ist eine DHT Implementierung
Wie werden beim Chord die IDs auf die Knoten abgebildet?
- Der Hashraum ist eindimensionaler Raum mit Werten von 0 bis 2(^m)-1
- Jeder Knoten hat einen Pointer zu seinem Vorgänger
- Jeder Knoten ist Werte von [VorgängerID+1, self.ID] verantwordlich
Wie sieht der Lookup beim Chord aus?
- lookup startet bei einem Knoten
- Nachricht geht im Kreis rum bis zum Vorgänger des verantwortlichen Knoten.
- Voränger teil Startknoten den Verantwortlichen mit
Wie sieht die Joining Operation beim Chord aus?
- Jeder Knoten A sendet periodisch eine stabalize Nachricht an seinen Nachfolger B
- Wenn B stabalize() erhält, sendet B notifiy(B’) mit B’ = pred(B) an A
- Wenn B’ = A bleibt alles gleich
- Wenn B’ != A: B’ wird der neue Nachfolger von A und A sendet stabalize() an B’
Joining Operation von Chord - Beispiel
Chords mit Finger Tables
- Finger Table halten Inforamtion über mögliche zuständige Knoten
hier ist m = 7
Was versteht man unter latency stretch?
Latency Stretch ist ein Faktor welcher beschreibt wie die Overlay-Topologie (also bei Chord die Ring- Struktur) durchschnittlich die Latenzzeiten vergrö- ßert im Vergleich zu einem vollvermaschten Netwerk, bei dem jede Anfrage den direkten Weg nehmen würde.
Was ist die Formel vom latency stretch?
Was ist die allgemeine Formel zum Ausrechnen des i-ten Werts in der Finger Table des Knotens mit der ID n bei Chord?
Wie vereinfacht eine Finger Table den Chord Lookup?
Der Aufwand eine beliebigen ID in Ring zu erreichen geht von O(n) Schritten auf O(log n) Schritten, wobei jeder Knoten nur m Tabelleneinträge aktuell halten muss.
