CRDTs verstehen: Warum das Lesen von Zuständen gefährlich sein kann und wie man sicher arbeitet

Konfliktfreie Replikative Datentypen, besser bekannt als CRDTs, werden immer populärer im Zusammenhang mit verteilten Systemen und Anwendungen, die eine hohe Verfügbarkeit sowie Skalierbarkeit benötigen. Diese Datenstrukturen versprechen eine eventual consistency, also eine „irgendwann einheitliche Konsistenz“ über verschiedene Replikas hinweg. Doch was bedeutet „eventual“ wirklich, und wie sicher ist es tatsächlich, den Zustand von CRDTs einfach so zu lesen? Trotz der scheinbaren Vorteile sind CRDTs keineswegs unproblematisch, wenn es um das Lesen ihrer rohen inneren Zustände geht. In der Praxis kann ein unbedachtes Lesen zu unvorhersehbaren Fehlern führen, die im schlimmsten Fall unerwünschte oder gar katastrophale Auswirkungen haben – wie ein unerwarteter Einkauf, der Sie teuer zu stehen kommt. Das zeigt exemplarisch das Bild von jemandem, der versehentlich eine Ferrari-Bestellung bestätigt, nur weil eine Replik inkonsistente Sicht auf den Warenkorb hat.

Eventual consistency garantiert, dass alle Replikas eines Systems langfristig auf denselben Zustand konvergieren, sofern keine weiteren Updates durchgeführt werden. Das Problem ist jedoch, dass niemand vorhersehen kann, wann „irgendwann“ tatsächlich eintritt. Während Sie also den CRDT-Zustand abfragen, liegt die Gefahr darin, dass Ihnen noch nicht alle Updates zugegangen sind und der gelesene Zustand demnach unvollständig oder falsch ist. Die Herausforderung liegt im zeitlichen Versatz der Replikation und in der Tatsache, dass es in einem verteilten System sehr schwierig ist, mit Sicherheit festzustellen, ob aktuell keine weiteren Updates ausstehen oder unterwegs sind. Die sogenannte Termination Detection, also das Erkennen, wann alle Updates abgeschlossen sind, ist dabei ein nicht monotones Problem.

Ein einziger verspäteter Nachrichteneingang kann eine zuvor scheinbar abgeschlossene Aussage zurücknehmen. Die CALM-Theorie (Consistency as Logical Monotonicity) bringt eine wichtige Erkenntnis: In verteilten Systemen lässt sich eine Koordinationsfreiheit nur dann gewährleisten, wenn die Programme monotone Spezifikationen verwenden. Monoton bedeutet hier, dass eine Eigenschaft oder ein Wert sich nur in eine Richtung entwickelt, typischerweise immer größer oder stabiler wird, ohne zu zuvor Angebrachtem zurückzukehren. Mit anderen Worten: Ohne Koordination sind das konsistente Verteilung und das Ende der Aktualisierung nur dann garantierbar, wenn keine nicht-deterministischen oder rücksetzenden Zustandsänderungen möglich sind. Termination Detection dagegen ist genau das Gegenteil – sie ist nicht monotone und erfordert daher Koordination, um sicher zu funktionieren.

Diese theoretischen Grundlagen haben praktische Konsequenzen: Das direkte Lesen des internen Zustands vieler CRDT-Typen ist keine sichere Operation. Ein populäres Beispiel dafür ist der Zwei-Phasen-Set-CRDT (Two-Phase Set, kurz 2P-Set). Dieser verwaltet intern zwei Mengen: eine Menge der hinzugefügten Elemente sowie eine Menge der entfernten Elemente. Beim Mergen zweier Replikas werden die jeweiligen Add- und Remove-Mengen einfach vereinigt, wodurch Konsistenz entsteht. Das Lesen des aktuellen Zustands bedeutet jedoch die Differenz beider Mengen zu bilden.

Das Problem: Diese Differenz ist per Definition eine nicht monotone Operation – wenn Elemente aus der Entfernt-Menge hinzugefügt werden, schrumpft der Ergebniszustand. Das bedeutet Inkremente und Dekremente des Lesebestandes sind möglich, was gerade bei einem verteilten System verheerend sein kann. Ein reale Anwendungsszene illustriert das am besten: Stellen Sie sich vor, Sie haben in einem Online-Shop einen Alltagseinkaufswagen als CRDT realisiert. Sie legen eine Kartoffel und einen Ferrari in den Einkaufswagen. Minuten später erkennen Sie, dass der Ferrari zu teuer ist, und entfernen ihn aus dem Wagen.

