Hallo, Habra!
Heute präsentieren wir Ihnen die Übersetzung eines komplexen Artikels über die Implementierung von verteilten Sperren mit Redis und möchten über die Perspektive von Redis als Thema sprechen. Eine Analyse des besprochenen Redlock-Algorithmus von Martin Kleppmann, dem Autor des Buches "", wird präsentiert .
Verteilte Sperren sind ein sehr nützliches Konzept, das in vielen Umgebungen verwendet wird, in denen verschiedene Prozesse mit gemeinsamen Ressourcen auf der Grundlage von gegenseitiger Exklusion arbeiten müssen.
Es gibt eine Reihe von Bibliotheken und Beiträgen, die beschreiben, wie man DLM (Distributed Lock Manager) mit Redis implementiert, aber jede Bibliothek verwendet ihren eigenen Ansatz, und die bereitgestellten Garantien sind im Vergleich zu dem, was mit etwas komplizierterem Design erreicht werden kann, ziemlich schwach.
In diesem Artikel werden wir versuchen, einen relativ kanonischen Algorithmus zu beschreiben, der zeigt, wie man mit Redis verteilte Sperren implementiert. Wir sprechen über den Algorithmus namens Redlock, der einen Distributed Lock Manager implementiert und unserer Meinung nach sicherer ist als der gängige Ansatz mit einer einzigen Instanz. Wir hoffen, dass die Community ihn analysiert, Feedback gibt und ihn als Ausgangspunkt für die Umsetzung komplexerer oder alternativer Projekte verwendet.
Implementierungen
Bevor wir zur Beschreibung des Algorithmus übergehen, geben wir einige Links zu bereits vorhandenen Implementierungen an. Diese können als Referenz verwendet werden.
- (Implementierung für Ruby). Es gibt auch Redlock-rb, ein Paket (gem) für die einfache Verteilung, nicht nur dafür.
- (Implementierung für Python).
- (Implementierung für Asyncio Python).
- (Implementierung für PHP).
- (eine weitere Implementierung für PHP)
- (PHP-Bibliothek für Sperren)
- (Implementierung für Go).
- (Implementierung für Java).
- (Implementierung für Perl).
- (Implementierung für C++).
- (Implementierung für C#/.NET).
- (Implementierung für C#/.NET). Mit Unterstützung für asynchrone Erweiterungen und Sperren.
- (Implementierung für C# .NET mit konfigurierbarem Datenspeicher)
- (Implementierung für C# .NET)
- (Implementierung für NodeJS). Beinhaltet Unterstützung für die Verlängerung von Sperren.
Garantien für Sicherheit und Verfügbarkeit
Wir werden unser Projekt nur mit drei Eigenschaften modellieren, die nach unserer Ansicht die minimalen Garantien bieten, die für die effektive Nutzung verteilter Sperren erforderlich sind.
- Eigenschaft der Sicherheit: Gegenseitiger Ausschluss. Zu jedem Zeitpunkt kann nur ein Client die Sperre halten.
- Eigenschaft der Verfügbarkeit A: Keine gegenseitigen Sperren. Letztendlich kann immer eine Sperre erlangt werden, selbst wenn der Client, der die Ressource gesperrt hat, ausfällt oder in ein anderes Segment der Festplatte gerät.
- Eigenschaft der Verfügbarkeit B: Fehlertoleranz. Solange die meisten Redis-Knoten funktionieren, sind die Clients in der Lage, Sperren zu erwerben und freizugeben.
Warum eine auf Wiederherstellung nach Ausfällen basierende Implementierung in diesem Fall unzureichend ist.
Um zu verstehen, was wir verbessern möchten, analysieren wir die aktuelle Situation, die sich mit den meisten Bibliotheken für verteilte Sperren, die auf Redis basieren, ergeben hat.
Der einfachste Weg, eine Ressource mit Redis zu sperren, besteht darin, einen Schlüssel in der Instanz zu erstellen. Normalerweise wird der Schlüssel mit einer begrenzten Lebensdauer erstellt, dies wird durch die in Redis bereitgestellte Möglichkeit der expires erreicht, daher wird dieser Schlüssel früher oder später freigegeben (Eigenschaft 2 in unserer Liste). Wenn der Client die Ressource freigeben muss, entfernt er den Schlüssel.
Auf den ersten Blick funktioniert diese Lösung gut, aber es gibt ein Problem: In unserer Architektur entsteht ein einzelner Ausfallpunkt. Was passiert, wenn der führende Redis-Instanz ausfällt? Lass uns dann einen Nachfolger hinzufügen! Und wir werden ihn nutzen, wenn der Führer nicht verfügbar ist. Leider ist diese Option nicht tragfähig. Auf diese Weise können wir die uns notwendige Eigenschaft des gegenseitigen Ausschlusses nicht richtig umsetzen, da die Replikation in Redis asynchron ist.
Es ist offensichtlich, dass in einem solchen Modell ein Wettlaufzustand entsteht:
- Client A erwirbt die Sperre beim Führenden.
- Der Führende fällt aus, bevor die Aufzeichnung des Schlüssels an den Nachfolger übertragen wird.
- Der Nachfolger wird zum Führenden.
- Client B erwirbt die Sperre für dieselbe Ressource, die bereits von A gesperrt ist. SICHERHEITSVERLETZUNG!
Es ist manchmal vollkommen normal, dass unter besonderen Umständen, zum Beispiel bei einem Ausfall, viele Kunden gleichzeitig eine Sperre halten können. In solchen Fällen kann eine auf Replikation basierende Lösung angewendet werden. In anderen Fällen empfehlen wir die in diesem Artikel beschriebene Lösung.
Richtige Implementierung mit einem einzigen Instanz
Bevor wir versuchen, die Nachteile der oben beschriebenen Konfiguration mit einer einzelnen Instanz zu überwinden, lassen Sie uns klären, wie wir in diesem einfachen Fall richtig vorgehen, da eine solche Lösung tatsächlich in Anwendungen zulässig ist, in denen ein Zustand Wettlauf manchmal akzeptabel ist, und auch weil die Sperre auf einer einzigen Instanz die Grundlage für den hier beschriebenen verteilten Algorithmus bildet.
Um eine Sperre zu erwerben, gehen wir wie folgt vor:
SET resource_name my_random_value NX PX 30000
Dieser Befehl setzt den Schlüssel nur, wenn er noch nicht existiert (Option NX), mit einer Gültigkeitsdauer von 30000 Millisekunden (Option PX). Für den Schlüssel wird der Wert „myrandomvalue“ festgelegt. Dieser Wert muss innerhalb aller Clients und aller Sperranfragen einzigartig sein.
Im Prinzip wird ein zufälliger Wert verwendet, um eine sichere Freigabe der Sperre zu ermöglichen, indem ein Skript verwendet wird, das Redis mitteilt: Lösche den Schlüssel nur, wenn er existiert, und der Wert, der gespeichert ist, genau das ist, was erwartet wurde. Dies wird mit dem folgenden Lua-Skript erreicht:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endEs ist wichtig, zu verhindern, dass eine Sperre, die von einem anderen Client gesetzt wurde, entfernt wird. Zum Beispiel kann ein Client eine Sperre erwerben, sich dann während einer Operation, die länger dauert als die Gültigkeitsdauer der ersten Sperre, blockieren (so dass die Gültigkeit des Schlüssels abläuft) und später die Sperre entfernen, die von einem anderen Client gesetzt wurde.
Ein einfaches DEL zu verwenden, ist unsicher, da der Client eine Sperre entfernen könnte, die von einem anderen Client gesetzt wurde. Im Gegensatz dazu ist es bei Verwendung des oben genannten Skripts so, dass jede Sperre „unterzeichnet“ ist durch eine zufällige Zeichenfolge, sodass nur der Client, der sie zuvor gesetzt hat, sie löschen kann.
Wie sollte diese zufällige Zeichenfolge aussehen? Ich nehme an, sie sollte 20 Bytes aus /dev/urandom bestehen, aber es gibt auch weniger aufwendige Möglichkeiten, eine ausreichend einzigartige Zeichenfolge für Ihre Zwecke zu erzeugen. Es wäre beispielsweise in Ordnung, RC4 mit /dev/urandom zu streuen und dann auf dieser Basis einen pseudorandomisierten Strom zu erzeugen. Eine einfachere Lösung besteht darin, die Unix-Zeit in Mikrosekundenplus die Client-ID zu kombinieren; dies ist nicht so sicher, entspricht aber dennoch dem Anforderungsniveau in den meisten Kontexten.
Die Zeit, die wir als Lebensdauer des Schlüssels verwenden, wird als „Lock Lifetime“ bezeichnet. Dieser Wert ist sowohl die Frist, nach deren Ablauf das Schloss automatisch freigegeben wird, als auch die Zeit, die der Client hat, um die Operation auszuführen, bevor ein anderer Client dieser wiederum diese Ressource sperren kann, ohne tatsächlich die Garantie der gegenseitigen Exklusion zu verletzen. Diese Garantie ist nur auf ein bestimmtes Zeitfenster beschränkt, das mit dem Erwerb der Sperre beginnt.
Wir haben also einen guten Weg besprochen, eine Sperre zu erwerben und freizugeben. Das System (wenn wir von einem nicht verteilten System sprechen, das aus einer einzigen und ständig verfügbaren Instanz besteht) ist sicher. Lassen Sie uns dieses Konzept auf ein verteiltes System erweitern, in dem wir solche Garantien nicht haben.
Der Redlock-Algorithmus
In der verteilten Version des Algorithmus gehen wir davon aus, dass wir N führende Redis-Instanzen haben. Diese Knoten sind völlig unabhängig voneinander, weshalb wir keine Replikation oder irgendein anderes implizites Koordinationssystem verwenden. Wir haben bereits erläutert, wie man sicher eine Sperre auf einer einzelnen Instanz erwirbt und freigibt. Wir nehmen als gegeben an, dass der Algorithmus bei der Arbeit mit einer einzelnen Instanz genau diese Methode verwenden wird. In unseren Beispielen setzen wir N auf 5, was ein vernünftiger Wert ist. Daher benötigen wir 5 führende Redis-Instanzen auf verschiedenen Computern oder virtuellen Maschinen, um sicherzustellen, dass sie im Wesentlichen unabhängig voneinander agieren.
Um eine Sperre zu erwerben, führt der Client die folgenden Operationen aus:
- Erhält die aktuelle Zeit in Millisekunden.
- Der Client versucht nacheinander, eine Sperre für alle N Instanzen zu erhalten, indem er in allen Fällen denselben Schlüsselname und zufällige Werte verwendet. In Schritt 2 verwendet der Client beim Setzen der Sperre für jede Instanz eine Verzögerung, die im Vergleich zur Zeit, nach der die Sperre automatisch aufgehoben wird, relativ kurz ist. Wenn die Sperrdauer beispielsweise 10 Sekunden beträgt, kann die Verzögerung im Bereich von etwa 5-50 Millisekunden liegen. Dadurch wird eine Situation ausgeschlossen, in der der Client lange gesperrt bleibt, während er versucht, eine ausgefallene Redis-Node zu erreichen: Wenn die Instanz nicht verfügbar ist, versuchen wir so schnell wie möglich, uns mit einer anderen Instanz zu verbinden.
- Um die Sperre zu erhalten, berechnet der Client, wie viel Zeit vergangen ist; dazu subtrahiert er den Zeitstempel, der im Schritt 1 erhalten wurde, vom aktuellen Zeitwert. Nur wenn der Client die Sperre für die meisten Instanzen (mindestens 3) erhalten hat und die insgesamt benötigte Zeit zum Erhalten der Sperre geringer ist als die Sperrdauer, wird davon ausgegangen, dass das Erhalten der Sperre erfolgreich war.
- Wenn die Sperre erhalten wurde, wird die ursprüngliche Sperrdauer minus die verstrichene Zeit, die in Schritt 3 berechnet wurde, als Herrschaftszeit der Sperre betrachtet.
- Wenn der Client aus irgendeinem Grund die Sperre nicht erhalten hat (entweder hat er nicht N/2+1 Instanzen sperren können oder die Sperrdauer ist negativ), wird er versuchen, alle Instanzen zu entsperren (auch diejenigen, die er für nicht sperrbar hielt).
Ist der Algorithmus asynchron?
Dieser Algorithmus geht davon aus, dass, obwohl es keine synchronisierten Uhren gibt, nach denen alle Prozesse arbeiten, die lokale Zeit in jedem Prozess dennoch ungefähr im selben Tempo verläuft, und der Fehler im Vergleich zur Gesamtdauer, nach der die Sperre automatisch aufgehoben wird, gering ist. Diese Annahme ähnelt sehr der Situation, die typischerweise bei normalen Computern zu finden ist: Jeder Computer hat lokale Uhren, und in der Regel können wir darauf vertrauen, dass die Zeitabweichung zwischen verschiedenen Computern gering ist.
In diesem Stadium müssen wir unsere Regel des gegenseitigen Ausschlusses genauer formulieren: Der gegenseitige Ausschluss ist nur gewährleistet, wenn der Kunde, der das Lock hält, die Arbeit innerhalb der Zeit, in der das Lock gültig ist (dieser Wert wurde in Schritt 3 ermittelt), minus einer weiteren Zeitspanne (insgesamt einige Millisekunden, um die Zeitabweichung zwischen den Prozessen auszugleichen), abschließt.
Weitere Informationen zu solchen Systemen, die die Abstimmung von Zeitabweichungen erfordern, bietet der folgende interessante Artikel: .
Wiederholter Versuch bei Fehlern
Wenn der Kunde das Lock nicht erhalten konnte, sollte er versuchen, es erneut zu erhalten, wobei er eine zufällige Verzögerung einhält; dies geschieht, um mehrere Clients, die gleichzeitig versuchen, ein Lock für dieselbe Ressource zu erwerben, zu synchronisieren (was zu einer Situation "geteilter Gehirne" führen kann, in der es keine Gewinner gibt). Darüber hinaus wird das Zeitfenster, in dem die Situation geteilter Gehirne auftreten kann, enger, je schneller der Kunde versucht, die Mehrzahl der Redis-Instanzen zu sperren (und desto weniger Bedarf es an Wiederholungen). Daher sollte der Kunde idealerweise versuchen, gleichzeitig SET-Befehle an N Instanzen über Multiplexing zu senden.
Hier sollte betont werden, wie wichtig es ist, dass Clients, die nicht die Mehrheit der Locks erwerben konnten, die (teilweise) erworbenen Locks freigeben, damit nicht auf das Ablaufen des Schlüssels gewartet werden muss, bevor das Lock über die Ressource erneut erworben werden kann (es sei denn, es tritt eine Netzwerkfragmentierung auf und der Kunde verliert die Verbindung zu den Redis-Instanzen, dann muss ein Verfügbarkeitsbonus aufgrund der Wartezeit auf das Ablaufen des Schlüssels bezahlt werden).
Lock-Freigabe
Die Lock-Freigabe ist ein einfacher Vorgang, der lediglich darin besteht, alle Instanzen zu entsperren, unabhängig davon, ob der Kunde glaubt, dass er eine bestimmte Instanz erfolgreich gesperrt hat.
Sicherheitsüberlegungen
Ist der Algorithmus sicher? Lassen Sie uns versuchen, uns vorzustellen, was in verschiedenen Szenarien passiert.
Angenommen, der Kunde konnte die Sperre über die meisten Instanzen erlangen. Jede dieser Instanzen wird einen Schlüssel mit der gleichen Lebensdauer für alle enthalten. Allerdings wurde jeder dieser Schlüssel zu einem anderen Zeitpunkt festgelegt, daher wird auch die Gültigkeit unterschiedlich ablaufen. Wenn jedoch der erste Schlüssel nicht später als T1 (die Zeit, die wir vor dem Kontakt mit dem ersten Server wählen) festgelegt wurde und der letzte Schlüssel nicht später als T2 (die Zeit, in der die Antwort vom letzten Server empfangen wurde), sind wir zuversichtlich, dass der erste Schlüssel in der Menge, deren Gültigkeit abläuft, mindestens bestehen bleibt. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle anderen Schlüssel werden später ablaufen, sodass wir sicher sein können, dass alle Schlüssel während dieser Zeit mindestens gültig sind.
Während der Zeit, in der die meisten Schlüssel gültig bleiben, kann ein anderer Kunde die Sperre nicht erwerben, da N/2+1 SET NX Operationen nicht erfolgreich sein können, wenn bereits N/2+1 Schlüssel existieren. Folglich, wenn die Sperre erlangt wurde, kann sie in diesem Moment nicht erneut erworben werden (was das Ausschlussprinzip verletzen würde).
Es ist wahr, dass wir sicherstellen möchten, dass eine Gruppe von Kunden, die gleichzeitig versuchen, eine Sperre zu erlangen, nicht gleichzeitig erfolgreich sein kann.
Wenn ein Kunde die Mehrheit der Instanzen gesperrt hat, indem er dafür etwa oder länger als die maximal mögliche Sperrdauer benötigt hat, betrachtet er die Sperre als ungültig und gibt die Instanzen frei. Daher müssen wir nur den Fall in Betracht ziehen, in dem es dem Kunden gelingt, die Mehrheit der Instanzen in einer kürzeren Zeitspanne zu sperren, als die Gültigkeit. In diesem Fall, was das oben angeführte Argument betrifft, während der Zeit MIN_VALIDITY darf kein Kunde in der Lage sein, die Sperre erneut zu erlangen. Daher können viele Kunden N/2+1 Instanzen zur gleichen Zeit (die am Ende der Phase 2 abläuft) nur dann sperren, wenn die Zeit zur Sperrung der Mehrheit länger war als die TTL-Zeit, was die Sperre ungültig macht.
Können Sie einen formalen Sicherheitsbeweis, bestehende ähnliche Algorithmen oder einen Fehler in der Darstellung nachweisen?
Überlegungen zur Verfügbarkeit
Die Verfügbarkeit des Systems hängt von drei Hauptmerkmalen ab:
- Automatische Entsperrung (da die Lebensdauer der Schlüssel abläuft): Letztendlich werden die Schlüssel wieder verfügbar sein, um für Sperren verwendet zu werden.
- Die Tatsache, dass Kunden sich in der Regel gegenseitig helfen, Sperren zu entfernen, wenn die benötigte Sperre nicht erworben wurde oder erworben wurde und die Arbeit abgeschlossen ist; daher ist es sehr wahrscheinlich, dass wir nicht darauf warten müssen, dass die Schlüssel ablaufen, um die Sperre erneut zu erwerben.
- Die Tatsache, dass, wenn ein Kunde erneut versuchen muss, eine Sperre zu erhalten, er vergleichsweise länger wartet als der Zeitraum, der benötigt wird, um die meisten Sperren zu erwerben. Dadurch wird die Wahrscheinlichkeit einer Wettbewerbssituation um Ressourcen verringert.
Es ist jedoch ein Preis für die Verringerung der Verfügbarkeit zu zahlen, der der TTL-Zeit in Netzwerksegmenten entspricht. Wenn es kontinuierliche Segmente gibt, kann dieser Preis einen unbestimmten Betrag annehmen. Dies geschieht jedes Mal, wenn ein Kunde eine Sperre erwirbt und dann in ein anderes Segment getrennt wird, bevor er sie freigeben kann.
Im Prinzip kann das System bei unendlichen kontinuierlichen Netzwerksegmenten unendlich lange nicht verfügbar bleiben.
Leistung, Wiederherstellung nach Ausfällen und fsync
Viele nutzen Redis, da eine hohe Leistung des Sperrservers erforderlich ist, sowohl hinsichtlich der Latenzen, die zum Erwerb und zur Freigabe von Sperren benötigt werden, als auch der Anzahl der solchen Erwerbs-/Freigabevorgänge, die pro Sekunde durchgeführt werden können. Um diesem Bedarf gerecht zu werden, gibt es eine Kommunikationsstrategie mit N Redis-Servern, um die Latenz zu verringern. Dies ist eine Multiplexing-Strategie (oder „Arme-Multiplexing“, bei der der Socket in den Nicht-Blockierungsmodus versetzt wird, alle Befehle gesendet werden und Befehle später gelesen werden, wobei davon ausgegangen wird, dass die Durchlaufzeit zwischen dem Client und jedem der Instanzen ähnlich ist).
Es ist jedoch auch zu berücksichtigen, dass Überlegungen zur langfristigen Datenspeicherung erforderlich sind, wenn wir ein Modell mit sicherer Wiederherstellung nach Ausfällen schaffen möchten.
Um das Problem zu klären, nehmen wir an, dass wir Redis ohne langfristige Datenspeicherung konfigurieren. Der Kunde kann 3 von 5 Instanzen sperren. Eine der Instanzen, die der Kunde sperren konnte, wird neu gestartet, und in diesem Moment treten wieder 3 Instanzen für die gleiche Ressource auf, die wir sperren können, und ein anderer Kunde kann seinerseits die neu gestartete Instanz sperren, was das Sicherheitsmerkmal der Exklusivität von Sperren verletzt.
Wenn die proaktive Datenspeicherung (AOF) aktiviert ist, verbessert sich die Situation etwas. Zum Beispiel kann der Server hochgefahren werden, indem der SHUTDOWN-Befehl gesendet und er neu gestartet wird. Da Ablaufoperationen in Redis semantisch so implementiert sind, dass die Zeit weiterhin vergeht, auch wenn der Server ausgeschaltet ist, sind alle unsere Anforderungen in Ordnung. In Ordnung, solange eine ordnungsgemäße Herunterfahren gewährleistet ist. Was ist jedoch bei Stromausfällen? Wenn Redis standardmäßig konfiguriert ist, mit fsync-Synchronisation auf die Festplatte jede Sekunde, dann könnte es sein, dass wir nach dem Neustart unseren Schlüssel nicht mehr haben. Theoretisch, wenn wir die Sicherheit der Sperren bei jedem Neustart der Instanz garantieren wollen, müssen wir fsync=always in den Einstellungen für die langfristige Datenspeicherung aktivieren. Das würde die Leistung vollständig ruinieren und auf das Niveau solcher CP-Systeme bringen, die traditionell für die sichere Implementierung verteilter Sperren verwendet werden.
Aber die Situation ist besser, als sie auf den ersten Blick erscheint. Grundsätzlich bleibt die Sicherheit des Algorithmus erhalten, da die Instanz, wenn sie nach einem Ausfall neu gestartet wird, nicht mehr an einer Sperre beteiligt ist, die derzeit aktiv ist.
Um dies zu gewährleisten, muss nur sichergestellt werden, dass die Instanz nach einem Ausfall für eine Zeitspanne nicht verfügbar bleibt, die gerade etwas über dem maximalen TTL liegt, den wir verwenden. So warten wir auf das Ablaufen der Frist und die automatische Freigabe aller Schlüssel, die zum Zeitpunkt des Ausfalls aktiv waren.
Mit der Nutzung von verzögerten Neustarts ist es grundsätzlich möglich, Sicherheit auch ohne eine langfristige Speicherkapazität in Redis zu erreichen. Es sei jedoch erwähnt, dass dies in einer Strafe wegen Verstoßes gegen die Verfügbarkeit resultieren kann. Beispielsweise wird das System im Falle des Ausfalls der meisten Instanzen global unzugänglich für die Dauer von TTL (und in dieser Zeit kann keine Ressource gesperrt werden).
Erhöhen der Verfügbarkeit des Algorithmus: Sperrzeit verlängern
Wenn die von den Clients ausgeführten Arbeiten aus kleinen Schritten bestehen, ist es möglich, die standardmäßig festgelegte Gültigkeitsdauer der Sperre zu verkürzen und einen Mechanismus zur Verlängerung der Sperren zu implementieren. Grundsätzlich, wenn der Client mit Berechnungen beschäftigt ist und die Gültigkeitsdauer der Sperre gefährlich sinkt, kann ein Lua-Skript an alle Instanzen gesendet werden, um TTL des Schlüssels zu verlängern, sofern der Schlüssel noch existiert und sein Wert weiterhin zufällig ist, wie er war, als die Sperre erworben wurde.
Der Client sollte die Sperre nur dann als erneut erworben betrachten, wenn es ihm gelingt, die Mehrheit der Instanzen innerhalb der Gültigkeitsdauer zu sperren.
Technisch ändert sich der Algorithmus dabei nicht, weshalb die maximale Anzahl der Wiederholungsversuche zum Erwerb von Sperren begrenzt werden sollte, da sonst die Eigenschaften der Verfügbarkeit gefährdet werden.
Quelle: habr.com
