Clever Geek Handbook

Verteilte Sperren mit Redis

Hallo Habr!



Heute machen wir Sie auf eine Übersetzung eines komplexen Artikels über die Implementierung verteilter Sperren mit Redis aufmerksam und schlagen vor, über die Perspektiven von Redis als Thema zu sprechen. Eine Analyse des betrachteten Redlock-Algorithmus von Martin Kleppman, Autor des Buches "High Load Applications ", wird hier gegeben .





Verteilte Sperren sind ein sehr nützliches Grundelement, das in vielen Umgebungen verwendet wird, in denen unterschiedliche Prozesse gemeinsam genutzte Ressourcen auf sich gegenseitig ausschließende Weise bearbeiten müssen.



Es gibt eine Reihe von Bibliotheken und Beiträgen, in denen beschrieben wird, wie ein DLM (Distributed Locking Manager) mit Redis implementiert wird. Jede Bibliothek verfolgt jedoch einen anderen Ansatz und die gewährten Garantien sind schwach im Vergleich zu dem, was mit einem etwas komplexeren Design erreicht werden kann.



In diesem Artikel werden wir versuchen, einen bedingt kanonischen Algorithmus zu beschreiben, der demonstriert, wie verteilte Sperren mit Redis implementiert werden. Wir werden über einen Algorithmus namens Redlock sprechenEs implementiert einen verteilten Sperrmanager und unserer Meinung nach ist dieser Algorithmus sicherer als der herkömmliche Einzelinstanzansatz. Wir hoffen, dass die Community es analysiert, Feedback gibt und es als Ausgangspunkt für die Umsetzung komplexerer oder alternativer Projekte verwendet.



Implementierungen



Bevor Sie mit der Beschreibung des Algorithmus fortfahren, finden Sie hier einige Links zu vorgefertigten Implementierungen. Sie können als Referenz verwendet werden.







Sicherheits- und Verfügbarkeitsgarantien



Wir werden unser Design mit nur drei Eigenschaften modellieren, von denen wir glauben, dass sie die Mindestgarantien bieten, die für die effektive Nutzung verteilter Schlösser erforderlich sind.



  1. Sicherheitseigenschaft: Gegenseitiger Ausschluss. Es kann jeweils nur ein Client eine Sperre halten.
  2. Barrierefreiheitseigenschaft A: Keine Deadlocks. Am Ende können Sie immer eine Sperre erhalten, selbst wenn der Client, der die Ressource gesperrt hat, ausfällt oder in einem anderen Festplattensegment landet.
  3. Zugänglichkeitseigenschaft B: Fehlertoleranz. Während die meisten Redis-Knoten ausgeführt werden, können Clients Sperren erwerben und freigeben.




Warum eine Failover-basierte Implementierung in diesem Fall nicht ausreicht

Um zu verstehen, was wir verbessern werden, analysieren wir den aktuellen Stand der Dinge mit den meisten Redis-basierten verteilten Sperrbibliotheken.



Der einfachste Weg, eine Ressource mit Redis zu sperren, besteht darin, einen Schlüssel für eine Instanz zu erstellen. Normalerweise wird ein Schlüssel mit einer begrenzten Lebensdauer erstellt. Dies wird mithilfe der in Redis bereitgestellten Ablauffunktion erreicht. Daher wird dieser Schlüssel früher oder später freigegeben (Eigenschaft 2 in unserer Liste). Wenn der Client die Ressource freigeben muss, wird der Schlüssel entfernt.



Auf den ersten Blick funktioniert diese Lösung gut, aber es gibt ein Problem: Es gibt einen einzigen Fehlerpunkt in unserer Architektur. Was passiert, wenn die Master-Redis-Instanz ausfällt? Fügen wir dann einen Follower hinzu! Und wir werden es verwenden, wenn der Host nicht verfügbar ist. Leider ist diese Option nicht realisierbar. Auf diese Weise können wir die Eigenschaft zur gegenseitigen Ausgrenzung, die wir zur Gewährleistung der Sicherheit benötigen, nicht korrekt implementieren, da die Replikation in Redis asynchron ist.



Offensichtlich tritt in einem solchen Modell eine Rennbedingung auf:

  1. Client A erhält eine Sperre für den Master.
  2. Der Master schlägt fehl, bevor das Schreiben auf den Schlüssel an den Slave übertragen wird.
  3. Der Anhänger wird zum Anführer befördert.
  4. Client B erhält eine Sperre für dieselbe Ressource, die bereits von A gesperrt wurde. SICHERHEITSVERLETZUNG!




