HighLoad++, Mikhail Tyulenev (MongoDB): Kausale Konsistenz: Von der Theorie zur Praxis

Die nächste Konferenz HighLoad++ findet am 6. und 7. April 2020 in Sankt Petersburg statt.
Details und Tickets unter diesem Link. HighLoad++ Sibirien 2019. Saal „Krasnojarsk“. 25. Juni, 12:00. Thesen und Präsentation.

Es kommt vor, dass praktische Anforderungen mit der Theorie in Konflikt stehen, in der wichtige Aspekte für ein kommerzielles Produkt nicht berücksichtigt werden. In diesem Vortrag wird der Prozess der Auswahl und Kombination verschiedener Ansätze zur Erstellung von Komponenten für die kausale Konsistenz basierend auf akademischen Forschungsergebnissen beschrieben, die aus den Anforderungen eines kommerziellen Produkts abgeleitet sind. Die Zuhörer erfahren von bestehenden theoretischen Ansätzen zu logischen Uhren, Abhängigkeitsverfolgung, Systemsicherheit, Zeitsynchronisation und warum MongoDB sich für bestimmte Lösungen entschieden hat.

Mikhail Tyulenev (im Folgenden – MT): – Ich werde über kausale Konsistenz sprechen – eine Funktion, an der wir bei MongoDB gearbeitet haben. Ich arbeite in der Gruppe für verteilte Systeme, wir haben sie vor etwa zwei Jahren entwickelt.

Im Verlauf musste ich mich mit einer Vielzahl akademischer Forschung auseinandersetzen, weil diese Funktion recht gut untersucht ist. Es stellte sich heraus, dass keine der Veröffentlichungen den Anforderungen im Produktionsumfeld entspricht, da die spezifischen Anforderungen, die in jeder Produktionsanwendung vorhanden sind, berücksichtigt werden müssen.

Ich werde darüber sprechen, wie wir, als Verbraucher akademischer Forschung, daraus etwas erstellen, das wir unseren Nutzern als fertiges Produkt anbieten können, das einfach und sicher zu verwenden ist.

Kausale Konsistenz. Lassen Sie uns die Begriffe klären

Zunächst möchte ich in groben Zügen erläutern, was kausale Konsistenz ist. Es gibt zwei Charaktere – Leonard und Penny (aus der Serie „The Big Bang Theory“):

Angenommen, Penny ist in Europa und Leonard möchte ihr eine Überraschung, eine Party, machen. Und er denkt sich nichts Besseres aus, als sie aus seiner Freundesliste zu entfernen und allen Freunden ein Update im Feed zu schicken: „Lasst uns Penny erfreuen!“ (sie ist in Europa, während sie schläft, sieht sie das alles nicht und kann es nicht sehen, weil sie nicht dort ist). Schließlich löscht er diesen Beitrag, entfernt ihn aus dem Feed und stellt den Zugang wieder her, sodass sie nichts bemerkt und es keinen Skandal gibt.
Das ist alles wunderbar, aber nehmen wir an, das System ist verteilt und die Ereignisse laufen nicht ganz so ab. Es könnte zum Beispiel passieren, dass die Zugriffsbeschränkung von Penny eintrat, nachdem dieser Beitrag erschienen ist, wenn die Ereignisse nicht durch kausale Zusammenhänge verbunden sind. Das ist ein Beispiel dafür, wann kausale Konsistenz erforderlich ist, um eine Geschäftsanforderung zu erfüllen (in diesem Fall).

Tatsächlich sind dies ziemlich nicht-triviale Eigenschaften von Datenbanken – nur sehr wenige unterstützen sie. Lassen Sie uns zu den Modellen übergehen.

Konsistenzmodelle

Was ist überhaupt ein Konsistenzmodell in Datenbanken? Es sind bestimmte Garantien, die ein verteiltes System bezüglich der Daten und der Reihenfolge, in der der Kunde sie erhalten kann, gibt.

Im Grunde hängen alle Konsistenzmodelle davon ab, wie sehr ein verteiltes System einer solchen Architektur ähnelt, die beispielsweise auf einem einzigen Node auf einem Laptop läuft. Und wie sehr sich ein System, das auf Tausenden von geografisch verteilten Nodes arbeitet, von einem Laptop unterscheidet, in dem all diese Eigenschaften prinzipiell automatisch erfüllt sind.

Deshalb gelten Konsistenzmodelle nur für verteilte Systeme. Alle Systeme, die früher existierten und auf vertikaler Skalierung basierten, hatten solche Probleme nicht. Dort gab es einen Buffer Cache, aus dem alles stets abgerufen wurde.

Starke Modell

Die tatsächlich erste Modell ist das Starke (oder auch Riseability, wie es oft genannt wird). Es handelt sich um ein Konsistenzmodell, das garantiert, dass jede Änderung, sobald die Bestätigung vorliegt, dass sie erfolgt ist, von allen Nutzern des Systems gesehen werden kann.

Das schafft eine globale Reihenfolge aller Ereignisse in der Datenbank. Dies ist eine sehr starke Konsistenzeigenschaft und sie ist insgesamt sehr kostenintensiv. Dennoch wird sie sehr gut unterstützt. Sie ist einfach sehr teuer und langsam – daher wird sie selten genutzt. Das nennt man Riseability.

Es gibt eine weitere, stärkere Eigenschaft, die im Spanner unterstützt wird – sie wird externe Konsistenz genannt. Darüber werden wir später sprechen.

Kausal

Das Nächste ist Causal, genau das, worüber ich gesprochen habe. Zwischen Strong und Causal gibt es noch einige Unterebenen, über die ich nicht sprechen werde, aber sie alle reduzieren sich auf Causal. Dieses Modell ist wichtig, weil es das stärkste von allen Modellen ist, die stärkste Konsistenz bei Vorhandensein von Netzwerken oder Partitionen.

Causals sind die Situation, in der Ereignisse durch eine kausale Beziehung verbunden sind. Sehr oft werden sie aus der Perspektive des Kunden als Read your own rights wahrgenommen. Wenn der Kunde bestimmte Werte beobachtet hat, kann er die Werte, die in der Vergangenheit waren, nicht sehen. Er beginnt bereits, präfixartige Lesevorgänge zu sehen. Das alles läuft auf dasselbe hinaus.
Causals als Konsistenzmodell bedeutet eine partielle Ordnung von Ereignissen auf dem Server, bei der die Ereignisse von allen Clients in derselben Reihenfolge beobachtet werden. In diesem Fall - Leonard und Penny.

