Chord: Difference between revisions

From
Jump to navigation Jump to search
No edit summary
Line 7: Line 7:


== System Modell ==
== System Modell ==
; Lastbalanzierung: [http://theory.lcs.mit.edu/~karger/Papers/Talks/Hash Consistent Hashing] sorgt für eine hinreichend gleichmässige Verteilung der Schlüssel im System.
; Lastbalanzierung: Chord nutzt [http://theory.lcs.mit.edu/~karger/Papers/Talks/Hash Consistent Hashing] für eine hinreichend gleichmässige Verteilung der Schlüssel im System.
; Dezentralisierung: Alle Knoten im System sind gleichberechtigt.
; Dezentralisierung: Alle Knoten im System sind gleichberechtigt.
; Skalierbarkeit: Eine Suche benötigt <i>O(log N)</i> Hops, wobei N die Anzahl aller Knoten im System ist.
; Skalierbarkeit: Eine Suche benötigt <i>O(log N)</i> Hops, wobei N die Anzahl aller Knoten im System ist.
; Verfügbarkeit: Das System passt sich Strukturänderungen an, garantiert dabei aber, dass der für einen Schlüssel zuständige Knoten zu jeder Zeit gefunden wird.
; Verfügbarkeit: Das System passt sich Strukturänderungen an, garantiert dabei aber, dass der für einen Schlüssel zuständige Knoten zu jeder Zeit gefunden wird.
; Flexible Namenswahl: Es gibt keine Einschränkungen bezüglich der Struktur bzw. Gestalt der verwendeten Schlüssel.
; Flexible Namenswahl: Es gibt keine Einschränkungen bezüglich der Struktur bzw. Gestalt der verwendeten Schlüssel.



== Topologie ==
== Topologie ==

Revision as of 15:10, 27 February 2006

Überblick

Chord ist ein einfaches, verteiltes Suchprotokoll für Peer-To-Peer Systeme, das Schlüssel auf Knoten abbildet. Dabei passt es sich effizient an Strukturveränderungen, wie das Ausfallen oder Hinzukommen von Knoten, an und sichert die Funktionalität auch während dieser Anpassung.
Das Protokoll skaliert sowohl in Bezug auf Speicherbedarf, als auch in Bezug auf Kommunikationsaufwand logarithmisch zur Anzahl der Knoten im System.


Aufbau von Chord

System Modell

Lastbalanzierung
Chord nutzt Consistent Hashing für eine hinreichend gleichmässige Verteilung der Schlüssel im System.
Dezentralisierung
Alle Knoten im System sind gleichberechtigt.
Skalierbarkeit
Eine Suche benötigt O(log N) Hops, wobei N die Anzahl aller Knoten im System ist.
Verfügbarkeit
Das System passt sich Strukturänderungen an, garantiert dabei aber, dass der für einen Schlüssel zuständige Knoten zu jeder Zeit gefunden wird.
Flexible Namenswahl
Es gibt keine Einschränkungen bezüglich der Struktur bzw. Gestalt der verwendeten Schlüssel.

Topologie

Schlüsselverteilung im Chord Ring

Jedem Knoten und Schlüssel wird eine m-Bit lange ID zugeordnet. Diese ID wird mittels einer Basishashfunktion, wie zum Beispiel SHA-1, berechnet, indem die Hashfunktion auf die IP-Adresse des Knotens bzw. den Schlüssel selbst angewendet wird.
Die Knoten sind in einem Ring modulo 2m (Chord Ring) angeordnet.
Ein Schlüssel wird dem Knoten zugewiesen, dessen ID grösser oder gleich der ID des Schlüssels ist. Dieser Knoten wird Successor Knoten genannt.
Die einzige Funktion, die Chord nun bietet ist, den für einen gegebenen Schlüssel k zuständigen Knoten n zu finden.

Einfache Suche

Eine einfache Möglichkeit der Suche nach einem Knoten im Chord Ring, ist die lineare Suche. Jeder Knoten n kennt seinen Nachfolgeknoten n' (Successor).

Wird nun eine Suchanfrage an einen Knoten gerichtet, prüft dieser, ob sein Nachfolgeknoten für den angefragten Schlüssel zuständig ist. Falls ja, ist die Suche beendet. Falls nicht, wird die Anfrage so lange an den jeweils nachfolgenden Knoten weitergereicht, bis das Ziel erreicht ist.

n.find_successor(id)
  if ( id ∈ (n, successor] )
    return successor;
  else
    return successor.find_successor(id);

Diese Form der Suche ist zwar nicht besonders effizient, da die Länge des Suchpfades linear zur Anzahl der Knoten im System wächst. Aber sie kann jederzeit als Fallback-Variante dienen. Da minimale Vorraussetzung für die lineare Suche, dass jeder Knoten seinen Nachfolgeknoten kennt, ist damit auch die minimale Vorraussetzung für die Korrektheit des Chord Protokolls.

Einfache Suche im Chord Ring

Skalierbare Suche

Eintritt neuer Knoten

Stabilisierung

Ausfall & Replikation

Erweiterungen

Anwendungen

Referenzen