Wie zähle ich google.com-Seitentreffer? Und wie speichert man den Zähler von Likes sehr beliebter Benutzer? In diesem Artikel wird vorgeschlagen, die Lösung dieser Probleme mithilfe von CRDT (Conflict-Free Replicated Data Types, was auf Russisch ungefähr als Conflict-Free Replicated Data Types übersetzt wird) und im allgemeineren Fall von Replikatsynchronisierungsaufgaben in einem verteilten System mit mehreren führenden Knoten in Betracht zu ziehen.

1. Einleitung

Wir sind seit langem daran gewöhnt, Anwendungen wie einen Kalender oder einen Notendienst wie Evernote zu verwenden. Sie zeichnen sich dadurch aus, dass Sie offline (von mehreren Geräten bis zu mehreren Personen gleichzeitig (mit denselben Daten) arbeiten können. Die Herausforderung für die Entwickler jeder solchen Anwendung besteht darin, die „reibungsloseste“ Synchronisierung von Daten sicherzustellen, die gleichzeitig auf mehreren Geräten geändert werden. Im Idealfall sollte keine Benutzerbeteiligung erforderlich sein, um Zusammenführungskonflikte zu lösen.

In einem früheren Artikel haben wir bereits einen Ansatz zur Lösung solcher Probleme in Betracht gezogen - Operational Transformation. Außerdem wird eine sehr ähnliche Methode beschrieben, die sowohl Vor- als auch Nachteile hat (zum Beispiel wurde CRDT für JSON noch nicht erfunden. Aktualisierung: Dank an msvn für den Link hier Hier ist ein Projekt der Autoren eines Forschungsartikels zur Implementierung von JSON in CRDT.

2. Starke eventuelle Konsistenz

In letzter Zeit wurde viel Arbeit geschrieben und viel Forschung auf dem Gebiet der eventuellen Konsistenz betrieben. Meiner Meinung nach gibt es jetzt einen starken Trend hin zu einer Verlagerung von starker Konsistenz zu verschiedenen Optionen für Konsistenz, um zu untersuchen, welche Konsistenz in welchen Situationen / Systemen rentabler anzuwenden ist, und um bestehende Definitionen zu überdenken. Dies führt zu Verwirrung, wenn beispielsweise die Autoren einiger Werke, die über Konsistenz sprechen, eine eventuelle Konsistenz mit einigen zusätzlichen Eigenschaften bedeuten und andere Autoren hierfür eine bestimmte Terminologie verwenden.

Die von den Autoren eines der Artikel aufgeworfene Frage kritisiert die derzeitige Definition der eventuellen Konsistenz: Wenn Ihr System auf alle Anfragen immer mit „42“ antwortet, ist alles in Ordnung, und es ist schließlich konsistent.

Ohne die Richtigkeit dieses Artikels zu verletzen, verwende ich gemäß den Autoren der Originalartikel die folgende Terminologie (bitte beachten Sie, dass dies keine strengen Definitionen sind, sondern Unterschiede):

• Starke Konsistenz (SC): Alle Schreibvorgänge sind streng geordnet. Eine Leseanforderung auf einem Replikat gibt das gleiche, zuletzt aufgezeichnete Ergebnis zurück. Echtzeitkonsens ist erforderlich, um Konflikte zu lösen (mit den daraus resultierenden Konsequenzen), kann einem Rückgang auf n / 2 - 1 Knoten standhalten.
• Eventuelle Konsistenz (EC): Aktualisieren Sie die Daten lokal und senden Sie das Update weiter. Das Lesen auf verschiedenen Replikaten kann veraltete Daten zurückgeben. Im Falle von Konflikten rollen wir entweder zurück oder entscheiden irgendwie, was zu tun ist. T.O. Konsens ist weiterhin erforderlich, jedoch nicht mehr in Echtzeit .
• Starke eventuelle Konsistenz (SEC): EC + zur Lösung von Konflikten haben Replikate einen vordefinierten Algorithmus. T.O. Konsens ist nicht erforderlich , er kann einem Abfall auf n - 1 Knoten standhalten.

Beachten Sie, dass SEC (sozusagen) das Problem des CAP-Theorems löst: Alle drei Eigenschaften sind erfüllt.

Wir sind also bereit, SC zu spenden, und möchten einen bestimmten Satz grundlegender Datentypen für unser möglicherweise instabiles verteiltes System haben, die Schreibkonflikte für uns automatisch lösen (keine Benutzerinteraktion oder Anforderung an einen Schiedsrichter erforderlich).

3. Aufgaben zu Likes und Hits

Zweifellos gibt es mehrere Algorithmen zur Lösung solcher Probleme. CRDT bietet einen ziemlich eleganten und einfachen Weg.

Google.com Trefferanzahl:

google.com verarbeitet ungefähr 150.000 Anfragen pro Sekunde aus der ganzen Welt. Offensichtlich muss der Zähler asynchron aktualisiert werden. Warteschlangen lösen das Problem teilweise. Wenn wir beispielsweise eine externe API bereitstellen, um diesen Wert abzurufen, müssen wir eine Replikation durchführen, um das Repository nicht mit Leseanforderungen zu versehen. Und wenn es bereits eine Replikation gibt, vielleicht ohne globale Warteschlangen?

Benutzerlikes zählen:

Die Aufgabe ist der vorherigen sehr ähnlich, nur dass Sie jetzt eindeutige Treffer zählen müssen.

4. Terminologie

Für ein umfassenderes Verständnis des Artikels müssen Sie die folgenden Begriffe kennen:

1. Idempotenz
   Sagt, dass das mehrmalige Anwenden der Operation das Ergebnis nicht ändert.
   Beispiele - GET-Operation oder Addition mit Null: $$$f (x) = x + 0$
   
2. Kommutativität
   $$$f (x, y) = f (y, x)$
   
3. Teilbestellung
   Reflexivität + Transitivität + Antisymmetrie
   
4. Halbgitter
   Teilweise bestelltes Set mit exakter Oberseite (Unterseite)
   
5. Versionsvektor
   Ein Dimensionsvektor ist gleich der Anzahl der Knoten, und jeder Knoten erhöht bei Auftreten eines bestimmten Ereignisses seinen Wert im Vektor. Während der Synchronisation werden Daten mit diesem Vektor übertragen, und dies führt eine Ordnungsbeziehung ein, mit der Sie bestimmen können, welches Replikat alte / neue Daten enthält.

5. Modelle synchronisieren

Staatsbasiert:

Es wird auch als passive Synchronisation bezeichnet und bildet den konvergenten replizierten Datentyp - CvRDT.
Es wird in Dateisystemen wie NFS, AFS, Coda und in KV-Speichern Riak, Dynamo verwendet
In diesem Fall tauschen die Replikate den Status direkt aus, das empfangende Replikat führt den empfangenen Status mit seinem aktuellen Status zusammen.


Um die Konvergenz von Replikaten mithilfe dieser Synchronisierung durchzuführen, ist Folgendes erforderlich:

• Die Daten bildeten ein Halbgitter
• Die Zusammenführungsfunktion ergab eine genaue Obergrenze
• Die Repliken bildeten einen zusammenhängenden Graphen.

Ein Beispiel:

• Datensatz: natürliche Zahlen $$$\ mathbb {N}$
• Mindestartikel: $$$- \ infty$
• $$$merge (x, y) = max (x, y)$

Solche Anforderungen geben uns eine kommutative und idempotente Zusammenführungsfunktion, die auf einem bestimmten Datensatz monoton wächst :


Dies stellt sicher, dass die Replikate früher oder später konvergieren und Sie sich keine Gedanken über das Datenübertragungsprotokoll machen müssen. Wir können Nachrichten mit einem neuen Status verlieren, sie mehrmals senden und sie sogar in beliebiger Reihenfolge senden .

Betriebsbasiert:

Es wird auch als aktive Synchronisation bezeichnet und bildet den kommutativen replizierten Datentyp - CmRDT.
Wird in kooperativen Systemen wie Bayou, Rover, IceCube, Telex verwendet.

In diesem Fall tauschen die Replikate Statusaktualisierungsvorgänge aus. Beim Aktualisieren von Daten wird das ursprüngliche Replikat:

• Ruft die generate () -Methode auf, die die effector () -Methode zurückgibt, die auf anderen Replikaten ausgeführt werden soll. Mit anderen Worten, effector () ist der Abschluss zum Ändern des Status der verbleibenden Replikate.
• Anwenden eines Effektors auf einen lokalen Staat
• Sendet den Effektor an alle anderen Repliken

Um eine Konvergenz von Replikaten durchzuführen, müssen die folgenden Bedingungen erfüllt sein:

• Zuverlässiges Lieferprotokoll
• Wenn der Effektor gemäß der eingegebenen Reihenfolge (für einen bestimmten Typ) an alle Replikate geliefert wird, sind simultane Effektoren kommutativ oder
• Wenn der Effektor an alle Replikate geliefert wird, ohne die Bestellung zu berücksichtigen, sind alle Effektoren kommutativ.
• Wenn der Effektor mehrmals geliefert werden kann, muss er idempotent sein
• Einige Implementierungen verwenden Warteschlangen (Kafka) als Teil des Übermittlungsprotokolls.

Delta-basiert:

In Anbetracht des Status / op-basiert ist leicht zu erkennen, dass es keinen Sinn macht, den gesamten Status zu senden, wenn ein Update nur einen Teil des Status ändert. Wenn eine große Anzahl von Änderungen einen Status (z. B. einen Zähler) betrifft, können Sie eine aggregierte Änderung und nicht alle Vorgänge senden Änderungen.

Die Delta-Synchronisation kombiniert beide Ansätze und sendet Delta-Mutatoren aus, die den Status gemäß dem letzten Synchronisationsdatum aktualisieren. Bei der anfänglichen Synchronisation muss der Status vollständig gesendet werden, und einige Implementierungen berücksichtigen in solchen Fällen bereits den Status der verbleibenden Replikate, wenn Delta-Mutatoren erstellt werden.

Die nächste Optimierungsmethode besteht darin, das op-basierte Protokoll zu komprimieren, wenn Verzögerungen zulässig sind.

Rein betriebsbasiert:

Es gibt eine Verzögerung beim Erstellen eines Opektors bei der op-basierten Synchronisation. In einigen Systemen ist dies möglicherweise nicht akzeptabel. Dann müssen Sie die ursprüngliche Änderung auf Kosten der Komplikation des Protokolls und der zusätzlichen Menge an Metadaten senden.

Standardanwendungsansätze:

• Wenn Updates sofort im System gesendet werden sollen, ist zustandsbasiert eine schlechte Wahl, da das Versenden des gesamten Status teurer ist als nur ein Update-Vorgang. Delta-basiert funktioniert besser, aber in diesem speziellen Fall ist der Unterschied zu zustandsbasiert gering.
• Wenn Sie das Replikat nach einem Fehler synchronisieren müssen, sind zustandsbasiert und deltabasiert die perfekte Wahl. Wenn Sie op-based verwenden müssen, stehen folgende Optionen zur Verfügung:
  
  1) Wirf alle verpassten Operationen ab dem Moment des Ausfalls
  2) Eine vollständige Kopie einer der Replikate und ein Rollback verpasster Vorgänge
