CRDT

Lisa:

Hallo und herzlich willkommen zu einer neuen Episode vom INNOQ Podcast. Heute zu einer besonderen Folge, zur Folge 99, einer Schnapszahl-Folge, haben wir uns das Thema CRDTs ausgesucht. Was das ist, was sich dahinter versteckt, warum das Ganze? Das werden uns heute Lucas Dohmen und Lars Hupel erzählen. Hallo ihr beiden.

Lars:

Hallo Lisa.

Lucas:

Hallo.

Lisa:

ich würde gerne mit der Basic Frage des Jahrhunderts anfangen. Was sind überhaupt CRDTs?

Lars:

Ja, also CRDTs steht für Conflict-free Replicated Data Type. Damit sollte eigentlich alles gesagt sein, oder?

Lucas:

Genau, da können wir an der Stelle die Aufnahme beenden. Scherz beiseite, es ist erst mal eine Art von Datentyp. Wir kennen wahrscheinlich viele, verkettete Liste wäre jetzt ein Datentyp. Und das sind Datentypen, die einem dabei helfen, Konflikte zu lösen. Nicht Konflikte im Team, sondern Konflikte in den Daten. Also beispielsweise, wir haben irgendwie eine Einkaufsliste und wir wollen dafür sorgen, dass zwei Leute daran getrennt voneinander arbeiten können. Und am Ende kommt aber dieselbe Einkaufsliste dabei raus. Das ist etwas, was man mit CRDTs lösen kann.

Lars:

Genau. Die Grundidee ist eigentlich, da steckt repliziert, also replicated mit drin, dass man mehrere Kopien von diesem Datentyp haben kann und man durch das Conflict-free diese Kopien dann immer wieder auf einen Stand bringen kann.

Lucas:

Genau.

Lisa:

Wenn ihr das so sagt, muss ich als erstes an Git denken. Da kann ich auch vor mich hin committen, ganz lustig und irgendwann kann ich es pushen und repliziert ist es ja, weil jeder irgendwie die Git-Historie auf seinem eigenen Rechner hat. Ist das so was in der Richtung oder hat das gar nichts damit zu tun?

Lucas:

Also grundsätzlich ist es quasi ein distributed, aber nicht conflict-free data type, weil wir kennen das wahrscheinlich alle. Wenn ich jetzt im Projekt erwas committe, dann passiert das erst mal offline. Wenn ich bei mir auf meinem Rechner jetzt einen Commit mache und der Lars ist im gleichen Projekt, dann kriegt der Lars es erst mal nicht mit. Bei dem lädt der Commit nicht. Und das ist erst mal grundsätzlich anders als bei früheren Versionskontrollsystemen wie SVN oder CVS, wo Commits grundsätzlich immer auf dem Server passiert sind, passieren die erst mal quasi “offline first”. Die passieren lokal bei mir, ich brauche nicht mit dem Internet verbunden zu sein, nicht mit Git verbunden zu sein. Das funktioniert einfach. Das, was es aber dafür auf der Gegenseite bedeutet ist, dass wenn ich dann mein Commit versuche auf den Server zu legen, könnte es natürlich sein, dass der Lars in der Zwischenzeit auch irgendwas committed hat. Vielleicht hat die Lisa auch noch irgendwas committed. Und jetzt muss irgendwie dieser Konflikt aufgelöst werden. Grundsätzlich ist es so, wenn wir verschiedene Orte haben, an den Daten geschrieben werden können, dann können immer Konflikte passieren. Das ist nicht vermeidbar. Wir können immer entweder sagen: Es gibt nur eine autoritäre Stelle, die sagt: Ich weiß, was geschrieben wurde. Das ist die eine Möglichkeit. Die andere Möglichkeit ist: Es gibt mehrere, und das bedeutet, es kann zu Konflikten kommen. Und Git ist dafür echt ein gutes Beispiel. Und ich vermute, die Entwicklerinnen und Entwickler, die diesem Podcast zuhören, die hatten auch alle schon ein Git Merge Konflikt und kennen auch, dass das manchmal schon relativ unangenehm sein kann, den auflösen zu müssen. Gerade wenn man mehrere Commits gemacht hat und die andere Person auch und dann versucht man das zusammenzubringen, dann kann das schon mal ganz schön fies werden. Und diese Art von User Experience wollen wir vielleicht nicht unseren Anwenderinnen und Anwendern, die unsere Webseite benutzen, zumuten, kann man sich jetzt vielleicht vorstellen. Also stellt euch mal vor, wir machen so ein Online Word und dann müssen wir das durchspielen in so einem Merge Editor. Da würden wahrscheinlich unsere Kunden und Kundinnen sagen: Nein, danke. Und das ist so ein bisschen auch ein Grund, warum man sich auf jeden Fall mal diese CRDTs anschauen kann.

Lars:

Aber interessant, dass du Word ansprichst, weil aktuell im Projekt, da programmiere ich gar nicht so viel, sondern ich mache ganz viele Dokumente in Word auf SharePoint und auch bei Word, wo man denkt, das ist eine Software, die für eine sehr breite Masse von Anwenderinnen gemacht wird, auch die, die nicht so technikaffin sind. Auch da kann man sich durchaus solche Merge Konflikte einhandeln. Also ich weiß nicht, ob jemand solche Word Dokumente aus der Hölle kennt, aber dann versucht man da irgendwie in diesem SharePoint zu speichern. Dann kommt auch so plötzlich: Sie haben einen Konflikt produziert und dann blickt man auch überhaupt nicht durch. Das ist jetzt nicht nur so, dass das jetzt Git da die einzige Software ist, die einem solche Konflikte vor die Füße kotzt. Da gibt es noch zahlreiche andere Softwares, die so was machen, auch welche, die jetzt nicht nur sich an Entwicklerinnen richtet.

Lucas:

Und was bedeutet das jetzt für uns, wenn wir eine Website bauen? Lucas hatte eben schon gesagt, wenn die Leute auf meiner Webseite sind, dann soll denen das natürlich nicht so passieren wie bei Git zum Beispiel. Aber was bedeutet das für mich, wenn ich jetzt eine Anwendung entwickle? Was muss ich tun? Worauf soll ich achten?

Lars:

Bei den allermeisten Anwendungen, die es heutzutage so gibt, Webanwendungen, wird dieses Problem weitestgehend erst mal ignoriert, weil man dann sagt: Ja, das ist eine Webseite, die ist im Browser und wenn du offline bist, hast du ein Problem. Und wenn wir uns zum Beispiel Google Docs mal anschauen, die haben das so gelöst, dass wenn die Verbindung abbricht, kann man nicht weiterschreiben. Und wenn jemand anderes schreibt, wird es quasi live auf mein System rüber kopiert und dann kann es gar nicht zu solchen Konflikten kommen. Das hat natürlich dann auch den Nachteil, dass wenn ich gar keine Internetverbindung habe, wenn ich zum Beispiel irgendwo in einer schönen Hütte in den Alpen bin, gerade im Urlaub, dann kann ich da halt nichts editieren. Und das ist natürlich blöd. Aber grundsätzlich ist es mal so, das werden sicherlich die allermeisten von unseren Zuhörerinnen schon mal gemerkt haben, dass es da ganz viele Sachen gibt, wo es entweder offline gar nicht unterstützt wird oder dass dann nur so halb unterstützt wird. Und dann hat man manchmal auch Datenverlust. Also dann tippt man irgendwas ein und dann ist wieder die Internetverbindung da, dann ist es plötzlich weg. Also ich glaube, diese Erfahrung haben schon sehr viele Leute gemacht, dass das einfach dieses Thema Offlinefähigkeit Synchronisierung einfach komplett ignoriert wird.

