Dein Cart-Service schreibt bei jedem Klick und darf im Dezember keinen einzigen Add-to-Cart ablehnen. In der Lastspitze fällt eine Platte aus, ein Rack-Switch flappt, vielleicht verschwindet ein Rechenzentrum vom Netz. Eine einzelne primäre Datenbank macht aus jedem dieser Fälle einen Ausfall.
Amazons Dynamo-Paper von 2007 beschrieb einen Store, der trotz all dem weiter Schreibzugriffe annimmt; Cassandra und Riak KV haben die meisten seiner Cluster-Ideen übernommen. Dieser Beitrag entwirft einen Store im Dynamo-Stil von der API bis zur Storage-Engine, vergleicht reale Systeme und zeichnet das Ergebnis.
Anforderungen und API
Dynamos Schnittstelle besteht aus zwei Operationen:
get(key) -> [value, ...], context
put(key, context, value) -> ok
get kann widersprüchliche Versionen plus einen opaken Context zurückgeben; der nächste put reicht ihn zurück und sagt damit, welche Versionen er ersetzt. Die Anforderungen:
- Immer schreibbar, auch wenn Nodes oder Verbindungen ausgefallen sind.
- Vorhersagbare Tail Latency. Die Beispiel-SLA des Papers sind 300 ms für 99,9 % der Requests bei einer Spitze von 500 Requests pro Sekunde.
- Kleine Werte, einzelne Keys: Objekte meist unter 1 MB, keine Operationen über mehrere Keys.
- Inkrementelle Skalierung, ein Node nach dem anderen.
Dimensionierung, bei 1-KB-Werten und halb vollen Platten als Reserve für Compaction: 1 Milliarde Keys sind 1 TB, mit drei Kopien 3 TB, also sechs Nodes mit je 1 TB, wie im Ring des Diagramms. Bei 30.000 Schreibvorgängen pro Sekunde bedeuten drei Kopien 90.000 Replikat-Schreibvorgänge, also 15.000 pro Node.
CAP und PACELC kurz erklärt
CAP besagt, dass ein Store bei einer Netzwerkpartition einige Requests ablehnen oder veraltete Lesezugriffe riskieren muss; Dynamo bleibt verfügbar. Daniel Abadis PACELC (2012) ergänzt, dass du auch ohne Partition Latenz gegen Konsistenz tauschst; er ordnet die Standardkonfigurationen von Dynamo, Cassandra und Riak als PA/EL ein.
Partitionierung mit Hash-Ring und virtuellen Nodes
Dynamo hasht jeden Key mit MD5 auf eine 128-Bit-Position im Ring, und der Key gehört zum ersten Node im Uhrzeigersinn. Wenn ein Node beitritt oder geht, verschieben sich nur benachbarte Bereiche statt fast aller Keys wie bei hash(key) % N; das Consistent-Hashing-Diagramm zeigt, wie.
Eine Position pro Node verteilt die Daten ungleich, deshalb bekommt jeder Node viele, genannt virtuelle Nodes oder Tokens. Cassandra 5.0 liefert 16 Tokens pro Node aus; Riaks Ring hat standardmäßig 64 Partitionen. Du gibst Range Scans auf: Benachbarte Keys landen auf verschiedenen Nodes, wie das Database-Sharding-Diagramm erklärt.
Replikation und Preference Lists
Jeder Key liegt auf N Nodes: dem Koordinator (dem ersten Node im Uhrzeigersinn) und den nächsten N − 1 verschiedenen physischen Nodes. Die Preference List des Keys läuft über diese hinaus weiter, sodass Ersatz bereitsteht, wenn ein Replikat ausfällt. Verteile Replikate über Fehlerdomänen: Dynamo verteilte jede Liste über Rechenzentren, und Cassandras NetworkTopologyStrategy verteilt sie über Racks. Jedes Replikat nimmt Schreibzugriffe an, anders als bei den Leader-basierten Setups im Database-Replication-Diagramm.
Quorums: R + W > N
Der Koordinator sendet jeden Schreibvorgang an alle N Replikate und antwortet nach W Bestätigungen; ein Lesevorgang antwortet nach R Antworten. Wenn R + W > N, teilen sich jede Lesemenge und jede bestätigte Schreibmenge mindestens einen Node.
| N, R, W | R + W > N | Was du bekommst | Was du zahlst |
|---|---|---|---|
| 3, 2, 2 | Ja | Lesezugriffe sehen den letzten bestätigten Schreibvorgang; ein Replikat darf ausfallen | Jeder Request wartet auf die zweitschnellste Antwort |
| 3, 1, 3 | Ja | Schnelle Lesezugriffe von jedem Replikat | Schreibvorgänge warten auf alle drei |
| 3, 1, 1 | Nein | Niedrigste Latenz, höchste Verfügbarkeit | Lesezugriffe können veraltet sein |
| 5, 3, 3 | Ja | Zwei Replikate dürfen ausfallen | Fünf Kopien jedes Werts |
Die gängige Konfiguration im Dynamo-Paper war (3, 2, 2), und leselastige Services wie der Produktkatalog nutzten R = 1, W = N. Cassandra setzt pro Request ein Consistency Level, von ONE bis ALL; QUORUM für Lesen und Schreiben ergibt R + W > N.
Überlappung ist keine Linearisierbarkeit. Ein Schreibvorgang, der ein Replikat erreicht und dann scheitert, kann in einem Lesevorgang auftauchen und im nächsten verschwinden; Cassandras standardmäßiger blockierender Read Repair verhindert das bei Quorum-Lesezugriffen. Compare-and-Set braucht Konsens, etwa in Cassandras Lightweight Transactions oder in einem Raft-basierten Store.
Konflikte: Last Write Wins, Vector Clocks oder CRDTs
Gleichzeitige Schreibvorgänge über verschiedene Replikate hinterlassen zwei Versionen. Drei Auswege:
| Strategie | Wie sie auflöst | Kann sie Updates verlieren? | Verwendet von |
|---|---|---|---|
| Last Write Wins | Der höchste Timestamp gewinnt | Ja, still; Clock Skew bestimmt den Gewinner | Cassandra, DynamoDB Global Tables, Riak bei entsprechender Konfiguration |
| Vector Clocks | Behält gleichzeitige Versionen; der Client führt zusammen | Nein, aber jeder Client muss zusammenführen | Dynamo, Riak (Dotted Version Vectors) |
| CRDTs | Datentypen, deren Merges immer konvergieren | Nein, bei den unterstützten Typen | Riak Counter, Sets und Maps |
Eine Vector Clock ist eine Liste von (Node, Zähler)-Paaren. Eine Version, deren Zähler alle kleiner oder gleich denen einer anderen sind, ist ein Vorfahr und kann weg; sonst bleiben beide. Der Cart-Service führte widersprüchliche Warenkörbe zusammen, daher gingen hinzugefügte Artikel nie verloren, gelöschte konnten aber zurückkommen. Konflikte waren selten: Über 24 Stunden sahen 99,94 % der Cart-Requests genau eine Version. CRDTs verlagern das Zusammenführen in den Datentyp selbst; kollaborative Editoren auf CRDT-Basis wenden dieselbe Idee auf gemeinsamen Text an.
Fehlerbehandlung: Hinted Handoff, Repair und Gossip
Sloppy Quorum und Hinted Handoff. Dynamo nutzt die ersten N gesunden Nodes der Preference List: Ist C ausgefallen, übernimmt D die Kopie von C mit einem Hint und gibt sie zurück, wenn C wieder da ist. Schreibvorgänge funktionieren weiter, aber ein Lesevorgang von B und dem wiederhergestellten C kann dann einen Schreibvorgang verpassen, den nur A und D bestätigt haben. Cassandra hält Quorums strikt: Hints zählen nur bei ANY zum Consistency Level und enden, nachdem ein Node 3 Stunden ausgefallen war (max_hint_window).
Read Repair und Anti-Entropy. Wenn Antworten voneinander abweichen, schreibt der Koordinator die neueste Version auf veraltete Replikate zurück. Für kalte Daten vergleichen Replikate Merkle-Trees pro Key-Bereich und synchronisieren nur die abweichenden Bereiche. Cassandras Doku empfiehlt, auf jedem Node mindestens alle 7 Tage nodetool repair auszuführen: Tombstones werden nach gc_grace_seconds (standardmäßig 10 Tage) entfernt, und ein nicht repariertes Replikat kann gelöschte Daten zurückbringen.
Gossip und Failure Detection. Jede Sekunde tauscht jeder Node Mitgliedschafts- und Token-Zustand mit einem zufälligen Peer aus; allen bekannte Seed-Nodes verhindern, dass der Ring sich aufspaltet. Cassandras Phi-Accrual-Detektor markiert einen Peer als ausgefallen, wenn der Verdacht phi_convict_threshold (Standard 8) überschreitet.
Der Schreibpfad: Commit Log, Memtable, SSTables
Cassandras Storage-Engine ist ein auf Schreiben optimierter Log-Structured-Merge-Tree (LSM):
- Den Schreibvorgang an das Commit Log anhängen. Standardmäßig (
periodic) bestätigt Cassandra sofort und synchronisiert alle 10 Sekunden, sodass ein Absturz dieses Fenster verlieren kann. - Ihn in die Memtable einfügen, eine sortierte Struktur im Speicher.
- Eine volle Memtable in eine unveränderliche, sortierte SSTable auf der Platte flushen.
- SSTables im Hintergrund kompaktieren, die neuesten Versionen behalten und abgelaufene Tombstones verwerfen.
Lesezugriffe prüfen die Memtable, dann die SSTables, und ein Bloom-Filter pro SSTable überspringt Dateien, die den Key nicht enthalten können: Mit 10 Bit pro Key und 7 Hash-Funktionen liegt die Falsch-Positiv-Rate bei (1 − e^(−0,7))^7, etwa 0,8 %. Size-Tiered Compaction ist der Standard; Cassandra 5.0 empfiehlt für neue Workloads seine Unified-Strategie.
Reale Systeme im Vergleich zum Paper
| Dynamo (2007) | Amazon DynamoDB | Cassandra 5.0 | Riak KV | |
|---|---|---|---|---|
| Partitionierung | MD5-Ring, gleich große Partitionen | Bereiche, die nach Größe oder Traffic geteilt werden | Murmur3-Ring, 16 Tokens pro Node | 160-Bit-Ring, 64 Partitionen |
| Replikation | Leaderlos, N pro Key | 3 Replikate über AZs, Multi-Paxos-Leader | Leaderlos, pro Rechenzentrum | Leaderlos, n_val 3 |
| Konsistenz | Sloppy Quorum | Standardmäßig eventual; starke Lesezugriffe vom Leader | Consistency Level pro Request | Sloppy Quorum, pr und pw |
| Konflikte | Vector Clocks | Leader ordnet Schreibvorgänge; Last Writer Wins über Regionen | Last Write Wins | Siblings oder CRDTs |
| Speicher | Berkeley DB, MySQL | B-Tree plus Write-Ahead-Log | LSM-Tree | Bitcask, LevelDB |
DynamoDB teilt den Namen, nicht das Design: Laut dem USENIX-Paper von 2022 bestätigt der Partition-Leader einen Schreibvorgang, sobald zwei von drei Replikaten ihn geloggt haben. Global Tables nutzen standardmäßig Last Writer Wins über Regionen; zum Zeitpunkt des Schreibens (November 2026) bieten sie außerdem Multi-Region Strong Consistency in genau drei Regionen.
Das Diagramm des Key-Value-Stores im Dynamo-Stil
Diagramminhalt
- Node B
- Node A
- Node C
- Node F
- Node D
- Node E
- Cart service
- Inside every node: LSM write path
- Commit log
- Memtable
- SSTables
- put(k, ctx, v)
- replica 2: ack
- replica 3: no reply
- hinted write for C: ack
- hand off when C recovers
- then insert
- flush when full
- gossip
So liest du es:
- Der Ring. Im Uhrzeigersinn ab hash(k), dem Punkt, ergibt sich die Preference List A bis F.
- Der Schreibvorgang. Der Cart-Service sendet put(k, ctx, v) an den Koordinator A, der an B und C repliziert.
- Der Ausfall. C ist ausgefallen, daher übernimmt D die Kopie von C mit einem Hint (gestrichelt, bernsteinfarben) und gibt sie später zurück. Mit W = 2 kehrt der put zurück, sobald A und B ihn haben.
- Gossip (gepunktet) läuft zwischen zufälligen Node-Paaren.
- Die Panels zeigen N, R, W und den Schreibpfad jedes Nodes.
Key-Value-Store-Diagramme klar zeichnen
- Folge einem Key. Markiere seinen Hash, schreibe seine Preference List aus und setze N, R und W daneben; ein Ring ohne Key erklärt nichts.
- Zeichne den Ausfall. Ein roter Node und eine gestrichelte Ausweichkante erklären ein Sloppy Quorum schneller als Text.
- Zeige Fehlerdomänen: Färbe Replikate nach Rack oder Zone, damit Reviewer prüfen können, dass sich keine zwei Kopien eine Domäne teilen.
- Überlasse Node-Interna einem einzigen Inset. Der Cluster kommt zuerst.
Ein häufiger Fehler: Pfeile vom Client zu jedem Replikat und kein Koordinator, was verbirgt, wer entscheidet, dass ein Schreibvorgang erfolgreich war. Die Schritt-für-Schritt-Methode für System Design behandelt Layout und Zahlen.
In Archboard nachbauen
- Melde dich mit Google oder GitHub an und erstelle ein Diagramm.
- Füge aus dem Paket Basis eine große graue Ellipse für den Token-Ring hinzu.
- Platziere sechs Server-Nodes aus dem Paket Netzwerk auf dem Ring, Node A bis Node F im Uhrzeigersinn. Färbe A und B grün, C rot und D bernsteinfarben und beschrifte ihre Rollen mit Text-Notizen aus Basis.
- Füge knapp vor Node A auf dem Ring eine kleine Ellipse für hash(k) hinzu, mit einem Text-Label.
- Füge einen Container aus dem Paket C4-Modell für den Cart-Service hinzu, mit einer put(k, ctx, v)-Kante zu Node A.
- Zeichne die Kanten: A nach B durchgezogen grün, A nach C gestrichelt rot mit Kreuz-Pfeilspitze, A nach D und D nach C gestrichelt bernsteinfarben (Hinted Write, dann Handoff) und eine gepunktete Gossip-Kante zwischen F und E mit einer Text-Notiz.
- Füge aus dem Paket Basis einen Markdown-Block mit N, R, W und dem Szenario hinzu.
- Füge aus dem Paket Basis einen Rahmen mit drei Komponente-Nodes aus dem Paket C4-Modell hinzu, Commit log, Memtable und SSTables, von oben nach unten verbunden, und eine Text-Notiz zu Bloom-Filtern.
Das Beispiel nutzt 14 Diagramm-Nodes und bleibt damit im Free-Plan.
FAQ
Wie entwirft man einen verteilten Key-Value-Store? Partitioniere mit Consistent Hashing, repliziere jeden Key auf N Nodes, stimme R und W ab, wähle eine Konfliktstrategie, ergänze Hinted Handoff und Anti-Entropy-Repair und betreibe pro Node einen LSM-Tree.
Was bedeutet R + W > N? Von N Replikaten wartet ein Schreibvorgang auf W und ein Lesevorgang auf R. Wenn R + W größer als N ist, erreicht jeder Lesevorgang mindestens ein Replikat, das den letzten bestätigten Schreibvorgang hält.
Basiert DynamoDB auf dem Dynamo-Paper? Nur teilweise: Jede Partition hat drei Replikate mit einem Multi-Paxos-Leader und B-Tree-Speicher, nicht Sloppy Quorums und Vector Clocks.
Was ist Hinted Handoff? Ein anderer Node speichert den Schreibvorgang eines nicht erreichbaren Replikats mit einem Hint und liefert ihn aus, wenn das Replikat zurückkehrt. Cassandra hört standardmäßig nach 3 Stunden Ausfall auf, für einen Node Hints zu speichern.
Sollte ich Last Write Wins oder Vector Clocks nutzen? Last Write Wins passt zu Daten, bei denen der Verlust eines gleichzeitigen Updates akzeptabel ist, etwa Sessions. Nutze Vector Clocks oder CRDTs, wenn jedes Update zählt, wie bei Warenkörben und Countern.