Hey Habr!
Heute machen wir Sie auf die Übersetzung eines komplexen Artikels über die Implementierung verteilter Sperren mit Redis aufmerksam und laden Sie ein, über die Aussichten von Redis als Thema zu sprechen. Analyse des betreffenden Redlock-Algorithmus von Martin Kleppmann, Autor des Buches „", gegeben .
Verteiltes Sperren ist ein sehr nützliches Grundelement, das in vielen Umgebungen verwendet wird, in denen verschiedene Prozesse auf gemeinsam genutzte Ressourcen in gegenseitig ausschließender Weise 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 verfolgt einen anderen Ansatz und die Garantien, die sie bieten, sind recht schwach im Vergleich zu dem, was mit einem etwas ausgefeilteren Design erreichbar ist.
In diesem Artikel werden wir versuchen, einen bedingten kanonischen Algorithmus zu beschreiben, der zeigt, wie verteiltes Sperren mit Redis implementiert wird. Wir werden über einen Algorithmus namens sprechen RotlockeEs implementiert einen verteilten Sperrmanager und unserer Meinung nach ist dieser Algorithmus sicherer als der übliche Einzelinstanzansatz. Wir hoffen, dass die Community es analysiert, Feedback gibt und es als Ausgangspunkt für komplexere oder alternative Projekte nutzt.
Implementierungen
Bevor wir mit der Beschreibung des Algorithmus fortfahren, stellen wir mehrere Links zu vorgefertigten Implementierungen bereit. Sie können als Referenz verwendet werden.
- (Implementierung für Ruby). Es gibt auch Redlock-rb, das ein Paket (Gem) hinzufügt, um die Verteilung zu erleichtern, und nicht nur deshalb.
- (Python-Implementierung).
- (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 Async- und Lock-Erweiterungen.
- (Implementierung für C# .NET mit konfigurierbarem Datenspeicher)
- (Implementierung für C# .NET)
- (Implementierung für NodeJS). Inklusive Unterstützung für die Verlängerung von Schlössern.
Sicherheits- und Verfügbarkeitsgarantien
Wir werden unseren Entwurf mit nur drei Eigenschaften modellieren, von denen wir glauben, dass sie die Mindestgarantien bieten, die für die effektive Nutzung verteilter Sperren erforderlich sind.
- Sicherheitseigentum: Gegenseitiger Ausschluss. Zu jedem Zeitpunkt kann nur ein Client die Sperre halten.
- Verfügbarkeitseigenschaft A: Keine Deadlocks. Es ist immer möglich, irgendwann eine Sperre zu erhalten, auch wenn der Client, der die Ressource gesperrt hat, ausfällt oder auf einem anderen Festplattensegment landet.
- Verfügbarkeitseigenschaft B: Fehlertoleranz. Solange die meisten Redis-Knoten ausgeführt werden, können Clients Sperren erwerben und freigeben.
Warum eine auf Failure Recovery basierende Implementierung in diesem Fall nicht ausreicht
Um zu verstehen, was wir verbessern werden, analysieren wir den aktuellen Stand der Dinge mit den meisten verteilten Sperrbibliotheken, die auf Redis basieren.
Der einfachste Weg, eine Ressource mit Redis zu sperren, besteht darin, einen Schlüssel in der Instanz zu erstellen. Normalerweise wird ein Schlüssel mit einer begrenzten Lebensdauer erstellt. Dies wird mithilfe der in Redis bereitgestellten Ablauffunktion erreicht, sodass dieser Schlüssel früher oder später freigegeben wird (Eigenschaft 2 in unserer Liste). Wenn der Client die Ressource freigeben muss, löscht er den Schlüssel.
Auf den ersten Blick funktioniert diese Lösung recht gut, allerdings gibt es ein Problem: Unsere Architektur schafft einen Single Point of Failure. Was passiert, wenn die Host-Redis-Instanz ausfällt? Dann fügen wir einen Sklaven hinzu! Und wir werden es verwenden, wenn der Moderator nicht verfügbar ist. Leider ist diese Option nicht realisierbar. Auf diese Weise können wir die Eigenschaft des gegenseitigen Ausschlusses, die wir zur Gewährleistung der Sicherheit benötigen, nicht ordnungsgemäß implementieren, da die Replikation in Redis asynchron erfolgt.
Offensichtlich tritt in einem solchen Modell eine Rennbedingung auf:
- Client A erwirbt eine Sperre für den Master.
- Der Master fällt aus, bevor die Schlüsseleingabe an den Slave übertragen wird.
- Der Gefolgsmann wird zum Anführer befördert.
- Client B erwirbt eine Sperre für dieselbe Ressource, die A bereits gesperrt hat. SICHERHEITSVERLETZUNG!
Manchmal ist es völlig normal, dass unter besonderen Umständen, beispielsweise bei einem Ausfall, viele Clients gleichzeitig die Sperre halten können. In solchen Fällen kann eine replikationsbasierte Lösung angewendet werden. Ansonsten empfehlen wir die in diesem Artikel beschriebene Lösung.
Korrekte Implementierung mit einer einzelnen Instanz
Bevor wir versuchen, die oben beschriebenen Mängel der Einzelinstanzkonfiguration zu überwinden, wollen wir verstehen, wie dieser einfache Fall richtig gehandhabt wird, da diese Lösung tatsächlich in Anwendungen gültig ist, in denen von Zeit zu Zeit eine Race-Bedingung akzeptabel ist, und auch, weil das Blockieren auf einer Eine einzelne Instanz dient als Grundlage, die im hier beschriebenen verteilten Algorithmus verwendet wird.
Gehen Sie wie folgt 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 (NX-Option), mit einer Gültigkeitsdauer von 30000 Millisekunden (PX-Option). Der Schlüssel ist auf „myrandomvalue" Dieser Wert muss für alle Clients und alle Sperranforderungen eindeutig sein.
Grundsätzlich wird ein Zufallswert verwendet, um die Sperre sicher aufzuheben, wobei ein Skript Redis mitteilt: Entfernen Sie den Schlüssel nur, wenn er existiert 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
endDies ist wichtig, um zu verhindern, dass eine von einem anderen Client gehaltene Sperre entfernt wird. Beispielsweise könnte ein Client eine Sperre erwerben, dann bei einem Vorgang gesperrt werden, der länger dauert als die erste Sperre (so dass der Schlüssel ablaufen kann) und später die Sperre entfernen, die ein anderer Client platziert hat.
Die Verwendung eines einfachen DEL ist unsicher, da ein Client eine von einem anderen Client gehaltene Sperre entfernen kann. 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 Zufallszeichenfolge sein? Ich schätze, es sollte 20 Bytes von /dev/urandom entfernt sein, aber Sie können kostengünstigere Möglichkeiten finden, die Zeichenfolge für Ihre Zwecke eindeutig genug zu machen. Beispielsweise wäre es in Ordnung, RC4 mit /dev/urandom zu initialisieren und daraus dann einen pseudozufälligen Stream zu generieren. Eine einfachere Lösung beinhaltet eine Kombination aus Unix-Zeit in Mikrosekundenauflösung plus der Client-ID; Es ist nicht so sicher, aber in den meisten Fällen wahrscheinlich der Aufgabe gewachsen.
Die Zeit, die wir als Maß für die Lebensdauer des Schlüssels verwenden, wird als „Lebensdauer des Schlosses“ bezeichnet. Dieser Wert gibt sowohl die Zeitspanne an, bevor die Sperre automatisch aufgehoben wird, als auch die Zeitspanne, die ein Client hat, um einen Vorgang abzuschließen, bevor ein anderer Client wiederum diese Ressource sperren kann, ohne tatsächlich gegen gegenseitige Ausschlussgarantien zu verstoßen. Diese Garantie ist nur auf ein bestimmtes Zeitfenster beschränkt, das mit dem Kauf des Schlosses beginnt.
Deshalb haben wir eine gute Möglichkeit besprochen, eine Sperre zu erwerben und aufzuheben. Das System (wenn es sich um ein nicht verteiltes System handelt, das aus einer einzigen und immer verfügbaren Instanz besteht) ist sicher. Erweitern wir dieses Konzept auf ein verteiltes System, in dem wir keine derartigen Garantien haben.
Redlock-Algorithmus
Die verteilte Version des Algorithmus geht davon aus, dass wir N Redis-Master haben. Diese Knoten sind völlig unabhängig voneinander, daher verwenden wir keine Replikation oder ein anderes implizites Koordinationssystem. Wir haben bereits erläutert, wie Sie eine Sperre für eine einzelne Instanz sicher erwerben und freigeben. Wir gehen davon aus, dass der Algorithmus, wenn er mit einer einzelnen Instanz arbeitet, genau diese Methode verwendet. In unseren Beispielen haben wir N auf 5 gesetzt, was ein sinnvoller Wert ist. Daher müssen wir 5 Redis-Master auf verschiedenen Computern oder virtuellen Maschinen einsetzen, um sicherzustellen, dass diese weitgehend unabhängig voneinander agieren.
Um eine Sperre zu erhalten, führt der Client die folgenden Vorgänge aus:
- Ruft die aktuelle Zeit in Millisekunden ab.
- Versucht nacheinander, eine Sperre für alle N Instanzen zu erhalten, wobei in allen Fällen derselbe Schlüsselname und die gleichen Zufallswerte verwendet werden. Wenn der Client in Stufe 2 eine Sperre pro Instanz einrichtet, verwendet der Client eine Verzögerung, um sie zu erhalten, die kurz genug ist im Vergleich zu der Zeit, nach der die Sperre automatisch aufgehoben wird. Wenn die Blockierungsdauer beispielsweise 10 Sekunden beträgt, kann die Verzögerung im Bereich von etwa 5 bis 50 Millisekunden liegen. Dadurch entfällt die Situation, in der der Client möglicherweise längere Zeit blockiert bleibt und versucht, einen ausgefallenen Redis-Knoten zu erreichen: Wenn die Instanz nicht verfügbar ist, versuchen wir, so schnell wie möglich eine Verbindung zu einer anderen Instanz herzustellen.
- Um eine Sperre auszuführen, berechnet der Client, wie viel Zeit vergangen ist. Dazu subtrahiert es vom tatsächlichen Zeitwert den Zeitstempel, der in Schritt 1 erhalten wurde. Dies gilt nur dann, wenn der Client in der Lage war, die Sperre für die meisten Instanzen (mindestens 3) zu erhalten, und wie viel Zeit dafür insgesamt gedauert hat Wenn die Sperrdauer kürzer ist, gilt die Sperre als erhalten.
- Wenn eine Sperre erworben wurde, wird die Sperrdauer als die ursprüngliche Sperrdauer abzüglich der in Schritt 3 berechneten verstrichenen Zeit angenommen.
- Wenn der Client die Sperre aus irgendeinem Grund nicht erhält (entweder konnte er N/2+1 Instanzen nicht sperren oder die Sperrdauer war negativ), versucht er, alle Instanzen zu entsperren (auch diejenigen, von denen er dachte, dass er sie nicht blockieren könnte). ).
Ist der Algorithmus asynchron?
Dieser Algorithmus basiert auf der Annahme, dass, obwohl es keine synchronisierte Uhr gibt, auf der alle Prozesse funktionieren würden, die lokale Zeit in jedem Prozess immer noch ungefähr im gleichen Tempo fließt und der Fehler im Vergleich zur Gesamtzeit, nach der die Sperre erfolgt, gering ist automatisch freigegeben. Diese Annahme ist der für gewöhnliche Computer typischen Situation sehr ähnlich: Jeder Computer verfügt über eine lokale Uhr, und wir können uns normalerweise darauf verlassen, dass der Zeitunterschied zwischen verschiedenen Computern gering ist.
An dieser Stelle müssen wir unsere Regel zum gegenseitigen Ausschluss sorgfältiger formulieren: Der gegenseitige Ausschluss ist nur dann garantiert, wenn der Client, der die Sperre hält, während der Gültigkeitsdauer der Sperre (dieser Wert wird in Schritt 3 ermittelt) abzüglich etwas mehr Zeit (insgesamt einige) austritt Millisekunden, um den Zeitunterschied zwischen Prozessen auszugleichen).
Der folgende interessante Artikel erzählt mehr über solche Systeme, die eine Koordination von Zeitintervallen erfordern: .
Bei Fehler erneut versuchen
Wenn es einem Client nicht gelingt, eine Sperre zu erhalten, muss er es nach einer zufälligen Verzögerung erneut versuchen. Dies geschieht, um mehrere Clients zu desynchronisieren, die gleichzeitig versuchen, eine Sperre für dieselbe Ressource zu erlangen (was zu einer „Split-Brain“-Situation führen kann, in der es keine Gewinner gibt). Darüber hinaus gilt: Je schneller ein Client versucht, eine Sperre für die meisten Redis-Instanzen zu erhalten, desto enger ist das Zeitfenster, in dem eine Split-Brain-Situation auftreten kann (und desto geringer ist der Bedarf an Wiederholungsversuchen). Daher sollte der Client im Idealfall versuchen, SET-Befehle mithilfe von Multiplexing gleichzeitig an N Instanzen zu senden.
An dieser Stelle muss betont werden, wie wichtig es für Clients ist, denen es nicht gelingt, die meisten Sperren zu erhalten, die (teilweise) erworbenen Sperren freizugeben, sodass sie nicht auf das Ablaufen des Schlüssels warten müssen, bevor die Sperre für die Ressource erneut erworben werden kann (Wenn jedoch eine Netzwerkfragmentierung auftritt und der Client den Kontakt zu den Redis-Instanzen verliert, müssen Sie eine Verfügbarkeitsstrafe zahlen, während Sie auf den Ablauf des Schlüssels warten).
Lösen Sie die Sperre
Das Aufheben einer Sperre ist ein einfacher Vorgang, der lediglich das Entsperren aller Instanzen erfordert, unabhängig davon, ob der Client eine bestimmte Instanz offenbar erfolgreich gesperrt hat.
Sicherheitsüberlegungen
Ist der Algorithmus sicher? Versuchen wir uns vorzustellen, was in verschiedenen Szenarien passiert.
Nehmen wir zunächst an, dass der Client für die meisten Instanzen eine Sperre erhalten konnte. Jede Instanz enthält einen Schlüssel mit der gleichen Lebensdauer für alle. Allerdings wurde jeder dieser Schlüssel zu einem anderen Zeitpunkt installiert und läuft daher zu unterschiedlichen Zeiten ab. Wenn jedoch der erste Schlüssel zu einem Zeitpunkt installiert wurde, der nicht schlechter als T1 war (der Zeitpunkt, den wir wählen, bevor wir den ersten Server kontaktieren), und der letzte Schlüssel zu einem Zeitpunkt installiert wurde, der nicht schlechter als T2 war (der Zeitpunkt, zu dem die Antwort empfangen wurde). vom letzten Server), dann sind wir zuversichtlich, dass zumindest der erste Schlüssel im Satz, der abläuft, überleben wird MIN_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 diesen Zeitraum gleichzeitig gültig sind.
Während die meisten Schlüssel gültig bleiben, kann ein anderer Client die Sperre nicht erwerben, da N/2+1 SET NX-Vorgänge nicht erfolgreich sein können, wenn bereits N/2+1 Schlüssel vorhanden sind. Daher ist es unmöglich, eine einmal erworbene Sperre im selben Moment erneut zu erwerben (dies würde die Eigenschaft des gegenseitigen Ausschlusses verletzen).
Wir möchten jedoch sicherstellen, dass mehrere Clients, die gleichzeitig versuchen, eine Sperre zu erhalten, nicht gleichzeitig erfolgreich sein können.
Wenn der Client die meisten Instanzen für etwa oder länger als die maximale Sperrdauer gesperrt hat, betrachtet er die Sperre als ungültig und entsperrt die Instanzen. Daher müssen wir nur den Fall berücksichtigen, in dem es dem Kunden gelungen ist, die meisten Instanzen in einer Zeit zu blockieren, die unter dem Ablaufdatum liegt. In diesem Fall, in Bezug auf das obige Argument, während der Zeit MIN_VALIDITY Kein Client sollte in der Lage sein, die Sperre erneut zu erhalten. Daher können viele Clients N/2+1 Instanzen gleichzeitig (was am Ende von Stufe 2 endet) nur dann sperren, wenn die Zeit zum Sperren der Mehrheit länger als die TTL-Zeit war, was die Sperre ungültig macht.
Können Sie einen formellen Sicherheitsnachweis vorlegen, auf vorhandene ähnliche Algorithmen hinweisen oder einen Fehler im oben genannten finden?
Überlegungen zur Barrierefreiheit
Die Systemverfügbarkeit hängt von drei Hauptmerkmalen ab:
- Schlösser automatisch freigeben (wenn Schlüssel ablaufen): Schlüssel stehen irgendwann wieder zur Verfügung, um für Schlösser verwendet zu werden.
- Die Tatsache, dass Kunden sich in der Regel gegenseitig helfen, indem sie Sperren entfernen, wenn die gewünschte Sperre nicht erworben wurde oder erworben wurde und die Arbeit abgeschlossen wurde; Es ist also wahrscheinlich, dass wir nicht warten müssen, bis die Schlüssel abgelaufen sind, um das Schloss wieder zu erhalten.
- Die Tatsache, dass ein Client, wenn er erneut versuchen muss, eine Sperre zu erhalten, vergleichsweise länger wartet als für die meisten Sperren erforderlich ist. Dies verringert die Wahrscheinlichkeit, dass es im Wettbewerb um Ressourcen zu einer Split-Brain-Situation kommt.
Es gibt jedoch eine Verfügbarkeitseinbuße in Höhe der TTL der Netzwerksegmente. Wenn also zusammenhängende Segmente vorhanden sind, kann die Einbuße unbegrenzt sein. Dies geschieht immer dann, wenn ein Client eine Sperre erwirbt und sich dann auf ein anderes Segment ausbreitet, bevor er sie freigeben kann.
Prinzipiell kann ein System bei unendlich vielen zusammenhängenden Netzwerksegmenten für einen unendlichen Zeitraum nicht verfügbar bleiben.
Leistung, Failover und Fsync
Viele Menschen verwenden Redis, weil sie eine hohe Sperrserverleistung im Hinblick auf die erforderliche Latenz zum Erwerb und Freigeben von Sperren und die Anzahl der Erwerbe/Freigaben, die pro Sekunde durchgeführt werden können, benötigen. Um diese Anforderung zu erfüllen, gibt es eine Strategie zur Kommunikation mit N Redis-Servern, um die Latenz zu reduzieren. Dies ist eine Multiplexing-Strategie (oder „Multiplexing des armen Mannes“, bei der der Socket in den nicht blockierenden Modus versetzt wird, alle Befehle sendet und die Befehle später liest, vorausgesetzt, dass die Umlaufzeit zwischen dem Client und jeder Instanz ähnlich ist). .
Allerdings müssen wir auch die mit der langfristigen Datenspeicherung verbundenen Überlegungen berücksichtigen, wenn wir ein Modell mit zuverlässiger Wiederherstellung nach Ausfällen anstreben.
Um das Problem zu klären, gehen wir grundsätzlich davon aus, dass wir Redis ohne jegliche langfristige Datenspeicherung konfigurieren. Dem Client gelingt es, 3 von 5 Instanzen zu blockieren. Eine der Instanzen, die der Client blockieren konnte, wird neu gestartet, und in diesem Moment gibt es wieder drei Instanzen für dieselbe Ressource, die wir blockieren können, und ein anderer Client kann wiederum die neu gestartete Instanz blockieren und damit die Sicherheitseigenschaft verletzen geht von der Exklusivität der Schlösser aus.
Wenn Sie Data-Ahead (AOF) aktivieren, wird sich die Situation leicht verbessern. Sie können beispielsweise einen Server heraufstufen, indem Sie den Befehl SHUTDOWN senden und ihn neu starten. Da Ablaufoperationen in Redis semantisch so implementiert sind, dass die Zeit auch dann weiterfließt, wenn der Server ausgeschaltet ist, sind alle unsere Anforderungen in Ordnung. Dies ist normal, solange ein normaler Shutdown gewährleistet ist. Was tun bei Stromausfällen? Wenn Redis standardmäßig so konfiguriert ist, dass fsync jede Sekunde auf der Festplatte synchronisiert, ist es möglich, dass wir nach einem Neustart unseren Schlüssel nicht mehr haben. Wenn wir die Sperrsicherheit bei jedem Instanzneustart garantieren wollen, sollten wir theoretisch die Sperre aktivieren fsync=always in den Einstellungen zur Langzeitdatenspeicherung. Dadurch wird die Leistung vollständig beeinträchtigt, bis hin zu CP-Systemen, die traditionell zur sicheren Implementierung verteilter Sperren verwendet werden.
Doch die Situation ist besser, als es auf den ersten Blick scheint. Grundsätzlich bleibt die Sicherheit des Algorithmus erhalten, da die Instanz bei einem Neustart nach einem Ausfall nicht mehr an einer aktuell aktiven Sperre teilnimmt.
Um dies sicherzustellen, müssen wir lediglich sicherstellen, dass die Instanz nach einem Ausfall für einen Zeitraum nicht verfügbar bleibt, der geringfügig über der von uns verwendeten maximalen TTL liegt. Auf diese Weise warten wir bis zum Ablaufdatum und der automatischen Freigabe aller Schlüssel, die zum Zeitpunkt des Fehlers aktiv waren.
Durch verzögerte Neustarts ist es prinzipiell möglich, Sicherheit auch ohne langfristige Persistenz in Redis zu erreichen. Beachten Sie jedoch, dass dies zu einem Bußgeld wegen Verstoßes gegen die Barrierefreiheit führen kann. Wenn beispielsweise die meisten Instanzen ausfallen, ist das System für die TTL global nicht verfügbar (und während dieser Zeit kann keine Ressource blockiert werden).
Wir erhöhen die Verfügbarkeit des Algorithmus: Wir erweitern die Blockierung
Wenn die von Clients ausgeführte Arbeit aus kleinen Schritten besteht, ist es möglich, die standardmäßige Sperrdauer zu reduzieren und einen Mechanismus zum Erweitern von Sperren zu implementieren. Wenn der Client mit dem Rechnen beschäftigt ist und der Sperrenablaufwert gefährlich niedrig ist, können Sie im Prinzip ein Lua-Skript an alle Instanzen senden, das die TTL des Schlüssels erweitert, sofern der Schlüssel noch existiert und sein Wert immer noch ein zufälliger Wert ist, der erhalten wird, wenn der Schloss erworben wurde.
Ein Client sollte die erneute Erlangung einer Sperre nur dann in Betracht ziehen, wenn es ihm gelungen ist, die meisten Instanzen innerhalb des Gültigkeitszeitraums zu sperren.
Technisch gesehen ändert sich der Algorithmus zwar nicht, daher muss die maximale Anzahl wiederholter Versuche, Sperren zu erhalten, begrenzt werden, da andernfalls die Barrierefreiheitseigenschaften verletzt werden.
Source: habr.com