In verteilten Systemen gibt es eine Reihe grundlegender Probleme: effiziente verteilte Transaktionen, genau einmalige Datenverarbeitung, genaue Synchronisation der physischen Uhren. Um das letztere Problem zu lösen , wurden verschiedene Arten von Logiktakten erfunden .

Trotzdem haben Vektoruhren unangenehme Eigenschaften: Sie führen eine bedingte Abhängigkeit zwischen Ereignissen ein, bei denen sie nicht existieren, und verlieren sie dort, wo sie tatsächlich sind.

Sie können sich jedoch etwas Zuverlässigeres einfallen lassen - Kronos. In diesem Artikel werden wir uns den Ursache-Wirkungs-Beziehungsabrechnungsalgorithmus und seine Anwendung zum Erstellen von Schlüsselwertspeichern mit verteilten Transaktionen ansehen.

Die Probleme

Wie bereits erwähnt, gibt es eine Reihe von Problemen mit der logischen Uhr:

• Nicht existierende Abhängigkeiten entstehen, weil eine logische Uhr eine vollständige Reihenfolge von Ereignissen einführt - das heißt, jedes von zwei Ereignissen kann als bedingt früher und welches bedingt später bezeichnet werden. Der Vertrag ist an Bedingungen geknüpft, da es unmöglich ist, die Beziehung zwischen Ereignissen in der Zeit genau zu bestimmen, auch aufgrund der speziellen Relativitätstheorie.

  
  

• Andererseits berücksichtigt ein Logiktakt nur die Verbindung durch Nachrichten innerhalb des Systems. Wenn zwei Ereignisse miteinander verbunden sind, jedoch außerhalb des Systems, z. B. durch den Benutzer (Hinzufügen von Waren zum Warenkorb in einem Teil des Systems -> Zahlung für die Bestellung), kann die logische Uhr eine solche Beziehung übersehen.

  
  

• Auf logische Uhren kann nicht von außen zugegriffen werden, und es ist auch schwierig, mehrere unabhängige Komponenten (verteiltes Dateisystem, Anforderungsverarbeitungsdienste, Analyse) miteinander zu verbinden.

  
  

Lösung

Ein Artikel von Kronos aus dem Jahr 2014 : Das Design und die Implementierung eines Event Ordering Service schlägt eine Lösung vor - einen eigenständigen Service, der die Ursache-Wirkungs-Beziehungen in Events berücksichtigt.

Die Hauptabstraktion in Kronos ist ein Ereignis, bei dem eine teilweise Ordnung eingeführt wird. Das Kausalitätsverhältnis ist transitiv - das heißt, wenn wir beispielsweise wissen, dass die Erstellung einer Datei ihrer Änderung vorausgeht und die Änderung der Löschung vorausgeht, können wir eine logische Schlussfolgerung ziehen, dass die Erstellung vor dem Löschen erfolgt ist.

Die Mindest-API kann mit den folgenden Methoden definiert werden:

Implementierung

Es ist logisch, dass das System auf einem orientierten Ereignisdiagramm mit einer effektiven Breitensuche zur Überprüfung der Beziehung von Ereignissen, einem Stabilitätsmechanismus im Fehlerfall und einer Speicherbereinigung basiert.

Wie aus der API assign_order akzeptiert die Anforderung assign_order einen Kausalbeziehungstyp: must oder prefer . must entspricht strengen Invarianten - z. B. " _->_ , darf " _->_ nicht angewendet werden, wenn es mit " must Beziehungen" in Konflikt steht. Ein Beispiel für die Verwendung von " prefer ist, dass früher eingegangene Anforderungen besser früher verpackt werden. Dies hat jedoch keinen Einfluss auf die Richtigkeit.

Effektives BFS

In unserem Fall ist das Diagramm möglicherweise groß, aber Ereignisse, für die Überprüfungsanforderungen ausgeführt werden, sind normalerweise geschlossen. Daher müssen Sie BFS in solchen Fällen schneller ausführen.

In der Standardimplementierung ist der längste Ort die Initialisierung des Arrays der besuchten Scheitelpunkte, die immer Zeit benötigt, die der Anzahl der Scheitelpunkte im Diagramm entspricht. Stattdessen können Sie eine Hash-Tabelle verwenden oder andere Tricks anwenden.

Müllabfuhr

Wie Sie der Tabelle acquire_ref können, gibt es zwei weitere Methoden: acquire_ref und release_ref .

In Kronos wird für jedes Ereignis ein Referenzzähler gespeichert. Während einige Dienste das Ereignis verarbeiten oder die Möglichkeit behalten, neue Ereignisse hinzuzufügen, die nach dem aktuellen Ereignis auftreten, wird der Link gespeichert. Wenn diese Notwendigkeit verschwindet, ruft der Dienst release_ref .

