NoSQL – Lamport Timestamps
Aktuell beschäftige ich mich mit der Problemlösung für ein Browsergame. Dieses soll kostengünstig betrieben werden können - auf einem Tomcat! Da die meisten (Cloud-)Provider vorallem Tomcat anbieten habe ich den anfänglichen Plan, einen V-Server mit einem vollwertigen Application-Server zu verwenden, verworfen.
Da CDI sehr mächtig ist und auch mit einem Tomcat nutzbar ist und als Programmiermodell in der näheren Zukunft im Bereich Java aus meiner Sicht immer mehr Anklang finden wird, ist es eine gute Übung für den beruflichen Alltag. Jede Bean kann über Dependency Injection ganz elegant von außen in eine andere Bean eingepflanzt und dort benutzt werden.
Dann bin ich auf die Problematik von Transaktionen gestoßen. Mein erster, schlichter Ansatz war, dass ich mir einen EntityManager mit Hilfe von Seam Persistence oder MyFaces CODI injecten lasse und über @Transactional dafür sorge, dass Transaktionen für Methoden zur Verfügung stehen. Ich wollte also mit JPA arbeiten. Da dies nicht so funktionierte, wie ich es mir vorstellte, habe ich die Versuche, es zum Laufen zu bringen, abgebrochen.
Aktuell suche ich mein Heil im Bereich NoSQL-Datenbanken. Einfach ein Objekt an die Datenbank übergeben und es persistiert - damit ist es nicht getan. Bei aufwändigeren Applikationen als einem reinen Archiv sollen die Daten auch verändert werden können. Und genau dort liegt der Grund für diesen Blog-Eintrag. Beim Informationen-Sammeln habe ich das Buch NoSQL - Einstieg in die Welt nichtrelationaler Web-2.0-Datenbanken von Stefan Edlich, Achim Friedland, Jens Hampe, Benjamin Brauer entdeckt. Ich bin noch nicht durch, allerdings war das Kapitel 2.5 Vector Clocks besonders interessant für mich. Dort wird nämlich die Lamport-Uhr erklärt, die mich auf folgende Idee brachte:
In einem Browsergame ist die Konsistenz relativ unwichtig. Natürlich sollten die Daten zu einem Zeitpunkt konsistent sein, wann dieser Zeitpunkt ist, bleibt dabei aber unerheblich. Bei meinem Browsergame soll es vorwiegend darum gehen, Ressourcen zu sammeln, um eine Siedlung auszubauen und dadurch eine Armee erzeugen zu können, mit der man andere Siedlungen von anderen Spielern angreifen kann.
Abstrakt gesehen geschieht also in der Regel folgendes: Es wird eine Entität erzeugt an der viele Informationen hängen. Es können Informationen hinzukommen (neue Armee), aber auch gelöscht werden (Armee wird besiegt, da alle Soldaten tot). Da davon auszugehen ist, dass nicht nur ein Spieler spielt, werden mehrere Entitäten dieser Art erzeugt. Für diese Entitäten werden regelmäßig Aktualisierungen bestimmter Felder vorgenommen. Diese Felder sind in der Regel Zahlen. Mit Zahlen können diverse Berechnungen vorgenommen werden.
Und hier kommt nun die Lamport-Uhr ins Spiel: Kurz gesprochen geht es um das "Zuweisen von eindeutigen Zeitstempeln an Nachrichten" (Wikipedia). Die Lamport-Uhren erlauben allerdings nicht das Erkennen von Nebenläufigkeit. Dazu wurden die Vektorenuhren entwickelt.
Nach meinem aktuellen Wissensstand (der noch sehr gering ist) zum Thema NoSQL-Datenbanken, werden Entitäten in NoSQL-Datenbanken meist mit einem Timestamp oder einer Revisionsnummer versehen, sodass man eine Art Reihenfolge von Änderungen der Entitäten erhält. Dies geht mir persönlich nicht weit genug.
Funktionale Programmiersprachen machen es möglich, auf große Datenmengen Funktionen ausführen zu lassen - und zwar parallel! Ich möchte ungern eine Entität aus der Datenbank laden, um einen Wert zu ändern und anschließend die ganze Entität aktualisieren. Stattdessen möchte ich der Datenbank sagen können, welches Feld für welche Entität mit welcher Funktion sie aktualisieren soll. Die Datenbank nimmt diese 3 Informationen als Einheit ("Nachricht") an und versieht sie mit einem Timestamp. Dabei ist es erstmal egal, wann diese Nachricht anschließend von der Datenbank verarbeitet wird, wichtig ist nur, dass sie verarbeitet wird! Die Reihenfolge der Verarbeitung mehrere Nachrichten wird durch den Timestamp festgelegt.
Dadurch, dass die Datenbank die Operationen verwaltet und keine Deltas ermitteln muss, lassen sich solche Operationen auch rückgängig machen, was sinnvoll für ein Browsergame ist. So könnte durch den Zugriff auf eine inkonsistente Replikation eine Operation ermöglicht werden, die auf einer konsistenten Replikation nicht möglich gewesen wäre. Bei großen Datenmengen kann das rückgängig machen einer Operation nicht manuell, sondern muss vollautomatisch geschehen. Da man allerdings nicht jede Operation rückgängig machen möchte, weil eine andere Operation Vorrang hat, müsste eine Nachricht neben dem Timestamp auch eine Priorität erhalten. So kann die Liste der Nachrichten nach zurückzurollenden Operationen durchsucht werden. Wenn bei der Synchronisierung aller Replikationen Fehler erkannt werden, können diese mit Hilfe des Timestamps und der Priorität ermitteln, welche Operationen zurückgerollt (aus der Liste gelöscht oder Umkehrung der Original-Operation) werden müssen und welche tatsächlich ausgeführt werden sollen.
Problematisch bleibt bei dieser Idee, dass es sehr viele Inkonsistenzen zwischen den einzelnen Replikationen geben könnte und dadurch viele Nachrichten zurückgerollt werden müssen. <p>Außerdem stellt sich mir die Frage, ob solche Funktionalität von einer Datenbank angeboten werden sollte oder über die Applikation selbst (z.B. durch die Nutzung eines Frameworks) implementiert werden muss?