HighLoad++, Michail Tjulenew (MongoDB): Kausale Konsistenz: von der Theorie zur Praxis

Die nächste HighLoad++ Konferenz findet am 6. und 7. April 2020 in St. Petersburg statt.
Details und Tickets über den Link. HighLoad++ Sibirien 2019. Raum „Krasnojarsk“. 25. Juni, 12:00. Abstracts und Präsentation nützlich sein..

Es kommt vor, dass praktische Anforderungen mit der Theorie in Konflikt stehen, wobei wichtige Aspekte für kommerzielle Produkte nicht berücksichtigt werden. In diesem Vortrag wird der Prozess der Auswahl und Kombination verschiedener Ansätze zur Erstellung von Komponenten der Kausalen Konsistenz basierend auf akademischen Forschungsergebnissen unter den Anforderungen eines kommerziellen Produkts vorgestellt. Die Zuhörer erfahren von bestehenden theoretischen Ansätzen zu logischen Uhren, Abhängigkeitsverfolgung, Systemsicherheit, Uhren-Synchronisation und warum MongoDB bei bestimmten Lösungen geblieben ist.

Michail Tjulenew (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 des Prozesses musste ich mit einer Vielzahl akademischer Forschungen vertraut werden, da dieses Feature gut erforscht ist. Es stellte sich heraus, dass kein Artikel den spezifischen Anforderungen entsprach, die in Produktionsumgebungen benötigt werden, aufgrund der sehr speziellen Anforderungen, die wahrscheinlich in jeder Produktionsanwendung vorhanden sind.

Ich werde darüber berichten, wie wir als Verbraucher akademischer Forschung etwas daraus entwickeln, das wir unseren Nutzern als fertiges Produkt präsentieren können, das einfach und sicher zu verwenden ist.

Kausale Konsistenz (Causal Consistency). 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 eine Überraschung für sie organisieren. Er entscheidet sich dafür, sie aus seiner Freundesliste zu entfernen und allen Freunden ein Update im Feed zu senden: „Lasst uns Penny eine Freude machen!“ (Sie ist in Europa, schläft und sieht das alles nicht, weil sie nicht dort ist). Am Ende löscht er diesen Beitrag, entfernt ihn aus dem Feed und stellt den Zugang wieder her, damit sie nichts merkt und es zu keinem Skandal kommt.
Das ist alles wunderbar, aber nehmen wir an, dass das System verteilt ist und die Ereignisse nicht ganz wie geplant ablaufen. Es könnte zum Beispiel passieren, dass Pennys Zugangsbeschränkung nach dem Erscheinen dieses Beitrags erfolgt, wenn die Ereignisse nicht kausal miteinander verbunden sind. Tatsächlich ist dies ein Beispiel dafür, dass kausale Konsistenz benötigt wird, um eine Geschäftsanforderung zu erfüllen (in diesem Fall).

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

Konsistenzmodelle (Consistency Models)

Was ist überhaupt das Konsistenzmodell in Datenbanken? Es sind bestimmte Garantien, die ein verteiltes System hinsichtlich der Daten, die der Kunde empfangen kann, und der Reihenfolge, in der dies geschieht, bietet.

Letztendlich lassen sich alle Konsistenzmodelle darauf zurückführen, wie ähnlich ein verteiltes System einem System ist, das beispielsweise auf einem einzelnen Node auf einem Laptop läuft. Und es stellt sich die Frage, inwieweit ein System, das auf Tausenden von geografisch verteilten 'Nods' arbeitet, dem Laptop ähnelt, bei dem all diese Eigenschaften im Grunde automatisch erfüllt sind.

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

Das Strong-Modell

Das erste Modell ist das Strong (oder auch Linearity, wie es oft genannt wird). Dies ist ein Konsistenzmodell, das garantiert, dass jede Änderung, sobald die Bestätigung erfolgt, dass sie stattgefunden hat, für alle Benutzer des Systems sichtbar wird.

Dies stellt eine globale Ordnung aller Ereignisse in der Datenbank her. Es ist eine sehr mächtige Konsistenz-Eigenschaft, aber auch kostspielig. Dennoch wird sie gut unterstützt. Es ist einfach sehr teuer und langsam – weshalb sie selten genutzt wird. Dies wird als Erreichbarkeit bezeichnet.

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

Kausal

Das nächste ist kausal, das ist genau das, worüber ich gesprochen habe. Zwischen starker und kausaler Konsistenz gibt es noch einige Unterebenen, die ich nicht ansprechen werde, aber sie führen alle zur kausalen Konsistenz. Dies ist ein wichtiges Modell, weil es das stärkste von allen Modellen ist, die stärkste Konsistenz in Anwesenheit von Netzwerken oder Partitionen.

Kausale Konsistenzen sind im Wesentlichen Situationen, in denen Ereignisse durch eine Ursache-Wirkung-Beziehung verbunden sind. Häufig werden sie aus Sicht des Kunden als 'Lesen der eigenen Rechte' wahrgenommen. Wenn ein Kunde bestimmte Werte beobachtet hat, kann er die Werte aus der Vergangenheit nicht mehr sehen. Er beginnt bereits, präfixierte Lesungen zu sehen. Das alles läuft auf dasselbe hinaus.
Causals als Konsistenzmodell – eine teilweise Ordnung von Ereignissen auf dem Server, bei der Ereignisse von allen Clients in derselben Reihenfolge beobachtet werden. In diesem Fall – Leonard und Penny.

Eventual

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

In diesem Moment gibt es keine definitive Aussage, sonst würde es zu einer External Consistency – eine ganz andere Geschichte. Dennoch ist dies ein sehr populäres Modell, das am weitesten verbreitet ist. Standardmäßig verwenden alle Benutzer verteilter Systeme genau die Eventual Consistency.

Ich möchte einige vergleichende Beispiele anführen:

Was bedeuten diese Pfeile?

• Latenz. Wenn die Konsistenzstärke erhöht wird, wird sie aus nachvollziehbaren Gründen größer: Es müssen mehr Einträge erstellt und Bestätigungen von allen Hosts und Knoten im Cluster eingeholt werden, dass die Daten dort bereits vorhanden sind. Entsprechend ist die Eventual Consistency die schnellste Antwort, da man in der Regel sogar im Speicher committen kann und dies grundsätzlich ausreichend ist.
• Verfügbarkeit. Wenn man dies als die Fähigkeit des Systems versteht, auf Anfragen zu antworten, trotz Netzwerkunterbrechungen, Partitionierungen oder anderer Ausfälle – erhöht sich die Fehlertoleranz bei einer reduzierten Konsistenzmodell, da es ausreicht, dass ein Host aktiv bleibt und dabei bestimmte Daten liefert. Eventual Consistency garantiert überhaupt nichts bezüglich der Daten – es kann alles Mögliche sein.
• Anomalien. Dabei steigt natürlich die Anzahl der Anomalien. Bei starker Konsistenz sollte es diese fast gar nicht geben, während sie bei eventueller Konsistenz beliebig auftreten können. Die Frage ist: Warum entscheiden sich Menschen für eventuelle Konsistenz, wenn diese Anomalien enthält? Die Antwort liegt darin, dass Modelle der eventuellen Konsistenz anwendbar sind, und Anomalien treten zum Beispiel nur für kurze Zeit auf; es besteht die Möglichkeit, einen Master für Lesevorgänge zu verwenden und mehr oder weniger konsistente Daten zu lesen; oft gibt es die Möglichkeit, starke Konsistenzmodelle zu nutzen. Praktisch funktioniert das, und die Anzahl der Anomalien ist oft zeitlich begrenzt.

CAP-Theorem

Wenn Sie die Worte Konsistenz und Verfügbarkeit hören, was kommt Ihnen in den Sinn? Richtig – das CAP-Theorem! Ich möchte jetzt einen Mythos entkräften… Es bin nicht ich, sondern Martin Kleppmann, der einen großartigen Artikel und ein großartiges Buch geschrieben hat.

Der CAP-Satz ist ein Prinzip, das in den 2000er Jahren formuliert wurde. Es besagt, dass Konsistenz, Verfügbarkeit und Partitionierung: wähle zwei, und du kannst nicht alle drei auswählen. Ursprünglich war es ein Konzept. Einige Jahre später wurde es von Gilbert und Lynch als Theorem bewiesen. Danach wurde es als Mantra verwendet – Systeme wurden in CA, CP, AP usw. unterteilt.

Dieses Theorem wurde tatsächlich für folgende Fälle bewiesen … Zunächst wurde Verfügbarkeit nicht als kontinuierlicher Wert von null bis hundert betrachtet (0 – das System ist „tot“, 100 – es reagiert schnell; so haben wir es gewöhnt zu betrachten), sondern als eine Eigenschaft des Algorithmus, die garantiert, dass er bei allen Ausführungen Daten zurückgibt.

Im Zusammenhang mit der Antwortzeit wird überhaupt kein Wort verloren! Es gibt einen Algorithmus, der Daten in 100 Jahren zurückgibt – ein vollkommen verfügbarer Algorithmus, der Teil des CAP-Satzes ist.
Zweitens wurde das Theorem für Änderungen bei Werten desselben Schlüssels bewiesen, wobei diese Änderungen eine anpassbare Linie darstellen. Das bedeutet, dass sie in der Praxis kaum verwendet werden, da andere Modelle wie Eventual Consistency oder Strong Consistency praktizierter sein könnten.

Warum das Ganze? Weil der CAP-Satz in der Form, in der er bewiesen wurde, praktisch nicht anwendbar ist und selten genutzt wird. In theoretischer Form schränkt er auf gewisse Weise ein. Es ergibt sich ein Prinzip, das intuitiv wahr ist, aber nicht wirklich bewiesen wurde.

Kausale Konsistenz – das stärkste Modell

Was derzeit geschieht, ist, dass man alle drei Dinge erhalten kann: Konsistenz und Verfügbarkeit können auch bei Partitionen sichergestellt werden. Insbesondere die kausale Konsistenz ist das stärkste Konsistenzmodell, das auch bei Partitionen (Netzwerkausfällen) weiterhin funktioniert. Daher ist es von großem Interesse für uns, und deshalb haben wir uns damit beschäftigt.

Es vereinfacht zunächst die Arbeit der Anwendungsentwickler. Insbesondere durch die umfangreiche Unterstützung seitens des Servers: Wenn alle Transaktionen eines Clients garantiert in derselben Reihenfolge beim anderen Client ankommen. Zweitens hält es auch Partitionen stand.

Die interne Funktionsweise von MongoDB

Angesichts des Mittagessens begeben wir uns in die Küche. Ich werde das Systemmodell erläutern, insbesondere was MongoDB ist, für diejenigen, die zum ersten Mal von dieser Datenbank hören.

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

Sharding in MongoDB (eine nicht-relationale Datenbank) führt eine automatische Lastenverteilung durch, das heißt, jede Dokumentensammlung (oder „Tabelle“ im Sinne relationaler Daten) wird in Fragmente unterteilt, und der Server verschiebt diese automatisch zwischen den Shards.

Der Query Router, der die Anfragen verteilt, agiert für den Client als ein gewisser 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 Einträge entgegennehmen, die die Schlüssel unterstützen, die er in sich hält. Multi-Master-Write ist nicht möglich.

Wir haben Version 4.2 veröffentlicht – darin sind neue interessante Funktionen hinzugekommen. Insbesondere ist Lucene integriert – eine durchführbare Java-Suchfunktion direkt in MongoDB, wodurch die Suche über Lucene, ähnlich wie in Elasticsearch, möglich geworden ist.

Wir haben ein neues Produkt geschaffen – Charts, das ebenfalls auf „Atlas“ verfügbar ist (unser eigener Cloud „Mongo“). Es gibt ein Free Tier – man kann damit experimentieren. Mir haben die Charts sehr gefallen – die Datenvisualisierung ist äußerst intuitiv.

Causal Consistency

Ich habe etwa 230 Artikel gezählt, die zu diesem Thema von Leslie Lampert veröffentlicht wurden. Jetzt erinnere ich mich und kann Ihnen einige Teile dieser Materialien übermitteln.

Alles begann mit einem Artikel von Leslie Lampert, der in den 1970er Jahren geschrieben wurde. Wie Sie sehen, gibt es immer noch laufende Forschungen zu diesem Thema. Momentan erfährt Causal Consistency aufgrund der Entwicklungen in verteilten Systemen großes Interesse.

Einschränkungen

Welche Einschränkungen gibt es? Das ist tatsächlich einer der Hauptpunkte, denn die Einschränkungen, die Produktion Systeme auferlegen, unterscheiden sich stark von den Einschränkungen in akademischen Artikeln. Oft sind sie ziemlich künstlich.

• Erstens: „MongoDB“ ist ein Single-Master-System, wie ich bereits erwähnt 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 offensichtlich einschränken.
• Wir bieten Cloud-Lösungen an, aber wir glauben, dass Benutzer die Möglichkeit haben sollten, die Software herunterzuladen, sie auf ihrem Laptop auszuführen und dass alles einwandfrei funktioniert.
• Wir gehen davon aus, dass Research selten genutzt wird: Externe Kunden können tun, was sie wollen. MongoDB ist Open Source, was bedeutet, dass Kunden die Möglichkeit haben, es entsprechend ihrer Bedürfnisse zu verändern. Wir erwarten, dass es zu komplexen Situationen kommen kann.
• Für externe Kunden außerhalb des Perimeters besteht eine wichtige Einschränkung: Wenn diese Funktion deaktiviert ist, sollten keine Leistungsbeeinträchtigungen sichtbar sein.
• Ein weiterer Punkt – eher unkonventionell: die Kompatibilität zwischen alten und neuen Versionen. Alte Treiber müssen neue Updates unterstützen, und die Datenbank muss alte Treiber unterstützen.

Insgesamt bringt das einige Einschränkungen mit sich.

Komponenten der kausalen Konsistenz

Ich möchte nun einige Komponenten vorstellen. Wenn wir im Allgemeinen Causal Consistency betrachten, können wir verschiedene Bereiche identifizieren. Wir haben aus Arbeiten ausgewählt, die zu einem bestimmten Bereich gehören: Dependency Tracking, die Auswahl der Uhren, wie diese Uhren miteinander synchronisiert werden können, und wie wir die Sicherheit gewährleisten – das ist ein grober Plan, über den ich sprechen werde:

Vollständiges Dependency Tracking (Full Dependency Tracking)

Wozu ist es notwendig? Damit bei der Replikation von Daten – jede Eintragung, jede Datenänderung Informationen darüber enthält, von welchen Änderungen sie abhängt. Die erste und naivste Änderung ist, wenn jede Nachricht, die eine Eintragung enthält, Informationen über die vorherigen Nachrichten enthält:

In diesem Beispiel steht die Nummer in geschweiften Klammern für die Eintragungsnummern. Manchmal werden diese Eintragungen mit Werten sogar ganz übergeben, manchmal auch bestimmte Versionen. Das Wesentliche ist, dass jede Änderung Informationen über die vorherige enthält (dies alles ist implizit enthalten).

Warum haben wir uns entschieden, diesen Ansatz (vollständiges Tracking) nicht zu verwenden? Offensichtlich, weil dieser Ansatz unpraktisch ist: Jede Veränderung in einem sozialen Netzwerk hängt von allen vorherigen Änderungen in diesem sozialen Netzwerk ab, was bedeutet, dass man beispielsweise "Facebook" oder "VKontakte" in jedem Update übermitteln muss. Dennoch gibt es viele Studien zu genau diesem Thema, dem Full Dependency Tracking – dies betrifft presoziale Netzwerke, und für einige Situationen funktioniert es wirklich.

Explizites Abhängigkeits-Tracking

Das nächste ist ein eingeschränkterer Ansatz. Hier wird ebenfalls die Übertragung von Informationen betrachtet, aber nur von den Informationen, die eindeutig abhängen. Was von was abhängt, wird in der Regel bereits von der Anwendung definiert. Wenn Daten repliziert werden, werden bei der Abfrage nur die Antworten ausgegeben, wenn die vorherigen Abhängigkeiten erfüllt sind, das heißt, angezeigt wurden. Das ist das Wesen davon, wie kausale Konsistenz funktioniert.

Sie sieht, dass der Datensatz 5 von den Datensätzen 1, 2, 3, 4 abhängt – folglich wartet sie, bevor der Kunde Zugang zu den Änderungen erhält, die durch Penny's Zugriffsregelung vorgenommen wurden, solange alle vorherigen Änderungen bereits in der Datenbank verarbeitet wurden.

Das ist auch für uns nicht akzeptabel, da es einfach zu viele Informationen gibt, was zu Verzögerungen führen wird. Es gibt einen anderen Ansatz…

Lamport-Uhr (Lamport Clock)

Sie sind sehr alt. Die Lamport-Uhr bedeutet, dass diese Abhängigkeiten in eine skalare Funktion umgewandelt werden, die als Lamport-Uhr bezeichnet 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 dem Prozess momentan bekannt ist, sendet jede Nachricht. Es ist klar, dass Prozesse asynchron sein können und völlig unterschiedliche Zeiten haben. Dennoch gleicht das System durch diesen Nachrichtenaustausch irgendwie die Uhren aus. Was passiert in diesem Fall?

Ich habe den großen Shard halbiert, um es klarer zu machen: Friends können in einem Knoten leben, der ein Stück der Sammlung enthält, während Feed in einem anderen Knoten untergebracht ist, der ebenfalls ein Stück dieser Sammlung enthält. Verstehst du, wie sie nicht in der Warteschlange landen können? Zuerst wird Feed sagen: „Repliziert“, und dann – Friends. Wenn das System keine Garantien bietet, dass Feed nicht angezeigt wird, solange die Abhängigkeiten von Friends in der Friends-Sammlung ebenfalls nicht bereitgestellt sind, stellen wir genau die Situation fest, die ich erwähnt habe.

Du siehst, wie die logische Zeit des Counters bei Feed steigt:

Das Hauptmerkmal dieser Lamport-Uhr und der kausalen Konsistenz (erklärt durch die Lamport-Uhr) ist folgendes: Wenn wir die Ereignisse A und B haben und Ereignis B von Ereignis A abhängt*, 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, d.h. A geschah vor B – dies stellt eine Beziehung dar, die die gesamte Menge der Ereignisse, die überhaupt geschehen sind, teilweise ordnet.

In die entgegengesetzte Richtung ist es falsch. Das ist tatsächlich eine der Hauptnachteile der Lamport-Uhr – partielle Ordnung. Es gibt das Konzept von gleichzeitigen Ereignissen, also Ereignissen, bei denen weder (A geschah vor B) noch (A geschah nach B). Ein Beispiel könnte sein, wenn Leonard jemanden in seine Freundeliste hinzufügt (nicht unbedingt Leonard selbst, sondern beispielsweise Sheldon).
Das ist genau die Eigenschaft, die häufig bei der Arbeit mit Lamport-Uhren verwendet wird: Man schaut sich die Funktion an und zieht daraus den Schluss, dass vielleicht diese Ereignisse voneinander abhängig sind. Denn in eine Richtung ist es tatsächlich so: Wenn LogicalTime A kleiner ist als LogicalTime B, kann B nicht vor A geschehen; ist es größer, dann könnte es sein.

Vektoruhren (Vector Clock)

Die logische Weiterentwicklung der Lamport-Uhr sind die Vektoruhren. Sie unterscheiden sich dadurch, dass jeder Knoten, der hier vorhanden ist, seine eigenen separaten Uhren enthält, die als Vektor übertragen werden.
In diesem Fall sehen Sie, dass der Nullindex des Vektors für den Feed verantwortlich ist, und der erste Index des Vektors für die Freunde (jeder dieser Knoten). Und nun werden sie erhöht: Der Nullindex für den „Feed“ wird bei der Registrierung erhöht – 1, 2, 3:

Was macht Vektoruhren besser? Sie ermöglichen es, nachzuvollziehen, welche Ereignisse gleichzeitig stattfinden und wann sie auf verschiedenen Knoten auftreten. Das ist für ein Sharding-System wie MongoDB äußerst wichtig. Dennoch haben wir uns nicht dafür entschieden, obwohl es eine interessante Lösung ist, die großartig funktioniert und wahrscheinlich auch für uns geeignet wäre…

Wenn wir 10.000 Shards haben, können wir nicht 10.000 Komponenten übertragen, selbst wenn wir komprimieren und uns etwas einfallen lassen – die Nutzlast wird trotzdem um ein Vielfaches geringer sein als das gesamte Volumen dieses Vektors. Daher haben wir widerwillig diesen Ansatz aufgegeben und sind zu einem anderen übergegangen.

Spanner TrueTime. Atomuhren

Ich habe gesagt, dass es eine Geschichte über „Spanner“ geben wird. Das ist eine coole Sache, wirklich aus dem 21. Jahrhundert: Atomuhren, GPS-Synchronisation.

Was ist die Idee? „Spanner“ ist Googles System, das vor kurzem sogar für die Öffentlichkeit zugänglich gemacht 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 Zeitpunkt „eintritt“.

Durch das einfache Speichern in der Datenbank und das Warten einer bestimmten Zeit wird automatisch die Serialisierbarkeit von Ereignissen gewährleistet. Sie verfügen über das stärkste Konsistenzmodell, das man sich vorstellen kann – es ist externe Konsistenz.

* Das ist das Hauptproblem der Lamport-Uhren – sie sind in verteilten Systemen nie synchron. Sie können auseinanderdriften, selbst mit NTP arbeiten sie nicht besonders gut. Die "Spanner"-Uhren haben Atomuhren und Synchronisation, die offenbar im Mikrosekundenbereich funktioniert.

Warum haben wir diese nicht gewählt? Wir setzen nicht voraus, dass unsere Nutzer eingebaute Atomuhren haben. Wenn diese in jedem Laptop verbaut sind, mit einer großartigen GPS-Synchronisation – dann ja… Aber derzeit ist das Beste, was möglich ist, die "Amazon", Basisstationen – für die Enthusiasten… Daher haben wir andere Uhren verwendet.

Hybride Uhren (Hybrid Clock)

Das ist tatsächlich das, was in "MongoDB" tickt, um kausale Konsistenz zu gewährleisten. Was macht sie hybrid? Hybrid ist ein skalarer Wert, aber er besteht aus zwei Komponenten:

• Erstens – die Unix-Epoche (wie viele Sekunden seit dem "Beginn der Computerwelt" vergangen sind).
• Das zweite ist ein gewisser Inkrement, ebenfalls ein 32-Bit unsigned int.

Das ist eigentlich 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, wird dieser Teil mit den Uhren synchronisiert, sodass die Zeit immer mehr oder weniger korrekt ist, und der Inkrement ermöglicht es, Ereignisse zu unterscheiden, die zum gleichen Zeitpunkt aufgetreten sind.

Warum ist das für MongoDB wichtig? Weil es ermöglicht, Backups zu bestimmten Zeitpunkten zu erstellen, also wird das Ereignis mit einer Zeitstempel indiziert. Das ist wichtig, wenn bestimmte Ereignisse benötigt werden; für die Datenbank sind Ereignisse Änderungen, die zu bestimmten Zeitpunkten in der Datenbank erfolgt sind.

Den wichtigsten Grund erkläre ich nur Ihnen (bitte, sagen Sie es niemandem)! Wir haben das so gemacht, weil es so aussieht, dass geordnete, indexierte Daten im MongoDB OpLog gespeichert werden. Das OpLog ist eine Datenstruktur, die alle Änderungen in der Datenbank enthält: Diese gelangen zunächst in das OpLog und werden dann auf die eigentliche Storage angewendet, wenn es sich um replizierte Daten oder Shards handelt.

Das war der Hauptgrund. Es gibt schließlich auch praktische Anforderungen an die Datenbankentwicklung, was bedeutet, dass es einfach sein muss – wenig Code, so wenige defekte Elemente wie möglich, die neu geschrieben und getestet werden müssen. Die Tatsache, dass unsere OpLogs von hybriden Uhren indiziert wurden, hat erheblich geholfen und die richtige Wahl ermöglicht. Das hat sich wirklich ausgezahlt und irgendwie magisch beim ersten Prototypen funktioniert. Es war einfach großartig!

Uhrensynchronisation

Es gibt mehrere Methoden zur Synchronisation, die in der wissenschaftlichen Literatur beschrieben sind. Ich spreche von der Synchronisation, wenn wir zwei unterschiedliche Shards haben. Wenn es ein Replica-Set gibt, ist keine Synchronisation erforderlich: das ist ein "Single-Master"; wir haben ein OpLog, in das alle Änderungen eingehen – in diesem Fall ist alles bereits sequenziell im "OpLog" geordnet. Aber wenn wir zwei verschiedene Shards haben, ist Zeit-Synchronisation hier wichtig. Hier haben die Vektoruhren mehr geholfen! Aber die haben wir nicht.

Die zweite Möglichkeit sind die "Heartbeats". Hier können wir bestimmte Signale austauschen, die in festen Intervallen auftreten. Allerdings sind die "Heartbeats" zu langsam, um die Latenz für unseren Kunden zu gewährleisten.

Echte Zeit ist natürlich eine wunderbare Sache. Aber das ist wahrscheinlich die Zukunft... Obwohl es im "Atlas" bereits möglich ist, gibt es schon schnelle "Amazon"-Zeit-Synchronisierer. Doch diese werden nicht für alle zugänglich sein.

Gossiping bedeutet, dass alle Nachrichten Zeitstempel enthalten. Das ist ungefähr das, was wir verwenden. Jede Nachricht zwischen den Knoten, den Treibern, dem Router und den Datenknoten - alles für "MongoDB" - sind Elemente, Komponenten der Datenbank, die Uhren beinhalten, die ticken. Überall gibt es Werte für hybridisierte Zeit, diese werden übertragen. 64 Bits? Das lässt sich machen.

Wie funktioniert das alles zusammen?

Hier betrachte ich ein Replikat-Set, um es etwas einfacher zu machen. Es gibt einen Primär- und einen Sekundärknoten. Der Sekundärknoten führt die Replikation durch und ist nicht immer vollständig mit dem Primärknoten synchronisiert.

Es erfolgt ein Insert in die „Primärdaten“ mit einem bestimmten Zeitwert. Dieses Insert erhöht den internen Zähler um 11, wenn dies das Maximum ist. Andernfalls wird es die Zeitwerte überprüfen und sich nach den Stunden synchronisieren, wenn die Stundenwerte größer sind. Dies ermöglicht eine zeitliche Sortierung.

Nachdem er den Eintrag vornimmt, gibt es einen wichtigen Moment. Die Uhren in „MongoDB“ werden nur im Falle eines Eintrags im „Oplog“ inkrementiert. Dies ist das Ereignis, das den Zustand des Systems verändert. In allen klassischen Artikeln wird ein Ereignis als das Eintreffen einer Nachricht in einem Knoten betrachtet: eine Nachricht ist angekommen – das bedeutet, das System hat seinen Zustand geändert.

Dies hängt damit zusammen, dass es bei der Untersuchung nicht ganz klar ist, wie diese Nachricht interpretiert werden wird. Wir wissen genau, dass wenn sie nicht im „Oplog“ reflektiert ist, sie auf keine Weise interpretiert werden kann, und die Systemzustandsänderung nur durch einen Eintrag im „Oplog“ erfolgt. Das vereinfacht alles für uns: sowohl das Modell ist vereinfacht, als auch es ermöglicht eine Sortierung innerhalb eines Replikat-Sets und viele andere nützliche Dinge.

Es wird ein Wert zurückgegeben, der bereits im "OpLog" gespeichert ist – wir wissen, dass dieser Wert im "OpLog" bereits vorhanden ist und seine Zeit 12 Uhr beträgt. Jetzt sagen wir, dass das Lesen von einem anderen Node (Secondary) beginnt, und er überträgt bereits afterClusterTime in der Nachricht. Er sagt: „Ich benötige alles, was mindestens nach 12 Uhr oder zur gleichen Zeit passiert ist“ (siehe Abbildung oben).

Das nennt man Causal and consistent (CAT). Es gibt ein Konzept in der Theorie, das besagt, 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 zu dem Zeitpunkt 12 Schlüssel beobachtet wurde.

Hier ist momentan nichts, da dies sich so verhält, als ob die Situation simuliert wird, in der Secondary Daten von Primary replizieren muss. Er wartet… Und hier sind die Daten angekommen – die Werte werden zurückgegeben.

So funktioniert das ungefähr. Fast.

Was bedeutet "fast schon"? Stellen wir uns vor, es gibt einen Menschen, der verstanden hat, wie das alles funktioniert. Er hat erkannt, dass jedes Mal, wenn ein ClusterTime auftritt, die internen logischen Uhren aktualisiert werden, und dann wird der nächste Eintrag um eins erhöht. Diese Funktion umfasst 20 Zeilen. Angenommen, dieser Mensch überträgt die größtmögliche 64-Bit-Zahl minus eins.

Warum „minus eins“? Weil die internen Uhren in diesen Wert eingepasst werden (offensichtlich ist dies der größte mögliche Wert, der über der aktuellen Zeit liegt), dann erfolgt der Eintrag in das „Op-Log“, und die Uhren werden um eins erhöht – und dann haben wir den wirklich maximalen Wert (da sind einfach alle Einsen, weiter geht’s nicht, unsignierte Integer).

Es ist klar, dass das System nach diesem Vorgang absolut für nichts mehr verfügbar ist. Es kann nur entladen und gereinigt werden – das erfordert viel manuelle Arbeit. Vollständige Verfügbarkeit:

Außerdem, falls dies irgendwohin repliziert wird, stürzt der gesamte Cluster einfach ab. Eine absolut inakzeptable Situation, die jeder Mensch sehr schnell und einfach herbeiführen kann! Daher haben wir diesen Punkt als einen der wichtigsten betrachtet. Wie kann man das verhindern?

Unser Weg ist es, clusterTime zu unterschreiben

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

Die Signatur wird mit einem Schlüssel generiert, der in der Datenbank innerhalb eines geschützten Bereichs gespeichert ist; der Schlüssel selbst wird generiert und aktualisiert (Benutzer sehen davon nichts). Ein Hash wird erzeugt, und jede Nachricht wird beim Erstellen signiert und beim Empfang validiert.
Vielleicht stellt sich die Frage: "Wie sehr verlangsamt das alles?" Ich habe gesagt, dass es schnell funktionieren sollte, insbesondere ohne diese Funktion.

Was bedeutet es, in diesem Fall nach kausaler Konsistenz zu arbeiten? Das bedeutet, den afterClusterTime-Parameter anzuzeigen. Ansonsten werden die Werte in jedem Fall übermittelt. Gossiping arbeitet seit Version 3.6 immer.

Wenn wir die ständige Generierung von Signaturen beibehalten, wird dies das System sogar ohne die Funktion verlangsamen, was nicht unseren Ansätzen und Anforderungen entspricht. Und was haben wir getan?

Mach das schnell!

Es ist eine ziemlich einfache Sache, aber der Trick ist interessant – ich teile es, vielleicht interessiert es jemand.
Wir haben einen Hash, in dem die signierten Daten gespeichert sind. Alle Daten laufen durch den Cache. Der Cache signiert nicht konkret die Zeit, sondern einen Bereich. Wenn ein Wert eintrifft, generieren wir den Bereich, maskieren die letzten 16 Bit, und dieses Ergebnis signieren wir:

Durch diese Signatur beschleunigen wir das System (theoretisch) um das 65.000-Fache. Es funktioniert hervorragend: bei Experimenten wurde die Zeit für den sequentiellen Update-Prozess tatsächlich um das 10.000-Fache verkürzt. Klar, wenn sie unregelmäßig sind, klappt es nicht. Aber in den meisten praktischen Fällen funktioniert es. Die Kombination aus der Signatur des Bereichs zusammen mit der Hauptsignatur hat ein Sicherheitsproblem gelöst.

Was haben wir gelernt?

Lektionen, die wir daraus gezogen haben:

• Es ist wichtig, Materialien, Geschichten und Artikel zu lesen, denn es gibt viel Interessantes zu entdecken. Wenn wir an einem Feature arbeiten (insbesondere jetzt, wo wir Transaktionen verarbeitet haben usw.), müssen wir lesen und verstehen. Das kostet Zeit, ist aber tatsächlich sehr hilfreich, weil es klar macht, wo wir stehen. Wir haben anscheinend nichts Neues erfunden – wir haben einfach die Zutaten genommen.

  Generell gibt es einen gewissen Unterschied im Denken, wenn es um akademische Konferenzen geht (wie zum Beispiel die "Sigmon"), wo alle auf neue Ideen fokussiert sind. Was ist die Neuheit unseres Algorithmus? Hier gibt es nicht viel Neues. Die Neuheit liegt eher darin, wie wir bestehende Ansätze miteinander kombiniert haben. Daher ist es wichtig, die Klassiker zu lesen, beginnend mit Lamport.

• In der Produktion gelten völlig andere Anforderungen. Ich bin mir sicher, dass viele von Ihnen nicht mit "sphärischen" Datenbanken in einem abstrakten Vakuum konfrontiert sind, sondern mit normalen, realen Dingen, die Probleme in Bezug auf Verfügbarkeit, Latenz und Ausfallsicherheit aufweisen.
• Das Letzte ist, dass wir verschiedene Ideen betrachten und mehrere grundsätzlich verschiedene Artikel zu einem Ansatz kombiniert haben. Die Idee des Signierens stammt beispielsweise aus einem Artikel, der das Paxos-Protokoll betrachtete, welches für nicht-byzantinische Fehler innerhalb des Autorisierungsprotokolls gedacht ist, während es für byzantinische Fehler außerhalb des Autorisierungsprotokolls gilt... Insgesamt ist das genau das, was wir schließlich umgesetzt haben.

  Hier gibt es absolut nichts Neues! Aber sobald wir alles zusammen mischen… Es wäre so, als würde man sagen, dass das Rezept für Olivier-Salat Unsinn ist, nur weil Eier, Mayonnaise und Gurken bereits erfunden wurden… Es ist etwa die gleiche Geschichte.

Damit schließe ich. Vielen Dank!

Fragen

Frage aus dem Publikum (im Folgenden – F): – Vielen Dank, Michail, für den Vortrag! Das Thema Zeit ist interessant. Sie verwenden Gossiping. Sie sagten, 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, auch viele Query-Planer, und auch viele Shards… Was passiert mit dem System, wenn es plötzlich zu einem Ungleichgewicht kommt: jemand denkt, er ist eine Minute voraus, jemand anderer – eine Minute hinterher? Wo landen wir?

MT: – Das ist tatsächlich eine großartige Frage! Ich wollte gerade über die Shards sprechen. Wenn ich die Frage richtig verstehe, haben wir die Situation: Es gibt Shard 1 und Shard 2, das Lesen erfolgt von diesen beiden Shards – sie haben Unterschiede, interagieren nicht miteinander, weil die Zeiten, die sie kennen, unterschiedlich sind, insbesondere die Zeit, die in ihren Logbüchern existiert.
Angenommen, shard 1 hat eine Million Einträge gemacht, shard 2 hingegen gar nichts, und die Anfrage kam an zwei shards. Und shard 1 hat eine afterClusterTime von über einer Million. In einem solchen Fall, wie ich erklärt habe, wird shard 2 niemals antworten.

Frage: – Ich wollte wissen, wie sie sich synchronisieren und eine logische Zeit wählen?

MT: – Das Synchronisieren ist ganz einfach. Ein shard, wenn er nach afterClusterTime keine Zeit im "OpLog" findet, initiiert no approved. Das bedeutet, dass er seine Zeit auf diesen Wert anhebt. Das zeigt an, dass es keine Ereignisse gibt, die dieser Anfrage entsprechen. Er erstellt dieses Ereignis künstlich und wird dadurch kausal konsistent.

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

MT: – Der shard ist so strukturiert, dass diese bereits nicht mehr eintreffen, da es sich um einen Single-Master handelt. Wenn er bereits geschrieben hat, werden sie nicht mehr eintreffen, sondern kommen danach. Es kann nicht passieren, dass irgendwo etwas stecken bleibt, er dann no write macht und diese Ereignisse eintreffen – und die kausale Konsistenz gestört wird. Wenn er no write macht, müssen alle noch weiter eintreffen (er wird auf sie warten).

Frage: – Ich habe einige Fragen zu Warteschlangen. Kausale Konsistenz setzt voraus, dass es eine bestimmte Reihenfolge von Aktionen gibt, die ausgeführt werden müssen. Was passiert, wenn ein Paket verloren geht? Der 10. und 11. sind gegangen, aber der 12. fehlt, während alle anderen darauf warten, dass er bearbeitet wird. Und plötzlich stirbt unsere Maschine, wir können nichts mehr tun. Gibt es eine maximale Länge der Warteschlange, die sich aufstaut, bevor sie bearbeitet wird? Welche schwerwiegenden Fehler treten auf, wenn ein Zustand verloren geht? Besonders wenn wir aufzeichnen, dass es einen vorherigen Zustand gibt, von dem wir ausgehen sollten? Aber darauf haben wir uns nicht gestützt!

MT: – Auch eine großartige 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 die Aufzeichnung nicht im Quorum ist oder wenn das Lesen nicht quorum ist (es kann ebenfalls Müll auftauchen).
Bezüglich der kausalen Konsistenz haben wir eine umfangreiche experimentelle Überprüfung durchgeführt, deren Ergebnis zeigte, dass bei nicht quorum konformen Schreib- und Lesevorgängen Verstöße gegen die kausale Konsistenz auftreten. Genau das, was Sie sagen!

Unser Tipp: Verwenden Sie mindestens ein Quorum-Lesen bei der Nutzung von Kausal-Konsistenz. In diesem Fall gehen keine Daten verloren, selbst wenn das Quorum-Write verloren geht... Dies ist eine orthogonale Situation: Wenn der Benutzer nicht möchte, dass Daten verloren gehen, muss er Quorum-Write verwenden. Kausal-Konsistenz garantiert nicht die Haltbarkeit. Die Garantie für die Haltbarkeit bieten Replikation und die mit der Replikation verbundene Technik.

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

MT: – Lass mich das klarstellen. Ein Shard (d. h. eine horizontale Partition) hat immer einen Primary. In einem Shard kann es einen „Master“ und Replikate geben. Aber der Shard muss immer das Schreiben unterstützen, da er einen bestimmten Bereich abdecken muss (im Shard befindet sich der Primary).

Frage: – Bedeutet das, dass alles rein vom „Master“ abhängt? Wird immer die „Master“-Zeit verwendet?

MT: – Ja. Man kann bildlich sagen: Die Uhren ticken, wenn ein Write im „Master“ erfolgt, im „OpLog“.

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

MT: – Man muss überhaupt nichts wissen! Wenn es darum geht, wie es beim Kunden funktioniert: Der Kunde muss, wenn er Causal Consistency nutzen möchte, eine Sitzung öffnen. In dieser Sitzung sind sowohl die Transaktionen als auch die Rechte enthalten... Eine Sitzung ist eine Anordnung der logischen Ereignisse, die mit dem Kunden stattfinden.

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

Der Kunde muss absolut nichts wissen! Es ist für ihn vollkommen intransparent. Wenn Menschen diese Funktionen nutzen, was erlaubt das? Erstens kann man sekundäre Systeme sicher lesen: Man kann auf dem Primärsystem schreiben und von geografisch replizierten sekundären Systemen lesen und sich sicher sein, dass es funktioniert. Gleichzeitig können die Sitzungen, die auf dem Primärsystem aufgezeichnet wurden, auch auf das Sekundärsystem übertragen werden, das heißt, man kann nicht nur eine Sitzung, sondern mehrere nutzen.

Frage: – Mit dem Thema der eventualen Konsistenz ist eng der neue Bereich der Informatik – die Datentypen CRDT (konflikfreig replicierte Datentypen) verbunden. Haben Sie eine Integration dieser Datentypen in die Datenbank in Betracht gezogen und was können Sie dazu sagen?

MT: – Gute Frage! CRDT macht Sinn bei Schreibkonflikten: in MongoDB – ein einzelner Master.

Frage: – Ich habe eine Frage von den DevOps. In der heutigen Welt gibt es manchmal solche hinterhältigen Situationen, in denen ein byzantinischer Fehler auftritt und böse Leute innerhalb des geschützten Perimeters beginnen, sich in das Protokoll einzuhacken, indem sie speziell gestaltete Pakete senden?

MT: – Böse Leute im Inneren des Perimeters sind wie ein trojanisches Pferd! Böse Leute innerhalb des Perimeters können viele schädliche Dinge tun.

Frage: – Es ist klar, dass es nicht richtig ist, im Server eine Art Lücke zu lassen, durch die man einen Elefantenpark hindurchschieben und den gesamten Cluster für immer zum Absturz bringen kann... Es wird Zeit brauchen, um manuell wiederherzustellen... Das ist, gelinde gesagt, nicht korrekt. Andererseits ist es interessant zu wissen: Kommt es in der Realität, in der Praxis, tatsächlich zu solchen internen Angriffen?

MT: – Da ich in der realen Welt selten mit Sicherheitsverletzungen konfrontiert werde, kann ich nicht sagen, ob sie tatsächlich passieren. Aber was die Entwicklerphilosophie angeht, so denken wir folgendermaßen: Wir haben einen Umfang, der die Leute, die für die Sicherheit zuständig sind, schützt – das ist das Schloss, die Mauer; innerhalb dieses Umfangs kann man alles Mögliche tun. Es ist klar, dass es Benutzer gibt, die nur ansehen können, und solche, die die Berechtigung haben, Verzeichnisse zu löschen.

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

Frage: – In einem geschützten Umfang wird manchmal versucht, unerwartete Protokolle für den Server zu erstellen, um den Server lahmzulegen und, wenn man Glück hat, den gesamten Cluster... Ist es wirklich so "gut"?

MT: – Ich habe noch nie von solchen Dingen gehört. Dass man so einen Server zum Absturz bringen kann, ist kein Geheimnis. Innerhalb des Protokolls, als autorisierter Nutzer, der eine Nachricht schreiben kann, ist das jedoch nicht möglich, da es trotzdem verifiziert wird. Es besteht die Möglichkeit, diese Authentifizierung für Nutzer abzuschalten, die es nicht wollen – das sind dann ihre Probleme; sie haben, grob gesagt, selbst die Mauern eingerissen und können einen Elefanten hineinstecken, der alles zertrampelt… Man könnte sich auch als Techniker verkleiden, vorbeikommen und ihn herausziehen!

Frage: – Vielen Dank für den Vortrag. Sergej ("Yandex"). In MongoDB gibt es eine Konstante, die die Anzahl der abstimmenden Mitglieder im Replica Set limitiert, und diese Konstante beträgt 7. Warum ist das eine Konstante? Warum ist das kein Parameter?

MT: – In einem Replica Set haben wir auch mal 40 Knoten. Dort gibt es immer eine Mehrheit. Ich weiß nicht, welche Version…

Frage: – Im Replica Set kann man nicht abstimmende Mitglieder betreiben, aber abstimmende – maximal 7. Wie gehen wir in diesem Fall mit einem Ausfall um, wenn unser Replica Set auf 3 Rechenzentren verteilt ist? Ein Rechenzentrum kann problemlos ausfallen, und ein weiteres Gerät könnte ebenfalls ausfallen.

MT: – Das liegt schon etwas außerhalb des Vortrags. Das ist eine allgemeine Frage. Vielleicht kann ich später darüber 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 Ihren Freunden empfehlen. Cloud-VPS für Entwickler ab 4,99 $, eine einzigartige Alternative zu Einsteiger-Servern, die wir für Sie entwickelt haben: Alles über VPS (KVM) E5-2697 v3 (6 Kerne) 10GB DDR4 480GB SSD 1Gbps ab 19 $ oder wie man einen Server richtig teilt? (Verfügbar sind Optionen mit RAID1 und RAID10, bis zu 24 Kerne und bis zu 40GB DDR4).

Dell R730xd im Equinix Tier IV Rechenzentrum in Amsterdam zum halben Preis? 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 darüber Wie man eine Unternehmenskosten-Infrastruktur mit Dell R730xd E5-2650 v4-Servern für ein paar Euro aufbaut?

Quelle: habr.com