In diesem Artikel werden wir die Architektur des einfachen und effizienten KV-Speichers mithilfe der Kettenreplikation betrachten, die aktiv untersucht und in verschiedenen Systemen erfolgreich eingesetzt wird.

Dies ist die erste Hälfte eines Kettenreplikationsartikels. Der zweite Teil ist hier . Zuerst wird es eine kleine Theorie geben, dann einige Anwendungsbeispiele mit verschiedenen Modifikationen.

1. Das Ziel ist die Erklärung des Problems und der Vergleich mit dem Primär- / Sicherungsprotokoll.
2. Die Kettenreplikation ist ein grundlegender Ansatz.
3. Kettenreplikation - verteilte Anforderungen.
4. FAWN: ein schnelles Array von Wimpy-Knoten.

1. Einleitung

1.1 Zweck

Angenommen, wir möchten einen einfachen Schlüsselwertspeicher entwerfen. Das Repository wird eine sehr minimale Schnittstelle haben:

1. Schreiben (Schlüssel, Objekt): Wertwert durch Schlüsselschlüssel speichern / aktualisieren.
2. read (key): Gibt den gespeicherten Wert per Schlüssel zurück.

Wir wissen auch, dass die Datengröße relativ klein ist (alles passt auf einen Server, es ist kein Sharding erforderlich), aber es kann viele Schreib- / Leseanforderungen geben.

Unser Ziel ist es, einer großen Anzahl von Anforderungen ( hoher Durchsatz, HT ), hoher Verfügbarkeit ( HA ) und strenger Konsistenz ( SC ) standzuhalten.

In vielen Systemen wird SC für HA + HT geopfert, da die Erfüllung aller drei Eigenschaften keine triviale Aufgabe ist. Amazon Dynamo war ein großer Fortschritt und brachte eine Reihe von Datenbanken im Dynamo-Stil hervor, wie Cassandra, Riak, Voldemort usw.

1.2 Primär / Backup

Einer der gebräuchlichsten und einfachsten Ansätze zum Aufbau eines solchen Speichersystems ist die Verwendung der Primär- / Sicherungsreplikation.
Wir haben 1 Primärserver, mehrere Sicherungsserver, Schreib- / Lesevorgänge werden nur über den Primärserver ausgeführt.


Hier zeigt das Bild eines der möglichen Interaktionsprotokolle (primäres Warten auf Bestätigung von allen Sicherungen, bevor die Bestätigung an den Client gesendet wird). Es gibt andere Optionen (die sich nicht gegenseitig ausschließen), zum Beispiel:

• Primary organisiert Schreibanfragen streng.
• Primary sendet eine Bestätigung, sobald eine der Sicherungen mit einer Bestätigung antwortet.
• Schlampiges Quorum und angedeutete Übergabe.
• Usw.

Es ist auch ein separater Prozess erforderlich, der den Status des Clusters überwacht (die Konfiguration an die Teilnehmer verteilt) und bei einem Absturz des Host-Servers die Wahl eines neuen Servers vornimmt (initiiert) und auch festlegt, was bei einem geteilten Gehirn zu tun ist. Abhängig von den Anforderungen kann ein Teil dieser Logik als Teil des Replikationsalgorithmus, ein Teil als Drittanbieteranwendung (z. B. ein Tierpfleger zum Speichern der Konfiguration) usw. ausgeführt werden.

Offensichtlich wird die Leistung der Primär- / Sicherungsreplikation früher oder später durch zwei Engpässe begrenzt sein:

• Leistung des Primärservers.
• Anzahl der Sicherungsserver.

Je mehr Zuverlässigkeits- / Konsistenzanforderungen an einen Cluster gestellt werden, desto schneller wird dieser Moment.

Gibt es andere Möglichkeiten, um unser Ziel zu erreichen?

1.3 Kettenreplikation

Im Allgemeinen besteht die Kettenreplikation aus einer Sequenz (Kette) von Servern mit speziellen Rollen HEAD (der Server, mit dem der Client kommuniziert) und TAIL (Ende der Kette, SC-Garantie). Eine Kette hat mindestens die folgenden Eigenschaften:

1. Widersteht Drop auf n - 1 Server.
2. Die Schreibgeschwindigkeit unterscheidet sich nicht wesentlich von der Geschwindigkeit von SC Primary / Backup.
3. Die Neukonfiguration des Clusters im Falle eines HEAD-Absturzes erfolgt viel schneller als bei Primary, der Rest der Server ist vergleichsweise oder schneller als bei Primary / Backup.

Ein kleiner, aber wichtiger Punkt - eine zuverlässige FIFO-Verbindung zwischen Servern ist erforderlich .

Lassen Sie uns die verschiedenen Methoden zur Konstruktion der Kettenreplikation genauer untersuchen.

2. Der grundlegende Ansatz

2.1 Betriebsalgorithmus

Clients senden Schreibanforderungen an den Kopfknoten und Leseanforderungen an den Endknoten. Die Antwort kommt immer vom Schwanz. Nachdem Head eine Änderungsanforderung erhalten hat, berechnet er die erforderliche Statusänderung, wendet sie an und sendet sie an den nächsten Knoten. Sobald Tail es verarbeitet, wird eine ACK-Antwort zurück in die Kette gesendet. Wenn eine Leseanforderung einen Wert von x zurückgibt, wird sie offensichtlich auf allen Knoten gespeichert.

2.2 Replikationsprotokoll

Wir nummerieren die Server von Kopf bis Ende und dann auf jedem Knoten $$$i$ wir werden zusätzlich speichern:

• $$$Pending_i$ - eine Liste der vom Knoten empfangenen Anforderungen, die noch nicht von tail verarbeitet wurden.
• $$$Sent_i$ - Eine Liste der vom Server an seinen Nachfolger gesendeten Anforderungen, die noch nicht von tail verarbeitet wurden.
• $$$History_i (Schlüssel)$ - den Verlauf der Änderungen des Schlüsselwerts (Sie können sowohl den Verlauf als auch nur den Gesamtwert speichern). Beachten Sie Folgendes:

  $$

  $$History_j (Schlüssel) \ subseteq History_i (Schlüssel), \ forall j> i$$
  
  
• Und auch:

  $$

  $$Sent_i \ subseteq Pending_i \\ History_i (Schlüssel) = History_ {i + 1} (Schlüssel) \ cup Sent_i$$
  
  

2.3 Server-Failover

Wie in der Einleitung erwähnt, benötigen wir eine Art Master-Prozess, der:

• Identifiziert einen ausgefallenen Server.
• Benachrichtigt seinen Vorgänger und Nachfolger über Änderungen in der Schaltung.
• Wenn der Server Tail oder Head ist, benachrichtigt er Clients über ihre Änderung.

Wir glauben, dass der Master-Prozess stabil ist und niemals abstürzt. Die Wahl eines solchen Verfahrens würde den Rahmen dieses Artikels sprengen.

Die zweite sehr wichtige Annahme ist, dass wir davon ausgehen, dass die Server Fail-Stop sind:

• Bei einem (internen) Fehler funktioniert der Server nicht mehr und gibt kein falsches Ergebnis aus.
• Der Serverausfall wird immer vom Master-Prozess bestimmt.

Mal sehen, wie ein neuer Server hinzugefügt wird:
Theoretisch kann an jeder Stelle in der Kette ein neuer Server hinzugefügt werden. Das Hinzufügen zum Ende scheint am wenigsten schwierig zu sein. Sie müssen lediglich den Status des aktuellen Endes auf den neuen Server kopieren, den Assistenten über die Änderung in der Kette benachrichtigen und das alte Ende benachrichtigen, dass Anforderungen jetzt weiter gesendet werden müssen.

Betrachten Sie abschließend drei mögliche Fehlerszenarien:

