Consistent Hashing

Alle Rechner sind als Ring angeordnet (zumindest logisch, physikalisch ist die Vernetzung anders). Aus jedem Key wird mittels MD5 ein Hashwert berechnet. Jedem Knoten ist nun ein bestimmter Teil des Wertebereichs des Ergebnisses der Hashfunktion zugeordnet, zu dem der jeweilige Knoten die zugehörige Datei speichert. Eine bestimmte Anzahl der im Ring nachfolgenden Knoten speichern zudem eine Kopie, wobei die Gesamtzahl der speichernden Knoten konfigurierbar ist. Um die Ausfallsicherheit zu maximieren, werden Knoten nicht nur auf unterschiedliche Rechner und Racks, sondern auch verschiedene Rechenzentren verteilt.

Ein Beispiel für den Fall von insgesamt sechs Knoten mit redundanter Speicherung auf jeweils drei Knoten (N=3) findet sich in nebenstehender Abbildung.

Da es sich um eine heterogene Systemlandschaft handelt, bei der die Speicherkapazität der eingesetzten Knotenrechner unterschiedlich sein kann (und zudem manche Dateien häufiger nachgefragt werden als andere) nutzt Dynamo sogenannte virtuelle Knoten. Das Konzept virtueller Knoten ermöglicht, dass sich auf einem physikalischen Knoten mehrere virtuelle Knoten desselben Rings befinden können. Dies ermöglicht eine bessere Auslastung bei unterschiedlichen Speicherkapazitäten der physikalischen Knoten, da durch die Gleichverteilung der Hashfunktion die Speicherauslastung für alle Knoten gleich groß ist und so einem physischen Knoten mit höherer Speicherkapazität mehrere virtuelle Knoten zugeordnet werden können.

Sloppy Quorum und Hinted Handoff

Um die Ausfallsicherheit des Systems zu gewährleisten, wurden neben dem Parameter N (der Anzahl an Knoten, auf denen repliziert wird) noch die Parameter R (Read ‚Lesen‘) und W (Write ‚Schreiben‘) eingeführt, die ebenfalls konfigurierbar sind. Diese Parameter sind so ähnlich auch schon aus Quorumsystemen bekannt. Allerdings wurden sie hier soweit abgewandelt, dass man von sloppy ‚schlampig‘, sprechen kann. Diese legen fest, wie viele der Knoten eine Lese- oder Schreiboperation als erfolgreich melden müssen, damit die Aktion als erfolgreich gilt. In der Standardkonfiguration ist das Tupel (N, R, W) mit den Werten (3, 2, 2) belegt. Dies bedeutet, dass

• jede Datei dreimal gespeichert wird,
• ein Lesezugriff als erfolgreich gilt, sobald mindestens zwei Knoten die Datei zurückliefern und
• ein Schreibzugriff als erfolgreich gilt, sobald mindestens zwei Knoten den Zugriff als erfolgreich melden.

Die Parameter erlauben es auch einer Anwendung, das System genau für ihren Bedarf anzupassen. Beispielsweise würde eine Konfiguration von (3, 1, 3) dafür sorgen, dass man eine Art Lesepuffer realisiert hat (nur ein Knoten muss für ein Lesezugriff antworten, alle Kopien müssen immer erfolgreich geschrieben werden, da N = W), wohingegen ein System mit W = 1 für schnellstmögliche Schreibzugriffe optimiert ist. Die Konfiguration (1, 1, 1) wiederum realisiert einfach ein ganz normales (allerdings auch nicht hoch verfügbares) Dateisystem (entsprechend mit Replikation auch als (2,2,2), (3,3,3) usw.).

Falls der Koordinatorknoten (der Knoten, in dessen Bereich der Hashwert eigentlich fällt) nicht verfügbar ist, greift das sogenannte Hinted Handoff: Wenn im Beispiel der obigen Abbildung der Hashwert 3 und Knoten A nicht verfügbar wäre, so würde die Kopie stattdessen an Knoten D weitergegeben (Handoff) mit dem Vermerk (Hinted), dass diese Datei eigentlich zu Knoten A gehört. Darum speichert D diese Kopien auch in einer separaten lokalen Datenbank und fragt von Zeit zu Zeit bei A nach, ob der Knoten wieder verfügbar ist. Sobald dies der Fall ist, werden alle hinted-Kopien an A übertragen. Nach erfolgreichem Transfer kann D das hinted-Objekt löschen.

Vector Clocks

Durch die Sloppy-Quorum-Konfiguration von (3, 2, 2) kann es unter Umständen zu unterschiedlichen Versionen kommen. Da Updates auch im Hintergrund weitergegeben werden dürfen (z. B. an den dritten Knoten), kann es sein, dass nach einem erfolgreichen Schreibzugriff (der aber nur zwei Knoten erreicht hat) direkt ein Lesezugriff folgt, der nun möglicherweise zwei verschiedene Versionen zurückliefert. Um diesen Konflikt zu lösen, gibt es die sogenannten Vektoruhren, auch Vector Clocks genannt, die im Prinzip einfach nur Versionszähler sind. Jede Datei enthält einen Vektor aus Tupeln der Form (Knoten-ID, Versionsnummer), wobei bei einem Update jeder Knoten immer seine in der Datei enthaltene Versionsnummer um eins erhöht. In dem beschriebenen Problemfall würde nun der Koordinator beispielsweise für denselben Knoten einmal die Version 14 und einmal Version 15 zurückbekommen und anhand dieser Versionsnummern erkennen können, welche Version die neueste ist. Dementsprechend würde der anfragende Client auch nur die neueste Version mit der Versionsnummer 15 zurückgeliefert bekommen.