Manchmal ist es völlig normal, dass unter bestimmten Umständen, z. B. bei einem Fehler, mehrere Clients gleichzeitig eine Sperre halten können. In solchen Fällen können Sie eine replikationsbasierte Lösung anwenden. Andernfalls empfehlen wir die in diesem Artikel beschriebene Lösung.



Richtige Implementierung einer einzelnen Instanz



Bevor wir versuchen, die oben beschriebenen Mängel der Konfiguration einer einzelnen Instanz zu überwinden, wollen wir herausfinden, wie dieser einfache Fall behandelt wird, da dies in Anwendungen, in denen die Rennbedingungen gelegentlich akzeptabel sind, tatsächlich akzeptabel ist auch weil das Sperren einer einzelnen Instanz als Grundlage für den hier beschriebenen verteilten Algorithmus dient.



Gehen Sie folgendermaßen vor, um eine Sperre zu erhalten:



SET resource_name my_random_value NX PX 30000



Dieser Befehl installiert einen Schlüssel nur, wenn er noch nicht vorhanden ist (Option NX), mit einem Ablaufdatum von 30.000 Millisekunden (Option PX). Der Schlüssel ist auf " myrandomvalue" gesetzt. Dieser Wert muss für alle Clients und für alle Sperranforderungen eindeutig sein.

Grundsätzlich wird der Zufallswert verwendet, um die Sperre sicher aufzuheben. Ein Skript weist Redis an, den Schlüssel nur zu entfernen, wenn er vorhanden ist und der darin gespeicherte Wert genau dem entspricht, 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
end




Dies ist wichtig, um die Freigabe einer Sperre durch einen anderen Client zu verhindern. Beispielsweise kann ein Client eine Sperre erwerben, dann eine Operation blockieren, die länger als die erste Sperre dauert (damit der Schlüssel abläuft) und später die Sperre entfernen, die ein anderer Client gesetzt hat.

Es ist nicht sicher, ein einfaches DEL zu verwenden, da ein Client möglicherweise eine von einem anderen Client gehaltene Sperre aufhebt. Im Gegensatz dazu wird bei Verwendung des obigen Skripts jede Sperre mit einer zufälligen Zeichenfolge „signiert“, sodass nur der Client, der sie zuvor platziert hat, sie entfernen kann.



Was soll diese zufällige Zeichenfolge sein? Ich denke, es sollte 20 Bytes von / dev / urandom entfernt sein, aber Sie können kostengünstigere Möglichkeiten finden, um die Zeichenfolge für den Zweck, den Sie erreichen möchten, eindeutig genug zu machen. Zum Beispiel wäre es in Ordnung, RC4 mit / dev / urandom zu setzen und dann einen darauf basierenden Pseudozufallsstrom zu generieren. Eine einfachere Lösung besteht darin, die Mikrosekunden-Unix-Zeit mit der Client-ID zu kombinieren. es ist nicht ganz so sicher, aber in den meisten Kontexten vielleicht auf der Ebene der Herausforderung.



Die Zeit, die wir als Maß für die Lebensdauer des Schlüssels verwenden, wird als "Ablaufzeit der Sperre" bezeichnet. Dieser Wert ist sowohl die Zeit, nach der die Sperre automatisch aufgehoben wird, als auch die Zeit, nach der der Client den Vorgang abschließen muss, bevor ein anderer Client die Ressource sperren kann, ohne die gegenseitigen Ausschlussgarantien tatsächlich zu verletzen. Eine solche Garantie ist nur auf ein bestimmtes Zeitfenster beschränkt, das ab dem Zeitpunkt des Erwerbs des Schlosses beginnt.



Wir haben also einen guten Weg besprochen, um ein Schloss zu erwerben und freizugeben. Das System (wenn es sich um ein nicht zugewiesenes System handelt, das aus einer einzelnen und immer verfügbaren Instanz besteht) ist sicher. Erweitern wir dieses Konzept auf ein verteiltes System, für das wir keine solchen Garantien haben.



Redlock-Algorithmus