2.3.1 Kopfsturz
Entfernen Sie einfach den Server aus der Kette und weisen Sie den nächsten neuen Kopf zu. Nur der Verlust dieser Anfragen von $$$Pending_ {head}$ das wurden nicht weiter geschickt - $$$Pending_ {head} \ setminus Sent_ {head}$

2.3.2 Fallschwanz
Wir entfernen den Server aus der Kette und weisen den vorherigen dem neuen Schwanz zu $$$Sent_ {tail - 1}$ gelöscht (alle diese Vorgänge sind jeweils als verarbeiteter Schwanz markiert) $$$Pending_ {tail - 1}$ nimmt ab.

2.3.3 Fallender Zwischenknoten $$$k$
Der Assistent informiert die Knoten $$$k-1$ und $$$k + 1$ über die Neuordnung in einer Kette.
Möglicher Verlust $$$Sent_ {k-1}$ wenn der Knoten $$$k$ Ich konnte sie daher nach dem Löschen des Knotens nicht weiter an meinen Nachfolger senden $$$k$ Von der Kette wird das erste, was wieder gesendet wird $$$Sent_ {k - 1}$ und erst nach diesem Knoten $$$k - 1$ verarbeitet weiterhin neue Anfragen.

2.4 Vergleich mit Backup / Primärprotokoll

• Bei der Kettenreplikation ist nur ein Server (Tail) an der Ausführung von Leseanforderungen beteiligt und gibt sofort eine Antwort, während er bei P / B Primary primär auf die Bestätigung des Abschlusses von Schreibanforderungen warten kann.
• In beiden Ansätzen wird die Schreibanforderung auf allen Servern ausgeführt, P / B erledigt dies aufgrund der parallelen Ausführung schneller.

Verzögerungen bei der Replikation der Fehlerkette:

• Kopf: Die Ausführung von Leseanforderungen wird nicht unterbrochen, Schreibanforderungen werden um 2 Nachrichten verzögert - vom Master an alle Server über den neuen Kopf und vom Master an alle Clients über den neuen Kopf.
• Zwischenserver: Leseanforderungen werden nicht unterbrochen. Aufzeichnungsanforderungen können zur Laufzeit verzögert werden $$$Sent_i$ Es gibt keine Aktualisierungsverluste.
• Tail: Verzögerung der Lese- und Schreibanforderungen für zwei Nachrichten - Benachrichtigung $$$tail - 1$ über den neuen Schwanz und alarmieren Sie die Kunden über den neuen Schwanz.

Fehler P / B Verzögerungen:

• Primär: 5 Nachrichtenverzögerung, um einen neuen Primär- und Synchronisierungsstatus auszuwählen.
• Sicherung: Es gibt keine Leseverzögerungen, wenn keine Schreibanforderungen vorliegen. Wenn eine Aufnahmeanforderung angezeigt wird, ist eine Verzögerung von 1 Nachricht möglich.

Wie Sie sehen können, ist der schlimmste Schwanzfehler bei der Kettenreplikation schneller als der schlimmste bei P / B (primär).

Die Autoren dieses Ansatzes führten Belastungstests durch, die eine vergleichbare Leistung mit dem P / B-Protokoll zeigten.

3. Verteilte Abfragen (Kettenreplikation mit aufgeteilten Abfragen - CRAQ)

Der grundlegende Ansatz weist eine offensichtliche Schwäche auf - Tail, der alle Leseanforderungen verarbeitet. Dies kann zu zwei Problemen führen:

• Der Schwanz wird zum Hotspot, d.h. Ein Server, der weit mehr Anforderungen verarbeitet als jeder andere Knoten.
• Wenn Sie eine Kette in mehreren Rechenzentren platzieren, kann der Schwanz sehr weit entfernt sein, was die Schreibanforderungen verlangsamt.

Die Idee von CRAQ ist recht einfach: Lassen Sie Leseanforderungen auf alle Server außer Tail eingehen. Um die Konsistenz zu gewährleisten, speichern wir den Vektor der Objektversionen für Schreibanforderungen. Im Falle von Mehrdeutigkeiten fordern die Knoten Tail an, um die neueste feste Version zu erhalten.

