Wir betrachten weiterhin Beispiele für die Verwendung der Kettenreplikation. Grundlegende Definitionen und Architekturen wurden im ersten Teil angegeben . Ich empfehle, dass Sie sich damit vertraut machen, bevor Sie den zweiten Teil lesen.

In diesem Artikel werden wir die folgenden Systeme untersuchen:

• Hibari ist ein verteiltes fehlertolerantes Repository, das in erlang geschrieben wurde.
• HyperDex - verteilter Schlüsselwertspeicher mit Unterstützung für die schnelle Suche nach sekundären Attributen und die Bereichssuche.
• ChainReaction - Kausal + Konsistenz und Geo-Replikation.
• Aufbau eines verteilten Systems ohne zusätzliche externe Überwachungs- / Rekonfigurationsprozesse.

5. Hibari

Hibari ist ein verteiltes fehlertolerantes KV-Repository, das in erlang geschrieben wurde. Verwendet die Kettenreplikation (grundlegender Ansatz), d.h. erreicht strenge Konsistenz. In Tests zeigt Hibari eine hohe Leistung - mehrere tausend Updates pro Sekunde werden auf Servern mit zwei Einheiten (1-KB-Anforderungen) erzielt.

5.1 Architektur

Konsistentes Hashing wird zum Platzieren von Daten verwendet. Die Basis der Speicherung sind physische und logische Blöcke. Der physische Baustein ist ein Server mit Linux, möglicherweise eine EC2-Instanz und im Allgemeinen die VM als Ganzes. Ein logischer Baustein ist eine Speicherinstanz, mit der die Hauptprozesse des Clusters arbeiten, und jeder Block ist ein Knoten in einer Kette. Im folgenden Beispiel ist der Cluster mit 2 logischen Blöcken auf jedem physischen Block und einer Kettenlänge von 2 konfiguriert. Beachten Sie, dass die Knoten der Kette über den physischen Blöcken „verschmiert“ sind, um die Zuverlässigkeit zu erhöhen.

Der Master-Prozess (siehe Definition im ersten Teil) wird als Admin-Server bezeichnet .

Daten werden in „Tabellen“ gespeichert, die einfach in Namespaces unterteilt sind, jede Tabelle wird in mindestens einer Kette gespeichert und jede Kette speichert Daten in nur einer Tabelle.

Der Hibari-Client erhält vom Admin-Server Aktualisierungen mit einer Liste aller Kopf- und Endpunkte aller Ketten (und aller Tabellen). Somit wissen Kunden sofort, an welchen logischen Knoten die Anforderung gesendet werden soll.

5.2 Hashing

Hibari benutzt ein Paar $$$\ {T, K \}$ um den Namen der Kette zu bestimmen, in der der Schlüssel gespeichert ist $$$K$ in der Tabelle $$$T$ : Schlüssel $$$K$ dem Intervall zugeordnet $$$[0.1, 1.0)$ (unter Verwendung von MD5), das in Abschnitte unterteilt ist, für die eine Kette verantwortlich ist. Die Abschnitte können je nach "Gewicht" der Kette unterschiedlich breit sein, zum Beispiel:



Wenn also einige physische Blöcke sehr mächtig sind, können die darauf befindlichen Ketten breitere Abschnitte erhalten (dann fallen mehr Schlüssel auf sie).

6. HyperDex

Ziel dieses Projekts war es, ein verteiltes Schlüsselwert-Repository zu erstellen, das im Gegensatz zu anderen gängigen Lösungen (BigTable, Cassandra, Dynamo) eine schnelle Suche nach sekundären Attributen unterstützt und schnell eine Bereichssuche durchführen kann. Um beispielsweise in den zuvor betrachteten Systemen nach allen Werten in einem bestimmten Bereich zu suchen, müssen Sie alle Server durchlaufen, was natürlich nicht akzeptabel ist. HyperDex löst dieses Problem mithilfe von Hyperspace Hashing .

6.1 Architektur

Die Idee des Hyperraum-Hashing ist zu bauen $$$n$ -dimensionaler Raum, in dem jedes Attribut einer Koordinatenachse entspricht. Beispielsweise kann für Objekte (Vorname, Nachname, Telefonnummer) das Leerzeichen folgendermaßen aussehen:



Die graue Hyperebene durchläuft alle Schlüssel, wobei Nachname = Smith, gelb - über alle Schlüssel, wobei Vorname = John. Der Schnittpunkt dieser Ebenen bildet eine Antwort auf die Telefonnummern der Suchanfragen von Personen mit dem Namen John und dem Nachnamen Smith. Also die Anfrage nach $$$k$ Attribute gibt zurück $$$(n-k)$ -dimensionaler Unterraum.

Der Suchraum ist unterteilt in $$$n$ -dimensionale disjunkte Regionen, und jede Region ist einem einzelnen Server zugeordnet. Ein Objekt mit Koordinaten aus einer Region wird auf dem Server dieser Region gespeichert. Somit wird ein Hash zwischen Objekten und Servern erstellt.

Eine Suchabfrage (nach Bereich) bestimmt die Regionen, die in der resultierenden Hyperebene enthalten sind, und reduziert somit die Anzahl der abgefragten Server auf ein Minimum.

Bei diesem Ansatz gibt es ein Problem: Die Anzahl der erforderlichen Server wächst exponentiell von der Anzahl der Attribute, d. H. wenn Attribute $$$k$ dann brauchst du $$$O (2 ^ k)$ Server. Um dieses Problem zu lösen, wendet HyperDex eine Partition des Hyperraums in Unterräume (mit einer niedrigeren Dimension) mit jeweils einer Teilmenge von Attributen an:

6.2 Replikation

Um eine strikte Konsistenz zu gewährleisten, entwickelten die Autoren einen speziellen Ansatz, der auf einer kettenreplikationswertabhängigen Verkettung basiert, wobei jeder nachfolgende Knoten durch Hashing des entsprechenden Attributs bestimmt wird. Zum Beispiel der Schlüssel $$$("John", "Smith")$ Zuerst wird es in den Schlüsselraum gehasht (wir erhalten die Kopfkette, auch Punktführer genannt ), dann den Hash von$$ $ inline $ "John" $ inline $ auf die Koordinate auf der entsprechenden Achse und so weiter. (Ein Beispiel für ein Update finden Sie in der Abbildung unten. $$$u_1$ )

Alle Aktualisierungen durchlaufen einen Punkteführer, der Anforderungen anordnet (Linearisierbarkeit).



Wenn das Update zu einer Änderung in der Region führt, wird zuerst die neue Version unmittelbar nach der alten geschrieben (siehe Update $$$u_2$ ), und nach dem Empfang der ACK von tail wird der Link zur alten Version vom vorherigen Server geändert. Zu gleichzeitigen Anforderungen (z. $$$u_2$ und $$$u_3$ ) hat nicht gegen den Konsistenzpunkt-Leader verstoßen. Wenn er empfangen wird, werden dem Server Versionsverwaltung und andere Metainformationen hinzugefügt $$$u_3$ vorher $$$u_2$ könnte feststellen, dass die Bestellung fehlerhaft ist und Sie warten müssen $$$u_2$ .

7. Kettenreaktion

Es wird ein Kausal + Konvergenz-Modell verwendet, das die Bedingung für konfliktfreie Konvergenz zur kausalen (kausalen) Konvergenz hinzufügt. Um die kausale Konvergenz zu gewährleisten, werden jeder Anforderung Metadaten hinzugefügt, die die Versionen aller kausal abhängigen Schlüssel angeben. ChainReaction ermöglicht die Georeplikation in mehreren Rechenzentren und ist eine Weiterentwicklung der CRAQ-Idee.

7.1 Architektur

Die Architektur von FAWN wird mit geringfügigen Änderungen verwendet - jeder DC besteht aus Datenservern - Backends (Datenspeicherung, Replikation, Bildung eines DHT-Rings) und Client-Proxys - Frontends (Senden einer Anforderung an einen bestimmten Knoten). Jeder Schlüssel wird auf R aufeinanderfolgende Knoten repliziert und bildet eine Kette. Leseanforderungen werden vom Ende und Schreiben vom Kopf verarbeitet.

7.2 Ein Rechenzentrum

Wir stellen eine wichtige Eigenschaft fest, die sich aus der Kettenreplikation ergibt - wenn der Knoten $$$k$ kausal konsistent mit einigen Client-Operationen, dann auch mit allen vorherigen Knoten. Also wenn die Operation $$$Op$ wurde zuletzt von uns auf der Seite gesehen $$$j$ , dann alle kausalabhängig (von $$$Op$ ) Leseoperationen können nur an Knoten von Kopf bis ausgeführt werden $$$j$ . Sobald $$$Op$ wird am Ende ausgeführt - es gibt keine Leseeinschränkungen. Bezeichnen Sie die Schreibvorgänge, die von tail im DC ausgeführt wurden $$$d$ wie DC-Write-Stable (d) .