Die verteilte Version des Algorithmus geht davon aus, dass wir N führende Redis haben. Diese Knoten sind völlig unabhängig voneinander, sodass wir keine Replikation oder ein anderes implizites Koordinationssystem verwenden. Wir haben bereits erläutert, wie Sie Sperren für eine einzelne Instanz sicher erwerben und freigeben können. Wir gehen davon aus, dass der Algorithmus diese Methode verwendet, wenn er mit einer einzelnen Instanz arbeitet. In unseren Beispielen setzen wir N auf 5, was ein durchaus vernünftiger Wert ist. Daher müssen wir 5 Redis-Master auf verschiedenen Computern oder virtuellen Maschinen verwenden, um sicherzustellen, dass sie weitgehend unabhängig voneinander arbeiten.



Um eine Sperre zu erhalten, führt der Client die folgenden Vorgänge aus:



  1. Ruft die aktuelle Zeit in Millisekunden ab.
  2. N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
  3. , , ; , 1. , ( 3), , , , , , .
  4. , , 3.
  5. - ( N/2+1 , ), ( , , , ).




Ist der Algorithmus asynchron?



Dieser Algorithmus basiert auf der Annahme, dass, obwohl es keine synchronisierte Uhr gibt, mit der alle Prozesse arbeiten würden, die Ortszeit in jedem Prozess immer noch ungefähr mit der gleichen Rate fließt und der Fehler im Vergleich zur Gesamtzeit, nach der die Sperre automatisch aufgehoben wird, gering ist. Diese Annahme ist der für normale Computer typischen Situation sehr ähnlich: Jeder Computer verfügt über eine lokale Uhr, und normalerweise können wir uns darauf verlassen, dass der Zeitunterschied auf verschiedenen Computern gering ist.



In diesem Stadium sollten wir bei der Formulierung unserer Regel des gegenseitigen Ausschlusses vorsichtiger sein: Der gegenseitige Ausschluss ist nur dann gewährleistet, wenn der Client, der die Sperre hält, innerhalb der Zeit, in der die Sperre gültig ist (dieser Wert wurde in Schritt 3 erhalten), abzüglich einer gewissen Zeit (insgesamt) abgeschlossen ist mehrere Millisekunden, um den Zeitunterschied zwischen den Prozessen auszugleichen).



Der folgende interessante Artikel enthält weitere Informationen zu solchen Systemen, für die eine Zeitlücke erforderlich ist: Leases: Ein effizienter fehlertoleranter Mechanismus für die Konsistenz des verteilten Dateicaches .



Wiederholen Sie den Vorgang bei einem Fehler



Wenn der Client die Sperre nicht erhält, sollte er es mit einer zufälligen Verzögerung erneut versuchen. Dies geschieht, um mehrere Clients gleichzeitig zu synchronisieren, die versuchen, eine Sperre für dieselbe Ressource zu erlangen (was zu einer Split-Brain-Situation führen kann, in der es keine Gewinner gibt). Je schneller ein Client versucht, eine Sperre für die meisten Redis-Instanzen zu erlangen, desto enger wird das Fenster, in dem eine Split-Brain-Situation auftreten kann (und desto weniger Wiederholungen sind erforderlich). Daher sollte der Client im Idealfall versuchen, SET-Befehle gleichzeitig mithilfe von Multiplexing an N Instanzen zu senden.



