Fünf Studenten und drei verteilte Schlüsselwertspeicher

Oder wie wir die Client-C ++ - Bibliothek für ZooKeeper, etcd und Consul KV geschrieben haben

In der Welt der verteilten Systeme gibt es eine Reihe typischer Aufgaben: Speichern von Informationen über die Zusammensetzung des Clusters, Verwalten der Konfiguration von Knoten, Erkennen fehlerhafter Knoten, Auswählen eines Leiters und andere . Um diese Probleme zu lösen, wurden spezielle verteilte Systeme geschaffen - Koordinierungsdienste. Jetzt werden wir uns für drei davon interessieren: ZooKeeper, etcd und Consul. Von allen umfangreichen Funktionen von Consul werden wir uns auf Consul KV konzentrieren.



Tatsächlich sind alle diese Systeme fehlertolerante linearisierte Schlüsselwertspeicher. Obwohl ihre Datenmodelle signifikante Unterschiede aufweisen, die wir später diskutieren werden, ermöglichen sie uns, dieselben praktischen Probleme zu lösen. Offensichtlich ist jede Anwendung, die den Koordinierungsdienst verwendet, an eine von ihnen gebunden, was dazu führen kann, dass mehrere Systeme unterstützt werden müssen, die dieselben Aufgaben in einem Rechenzentrum für verschiedene Anwendungen lösen.

Die Idee zur Lösung dieses Problems entstand in einer australischen Beratungsagentur, und wir, ein kleines Team von Studenten, mussten sie umsetzen, worüber ich Ihnen erzählen werde.

Wir konnten eine Bibliothek erstellen, die eine gemeinsame Schnittstelle für die Arbeit mit ZooKeeper, etcd und Consul KV bietet. Die Bibliothek ist in C ++ geschrieben, es ist jedoch geplant, sie in andere Sprachen zu portieren.

Datenmodelle

Um eine gemeinsame Schnittstelle für drei verschiedene Systeme zu entwickeln, müssen Sie verstehen, was sie gemeinsam haben und wie sie sich unterscheiden. Lass es uns richtig machen.

Tierpfleger



Schlüssel sind in einem Baum organisiert und werden als Knoten (znodes) bezeichnet. Dementsprechend können Sie für die Website eine Liste seiner Kinder erhalten. Die Vorgänge zum Erstellen von znode (create) und zum Ändern des Werts (setData) sind getrennt: Nur vorhandene Schlüssel können Werte lesen und ändern. Uhren können an Vorgänge angehängt werden, bei denen die Existenz eines Knotens überprüft, ein Wert gelesen und untergeordnete Elemente abgerufen werden. Watch ist ein einmaliger Auslöser, der ausgelöst wird, wenn sich die Version der entsprechenden Daten auf dem Server ändert. Ephemere Knoten werden verwendet, um Fehler zu erkennen. Sie sind an die Sitzung des Clients angehängt, der sie erstellt hat. Wenn ein Client eine Sitzung schließt oder ZooKeeper nicht mehr über seine Existenz informiert, werden diese Knoten automatisch gelöscht. Es werden einfache Transaktionen unterstützt - eine Reihe von Vorgängen, die entweder alle erfolgreich sind oder fehlschlagen, wenn mindestens einer davon nicht möglich ist.

etcd



Die Entwickler dieses Systems waren eindeutig von ZooKeeper inspiriert und haben daher alles anders gemacht. Die Schlüsselhierarchie ist nicht hier, aber sie bilden eine lexikographisch geordnete Menge. Sie können alle Schlüssel abrufen oder löschen, die zu einem bestimmten Bereich gehören. Eine solche Struktur mag seltsam erscheinen, ist aber tatsächlich sehr ausdrucksstark, und die hierarchische Sichtweise durch sie lässt sich leicht emulieren.

Es gibt keine Standard-Vergleichs- und Set-Operation in etcd, aber es gibt etwas Besseres - Transaktionen. Natürlich sind sie in allen drei Systemen vorhanden, aber in etcd sind Transaktionen besonders gut. Sie bestehen aus drei Blöcken: Prüfung, Erfolg, Misserfolg. Der erste Block enthält eine Reihe von Bedingungen, die zweite und dritte Operation. Eine Transaktion wird atomar ausgeführt. Wenn alle Bedingungen erfüllt sind, wird der Erfolgsblock ausgeführt, andernfalls - Fehler. In API-Version 3.3 können Erfolgs- und Fehlerblöcke verschachtelte Transaktionen enthalten. Das heißt, es ist möglich, bedingte Konstruktionen einer nahezu willkürlichen Verschachtelungsebene atomar auszuführen. Weitere Informationen zu den vorhandenen Überprüfungen und Vorgängen finden Sie in der Dokumentation .