Problematisch wird es eigentlich nur, wenn der eigentliche Koordinator aus irgendeinem Grund ausgefallen ist und es gleichzeitig zu parallelem Zugriff kommt. Beispielsweise könnte sich folgender Ablauf ergeben:

1. Knoten A koordiniert ein Write ⇒ ([A,1]).
2. Knoten A koordiniert ein Write ⇒ ([A,2]).
3. Knoten A fällt aus.
4. Knoten B koordiniert ein Write ⇒ ([A,2],[B,1]). Gleichzeitig koordiniert Knoten C ein Write ⇒ ([A,2],[C,1]).
5. Knoten A ist wieder verfügbar.
6. Knoten A koordiniert ein Read und bekommt die Version ([A,2],[B,1]) und die Version ([A,2],[C,1]) zurückgeliefert.

In diesem Fall ist nicht entscheidbar, ob die Version von B oder C die neuere ist, und die Auflösung wird in die Anwendungsebene verschoben, der Client erhält beide Versionen. Im Beispiel des Shopping Cart Service würden beispielsweise beide Versionen vereinigt werden und von Knoten A die neue Version ([A,3],[B,1],[C,1]) geschrieben werden. Dies ist aber abhängig von der jeweiligen Anwendung. Sofern eine Anwendung es vorzieht, sich nicht um Fehlerauflösung zu kümmern, so gibt es auch einfache last-write-wins-Strategien vorimplementiert.

Anti-Entropie durch Merkle Trees

Durch das Hinted Handoff können weitere Probleme entstehen. Beispielsweise ist folgender Ablauf möglich:

1. Knoten A fällt aus, Knoten B, C und D müssen neue Replikas speichern.
2. Ein Write wird von B koordiniert, D markiert die Datei als Hinted Handoff.
3. Knoten D fällt aus.
4. Knoten A ist wieder verfügbar, bekommt aber, weil D offline ist, die Kopie nicht zurückgespielt.

Problem: A bekommt gar nicht mit, dass es eine alte Version hat und es zu dem Zeitpunkt nur N−1 Kopien gibt. Um dieses Problem zu umgehen, vergleicht A beim Neustart seine Kopien mit denen von B und C. Um allerdings den Traffic und die Rechenbelastung möglichst gering zu halten, werden dafür sogenannte Merkle Trees verwendet. Merkle Trees sind Bäume, die in ihren Blättern Hashwerte der Dateien haben, in der Wurzel einen Hash über alle Hashs und in den Knoten dazwischen entsprechende Hashs für den Teilbaum. Dadurch müssen A und B zunächst nur den Wurzelhash austauschen und können dann feststellen, ob ihre Kopien alle identisch sind oder nicht. Falls nicht, wird der Baum traversiert, bis das schuldige Blatt gefunden ist. Anschließend kann entsprechend über die Vector Clocks geschaut werden, welches die neuere Version ist, und diese entsprechend kopiert werden.

Im Fall, dass (analog zum Beispiel) die Netzwerkverbindung zu A abreißt und A das direkt gar nicht mitbekommt, wird entweder A beim nächsten Read mit Hilfe der Vector Clocks feststellen, dass eine alte Version vorliegt, oder im Rahmen der regelmäßigen Gossipnachrichten, da dort auch die Hashs der Merkle Trees übermittelt werden.

Gossip-basiertes Protokoll

Damit bei einem temporären Ausfall eines Knotens nicht jedes Mal die gesamte Kreisstruktur neu aufgebaut werden muss, gibt es die Hinted Handoffs. Allerdings muss es auch möglich sein, Knoten dauerhaft aus dem Netz zu entfernen oder hinzuzufügen. Um dies einfach zu ermöglichen, wird per Kommandozeilentool oder Browser von einem Administrator nach Login auf einem beliebigen Knoten ein Eintrag in einer entsprechenden Konfigurationsdatei vorgenommen. Diese Änderung wird dann an alle anderen Knoten des Rings über ein Gossip-basiertes Protokoll kommuniziert. Über dieses Protokoll wird sowohl die Aufteilung der virtuellen Knoten auf den Rechnern als auch eine Liste der Rechner ständig aktuell gehalten.

Ein einfaches Beispiel für das explizite Hinzufügen von Knoten X zu Netzwerk ABCD wäre dann wie folgt:

Die Reihenfolge bei der Kommunikation (wer sich mit wem austauscht) ist dabei zufällig und es muss sich nicht bei jeder Kommunikation eine Änderung ergeben (im Beispiel: Schritt 4).

Wird ein Knoten entfernt oder hinzugefügt, muss sich zwangsläufig auch die Aufteilung der virtuellen Knoten auf die physikalischen Rechner verändern, wofür es mehrere Verfahren gibt. Die einfachste Variante davon ist – im Fall einer nicht heterogenen Systemlandschaft – dass auf jedem physikalischen Rechner die gleiche Anzahl an gleich großen virtuellen Knoten liegen soll. Beim Entfernen eines Knotens werden somit die betreffenden virtuellen Knoten auf zufällig ausgewählte physikalische Knoten kopiert, die weniger virtuelle Knoten als der Rest des Rings besitzen. Umgekehrt übernimmt ein neu hinzukommender Knoten virtuelle Knoten von voll ausgelasteten Knoten – ebenfalls zufällig ausgewählt.