• Wie oben erwähnt, erfordert op-based, dass Updates genau einmal an jedes Replikat gesendet werden. Die Lieferanforderung kann nur einmal weggelassen werden, wenn der Effektor idempotent ist. In der Praxis ist es viel einfacher, die erste als die zweite zu implementieren.

Die Beziehung zwischen Op-basiert und State-basiert:

Zwei Ansätze können durcheinander emuliert werden, daher werden wir in Zukunft CRDT ohne Bezugnahme auf ein bestimmtes Synchronisationsmodell betrachten.

6. CRDT

6.1 Zähler

Eine Ganzzahl, die zwei Operationen unterstützt: inc und dec. Betrachten Sie als Beispiel mögliche Implementierungen für op- und zustandsbasierte Synchronisationen:

Op-basierter Zähler:

Natürlich nur Updates senden. Beispiel für inc:

function generator() { return function (counter) { counter += 1 } } 

Staatszähler:

Die Implementierung ist nicht mehr so ​​offensichtlich, da unklar ist, wie die Zusammenführungsfunktion aussehen soll.

Betrachten Sie die folgenden Optionen:

Monoton ansteigender Zähler (nur Inkrementzähler, G-Zähler):

Die Daten werden als Vektor mit einer Dimension gespeichert, die der Anzahl der Knoten (Versionsvektor) entspricht, und jedes Replikat erhöht den Positionswert mit seiner ID.

