Ich bin ein Neuling in verteilten Systemen und ich versuche, einen Einblick in das Konzept von CRDT zu bekommen. Ich weiß, dass es drei Notationen hat:Was ist CRDT in verteilten Systemen?
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
Kann jemand ein Beispiel geben, wo wir CRDT Systeme in verteilten verwenden? Vielen Dank im Voraus.
CRDTs sind inspiriert von der Arbeit von Marc Shapiro. In verteilten Datenverarbeitung, ein konfliktfreie replizierten Daten-Typ (abgekürzt CRDT) ist eine Art von Datenstruktur speziell entwickelte verwendet starke eventuelle Konsistenz (SEC) und Monotonie (Fehlen von Rollbacks) zu erzielen. Es gibt zwei alternative Wege, um SEC zu gewährleisten: betriebsbasierte CRDTs und zustandsbasierte CRDTs.
CRDTs auf verschiedenen Repliken können voneinander abweichen, aber am Ende können sie zusammengeführt werden sicher einen schließlich konsistenten Wert bereitstellt. Mit anderen Worten, CRDTs haben eine Merge-Methode, die idempotent, kommutativ und assoziativ ist.
Die beiden Alternativen sind äquivalent, wie man die anderen emulieren kann, aber der Betrieb basierte CRDTs erfordert 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, wo sie
Riak ist die populärste Open-Source-Bibliothek von CRDT ist und wird von Bet365 und League of Legends verwendet werden. Im Folgenden finden Sie einige nützliche Links, die Riak unterstützen.
1- Bet365 (Verwendet Erlang und Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2- League of Legends nutzt die Riak CRDT Implementierung für seine In-Game-Chat-System (die 7,5 Millionen gleichzeitige Benutzer und 11.000 Nachrichten pro Sekunde Griffe)
3- Roshi von Soundcloud implementiert, die ein LWW zeitgestempelt Set unterstützt: -Blog Beitrag: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
Diese drei Erweiterungen des Akronyms bedeuten im Grunde das Gleiche.
Eine CRDT ist konvergent, wenn dieselben Operationen, die in einer anderen Sequenz angewendet werden, dasselbe Ergebnis (konvergiert) ergeben. 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 das gleiche, egal welche der drei Erweiterungen Sie verwenden - obwohl ich persönlich lieber "Convergent".
Vielen Dank @cliffordheath. Sie haben alle drei Terminologien im Detail erklärt. Aber können Sie bitte Site ein Beispiel dafür? –
Der allererste Google-Hit für CRDT erklärt es im Detail mit Beispielen. Ich habe gerade erklärt, warum die Namen dasselbe bedeuten. – cliffordheath
CRDTs Math verwendet Konsistenz in einem verteilten Cluster zu erzwingen, ohne sich um Konsens zu kümmern und ein assoziierte Latenz/Nichtverfügbarkeit. Die Menge der Werte, die eine CRDT jederzeit annehmen kann, fällt in die Kategorie eines Semi-Gitters (insbesondere eines Joins-Semi-Gitters), das ein POSET (partiell geordnete Menge) mit einer Funktion der kleinsten oberen Grenze ist (
). LUB).
In einfachen Worten, ein POSET ist 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 < (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 Aktualisierungen dieses Datentyps erhöht werden müssen. CRDTs haben einen monoton ansteigenden Status, in dem Clients nie einen Status-Rollback beobachten.
Diese excellent article verwendet das Array, das ich oben als ein Beispiel verwendet habe. Wenn ein CRDT diese Werte beibehält, wenn 2 Replikate versuchen, einen Konsens zwischen (4,5) und (6,3) zu erzielen, können sie eine LUB = (6,5) als Konsens auswählen und ihr beide Replikate zuweisen. Da die Werte ansteigen, ist dies ein guter Wert, um sich festzulegen.
ist es 2 Möglichkeiten für CRDTs miteinander über Repliken synchron zu halten, können sie Zustand übertragen über periodisch (konvergente replizierten Datentyp), oder sie können Aktualisierungen (Deltas) übertragen über, wie sie sie erhalten (kommutativ replizierten Datentyp). Ersteres erfordert mehr Bandbreite.
SoundCloud Roshi ist ein gutes Beispiel (obwohl nicht mehr in der Entwicklung scheint es), sie speichern Daten mit einem Zeitstempel verbunden, wo der Zeitstempel ist offensichtlich inkrementieren. Alle Aktualisierungen, die mit einem Zeitstempel kommen, 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 bedeutet gleiche wie update2 von update1 gefolgt)
Writes werden an alle Cluster gesendet, und wenn bestimmte Knoten aufgrund eines Problems wie Langsamkeit oder Partition nicht reagieren, werden sie später über eine read-repair, aufholen zu erwarten, die, dass die gewährleistet, 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 der read-repair tauschen Replikate Zustand, und da Daten an die Semi-Gitter-Eigenschaft haftet, konvergieren sie.
PS. Systeme, die CRDTs verwenden, sind schließlich konsistent, d. H. Sie nehmen AP (hochverfügbar und partitionstolerant) in CAP theorem an.
die akzeptierte Mark Antwort, wenn es Ihre Frage beantwortet. –