Aufgrund der asynchronen Natur des Systems kann es passieren, dass die Replikationen nicht in der gleichen Reihenfolge erfolgen. Eine Replik könnte eine Bestellung für den Ferrari freigeben, bevor sie vom Entfernen informiert wird, weil Nachrichten verzögert sind. Daraus folgt, dass der Shop den Ferrari versendet, obwohl Sie diesen Schritt gar nicht wollten. Die Ursache liegt darin, dass nur die Merge-Operationen sicher sind, das Lesen des Zustands in seiner Rohform aber nicht. Doch was ist mit einfachen CRDTs wie dem Grow-Only-Set? Dessen Leseoperation ist tatsächlich monoton, denn es werden nur Elemente hinzugefügt, die nie wieder entfernt werden.

Das klingt erstmal sicherer. Allerdings liegt die Gefahr im nachgelagerten Code: Wenn Sie abhängige Funktionen implementieren, die nicht monoton sind – etwa eine essbarkeitsprüfung eines Sets von Zutaten, dann kann sich der Zustand des Sets nur erweitern, doch das Ergebnis der essbarkeitsüberprüfung kann sich im Zeitverlauf von falsch zu wahr und wieder zu falsch ändern. Das zeigt, dass auch monotone CRDT-Zustände in Kombination mit nicht-monotonen Logiken instabil sind. Es ist also nicht nur die Datenstruktur selbst, sondern die gesamte Verarbeitungslogik, die monotone Eigenschaften respektieren müssen, um eine sichere Anwendung zu garantieren. Wie kann man also sicher mit CRDTs arbeiten? Ein erster wichtiger Schritt ist die sorgfältige Kapselung des Zustands.

Ähnlich wie radioaktive Substanzen, die nicht direkter Berührung ausgesetzt werden sollten, empfiehlt es sich, den CRDT-Zustand nur über stark typisierte Schnittstellen zu exponieren. Vor allem Lesefunktionen sollten als „unsicher“ gekennzeichnet werden und nur mit Bedacht eingesetzt werden. Programmiersprachen mit starken Typsystemen, wie Rust, bieten hier bereits Möglichkeiten, solche Sicherheitsnetze einzubauen. Projekte wie Hydro befassen sich gezielt mit besten Praktiken für CRDTs und Monotonie. Zusätzlich können monotone Funktionen, sogenannte Threshold-Funktionen, Sicherheitsschienen geben.

Grundprinzip dieser Funktionen ist, dass sie Zustände in eine endliche monoton geordnete Skala abbilden, in der es ein gut definiertes oberes Maximum gibt. Solange wir vor dem Erreichen dieser Schwelle sind, sind sämtliche Werte noch unsicher, aber ab der Überschreitung des Thresholds können wir mit einer sicheren Wahrheit rechnen. Ein typisches Beispiel dafür ist ein Boolescher Wert mit false und true, bei dem true als oberer Grenzwert fungiert. Solche Funktionen erlauben eine sichere Abfrage, wann Zustände als abgeschlossen gelten können – und damit koordinationsfreie Termination erkennen. Diese Konzepte sind nicht nur theoretischer Luxus, sondern bilden die Praxisbasis für den Umgang mit verteilten Datenstrukturen in der Softwareentwicklung.

Dennoch sind Koordinationsmechanismen weiterhin unverzichtbar, dort wo Terminierungserkennung und nicht-monotone Logiken benötigt werden. Empirisch hat sich gezeigt, dass eine Mischung aus lokal koordinationsfreier Berechnung und gelegentlicher globaler Koordination, etwa über Konsensprotokolle wie Paxos oder Two-Phase Commit, ein interessantes Gleichgewicht ergibt. Gedanklich entspricht das der Erkenntnis, dass „die meisten Programme nicht vollständig monoton sind, aber überwiegend monoton“. Solange Koordination strategisch und sparsam eingesetzt wird, halten Systeme hohe Verfügbarkeit und Konsistenz im Einklang. Für Entwickler eine wichtige Empfehlung lautet daher, nicht der Versuchung zu erliegen, das gesamte CRDT-Innere einfach so auszulesen und zu verarbeiten.

Stattdessen sollte man zeitliche Koordination heranziehen, beispielsweise in Form einer expliziten Phasenbeendigung oder eines Schwellenwerts in den CRDT-Daten, bevor wichtige Entscheidungen getroffen werden. Auch bei der Verwendung komplexerer CRDT-Typen wie OR-Sets gilt, dass direkte, nicht abstrahierte Leseoperationen problematisch sind und meist Koordination erfordern, sonst verlieren sie ihre Vorteile gegenüber traditionellen Datenbanken. Angesichts dieser Komplexität ist auch das gestiegene Interesse an formaler Forschung verständlich, die über die Grundlagen der CALM-Theorie hinausgeht. Aktuelle Arbeiten, etwa im ICDT 25-Konferenzprogramm, untersuchen noch feinere Sicherheitsbereiche für free termination und monotoniebasierte Terminationsbedingungen. Ebenso wird an erweiterten Versionen der CALM-Theorie gearbeitet, die Bedingungen aufzeigen, unter denen auch „globale Wissensstände“ in Koordinationsfreiheiten eingegliedert werden können, zum Beispiel durch die Arbeiten von Baccaert und Ketsman.