Jeder Client speichert eine Liste (Metadaten) aller vom Client angeforderten Schlüssel im Format (Schlüssel, Version, chainIndex), wobei chainIndex die Position des Knotens in der Kette ist, der die letzte Anforderung für den Schlüsselschlüssel beantwortet hat. Metadaten werden nur für Schlüssel gespeichert, von denen der Client nicht weiß, ob sie DC-Write-Stable (d) sind oder nicht .

7.2.1 Schreibvorgang

Beachten Sie, dass keine Leseanforderung frühere Versionen lesen kann, sobald die Operation DC-Write-Stable (d) geworden ist.

Für jede Schreibanforderung wird eine Liste aller Schlüssel hinzugefügt, für die Lesevorgänge ausgeführt wurden, bevor der letzte Schreibvorgang ausgeführt wurde. Sobald der Client-Proxy die Anforderung empfängt, führt er blockierende Lesevorgänge an den Endpunkten aller Schlüssel aus den Metadaten durch (wir warten auf die Bestätigung des Vorhandenseins derselben oder einer neueren Version, dh wir erfüllen die Bedingung der kausalen Konsistenz). Sobald Bestätigungen eingegangen sind, wird eine Schreibanforderung an den Kopf der entsprechenden Kette gesendet.



Sobald der neue Wert gespeichert ist $$$k$ Knoten der Kette wird eine Benachrichtigung an den Client gesendet (mit dem Index des letzten Knotens). Der Client aktualisiert den chainIndex und entfernt die Metadaten der gesendeten Schlüssel als es wurde über sie bekannt, dass sie DC-Write-Stable sind (d). Parallel dazu setzt sich die Aufnahme fort - träge Ausbreitung . Daher wird dem Schreiben von Operationen am ersten Vorrang eingeräumt $$$k$ Knoten. Sobald Tail die neue Version des Schlüssels speichert, wird eine Benachrichtigung an den Client gesendet und an alle Knoten der Kette gesendet, damit diese den Schlüssel als stabil markieren.

7.2.2 Lesevorgang

Der Client-Proxy sendet eine Leseanforderung an $$$index: = rand (1, chainIndex)$ Knoten in der Schaltung, während die Last verteilt wird. Als Antwort sendet der Knoten den Wert und die Version dieses Werts. Die Antwort wird an den Client gesendet, während:

• Wenn die Version stabil ist, entspricht der neue chainIndex der Größe der Kette.
• Wenn die Version neuer ist, ist der neue chainIndex = index.
• Andernfalls ändert sich chainIndex nicht.

7.2.3 Knoten-Failover

Es ist fast vollständig identisch mit dem grundlegenden Ansatz, mit einigen Unterschieden in der Tatsache, dass chainIndex auf dem Client in einigen Fällen ungültig wird - dies kann leicht festgestellt werden, wenn Anforderungen ausgeführt werden (es gibt keinen Schlüssel in dieser Version) und die Anforderung wird an den Kopf der Kette umgeleitet, um nach dem Knoten mit der gewünschten Version zu suchen.

7.3 Mehrere ( $$$N$ ) Rechenzentren (Geo-Replikation)

Wir verwenden Algorithmen aus einer Single-Server-Architektur als Basis und passen sie auf ein Minimum an. Für den Anfang benötigen wir in Metadaten anstelle von Versions- und ChainIndex-Werten versionierte Vektoren mit N Dimensionen.

Wir definieren Global-Write-Stable auf ähnliche Weise wie DC-Write-Stable (d) - die Schreiboperation wird als Global-Write-Stable betrachtet, wenn sie in allen DCs an Schwänzen ausgeführt wurde.

In jedem DC - remote_proxy wird eine neue Komponente angezeigt . Ihre Aufgabe besteht darin, Aktualisierungen von anderen DCs zu empfangen / zu senden.

7.3.1 Ausführen eines Schreibvorgangs (auf dem Server) $$$i$ )

Der Anfang ähnelt einer Single-Server-Architektur - wir führen blockierende Lesevorgänge durch und schreiben in den ersten $$$k$ Knoten einer Kette. Zu diesem Zeitpunkt sendet der Client-Proxy dem Client einen neuen chainIndex-Vektor, in dem bis auf die Position überall Nullen stehen $$$i$ - Es gibt eine Bedeutung $$$k$ . Weiter - wie immer. Eine zusätzliche Operation ganz am Ende - das Update wird an remote_proxy gesendet, das mehrere Anforderungen sammelt und dann alles sendet.