3.1 CRAQ

Wir formalisieren die CRAQ-Architektur:
Jeder Knoten mit Ausnahme von tail verarbeitet Leseanforderungen und gibt eine Antwort zurück, und head gibt eine Antwort von Schreibanforderungen zurück (vergleiche mit dem grundlegenden Ansatz).


Auf jedem Nicht-Endknoten können mehrere Versionen desselben Objekts gespeichert werden, und die Versionen bilden eine streng monoton ansteigende Sequenz. Für jede Version wird ein zusätzliches Attribut "sauber" oder "schmutzig" hinzugefügt. Anfangs sind alle Versionen sauber.

Sobald der Knoten eine Schreibanforderung empfängt, fügt er die empfangene Version zur Liste der Versionen hinzu und dann:

• Wenn der Knoten Tail ist, markiert er die Version als sauber. In diesem Moment gilt die Version als fest und sendet eine Bestätigung zurück in die Kette.
• Andernfalls wird die Version als fehlerhaft markiert und die Anforderung weiter unten in der Kette gesendet.

Sobald der Knoten eine Bestätigung vom Nachfolger erhält, markiert er die Version als sauber und löscht alle vorherigen Versionen.

Sobald der Knoten eine Leseanforderung erhält:

• Wenn die letzte dem Knoten bekannte Version des Objekts sauber ist, wird sie zurückgegeben.
• Andernfalls fordert er Tail an, um die neueste feste Version des Objekts zu erhalten, die er an den Client zurückgibt. (Konstruktionsbedingt befindet sich eine solche Version immer auf dem Knoten).

Bei Anwendungen mit einer Dominanz von Leseanforderungen wächst die CRAQ-Leistung linear mit dem Wachstum der Knoten . Bei einer Dominanz von Schreibanforderungen ist die Leistung nicht schlechter als die des Basisansatzes.

CRAQ kann sich sowohl in einem als auch in mehreren Rechenzentren befinden. Auf diese Weise können Kunden die nächstgelegenen Knoten auswählen, um die Geschwindigkeit der Leseanforderungen zu erhöhen.

3.2 Konsistenz in CRAQ

CRAQ bietet eine starke Konsistenz, außer in einem Fall: Wenn der Knoten die letzte festgeschriebene Version von tail empfängt, kann tail die neue Version festschreiben, bevor der Knoten auf den Client antwortet. In dieser Situation bietet CRAQ monotones Lesen (sequentielle Leseanforderungen gehören nicht der Vergangenheit an, können aber alte Daten zurückgeben) für die gesamte Kette .

Eine schwache Konsistenz ist ebenfalls möglich:

• Eventuelle Konsistenz: Der Knoten fordert nicht die neueste festgeschriebene Version von tail an. Dies stört den monotonen Messwert in der gesamten Kette, hält den monotonen Messwert jedoch auf demselben Knoten . Darüber hinaus kann es der Toleranz der Netzwerkpartitionierung standhalten.
• Begrenzte mögliche Konsistenz: Geben Sie eine fehlerhafte Version nur bis zu einem bestimmten Punkt zurück. Beispielsweise sollte der Unterschied zwischen schmutzigen und sauberen Versionen N Revisionen nicht überschreiten. Oder ein Zeitlimit.

3.3 Server-Failover

Ähnlich dem grundlegenden Ansatz.

3.4 Optional

CRAQ hat eine interessante Funktion: Sie können Multicast während des Aufnahmevorgangs verwenden. Angenommen, head sendet die Änderung mit einem Multicast und sendet über die Kette nur eine Kennung für dieses Ereignis. Wenn das Update selbst nicht am Knoten angekommen ist, kann es warten und es vom nächsten Knoten empfangen, wenn Tail eine Bestätigungsnachricht über die Änderung sendet. Ebenso kann Tail eine Bestätigung der Fixierung mit Multicast senden.

4. FAWN: Ein schnelles Array von Wimpy-Knoten