Eventual

Das dritte Modell ist die Eventual Consistency. Das ist das, was alle verteilten Systeme unterstützen, das Mindestmodell, das überhaupt sinnvoll ist. Es bedeutet Folgendes: Wenn wir Änderungen an den Daten vornehmen, werden sie irgendwann konsistent.

In diesem Moment sagt es nichts, sonst würde es zur External Consistency werden - das wäre eine ganz andere Geschichte. Dennoch ist dies ein sehr beliebtes Modell, das am weitesten verbreitet ist. Standardmäßig verwenden alle Benutzer verteilter Systeme tatsächlich die Eventual Consistency.

Ich möchte einige vergleichende Beispiele anführen:

Was bedeuten diese Pfeile?

• Latenz. Bei zunehmender Stärke der Konsistenz wird sie aus offensichtlichen Gründen größer: Es müssen mehr Aufzeichnungen gemacht, Bestätigungen von allen Hosts und Knoten im Cluster eingeholt werden, dass die Daten dort bereits vorhanden sind. Dementsprechend ist die Eventual Consistency die schnellste Antwort, weil man dort in der Regel sogar im Speicher committieren kann und das grundsätzlich ausreicht.
• Verfügbarkeit. Wenn man dies als die Möglichkeit versteht, dass das System bei Vorhandensein von Netzwerkunterbrechungen, Partitionen oder einigen Ausfällen antworten kann - die Fehlertoleranz steigt bei abnehmendem Konsistenzmodell, da es ausreicht, dass ein Host erreichbar ist und dabei einige Daten liefert. Eventual Consistency garantiert im Übrigen nichts über die Daten - es kann alles Mögliche sein.
• Anomalien. Dabei steigt natürlich die Anzahl der Anomalien. Bei Strong Consistency sollten diese eigentlich kaum vorkommen, während sie bei Eventual Consistency beliebig häufig sein können. Die Frage stellt sich: Warum wählen die Menschen Eventual Consistency, wenn sie Anomalien enthält? Die Antwort liegt darin, dass Eventual Consistency-Modelle anwendbar sind und Anomalien zum Beispiel nur für einen kurzen Zeitraum bestehen; es gibt die Möglichkeit, einen Master zum Lesen zu nutzen und mehr oder weniger konsistente Daten zu lesen; oft gibt es die Möglichkeit, starke Konsistenzmodelle zu verwenden. Praktisch funktioniert das und häufig ist die Anzahl der Anomalien zeitlich begrenzt.

CAP-Theorem

Wenn Sie die Begriffe Consistency und Availability sehen, was kommt Ihnen in den Sinn? Richtig – das CAP-Theorem! Ich möchte jetzt einen Mythos aufklären… Das bin nicht ich – es ist Martin Kleppmann, der einen großartigen Artikel und ein hervorragendes Buch geschrieben hat.

Das CAP-Theorem ist ein Prinzip, das in den 2000er Jahren formuliert wurde, wonach Consistency, Availability und Partitions: Wählen Sie beliebig zwei, und die dritte kann nicht gewählt werden. Das war ein gewisses Prinzip. Es wurde einige Jahre später als Theorem bewiesen, das taten Gilbert und Lynch. Danach wurde es wie ein Mantra verwendet – Systeme wurden in CA, CP, AP und so weiter unterteilt.

Dieses Theorem wurde tatsächlich für folgende Fälle bewiesen... Erstens wurde Availability nicht als kontinuierlicher Wert von null bis hundert betrachtet (0 – System 'tot', 100 – antwortet schnell; so haben wir es uns angewöhnt zu betrachten), sondern als eine Eigenschaft eines Algorithmus, die garantiert, dass er bei allen seinen Ausführungen Daten zurückgibt.

Über die Antwortzeit steht dort kein Wort! Es gibt einen Algorithmus, der Daten nach 100 Jahren zurückgibt – ein völlig hervorragender verfügbarer Algorithmus, der Teil des CAP-Theorems ist.
Zweitens: Das Theorem wurde für Änderungen der Werte desselben Schlüssels bewiesen, wobei diese Änderungen eine resizable Linie darstellen. Das bedeutet, dass sie in der Praxis kaum verwendet werden, weil es andere Modelle wie Eventual Consistency, Strong Consistency (vielleicht) gibt.

Worauf will ich hinaus? Auf das, dass das CAP-Theorem in der Form, wie es bewiesen wurde, praktisch nicht anwendbar ist und selten verwendet wird. In der theoretischen Form schränkt es auf eine gewisse Weise alles ein. Es ergibt sich ein gewisses Prinzip, das intuitiv korrekt ist, aber insgesamt nicht wirklich bewiesen ist.

Causal Consistency ist das stärkste Modell

Was jetzt passiert, ist, dass man alle drei Dinge erhalten kann: Konsistenz, Verfügbarkeit kann durch Partitionen erreicht werden. Insbesondere die kausale Konsistenz – das ist das stärkste Konsistenzmodell, das auch bei Partitions (Netzwerkausfällen) funktioniert. Deshalb ist es so interessant, daher haben wir uns damit beschäftigt.

Erstens vereinfacht es die Arbeit der Anwendungsentwickler. Insbesondere gibt es eine starke Unterstützung vom Server: Wenn alle Aufzeichnungen, die innerhalb eines Clients erfolgen, garantiert in dieser Reihenfolge auf einem anderen Client ankommen. Zweitens hält sie Partitionen stand.

Die interne Küche von MongoDB

Im Gedenken an das Mittagessen bewegen wir uns in die Küche. Ich werde über das Systemmodell erzählen, insbesondere – was MongoDB für diejenigen ist, die zum ersten Mal von dieser Datenbank hören.

MongoDB (im Folgenden „MongoDB“) ist ein verteiltes System, das horizontale Skalierung unterstützt, also Sharding; und innerhalb jedes Shards unterstützt es auch Datenredundanz, also Replikation.

Sharding in „MongoDB“ (kein relationales DBMS) führt eine automatische Balancierung durch, das heißt, jede Dokumentensammlung (oder „Tabelle“ in relationalen Daten) wird in Stücke zerlegt, und der Server bewegt sie automatisch zwischen den Shards.