Hier treten zwei Probleme auf:

• Wie kann man Abhängigkeiten zwischen verschiedenen Updates von verschiedenen DCs sicherstellen?
  
  Jeder remote_proxy speichert einen lokalen Versionsvektor $$$rvp$ Abmessungen $$$N$ , speichert die Anzahl der gesendeten und empfangenen Updates und sendet sie in jedem Update. Wenn also ein Update von einem anderen DC empfangen wird, überprüft remote_proxy die Zähler, und wenn der lokale Zähler kleiner ist, wird die Operation blockiert, bis das entsprechende Update empfangen wird.
• Wie können Abhängigkeiten für diesen Vorgang in anderen Domänencontrollern bereitgestellt werden?
  
  Dies wird mit einem Bloom-Filter erreicht. Wenn Schreib- / Lesevorgänge vom Client-Proxy ausgeführt werden, wird zusätzlich zu den Metadaten für jeden Schlüssel ein Bloom-Filter gesendet (sogenannte Antwortfilter). Diese Filter werden in der AccessedObjects- Liste gespeichert. Wenn Sie Schreib- / Lesevorgänge anfordern, senden die Metadaten auch gesendete Schlüssel ODER-Filter (als Abhängigkeitsfilter bezeichnet). In ähnlicher Weise werden nach dem Schreibvorgang die entsprechenden Filter gelöscht. Beim Senden einer Schreiboperation an einen anderen DC werden auch ein Abhängigkeitsfilter und ein Antwortfilter für diese Anforderung gesendet.
  
  Ferner prüft der entfernte Gleichstrom, nachdem er alle diese Informationen empfangen hat, ob solche Operationen möglicherweise zufällig abhängig sind, wenn die gesetzten Bits des Antwortfilters mit den gesetzten Bits mehrerer Abfragefilter übereinstimmen. Potenziell - weil ein Blütenfilter.

7.3.2 Lesevorgang

Ähnlich wie bei einer Einzelserver-Architektur, angepasst an die Verwendung des chainIndex-Vektors anstelle eines Skalars und die Möglichkeit des Fehlens eines Schlüssels im Domänencontroller (da Aktualisierungen asynchron sind), warten Sie entweder oder leiten Sie die Anforderung an einen anderen Domänencontroller weiter.

7.3.3 Konfliktlösung

Dank der Metadaten werden kausalabhängige Operationen immer in der richtigen Reihenfolge ausgeführt (manchmal müssen Sie den Prozess dafür blockieren). Wettbewerbsänderungen in verschiedenen DCs können jedoch zu Konflikten führen. Um solche Situationen zu lösen, wird Last Write Wins verwendet, für die in jeder Aktualisierungsoperation ein Paar vorhanden ist $$$(Uhr, s)$ wo $$$c$ - Stunden auf Proxy und $$$s$ - ID von DC.

7.3.4 Behandlung von Knotenfehlern

Ähnlich der Single-Server-Architektur.

8. Nutzung von Sharding beim Entwurf skalierbarer Replikationsprotokolle

Ziel der Studie ist es, ein verteiltes System mit Shards und Replikation zu erstellen, ohne einen externen Masterprozess zum Neukonfigurieren / Überwachen des Clusters zu verwenden.

In den wichtigsten aktuellen Ansätzen sehen die Autoren die folgenden Nachteile:

Replikation:

• Primär / Sicherung - führt zu einer Diskrepanz im Status, wenn Primär fälschlicherweise als fehlgeschlagen identifiziert wurde.
• Quorum Intersection - kann zu einer Statusdiskrepanz während der Cluster-Rekonfiguration führen.

Strikte Konsistenz:

• Protokolle basieren bei Bedarf auf Mehrheitsabstimmungsalgorithmen (z. B. Paxos) $$$2 * N + 1$ Knoten fallen lassen $$$N$ Knoten.

Erkennung von Knotenfehlern:

• P / B und CR implizieren das Vorhandensein einer perfekten Erkennung fehlerhafter Knoten mit einem Fail-Stop-Modell, das in der Praxis nicht erreichbar ist und Sie müssen ein geeignetes Scanintervall auswählen.
• ZooKeeper unterliegt denselben Problemen: Bei einer großen Anzahl von Clients ist eine erhebliche Zeit (> 1 Sekunde) erforderlich, um die Konfiguration zu aktualisieren.