Lucas:

Ich glaube, dass es auch erst mal wichtig ist, noch mal mit den Fachleuten durch zu sprechen, was genau wir denn haben wollen. Ich nehme noch mal das Beispiel von Lars gerade mit Google Docs. Da ist es jetzt nicht so, dass die Anwendung, wenn du offline bist, einfach gar nichts mehr tut, sondern sie geht in einen “Read Only” Modus. Das heißt also, ich kann nur noch lesen, aber ich kann nicht mehr schreiben. Und das kann auch für viele Anwendungen schon gut sein. Es ist viel einfacher zu implementieren. Und dann sagt man einfach: Sobald du offline bist, kannst du nur noch die Version, die du kennst, offline anschauen und fertig. Das ist aber, wie Lars schon sagte, in manchen Situationen auch total blöd. Jetzt will ich vielleicht noch mein Dokument weiterschreiben, jetzt geht es nicht mehr, aber zumindest kann ich es lesen. Das ist schon besser als bei vielen Webanwendungen, wo ich noch nicht mal lesend auf meine Anwendung zugreifen kann. Ein Beispiel für mich wäre jetzt Slack. Slack kennen wahrscheinlich die meisten, als ein Unternehmenschat. Da ist es erst mal so, dass es irgendwie logisch ist, dass die Anwendung nur funktioniert, wenn wir online sind. Weil wenn ich jetzt einem von euch beiden eine Nachricht schicken will, dann geht das nur, wenn ihr da seid. Also hat das wenig Wert offline. Aber es gibt einen Teil von der Anwendung, der offline durchaus total interessant sein könnte. Und das wäre zum Beispiel das Archiv. Wenn ich jetzt irgendwie schnell auf eine vergangene Information zugreifen will: Wann war noch mal das nächste INNOQ Event, das hat doch jemand geschrieben und ich möchte das schnell suchen können, dann wäre es echt cool, wenn ich das Archiv offline zur Verfügung hat. Es ist in Slack nicht so. Wenn ich offline bin, kann ich auch nicht suchen, dann kann ich mit ein bisschen Glück noch bisschen hoch scrollen und das war’s dann aber auch. Und mehr ist einfach nicht da. Auch bei so einer Anwendung könnten wir uns überlegen, dass bestimmte Teile der Anwendung auch offline attraktiv sein könnten. Das heißt also, für mich ist Offlinefähigkeit nicht unbedingt eine Entscheidung, die für die Gesamtanwendung getroffen werden muss, sondern kann auch für Teile der Anwendung getroffen werden, weil die eben offline Sinn ergeben. Dann, was Lars auch schon erwähnt hat, könnte es natürlich sein, ich möchte einfach nur dafür sorgen. Mir fällt gerade nichts ein. Ich glaube das war bei Jira. Da hatte ich das auf jeden Fall auch schon mal, das war so eine Art Ticketsystem und ich habe ein ganz langes Ticket geschrieben und dann habe ich auf Abschicken gedrückt und aus irgendeinem Grund war kurz mal die Verbindung weg und dann war mein gesamter Text verloren. Dann war alles, was ich geschrieben habe, einfach weg und ich konnte es auch nicht wiederherstellen. Das ist eine unglaublich schreckliche User Experience für alles, wo man irgendwie mehr als, wenn du zwei Zeilen schreibst, ist es jetzt nicht so wild, aber wenn du so ein ganzes Ticket geschrieben hast und abschickst und das ist weg, das ist schon sehr ärgerlich. Das wäre jetzt auch eine Möglichkeit, wo es jetzt erst mal gar nicht so sehr um Konflikte oder sowas geht, sondern wenn ich ein neues Ticket erzeuge, dann steht es dann mit nichts im Konflikt, dann möchte ich nur dafür sorgen, dass die Information, die ich schicke, irgendwie offline mit gespeichert wird, dass falls jetzt mein Browserfenster abstürzt oder meine Internetverbindung kurz weg ist, wenn ich es abschicke, dass da die ganzen Daten nicht verloren gehen. Das wäre auch so eine Art von User Experience und das würde ich jetzt auch klar abgrenzen für diesen Podcast. Es gibt jetzt diesen Leserzugriff. Dafür brauche ich nicht so was wie CRDTs. Und auch wenn ich jetzt einfach nur quasi lokal zwischenspeichern möchte, dass ich Informationen nicht zum Server schicke, brauche ich dafür auch nicht unbedingt CRDTs. Die brauche ich tatsächlich erst, wenn ich in einer Situation bin, wo mehrere Geräte oder mehrere Personen versuchen den gleichen Datensatz zu editieren. An dem Punkt sollte ich mir auf jeden Fall CRDTs anschauen, aber die anderen Fälle sind wirklich uninteressant. Wir sollten auf jeden Fall immer erst mal abklären, was brauchen wir denn tatsächlich? Weil für viele Anwendungsfälle wäre das eigentlich völlig übertrieben, dann da auf CRDTs zu setzen oder auf solche kompliziertere Technologien. Mir ist es nur deswegen auch wichtig, darauf einzugehen, weil ich das jetzt schon häufiger gehört habe, wenn Leute eine Single Page Anwendung bauen, wie jetzt zum Beispiel eine React Anwendung oder eine Angular Anwendung, dann hat man erst mal dafür gesorgt, dass man alles auf dem Client rendern kann ohne mit dem Server Kontakt aufnehmen zu müssen. Aber das heißt auf keinen Fall, dass wir jetzt schon offline fähig sind. Das ist mir ganz wichtig. Das heißt jetzt erstmal nur, wir können offline in der Anwendung hin und her springen. Aber was genau passiert, wenn ich irgendwelche Sachen speichere und wenn dann im Hintergrund ein JSON-Request an einen Server geschickt wird und wenn das failed und keiner merkt das und der ist einfach weg, dann ist das das Gegenteil von offline fähig. Das ist noch schlimmer, als wenn einfach eine Fehlerseite angezeigt wird, weil ich vielleicht nicht mal mitbekomme, dass es kaputt ist. Deswegen finde ich es immer wichtig, darauf nochmal einzugehen, dass man erst noch mal die Requirements und ich würde sagen, es sind auf jeden Fall fachliche Anforderungen, die man da hat, noch mal betrachtet und überlegt: Was genau brauchen wir an Offlinefähigkeit? Brauchen wir vielleicht gar keine oder brauchen wir nur Lesen? Oder brauchen wir nur einen Zwischenspeicher, der Sachen, bevor wir die zum Server schicken, in einem Local Storage abspeichert? Oder brauchen wir tatsächlich irgendwas, wo mehrere Parteien gleichzeitig editieren können?

Lisa:

Quasi die Offlinefähigkeit als Qualitätsziel in Betracht ziehen und mit den Stakeholdern abklären, ob das gewünscht ist oder nicht und durchaus immer in Betracht ziehen, wenn man eine Webanwendung baut. Das würde ich mir jetzt für die Offlinefähigkeit mit Lesezugriff merken wollen.

Lars:

Mit dem Fachbereich sprechen ist generell eine gute Idee.

Lisa:

Das habe ich auch schon mal gehört. Und jetzt sagtest du, Lesezugriff haben wir jetzt quasi abgefrühstückt. Und jetzt geht es um diese ganzen Merge Konflikte, Schreibkonflikte, Git Merge Konflikte hatten wir vorhin schon. Du hast vorhin auch schon eine Einkaufsliste erwähnt. Ich glaube, das ist ein gutes Beispiel, wo man sich in einem Podcast auch langhangeln kann. Wir sind hier zu dritt. Wir wollen für unsere riesige Silvesterparty einkaufen. Lars schreibt Käse auf die Liste. Lucas schreibt Champagner auf die Liste und ich schreibe jetzt Lebkuchen auf die Liste oder was auch immer. Und zwei von drei waren offline. Einer von drei nicht und unsere Einkaufsliste schmatzt jetzt ab, weil das genau so war. Wie geht man damit um?