Der Query Router, der die Anfragen verteilt, ist für den Client eine Art von Client, über den er arbeitet. Er weiß bereits, wo sich welche Daten befinden und leitet alle Anfragen an den richtigen Shard weiter.

Ein weiterer wichtiger Punkt: MongoDB ist ein Single Master. Es gibt einen Primary – dieser kann Aufzeichnungen übernehmen, die die Schlüssel unterstützen, die er enthält. Multi-Master-Schreibvorgänge sind nicht möglich.

Wir haben das Release 4.2 gemacht – es sind neue interessante Dinge hinzugekommen. Insbesondere haben wir Lucene eingeführt – die Suche – also ausführbares Java direkt in „Mongo“, und jetzt ist es möglich, die Suche über Lucene durchzuführen, genauso wie in „Elasticsearch“.

Und wir haben ein neues Produkt geschaffen – Charts, das ebenfalls auf „Atlas“ (der eigene Cloud von „Mongo“) verfügbar ist. Sie haben ein Free Tier – man kann damit experimentieren. Charts hat mir sehr gefallen – Datenvisualisierung, sehr intuitiv.

Zutaten der kausalen Konsistenz

Ich habe ungefähr 230 Artikel gezählt, die zu diesem Thema veröffentlicht wurden – von Leslie Lamport. Ich werde Ihnen jetzt aus meinem Gedächtnis einige Teile dieser Materialien übermitteln.

Alles begann mit dem Artikel von Leslie Lampert, der in den 1970er Jahren geschrieben wurde. Wie Sie sehen, gibt es bis heute weiterhin Forschungsarbeiten zu diesem Thema. Derzeit erlebt die kausale Konsistenz ein Interesse im Zusammenhang mit der Entwicklung von verteilten Systemen.

Einschränkungen

Welche Einschränkungen gibt es? Das ist tatsächlich einer der Hauptpunkte, denn die Einschränkungen, die Produktionssysteme aufweisen, unterscheiden sich erheblich von den Einschränkungen, die in akademischen Artikeln existieren. Oft sind sie recht künstlich.

• Erstens, „MongoDB“ ist ein Single-Master, wie ich bereits gesagt habe (das vereinfacht vieles).
• Wir gehen davon aus, dass das System etwa 10.000 Shards unterstützen sollte. Wir können keine architektonischen Entscheidungen treffen, die diesen Wert eindeutig einschränken.
• Wir haben eine Cloud, aber wir gehen davon aus, dass der Benutzer die Möglichkeit haben sollte, wenn er das Binary herunterlädt, es auf seinem Laptop ausführt und alles perfekt funktioniert.
• Wir gehen davon aus, dass das in der Forschung selten genutzt wird: externe Clients können tun, was sie wollen. „MongoDB“ ist Open Source. Entsprechend können Clients sehr clever oder bösartig sein – sie können alles kaputtmachen wollen. Wir gehen davon aus, dass byzantinische Fehler auftreten können.
• Für externe Clients, die außerhalb des Perimeters sind – eine wichtige Einschränkung: Wenn diese Funktion deaktiviert ist, sollten keine Leistungsverschlechterungen beobachtet werden.
• Ein weiterer Punkt – ganz anti-akademisch: die Kompatibilität zwischen früheren und zukünftigen Versionen. Alte Treiber müssen neue Updates unterstützen, und die Datenbank muss alte Treiber unterstützen.

Insgesamt stellen all dies Einschränkungen dar.

Komponenten der kausalen Konsistenz

Ich werde jetzt einige Komponenten vorstellen. Wenn man die kausale Konsistenz betrachtet, lassen sich verschiedene Blöcke unterscheiden. Wir haben aus Arbeiten ausgewählt, die zu einem bestimmten Block gehören: Abhängigkeitsverfolgung, die Auswahl von Uhren, wie diese Uhren untereinander synchronisiert werden können, und wie wir Sicherheit gewährleisten – das ist ein grober Überblick über das, worüber ich sprechen werde:

Vollständige Abhängigkeitsverfolgung (Full Dependency Tracking)

Warum ist das nötig? Damit, wenn Daten repliziert werden – jeder Eintrag, jede Änderung der Daten enthält Informationen darüber, von welchen Änderungen sie abhängt. Die allererste und naivste Änderung ist die, dass jede Nachricht, die einen Eintrag enthält, Informationen über die vorherigen Nachrichten enthält:

In diesem Beispiel sind die Nummern in geschweiften Klammern die Eintragsnummern. Manchmal werden diese Einträge mit den Werten sogar ganz übergeben, manchmal werden irgendwelche Versionen übergeben. Der Kern der Sache ist, dass jede Änderung Informationen über die vorherige enthält (sie trägt all dies klar in sich).

Warum haben wir uns entschieden, einen solchen Ansatz (vollständiges Tracking) nicht zu verwenden? Offensichtlich, weil dieser Ansatz unpraktisch ist: Jede Änderung in einem sozialen Netzwerk hängt von allen vorherigen Änderungen in diesem sozialen Netzwerk ab, was zum Beispiel „Facebook“ oder „VKontakte“ in jedem Update überträgt. Dennoch gibt es viele Studien über genau das Full Dependency Tracking – das sind prä-soziale Netzwerke, in einigen Situationen funktioniert das tatsächlich.

Explizites Abhängigkeits-Tracking (Explicit Dependency Tracking)

Der nächste ist eingeschränkter. Hier wird ebenfalls die Übertragung von Informationen betrachtet, aber nur von der, die offensichtlich abhängt. Was von was abhängt, bestimmt in der Regel bereits die Anwendung. Wenn Daten repliziert werden, werden bei einer Anfrage nur die Antworten zurückgegeben, wenn die vorherigen Abhängigkeiten erfüllt sind, das heißt, angezeigt werden. Darin liegt der Kern, wie kausale Konsistenz funktioniert.

Sie sieht, dass Eintrag 5 von den Einträgen 1, 2, 3, 4 abhängt – entsprechend wartet sie, bevor der Kunde Zugriff auf die Änderungen erhält, die durch das Zugriffsrecht von Penny vorgenommen wurden, wenn alle vorherigen Änderungen bereits in die Datenbank eingegangen sind.