Kronos löscht das Ereignis, wenn alle Bedingungen erfüllt sind:

1. Die Anzahl der Links hat Null erreicht
2. Alle Ereignisse davor sind bereits aus dem Diagramm gelöscht.

Dieser Ansatz schränkt mögliche Abfragen nicht ein, spart jedoch Speicher in Kronos.

Anwendungen

Betrachten Sie die Verwendung des Systems am Beispiel der Schlüsselwertspeicherung mit verteilten Transaktionen.

Angenommen, es gibt mehrere Server. Jeder Server ist für eine Reihe von Schlüsseln verantwortlich.

Jede Transaktion entspricht einem Ereignis in Kronos. Für jeden Schlüssel muss der Server die Nummer der letzten Transaktion speichern, an der dieser Schlüssel teilgenommen hat. Der Client erstellt ein Ereignis und sendet seine Nummer an alle Server, deren Schlüssel von dieser Transaktion betroffen sind. Der Server versucht, in Kronos eine Abhängigkeit zwischen der aktuellen Transaktionsnummer und dem vorherigen Ereignis zu erstellen, das für diesen Schlüssel gespeichert wurde. Wenn Sie die Abhängigkeit nicht erstellen können, wird die Transaktion als nicht erfolgreich erkannt (beachten Sie, dass bis jetzt noch keine Interaktion mit den Daten besteht).

Wenn alle Operationen zum Hinzufügen von Abhängigkeiten erfolgreich abgeschlossen wurden, bedeutet dies, dass die Transaktion stattfindet und ausgeführt werden kann. Server erfahren dies vom Client und beginnen, Teile der Transaktion auszuführen.

Beachten Sie, dass solche Transaktionen ACID sind :

• Atomarität : Die Transaktion wird entweder nicht in Kronos oder für die Ausführung auf allen Knoten geplant.
• Konsistenz : automatisch in KV-Repositorys.
• Isolation : Wenn sich zwei Transaktionen gemäß Daten überschneiden, werden sie durch einen Kausalzusammenhang in Kronos verbunden, was bedeutet, dass eine vor der anderen ausgeführt wird.
• Haltbarkeit : Da Kronos sturzsicher ist und davon ausgeht, dass jede Replik des Tresors auch stabil ist, muss nur die Persistenz der Daten ausstehender Transaktionen nachgewiesen werden. Wenn die Transaktion vom Client als erfolgreich markiert wird, der Datensatz jedoch noch nicht auf dem Server abgeschlossen wurde, ist diese Tatsache leicht festzustellen, da der Server auch die abgeschlossenen Teile der Transaktionen verfolgt.

Leistung

Die Implementierung eines solchen KV-Speichers kann tatsächlich effektiv sein. Der ursprüngliche Artikel zitiert Daten, dass die beschriebene Implementierung von KV-Speicher viermal schneller ist als die auf Sperren basierende Transaktion.

Darüber hinaus liegt das System über Kronos im Vergleich zu MongoDB nur 6% zurück, obwohl MongoDB keine verteilten Transaktionen verwendet.

Analyse

Der Betrieb von Kronos hat jedoch mehrere Nachteile.

• Erstens gibt es den Aufwand für den Zugriff auf Kronos - für jede Anforderung ist mindestens ein Anruf erforderlich.
• Kronos wird auch eine einzige Fehlerquelle sein - die Autoren des Artikels bieten keine Möglichkeiten zum Partitionieren des Ereignisdiagramms.
• Es wäre schön, dem System eine Reihe von Methoden hinzuzufügen. Im Beispiel mit KV-Speicher wäre es beispielsweise schön, einen Rückruf zu haben, der den Server über den Status der Transaktion informiert - er wurde erfolgreich mit allen erforderlichen Abhängigkeiten zum Diagramm hinzugefügt - oder umgekehrt konnte die Transaktion nicht abgeschlossen werden.

Das beschriebene System ermöglicht jedoch eine flexible Kontrolle des Kausalzusammenhangs zwischen Ereignissen, wodurch eine vorhersehbare Einhaltung der erforderlichen Invarianten sichergestellt wird.

Fazit

Darüber unterrichten wir an der GoTo School Schüler und Schüler in Richtung verteilter Systeme.

Und es gibt Algorithmen und Anwendungen , Angewandte Programmierung, Bioinformatik und Datenanalyse

Besuchen Sie unsere Herbstschule vom 27. Oktober bis 4. November oder die Winterschule Anfang Januar.

Und wenn Sie kein Schüler oder Schüler mehr sind, kommen Sie, um zu unterrichten .