Die Zusammenführungsfunktion nimmt an den entsprechenden Positionen ein Maximum ein, und der Endwert ist die Summe aller Elemente des Vektors

$$

$$\ begin {align} inc () &: V [id ()] = V [id ()] + 1 \\ value () &: \ sum_ {i = 0} ^ {n} V [i] \\ Merge (C_1, C_2) &: i \ in [1..n] \ Ergebnis [i] = max (C_1.V [i], C_2.V [i]) \ end {align}$$

Sie können auch das G-Set verwenden (siehe unten)

Anwendung:

• Klicks / Treffer zählen (sic!)

Zähler mit Dekrementunterstützung (PN-Zähler)

Wir starten zwei G-Zähler - einen für Inkrementierungsoperationen, den zweiten - für Dekrementierung

Anwendung:

• Die Anzahl der angemeldeten Benutzer in einem P2P-Netzwerk, z. B. Skype

Nicht negativer Zähler

Eine einfache Implementierung existiert noch nicht. Schlagen Sie Ihre Ideen in den Kommentaren vor, diskutieren Sie.

6.2 Registrieren

Eine Speicherzelle mit zwei Operationen - Zuweisen (Schreiben) und Wert (Lesen).
Das Problem ist, dass die Zuweisung nicht kommutativ ist. Es gibt zwei Ansätze, um dieses Problem zu lösen:

Last-Write-Wins-Register (LWW-Register):

Wir geben die vollständige Reihenfolge durch die Generierung einer eindeutigen ID für jede Operation ein (z. B. Zeitstempel).

Ein Beispiel für die Synchronisation ist der Austausch von Paaren (Wert, ID):


Anwendung:

• Spalten in Cassandra
• NFS - Datei ganz oder teilweise

Register mit mehreren Werten (Multi-Value Register, MV-Register):

Der Ansatz ähnelt einem G-Zähler - wir speichern die Menge (Wert, Versionsvektor). Wert registrieren - alle Werte beim Zusammenführen - LWW separat für jeden Wert im Vektor.


Anwendung:

• Korb in Amazon. Damit ist ein bekannter Fehler verbunden, der nach dem Entfernen eines Artikels aus dem Warenkorb dort erneut angezeigt wird. Der Grund ist, dass das Register trotz der Tatsache, dass es eine Reihe von Werten speichert, keine Menge ist (siehe Abbildung unten). Amazon betrachtet dies übrigens nicht einmal als Fehler - es steigert sogar den Umsatz.
• Riak. In einem allgemeineren Fall verschieben wir das Problem der Auswahl des tatsächlichen Werts (Hinweis - es gibt keinen Konflikt!) Auf die Anwendung.

Erklärung des Fehlers in Amazon:

6.3 Lose

Die Menge ist der Grundtyp für die Erstellung von Containern, Karten und Diagrammen und unterstützt Operationen - add und rmv, die nicht kommutativ sind.