Das befriedigt uns auch nicht, weil es trotzdem zu viele Informationen gibt, und das wird langsam machen. Es gibt einen anderen Ansatz…

Lamport-Uhr (Lamport Clock)

Sie sind sehr alt. Die Lamport-Uhr impliziert, dass diese Abhängigkeiten in eine skalare Funktion zusammengefasst werden, die Lamport-Uhr genannt wird.

Eine skalare Funktion ist eine abstrakte Zahl. Oft wird sie als logische Zeit bezeichnet. Bei jedem Ereignis erhöht sich dieser Zähler. Der Zähler, der derzeit dem Prozess bekannt ist, sendet jede Nachricht. Es ist klar, dass Prozesse desynchronisiert sein können und unterschiedliche Zeiten haben können. Dennoch gleicht das System durch diesen Nachrichtenaustausch die Uhren irgendwie aus. Was passiert in diesem Fall?

Ich habe den großen Shard halbiert, um es verständlich zu machen: Friends können in einem Knoten leben, der ein Stück der Sammlung enthält, während Feed in einem völlig anderen Knoten leben kann, der ein Stück dieser Sammlung enthält. Ist klar, wie sie nicht in der Warteschlange landen können? Zuerst sagt Feed: "Repliziert", und dann - Friends. Wenn das System keine Garantien bietet, dass Feed nicht angezeigt wird, solange die Abhängigkeiten von Friends in der Sammlung Friends auch nicht geliefert werden, haben wir genau die Situation, die ich erwähnt habe.

Sie sehen, wie sich die logische Zeit des Counters auf dem Feed erhöht:

Daher ist die Hauptsache, die diese Lamport-Uhr und die kausale Konsistenz (erklärt durch die Lamport-Uhr) zusammenhält: Wenn wir Ereignisse A und B haben und Ereignis B von Ereignis A abhängt *, dann folgt daraus, dass die Logische Zeit von Ereignis A kleiner ist als die Logische Zeit von Ereignis B.

* Manchmal wird auch gesagt, dass A vor B passiert ist, das heißt, A geschah vor B – das ist eine Art Relation, die die Gesamtheit der Ereignisse, die überhaupt stattgefunden haben, teilweise ordnet.

Umgekehrt gilt das nicht. Das ist tatsächlich einer der Hauptnachteile der Lamport-Uhr – die partielle Ordnung. Es gibt das Konzept von gleichzeitigen Ereignissen, das heißt Ereignisse, bei denen weder (A passiert vor B) noch (A passiert vor B) gilt. Ein Beispiel könnte das gleichzeitige Hinzufügen von Leonard zu den Freunden einer anderen Person sein (nicht einmal von Leonard, sondern von Sheldon, zum Beispiel).
Das ist die Eigenschaft, die oft bei der Arbeit mit Lamport-Uhren genutzt wird: Man schaut sich genau die Funktion an und zieht daraus den Schluss – vielleicht sind diese Ereignisse abhängig. Denn in eine Richtung ist es wahr: Wenn die Logische Zeit A kleiner ist als die Logische Zeit B, dann kann B nicht vor A passieren; ist sie größer, dann kann es sein.

Vektor-Uhren (Vector Clock)

Die logische Entwicklung der Lamport-Uhren sind die Vektor-Uhren. Sie unterscheiden sich dadurch, dass jeder Knoten, der hier vorhanden ist, seine eigenen, separaten Uhren enthält, und diese werden als Vektor übermittelt.
In diesem Fall sehen Sie, dass der Nullindex des Vektors für den Feed und der erste Index des Vektors für die Freunde verantwortlich ist (jede dieser Knoten). Und jetzt werden sie zunehmen: Der Nullindex des "Feeds" erhöht sich bei der Aufzeichnung – 1, 2, 3:

Was sind die Vorteile von Vektoruhren? Sie ermöglichen es, welche Ereignisse simultan sind und wann sie an verschiedenen Knoten stattfinden. Das ist für das Sharding-System wie "MongoDB" sehr wichtig. Wir haben uns jedoch nicht dafür entschieden, obwohl es ein großartiges Tool ist, das wunderbar funktioniert und uns wahrscheinlich gepasst hätte...

Wenn wir 10.000 Shards haben, können wir keine 10.000 Komponenten übermitteln, selbst wenn wir komprimieren oder etwas anderes einfallen lassen – die Nuttungsrate wird immer viel geringer sein als das Volumen des gesamten Vektors. Daher, mit schwerem Herzen, haben wir darauf verzichtet und sind zu einer anderen Lösung übergegangen.

Spanner TrueTime. Atomuhren

Ich habe gesagt, dass es um den "Spanner" geht. Das ist ein cooles Ding, direkt aus dem 21. Jahrhundert: Atomuhren, GPS-Synchronisation.

Was ist die Idee? Der "Spanner" ist ein Google-System, das kürzlich sogar für die Leute verfügbar wurde (sie haben SQL hinzugefügt). Jede Transaktion hat dort einen bestimmten Zeitstempel. Da die Zeit synchronisiert ist*, kann jedem Ereignis eine bestimmte Zeit zugewiesen werden – Atomuhren haben eine Wartezeit, nach der garantiert "ein anderes Zeitgeschehen" eintritt.

Somit wird durch einfaches Eintragen in die Datenbank und Warten einer gewissen Zeit automatisch die Serialisierbarkeit des Ereignisses garantiert. Sie haben das stärkste Konsistenzmodell, das man sich grundsätzlich vorstellen kann – es ist externe Konsistenz.

* Das ist das Hauptproblem der Lamport-Uhren – sie sind in verteilten Systemen niemals synchron. Sie können auseinanderdriften, selbst bei vorhandener NTP funktionieren sie nicht sehr gut. Der "Spanner" verfügt über Atomuhren und Synchronisation, anscheinend auf Mikrosekunden genau.

Warum haben wir uns nicht dafür entschieden? Wir gehen nicht davon aus, dass unsere Nutzer über eingebaute Atomuhren verfügen. Wenn sie eingebaut in jedes Laptop verfügbar sind, wird es eine super coole GPS-Synchronisation geben – dann ja... Aber bis jetzt ist das Beste, was möglich ist – Amazon, Basisstationen – für Enthusiasten... Deshalb haben wir andere Uhren verwendet.