Der von den Autoren vorgeschlagene Ansatz, Elastic Replication genannt , weist diese Mängel nicht auf und weist die folgenden Merkmale auf:

• Strikte Konsistenz.
• Fallen standhalten $$$N$ Knoten müssen haben $$$N + 1$ Knoten.
• Neukonfiguration ohne Konsistenzverlust.
• Es sind keine Konsensprotokolle erforderlich, die auf einer Mehrheitsentscheidung beruhen.

Zusammenfassungsschild:

8.1 Organisation von Replikaten

Jeder Shard definiert eine Folge von Konfigurationen $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ Beispielsweise enthält die neue Konfiguration keine heruntergefallene Replik $$$\ mathcal {C} = \ mathcal {C} :::( Replikate \ setminus R_j)$

Jedes Element der Konfigurationssequenz besteht aus:

• Replikate - eine Reihe von Replikaten.
• Bestellnummer eines Replikats mit einer besonderen Rolle (siehe unten).

Jeder Splitter wird durch eine Reihe von Repliken dargestellt (nach Konstruktion - $$$N$ ), d.h. Wir teilen die Rollen von "Shard" und "Replica" nicht auf.

Jedes Replikat speichert die folgenden Daten:

• Konfidenz der Konfiguration, zu der dieses Replikat gehört.
• Besteller - Welches Replikat ist der Besteller dieser Konfiguration?
• Modus - Replikationsmodus, einer von drei: $$$PENDING$ (alle Repliken von Nicht- $$$C_1$ ), $$$ACTIVE$ (alle Repliken von $$$C_1$ ), $$$IMMUTABLE$ .
• Verlauf - Abfolge von Vorgängen für die tatsächlichen Replikatdaten $$$op_1 :: op_2 :: \ dots$ (oder nur eine Bedingung).
• Stable - Die maximale Länge des Verlaufspräfixes, die von diesem Replikat festgelegt wird. Offensichtlich $$$0 <= stabil <= Länge (Verlauf)$ .

Das Hauptziel eines Replikatbestellers besteht darin, Anforderungen an die übrigen Replikate zu senden und das größte Verlaufspräfix beizubehalten:

8.2 Organisation von Scherben

Scherben werden zu Ringen kombiniert, die als Gummibänder bezeichnet werden . Jeder Splitter gehört nur zu einem Ring. Der Vorläufer jeder Scherbe $$$X$ spielt eine besondere Rolle - er ist ein Sequenzer für ihn. Die Aufgabe des Sequenzers besteht darin, seinem Nachfolger bei Replikationsfehlern eine neue Konfiguration zu geben.


Zwei Bedingungen sind erforderlich:

• Jedes Gummiband hat mindestens eine Scherbe und eine funktionierende Nachbildung.
• Jedes Gummiband hat mindestens eine Scherbe, in der alle Repliken funktionieren.

Die zweite Bedingung scheint zu streng, entspricht jedoch der „traditionellen“ Bedingung, dass der Master-Prozess niemals abfällt.

8.3 Verwenden der Kettenreplikation

Wie Sie vielleicht erraten haben, sind die Repliken als Kette organisiert (grundlegender Ansatz) - der Besteller wird mit geringfügigen Unterschieden der Kopf sein:

• Bei einem Fehler in CR wird der Knoten aus der Kette geworfen (und durch einen neuen ersetzt). In ER wird eine neue Kette erstellt.
• Leseanforderungen in CR werden von Tail verarbeitet, in ER durchlaufen sie die gesamte Kette auf die gleiche Weise wie Schreibanforderungen.

8.5 Neukonfiguration im Fehlerfall

• Replikate werden sowohl von Replikaten Ihres Shards als auch von Replikaten eines Sequenzer-Shards überwacht.
• Sobald ein Fehler erkannt wird, senden Replikate einen Befehl dazu.
• Der Sequenzer sendet eine neue Konfiguration (ohne ein fehlgeschlagenes Replikat).
• Es wird eine neue Replik erstellt, die ihren Zustand mit dem Gummiband synchronisiert.
• Danach sendet der Sequenzer die neue Konfiguration mit dem hinzugefügten Replikat.

Referenzen

• Hibari
• hyperdex.orgerdex.org
• HyperDex: Ein verteilter, durchsuchbarer Schlüsselwertspeicher
• Kettenreaktion
• Nutzung von Sharding beim Entwurf skalierbarer Replikationsprotokolle