Lars:

Da hast du schon ein schönes Beispiel genannt. Es gibt nämlich einen konkreten CRDT, also CRDT ist ein Bündel von verschiedenen Datentypen. Also so ein bisschen kann man sich das vorstellen, wie die verteilte Variante von Java.util Collections. Und eines von diesen Datentypen einfacher ist in so einem Grow Sets, also Mengen, die immer nur wachsen können. Sets, wie man sie auch in Java und in Go und sonstwie kennt. Das heißt, das sind Collections, wo jedes Element nur einmal drin sein darf und wo auch die Reihenfolge keine Rolle spielt. Weil wenn wir jetzt zum Beispiel zu dritt einkaufen gehen, dann ist das eigentlich völlig egal, ob zuerst die Tiefkühlpizza im Einkaufswagen landet oder zuletzt. Das ist eigentlich völlig egal, Hauptsache, wir haben dann irgendwann alle zusammen und das ist jetzt relativ einfach erklärt. Wir wollen jetzt eine Anwendung, zum Beispiel eine App für das Mobiltelefon und dann können einfach alle irgendwelche Items hinzufügen zu der Einkaufsliste. Und das Synchronisieren ist dann sehr einfach. Man nimmt einfach alles zusammen, streicht die Duplikate raus. Wenn jetzt zum Beispiel sowohl Lucas als auch ich den Champagner aufgeschrieben haben, dann kommt der dann nur einmal raus, am Ende in der Liste. Dieser Zustand kann dann auf alle verteilt werden. Und das Coole ist jetzt auch, dadurch, dass es eine Menge ist und dass die nicht tube ist, spielt es keine Rolle, wer mit wem zuerst synchronisiert. Nehmen wir jetzt mal dieses Szenario. Wir haben drei Leute und dann können zuerst Lucas und ich synchronisieren, dann haben wir zumindest schon mal einen gemeinsamen Stand. Dann kann Lucas mit Lisa synchronisieren. Dann hat Lisa das von mir auch mitgekriegt, weil ich habe das dem Lucas gegeben und dann kann ich noch mal mit Lisa synchronisieren und dann haben wir alle den gleichen Stand. Und die Garantie von diesem Datentyp ist jetzt, dass es völlig egal ist, in welcher Reihenfolge wir das synchronisieren, solange mal jeder mit jedem spricht, zu einem bestimmten Zeitpunkt, dann kriegt man da immer einen gemeinsamen Stand. Und für eine Einkaufsliste ist ein Grow Set ganz praktisch. Das hat allerdings einen kleinen Nachteil, wie der Name Grow Set darauf hindeuten lässt, man kann aus dem Grow Set nichts mehr löschen, weil sonst nämlich das Problem ist, wir sind jetzt alle an einem bestimmten Stand und dann sage ich: Nee, lass mal doch keinen Champagner kaufen, lass uns doch vielleicht nur den billigen Sekt kaufen und ich streiche jetzt den Champagner raus. Dann ist es jetzt erst mal nicht unmittelbar klar, ob ich jetzt einfach nur den Champagner noch nicht mitgekriegt habe bei mir oder ob ich den jetzt wirklich aktiv aus dem Set entfernt habe. Und dann könnte es sein, dass wenn ich jetzt dann das nächste Mal synchronisiere, denn der Champagner wieder auftaucht auf meiner Liste. Und ich glaube, das haben auch ganz viele Leute schon mal gehabt. Eine Anwendung, wo einfach gelöschte Daten plötzlich wieder auftauchen und nicht ganz klar ist, wann die jetzt gelöscht worden sind oder ob sie überhaupt gelöscht worden sind.

Lucas:

Und das ist auch was. Da kann man auch noch mal darauf eingehen, dass das tatsächlich noch nicht mal unbedingt was mit Offlinefähigkeit zu tun hat über dieses Problem nachzudenken, weil eine der ersten Firmen, die ein bisschen über dieses ganz große Problem nachgedacht haben, war halt Amazon. Bei Amazon gibt es den Warenkorb. Und wenn ich jetzt irgendwas in den Warenkorb reinwerfe und auf einem anderen Gerät auch was reinwerfe, dann muss das irgendwie dafür sorgen, dass das am selben Punkt landet. Das ist bei Amazon so, das ist jetzt erst mal nicht offline fähig. Das auch nicht so viel Sinn ergibt bei einem Onlineshop. Aber da ist es jetzt trotzdem so, dass die keine einfache Datenbank benutzen, die immer vollständig alle auf dem selben Stand sind, weil das einfach Performance mäßig nicht geht. Das führt jetzt ein bisschen zu weit, aber auch da müssen wir mit diesem Problem umgehen. Was passiert denn, wenn ich zwei Versionen von diesem Warenkorb auf meinem Server habe und ich muss die wieder zusammenbringen? Und da ist es halt, es gibt ein Paper von Amazon, wo die das beschrieben haben, dass auch viele weitere Sachen inspiriert hat. Und da haben die gesagt, im Fall der Fälle sagen wir, wenn wir zwei Instanzen vom Warenkorb haben, dann nehmen wir die Union von beiden, also die Zusammenführung von allen Sachen, die da drin sind. Das heißt also, wenn ich jetzt an dem einen Ort was gelöscht habe und bei dem anderen Ort nicht, dann nehmen die im Zweifel das lieber den Warenkorb rein, weil die sagen: Ja, mehr Dinge im Warenkorb ist mehr Umsatz und das ist besser. Das heißt also, das ist auch wieder eine fachliche Entscheidung, dass Amazon sich dafür entschieden hat. Im Zweifel nehmen wir es lieber mit rein. Und so ähnlich könnten wir das bei unserer Einkaufsliste. Da könnten wir sagen, wenn jetzt zwei Leute da was reingeworfen haben und ich bin mir nicht siche, ob das Rauswerfen oder das Reinwerfen wichtiger wäre, könnten wir das Reinwerfen mit reinnehmen, im Zweifel kaufen wir eine Sache zu viel und dann haben wir Champagner und Billig Schnaps und das ist immer noch besser als gar nichts. Das könnte sein.

Lucas:

Aber vielleicht sollten wir auch noch kurz erklären, dass auch bei den CRDTs eine Lösung für dieses Problem auch existiert, weil man sich fachlich dafür enthält, dass das nicht gut genug ist, das so zu machen. Und zwar hat das den etwas morbiden Namen Grabstein oder tombstone auf Englisch. Es kann also sein, dass man dann das so implementiert, dass gelöschte Einträge gar nicht wirklich gelöscht werden. Sie werden nur als gelöscht markiert. Sie werden also mit so einem Grabstein versehen. Und das ist auch tatsächlich gar keine neue Technologie. Also gerade, wenn man sich die Datenbankprodukte anschaut, zum Beispiel so ein Postgres, wenn man dann DELETE ausführt, dann wird die Zeile nicht wirklich gelöscht, sondern sie wird als gelöscht markiert. Beim Synchronisieren kann man dann eben feststellen: Aha, ich habe jetzt hier vom Lars den Datensatz bekommen. Soundso ist jetzt gelöscht worden. Dann können es alle anderen auch als gelöscht markieren. Dann muss man aufpassen, dass wenn man in einen Datensatz überhaupt mal gelöscht worden ist, kann man ihn da nicht wieder hinzufügen. Das ist dieses Konzept, was sich Two-Phase Set. Das Two-Phase-Set ist auch ein CRDT, eine Instanz von diesem CRDT Bündel, womit man genau das Löschen auch mit umsetzen kann. Und die nächste Frage, die dann meistens gestellt wird, ist: Ja gut, aber wenn ich jetzt diese ganzen Grabsteine mit mir umherschleife, wird dann nicht meinen Datenbestand riesig? Stimmt. Man kann dann Checkpoints implementieren, dass man sagt: Wenn jetzt alle bekannten Kopien meines Datentyps synchronisiert sind, dann lasse ich so einen Prozess laufen, der die einfach dann rausschmeißt. Und ist es wieder gut. Bei PostgreSQL würde man das Vacuuming nennen, glaube ich. Man geht dann mit dem Staubsauger durch und räumt die Grabsteine ab. Um mal in dieser gemischten Metapher zu bleiben. Und dann ist auch wieder der Zustand wiederhergestellt, wo man keine unnützen Daten mehr speichern muss.

