Was ist CRDT in verteilten Systemen?

CRDTs sind inspiriert von der Arbeit von Marc Shapiro. Im verteilten Computing ist ein konfliktfrei replizierter Datentyp (abgekürzt CRDT) eine Art speziell entworfener Datenstruktur, die verwendet wird, um eine starke endgültige Konsistenz (SEC) und Monotonie (keine Rollbacks) zu erreichen. Es gibt zwei alternative Wege, um SEC zu gewährleisten: betriebsbasierte CRDTs und zustandsbasierte CRDTs.

CRDTs auf verschiedenen Replikaten können voneinander abweichen, aber am Ende können sie sicher zusammengeführt werden, was zu einem letztendlich konsistenten Wert führt. Mit anderen Worten, CRDTs haben eine Mischmethode, die idempotent, kommutativ und assoziativ ist.

Die beiden Alternativen sind äquivalent, da man die anderen emulieren kann, aber operationsbasierte CRDTs erfordern zusätzliche Garantien von der Kommunikations-Middleware. CRDTs werden verwendet, um Daten über mehrere Computer in einem Netzwerk zu replizieren und Updates auszuführen, ohne dass eine Remote-Synchronisierung erforderlich ist. Dies würde zu Konflikten bei der Zusammenführung von Systemen führen, die eine konventionelle Konsistenz-Technologie verwenden, aber CRDTs sind so ausgelegt, dass Konflikte mathematisch unmöglich sind. Unter den Einschränkungen des CAP-Theorems bieten sie die stärksten Konsistenzgarantien für verfügbare / partitionstolerante (AP) Einstellungen.

Einige Beispiele, in denen sie verwendet werden

Riak ist die populärste Open-Source-Bibliothek von CRDTs und wird von Bet365 und League of Legends verwendet. Im Folgenden finden Sie einige nützliche Links, die Riak unterstützen.

1- Bet365 (Verwendet Erlang und Riak) Ссылка

2- League of Legends verwendet die Riak CRDT-Implementierung für sein In-Game-Chat-System (das 7,5 Millionen gleichzeitige Benutzer und 11.000 Nachrichten pro Sekunde verarbeitet)

3- Roshi von SoundCloud implementiert, das ein zeitgestempeltes LWW-Set unterstützt: -Blog Beitrag: Ссылка

Diese drei Erweiterungen des Akronyms bedeuten im Grunde dasselbe.

Eine CRDT ist konvergent, wenn dieselben Operationen, die in einer anderen Sequenz angewendet werden, dasselbe Ergebnis erzeugen (konvergieren). Das heißt, die Operationen können kommutiert werden - es ist eine kommutative RDT. Der Grund, dass die Operationen in einer anderen Reihenfolge angewendet werden können und immer noch das gleiche Ergebnis erhalten, ist, dass die Operationen konfliktfrei sind.

Also CRDT bedeutet dasselbe, egal welche der drei Erweiterungen Sie verwenden - obwohl ich persönlich "Convergent" bevorzuge.

CRDTs verwenden Math, um Konsistenz in einem verteilten Cluster zu erzwingen, ohne sich um Konsens und die damit verbundene Latenz / Nichtverfügbarkeit kümmern zu müssen.

Die Menge der Werte, die eine CRDT jederzeit annehmen kann, fällt in die Kategorie eines Semi-Gitters (insbesondere eines Joins-Semi-Gitters), welches ein POSET (partiell geordnete Menge) mit einer Funktion der kleinsten oberen Grenze (LUB) ist ).

Vereinfacht ausgedrückt ist ein POSET eine Sammlung von Artikeln, in denen nicht alle vergleichbar sind. Z.B. in einem Array von Paaren: {(2,4), (4, 5), (2, 1), (6, 3)} , (2,4) ist & lt; (4,5) , kann aber nicht mit (6,3) verglichen werden (da ein Element größer und das andere kleiner ist). Nun, ein Semi-Gitter ist ein POSET, in dem 2 Paare gegeben sind, auch wenn Sie die beiden nicht vergleichen können, können Sie ein Element finden, das größer als beides ist.

Eine weitere Bedingung ist, dass Updates für diesen Datentyp erhöht werden müssen. CRDTs haben einen monoton ansteigenden Zustand, in dem Clients niemals den Status-Rollback beobachten.

Dieser exzellente Artikel verwendet das Array Ich habe oben als Beispiel verwendet. Wenn eine CRDT diese Werte beibehält, wenn zwei Repliken versuchen, einen Konsens zwischen (4,5) und (6,3) zu erreichen, können sie eine LUB = (6,5) als Konsens auswählen und ihr beide Replikate zuweisen. Seit den Werten steigen, das ist ein guter Wert, um sich zu beruhigen.

CRDTs können auf zwei Arten über Replikate hinweg miteinander synchronisiert werden, sie können den Status regelmäßig (konvergenter replizierter Datentyp) übertragen oder sie können Aktualisierungen (Deltas) direkt übertragen, wenn sie diese erhalten (kommutativ replizierter Datentyp). . Ersteres erfordert mehr Bandbreite.

SoundClouds Roshi ist ein gutes Beispiel (obwohl es nicht mehr in der Entwicklung scheint), sie speichern Daten, die mit einem Zeitstempel verknüpft sind, wo der Zeitstempel offensichtlich inkrementiert. Alle Aktualisierungen, die einen Zeitstempel enthalten, der kleiner oder gleich dem gespeicherten ist, werden verworfen, was Idempotenz (wiederholte Schreibvorgänge sind OK) und Kommutativität (Schreibzugriffe in Ordnung) gewährleistet. Kommutierbarkeit ist a=b means b=a , was in diesem Fall update1 gefolgt von update2 ist dasselbe wie update2, gefolgt von update1)

Schreibvorgänge werden an alle Cluster gesendet, und wenn bestimmte Knoten aufgrund eines Problems wie Langsamkeit oder Partition nicht antworten, wird erwartet, dass sie später über ein read-repair aufholen, wodurch sichergestellt wird, dass die Werte konvergieren. Die Konvergenz kann über 2 Protokolle erreicht werden, wie ich oben erwähnt habe, propagieren Zustand oder Updates für andere Replikate. Ich glaube, Roshi macht das erste. Als Teil von read-repair konvergieren Replikate, und da Daten an die Semi-Gitter-Eigenschaft gebunden sind, konvergieren sie.

PS. Systeme, die CRDTs verwenden, sind schließlich konsistent, dh sie verwenden AP (hoch verfügbar und partitionstolerant) im CAP-Theorem .

Noch eine ausgezeichnete Lektüre zu diesem Thema.