Auch hier gibt es Uhren, die jedoch etwas komplexer und wiederverwendbarer sind. Das heißt, nachdem Sie watch auf einer Reihe von Tasten installiert haben, erhalten Sie alle Updates in diesem Bereich, bis Sie die Uhr abbrechen, und nicht nur die erste. In etcd entsprechen Leases ZooKeeper-Client-Sitzungen.

Konsul KV

Es gibt auch keine strenge hierarchische Struktur, aber Consul kann das Erscheinungsbild erstellen, das es gibt: Sie können alle Schlüssel mit dem angegebenen Präfix empfangen und löschen, dh mit dem "Teilbaum" des Schlüssels arbeiten. Solche Abfragen werden als rekursiv bezeichnet. Darüber hinaus kann Consul nur Schlüssel auswählen, die nicht das angegebene Zeichen nach dem Präfix enthalten, was dem Empfang sofortiger „Kinder“ entspricht. Es ist jedoch zu beachten, dass dies genau das Erscheinungsbild einer hierarchischen Struktur ist: Es ist durchaus möglich, einen Schlüssel zu erstellen, wenn sein übergeordnetes Element nicht vorhanden ist, oder einen Schlüssel mit untergeordneten Schlüsseln zu löschen, während die untergeordneten Elemente weiterhin im System gespeichert werden.


Anstelle von Uhren werden in Consul HTTP-Anforderungen blockiert. Im Wesentlichen handelt es sich hierbei um gewöhnliche Aufrufe der Datenlesemethode, für die zusammen mit anderen Parametern die letzte bekannte Version der Daten angegeben wird. Wenn die aktuelle Version der entsprechenden Daten auf dem Server größer als die angegebene ist, wird die Antwort sofort zurückgegeben, andernfalls, wenn sich der Wert ändert. Es gibt hier auch Sitzungen, die jederzeit an Schlüssel angehängt werden können. Es ist erwähnenswert, dass es im Gegensatz zu etcd und ZooKeeper, wo das Löschen von Sitzungen zum Entfernen verwandter Schlüssel führt, einen Modus gibt, in dem die Sitzung einfach von diesen getrennt wird. Transaktionen sind verfügbar, ohne Verzweigung, aber mit allen Arten von Prüfungen.

Bring alles zusammen

Das strengste Datenmodell ist ZooKeeper. In etcd verfügbare Expressive Range-Anforderungen können weder in ZooKeeper noch in Consul effizient emuliert werden. Beim Versuch, das Beste aus allen Diensten herauszuholen, haben wir eine Schnittstelle erhalten, die fast der ZooKeeper-Schnittstelle entspricht, mit den folgenden wesentlichen Ausnahmen:

• Sequenz-, Container- und TTL-Knoten werden nicht unterstützt
• ACLs werden nicht unterstützt
• Die set-Methode erstellt einen Schlüssel, wenn dieser nicht vorhanden war (in ZK gibt setData in diesem Fall einen Fehler zurück).
• set- und cas-Methoden sind getrennt (in ZK sind sie im Wesentlichen dasselbe)
• Die Löschmethode löscht den Scheitelpunkt zusammen mit dem Teilbaum (in ZK gibt delete einen Fehler zurück, wenn der Scheitelpunkt untergeordnete Elemente hat).
• Für jeden Schlüssel gibt es nur eine Version - die Version des Werts (in ZK gibt es drei davon )

Die Ablehnung von sequentiellen Knoten beruht auf der Tatsache, dass in etcd und Consul keine integrierte Unterstützung für sie vorhanden ist und dass sie zusätzlich zur resultierenden Bibliotheksschnittstelle vom Benutzer einfach implementiert werden können.

Um dasselbe Verhalten beim Entfernen des obersten ZooKeeper zu implementieren, muss für jeden Schlüssel ein separater untergeordneter Zähler in etcd und Consul verwaltet werden. Da wir versucht haben, das Speichern von Metainformationen zu vermeiden, wurde beschlossen, den gesamten Teilbaum zu löschen.

Feinheiten der Umsetzung

Lassen Sie uns einige Aspekte der Implementierung der Bibliotheksschnittstelle in verschiedenen Systemen genauer betrachten.

Hierarchie in etcd

