Amazon Dynamo
Amazon Dynamo ist genau wie Amazon S3 oder das Google File System ein verteiltes Storagesystem und ist damit in gewisser Weise ebenso im Kontext von Infrastructure as a Service einzuordnen. Vergleichbar dem Google File System ist auch Dynamo für einen konkreten Anwendungsfall optimiert, der sich aus der Natur der internen Amazonservices ergibt.
Aufbau
Dynamo baut auf einem Netz von handelsüblichen Rechnern auf, die alle völlig gleich berechtigt agieren, d.h. es gibt keine zentrale Steuerung oder Verwaltung, jeder Knoten kann jede Aufgabe wahrnehmen. Dies wurde gemacht, um die Skalierbarkeit des Systems zu sichern.
Dienste wie der Shopping Cart Service (der Dienst, der den Warenkorb verwaltet) erwarten, dass das System immer geschrieben werden kann, hoch verfügbar ist und geringe Latenzzeiten aufweist. Da die in den ACID-Kriterien definierten Eigenschaft der Konsistenz und hohe Verfügbarkeit gegensätzlich sind, wurde - im Gegensatz zu traditionellen Datenbanksystemen - diese Eigenschaft zu einer eventual consistency ("vielleicht ist es irgendwann konsistent") aufgeweicht. Eine weitere Eigenschaft war, dass überwiegend kleine (weniger als 1MB große) Dateien in Form von key-value-Paaren gespeichert werden sollen. Komplizierte Datenbankanfragen müssen nicht unterstützt werden.
Um die gewünschten Eigenschaften zu erreichen, wurde eine Reihe bereits vorher in anderem Zusammenhang bekannter Verfahren genutzt:
- Consistent Hashing
- Sloppy Quorum und Hinted Handoff
- Vector Clocks
- Anti-Entropie durch Merkle Trees
- Gossip-basiertes Protokoll
Consistent Hashing
Alle Rechner sind in Form eines Rings angeordnet (zumindest virtuell, physikalisch ist die Vernetzung anders). Aus jedem Key wird nun mittels MD5 ein Hashwert berechnet. Jedem Knoten ist nun ein bestimmter Wertebereich der Hashfunktion zugeordnet und dementsprechend wird dort sowie auf den N-1 nachfolgenden Knoten (N ist konfigurierbar) jeweils eine Kopie der Datei gespeichert. Da es sich um eine heterogene Systemlandschaft handelt und manche Dateien häufiger nachgefragt werden als andere, nutzt Dynamo sogenannte virtuelle Knoten. D.h. in dem Ring werden virtuelle Knoten angeordnet, die dann wiederum physikalischen Knoten zugeordnet werden. Dabei ist es normal, dass ein Rechner mehrere virtuelle Knoten beherbergt. Um die Ausfallsicherheit zu maximieren, werden Knoten nicht nur auf unterschiedliche Rechner und Racks sondern sogar auch verschiedene Rechenzentren verteilt.
Ein Beispiel für den Fall N = 3 findet sich rechts im Bild.
Sloppy Quorum und Hinted Handoff
Um sicherzustellen, dass auf das System immer zugegriffen werden kann, 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 (engl.: "schlampig") sprechen kann. In der Standardkonfiguration ist das Tupel (N,R,W) mit den Werten (3,2,2) belegt. Dies hat zur Folge, dass
- jede Datei dreimal gespeichert wird,
- ein Schreibzugriff als erfolgreich gilt, sobald mindestens zwei Knoten den Write als erfolgreich melden und
- ein Lesezugriff als erfolgreich gilt, sobald mindestens zwei Knoten die Datei zurückliefern.
Die Parameter erlauben es auch jeder Anwendung, das System genau für ihren Bedarf anzupassen. Bspw. 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 read antworten, alle Kopien müssen immer gleich sein: N = W), wohingegen ein System mit W = 1 das wohl schnellste System für Writes sein dürfte. (3,3,3) wiederum realisiert einfach ein ganz normales (allerdings auch nicht hoch verfügbares) Dateisystem.
Falls der Koordinatorknoten (der Knoten, in dessen Bereich der Hashwert eigentlich fällt) nicht verfügbar ist, greift das sogenannte Hinted Handoff: Analog zum Bild die Annahme, dass der Hashwert 3 sei. Ist nun Knoten A nicht verfügbar, so wird 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.
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 2 Knoten erreicht hat) direkt ein Lesezugriff kommt, der nun möglicherweise zwei verschiedene Versionen zurückliefert. Um diesem Problem zu begegnen, gibt es die sogenannten Vector Clocks, 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 immer die Versionsnummer um eins erhöht wird. In dem beschriebenen Problemfall würde nun der Koordinator bspw. einmal Version 14 und einmal Version 15 zurückbekommen und sofort erkennen, dass Version 15 die neueste ist. Dementsprechend würde der anfragende Client auch nur die Version 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. Bspw. könnte sich folgender Ablauf ergeben:
- Knoten A koordiniert ein Write => ([A,1]).
- Knoten A koordiniert ein Write => ([A,2]).
- Knoten A fällt aus.
- Knoten B koordiniert ein Write => ([A,2],[B,1]). Gleichzeitig koordiniert Knoten C ein Write => ([A,2],[C,1]).
- Knoten A ist wieder verfügbar.
- Knoten A koordiniert ein Read und bekommt die Version ([A,2],[B,1]) und die Version ([A,2],[C,1]) zurückgeliefert.
Problem: Sowohl die Änderung von B als auch die von C ist von Bedeutung.
Lösung: Die Auflösung wird in die Anwendungsebene verschoben und der Client erhält beide Versionen. Im Beispiel des Shopping Cart Service würden bspw. 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. Bspw. ist ja folgender Ablauf möglich:
- Knoten A fällt aus, Knoten B, C und D müssen neue Replika speichern.
- Ein Write wird von B koordiniert, D markiert die Datei als Hinted Handoff.
- Knoten D fällt aus.
- 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.
Gossip-basiertes Protokoll
Damit bei einem temporären Ausfall eines Knotens nicht jedesmal die gesamte Kreisstruktur neu aufgebaut werden muss, gibt es ja die Hinted Handoffs. Allerdings muss es auch möglich sein, Knoten dauerhaft aus dem Netz zu entfernen oder hinzuzufügen. Um dies möglichst einfach zu ermöglichen, wird dies explizit per Kommandozeilentool oder Browser von einem Administrator gemacht: Login auf einem beliebigen Knoten und dort ins Log schreiben, dass Knoten X jetzt auch verfügbar ist. Untereinander kommunizieren die Knoten über ein Gossip-basiertes Protokoll, über das sowohl die Aufteilung der virtuellen Knoten auf die Rechner als auch eine Liste der Rechner ständig aktuell gehalten wird.
Ein einfaches Beispiel für das explizite Hinzufügen von Knoten X zu Netzwerk ABCD wäre dann wie folgt:
| Schritt | Aktion | Tabelle von A | Tabelle von N | Tabelle von C | Tabelle von D | Tabelle von X |
|---|---|---|---|---|---|---|
| 1 | Ausgangszustand | ABCD | ABCD | ABCD | ABCD | X |
| 2 | X wird bei A angemeldet | ABCDX | ABCD | ABCD | ABCD | ABCDX |
| 3 | A kommuniziert mit B | ABCDX | ABCDX | ABCD | ABCD | ABCDX |
| 4 | C kommuniziert mit D | ABCDX | ABCDX | ABCD | ABCD | ABCDX |
| 5 | B kommuniziert mit D | ABCDX | ABCDX | ABCD | ABCDX | ABCDX |
| 6 | A kommuniziert mit C | ABCDX | ABCDX | ABCDX | ABCDX | ABCDX |
| 7 | Endzustand erreicht | ABCDX | ABCDX | ABCDX | ABCDX | ABCDX |
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).