Content Addressable Network

Content Addressable Network (kurz CAN) gehört zu den strukturierten Peer-to-Peer-Netzen, welche auch unter Distributed Hash Table bekannt sind. Im Grunde stellt CAN eine Implementation dieser verteilten Hashtabellen dar. Vorteile solcher strukturierten Netze sind unter anderem die effiziente und zielgerichtete Suche. Existiert der gesuchte Inhalt im Netz, wird dieser auch garantiert gefunden.^[1]

Grundlegendes Design

CAN stellt ein logisches Overlay-Netz dar, welches nicht dem physikalischen Netz entsprechen muss. Die logische Struktur bildet einen d-dimensionalen Torus in welchem Key-Value Paare (K, V) in den Punkten des Koordinatensystems gespeichert werden. Für die Bestimmung des Punktes wird eine, unter allen Knoten bekannte, Hash-Funktion verwendet. Den Koordinatenraum des Torus teilen sich alle Knoten, welche dem CAN beiwohnen, in sogenannte Zones auf. Dementsprechend besitzt ein Knoten die Key-Value Paare deren Punktkoordinaten in der Zone des Knotens liegen. Dadurch, dass die Knoten nur die Adressen und Wertebereiche ihrer direkten Nachbarn kennen, muss für die Suche eines Inhalts, welcher nicht in direkter Nachbarschaft, bzw. in der eigenen Zone liegt, eine Anfrage durch das Netz geroutet werden.^[1]^[2]

Routing

Um eine Suchanfrage durch das Netz zu lenken wird diese an den Nachbarn weitergeleitet, welcher den kürzesten euklidischen Abstand zum Ziel hat. Dabei ist es wichtig zu wissen wer die Nachbarn sind. In einem d-dimensionalen Koordinatensystem sind zwei Knoten Nachbarn wenn sich ihre Koordinaten der Zonen in d - 1 Dimensionen überschneiden. Somit ist es möglich, dass ein Knoten mehrere Nachbarn und damit auch mehrere Wege zum Ziel hat. Das macht diese Implementation sehr robust. Das bedeutet, insofern ein Knoten ausfällt, wird die Anfrage an den nächstbesten Nachbarn weitergeleitet. Gleiches gilt auch, wenn mehrere Knoten ausfallen. Fallen alle direkten Nachbarn aus, nutzt der Knoten eine Ringsuche. Diese Ringsuche ist ein statusloses, kontrolliertes Fluten per Unicast im Mesh-Netz des CAN. Damit soll ein Knoten gefunden werden, welcher näher am Ziel ist als der suchende Knoten um die Anfrage weiterzuleiten.^[1]^[3]

durchschnittliche Pfadlänge: $\left({\frac {d}{4}}\right)\cdot \left(n^{\frac {1}{d}}\right)$ ; wobei $n={\text{AnzahlKnoten}}$ , $d={\text{AnzahlDimension}}$
ansteigende Pfadlänge beim Hinzufügen eines Knoten: $O\left(n^{\frac {1}{d}}\right)$

Aufbau der CAN-Struktur

Hinzufügen eines Knotens:

Finden eines bereits im CAN befindlichen Knotens
Finden eines Knotens, welcher seine Zone aufteilt
Benachrichtigen der benachbarten Knoten über neuen Nachbarn

Entfernen eines Knotens:

Zusammenfügen der Zonen; Update der Routing-Tabellen

Ausfall von Nodes:

Takeover-Message

Finden eines Knotens

Um dem CAN beizutreten, muss der Knoten, welcher beitreten möchte, einen bereits im CAN befindliche Bootstrap-Knoten ausfindig machen. Das geschieht mittels eines Bootstrap-Algorithmus wie in P.Francis: Yoid: Extending the Internet Multicast Architecture^[4] beschrieben.^[1] Dadurch erhält der Knoten eine IP eines solchen Bootstrap-Knotens, welcher eine IP-Adressen Liste im CAN befindlicher Knoten hat und zurückliefert. Mit dieser Liste kann der neue Knoten nun beginnen eine Zone zu finden.

Finden der Zone

Mit der, unter Finden eines Knoten erwähnten, IP-Liste hat der neue Knoten seine Einstiegspunkte in das CAN. Danach wählt der neue Knoten einen zufälligen Punkt im Koordinatensystem und sendet einen JOIN-Request mit den Koordinaten des Punktes als Ziel. Diese Anfrage wird nun über die CAN-Knoten und den Routing-Algorithmus verteilt bis zum Knoten mit dem Punkt in seiner Zone. Dieser Knoten teilt seine eigene Zone auf. Diese Teilung wird durch eine spezielle Achsenreihenfolge realisiert.^[1] Zunächst wird eine Zone entlang der X-Dimension geteilt, dann in Y-Dimension. Das ist auch für die spätere Wiederzusammenführung von Zonen wichtig. Nach der Teilung werden die jeweilige Key-Value Paare an den neuen Knoten übergeben.