Lucas:

Genau, das hat Lars schon erwähnt, aber nochmal um das zu betonen Das ist nur dann möglich, wenn wir uns sicher sein können, dass alle beteiligten Parteien diesen Stand schon hatten. Weil sonst könnte es sein. Sagen wir jetzt mal, wir haben irgendwie drei Geräte. Lisas Handy, mein Handy und mein uralt Handy und das liegt irgendwo im Sofa. Und jetzt ist das aber nicht mehr mit dem Internet verbunden, weil es gar keinen Akku mehr hat. Aber da hatte ich noch eine ganz wichtige ToDo für unsere Silvesterparty aufgeschrieben und ich weiß es auch schon gar nicht mehr ,aber es liegt irgendwo im Sofa und jetzt wird irgendwie auf dem Server dieser Cleaner Prozess gestartet und der geht davon aus, dass alle Leute den aktuellen Stand haben, aber das Sofagerät hat es nicht. Dann kann es dazu kommen, dass dieser Konflikt dann im Nachhinein nicht mehr aufgeräumt werden kann. Also die CRDTs, grundlegend, sagen alle, die Gesamthistorie ist bekannt und alles was wir an Vacuuming usw. durchführen, sind quasi Optimierungen, die notwendig für die Praxis sind, ohne Zweifel. Aber wo wir dann uns überlegen müssen, wie können wir weiterhin die Garantien einhalten? Und es klingt jetzt erst mal so, der Lucas sagt: Ja, dann geht es gar nicht. Aber das ist nicht so, sondern grundsätzlich wissen wir ja, welche Geräte mit beteiligt waren, also welche Geräte diesen Datensatz haben. Das Problem ist nur, wenn tatsächlich eins der Geräte längere Zeit offline ist, müssen wir eine Entscheidung treffen, die aber auch wieder eher eine fachliche Entscheidung ist. Ist dieses Gerät einfach weg. Es kann auch sein, dass ich ein Gerät hatte und habe einen Backup eingespielt. Und das gibt es einfach nicht mehr ,das Gerät. Oder ist das Gerät tatsächlich einfach nur lange offline und wir müssen irgendwie dafür sorgen, dass es wieder online geht. Und dann müssen wir einfach eine Entscheidung treffen. Aber grundsätzlich sollten wir in der Praxis auf jeden Fall, wenn wir solche Sachen machen, über so eine Strategie nachdenken, wie wir an Checkpoints kommen. Und das ist bei einem Online System, bei einer Datenbank, einer verteilten Datenbank, ist das wesentlich einfacher zu handhaben als bei Geräten, weil das hatten wir am Anfang bei der Motivation noch ein bisschen vergessen, das würde ich noch mal kurz nachtragen. Eine Sache, die auch ganz wichtig ist, die bei manchen noch nicht so ganz angekommen ist, ein ganz wichtiger Grund für solche Synchronisationssachen ist auch, dass die meisten Leute mittlerweile nicht mehr ein Gerät haben, sondern mehrere. es ist nicht so, dass jede Benutzerin exakt ein Gerät hat und mit dem ist sie mit dem Internet verbunden und fertig, sondern man einen Smartphone, einen Computer. Vielleicht hat man sogar noch ein Tablet und alle davon sollen diese Daten haben und dann hat man noch zusätzlich noch eine zweite Person und die hat auch noch mal drei Geräte und die müssen alle miteinander synchronisiert werden. Und gerade wenn man mehrere Geräte hat, sind sie auch nicht immer alle online, sondern manche sind dann einfach vielleicht irgendwo im Schrank oder im Schuhkarton, weil es ein Raspberry PI ist. Und dann muss man überlegen, was man dann tut. Und das wollte ich einfach nur mal erwähnen, weil ich das einfach immer wichtig finde, wenn man die Use Cases sich noch mal durchschaut. Was ist denn, wenn wir ein Gerät haben, was wirklich nur einmal die Woche online ist, weil es einfach nicht so häufig benutze? Funktioniert es dann noch? Aber grundsätzlich sind diese zwei P-Sets eines von denen, ich würde sagen, immer noch relativ einfachen Datenstrukturen, obwohl es schon eine komplexere ist als so ein Grow Set, aber immer noch ein relativ einfacher Baustein, der schon mal ganz gut dieses Problem von diesen tombstones oder Grabstein gut demonstriert, das man dann hat. Und das hat man tatsächlich bei den komplexeren Datentypen einfach noch mal um 1 hoch gedreht.

Lisa:

Ich hätte schon mal eine Frage zu diesen Grow Sets und Two-Phase Sets. Ist es denn so, wenn ich sowas in meiner Anwendung verwenden möchte, ich das dann von klein auf implementieren muss oder gibt es schon vorgefertigte Lösungen, die ich verwenden kann?

Lars:

Die Grow Sets und die Two-Phase Sets wären jetzt noch relativ einfach zu implementieren. So ein Grow Set kann man mehr oder weniger schnell zusammen stricken, wenn man sich einfach ein Java-Set zum Beispiel nimmt, ein Go- oder ein Haskell-Set, was man hat und dann immer die Vereinigung davon berechnet. Die Collection Klassen haben alle so Union Operationen. Und so ein Two-Phase Set, das wäre dann letztendlich implementiert, wo man an jedes Element noch ein Flag anschreibt, ist es drinnen oder draußen? Es wäre also etwas, was man noch relativ einfach implementieren kann. Lucas und ich, wir waren mal vor einem Jahr in einem Projekt zusammen, da haben wir so was gebaut für Semantic Web. Ja, das gibt es noch. Manche Leute machen das noch. Und da haben wir auch einen CRDT für RDF People zusammen gestrickt. Das war jetzt kein riesiger Act sowas zu machen, aber es gibt für sowas auch Bibliotheken. Wenn man im Frontend Bereich unterwegs ist, muss man sich sowieso mit JavaScript auseinandersetzen, ob man will oder nicht. Und gerade für JavaScript gibt es eine sehr populäre Bibliothek, die nennt sich Auto-Merge und das kann aber noch eine ganze Reihe von anderen Datentypen, auf die wir vielleicht auch noch mal kurz eingehen sollten. Aber grundsätzlich gibt es da schon Mittel, dass man das nicht immer neu erfinden muss. Aber man muss dann auch schauen, ob dieses Auto-Merge auch fachlich das abdeckt, was man eigentlich möchte. Das hat Lucas auch schon mehrmals gesagt. Das implementiert so ein Standard Verhalten für das Mergeing von Instanzen, von den Datentypen. Und es kann in Einzelfällen auch sein, dass diese Standardverhalten eben nicht das gewünschte Verhalten ist. Und dann muss man noch mal Hand anlegen und muss es dann selbst machen. Aber es ist eigentlich auch keine Raketenwissenschaft. Es kann sein, dass man sich mal zusammensetzen muss und das ein bisschen durchdekliniert. Was gibt es Dinge zu Fälle, wer hat hier was entfernt? Wer hat da was, keine Ahnung. Kann auch sein, dass dann mal bei was rauskommt, was nicht ganz ein CRDT ist oder zumindest nicht der mathematischen Definition entspricht. Das können wir uns vielleicht nachher auch mal anschauen, was das genau bedeutet. Aber das ist auch nicht schlimm, solange man sich Gedanken gemacht hat, was passieren soll in diesem Synchronisierungsfall, das ist glaube ich schon mal die halbe Miete.