Die Aufrechterhaltung einer hierarchischen Ansicht in etcd war eine der interessantesten Aufgaben. Bereichsanforderungen erleichtern das Abrufen einer Liste von Schlüsseln mit einem bestimmten Präfix. Wenn Sie beispielsweise alles möchten, was mit "/foo" beginnt, fordern Sie den Bereich ["/foo", "/fop") . Dies würde jedoch den gesamten Teilbaum des Schlüssels zurückgeben, was möglicherweise nicht akzeptabel ist, wenn der Teilbaum groß ist. Zunächst wollten wir den in zetcd implementierten Schlüsselkonvertierungsmechanismus verwenden . Dabei wird am Anfang des Schlüssels ein Byte hinzugefügt, das der Tiefe des Knotens im Baum entspricht. Ich werde ein Beispiel geben.

 "/foo" -> "\u01/foo" "/foo/bar" -> "\u02/foo/bar" 

Dann können Sie alle unmittelbaren ["\u02/foo/", "\u02/foo0") Taste "/foo" ["\u02/foo/", "\u02/foo0") indem Sie den Bereich ["\u02/foo/", "\u02/foo0") . Ja, in ASCII folgt "/" "0" unmittelbar auf "/" .

Aber wie löscht man dann einen Scheitelpunkt? Es stellt sich heraus, dass Sie alle Bereiche der Form ["\uXX/foo/", "\uXX/foo0") für XX von 01 bis FF ["\uXX/foo/", "\uXX/foo0") . Und dann stießen wir auf ein Limit für die Anzahl der Vorgänge innerhalb einer einzelnen Transaktion.

Als Ergebnis wurde ein einfaches Schlüsselkonvertierungssystem erfunden, das es ermöglichte, sowohl das Entfernen des Schlüssels als auch den Empfang einer Liste von Kindern effektiv zu implementieren. Es reicht aus, vor dem letzten Token ein spezielles Symbol hinzuzufügen. Zum Beispiel:

 "/very" -> "/\u00very" "/very/long" -> "/very/\u00long" "/very/long/path" -> "/very/long/\u00path" 

"/\u00very" dann die Taste "/very" löschen, werden "/\u00very" und der Bereich ["/very/", "/very0") , und alle ["/very/", "/very0") , Schlüssel aus dem Bereich ["/very/\u00", "/very/\u01") .

Entfernen eines Schlüssels in ZooKeeper

Wie bereits erwähnt, können Sie in ZooKeeper einen Knoten nicht löschen, wenn er untergeordnete Knoten hat. Wir wollen den Schlüssel zusammen mit dem Teilbaum löschen. Wie man ist Wir machen es optimistisch. Zuerst durchlaufen wir den Teilbaum rekursiv und erhalten die untergeordneten Elemente jedes Scheitelpunkts in einer separaten Abfrage. Dann erstellen wir eine Transaktion, die versucht, alle Knoten des Teilbaums in der richtigen Reihenfolge zu löschen. Natürlich können zwischen dem Lesen und Löschen eines Teilbaums Änderungen auftreten. In diesem Fall schlägt die Transaktion fehl. Darüber hinaus kann sich der Teilbaum während des Lesevorgangs ändern. Eine Abfrage für die untergeordneten Knoten des nächsten Knotens kann einen Fehler zurückgeben, wenn beispielsweise dieser Scheitelpunkt bereits gelöscht wurde. In beiden Fällen wiederholen wir den gesamten Vorgang erneut.

Dieser Ansatz macht das Löschen eines Schlüssels sehr unwirksam, wenn er untergeordnete Elemente hat, und noch mehr, wenn die Anwendung weiterhin mit dem Teilbaum arbeitet und Schlüssel löscht und erstellt. Dies ermöglichte es uns jedoch, die Implementierung anderer Methoden in etcd und Consul nicht zu erschweren.

in ZooKeeper eingestellt

In ZooKeeper gibt es separate Methoden, die mit der Baumstruktur (create, delete, getChildren) und mit Daten in Knoten (setData, getData) arbeiten. Darüber hinaus haben alle Methoden strenge Voraussetzungen: create gibt einen Fehler zurück, wenn der Knoten bereits erstellt, gelöscht oder setData - falls noch nicht vorhanden. Wir brauchten die set-Methode, die aufgerufen werden kann, ohne über den Schlüssel nachzudenken.

Eine Möglichkeit besteht darin, einen optimistischen Ansatz wie beim Löschen anzuwenden. Überprüfen Sie, ob der Knoten vorhanden ist. Wenn vorhanden, rufen Sie setData auf, andernfalls erstellen Sie. Wenn die letzte Methode einen Fehler zurückgegeben hat, wiederholen Sie den Vorgang erneut. Das erste, was zu beachten ist, ist die Sinnlosigkeit der Existenzprüfung. Sie können create sofort aufrufen. Ein erfolgreicher Abschluss bedeutet, dass der Knoten nicht vorhanden war und erstellt wurde. Andernfalls gibt create den entsprechenden Fehler zurück, wonach setData aufgerufen werden muss. Natürlich kann zwischen den Aufrufen der Scheitelpunkt durch einen konkurrierenden Aufruf entfernt werden, und setData gibt auch einen Fehler zurück. In diesem Fall können Sie alles noch einmal wiederholen, aber lohnt es sich?