Eine sehr interessante Studie, die nicht direkt mit dem Thema dieses Artikels zusammenhängt, sondern als Beispiel für die Verwendung der Kettenreplikation dient.

Hochleistungsspeicher mit Schlüsselwerten (Dynamo, memcached, Voldemort) weisen gemeinsame Merkmale auf: Sie erfordern E / A, ein Minimum an Rechenleistung, parallelen unabhängigen Zugriff auf zufällige Schlüssel in großen Mengen und kleine Schlüsselwerte bis zu 1 KB.

Server mit Festplatten sind aufgrund des langen Suchvorgangs (Direktzugriffszeit) nicht für solche Cluster geeignet, und Server mit einer großen Anzahl von DRAMs verbrauchen überraschend viel Strom - 2 GB DRAM entsprechen 1 TB Festplatte.

Der Aufbau eines effektiven (Bandbreiten-) Clusters mit minimalem Stromverbrauch ist das Ziel der ursprünglichen Studie. 50% der Serverkosten für drei Jahre sind Stromkosten, und moderne Energiesparmodi sind nicht so effektiv wie angekündigt - bei Tests mit 20% Last blieb der CPU-Verbrauch bei 50%, und andere Serverkomponenten verfügen überhaupt nicht über Energiesparmodi ( DRAM zum Beispiel funktioniert bereits mindestens). Es ist wichtig zu beachten, dass sich in solchen Clustern die Lücke zwischen CPU und E / A vergrößert - eine leistungsstarke CPU muss warten, bis der E / A-Vorgang abgeschlossen ist.

4.1 Architektur

Der FAWN-Cluster basiert auf alten Servern für 250 US-Dollar (Preise von 2009) und verfügt über eine integrierte 500-MHz-CPU, 512 MB RAM und eine 32-Gbit-SSD. Wenn Sie mit der Amazon Dynamo-Architektur oder dem konsistenten Hashing vertraut sind, sind Sie mit der FAWN-Architektur vertraut:

1. Jeder physische Server enthält mehrere virtuelle Knoten, von denen jeder eine eigene VID hat.
2. VIDs bilden einen Ring, jede VID ist für den Bereich „hinter sich“ verantwortlich (zum Beispiel ist A1 für die Tasten im Bereich R1 verantwortlich).
3. Um die Zuverlässigkeit zu erhöhen, werden Daten im Uhrzeigersinn auf R der folgenden Knoten repliziert. (Mit R = 2 wird beispielsweise der Schlüssel auf A1 auf B1 und C1 repliziert.) Wir erhalten also eine Kettenreplikation (grundlegender Ansatz).
4. Leseanforderungen gehen an die Endkette, d.h. Das Lesen des Schlüssels von A1 geht zu C1.
5. Schreibanfragen gehen an die Kopfkette und gehen bis zum Ende durch.

Die Serverzuordnung wird auf einem Cluster von Frontend-Servern gespeichert, von denen jeder für seine spezifische VID-Liste verantwortlich ist, und kann die Anforderung an einen anderen Frontend-Server umleiten.

4.2 Testergebnisse

Beim Lasttest erreicht der FAWN einen QPS (Abfragen pro Sekunde) von 90% des QPS auf einem Flash-Laufwerk mit zufälligem Lesevorgang.

In der folgenden Tabelle werden die Gesamtbetriebskosten (TCO) verschiedener Konfigurationen verglichen, wobei die Basis für Traditional ein 1000-Dollar-Server mit 200 W Verbrauch (Preise 2009) ist:

Also, wenn:

• Big Data, wenige Abfragen: FAWN + 2 TB 7200 U / min
• Eine kleine Datenmenge, viele Anfragen: FAWN + 2GB DRAM
• Durchschnittswerte: FAWN + 32 GB SSD

Referenzen

• Kettenreplikation zur Unterstützung von hohem Durchsatz und hoher Verfügbarkeit
• Objektspeicherung in CRAQ: Kettenreplikation mit hohem Durchsatz für hauptsächlich lesbare Workloads
• FAWN: Ein schnelles Array von Wimpy-Knoten