Lucas:

Ja, aber da muss man auf jeden Fall noch mal ganz klar darauf schauen, an welchen Orten möchte ich auf diese Datenschreiben zugreifen? Ich brauche, wenn ich so eine Library habe, muss ich natürlich schauen, kriege ich die auch auf dem Server zum Laufen, wenn ich zum Beispiel auch serverseitig noch Sachen reinschreiben möchte? Oder brauche ich die vielleicht nur in JavaScript? Dann reicht vielleicht auch eine JavaScript Library. Oder möchte ich vielleicht sogar, dass die Datenbank das mit versteht? Und da müssen wir uns dann auf jeden Fall die Lösung nochmal anschauen, ob das zu dem passt, was wir brauchen. Auto-Merge ist eine Library, die Lars und ich beide sehr gerne mögen. Die ist auch schön einfach zu benutzen und von vertrauenswürdigen Forschern mitentwickelt worden, deswegen auf jeden Fall empfehlenswert als Startpunkt. Da muss man aber auch ganz klar sagen: Wenn man jetzt bei Auto-Merge sagt: Bitte speichere mal dieses aktuelle Datum ab, dann ist es so eine Binär-Suppe, die man irgendwo hinlegen muss. Und wenn man sich jetzt überlegt, ich möchte die in meine Datenbank legen, dann bedeutet das erst mal, dass wenn ich die so wie sie ist in die Datenbank lege, kann die Datenbank darauf keine Queries oder so durchführen. Das muss ich immer im Hinterkopf behalten, wenn ich ein Format habe, was von der Datenbank nicht interpretiert werden kann, bedeutet das erst mal, dass das nicht von geindext oder durchsucht werden kann. Und das ist manchmal schon ein No-Go. Wenn wir uns überlegen, wir wollen vielleicht irgendwelche großen Suchen über mehrere Dokumente machen können. Und wir können die Dokumente nicht mehr lesen auf dem Server, ohne sie vielleicht alle aus der Datenbank zu holen, in einem JavaScript Dodge S Prozess zu holen und dann da zu durchsuchen, kann das schon ein Problem sein. Das müssen wir im Hinterkopf behalten. Es gibt die Datenbank Riak, eine Open Source Datenbank, die sehr früh mit CRDTs geforscht hat und auch schon viel damit gemacht haben. Das war vor sieben oder acht Jahren, da haben die die eingeführt, auch in die Datenbank, sodass man da solche ganze Sachen als Datentypen der Datenbank hatten und das hatte den großen Vorteil, dass man dann immer noch weitere Operationen darauf ausführen konnte auf der Datenbank. Dafür war es aber so, dass diese Datentypen nicht in JavaScript funktioniert haben. Das heißt, da konnte man nicht ohne Weiteres eine Offline Fähigkeit daraus bauen. Und das sollte man sich einfach noch mal anschauen. Je nachdem, welche Lösung ich jetzt gefunden habe, erfüllt sie da die ganzen Use Cases, die ich habe und gerade noch mal schauen: Kann ich sowohl aus JavaScript als auch aus der Datenbank darauf zugreifen? Sonst muss ich mir vielleicht Lösungen suchen. Vielleicht muss ich die Sachen in der Datenbank noch mal lesbar ablegen, dass die Datenbank darauf zugreifen kann. Wenn ihr das Produkt irgendwo einsetzen wollt, dann schaut euch das auf jeden Fall noch mal vorher an, denkt das noch mal durch. Was bedeutet das jetzt für solche Suchen? Und dann müsst ihr auf jeden Fall auch schauen, dass ihr da das hinbekommt, dass ihr das Vacuuming, das Staubsaugen, als Strategie etabliert bekommt, weil sonst wächst eure Datenbank immer weiter an mit diesen riesen Datenwulsten und dann habt ihr irgendwann auch ein Problem.

Lisa:

Jetzt hatten wir angefangen und haben über diese Einkaufsliste gesprochen. Was ist denn jetzt aber, wenn ich jetzt eine ToDo-Liste für unsere nächste Party machen möchte? Und das ist total relevant, dass die Dinge, die da eingefügt werden, in der richtigen Reihenfolge sind, weil ihr habt vorhin ganz oft explizit gesagt, dass wir jetzt über unsortierte Dinge reden. Aber es gibt auch in der Realität sortierte Dinge, die man irgendwie synchronisieren möchte. Was macht man dann?

Lars:

Dann können wir vielleicht an der Stelle erwähnen, dass dieses Auto-Merge ganz einfach JSON unterstützt als Datentyp. Ich kann den Auto-Merge praktisch beliebige JSON Dokumente mit zusammenklöppeln und kann dann auch sagen: Ich habe jetzt hier einen JSON Array und die Arrays sind sortiert in JavaScript. Also nicht sortiert, aber sie sind in einer bestimmten Reihenfolge. Und ich kann dann auch sagen, im Auto-Merge: Füge mir mal bitte dieses Ding jetzt hier hinten an und dann wird es hinten angefügt und nicht irgendwie an irgendeiner Stelle, wo es ihm gerade passt. Oder ich kann auch in einem Objekt irgendeinen Schlüssel schreiben, irgendeinen Schlüssel lesen, Schlüssel löschen und so weiter. Das geht alles und man kann sich das von der Ergonomie ein bisschen vorstellen, wie Git. Man hat dann ein Dokument und dann ruft man auf diesem Dokument eine Change Operation auf, das kann auch eine Commit Message angeben. Das wird von Auto-Merge auch mit unterstützt, dass man sich das quasi in der Historien Ansicht auch nochmal anschauen kann, was jetzt da geändert worden ist. Und man kann dann auch mehrere Änderungen gleichzeitig machen, wenn die irgendwie atomar sind oder so und dann wird beim Mergeing dann drauf Wert gelegt, dass die Reihenfolge beibehalten bleibt. Und das hinten anfügen ist jetzt mal ein schönes Beispiel, weil dann kann ich schon sagen, dass wir da auch Konflikte provozieren können. Zum Beispiel gehen wir davon aus, dass Lucas hinten was anfügt und Lisa auch was hinten anfügt. Dann ist jetzt nicht klar, wer von beiden jetzt gewinnt, an der Stelle. Also wer ist jetzt das vorletzte und das letzte Element? Und wie Auto-Merge das auflöst, ist dass jede Instanz eine Unique ID bekommt. Das ist einfach eine New U-ID, der generiert wird pro Instanz und ich glaube, es ist dann einfach so gelöst, dass die niedrigste oder die höchste, die gewinnt dann einfach. Es gibt dann da eine bestimmte Ordnung, die dann auf den Instanzen auch festgelegt wird, auf den verschiedenen Kopien. Und dadurch ist es dann aber immer deterministisch. Das heißt, egal ob das Merge vom Lucas gemacht wird oder ob das Merge von Lisa gemacht wird, es kommt immer das gleiche heraus. Es ist nicht so, dass Lucas sagt: Ich gewinne und Lisa sagt: Nein, aber ich gewinne. Es ist wirklich dann immer die deterministische Reihenfolge. Und das ist eine Garantie, die von Auto-Merge gegeben wird, dass mit ihren mathematischen Konzepten, die dahinter stehen, immer so eine deterministische kommutative Mergeing Operation möglich ist.

