Chord

Ü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

Consistent Hashing sorgt 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.

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 2^m (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.