Hybride Uhren (Hybrid Clock)

Das ist praktisch das, was in MongoDB tickt, um kausale Konsistenz sicherzustellen. Hybrid sind sie worin? Ein Hybrid ist ein Skalarwert, der aus zwei Komponenten besteht:

• Die erste ist die Unix-Zeit (die Anzahl der Sekunden seit "Beginn der Computerwelt").
• Die zweite ist ein gewisser Inkrement, ebenfalls ein 32-Bit unsigned int.

Das ist im Wesentlichen alles. Es gibt einen Ansatz: Der Teil, der für die Zeit verantwortlich ist, wird ständig mit den Uhren synchronisiert; jedes Mal, wenn ein Update erfolgt, synchronisiert sich dieser Teil mit den Uhren und es stellt sich heraus, dass die Zeit immer mehr oder weniger korrekt ist, während der Inkrement es ermöglicht, Veranstaltungen zu unterscheiden, die im selben Moment stattfinden.

Warum ist das wichtig für MongoDB? Weil es ermöglicht, bestimmte Backups und Wiederherstellungen zu einem bestimmten Zeitpunkt durchzuführen, das heißt, die Ereignisse werden zeitlich indiziert. Das ist wichtig, wenn bestimmte Ereignisse benötigt werden; für eine Datenbank sind Ereignisse die Änderungen in der Datenbank, die in bestimmten Zeiträumen stattgefunden haben.

Den wichtigsten Grund werde ich nur Ihnen sagen (bitte, erzählen Sie es niemandem)! Wir haben das so gemacht, weil so die geordneten, indizierten Daten im MongoDB OpLog aussehen. OpLog ist eine Datenstruktur, die alle Änderungen in der Datenbank enthält: Sie gelangen zunächst in das OpLog und werden dann erst auf den Storage angewendet, wenn es sich um eine replizierte Datensatz oder Shard handelt.

Das war der Hauptgrund. Es gibt jedoch auch praktische Anforderungen an die Entwicklung der Datenbank, das bedeutet, dass es einfach sein muss - wenig Code, so wenige defekte Elemente wie möglich, die neu geschrieben und getestet werden müssen. Dass unsere OpLogs mit hybriden Uhren indiziert waren, hat stark geholfen und die richtige Wahl ermöglicht. Das hat sich tatsächlich bewährt und irgendwie zauberhaft beim ersten Prototypen funktioniert. Es war wirklich großartig!

Uhrensynchronisation

Es gibt mehrere synchronisationsmethoden, die in der wissenschaftlichen literatur beschrieben sind. Ich spreche von synchronisation, wenn wir zwei verschiedene shards haben. Wenn es nur einen replika-satz gibt, ist keine synchronisation notwendig: das ist «single-master»; wir haben ein OpLog, in das alle änderungen eingehen – in diesem fall sind die gesamten einträge bereits sequenziell im «OpLog» geordnet. Aber wenn wir zwei unterschiedliche shards haben, ist die synchronisation der zeit wichtig. Hier haben vektoruhren mehr geholfen! Aber die haben wir nicht.

Die zweite möglichkeit sind die «Herzschläge» (Heartbeats). Man kann einige signale austauschen, die in regelmäßigen abständen gesendet werden. Aber die «Herzschläge» sind zu langsam, wir können die latenz unseren kunden nicht bieten.

Echte zeit – das ist natürlich eine großartige sache. Aber wiederum, das ist wahrscheinlich die zukunft… Obwohl man im «Atlas» bereits arbeiten kann, gibt es schon schnelle «amazonische» zeitsynchronisatoren. Aber das wird nicht für alle verfügbar sein.

Gossiping ist, wenn alle nachrichten eine zeitangabe enthalten. Das ist ungefähr das, was wir verwenden. Jede nachricht zwischen nützen, treibern, routen und datenknoten – alles für «MongoDB» – sind irgendwelche elemente, komponenten einer datenbank, die uhren besitzen, die ticken. Überall haben sie den wert der hybriden zeit, der übertragen wird. 64 bit? Das ist möglich, das lässt sich umsetzen.

Wie funktioniert das alles zusammen?

Hier betrachte ich ein replika-set, um es etwas einfacher zu halten. Es gibt einen Primary und einen Secondary. Der Secondary führt die replikation durch und ist nicht immer vollständig mit dem Primary synchronisiert.

Es erfolgt ein einfügen (insert) im «Primary» mit einem bestimmten zeitwert. Dieses insert erhöht den internen zähler um 11, wenn das maximum erreicht ist. Oder es wird die zeiten überprüft und synchronisiert sich nach den uhren, wenn die zeiten höher sind. Dies ermöglicht eine zeitliche ordnung.

Nachdem er den eintrag vorgenommen hat, tritt ein wichtiger moment ein. Die uhren in «MongoDB» werden nur dann inkrementiert, wenn ein eintrag im «OpLog» erfolgt. Das ist das ereignis, das den zustand des systems ändert. In allen klassischen artikeln wird ein ereignis als das eintrudeln einer nachricht in einem knoten betrachtet: eine nachricht ist angekommen – das bedeutet, das system hat seinen zustand geändert.

Das hängt damit zusammen, dass man bei der Forschung nicht genau verstehen kann, wie diese Nachricht interpretiert wird. Wir wissen sicher, dass, wenn sie nicht im "Oplog" erfasst ist, sie überhaupt nicht interpretiert wird, und die Systemzustandsänderung ist nur der Eintrag im "Oplog". Das vereinfacht uns alles: sowohl das Modell als auch die Möglichkeit, innerhalb eines Replikatsatzes zu ordnen, sowie viele andere nützliche Dinge.

Es wird der Wert zurückgegeben, der bereits im "Oplog" gespeichert ist – wir wissen, dass dieser Wert im "Oplog" bereits vorhanden ist, und seine Zeit ist 12. Angenommen, jetzt beginnt das Lesen von einem anderen Knoten (Secondary), und er überträgt bereits afterClusterTime in der Nachricht selbst. Er sagt: "Ich benötige alles, was mindestens nach 12 oder während der zwölf passiert ist" (siehe Bild oben).

Das nennt man Causal a consistent (CAT). Es gibt ein solches Konzept in der Theorie, dass dies ein gewisser Zeitabschnitt ist, der für sich selbst konsistent ist. In diesem Fall kann man sagen, dass dies der Zustand des Systems ist, der im Moment 12 beobachtet wurde.