Einfügen ins Routing

Nach der Teilung, lernt der neue Knoten die IP-Adressen der direkten Nachbarn vom vorherigen Besitzer der Zone. Nachdem die beiden Knoten ihre neuen Nachbarn kennen, müssen diese über die Teilung informiert werden. Es wird also umgehend eine UPDATE-Message an die umliegenden Nachbarn geschickt, damit diese ihre eigenen Routing-Tabellen updaten können. Das Hinzufügen eines Knoten beeinträchtigt also offensichtlich nur einen kleinen Anteil aller Knoten im CAN, d. h. nur die Knoten, welche die geteilte Zone als direkten Nachbarn haben. Das ist bspw. vorteilhaft, wenn sehr viele Knoten verwaltet werden müssen. Dabei ist entscheidend, dass die Anzahl der Nachbarn eines Knotens nur von der Dimension und nicht von der Gesamtanzahl aller Knoten abhängt.^[1]

Beeinträchtigte Knoten durch Hinzufügen eines Knotens: $O({\text{AnzahlDimensionen}})$ ^[1]

Verlassen des CAN

Möchte ein Knoten das CAN verlassen, existieren zwei Möglichkeiten. Erstens, der Knoten überträgt seine Zone an einen seiner Nachbarn (freie Wahl). Entsteht daraus eine valide Zone (Verteilungsgleichgewicht -- die Zonen sind alle annähernd gleich), werden die Key-Value Paare übertragen und der Knoten kann das CAN verlassen. Zweitens, der Knoten findet keinen geeigneten Nachbarn und reicht seine Zone an den Nachbarn mit der zur Zeit kleinsten Zone weiter. Dieser Nachbar muss dann für eine kurze Zeit zwei Zonen verwalten. Treten gleichzeitig mehrere solcher Fälle ein, kann es zu einem Fragmentieren des Wertebereichs kommen. Um dies zu vermeiden, gibt es einen Hintergrundalgorithmus -- Background Zone Reassignment -- welcher im Hintergrund die Zonen neu verteilt.^[1] Wichtig ist beim Verlassen des CAN, dass die Knoten das Netz graceful verlassen müssen. Das bedeutet, sie müssen erst ihre Zone inkl. Key-Value Paare an einen benachbarten Knoten übergeben.^[3]

Ausfallsicherheit des CAN

Natürlich muss das CAN auch gegen Netzwerkfehler und Ausfällen von anderen Knoten geschützt sein. Dieser Schutz zeigt sich in einer Art Takeover-Prozedur.^[1] Unter normalen Umständen sendet jeder Knoten regelmäßig Update-Nachrichten an seine Nachbarn, um zu zeigen, dass er selbst noch aktiv und erreichbar ist. Das Ausbleiben eines Updates signalisiert einen Fehler eines Knotens. Diese implizite Signalisierung führt zu einem sofortigen Takeover der benachbarten Knoten. Andernfalls wären die Key-Value Paare der Zone verloren. Jeder Nachbar führt diesen Algorithmus unabhängig von den anderen Nachbarn aus und startet einen Takeover-Timer in Proportion der eigenen Zonengröße. Ist dieser Timer abgelaufen, sendet der Knoten eine TAKEOVER-Message an alle Nachbarn des verloren gegangenen Knotens. Erhält ein Knoten eine solche Nachricht gleicht dieser die in der Nachricht enthaltene Zonengröße mit seiner eigenen ab. Ist diese kleiner als seine eigene, stoppt er die Takeover-Prozedur. Andernfalls antwortet er mit einer eigenen TAKEOVER-Message. Auf diesem Weg wird am effektivsten ein aktiver, benachbarter Knoten mit der aktuell kleinsten Zone gefunden, welcher die Zone des fehlerhaften Knotens übernimmt. Auch in diesem Fall kann es passieren, dass ein Knoten mehrere Zonen gleichzeitig verwalten muss. Auch hier greift wieder der Background Zone Reassignment-Algorithmus.

Erweiterungen im Design

Betrachtet man das Grunddesign des CAN, wird schnell deutlich, dass die Freiheit des Overlay-Netzes gegenüber dem physikalischen Netz nicht unbedingt ein Vorteil sein muss. Grund dafür ist die Möglichkeit, dass die physikalischen Knoten auf verschiedenen Kontinenten und damit auch hinter mehreren IP-Hops liegen. Daraus kann man schließen, dass trotz eines Nachbarschaftsverhältnisses auf Overlay-Ebene sehr große Verzögerungen auf physikalischer Ebene auftreten können.