Lucas:

Und das hat auch noch einen sehr angenehmen Effekt. Das wird man dann wertschätzen, wenn man das erste Mal eine Offline Anwendung versucht hat zu bauen, dass, wenn ich dieselbe Operation nochmal rein-merge, das von Auto-Merge erkannt wird. Ah, diese Information habe ich schon und solange geht nichts kaputt. Netzwerke sind nicht verlässlich und manche Nachrichten werden vielleicht auch zweimal zugestellt und ich kriege von Lars zweimal die Nachricht: Bitte füge doch mal den Champagner hinzu. Das ist aber zweimal der gleiche Champagner, dann wird Auto-Merge das erkennen und sagen: Ah, okay, den habe ich schon hinzugefügt, dann steht jetzt hier ein Champagner. Das ist auch eine ganz wichtige Eigenschaft und ist auch etwas, was, wenn man nicht solche Konzepte verwendet, sehr schwer sicherzustellen ist. Man muss einfach dann schauen, dass das tatsächlich funktioniert, dass das nur einmal passiert. Und am Ende kommt dann auf allen Geräten, wenn alle Geräte, alle Nachrichten oder alle Change Sets bekommen haben, sind alle auf dem selben Stand. Und dann haben sie auch dieselbe Datenstruktur in derselben Reihenfolge. Das ist das Schöne. Auto-Merge bietet da alles an, was zu JSON gehört. Also Strings, Numbers, Arrays, Objects würde ich jetzt mal zusammengefasst sagen, das Wichtigste. Dann gibt es dann auch so was wie Push und ist intern da drin gebaut, dass Push halt bedeutet: Füge es als letztes an. Und das ist alles untendrunter abstrahiert. Das heißt, wenn ich weiß, wie man JSON verwendet und wie man die Datentypen, die da drin sind, mit den normalen Operationen, die in JavaScript zur Verfügung stehen, verwenden kann, dann weiß ich schon wie man Auto-Merge benutzt. Das ist das sehr attraktive daran. Aber das ist genau wie bei JSON, dass wenn ich mein eigenes Objekt erzeuge, mit einem anderen Prototypen, irgendwas besonderes und lege das da rein, dann funktioniert das nicht, dann verliert es seinen Prototypen. Also es sind wirklich nur diese ganz einfachen Datentypen, diese grundlegenden Datentypen. Aber das kennen wir auch schon, wenn wir versuchen eine React oder eine Angular Anwendung mit dem Server reden zu lassen, dann müssen wir auch JSON daraus machen. Da funktioniert das auch schon nicht. Es ist jetzt keine neue Einschränkung, würde ich sagen. Es ist das, was man sowieso kennt, wenn man im Frontend unterwegs ist, dass man das als Subset hat. Aber gleichzeitig ist das schon eine sehr komfortable Datenstruktur, wo man nicht über diese Details, wie jetzt Grow Sets und so weiter nachdenken muss und trotzdem echt einen schönen Baukasten von Operationen hat, die man da verwenden kann.

Lars:

Genau, da würde ich gleich an der Stelle noch mal kurz einhaken, weil das ist ein wichtiger Punkt, den man auch mal unterstreichen kann. Es ist jetzt nicht so, dass ich einfach mir eine beliebige Datenstruktur ausdenken kann und dann kann ich da irgendwie sagen: Ich tu ein Auto-Merge rein und zack, ist es ein CRDT und dann habe ich da die ganzen coolen Eigenschaften. CRDTs beschreibt diese Menge an Datentypen oder einen Bündel an Datentypen. Das sind teilweise sehr einfache Dinge, wie zum Beispiel diese Grow Sets. Und ich kann mir die auf bestimmte Art und Weise auch zusammen stöpseln, um dann auf kompliziertere Datenstrukturen oder ausdrucksstärkere Datenstrukturen zu kommen. Aber das ist auch Arbeit, die ich dann tun muss. Bei Auto-Merge hat man gesagt: Naja, diese JSON Dokumente, das passt auf, ich denke mir eine Zahl aus, 90% aller Anwendungsfälle. Das kannst du mit JSON Dokumenten sehr einfach ausdrücken und für die restlichen 10% musst du dann wirklich was tun. es ist jetzt nicht so, dass er dir wirklich komplett die Arbeit erspart. Dieses Silver Bullet ist es noch lange nicht. Aber dadurch, dass wir, ich sage mal in modernen Architekturen sehr viele APIs haben, die eh schon JSON sprechen, bietet sich das einfach an. Sie hätten genauso gut auch die Forscher hinter Auto-Merge hätten auch sagen können: Ja gut, lass mal XML jetzt machen als Datenstruktur, weil SOAP ist geil. Das hätten sie machen können, aber wäre heutzutage ein bisschen aus der Zeit gefallen. Es kann sein, dass in zehn Jahren dann sich herausstellt: JSON ist jetzt nicht mehr cool, wir machen jetzt YAML oder irgendwas ganz anderes. Dann müsste man diese Bibliothek nochmal anpassen, dass sie dann auch mit anderen Arten von Datenstrukturen arbeiten kann.

Lisa:

Jetzt hatten wir Grow Sets, 2-Phase-Sets und JSON schon als Beispiel für CRDT Datentypen. Habt ihr noch irgendwelche Beispiele, die super wichtig sind und die wir nennen sollten in der Folge?

Lars:

Ein wichtiges Beispiel für dich ist noch Text. Grundsätzlich können wir uns sowas vorstellen wie Google Docs oder wie auch immer das jetzt bei anderen Firmen heißt, wo wir kollaborativ an einem Text editieren wollen und besser sein wollen als Google Docs und auch offline fähig weiter editieren wollen. Dann gibt es Datentype , die tatsächlich dafür da sind, Text abzubilden als CRDT. Da kann man sich jetzt vorstellen, wir drei schreiben jetzt zusammen einen Artikel über CRDTs, dann schreibt einer die Einleitung, der andere die Mitte und die Lisa schreibt den Abschluss. Dann ist es so, dann wachsen diese drei Texte unabhängig voneinander weiter und das ist relativ einfach zu mergen. Aber was ist, wenn jetzt die Lisa vorne einen Rechtschreibfehler findet und den er editiert? Dann muss das auch wieder aufgelöst werden. Und dieser komplexe Fall, den kann man tatsächlich auch mit CRDTs lösen. Und das hat sich auch in der letzten Zeit weiter entwickelt, die Datenstrukturen, die wir da haben. Und von den Leuten, die hinter Auto-Merge stecken, gibt es einen neuen CRDT, der heißt Paripex, den werden wir auch in den Shownotes verlinken, der sogar dazu fähig ist, Rich Text, also mit Bold und Italics in CRDTs abzubilden. Das heißt, das Paripex kann mergen, dass du den Text, wo ich gerade den Rechtschreibfehler drin gefixt habe und du den Bold gemacht hast, kann es sogar diese Änderungen zusammenführen.

Lars:

Und Kommentare kann er auch.

Lucas:

Und Kommentare. Man kann damit tatsächlich Auto-Word schreiben. Das neue Word auf Basis von Auto-Merge und Paripex. Das ist tatsächlich sehr cool. Das ist auch noch relativ neu, das ist im November herausgekommen. Das heißt also, das kann man sich auf jeden Fall mal anschauen, wenn man so was machen möchte. Und wenn man sich das durchliest, dann juckt es einen schon so ein bisschen in den Fingern, vielleicht mal ein Texteditor selbst zu bauen. Das finde ich auf jeden Fall auch beeindruckende Datenstrukturen. Es wirkt immer erst mal einfach, aber umso länger man darüber nachdenkt, umso komplizierter wird das mit diesem Text editieren. Und da haben sich Leute, die tatsächlich Ahnung davon haben, sehr ausführlich mit beschäftigt und auch ausführlich beschrieben, wie es funktioniert. Es ist jetzt nicht einfach eine Implementierung und dann steht da drunter: Stimmt so, sondern es ist quasi ein ganzes wissenschaftliches Papier, wo drin erklärt ist, wie das funktioniert, was die Konzepte davon sind. Und wenn euch das interessiert, dann schaut euch das auf jeden Fall mal an. Genau, und wenn ihr so was bauen wollt, dann schaut euch auf jeden Fall Paripex an. Ich glaube, das ist aktuell eine sehr interessante Lösung für so ein Problem.

Lisa:

Gibt es neben Text noch ein weiterer Datentyp oder sind das dann die wichtigsten Datentypen, die man haben kann?

Lars:

Ja, es gibt noch ein paar andere Datentypen, die teilweise eher so ein Nischendasein haben, aber natürlich auch ganz wichtig sind. Zum Beispiel gibt es ein Register, die gibt es dann in verschiedenen Geschmacksrichtungen, zum Beispiel, in Last Write Wins Register, wie der Name schon sagt, wer dann zuletzt reinschreibt, dessen Wert gewinnt. Es gibt Multi-Value Register, da gibt es dann spezielle Techniken, um Konfigurierungen um Schreiboperationen zu erkennen und wenn es einen Konflikt gibt, wird einfach beides genommen, in das Register reingeschrieben. Und in der Hinsicht gibt es noch einige andere Sachen. Es gibt auch Register, die wiederholt durch Schreib- und Löschzyklen unterstützen. Da kann man dann zum Beispiel sagen, der Eintrag wurde dreimal hinzugefügt, aber nur zweimal gelöscht, also ist er dann jetzt praktisch da. Und da gibt es noch eine ganze Reihe von anderen Sachen, die jetzt standalone erst mal nicht besonders hilfreich erscheinen, aber wenn man sie dann mit den anderen Sachen kombiniert, dann wird dann ein Schuh draus. Ach ja, und den allereinfachsten haben wir ganz vergessen, nämlich den Counter. Der Counter ist ein extrem einfacher CRDT, weil ich drücke einfach auf +1 und dann werden einfach alle +1 und zusammengezählt. Das wäre der allereinfachste CRDT.

Lucas:

Und ich finde aber, obwohl er so einfach ist, das ist etwas, was an einigen Stellen schon schief geht. Wenn man sich überlegt, ihr habt jetzt irgendwie eine super große Webanwendung wie YouTube und wollt zählen, wie viele Likes so ein Video hat? Heißt das bei YouTube so? Daumen hochs. Ich weiß es nicht. Dann ist es erst mal so, es ist quasi zu jedem Zeitpunkt nicht so wichtig, dass jetzt die exakte Anzahl von Daumen hochs richtig gezählt ist aber es soll irgendwie am Ende konvergieren, zu derselben Zahl. Das heißt also, auch wenn dann zwischendurch die Daumen nicht bei allen gleich sind, irgendwann sollen sie die gleichen sein. Und die Lösungen in einigen Datenbanken, die sich sehr auf Uhren und Last Write Wins verlassen, wäre es dann jetzt so, dass irgendeine von den Datenbankknoten gewinnt und sagt: Ja, du hast fünf Likes, du sieben Likes, dann machen wir mal sieben draus, obwohl die richtige Antwort quasi die Summe aus beidem wäre oder so was. Und da kann einem so ein CRDT Datentyp für Counter tatsächlich helfen, fachlich die richtige Antwort raus zu bekommen. Die anderen Datentypen sind jetzt ein bisschen zu schwer zu erklären ohne Visualisierung. Aber bei so einem Counter kann man sich es gut vorstellen, dass man sich statt sich die Zahl konkret zu merken, merkt man sich quasi nur die Änderung, die durchgeführt wurde. Der eine Knoten merkt sich, ich habe drei dazubekommen und mein Ausgangspunkt war vier und der andere merkt: Ich habe fünf dazubekommen und mein Ausgangspunkt war vier. Dann berechnet mal vier plus fünf, plus drei, dann hat man das Ergebnis von beiden zusammen. Das kann man sich jetzt so grundsätzlich vorstellen, wie so ein Counter funktionieren könnte und dass das die bessere Lösung ist, als einfach zu sagen, der, der als letztes vor den beiden geschrieben hat, hat Recht gehabt. Das ist diese Last Write Wins Strategie, die in ganz wenigen Fällen richtig ist, aber eher weniger.

Lisa:

Jetzt haben wir ganz schön viele Datentypen, haben das grundlegende Prinzip hinter CRDTs geklärt. Aber man hat hier nicht umsonst Lars und Lucas zu Gast, wenn man nicht noch wenigstens ein bisschen versuchen wollen würde, die grundlegenden Konzepte zu erörtern. Wollt ihr das vielleicht mal versuchen? Was sind die grundlegenden, vielleicht mathematischen Konzepte, die hinter CRDTs stecken?

Lars:

Ah, danke schön. Ich dachte, du fragst gar nicht mehr, Lisa. Da kann ich jetzt mein Mathebuch wieder aufsetzen. die Grundidee, mathematisch gesehen sind die sogenannten Verbände, das ist eine mathematische Struktur. Verband klingt jetzt erst mal nach Krankenhaus oder so. Auf Englisch heißen die Dinger lattices. Und ein Verband ist letztendlich eine abstrakte Beschreibung einer Ordnungsrelation. Das heißt, ich kann also zwei Objekte miteinander vergleichen und kann sagen: Das Objekt ist kleiner als das andere. Bei Zahlen zum Beispiel wäre es einfach der Kleiner-Gleich-Operator, den wir kennen und bei den Sets wäre es zum Beispiel die Teilmengenrelation. Wir können zum Beispiel sagen, wenn jetzt die Einkaufsliste, sagen wir mal Äpfel und Birnen enthält, dann ist die kleiner als die Einkaufsliste, die Äpfel, Birnen und Müsli enthält. Dadurch können wir also eine Relation zwischen zwei Objekten herstellen. Der wichtige Punkt ist jetzt, dass diese Verbände nicht nur eine Ordnungsrelation sind, sondern sie sind auch eine Möglichkeit, um eine Vereinigung zu bilden von zwei verschiedenen Objekten. Und die Vereinigung hat die schöne Eigenschaft, dass sie immer größer ist als die einzelnen Teile, die in die Vereinigung eingeflossen sind. Bei den Mengen wäre es jetzt die ganz normale Mengenvereinigung. Bei Zahlen könnte es zum Beispiel die Maximumoperation sein zwischen zwei bestimmten Zahlen. Und das Schöne an diesen Verbänden ist, dass sie festlegen, dass diese Vereinigungsoperationen immer kommutativ sein muss. Das heißt, ich kann sie auslosen, in welcher Reihenfolge ich sie auslose ist eigentlich egal. Sie muss auch assoziativ sein. Und jetzt kommt noch der Clou, idempotent muss sie auch noch sein. Das heißt, wenn ich ein Objekt mit sich selbst vereinige, kommt nur das Objekt raus. Und diese drei Eigenschaften, Kommutativität, Assoziativität und Idempotenz führen zu diesen coolen Eigenschaften, die wir jetzt in den letzten 40 Minuten schon lang und breit diskutiert haben. Dazu kann man das dann benutzen und man kann das auch formal beweisen. Viele von diesen CRDTs, die wir diskutiert haben, da existieren formal stringente Beweise, dass tatsächlich genau diese Eigenschaften auch erfüllt sind. Und jetzt ist es so, dass sich aus jedem von diesen Verbänden eigentlich nur ein CRDT konstruieren kann und umgekehrt, wenn ich einen neuen CRDT konstruieren will, muss ich mir erstmal überlegen, was ist jetzt eigentlich der Verband der darunter ist?

