Verteilte Daten ohne Mühe: Conflict-Free Replicated Data Types

Bei verteilten Anwendungen treten regelmäßig Konflikte auf, die sogenannten “fallacies of distributed computing”. Conflict-Free Replicated Data Types versprechen Abhilfe. Dieser Artikel gibt einen ersten Einblick in diesen vielversprechenden Ansatz.

Architektur/Methoden  –  1 Kommentare
Verteilte Daten ohne Mühe: Conflict-Free Replicated Data Types

Wenn die Daten von verteilten Anwendungen parallel an verschiedenen Orten geändert werden müssen, treten immer wieder Synchronisierungsprobleme auf. Bricht zudem die Netzwerkverbindung ab, scheitert jeglicher Synchronisationsversuch. Einen lohnenswerten Ansatz, um mit solchen Konflikten umzugehen, bieten die Conflict-Free Replicated Data Types (CRDTs).

Der vermutlich einfachste CRDT ist ein G-Set (Grow-Only Set). Ein G-Set ist eine Menge, zu der Elemente nur hinzugefügt, aber nicht entfernt werden können. Zunächst mag eine solche Datenstruktur überraschen. Tatsächlich gibt es aber viele Anwendungsfälle, in denen das Entfernen von Daten nicht gewünscht ist. Domain-Daten dürfen oft nicht gelöscht werden, um ein späteres Auditing zu ermöglichen. Des Weiteren werden G-Sets in anderen CRDTs genutzt, denn es ist üblich, komplexe CRDTs aus einfachen zusammenzusetzen.

Ein Knoten einer verteilten Anwendung ist eine Komponente, die im Bedarfsfall unabhängig von den anderen Teilen der Anwendung funktionieren kann. Jeder dieser Knoten arbeitet mit einer eigenen Kopie eines CRDTs, genannt Replika.

Das folgende Beispiel verdeutlicht die zugrundeliegende Funktionsweise: Zwei Benutzer, Anton und Berta, fügen parallel Elemente in einen G-Set ein, während sie offline sind. Anton fügt Äpfel und Birnen zu der Menge hinzu, Berta Birnen und Pfirsiche. Wenn die Verbindung zwischen den beiden Benutzern wieder hergestellt wird, synchronisieren sich die beiden Replikas automatisch, indem die Vereinigungsmenge gebildet wird. Anton und Bertha haben am Ende also Äpfel, Birnen und Pfirsiche in ihrer Replika des G-Sets.

Bereits dieses einfache Beispiel macht die Vorteile von CRDTs deutlich. Einerseits sind sie kinderleicht zu benutzen. Der Anwendungsentwickler kann fast vollständig ignorieren, dass es sich bei einem CRDT um eine verteilte Datenstruktur handelt, denn die gesamte Kommunikation und Synchronisierung lässt sich automatisieren. Andererseits erübrigen sich viele der üblichen Probleme von verteilten Anwendungen, die sogenannten “fallacies of distributed computing”. Instabile Netzwerkverbindungen sind kein Problem, denn CRDTs sind sogar offline weiter benutzbar. Auch die Latenz spielt keine Rolle mehr.

G-Set: a) Die Replikas des G-Sets sind synchronisiert, aber die Verbindung ist unterbrochen. Anton fügt eine Birne hinzu, Berta Kirschen. b) Die Replikas sind jede für sich valide, berücksichtigen aber nur lokale Änderungen. c) Die Verbindung wurde wieder hergestellt, die Replikas synchronisieren sich automatisch im Hintergrund.

Im obigen Beispiel ist es für Anton und Berta unerheblich, wie lange Nachrichten zwischen ihnen unterwegs sind, denn sie arbeiten nur auf ihren lokalen Kopien. Solange sichergestellt ist, dass die zwischen ihnen ausgetauschten Nachrichten irgendwann ankommen, werden ihre Replikas auch irgendwann synchronisiert.

Die Eigenschaft eines verteilten Systems, einen konsistenten Zustand zu erreichen, wenn die einzelnen Knoten verbunden sind und von außen keine Änderungen mehr hinzukommen, wird „Eventual Consistency“ genannt. Sie ist kein neues Konzept, aber bislang war die Umsetzung schwierig. Entweder man entschied sich für ein proprietäres Produkt, dessen Verhalten bei sich widersprechenden parallelen Änderungen oft nur ungenau dokumentiert war. Oder man machte es selbst, was kompliziert und fehleranfällig war. CRDTs bieten „Eventual Consistency“ gepaart mit einfacher Verwendung und klarem Verhalten im Konfliktfall.