Wenn beide Methoden einen Fehler zurückgegeben haben, wissen wir mit Sicherheit, dass eine konkurrierende Löschung stattgefunden hat. Stellen Sie sich vor, diese Löschung erfolgte nach dem Aufruf von set. Unabhängig davon, welchen Wert wir zu ermitteln versuchen, wird er bereits gelöscht. Sie können also davon ausgehen, dass das Set erfolgreich war, auch wenn tatsächlich nichts geschrieben wurde.

Weitere technische Details

In diesem Abschnitt schweifen wir von verteilten Systemen ab und sprechen über das Codieren.
Eine der Hauptanforderungen des Kunden war plattformübergreifend: Unter Linux, MacOS und Windows muss mindestens einer der Dienste unterstützt werden. Anfangs haben wir die Entwicklung nur unter Linux durchgeführt, und in anderen Systemen haben wir später mit dem Testen begonnen. Dies verursachte viele Probleme, für die es einige Zeit völlig unklar war, wie man vorgehen sollte. Daher werden jetzt alle drei Koordinierungsdienste unter Linux und MacOS und nur Consul KV unter Windows unterstützt.

Von Anfang an haben wir versucht, vorgefertigte Bibliotheken für den Zugriff auf Dienste zu verwenden. Im Fall von ZooKeeper fiel die Wahl auf ZooKeeper C ++ , das am Ende unter Windows nicht kompiliert werden konnte. Dies ist jedoch nicht überraschend: Die Bibliothek ist nur unter Linux positioniert. Für Consul war ppconsul die einzige Option. Ich musste Unterstützung für Sitzungen und Transaktionen hinzufügen. Für etcd wurde nie eine vollwertige Bibliothek gefunden, die die neueste Version des Protokolls unterstützt. Daher haben wir nur einen grpc-Client generiert .

Inspiriert von der asynchronen Schnittstelle der ZooKeeper C ++ - Bibliothek haben wir uns entschlossen, auch die asynchrone Schnittstelle zu implementieren. In ZooKeeper C ++ werden hierfür Future / Promise-Primitive verwendet. In STL sind sie leider sehr bescheiden implementiert. Beispielsweise gibt es keine then-Methode , die die übergebene Funktion auf das zukünftige Ergebnis anwendet , sobald es verfügbar ist. In unserem Fall ist eine solche Methode erforderlich, um das Ergebnis in das Format unserer Bibliothek zu konvertieren. Um dieses Problem zu umgehen, mussten wir unseren einfachen Thread-Pool implementieren, da wir auf Kundenwunsch keine umfangreichen Bibliotheken von Drittanbietern wie Boost verwenden konnten.

Unsere Implementierung von funktioniert dann wie folgt. Beim Aufruf wird ein zusätzliches Versprechen / zukünftiges Paar erstellt. Die neue Zukunft wird zurückgegeben, und die übertragene wird zusammen mit der entsprechenden Funktion und einem zusätzlichen Versprechen in die Warteschlange gestellt. Ein Thread aus dem Pool wählt mehrere Futures aus der Warteschlange aus und fragt sie mit wait_for ab. Wenn das Ergebnis verfügbar ist, wird die entsprechende Funktion aufgerufen und ihr Rückgabewert an Versprechen übergeben.

Wir haben denselben Thread-Pool verwendet, um Anforderungen an etcd und Consul auszuführen. Dies bedeutet, dass mehrere verschiedene Threads mit den zugrunde liegenden Bibliotheken arbeiten können. ppconsul ist nicht threadsicher, daher sind Aufrufe durch Sperren durch Sperren geschützt.
Sie können mit grpc aus mehreren Threads arbeiten, aber es gibt Feinheiten. Etcd-Uhren werden über grpc-Streams implementiert. Dies sind bidirektionale Kanäle für bestimmte Arten von Nachrichten. Die Bibliothek erstellt einen einzelnen Stream für alle Uhren und einen einzelnen Stream, der eingehende Nachrichten verarbeitet. Daher verbietet grpc das Streamen paralleler Aufnahmen. Dies bedeutet, dass Sie beim Initialisieren oder Löschen der Uhr warten müssen, bis das Senden der vorherigen Anforderung abgeschlossen ist, bevor Sie die nächste senden. Wir verwenden bedingte Variablen für die Synchronisation.

Zusammenfassung

Überzeugen Sie sich selbst: liboffkv .

Unser Team: Raed Romanov , Ivan Glushenkov , Dmitry Kamaldinov , Victor Krapivensky , Vitaly Ivanin .