Durchschnittliche Verzögerung einer Suche:^[1] $\operatorname {avg} ({\text{NumberOfCANHops}})\cdot \operatorname {avg} ({\text{LatencyPerHop}})$

Um diese Latenz zu verringern gibt es zwei Ansatzpunkte:^[1]

Reduzierung der Pfadlänge
Reduzierung der Latenz an den Hops

Multidimensionale Betrachtung

Eine Möglichkeit die Pfadlänge zu reduzieren, ist die Erhöhung der Dimensionen des Koordinatensystems. Gleichzeitig wird die Gesamtverzögerung dadurch verringert, denn jeder Knoten hat mit steigender Dimension mehr Nachbarn. Weiterhin wird auch die Ausfallsicherheit erhöht, denn einem Knoten stehen bei einem Ausfall eines direkten Nachbarn mehrere Alternativen zur Verfügung. Im Umkehrschluss bedeutet das aber auch, dass die Routing-Tabellen minimal größer werden. Somit kann man für die Skalierung der Pfadlänge die Formel aus Routing adaptieren und sagen, dass für diese Betrachtungsweise eine zusätzliche Abhängigkeit von der Anzahl der Dimensionen gilt.

Skalierung der Pfadlänge: $O\left(d\cdot n^{\frac {1}{n}}\right)$

Realities

Wenn die Dimensionen des Koordinatenraumes nicht begrenzt werden, ist auch die Anzahl der Koordinatenräume pro Knoten unbegrenzt. Das bedeutet, dass jeder Knoten mehrere Koordinatenräume und somit auch mehrere Zonen zugewiesen bekommt, welche voneinander unabhängig sind. Diese verschiedenen Koordinatenräume nennt man Realities. Bei einer Anzahl von r Realities ist ein Knoten r Koordinatenräumen zugeordnet und hat r Nachbarschaftslisten, also pro Koordinatenraum eine Liste. Vorteil des Ganzen ist die erhöhte Datenverfügbarkeit aufgrund von Replikationen der Hash-Tabellen in jeder Reality. Es ergeben sich somit noch mehr Wege durch das CAN zum Ziel. Dadurch wird die durchschnittliche Pfadlänge verkürzt, weil der Knoten im Falle einer Paketweiterleitung zunächst in jeder Reality prüft, welcher Nachbarknoten dem Ziel am nächsten ist.^[1]^[2]

Multiple Hash-Funktionen

Ein anderer Ansatz zur Reduzierung von Pfadlängen und Erhöhung der Verfügbarkeit wäre die Nutzung von mehreren Hash-Funktionen auf demselben Schlüssel. Nutzt man eine Anzahl von k Hash-Funktionen, kann man einen einzigen Schlüssel eines Key-Value-Paares in k Punkten des Koordinatensystems speichern. Somit verteilt sich der Schlüssel auch auf verschiedene Knoten und es ergibt sich eine höhere Replikation der Daten sowie eine Verkürzung der durchschnittlichen Pfadlänge und Latenz. Zu Bedenken wäre, dass sich dadurch aber die Größe der Key-Value Datenbank erhöht, da jeder Knoten eine größere Menge an Schlüsseln verwalten muss und sich der Verkehr für Anfragen um den Faktor k erhöht.

In A Scalable Content-Addressable Network werden noch weitere Ansätze zu den oben genannten Punkten erwähnt und ausgeführt. Zudem ist eine tabellarische Gegenüberstellung aller Umsetzungen der Designerweiterungen aufgeführt.^[1]

Siehe auch

Einzelnachweise

↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker: A Scalable Content-Addressable Network. Aug. 2001, SIGCOM'01.
↑ ^a ^b D. Korzun, A. Gurtov: Structured Peer-to-Peer Systems: Fundamentals of Hierarchical Organization, Routing, Scaling, and Security. Springer Science+Business Media, New York 2013.
↑ ^a ^b Konrad Miller: Vorlesung Distributed Operating Systems, Juli 2009.
↑ P. Francis: Yoid: Extending the Internet Multicast Architecture. YOID-Webseite, Unpublished Paper Apr. 2000.

[Quelle1-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker: A Scalable Content-Addressable Network. Aug. 2001, SIGCOM'01.

[Quelle2-2] D. Korzun, A. Gurtov: Structured Peer-to-Peer Systems: Fundamentals of Hierarchical Organization, Routing, Scaling, and Security. Springer Science+Business Media, New York 2013.

[Quelle3-3] Konrad Miller: Vorlesung Distributed Operating Systems, Juli 2009.

[Quelle4-4] P. Francis: Yoid: Extending the Internet Multicast Architecture. YOID-Webseite, Unpublished Paper Apr. 2000.

[1]

[2]

[3]

[4]