Hier ist momentan noch nichts, weil es quasi die Situation simuliert, in der der Secondary die Daten vom Primary replizieren muss. Er wartet... Und hier kommen die Daten – er gibt diese Werte zurück.

So funktioniert es ungefähr. Fast.

Was bedeutet "fast"? Angenommen, es gibt eine Person, die gelesen und verstanden hat, wie das alles funktioniert. Sie hat verstanden, dass jedes Mal, wenn ClusterTime auftritt, die internen logischen Uhren aktualisiert werden, und dann erhöht der nächste Eintrag um eins. Diese Funktion nimmt 20 Zeilen ein. Angenommen, diese Person überträgt die maximal große 64-Bit-Zahl minus eins.

Warum "minus eins"? Weil die internen Uhren in diesen Wert eingesetzt werden (offensichtlich ist das die größte mögliche und größer als die aktuelle Zeit), dann erfolgt der Eintrag im "Oplog", und die Uhren werden erneut um eins inkrementiert – und dann wird bereits der maximale Wert erreicht (da sind einfach alle Einsen, weiter geht es nicht, unsaint int's).

Es ist klar, dass das System danach absolut für nichts verfügbar wird. Man kann es nur entladen, reinigen – viel Handarbeit. Vollständige Verfügbarkeit:

Wenn sich das irgendwo anders repliziert, fällt der gesamte Cluster aus. Eine absolut inakzeptable Situation, die jeder sehr schnell und einfach organisieren kann! Daher haben wir diesen Punkt als einen der wichtigsten angesehen. Wie kann man das verhindern?

Unser Weg ist es, clusterTime zu unterschreiben.

So wird es in der Nachricht übermittelt (vor dem blauen Text). Aber wir haben auch begonnen, eine Signatur zu generieren (blauer Text):

Die Signatur wird mit einem Schlüssel generiert, der innerhalb der Datenbank im geschützten Bereich gespeichert ist; sie wird selbst generiert und aktualisiert (die Benutzer sehen davon nichts). Ein Hash wird generiert, und jede Nachricht wird beim Erstellen signiert und beim Empfang validiert.
Wahrscheinlich fragen sich die Leute: „Wie sehr verlangsamt das alles?“ Ich habe gesagt, dass es schnell funktionieren sollte, insbesondere ohne diese Funktion.

Was bedeutet es in diesem Fall, Causal consistency zu nutzen? Es zeigt den afterClusterTime-Parameter an. Andernfalls werden Werte in jedem Fall übertragen. Gossiping funktioniert seit Version 3.6 immer.

Wenn wir eine ständige Generierung von Signaturen beibehalten, wird das die Systeme selbst ohne diese Funktion verlangsamen, was unseren Ansätzen und Anforderungen nicht entspricht. Was haben wir also gemacht?

Mach das schnell!

Es ist eine ziemlich einfache Sache, aber der Trick ist interessant – ich teile es, vielleicht interessiert es jemanden.
Wir haben einen Hash, in dem signierte Daten gespeichert sind. Alle Daten gehen durch den Cache. Der Cache signiert nicht spezifisch die Zeit, sondern einen Bereich. Wenn ein bestimmter Wert eintrifft, generieren wir einen Bereich, maskieren die letzten 16 Bits, und diesen Wert signieren wir:

Durch den Erhalt einer solchen Signatur beschleunigen wir das System (theoretisch) um 65.000 Mal. Es funktioniert hervorragend: Als wir Experimente durchführten, wurde die Zeit für unser sequenzielles Update tatsächlich um 10.000 Mal verkürzt. Es ist klar, dass das nicht funktioniert, wenn sie durcheinander kommen. Aber in den meisten praktischen Fällen funktioniert es. Die Kombination aus Range-Signatur und Signatur hat das Sicherheitsproblem gelöst.

Was haben wir gelernt?

Die Lektionen, die wir daraus gezogen haben:

• Man muss Materialien, Geschichten und Artikel lesen, weil es viel Interessantes gibt. Wenn wir an einer Funktion arbeiten (besonders jetzt, wo wir Transaktionen gemacht haben usw.), sollte man lesen und sich einarbeiten. Das kostet Zeit, ist aber sehr nützlich, da man versteht, wo wir stehen. Wir haben nichts wirklich Neues erfunden – wir haben einfach Zutaten verwendet.

  Generell gibt es einen bestimmten Unterschied im Denken, wenn eine akademische Konferenz stattfindet (zum Beispiel "Sigmon") – dort konzentriert sich jeder auf neue Ideen. Was ist die Neuheit unseres Algorithmus? Hier gibt es nicht viel Neuheit. Die Neuheit besteht vielmehr darin, wie wir bestehende Ansätze miteinander gemischt haben. Deshalb ist es wichtig, die Klassiker zu lesen, beginnend mit Lamport.

• Im Produktionsumfeld gibt es völlig andere Anforderungen. Ich bin mir sicher, dass viele von Ihnen es nicht mit "sphärischen" Datenbanken im abstrakten Vakuum zu tun haben, sondern mit normalen, realen Dingen, die Probleme hinsichtlich Verfügbarkeit, Latenz und Fehlertoleranz haben.
• Zuletzt mussten wir verschiedene Ideen in Betracht ziehen und mehrere völlig unterschiedliche Artikel zu einem Ansatz kombinieren. Die Idee des Signierens stammt zum Beispiel aus einem Artikel, der das Paxos-Protokoll behandelt hat, das für nicht-byzantinische Fehler innerhalb des Autorisierungsprotokolls gedacht ist, für byzantinische – außerhalb des Autorisierungsprotokolls... Insgesamt ist das genau das, was wir am Ende getan haben.

  Hier gibt es absolut nichts Neues! Aber sobald wir all das zusammengefügt haben... Es ist dasselbe wie zu sagen, dass das Rezept für Salat Olivier nichts Besonderes ist, weil Eier, Mayonnaise und Gurken bereits erfunden wurden... Es ist ungefähr die gleiche Geschichte.

Ich beende damit. Danke!

Fragen

Frage aus dem Publikum (im Folgenden – F): – Vielen Dank, Michail, für den Vortrag! Das Thema Zeit ist interessant. Sie verwenden Gossiping. Sie haben gesagt, dass jeder seine eigene Zeit hat, jeder kennt seine lokale Zeit. Ich habe so verstanden, dass wir einen Treiber haben – es kann viele Kunden mit Treibern geben, ebenso viele Abfrageplaner, auch viele Shards... Was passiert mit dem System, wenn es plötzlich eine Diskrepanz gibt: einer denkt, dass er eine Minute voraus ist, der andere – eine Minute hinterher? Wo landen wir?

MT: – Eine ausgezeichnete Frage! Ich wollte gerade über die Shards sprechen. Wenn ich die Frage richtig verstehe, haben wir die Situation, dass es Shard 1 und Shard 2 gibt. Das Lesen erfolgt von diesen beiden Shards – sie haben unterschiedliche Zeiten, und sie interagieren nicht miteinander, weil die Zeit, die sie kennen, unterschiedlich ist, besonders die Zeit, die in ihren Op-Logs existiert.
Angenommen, Shard 1 hat eine Million Einträge gemacht, Shard 2 – überhaupt nichts, und die Anfrage kam an beide Shards. Und der erste hat eine afterClusterTime von über einer Million. In dieser Situation, wie ich erklärt habe, wird Shard 2 nie antworten.

Frage: – Ich wollte wissen, wie sie synchronisiert werden und eine logische Zeit auswählen?

MT: – Die Synchronisierung erfolgt sehr einfach. Wenn Shard eine afterClusterTime erhält und die Zeit im „Op-Log“ nicht findet – initiiert es no approved. Das bedeutet, dass es seine Zeit auf diesen Wert anhebt. Das bedeutet, dass es keine Ereignisse gibt, die auf diese Anfrage reagieren. Es erzeugt dieses Ereignis künstlich und ist somit kausal konsistent.

Frage: – Und was, wenn danach noch irgendwelche Ereignisse eintreffen, die im Netzwerk irgendwo verloren gegangen sind?

MT: – Shard ist so konstruiert, dass sie nicht mehr eintreffen, da es einen Single Master gibt. Wenn er bereits geschrieben hat, dann werden sie nicht mehr eintreffen, sondern danach. Es kann nicht passieren, dass irgendwo etwas stecken bleibt, dann macht er no write und diese Ereignisse kommen an – und die kausale Konsistenz wird verletzt. Wenn er no write macht, müssen sie alle danach kommen (er wird auf sie warten).

Frage: – Ich habe einige Fragen zu den Warteschlangen. Kausale Konsistenz setzt voraus, dass es eine bestimmte Warteschlange von Aktionen gibt, die ausgeführt werden müssen. Was passiert, wenn ein Paket verloren geht? Es kommt 10., 11. ... aber der 12. geht verloren, während alle anderen warten, dass es ausgeführt wird. Und plötzlich stirbt die Maschine, wir können nichts tun. Gibt es eine maximale Länge der Warteschlange, die sich anhäuft, bevor sie ausgeführt wird? Was für einen fatalen Fehler gibt es bei Verlust eines bestimmten Zustands? Zumal wir aufzeichnen, dass es einen vorherigen Zustand gibt, müssen wir doch irgendwie darauf basieren? Aber wir haben uns nicht darauf gestützt!

MT: – Auch eine ausgezeichnete Frage! Was tun wir? In MongoDB gibt es das Konzept von Quorum-Schreibvorgängen und Quorum-Lesungen. In welchen Fällen kann eine Nachricht verloren gehen? Wenn der Schreibvorgang ohne Quorum ist oder wenn die Lesevorgänge nicht quorum sind (da kann auch etwas Müll anhaften).
Bezüglich der kausalen Konsistenz haben wir eine umfangreiche experimentelle Überprüfung durchgeführt, deren Ergebnis war, dass, wenn Aufzeichnungen und Lesevorgänge nicht quorum-basiert sind, Verstöße gegen die kausale Konsistenz auftreten. Genau das, was Sie sagen!

Unser Rat: Verwenden Sie mindestens quorum-basiertes Lesen bei der Nutzung der kausalen Konsistenz. In diesem Fall wird nichts verloren gehen, selbst wenn die quorum-basierte Aufzeichnung ausfällt… Das ist eine orthogonale Situation: Wenn der Benutzer nicht möchte, dass Daten verloren gehen, muss er eine quorum-basierte Aufzeichnung verwenden. Kausale Konsistenz bietet keine Garantie für die Haltbarkeit. Die Garantie für die Haltbarkeit bietet die Replikation und die mit der Replikation verbundene Technik.

Frage: – Wenn wir eine Instanz erstellen, die bei uns das Sharding durchführt (nicht master, sondern slave), stützt sie sich auf die Unix-Zeit ihrer eigenen Maschine oder auf die Zeit des "Masters"; synchronisiert sie sich beim ersten Mal oder regelmäßig?

MT: – Jetzt werde ich das klären. Ein Shard (d. h. eine horizontale Partition) hat immer einen Primärschlüssel. In einem Shard kann es einen "Master" geben und Replikate. Aber der Shard unterstützt immer die Speicherung, weil er ein gewisses Domänenmodell unterstützen muss (im Shard befindet sich der Primärschlüssel).

Frage: – Das heißt, alles hängt rein vom "Master" ab? Wird immer die "Master"-Zeit verwendet?

MT: – Ja. Man kann bildlich sagen: Die Uhren ticken, wenn die Aufnahme im "Master", im "OpLog", erfolgt.

Frage: – Wir haben einen Kunden, der sich verbindet, und er muss über die Zeit nichts wissen?

MT: – Er muss gar nichts wissen! Wenn wir darüber sprechen, wie das beim Kunden funktioniert: Der Kunde muss, wenn er die kausale Konsistenz nutzen möchte, eine Sitzung eröffnen. In dieser Sitzung sind alles enthalten: Transaktionen in der Sitzung sowie Rechte abrufen… Eine Sitzung ist eine Anordnung der logischen Ereignisse, die mit dem Kunden passieren.

Wenn er diese Sitzung eröffnet und dort angibt, dass er kausale Konsistenz möchte (sofern die Sitzung standardmäßig kausale Konsistenz unterstützt), funktioniert alles automatisch. Der Treiber speichert diese Zeit und erhöht sie, wenn er eine neue Nachricht erhält. Er merkt sich, welche Antwort der vorherige Server zurückgegeben hat, der die Daten geliefert hat. Die nächste Anfrage wird afterCluster enthalten ("Zeit größer als diese").

Der Kunde muss wirklich überhaupt nichts wissen! Das ist für ihn völlig intransparent. Wenn die Leute diese Funktionen nutzen, was kann man damit erreichen? Erstens kann man sicher auf Secondaries lesen: Man kann auf das Primary schreiben und von geografisch replizierten Secondaries lesen und sich sicher sein, dass es funktioniert. Dabei können die Sessions, die auf dem Primary aufgezeichnet wurden, sogar an das Secondary übertragen werden, d. h. man kann nicht nur eine Session, sondern mehrere verwenden.

Frage: – Das Thema der Eventual Consistency ist eng verbunden mit einem neuen Bereich der Informatik – den CRDT-Datentypen (Conflict-free Replicated Data Types). Haben Sie über die Integration dieser Datentypen in die Datenbank nachgedacht und was können Sie dazu sagen?

MT: – Gute Frage! CRDT macht bei Konflikten beim Schreiben Sinn: in MongoDB – ein Single Master.

Frage: – Ich habe eine Frage von den DevOps. In der realen Welt gibt es solche heiklen Situationen, in denen ein byzantinischer Fehler auftritt und böse Menschen innerhalb des geschützten Bereichs anfangen, in das Protokoll einzugreifen und auf spezielle Weise manipulierte Pakete zu senden?

MT: – Böse Menschen innerhalb des Bereichs sind wie ein Trojanisches Pferd! Böse Menschen innerhalb des Bereichs können viele schlechte Dinge tun.

Frage: – Es ist offensichtlich, dass es nicht richtig ist, im Server ein Loch zu lassen, durch das man einen Zoo von Elefanten schieben und den gesamten Cluster für immer abstürzen lassen kann… Das würde Zeit für eine manuelle Wiederherstellung erfordern… Das ist, milde gesagt, nicht in Ordnung. Auf der anderen Seite ist es interessant, dass es im wirklichen Leben in der Praxis Situationen gibt, in denen tatsächlich solche internen Angriffe vorkommen?

MT: – Da ich in der realen Welt nicht oft mit Sicherheitsverletzungen konfrontiert bin, kann ich nicht sagen – vielleicht kommen sie vor. Aber wenn wir über die Entwicklerphilosophie sprechen, denken wir so: Wir haben einen Perimeter, der die Leute, die für die Sicherheit zuständig sind, absichert – das ist das Schloss, die Mauer; und innerhalb des Bereichs kann man tun, was man will. Es ist klar, dass es Benutzer gibt, die nur schauen können, und solche, die das Verzeichnis löschen können.

Je nach Rechten kann der Schaden, den Benutzer anrichten können, von einer Maus bis zu einem Elefanten reichen. Klar ist, dass ein Benutzer mit vollen Rechten alles tun kann. Ein Benutzer mit eingeschränkten Rechten kann erheblich weniger Schaden anrichten. Insbesondere kann er das System nicht zerstören.

Frage: – Im geschützten Bereich hat jemand unerwartete Protokolle für den Server erstellt, um den Server zu deaktivieren, und falls alles gut geht, sogar den gesamten Cluster... Kann es wirklich so "gut" sein?

MT: – Ich habe noch nie von solchen Dingen gehört. Dass man einen Server auf diese Weise lahmlegen kann, ist kein Geheimnis. Intern mit einem Protokoll, während man ein autorisierter Benutzer ist, der etwas derartiges in eine Nachricht schreiben kann... Eigentlich ist das nicht möglich, weil es trotzdem verifiziert werden muss. Es gibt die Möglichkeit, diese Authentifizierung für Benutzer, die es nicht wollen, zu deaktivieren – das sind dann deren Probleme; sie haben, grob gesagt, selbst die Mauern eingerissen und man könnte einen Elefanten hineinstecken, der alles niedertrampelt... Aber insgesamt könnte man in der Rolle eines Technikers kommen und ihn herausziehen!

Frage: – Danke für den Bericht. Sergey ("Yandex"). In "Mongo" gibt es eine Konstante, die die Anzahl der stimmberechtigten Mitglieder im Replica Set auf 7 (sieben) limitiert. Warum ist das eine Konstante? Warum ist das kein Parameter?

MT: – Im Replica Set haben wir manchmal bis zu 40 Knoten. Dort gibt es immer eine Mehrheit. Ich weiß nicht, welche Version...

Frage: – Im Replica Set kann man auch nicht-stimmberechtigte Mitglieder starten, aber stimmberechtigte maximal 7. Wie geht man in diesem Fall mit einem Ausfall um, wenn unser Replica Set über 3 Rechenzentren verteilt ist? Ein Rechenzentrum kann problemlos ausfallen, und auch eine Maschine kann ausfallen.

MT: – Das ist schon ein bisschen außerhalb des Berichts. Das ist eine allgemeine Frage. Vielleicht kann ich darüber später erzählen.

Ein wenig Werbung 🙂

Danke, dass Sie bei uns bleiben. Gefallen Ihnen unsere Artikel? Möchten Sie mehr interessante Inhalte sehen? Unterstützen Sie uns, indem Sie eine Bestellung aufgeben oder uns Freunden empfehlen, Cloud-VPS für Entwickler ab 4,99 $, ein einzigartiges Äquivalent zu Einsteigerservern, das wir für Sie entwickelt haben: Die ganze Wahrheit über VPS (KVM) E5-2697 v3 (6 Kerne) 10GB DDR4 480GB SSD 1Gbps ab 19 $ oder wie man einen Server richtig teilt? (es sind Optionen mit RAID1 und RAID10 bis zu 24 Kernen und bis zu 40GB DDR4 verfügbar).

Dell R730xd ist im Equinix Tier IV Rechenzentrum in Amsterdam doppelt so günstig? Nur bei uns 2 x Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 TB ab $199 in den Niederlanden! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — ab $99! Lesen Sie, wie man eine Unternehmensinfrastruktur der Klasse C mit Dell R730xd E5-2650 v4-Servern für 9000 Euro im Preis-Leistungs-Verhältnis aufbaut?

Quelle: habr.com