Hervorzuheben ist hier, wie wichtig es ist, dass Clients, die die meisten Sperren nicht erwerben konnten, (teilweise) erworbene Sperren freigeben, damit sie nicht auf das Ablaufdatum des Schlüssels warten müssen, bevor die Sperre für die Ressource erneut erfasst werden kann (wenn jedoch eine Netzwerkfragmentierung auftritt Wenn der Client den Kontakt zu den Redis-Instanzen verliert, müssen Sie eine Strafe für Zugriffsverletzungen zahlen, solange der Schlüssel abläuft.



Freigeben einer Sperre Das



Freigeben einer Sperre ist ein einfacher Vorgang, bei dem lediglich alle Instanzen entsperrt werden müssen, unabhängig davon, ob der Kunde glaubt, eine bestimmte Instanz erfolgreich sperren zu können.



Sicherheitsaspekte



Ist der Algorithmus sicher? Versuchen wir uns vorzustellen, was in verschiedenen Szenarien passiert.



Nehmen wir zunächst an, dass der Client in den meisten Fällen die Sperre erhalten hat. Jede der Instanzen enthält einen Schlüssel mit der gleichen Lebensdauer für alle. Jeder dieser Schlüssel wurde jedoch zu einem bestimmten Zeitpunkt installiert, sodass sie zu unterschiedlichen Zeiten ablaufen. Wenn jedoch der erste Schlüssel zu einem Zeitpunkt installiert wurde, der nicht schlechter als T1 ist (der Zeitpunkt, den wir vor der Kontaktaufnahme mit dem ersten Server ausgewählt haben), und der letzte Schlüssel zu einem Zeitpunkt installiert wurde, der nicht schlechter als T2 ist (der Zeitpunkt, zu dem eine Antwort vom letzten Server empfangen wurde), dann haben wir sind sicher, dass der erste Schlüssel im Satz, der abläuft, mindestens hältMIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT... Alle anderen Schlüssel verfallen später, sodass wir sicher sein können, dass alle Schlüssel mindestens für diese Zeit gleichzeitig gültig sind.



Während der Zeit, in der die meisten Schlüssel gültig bleiben, kann ein anderer Client die Sperre nicht erlangen, da N / 2 + 1 SET NX-Operationen nicht erfolgreich sein können, wenn bereits N / 2 + 1 Schlüssel vorhanden sind. Wenn das Schloss erworben wurde, ist es daher unmöglich, es im selben Moment wieder zu erwerben (dies würde die Eigenschaft des gegenseitigen Ausschlusses verletzen).

Wir möchten jedoch sicherstellen, dass viele Clients, die gleichzeitig versuchen, eine Sperre zu erhalten, nicht gleichzeitig erfolgreich sein können.



Wenn der Client die meisten Instanzen für mindestens die maximale Sperrdauer gesperrt hat, wird die Sperre ungültig und die Instanzen werden entsperrt. Daher müssen wir nur den Fall berücksichtigen, in dem der Client die meisten Instanzen in weniger als dem Ablaufdatum blockieren konnte. In diesem Fall sollte in Bezug auf das obige Argument MIN_VALIDITYkein Client in der Lage sein, die Sperre rechtzeitig wieder zu erlangen. Daher können mehrere Clients N / 2 + 1-Instanzen in derselben Zeitspanne (die am Ende von Stufe 2 endet) nur dann sperren, wenn die Zeit zum Sperren der Mehrheit größer als die TTL-Zeit war, wodurch die Sperre ungültig wird.



Können Sie einen formalen Sicherheitsnachweis erbringen, auf vorhandene ähnliche Algorithmen hinweisen oder oben einen Fehler finden?



Überlegungen zur



Verfügbarkeit Die Verfügbarkeit des Systems hängt von drei Hauptmerkmalen ab:



  1. Automatische Freigabe von Sperren (wenn Schlüssel ablaufen): Schließlich sind Schlüssel wieder verfügbar, um für Sperren verwendet zu werden.
  2. Die Tatsache, dass Kunden sich normalerweise gegenseitig helfen, indem sie Sperren entfernen, wenn die gewünschte Sperre nicht erworben wurde oder erworben wurde und die Arbeit abgeschlossen ist; Daher ist es wahrscheinlich, dass wir nicht warten müssen, bis die Schlüssel ablaufen, um das Schloss wieder zu erlangen.
  3. Die Tatsache, dass ein Kunde, wenn er erneut versuchen muss, ein Schloss zu erwerben, relativ lange wartet, als es zum Erwerb der meisten Schlösser erforderlich ist. Dies verringert die Wahrscheinlichkeit einer gespaltenen Gehirnsituation im Wettbewerb um Ressourcen.




Sie müssen jedoch eine Strafe für reduzierte Verfügbarkeit zahlen, die der TTL-Zeit in den Netzwerksegmenten entspricht. Wenn also zusammenhängende Segmente vorhanden sind, kann diese Strafe eine undefinierte Größe haben. Dies geschieht immer dann, wenn ein Client eine Sperre erwirbt und dann an einem anderen Segment festklemmt, bevor er es freigeben kann.



Im Prinzip kann das System bei unendlich zusammenhängenden Netzwerksegmenten für einen unendlichen Zeitraum nicht verfügbar bleiben.



Leistung, Failover und Fsync



Viele Benutzer verwenden Redis, weil sie eine hohe Leistung des Sperrservers bei der zum Erfassen und Freigeben von Sperren erforderlichen Latenz sowie der Anzahl solcher Erfassungs- / Freigabevorgänge, die pro Sekunde ausgeführt werden können, bereitstellen müssen. Um diese Anforderung zu erfüllen, gibt es eine Kommunikationsstrategie mit N Redis-Servern, um die Latenz zu verringern. Dies ist eine Multiplexing-Strategie (oder das Multiplexing eines armen Mannes, bei dem der Socket in den nicht blockierenden Modus versetzt wird, alle Befehle gesendet und die Befehle später gelesen werden, vorausgesetzt, die Umlaufzeit zwischen dem Client und jeder Instanz ist ähnlich).



Es ist wahr, dass auch eine langfristige Datenspeicherung in Betracht gezogen werden muss, wenn ein Modell mit zuverlässiger Wiederherstellung nach Fehlern erstellt werden soll.



Grundsätzlich nehmen wir zur Klärung des Problems an, dass wir Redis überhaupt ohne langfristige Datenspeicherung konfigurieren. Der Client kann 3 von 5 Instanzen blockieren. Eine der Instanzen, die der Client blockieren konnte, wird neu gestartet, und in diesem Moment werden erneut 3 Instanzen für dieselbe Ressource angezeigt, die wir blockieren können, und der andere Client kann wiederum die neu gestartete Instanz blockieren, wodurch die implizite Sicherheitseigenschaft verletzt wird Exklusivität von Schlössern.



Wenn Sie Data Advance (AOF) aktivieren, verbessert sich die Situation geringfügig. Sie können den Server beispielsweise hochstufen, indem Sie den Befehl SHUTDOWN senden und anschließend neu starten. Da die Ablaufvorgänge in Redis semantisch so implementiert sind, dass die Zeit auch nach dem Ausschalten des Servers weiter fließt, ist alles in Ordnung mit all unseren Anforderungen. Normal, solange das normale Herunterfahren gewährleistet ist. Was tun bei Stromausfall? Wenn Redis standardmäßig konfiguriert ist und fsync jede Sekunde auf der Festplatte synchronisiert wird, ist es möglich, dass wir nach dem Neustart unseren Schlüssel verpassen. Wenn wir theoretisch die Sicherheit von Sperren bei einem Neustart der Instanz gewährleisten möchten, müssen wir dies aktivierenfsync=alwaysin den Einstellungen für die langfristige Datenspeicherung. Dadurch wird die Leistung auf das Niveau von CP-Systemen, die traditionell zur sicheren Implementierung verteilter Sperren verwendet werden, vollständig beeinträchtigt.



Aber die Situation ist besser als man denkt. Im Prinzip bleibt der Algorithmus sicher, da eine Instanz beim Neustart nach einem Fehler nicht mehr an einer derzeit aktiven Sperre teilnimmt.



Um dies zu gewährleisten, müssen wir nur sicherstellen, dass die Instanz nach einem Fehler für einen Zeitraum nicht verfügbar bleibt, der geringfügig über der von uns verwendeten maximalen TTL liegt. Wir werden also auf den Ablauf und die automatische Freigabe aller Schlüssel warten, die zum Zeitpunkt der Ablehnung aktiv waren.



Durch die Verwendung von verzögerten Neustarts ist es im Prinzip möglich, Sicherheit ohne langfristige Persistenz in Redis zu erreichen. Beachten Sie jedoch, dass dies zu einer Beeinträchtigung der Barrierefreiheit führen kann. Wenn beispielsweise die meisten Instanzen fehlschlagen, ist das System für die TTL-Zeit global nicht mehr verfügbar (und zu diesem Zeitpunkt kann keine Ressource blockiert werden).



Erhöhung der Verfügbarkeit des Algorithmus: Erweiterung der Sperre



Wenn die von Clients geleistete Arbeit aus kleinen Schritten besteht, ist es möglich, die Standardsperrdauer zu verkürzen und einen Mechanismus zum Erweitern von Sperren zu implementieren. Wenn der Client mit Berechnungen beschäftigt ist und der Wert für das Ablaufen der Sperre gefährlich niedrig ist, können Sie grundsätzlich allen Instanzen ein Skript in Lua senden, das die TTL des Schlüssels erweitert, sofern der Schlüssel noch vorhanden ist und sein Wert noch zufällig ist, der beim Erwerb der Sperre erhalten wurde.



Ein Kunde sollte eine Sperre nur dann als wiedererlangt betrachten, wenn er die meisten Instanzen innerhalb des Gültigkeitszeitraums erfolgreich gesperrt hat.



Technisch gesehen ändert sich der Algorithmus in diesem Fall jedoch nicht, sodass die maximale Anzahl wiederholter Versuche, Sperren zu erwerben, begrenzt werden sollte, da sonst die Zugänglichkeitseigenschaften verletzt werden.


More articles:


All Articles