Lisa:

Nicht schlecht. Verbände. Habt ihr noch irgendein Konzept, was ihr im Rahmen von CRDTs erläutern möchtet? Oder war es das jetzt?

Lucas:

Grundsätzlich wollen wir das noch mal erwähnen, die Vector Clocks. Wir haben sie schon mal kurz erwähnt. Aber grundsätzlich gibt es ein Problem damit, wenn man versucht Uhren zu verwenden in verteilten Systemen. Es gibt zwei Probleme. Das eine Problem ist, dass die Uhren auf verschiedenen Geräten nicht synchron sind, auch wenn das heute immer besser wird, im Gegensatz zu früher, da war das noch häufiger der Fall. Aber auch heute ist es immer noch ein Problem mit Uhren, die synchron zu halten zwischen verschiedenen Systemen. Das geht noch einigermaßen, wenn sie im selben Rechenzentrum sind. Da haben wir dann auch immer relativ viel Kontrolle drüber, aber sobald wir über so was reden wie jetzt 5000 Telefone, die auf der Welt verteilt sind, irgendwann endet das mit dem Synchronsein. Das ist das eine Problem, aber das viel größere Problem und das lässt sich auch durch keine Technologie der Welt lösen, ist dass eine Uhr keine Kausalität kennt. Das heißt also, eine Uhr weiß nicht, welchen Stand etwas vorher hatte. Von welchem Stand gehen wir aus? Vector Clock kann das einem beantworten. Wenn wir jetzt eine Vector Clock haben für uns drei, die auf den selben Sachen herum arbeiten, dann weiß die Vector Clock, welchen gemeinsamen Stand wir kennen. Das heißt also, die hat quasi für jeden von uns einen eigenen Zähler und weiß: Ah okay, die Lisa kennt Stand 2 von Lucas, Stand 5 von Lars und meinen eigenen Stand 2. Und dann kann sie damit immer wissen, wann wir Informationen haben, die die anderen Personen nicht haben. Und ich persönlich würde es jetzt so sagen, dass Vektor Clock quasi einem sagen kann, wann er einen Konflikt hatte und CDTs können einem dabei helfen, diese Konflikte zu lösen. Das heißt, in solchen Libraries wie Auto-Merge sind dann sowohl CRDTs drin als auch Vektor Clocks und die helfen einem dann dabei, diese Konflikte zu entdecken und dann zu lösen. Und Vector Clocks sind auch eine, ich weiß nicht, ich glaube die sind von 1970, ich bin mir gar nicht mehr sicher, gibt es auf jeden Fall schon eine ganze Weile und die sind auch in jeder Menge Datenbanken eingebaut. Das ist so Standard Ding. Aber leider ist es immer noch so, dass einige Systeme sich auf die Uhrzeit verlassen. Und das hat immer das Problem, dass man dann diese Last Write Wins Lösungsstrategie fahren muss, weil man nicht die Kausalität kennt der Änderungen.

Lars:

Genau. Und jetzt kann ich auch noch mal einen Mathe Fact, Fun Fact rein ballern. Vector Clocks sind auch ein Beispiel für einen Verband. Auch Vector Clocks unterstützen diese Sortierung und auch die Vereinigung von Operationen und dass es praktisch die mathematische Fundierung und ich würde jetzt mal behaupten, dass wenn wir sagen, dass die Vector Clocks schon uralt sind. Dann würde ich mal sagen, die Verbände sind also noch viel urälte. Die sind schon sehr lange bekannt in dem Gebiet der Algebra.

Lisa:

Wer demnächst irgendwo prahlen möchte, sagt, dass eine Vector Clock ein mathematischer Verband ist. Ich versuche mir das zu merken, damit ich mit diesem Wissen irgendwo glänzen kann. Das war auf jeden Fall super spannend. Ich würde jetzt noch mal fragen: Habt ihr irgendwelche Tipps an die Zuhörerinnen zum Thema CRDT. Sowas wie: Jetzt auf jeden Fall machen oder lest mal XYZ oder sowas in der Richtung?

Lucas:

Mein Tipp wäre erst mal, wenn ihr euch mit JavaScript Anwendungen beschäftigt, es ist auch eigentlich egal ob das jetzt Server Seite oder Client Seite ist. Bei beiden funktioniert es, schaut euch auf jeden Fall mal Auto-Merge an und ich glaube, wenn man das mal verwendet hat einfach lokal, dann muss man jetzt noch nicht mal unbedingt mit Netzwerk anfangen oder so, beginnt man schon mal zu verstehen, was das Prinzip dahinter ist. Gerade das, was man jetzt auf der Audiospur bisschen schwer erklären kann, kann man dann einfach sich selbst klar machen: Ah, das ist cool. Dann hat man das im Hinterkopf, wenn man mal in ein Problem rein läuft, was sich dem irgendwie anbietet. Die Leute, die das gemacht haben, haben auch noch Hypermerge geschrieben. Das ist tatsächlich für Peer to Peer Anwendungen. Da braucht man dann noch nicht mal einen Server für, da kann die Anwendung direkt miteinander kommunizieren und da ist natürlich so was wie Auto-Merge auch Gold wert, wenn man P2P Anwendungen bauen möchte.

Lisa:

Hast du auch noch einen Tip, Lars?

Lars:

Ja, ich könnte jetzt noch ganz schamlos auf meine Blogpost Serie verweisen, die eine interaktive Einführung in die CRDTs bieten. Und das ist so gebaut, dass man im Browser, dass man da so Code Boxen hat, wo man mit den Konzepten herumspielen kann und mit einer Erklärung davor. Dann gibt es da Aufgaben, die man dann lösen soll. Und da kann man dann eben von Anfang an. Ich fange da an, erkläre das mit diesen Verbänden und dann die verschiedenen Eigenschaften, die es dann da gibt und baue dann die Grow Sets und so weiter zusammen. Und man kann sich das dann an JavaScript Code Beispielen dann selbst zusammenreimen, wie das funktioniert.

Lisa:

Sehr cool. Genau, ich glaube, dann sind wir auch am Ende unserer Folge angelangt. Ich fand es sehr spannend mit euch beiden und möchte direkt eine Werbung einstreuen. Ihr beiden habt nämlich auch einen Vortrag über das ganze Thema “Hilfe, wir sünden”. Wer beim Technology Day war, hat ihn vielleicht schon gesehen. Wer nicht die Chance hat, ihn dort zu sehen, zum Beispiel nächsten Monat bei der OOP wird er zu hören, zu sehen sein, dann auch mit Folien, was die Verbände deutlich einfacher machen wird, vermutlich. Vielen, vielen Dank, dass ihr beiden da wart. Vielen Dank an die Zuhörerinnen da draußen, dass ihr zugehört habt, auch trotz des mathematischen Inputs heute oder gerade deswegen. Man weiß es nicht. Bei der nächsten Folge wird es dann ganz besonders. Heute hatten wir die 99, die Schnapszahl Folge. Nächste Folge gibt es die Folge 100 und die wurde live beim INNOQ Technology Day am 1.12. 2021 aufgezeichnet und wird deswegen bestimmt unglaublich spannend sein. Wir freuen uns, dass ihr sie wieder anhören werdet. Bis dahin. Tschüss.