Um die Probleme zu l\u00f6sen, die sich zur Erf\u00fcllung der genannten Eigenschaften ergeben, gibt es unterschiedliche Ans\u00e4tze. Ein Ansatz ist Determinismus. Was das genau hei\u00dft und wie es genau funktioniert wollen wir an dem System \u201eSLOG\u201c genauer betrachten. SLOG ist laut dem Paper von Run et al. \u201eSLOG: Serializable, Low-Latency, Geo-Replicated Transactions\u201c der erste Systementwurf, welcher alle drei genannten Eigenschaften erf\u00fcllt.<\/p>\n\n\n\n
Nachdem im Folgenden die Probleme georeplizierter Datenbanken noch einmal genauer betrachtet werden, wird der Begriff Determinismus vor allem im Kontext von modernen Datenbanksystemen gekl\u00e4rt und das Prinzip wird anhand des Systems SLOG noch einmal genauer erl\u00e4utert.<\/p>\n\n\n\n
Was ist das Problem?<\/strong><\/h2>\n\n\n\nDie Probleme, die uns in replizierten Datenbanken begegnen, erschlie\u00dfen sich bereits aus der vorangegangenen Erkl\u00e4rung der drei Eigenschaften moderner Anwendungen. Im Folgenden wird das Ganze noch einmal Schritt f\u00fcr Schritt genauer betrachten und es wird klar, warum es zu diesen Problemen kommt.<\/p>\n\n\n\n
Single-Node-Datenbanken \u2013 Datenbanken, die f\u00fcr eine einzige Maschine konzipiert wurden \u2013 funktionieren sehr gut. Wenn Kunde 2 den Artikel 3 kaufen m\u00f6chte, werden diese zwei Items gelocked und erst dann sind die \u00c4nderungen m\u00f6glich (vgl. Abbildung 1). In einem einfachen Datenbanksystem ist die Serialisierbarkeit also ohne gro\u00dfes Zutun garantiert und \u00fcber die anderen zwei Eigenschaften muss sich gar nicht gek\u00fcmmert werden, da diese in diesem Kontext noch gar nicht wirklich relevant sind.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/SingleNode-1024x246.jpg\")
<\/a>Abbildung 1: Single-Node-DB <\/em><\/figcaption><\/figure>\n\n\n\nBei Multi-Node-Datenbanken wird das ganze schon etwas schwieriger und es braucht ein bisschen mehr Anstrengung. Man spricht hierbei auch von einem Scalability Problem. Die Kunden und die Artikel sind nicht mehr wie im Single-Node-Beispiel auf einer Maschine, sondern auf vier Maschinen aufgeteilt. Jede Maschine nutzt nur den Code welcher relevant f\u00fcr ihn ist. Jedoch muss es irgendeine Kommunikation zwischen beiden Maschinen geben, die den Maschinen gegenseitig best\u00e4tig, dass jede Maschine das getan hat, was sie auch tun soll. Jede Maschine muss ihren Part der Transaktion eigenst\u00e4ndig durchf\u00fchren. Diese Kommunikationsproblem kann durch Locking oder auch durch eine Two-Phase-Commit-Protokoll gel\u00f6st werden (vgl. Abbildung 2). Hierbei ergibt sich jedoch aufgrund dieser Protokolle wieder ein neues Problem. Durch das gesamte Protokoll muss gelockt werden. Dies f\u00fchrt zu einer Reduzierung der Geschwindigkeit unserer Transaktionen, da die Zeitr\u00e4ume, \u00fcber die die Locks gehalten werden m\u00fcssen, lange sind.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/MultiNodeDB.gif\")
<\/a>Abbildung 2: Multi-Node-DB<\/em><\/figcaption><\/figure>\n\n\n\nWenn wir jetzt aber repliziere Datenbanken haben, also Kopien der Datenbank auf der ganzen Welt verteilt, m\u00fcssen solche Locks noch viel l\u00e4nger gehalten werden, was noch mehr Zeit ben\u00f6tigt. <\/p>\n\n\n\n
Durch das Nutzen von replizierten Datenbanken an verschiedenen Locations wird N\u00e4he zu den Nutzern erreicht und um dadurch die Verf\u00fcgbarkeit zu steigern. Hierbei wird eine Transaktion erst in der eigentlichen Location durchgef\u00fchrt und danach \u2013 genauer gesagt nach dem das Commit-Protokoll durchgef\u00fchrt wird \u2013 wird die die Datenbank synchron in allen Locations auf der ganzen Welt repliziert (vgl. Abbildung 3). Das Problem ist hier, wie bereits erw\u00e4hnt, dass die Locks sehr lange gehalten werden m\u00fcssen, bis die Replikation abgeschlossen ist.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/ReplicaDB.gif\")
<\/a>Abbildung 3: Georeplizierte DB<\/em><\/figcaption><\/figure>\n\n\n\nWar es bei den Multi-Node-Datenbanken noch so, dass die Latenz vom Commit-Protokoll das Problem war, ist es bei replizierten Datenbanken nun die Latenz unseres Replikationsprotokolls. Beide Protokolle verursachen Latenzen durch das Halten von Locks.<\/p>\n\n\n\n
Genau diese Herausforderung kann durch Determinismus gel\u00f6st werden. <\/p>\n\n\n\n
Was ist Determinismus im Kontext von Datenbanken?<\/strong><\/h2>\n\n\n\nDeterminismus gibt es in allen m\u00f6glichen Fachgebieten, wie z.B. der Linguistik, der Biologie oder auch der Theologie. Laut Wikipedia ist \u201eder Determinismus (von lateinisch determinare \u201afestlegen\u2018, \u201aGrenzen setzen\u2018, \u201abegrenzen\u2018) die Auffassung, dass alle \u2013 insbesondere auch zuk\u00fcnftige \u2013 Ereignisse durch Vorbedingungen eindeutig festgelegt sind.\u201c Diese Definition trifft es im Zusammenhang mit verteilten Datenbanksystemen eigentlich schon ganz gut. Denn das ist was versucht wird in deterministischen Systemen zu erreichen. Genauer gesagt, wenn zwei getrennte Kopien des Systems die gleiche Eingabe sehen, dann sind sie in der Lage diese Eingabe unabh\u00e4ngig voneinander zu verarbeiten und aufgrund des Determinismus garantiert die gleiche Ausgabe (den gleichen Endzustand) zu ergeben.<\/p>\n\n\n\n
Lange war die st\u00e4rkste Garantie in Datenbanksystemen die Serialisierbarkeit. Hierbei wird sichergestellt, dass der Endzustand des Datenbanksystems auch bei der gleichzeitigen Verarbeitung vieler Transaktionen, dem entspricht, als h\u00e4tte es alle Transaktionen seriell verarbeitet. Jedoch wird hierbei keine Garantie \u00fcbernommen, in welcher seriellen Reihenfolge die Transaktionen verarbeitetet werden. Bei deterministischen Systemen wird aber die \u00c4quivalenz einer seriellen Reihenfolge garantiert. Es gibt also eine Verarbeitung von Transaktionen in einer einzigen vorbestimmten seriellen Reihenfolge. Dadurch gibt es nur einen m\u00f6glichen Zustand, in dem sich das System befinden kann, trotz des Vorhandenseins von potenziell nicht-deterministischem Code in der Transaktionslogik.<\/p>\n\n\n\n
Um nur einen m\u00f6glichen Endzustand zu erreichen, m\u00fcssen moderne deterministische Datenbanksysteme bei einem Anfangszustand und einer definierten Eingabe in das System, die Eingaben vorverarbeiten.<\/p>\n\n\n\n
Normalerweise arbeiten verschiedene Kommunikations-Threads, die es in bestehenden nicht-deterministischen Datenbanksystemen gibt, unabh\u00e4ngig voneinander. F\u00fcr deterministische Datenbanksysteme ist diese Architektur nicht praktikabel, da Determinismus nur garantiert werden kann wenn es eine klare, allgemeine vereinbarte Eingabe gibt. Um diese Garantie aber zu erf\u00fcllen, muss eine Aufzeichnung der Eingabe erstellt werden, nach der sich das gesamte System richten kann. In einer Ein-Maschinen-Architektur zum Beispiel kann dies erreicht werden, in dem alle Transaktionen durch einen Thread geleitet werden, der die Eingabetransaktionen in der Reihenfolge aufzeichnet, in der er sie beobachtet.<\/p>\n\n\n\n
F\u00fcr die Erstellung eines solchen deterministischen Ausf\u00fchrungsplans f\u00fcr mehrere replizierte Datenbanksysteme im Vergleich zu herk\u00f6mmlichen nichtdeterministischen Systemen ist mehr Wissen \u00fcber die Transaktion erforderlich, bevor sie verarbeitet werden kann. Vor allem aber muss die gesamte Transaktion w\u00e4hrend des Planungsprozesses vorhanden sein. Au\u00dferdem erfordert die Vorausplanung in der Regel Kenntnisse dar\u00fcber, auf welche Daten eine Transaktion zugreifen wird. Dieses Wissen wird entweder statisch aus der Inspektion des Transaktionscodes abgeleitet, durch konservative Sch\u00e4tzungen vorgenommen oder es werden Teile der Transaktion spekulativ ausgef\u00fchrt. In georeplizierten, hochskalierbaren Systemen kann dies zum Beispiel durch ein Protokoll wie Paxos geschehen. Hierbei werden alle Transaktionen vor der Verarbeitung durch dieses Protokoll geleitet, um einen Konsensus \u00fcber das System hinweg zu erzielen. Dies hat jedoch den Nachteil, dass jede Transaktion die regions\u00fcbergreifende Latenzzeit f\u00fcr die Ausf\u00fchrung von Paxos \u00fcber die Regionen hinweg bezahlen muss.<\/p>\n\n\n\n
Jedes System sieht in einem deterministischen System durch ein Konsensus-Protokoll wie Paxos dieselbe Eingabetransaktion, und solange sie dieselbe Eingabe sehen, werden sie in denselben Endzustand gelangen. Die einzige Koordination, die in einem deterministischen Datenbanksystem noch stattfinden muss, ist die Kommunikation, die erforderlich ist, um sich \u00fcber die Eingabe in das System zu einigen. Jegliche andere Kommunikation wie zum Beispiel Locking oder Two-Phase-Commit-Protokolle werden dann nicht mehr ben\u00f6tigt und Determinismus verringert dadurch die Latenzzeit und verbessert den Durchsatz.<\/p>\n\n\n\n
Die einzige Latenz, die wir jetzt noch haben ist die des Konsensus-Protokolls. Dies kann mit dem System SLOG gel\u00f6st werden, welches noch diesen Schritt weiter geht und versucht die Latenz, verursacht durch das globale Konsensus-Protokoll, zu entfernen.<\/p>\n\n\n\n
Wie funktioniert SLOG?<\/strong><\/h2>\n\n\n\nSLOG ist nicht der einzige deterministische Ansatz. Jedoch ist SLOG der einzige Ansatz, welcher den globalen Konsensus eliminiert und dadurch alle drei Eigenschaften garantieren kann. Dieses System entfernt den globalen Paxos-Prozess, um die Latenzzeit zu verringern. Im Folgenden wollen wir SLOG oberfl\u00e4chlich betrachten und sehen wie SLOG diesen Schritt im Vergleich zu herk\u00f6mmlichen deterministischen Ans\u00e4tzen weitergeht.<\/p>\n\n\n\n
Wie schafft es SLOG nun dieses Konsensus-Protokoll abzuschaffen? SLOG verwendet eine Master-orientierte Architektur. Hierbei wird jedes Datenelement in einer sogenannten \u201eHome\u201c-Region oder Heimatregion verwaltet, was bedeutet, dass jeder Datensatz einen prim\u00e4ren Speicherort besitzt. S<\/em>chreib- und linearisierbare Lesevorg\u00e4nge eines Datenelements m\u00fcssen an seine Heimatregion gerichtet sein und am prim\u00e4ren Speicherort verarbeitet werden. Eine Region in SLOG ist eine Gruppe von Servern, die \u00fcber ein Netzwerk mit niedriger Latenz verbunden sind. Jede SLOG-Region enth\u00e4lt eine Reihe von Servern, auf die die in dieser Region gespeicherten Daten aufgeteilt (und repliziert) werden. Ein Teil dieser Daten wird von dieser Region beherrscht (sie ist die Heimatregion f\u00fcr diese Daten) und der Rest ist eine Kopie von Daten aus einer anderen Heimatregion. Jedes Datenelement hat also seine prim\u00e4re Location (Heimatregion), was so viel bedeutet wie Nutzer in Berlin haben ihre prim\u00e4re Location in Berlin, Nutzer in Sydney haben ihre prim\u00e4re Location in Sydney. Wenn ich als Berliner nun Daten aus Sydney lesen m\u00f6chte, muss ich die Daten auch aus der Region Sydney lesen, weil diese Up-to-date sind.<\/p>\n\n\n\nDie Transaktionen in SLOG werden basierend auf dieser Aufteilung in Heimatregionen in zwei Kategorien eingeteilt:<\/p>\n\n\n\n
\n- Single-Home: Die Daten, auf die zugegriffen werden soll, haben ihr Home-Replika in derselben Region<\/li>\n\n\n\n
- Multi-Home: Die Daten, auf die zugegriffen werden soll, haben ihr Home-Replika in unterschiedlichen Regionen<\/li>\n<\/ul>\n\n\n\n
Lese- und Schreibzugriffe auf nahe gelegene Daten erfolgen schnell und ohne regions\u00fcbergreifende Kommunikation. F\u00fcr Lese- und Schreibvorg\u00e4nge auf entfernte Daten sowie f\u00fcr Transaktionen, die auf Daten aus mehreren Regionen zugreifen, einer Multi-Home-Transaktion, fallen jedoch regions\u00fcbergreifende Kommunikationskosten an. Die Ausf\u00fchrung von Multi-Home-Transaktionen stellen auch das technisch schwierigste Problem bei der Entwicklung von SLOG dar. Das Ziel besteht darin, strenge Serialisierungsgarantien und einen hohen Durchsatz bei einer potenziell gro\u00dfen Anzahl von Multi-Home-Transaktionen aufrechtzuerhalten, auch wenn diese auf konkurrierende Daten zugreifen und eine Koordinierung \u00fcber physisch entfernte Regionen hinweg erfordern.<\/p>\n\n\n\n
Auch SLOG verwendet ein Koordinationsprotokoll, um denselben Endzustand zu erreichen und nutzt einen solchen deterministischen Ausf\u00fchrungsrahmen wie oben beschrieben, um Skalierbarkeits- und Durchsatzbeschr\u00e4nkungen zu \u00fcberwinden. Jedoch ersetzt SLOG das globale Protokoll durch ein regionales Protokoll. In SLOG wird der globale, auf Paxos-basierte, Log entfernt und durch ein lokales Log-Protokoll, welches ebenfalls auf Paxos basiert, ersetzt. Jede Region unterh\u00e4lt ein lokales Eingabeprotokoll, das \u00fcber Paxos auf ihren Servern implementiert wird. Dieses lokale Protokoll enth\u00e4lt nur Transaktionen, die voraussichtlich Daten ver\u00e4ndern, die in dieser Region verwaltet werden. Dieses Eingabeprotokoll wird in Batches an alle anderen Regionen gesendet. Jeder Batch ist mit einer Sequenznummer gekennzeichnet und die anderen Regionen verwenden diese Sequenznummer, um sicherzustellen, dass sie keine Chargen aus dieser Region \u00fcbersehen haben. Auf diese Weise ist jede Region schlie\u00dflich in der Lage das vollst\u00e4ndige lokale Protokoll von jeder anderen Region zu rekonstruieren<\/p>\n\n\n\n
Angenommen wir haben eine Transaktion, welche nur auf Datenelemente aus einer Region zugreift (Single-Home-Transaktion), sieht das ganze wie in der folgenden Abbildung 4 aus:<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/SingleHome.gif\")
<\/a>Abbildung 4: SLOG-Single-Home-Transaction<\/em><\/figcaption><\/figure>\n\n\n\nWenn nun eine Transaktion auf Datenelemente aus zwei verschieden Regionen auftritt (T3 und T5 in Abbildung 5), wird diese aufgeteilt. Man spricht dann von einer Multi-Home-Transaktion:<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/MultiHome.gif\")
<\/a>Abbildung 5: Multi-Home-Transaction<\/em><\/figcaption><\/figure>\n\n\n\nDas globale Paxos-Log, welches zuvor in anderen deterministischen Ans\u00e4tzen f\u00fcr Multi-regionale Datenbanken vorhanden war, weicht einer lokalen Version eines solchen Paxos-Protokolls pro Region, welches nur noch asynchron an die anderen Regionen repliziert wird (vgl. Abbildung 6).<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/LocalLogsSLOG.gif\")
<\/a>Abbildung 6: SLOGs lokale Protokolle<\/em><\/figcaption><\/figure>\n\n\n\nDie lokalen Protokolle werden in jede andere Region repliziert und sind unterschiedlich verschachtelt, was dazu f\u00fchrt, dass T3 zum Beispiel in jeder Region anders angeordnet ist (vgl. Abbildung 7), was aber nicht weiter problematisch ist, da die Daten disjunkt sind. <\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/LocalOrder-1024x576.jpg\")
<\/a>Abbildung 7: SLOGs lokale Transaktionsreihenfolge<\/em><\/figcaption><\/figure>\n\n\n\nDie Regionen weichen nicht voneinander ab, da<\/p>\n\n\n\n
\n- das globale Protokoll in jeder Region die urspr\u00fcngliche Reihenfolge der lokalen Protokolle, die es verschachtelt, beibeh\u00e4lt.<\/li>\n\n\n\n
- lokale Protokolle aus verschiedenen Regionen auf disjunkte Daten zugreifen.<\/li>\n\n\n\n
- die deterministische Verarbeitungsmaschine sicherstellt, dass die Transaktionen so verarbeitet werden, dass das Endergebnis dem Ergebnis der Verarbeitung in der seriellen Reihenfolge entspricht, die im globalen Protokoll der jeweiligen Region vorliegt.<\/li>\n<\/ol>\n\n\n\n
Single-Home-Transaktionen (T1, T2, T4) werden \u00fcbertragen, sobald sie in ihrer Prim\u00e4rregion abgeschlossen sind.<\/p>\n\n\n\n
Multi-Home-Transaktionen (T3, T5), die auf Daten in mehreren Regionen zugreifen, m\u00fcssen auf die asynchrone Replikation des Eingabeprotokolls warten, bevor sie die Transaktion festschreiben k\u00f6nnen (sie m\u00fcssen auf das Eintreffen des Protokolls warten). Die Transaktion wird verarbeitet, sobald die entsprechenden Protokolls\u00e4tze in jeder lokalen Region vorhanden sind.<\/p>\n\n\n\n
Durch die Aufteilung in Single-Home und Multi-Home wird realisiert, dass die meisten Transaktionen schnell sind (Single-Home). Auch wenn die Transaktionen in mehreren Regionen etwas langsamer sind, verschlechtern sich die Latenzen und der Durchsatz nicht so stark.<\/p>\n\n\n\n
Fazit<\/h2>\n\n\n\n
Determinismus verringert die Latenzzeit und verbessert den Durchsatz, in dem es die M\u00f6glichkeit lokaler Deadlocks ausschlie\u00dft und verteilte Commit-Protokolle wie z.B. Two-Phase-Commit reduziert, beziehungsweise g\u00e4nzlich eliminiert. Experimente haben gezeigt, dass der Durchsatz bei deterministischen Systemen im Vergleich zu nicht-deterministischen Systemen bei zunehmender Konkurrenz deutlich besser performt (vgl. Abbildung 8).<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/Throughput_Vergleich-1024x576.jpg\")
<\/a>Abbildung 8: Durchsatzvergleich deterministischer und nicht-deterministischer Systeme<\/em><\/figcaption><\/figure>\n\n\n\nHerk\u00f6mmliche deterministische Systeme haben zwar weiterhin mit Latenzen (bzgl. des Konsensus-Protokolls) zu k\u00e4mpfen, jedoch gibt es Systeme wie SLOG, die versprechen auch diese Latenz zu verringern oder sogar zu eliminieren, um alle drei in der Einleitung genannten Eigenschaften zu erf\u00fcllen. <\/p>\n\n\n\n
F\u00fcr Datenbankreplikationen ist der offensichtlichste Vorteil deterministischer Datenbanksysteme die Gew\u00e4hrleistung, dass, solange alle Replikate denselben Input erhalten, diese nicht voneinander abweichen. Weitere Vorteile in der deterministischen Architektur sind auf jeden Fall die Skalierbarkeit, die Modularit\u00e4t und die Gleichzeitigkeit. Nicht-deterministische Ausf\u00e4lle f\u00fchren in einem deterministischen System nicht zu einem Transaktionsabbruch, da die Datenbank ihren Zustand zum Zeitpunkt des Absturzes immer wiederherstellen kann, was diese Systeme auch robuster gegen Fehler macht.<\/p>\n\n\n\n
Auf den ersten Blick scheinen deterministische Architekturans\u00e4tze in verteilten Datenbanken die L\u00f6sung f\u00fcr viele bekannte Probleme, doch leider ist dieser Ansatz nicht f\u00fcr alle Datenbankanwendungen praktikabel. Da f\u00fcr den Planungsprozess die gesamte Transaktion vorhanden sein muss, sind deterministische Datenbanksysteme schlecht geeignet f\u00fcr ORM-Tools und andere Anwendungen, die Transaktionen nur in Teilen an die Datenbank \u00fcbermitteln.<\/p>\n\n\n\n
Deterministische Datenbanksysteme haben sich als vielversprechender Weg zur Verbesserung der Skalierbarkeit, Modularit\u00e4t, des Durchsatzes und der Replikation von transaktionalen Datenbanksystemen erwiesen. Leider bieten alle neueren Implementierungen nur begrenzte oder gar keine Unterst\u00fctzung f\u00fcr interaktive Transaktionen, so dass sie in vielen bestehenden Implementierungen bisher nicht eingesetzt werden k\u00f6nnen.<\/p>\n\n\n\n
Quellen<\/h2>\n\n\n\n
Abadi, Daniel J. \u201eSLOG: Serializable, Low-Latency, Geo-Replicated Transactions\u201c. Gehalten auf der CMU Database Group – Vaccination Database Tech Talks (2021), CARNEGIE MELLON UNIVERSITY, 1. Februar 2021. https:\/\/www.youtube.com\/watch?v=TAdiilOOvNI&t=645s<\/a>.<\/p>\n\n\n\n\u201eDeterminismus\u201c. In Wikipedia<\/em>, 25. Dezember 2021. https:\/\/de.wikipedia.org\/w\/index.php?title=Determinismus&oldid=218485694<\/a>.<\/p>\n\n\n\nFaleiro, Daniel J. Abadi, Jose M. \u201eAn Overview of Deterministic Database Systems\u201c. Zugegriffen 15. M\u00e4rz 2022. https:\/\/cacm.acm.org\/magazines\/2018\/9\/230601-an-overview-of-deterministic-database-systems\/fulltext<\/a>.<\/p>\n\n\n\nRen, Kun, Dennis Li, und Daniel J. Abadi. \u201eSLOG: Serializable, Low-Latency, Geo-Replicated Transactions\u201c. Proceedings of the VLDB Endowment<\/em> 12, Nr. 11 (Juli 2019): 1747\u201361. https:\/\/doi.org\/10.14778\/3342263.3342647<\/a>.<\/p>\n\n\n\n\u201eStrict Serializability\u201c. Zugegriffen 23. M\u00e4rz 2022. https:\/\/jepsen.io\/consistency\/models\/strict-serializable<\/a>.<\/p>\n\n\n\n\u201eTransaction throughput\u201c. Zugegriffen 23. M\u00e4rz 2022. https:\/\/docs.oracle.com\/cd\/E17276_01\/html\/programmer_reference\/transapp_throughput.html<\/a>.<\/p>\n\n\n\n
![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2022\/03\/SingleNode.jpg\")
<\/a>Bei Multi-Node-Datenbanken wird das ganze schon etwas schwieriger und es braucht ein bisschen mehr Anstrengung. Man spricht hierbei auch von einem Scalability Problem. Die Kunden und die Artikel sind nicht mehr wie im Single-Node-Beispiel auf einer Maschine, sondern auf vier Maschinen aufgeteilt. Jede Maschine nutzt nur den Code welcher relevant f\u00fcr ihn ist. Jedoch muss es irgendeine Kommunikation zwischen beiden Maschinen geben, die den Maschinen gegenseitig best\u00e4tig, dass jede Maschine das getan hat, was sie auch tun soll. Jede Maschine muss ihren Part der Transaktion eigenst\u00e4ndig durchf\u00fchren. Diese Kommunikationsproblem kann durch Locking oder auch durch eine Two-Phase-Commit-Protokoll gel\u00f6st werden (vgl. Abbildung 2). Hierbei ergibt sich jedoch aufgrund dieser Protokolle wieder ein neues Problem. Durch das gesamte Protokoll muss gelockt werden. Dies f\u00fchrt zu einer Reduzierung der Geschwindigkeit unserer Transaktionen, da die Zeitr\u00e4ume, \u00fcber die die Locks gehalten werden m\u00fcssen, lange sind.<\/p>\n\n\n\n Wenn wir jetzt aber repliziere Datenbanken haben, also Kopien der Datenbank auf der ganzen Welt verteilt, m\u00fcssen solche Locks noch viel l\u00e4nger gehalten werden, was noch mehr Zeit ben\u00f6tigt. <\/p>\n\n\n\n Durch das Nutzen von replizierten Datenbanken an verschiedenen Locations wird N\u00e4he zu den Nutzern erreicht und um dadurch die Verf\u00fcgbarkeit zu steigern. Hierbei wird eine Transaktion erst in der eigentlichen Location durchgef\u00fchrt und danach \u2013 genauer gesagt nach dem das Commit-Protokoll durchgef\u00fchrt wird \u2013 wird die die Datenbank synchron in allen Locations auf der ganzen Welt repliziert (vgl. Abbildung 3). Das Problem ist hier, wie bereits erw\u00e4hnt, dass die Locks sehr lange gehalten werden m\u00fcssen, bis die Replikation abgeschlossen ist.<\/p>\n\n\n\n War es bei den Multi-Node-Datenbanken noch so, dass die Latenz vom Commit-Protokoll das Problem war, ist es bei replizierten Datenbanken nun die Latenz unseres Replikationsprotokolls. Beide Protokolle verursachen Latenzen durch das Halten von Locks.<\/p>\n\n\n\n Genau diese Herausforderung kann durch Determinismus gel\u00f6st werden. <\/p>\n\n\n\n Determinismus gibt es in allen m\u00f6glichen Fachgebieten, wie z.B. der Linguistik, der Biologie oder auch der Theologie. Laut Wikipedia ist \u201eder Determinismus (von lateinisch determinare \u201afestlegen\u2018, \u201aGrenzen setzen\u2018, \u201abegrenzen\u2018) die Auffassung, dass alle \u2013 insbesondere auch zuk\u00fcnftige \u2013 Ereignisse durch Vorbedingungen eindeutig festgelegt sind.\u201c Diese Definition trifft es im Zusammenhang mit verteilten Datenbanksystemen eigentlich schon ganz gut. Denn das ist was versucht wird in deterministischen Systemen zu erreichen. Genauer gesagt, wenn zwei getrennte Kopien des Systems die gleiche Eingabe sehen, dann sind sie in der Lage diese Eingabe unabh\u00e4ngig voneinander zu verarbeiten und aufgrund des Determinismus garantiert die gleiche Ausgabe (den gleichen Endzustand) zu ergeben.<\/p>\n\n\n\n Lange war die st\u00e4rkste Garantie in Datenbanksystemen die Serialisierbarkeit. Hierbei wird sichergestellt, dass der Endzustand des Datenbanksystems auch bei der gleichzeitigen Verarbeitung vieler Transaktionen, dem entspricht, als h\u00e4tte es alle Transaktionen seriell verarbeitet. Jedoch wird hierbei keine Garantie \u00fcbernommen, in welcher seriellen Reihenfolge die Transaktionen verarbeitetet werden. Bei deterministischen Systemen wird aber die \u00c4quivalenz einer seriellen Reihenfolge garantiert. Es gibt also eine Verarbeitung von Transaktionen in einer einzigen vorbestimmten seriellen Reihenfolge. Dadurch gibt es nur einen m\u00f6glichen Zustand, in dem sich das System befinden kann, trotz des Vorhandenseins von potenziell nicht-deterministischem Code in der Transaktionslogik.<\/p>\n\n\n\n Um nur einen m\u00f6glichen Endzustand zu erreichen, m\u00fcssen moderne deterministische Datenbanksysteme bei einem Anfangszustand und einer definierten Eingabe in das System, die Eingaben vorverarbeiten.<\/p>\n\n\n\n Normalerweise arbeiten verschiedene Kommunikations-Threads, die es in bestehenden nicht-deterministischen Datenbanksystemen gibt, unabh\u00e4ngig voneinander. F\u00fcr deterministische Datenbanksysteme ist diese Architektur nicht praktikabel, da Determinismus nur garantiert werden kann wenn es eine klare, allgemeine vereinbarte Eingabe gibt. Um diese Garantie aber zu erf\u00fcllen, muss eine Aufzeichnung der Eingabe erstellt werden, nach der sich das gesamte System richten kann. In einer Ein-Maschinen-Architektur zum Beispiel kann dies erreicht werden, in dem alle Transaktionen durch einen Thread geleitet werden, der die Eingabetransaktionen in der Reihenfolge aufzeichnet, in der er sie beobachtet.<\/p>\n\n\n\n F\u00fcr die Erstellung eines solchen deterministischen Ausf\u00fchrungsplans f\u00fcr mehrere replizierte Datenbanksysteme im Vergleich zu herk\u00f6mmlichen nichtdeterministischen Systemen ist mehr Wissen \u00fcber die Transaktion erforderlich, bevor sie verarbeitet werden kann. Vor allem aber muss die gesamte Transaktion w\u00e4hrend des Planungsprozesses vorhanden sein. Au\u00dferdem erfordert die Vorausplanung in der Regel Kenntnisse dar\u00fcber, auf welche Daten eine Transaktion zugreifen wird. Dieses Wissen wird entweder statisch aus der Inspektion des Transaktionscodes abgeleitet, durch konservative Sch\u00e4tzungen vorgenommen oder es werden Teile der Transaktion spekulativ ausgef\u00fchrt. In georeplizierten, hochskalierbaren Systemen kann dies zum Beispiel durch ein Protokoll wie Paxos geschehen. Hierbei werden alle Transaktionen vor der Verarbeitung durch dieses Protokoll geleitet, um einen Konsensus \u00fcber das System hinweg zu erzielen. Dies hat jedoch den Nachteil, dass jede Transaktion die regions\u00fcbergreifende Latenzzeit f\u00fcr die Ausf\u00fchrung von Paxos \u00fcber die Regionen hinweg bezahlen muss.<\/p>\n\n\n\n Jedes System sieht in einem deterministischen System durch ein Konsensus-Protokoll wie Paxos dieselbe Eingabetransaktion, und solange sie dieselbe Eingabe sehen, werden sie in denselben Endzustand gelangen. Die einzige Koordination, die in einem deterministischen Datenbanksystem noch stattfinden muss, ist die Kommunikation, die erforderlich ist, um sich \u00fcber die Eingabe in das System zu einigen. Jegliche andere Kommunikation wie zum Beispiel Locking oder Two-Phase-Commit-Protokolle werden dann nicht mehr ben\u00f6tigt und Determinismus verringert dadurch die Latenzzeit und verbessert den Durchsatz.<\/p>\n\n\n\n Die einzige Latenz, die wir jetzt noch haben ist die des Konsensus-Protokolls. Dies kann mit dem System SLOG gel\u00f6st werden, welches noch diesen Schritt weiter geht und versucht die Latenz, verursacht durch das globale Konsensus-Protokoll, zu entfernen.<\/p>\n\n\n\n SLOG ist nicht der einzige deterministische Ansatz. Jedoch ist SLOG der einzige Ansatz, welcher den globalen Konsensus eliminiert und dadurch alle drei Eigenschaften garantieren kann. Dieses System entfernt den globalen Paxos-Prozess, um die Latenzzeit zu verringern. Im Folgenden wollen wir SLOG oberfl\u00e4chlich betrachten und sehen wie SLOG diesen Schritt im Vergleich zu herk\u00f6mmlichen deterministischen Ans\u00e4tzen weitergeht.<\/p>\n\n\n\n Wie schafft es SLOG nun dieses Konsensus-Protokoll abzuschaffen? SLOG verwendet eine Master-orientierte Architektur. Hierbei wird jedes Datenelement in einer sogenannten \u201eHome\u201c-Region oder Heimatregion verwaltet, was bedeutet, dass jeder Datensatz einen prim\u00e4ren Speicherort besitzt. S<\/em>chreib- und linearisierbare Lesevorg\u00e4nge eines Datenelements m\u00fcssen an seine Heimatregion gerichtet sein und am prim\u00e4ren Speicherort verarbeitet werden. Eine Region in SLOG ist eine Gruppe von Servern, die \u00fcber ein Netzwerk mit niedriger Latenz verbunden sind. Jede SLOG-Region enth\u00e4lt eine Reihe von Servern, auf die die in dieser Region gespeicherten Daten aufgeteilt (und repliziert) werden. Ein Teil dieser Daten wird von dieser Region beherrscht (sie ist die Heimatregion f\u00fcr diese Daten) und der Rest ist eine Kopie von Daten aus einer anderen Heimatregion. Jedes Datenelement hat also seine prim\u00e4re Location (Heimatregion), was so viel bedeutet wie Nutzer in Berlin haben ihre prim\u00e4re Location in Berlin, Nutzer in Sydney haben ihre prim\u00e4re Location in Sydney. Wenn ich als Berliner nun Daten aus Sydney lesen m\u00f6chte, muss ich die Daten auch aus der Region Sydney lesen, weil diese Up-to-date sind.<\/p>\n\n\n\n Die Transaktionen in SLOG werden basierend auf dieser Aufteilung in Heimatregionen in zwei Kategorien eingeteilt:<\/p>\n\n\n\n Lese- und Schreibzugriffe auf nahe gelegene Daten erfolgen schnell und ohne regions\u00fcbergreifende Kommunikation. F\u00fcr Lese- und Schreibvorg\u00e4nge auf entfernte Daten sowie f\u00fcr Transaktionen, die auf Daten aus mehreren Regionen zugreifen, einer Multi-Home-Transaktion, fallen jedoch regions\u00fcbergreifende Kommunikationskosten an. Die Ausf\u00fchrung von Multi-Home-Transaktionen stellen auch das technisch schwierigste Problem bei der Entwicklung von SLOG dar. Das Ziel besteht darin, strenge Serialisierungsgarantien und einen hohen Durchsatz bei einer potenziell gro\u00dfen Anzahl von Multi-Home-Transaktionen aufrechtzuerhalten, auch wenn diese auf konkurrierende Daten zugreifen und eine Koordinierung \u00fcber physisch entfernte Regionen hinweg erfordern.<\/p>\n\n\n\n Auch SLOG verwendet ein Koordinationsprotokoll, um denselben Endzustand zu erreichen und nutzt einen solchen deterministischen Ausf\u00fchrungsrahmen wie oben beschrieben, um Skalierbarkeits- und Durchsatzbeschr\u00e4nkungen zu \u00fcberwinden. Jedoch ersetzt SLOG das globale Protokoll durch ein regionales Protokoll. In SLOG wird der globale, auf Paxos-basierte, Log entfernt und durch ein lokales Log-Protokoll, welches ebenfalls auf Paxos basiert, ersetzt. Jede Region unterh\u00e4lt ein lokales Eingabeprotokoll, das \u00fcber Paxos auf ihren Servern implementiert wird. Dieses lokale Protokoll enth\u00e4lt nur Transaktionen, die voraussichtlich Daten ver\u00e4ndern, die in dieser Region verwaltet werden. Dieses Eingabeprotokoll wird in Batches an alle anderen Regionen gesendet. Jeder Batch ist mit einer Sequenznummer gekennzeichnet und die anderen Regionen verwenden diese Sequenznummer, um sicherzustellen, dass sie keine Chargen aus dieser Region \u00fcbersehen haben. Auf diese Weise ist jede Region schlie\u00dflich in der Lage das vollst\u00e4ndige lokale Protokoll von jeder anderen Region zu rekonstruieren<\/p>\n\n\n\n Angenommen wir haben eine Transaktion, welche nur auf Datenelemente aus einer Region zugreift (Single-Home-Transaktion), sieht das ganze wie in der folgenden Abbildung 4 aus:<\/p>\n\n\n\n Wenn nun eine Transaktion auf Datenelemente aus zwei verschieden Regionen auftritt (T3 und T5 in Abbildung 5), wird diese aufgeteilt. Man spricht dann von einer Multi-Home-Transaktion:<\/p>\n\n\n\n Das globale Paxos-Log, welches zuvor in anderen deterministischen Ans\u00e4tzen f\u00fcr Multi-regionale Datenbanken vorhanden war, weicht einer lokalen Version eines solchen Paxos-Protokolls pro Region, welches nur noch asynchron an die anderen Regionen repliziert wird (vgl. Abbildung 6).<\/p>\n\n\n\n Die lokalen Protokolle werden in jede andere Region repliziert und sind unterschiedlich verschachtelt, was dazu f\u00fchrt, dass T3 zum Beispiel in jeder Region anders angeordnet ist (vgl. Abbildung 7), was aber nicht weiter problematisch ist, da die Daten disjunkt sind. <\/p>\n\n\n\n Die Regionen weichen nicht voneinander ab, da<\/p>\n\n\n\n Single-Home-Transaktionen (T1, T2, T4) werden \u00fcbertragen, sobald sie in ihrer Prim\u00e4rregion abgeschlossen sind.<\/p>\n\n\n\n Multi-Home-Transaktionen (T3, T5), die auf Daten in mehreren Regionen zugreifen, m\u00fcssen auf die asynchrone Replikation des Eingabeprotokolls warten, bevor sie die Transaktion festschreiben k\u00f6nnen (sie m\u00fcssen auf das Eintreffen des Protokolls warten). Die Transaktion wird verarbeitet, sobald die entsprechenden Protokolls\u00e4tze in jeder lokalen Region vorhanden sind.<\/p>\n\n\n\n Durch die Aufteilung in Single-Home und Multi-Home wird realisiert, dass die meisten Transaktionen schnell sind (Single-Home). Auch wenn die Transaktionen in mehreren Regionen etwas langsamer sind, verschlechtern sich die Latenzen und der Durchsatz nicht so stark.<\/p>\n\n\n\n Determinismus verringert die Latenzzeit und verbessert den Durchsatz, in dem es die M\u00f6glichkeit lokaler Deadlocks ausschlie\u00dft und verteilte Commit-Protokolle wie z.B. Two-Phase-Commit reduziert, beziehungsweise g\u00e4nzlich eliminiert. Experimente haben gezeigt, dass der Durchsatz bei deterministischen Systemen im Vergleich zu nicht-deterministischen Systemen bei zunehmender Konkurrenz deutlich besser performt (vgl. Abbildung 8).<\/p>\n\n\n\n Herk\u00f6mmliche deterministische Systeme haben zwar weiterhin mit Latenzen (bzgl. des Konsensus-Protokolls) zu k\u00e4mpfen, jedoch gibt es Systeme wie SLOG, die versprechen auch diese Latenz zu verringern oder sogar zu eliminieren, um alle drei in der Einleitung genannten Eigenschaften zu erf\u00fcllen. <\/p>\n\n\n\n F\u00fcr Datenbankreplikationen ist der offensichtlichste Vorteil deterministischer Datenbanksysteme die Gew\u00e4hrleistung, dass, solange alle Replikate denselben Input erhalten, diese nicht voneinander abweichen. Weitere Vorteile in der deterministischen Architektur sind auf jeden Fall die Skalierbarkeit, die Modularit\u00e4t und die Gleichzeitigkeit. Nicht-deterministische Ausf\u00e4lle f\u00fchren in einem deterministischen System nicht zu einem Transaktionsabbruch, da die Datenbank ihren Zustand zum Zeitpunkt des Absturzes immer wiederherstellen kann, was diese Systeme auch robuster gegen Fehler macht.<\/p>\n\n\n\n Auf den ersten Blick scheinen deterministische Architekturans\u00e4tze in verteilten Datenbanken die L\u00f6sung f\u00fcr viele bekannte Probleme, doch leider ist dieser Ansatz nicht f\u00fcr alle Datenbankanwendungen praktikabel. Da f\u00fcr den Planungsprozess die gesamte Transaktion vorhanden sein muss, sind deterministische Datenbanksysteme schlecht geeignet f\u00fcr ORM-Tools und andere Anwendungen, die Transaktionen nur in Teilen an die Datenbank \u00fcbermitteln.<\/p>\n\n\n\n Deterministische Datenbanksysteme haben sich als vielversprechender Weg zur Verbesserung der Skalierbarkeit, Modularit\u00e4t, des Durchsatzes und der Replikation von transaktionalen Datenbanksystemen erwiesen. Leider bieten alle neueren Implementierungen nur begrenzte oder gar keine Unterst\u00fctzung f\u00fcr interaktive Transaktionen, so dass sie in vielen bestehenden Implementierungen bisher nicht eingesetzt werden k\u00f6nnen.<\/p>\n\n\n\n Abadi, Daniel J. \u201eSLOG: Serializable, Low-Latency, Geo-Replicated Transactions\u201c. Gehalten auf der CMU Database Group – Vaccination Database Tech Talks (2021), CARNEGIE MELLON UNIVERSITY, 1. Februar 2021. https:\/\/www.youtube.com\/watch?v=TAdiilOOvNI&t=645s<\/a>.<\/p>\n\n\n\n \u201eDeterminismus\u201c. In Wikipedia<\/em>, 25. Dezember 2021. https:\/\/de.wikipedia.org\/w\/index.php?title=Determinismus&oldid=218485694<\/a>.<\/p>\n\n\n\n Faleiro, Daniel J. Abadi, Jose M. \u201eAn Overview of Deterministic Database Systems\u201c. Zugegriffen 15. M\u00e4rz 2022. https:\/\/cacm.acm.org\/magazines\/2018\/9\/230601-an-overview-of-deterministic-database-systems\/fulltext<\/a>.<\/p>\n\n\n\n Ren, Kun, Dennis Li, und Daniel J. Abadi. \u201eSLOG: Serializable, Low-Latency, Geo-Replicated Transactions\u201c. Proceedings of the VLDB Endowment<\/em> 12, Nr. 11 (Juli 2019): 1747\u201361. https:\/\/doi.org\/10.14778\/3342263.3342647<\/a>.<\/p>\n\n\n\n \u201eStrict Serializability\u201c. Zugegriffen 23. M\u00e4rz 2022. https:\/\/jepsen.io\/consistency\/models\/strict-serializable<\/a>.<\/p>\n\n\n\n \u201eTransaction throughput\u201c. Zugegriffen 23. M\u00e4rz 2022. https:\/\/docs.oracle.com\/cd\/E17276_01\/html\/programmer_reference\/transapp_throughput.html<\/a>.<\/p>\n\n\n\n<\/a><\/a>Was ist Determinismus im Kontext von Datenbanken?<\/strong><\/h2>\n\n\n\n
Wie funktioniert SLOG?<\/strong><\/h2>\n\n\n\n
\n
<\/a><\/a><\/a><\/a>\n
Fazit<\/h2>\n\n\n\n
<\/a>Quellen<\/h2>\n\n\n\n