Betrachten Sie die naive Implementierung der op-basierten Menge, in der add und rmv ausgeführt werden, sobald sie eintreffen (add kommt gleichzeitig zu 1 und 2 Replikaten, dann geht rmv zu 1).


Wie Sie sehen können, haben sich die Repliken schließlich aufgelöst. Betrachten Sie die verschiedenen Optionen zum Erstellen konfliktfreier Mengen:

Wachsendes Set (G-Set):

Die einfachste Lösung besteht darin, zu verhindern, dass Elemente gelöscht werden. Alles, was bleibt, ist die Kommutierungsoperation, die kommutativ ist. Die Zusammenführungsfunktion ist die Vereinigung von Mengen.

Zweiphasenset (2P-Set):

Wir erlauben Ihnen das Löschen, aber Sie können es nach dem Entfernen nicht wieder hinzufügen. Zur Implementierung richten wir einen separaten Satz entfernter G-Set-Elemente ein (ein solcher Satz wird als Tombstone-Satz bezeichnet).
Beispiel für zustandsbasiert:

$$

$$\ begin {align} lookup (e) &: e \ in A \ land e \ notin R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ zusammenführen (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {align}$$

LWW-Element Set:

Die nächste Möglichkeit, eine konfliktfreie Menge zu implementieren, besteht darin, eine vollständige Reihenfolge einzuführen. Eine der Optionen besteht darin, für jedes Element eindeutige Zeitstempel zu generieren.

Wir erhalten zwei Mengen - add-set und remove-set, wenn add () aufgerufen wird, add (element, unique_id ()), wenn überprüft wird, ob sich ein Element in der Menge befindet - schauen Sie, wo der Zeitstempel größer ist - in remove-set oder in add-set

PN-Set:

Variation mit der Reihenfolge der Menge - wir starten einen Zähler für jedes Element, wenn wir es hinzufügen, erhöhen wir es, wenn wir es löschen, verringern wir es. Ein Element befindet sich in der Menge, wenn sein Zähler positiv ist.

Beachten Sie den interessanten Effekt: In der dritten Replik führt das Hinzufügen eines Elements nicht zu dessen Erscheinungsbild.

Beobachten-Entfernen-Set, ODER-Set, Add-Win-Set:

Bei diesem Typ hat Hinzufügen Vorrang vor Entfernen. Implementierungsbeispiel: Jedem neu hinzugefügten Element wird ein eindeutiges Tag zugewiesen (relativ zum Element und nicht zum gesamten Satz). Rmv entfernt ein Element aus der Menge und sendet alle gesehenen Paare (Element, Tag) zur Entfernung an die Replikate.

Remove-Win-Set:

Ähnlich wie beim vorherigen, aber gleichzeitig gewinnt / rmv rmv.

6.4 Grafik

Dieser Typ basiert auf vielen. Das Problem ist folgendes: Wenn gleichzeitig Operationen addEdge (u, v) und removeVertex (u) ausgeführt werden - was soll ich tun? Folgende Optionen sind möglich:

• RemoveVertex-Priorität, alle Kanten, die auf diesen Scheitelpunkt fallen, werden gelöscht
• AddEdge-Priorität, gelöschte Scheitelpunkte wiederhergestellt
• Wir verzögern die Ausführung von removeVertex, bis alle gleichzeitigen addEdge ausgeführt werden.

Die einfachste Option ist die erste, für die Implementierung (2P2P-Graph) reicht es aus, zwei 2P-Sets zu erhalten, eines für die Eckpunkte und das zweite für die Kanten

6.5 Karte

Karte der Literale:

Zwei zu lösende Probleme:

• Was tun bei gleichzeitigen Put-Operationen? In Analogie zu Zählern können Sie entweder LWW- oder MV-Semantik wählen
• Was tun mit simultan put / rmv? In Analogie zu Sets können Sie entweder Put-Wins- oder RMV-Wins- oder Last-Put-Wins-Semantik verwenden.

CRDT-Zuordnung (Karte der CRDTs):

Ein interessanter Fall, weil Ermöglicht das Erstellen verschachtelter Zuordnungen. Fälle, in denen verschachtelte Typen geändert werden, werden nicht berücksichtigt. Dies sollte vom verschachtelten CRDT selbst entschieden werden.

Karte als rekursiv zurücksetzen entfernen

Die Entfernungsoperation "setzt" den Typwert auf einen bestimmten Startzustand zurück. Für einen Zähler ist dies beispielsweise ein Nullwert.

Betrachten Sie ein Beispiel - eine allgemeine Einkaufsliste. Einer der Benutzer fügt Mehl hinzu und der zweite führt eine Kaufabwicklung durch (dies führt zu einem Aufruf des Löschvorgangs für alle Elemente). Infolgedessen bleibt eine Einheit Mehl auf der Liste, was logisch erscheint.


Karte entfernen-gewinnt

Die Operation rmv hat Vorrang.

Beispiel: In einem Online-Spiel hat ein Alice-Spieler 10 Münzen und einen Hammer. Dann treten gleichzeitig zwei Ereignisse auf: Auf Replik A hat sie einen Nagel hergestellt, und auf Replik B wird ihr Charakter durch Entfernen aller Objekte gelöscht:



Beachten Sie, dass bei Verwendung von "Entfernen als rekursiv" möglicherweise ein Nagel verbleibt. Dies ist nicht der richtige Zustand, wenn das Zeichen entfernt wird.

Update gewinnt Karte

Aktualisierungen haben Vorrang oder brechen frühere Vorgänge ab, um gleichzeitig rmv zu löschen.

Beispiel: In einem Online-Spiel wird der Alice-Charakter auf Replik B aufgrund von Inaktivität gelöscht, aber gleichzeitig wird Aktivität auf Replik A ausgeführt. Offensichtlich muss der Löschvorgang abgebrochen werden.


Bei der Arbeit mit einer solchen Implementierung gibt es einen interessanten Effekt: Angenommen, wir haben zwei Replikate, A und B, und sie speichern die Menge mit einem Schlüssel k. Wenn dann A den Wert des Schlüssels k löscht und B alle Elemente der Menge löscht, hinterlassen die Replikate am Ende eine leere Menge mit dem Schlüssel k.

Beachten Sie, dass eine naive Implementierung nicht ordnungsgemäß funktioniert. Sie können nicht einfach alle vorherigen Löschvorgänge rückgängig machen. Im folgenden Beispiel wäre bei diesem Ansatz der Endzustand der Anfangszustand, was falsch ist:

Liste

Das Problem bei diesem Typ besteht darin, dass Elementindizes auf verschiedenen Replikaten nach lokalen Einfüge- / Löschvorgängen unterschiedlich sind. Um dieses Problem zu lösen, wird der Operational Transformation-Ansatz angewendet. Bei der Anwendung der erhaltenen Änderung sollte der Index des Elements im ursprünglichen Replikat berücksichtigt werden.

7. Riak

Betrachten Sie als Beispiel CRDT in Riak:

• Zähler: PN-Zähler
• Set: OR-Set
• Karte: Update gewinnt Karte der CRDTs
• (Boolesches) Flag: OR-Set wo maximal 1 Element
• Register: Paare (Wert, Zeitstempel)

8. Wer verwendet CRDT?

Der Wiki- Bereich enthält gute Beispiele.

9. Referenzen

• Key-CRDT-Speicher
• Ein konfliktfrei replizierter JSON-Datentyp
• Eine umfassende Studie zu konvergenten und kommutativ replizierten Datentypen
• Konvergenter und kommutativer replizierter Datentyp
• Konfliktfreier replizierter Datentyp
• Ein Bluffers Guide für CRDTs in Riak
• CRDTs: Ein UPDATE (oder nur ein PUT)
• Konfliktfreie replizierte Datentypen: Ein Überblick
• Starke Konsistenz und konfliktfreie replizierte Datentypen
• Eventuell konsistente Datenstrukturen