Hallo, Habr!
Heute präsentieren wir Ihnen eine anspruchsvolle Übersetzung eines Artikels über die Implementierung von verteilten Sperren mit Redis und diskutieren die Perspektiven von Redis als Thema. Die Analyse des besprochenen Redlock-Algorithmus von Martin Kleppmann, dem Autor des Buches "", wird vorgestellt .
Verteilte Sperren sind ein sehr nützliches Konzept, das in vielen Umgebungen angewendet wird, in denen verschiedene Prozesse an gemeinsamen Ressourcen im Sinne der gegenseitigen Exklusion arbeiten müssen.
Es gibt eine Reihe von Bibliotheken und Artikeln, die beschreiben, wie man DLM (Distributed Lock Manager) mit Redis implementiert, wobei jedoch jede Bibliothek ihren eigenen Ansatz verwendet und die dabei gegebenen Garantien im Vergleich zu dem, was durch etwas aufwendigeres Design erreicht werden kann, recht schwach sind.
In diesem Artikel werden wir versuchen, einen bedingt kanonischen Algorithmus zu beschreiben, der demonstriert, wie man verteilte Sperren mit Redis implementiert. Wir werden über den Algorithmus namens Redlock, er implementiert einen Manager für verteilte Sperren und, unserer Meinung nach, ist dieser Algorithmus sicherer als der herkömmliche Ansatz mit einer einzelnen Instanz. Wir hoffen, dass die Gemeinschaft ihn analysiert, Feedback gibt und ihn als Ausgangspunkt für die Umsetzung komplexerer oder alternativer Projekte nutzt.
Implementierungen
Bevor wir zur Beschreibung des Algorithmus übergehen, möchten wir einige Links zu bereits vorhandenen Implementierungen bereitstellen. Diese können als Referenz genutzt werden.
- (Implementierung für Ruby). Es gibt auch Redlock-rb, das ein Paket (Gem) für eine einfache Verteilung hinzufügt und 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 Async- und Lock-Erweiterungen.
- (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.
Sicherheits- und Verfügbarkeitsgarantien
Wir planen, unser Projekt nur mit drei Eigenschaften zu modellieren, die unserer Meinung nach die minimalen Garantien bieten, die für die effektive Nutzung verteilter Sperren erforderlich sind.
- Sicherheitseigenschaft: Gegenseitiger Ausschluss. Zu jedem Zeitpunkt kann nur ein Client eine Sperre halten.
- Verfügbarkeitsmerkmal A: Abwesenheit von Deadlocks. Letztendlich kann immer eine Sperre erlangt werden, selbst wenn der Client, der die Ressource gesperrt hat, ausfällt oder in einen anderen Festplattensegment wechselt.
- Verfügbarkeitsmerkmal B: Fehlertoleranz. Solange die Mehrheit der Redis-Knoten funktioniert, können Clients Sperren erwerben und freigeben.
Warum eine auf Fehlertoleranz basierende Implementierung in diesem Fall nicht ausreicht
Um zu verstehen, was wir verbessern möchten, lassen Sie uns die aktuelle Situation der meisten Bibliotheken für verteilte Sperren, die auf Redis basieren, analysieren.
Die einfachste Möglichkeit, 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, was durch die in Redis vorgesehene expires-Funktionalität erreicht wird. Daher wird dieser Schlüssel irgendwann freigegeben (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 gut, aber es gibt ein Problem: In unserer Architektur gibt es einen einzelnen Punkt des Fehlers. Was passiert, wenn die Hauptinstanz von Redis ausfällt? Lassen Sie uns dann eine Sekundärinstanz hinzufügen! Wir werden sie benutzen, wenn die Hauptinstanz nicht verfügbar ist. Leider ist diese Option nicht praktikabel. Dadurch können wir die für die Sicherheit erforderliche Eigenschaft der wechselseitigen Ausschluss nicht richtig implementieren, da die Replikation in Redis asynchron ist.
Es ist offensichtlich, dass in einem solchen Modell ein Konkurrenzzustand entsteht:
- Client A erwirbt die Sperre auf dem Hauptserver.
- Der Hauptserver fällt aus, bevor der Eintrag im Schlüssel an den Sekundärserver übertragen wird.
- Der Sekundärserver wird zum Hauptserver.
- Client B erwirbt die Sperre für dieselbe Ressource, die bereits von A gesperrt ist. SICHERHEITSVERLETZUNG!
Es ist manchmal völlig normal, dass in besonderen Umständen, wie bei einem Ausfall, viele Kunden gleichzeitig eine Sperre halten können. In solchen Fällen kann eine Lösung auf Basis von Replikation angewendet werden. In anderen Fällen empfehlen wir die in diesem Artikel beschriebene Lösung.
Die korrekte Implementierung mit einer einzelnen Instanz
Bevor wir versuchen, die Mängel der oben beschriebenen Konfiguration mit einer einzigen Instanz zu überwinden, lassen Sie uns verstehen, wie wir in diesem einfachen Fall richtig handeln, da eine solche Lösung tatsächlich in Anwendungen zulässig ist, in denen Zustandsrennen gelegentlich akzeptabel sind, und auch, weil die Sperre auf einer einzelnen Instanz die Grundlage für den hier beschriebenen verteilten Algorithmus bildet.
Um die Sperre zu erwerben, verfahren wir wie folgt:
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 Kunden und aller Sperranfragen einzigartig sein.
Im Prinzip wird ein zufälliger Wert verwendet, um eine sichere Freigabe der Sperre zu gewährleisten, indem ein Skript an Redis gesendet wird: Lösche den Schlüssel nur, wenn er existiert, und der gespeicherte Wert genau das ist, was erwartet wurde. Dies wird mit folgendem Lua-Skript erreicht:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endEs ist wichtig, um zu verhindern, dass eine Sperre, die von einem anderen Client gesetzt wurde, entfernt wird. Zum Beispiel kann ein Client eine Sperre erwerben, dann während einer Operation, die länger dauert als die Gültigkeitsdauer der ersten Sperre, blockiert werden (sodass die Gültigkeitsdauer des Schlüssels abläuft) und später die Sperre entfernen, die von einem anderen Client gesetzt wurde.
Die Verwendung eines einfachen DEL ist unsicher, da ein Client die Sperre entfernen kann, die von einem anderen Client gesetzt wurde. Im Gegensatz dazu ist bei der Verwendung des oben genannten Skripts jede Sperre mit einer zufälligen Zeichenfolge „unterzeichnet“, sodass nur der Client, der sie zuvor gesetzt hat, sie entfernen kann.
Was sollte diese zufällige Zeichenkette sein? Ich nehme an, es sollten 20 Bytes aus /dev/urandom sein, aber es gibt auch kostengünstigere Möglichkeiten, um eine ausreichend einzigartige Zeichenkette für Ihre Zwecke zu erstellen. Zum Beispiel wäre es in Ordnung, RC4 mit /dev/urandom zu säen und dann einen pseudorandomisierten Stream daraus zu generieren. Eine einfachere Lösung besteht in einer Kombination aus Unix-Zeit im Mikrosekundenbereich und der Kunden-ID; diese ist nicht ganz so sicher, erfüllt aber wahrscheinlich die Anforderungen der meisten Kontexte.
Die Zeit, die wir als Lebenszeit des Schlüssels verwenden, wird als „Sperrzeit“ bezeichnet. Dieser Wert ist gleichzeitig der Zeitraum, nach dem die Sperre automatisch freigegeben wird, und die Zeit, die der Kunde hat, um die Operation auszuführen, bevor ein anderer Kunde in der Lage ist, diese Ressource zu sperren, ohne die Garantien der wechselseitigen Ausschlussbedingungen tatsächlich 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, um ein Lock zu erwerben und freizugeben. Das System (sofern es sich um ein nicht verteiltes System mit einer einzigen, immer verfügbaren Instanz handelt) ist sicher. Lassen Sie uns dieses Konzept auf ein verteiltes System erweitern, in dem wir diese Garantien nicht haben.
Redlock-Algorithmus
In der verteilten Version des Algorithmus nehmen wir an, dass wir N führende Redis-Instanzen haben. Diese Knoten sind vollständig unabhängig voneinander, daher verwenden wir keine Replikation oder andere implizite Koordinationssysteme. Wir haben bereits erklärt, wie man sicher ein Lock auf einer einzelnen Instanz erwirbt und freigibt. Wir nehmen 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 müssen wir 5 führende Redis-Instanzen auf verschiedenen Computern oder virtuellen Maschinen verwenden, um sicherzustellen, dass sie im Wesentlichen unabhängig von einander arbeiten.
Um ein Lock zu erwerben, führt der Client die folgenden Operationen aus:
- Erhält die aktuelle Zeit in Millisekunden.
- Versucht nacheinander, ein Lock auf alle N Instanzen zu setzen, indem er in jedem Fall denselben Schlüsselnamen und zufällige Werte verwendet. In Phase 2, beim Setzen des Locks für jede Instanz, verwendet der Client eine Verzögerung, die im Vergleich zu der Zeit, nach der der Lock automatisch aufgehoben wird, ausreichend kurz ist. Zum Beispiel, wenn die Lock-Dauer 10 Sekunden beträgt, könnte die Verzögerung im Bereich von ~ 5-50 Millisekunden liegen. Dadurch wird die Situation ausgeschlossen, in der der Client lange blockiert bleibt und versucht, sich mit einem ausgefallenen Redis-Knoten zu verbinden: Wenn die Instanz nicht verfügbar ist, versuchen wir so schnell wie möglich, eine Verbindung zu einer anderen Instanz herzustellen.
- Um eine Sperre zu erhalten, berechnet der Kunde, wie viel Zeit vergangen ist; dazu subtrahiert er den Zeitstempel, der in Schritt 1 erhalten wurde, vom aktuellen Zeitwert. Nur wenn der Kunde die Sperre auf den meisten Instanzen (mindestens 3) erhalten hat und die insgesamt benötigte Zeit, um die Sperre zu erhalten, kürzer ist als die Gültigkeitsdauer der Sperre, gilt der Erhalt der Sperre als erfolgreich.
- Wenn die Sperre erhalten wurde, wird die Gültigkeitsdauer auf den ursprünglichen Wert der Sperrdauer minus der in Schritt 3 berechneten verstrichenen Zeit festgelegt.
- Wenn der Kunde aus irgendeinem Grund die Sperre nicht erhalten konnte (entweder weil er nicht N/2+1 Instanzen sperren konnte oder weil die Gültigkeitsdauer der Sperre negativ war), versucht er, alle Instanzen zu entsperren (auch die, von denen er dachte, dass er sie nicht sperren konnte).
Ist der Algorithmus asynchron?
Dieser Algorithmus basiert auf der Annahme, dass, obwohl es keine synchronisierten Uhren gibt, an denen alle Prozesse arbeiten, die lokale Zeit in jedem Prozess immer noch in etwa im gleichen Tempo verläuft und die Ungenauigkeit im Vergleich zur Gesamtzeit gering ist, nach der die Sperre automatisch aufgehoben wird. Diese Annahme ähnelt sehr einer Situation, die für herkömmliche Computer typisch ist: Jeder Computer hat ein lokales Uhrwerk, und normalerweise können wir darauf zählen, dass die Zeitabweichung zwischen verschiedenen Computern gering ist.
An diesem Punkt müssen wir unser Ausschlussregel genauer formulieren: Der Ausschluss ist nur garantiert, wenn der Client, der die Sperre hält, seine Aufgabe innerhalb der Zeit, in der die Sperre gültig ist (dieser Wert wurde in Schritt 3 ermittelt), plus noch etwas Zeit (nur einige Millisekunden, um die Zeitabweichung zwischen den Prozessen auszugleichen), abschließt.
Mehr über solche Systeme, die die Synchronisation von Zeitabweichungen erfordern, erfahren Sie in dem folgenden interessanten Artikel: .
Wiederholter Versuch bei Ablehnung
Wenn ein Kunde den Lock nicht erhalten konnte, sollte er es erneut versuchen, nachdem er eine zufällige Verzögerung eingehalten hat; dies geschieht, um mehrere Kunden, die gleichzeitig versuchen, den Lock für dieselbe Ressource zu erwerben, zu desynchronisieren (was zu einer Situation des „split-brain“ führen kann, in der es keine Gewinner gibt). Je schneller der Kunde versucht, den Lock für die meisten Redis-Instanzen zu erwerben, desto enger ist das Fenster, in dem die „split-brain“-Situation auftreten kann (und desto weniger müssen Wiederholungsversuche unternommen werden). Daher sollte der Kunde idealerweise gleichzeitig versuchen, SET-Befehle an N Instanzen über Multiplexing zu senden.
Hier ist es wichtig zu betonen, wie entscheidend es ist, dass Kunden, die die meisten Sperren nicht erwerben konnten, ihre (teilweise) erworbenen Sperren freigeben, um nicht auf das Ablaufen des Schlüssels warten zu müssen, bevor die Sperre auf die Ressource erneut erworben werden kann (allerdings, falls es zu einer Fragmentierung des Netzwerks kommt und der Kunde die Verbindung zu den Redis-Instanzen verliert, fällt eine Strafe für Verfügbarkeitsverletzung an, während das Ablaufen des Schlüssels abgewartet wird).
Sperre freigeben
Das Freigeben einer Sperre ist ein einfacher Vorgang, bei dem einfach alle Instanzen entsperrt werden müssen, unabhängig davon, ob der Kunde denkt, dass er eine bestimmte Instanz erfolgreich gesperrt hat.
Sicherheitsüberlegungen
Ist der Algorithmus sicher? Lassen Sie uns überlegen, was in verschiedenen Szenarien passiert.
Zunächst nehmen wir an, dass der Kunde die Kontrolle über die meisten Instanzen erhalten hat. Jede dieser Instanzen wird einen Schlüssel mit derselben Lebensdauer für alle enthalten. Allerdings wurde jeder dieser Schlüssel zu einem unterschiedlichen Zeitpunkt gesetzt, sodass ihre Gültigkeitsdauer zu unterschiedlichen Zeiten abläuft. Wenn der erste Schlüssel jedoch zu einem Zeitpunkt nicht schlechter als T1 (der Zeitpunkt, den wir vor der Kontaktaufnahme mit dem ersten Server wählen) gesetzt wurde und der letzte Schlüssel zu einem Zeitpunkt nicht schlechter als T2 (der Zeitpunkt, zu dem die Antwort vom letzten Server eingegangen ist) gesetzt wurde, sind wir sicher, dass der erste Schlüssel in der Menge, deren Gültigkeit abläuft, mindestens so lange bestehen bleibt MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Alle anderen Schlüssel laufen später ab, sodass wir sicher sein können, dass alle Schlüssel während dieses Zeitraums gleichzeitig 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 abgeschlossen werden können, wenn bereits N/2+1 Schlüssel existieren. Daher ist es unmöglich, die Sperre erneut zu erwerben, wenn sie einmal erworben wurde (das würde das Prinzip der gegenseitigen Ausschließung verletzen).
In der Tat möchten wir sicherstellen, dass eine Vielzahl von Kunden, die versuchen, eine Sperre gleichzeitig zu erwerben, dies nicht gleichzeitig erfolgreich tun kann.
Wenn ein Kunde die meisten Instanzen gesperrt hat und dafür ungefähr oder mehr als die maximale Sperrdauer benötigt hat, wird er die Sperre für ungültig halten und die Instanzen entsperren. Daher müssen wir nur den Fall berücksichtigen, in dem es dem Kunden gelungen ist, die meisten Instanzen innerhalb eines kürzeren Zeitrahmens als der Gültigkeitsdauer zu sperren. In diesem Fall, was das obige Argument betrifft, innerhalb des Zeitraums MIN_VALIDITY Kein Kunde sollte in der Lage sein, eine Sperre erneut zu erlangen. Daher können viele Kunden N/2+1 Instanzen gleichzeitig sperren (was am Ende der Phase 2 endet), nur wenn die Zeit für die Sperre der Mehrheit länger war als die TTL-Zeit, wodurch die Sperre ungültig wird.
Können Sie einen formalen Sicherheitsnachweis führen, ähnliche Algorithmen angeben oder einen Fehler in der Beschreibung finden?
Überlegungen zur Verfügbarkeit
Die Verfügbarkeit des Systems hängt von drei Hauptmerkmalen ab:
- Automatisches Aufheben der Sperre (da die Gültigkeit der Schlüssel abläuft): Letztendlich werden die Schlüssel erneut verfügbar sein, um für Sperren verwendet zu werden.
- Die Tatsache, dass Kunden sich normalerweise gegenseitig helfen, indem sie Sperren aufheben, wenn die benötigte Sperre nicht erworben wurde oder bereits erworben wurde und die Arbeit abgeschlossen ist; daher ist es wahrscheinlich, dass wir nicht auf das Verfallen der Schlüssel warten müssen, um die Sperre erneut zu erwerben.
- Die Tatsache, dass ein Kunde, wenn er erneut versucht, eine Sperre zu erlangen, vergleichsweise länger wartet als der Zeitraum, der erforderlich ist, um die meisten Sperren zu erwerben. Dadurch wird die Wahrscheinlichkeit einer Wettbewerbssituation um Ressourcen verringert.
Allerdings muss eine Strafe für die verringerten Verfügbarkeiten gezahlt werden, die der TTL-Zeit in Netzwerkssegmenten entspricht. Wenn es also kontinuierliche Segmente gibt, kann diese Strafe unbestimmte Dimensionen erreichen. Dies geschieht jedes Mal, wenn ein Kunde eine Sperre erwirbt und dann in ein anderes Segment abgeschnitten wird, bevor er sie freigeben kann.
Im Prinzip kann das System bei unendlichen kontinuierlichen Netzwerksegmenten für unbestimmte Zeit nicht verfügbar bleiben.
Performance, Wiederherstellung nach einem Ausfall und fsync
Viele setzen Redis ein, da eine hohe Serverleistung bei der Handhabung von Sperren erforderlich ist, sowohl in Bezug auf die Latenzzeiten für den Erwerb und die Freigabe von Sperren als auch auf die Anzahl der Operationen, die pro Sekunde durchgeführt werden können. Um diesen Anforderungen gerecht zu werden, gibt es eine Kommunikationsstrategie mit N Redis-Servern, um die Latenz zu reduzieren. Diese Strategie wird als Multiplexing bezeichnet (oder auch als "Arme-Leute-Multiplexing", bei dem der Socket in den nicht-blockierenden Modus versetzt wird, alle Befehle gesendet werden und die Antworten später gelesen werden, wobei davon ausgegangen wird, dass die Rundenzeiten zwischen dem Client und jedem der Instanzen ähnlich sind).
Es ist jedoch auch zu berücksichtigen, dass wir, wenn wir ein Modell mit verlässlichem Wiederherstellungsvermögen nach Ausfällen entwickeln wollen, das Thema der langfristigen Datenspeicherung ansprechen müssen.
Um das Problem zu klären, nehmen wir an, dass wir Redis ohne persistente Datenspeicherung konfigurieren. Der Kunde schafft es, 3 von 5 Instanzen zu sperren. Eine der Instanzen, die der Kunde sperren konnte, wird neu gestartet, und in diesem Moment entstehen erneut 3 Instanzen für dieselbe Ressource, die wir sperren können, und ein anderer Kunde kann wiederum die neu gestartete Instanz sperren, was das Sicherheitsmerkmal verletzt, das die Exklusivität der Sperren voraussetzt.
Wenn das vorzeitige Speichern von Daten (AOF) aktiviert ist, verbessert sich die Situation etwas. Beispielsweise kann der Server erhöht werden, indem der SHUTDOWN-Befehl gesendet und neu gestartet wird. Da Ablaufoperationen in Redis semantisch so implementiert sind, dass die Zeit auch beim Herunterfahren des Servers weiterläuft, sind alle unsere Anforderungen erfüllt. Unter der Voraussetzung, dass ein ordnungsgemäßer Shutdown gewährleistet ist, ist alles in Ordnung. Aber was ist im Falle eines Stromausfalls? Wenn Redis standardmäßig konfiguriert ist, mit fsync-Synchronisierung auf die Festplatte jede Sekunde, dann kann es nach dem Neustart sein, dass wir 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 zur langfristigen Datenspeicherung aktivieren. Dies wird die Leistung drastisch beeinträchtigen, auf das Niveau solcher CP-Systeme, die traditionell für die sichere Implementierung verteilter Sperren verwendet werden.
Die Situation ist jedoch besser, als sie auf den ersten Blick erscheint. Grundsätzlich bleibt die Sicherheit des Algorithmus erhalten, da ein Instanz nach einem Ausfall nicht mehr an einer aktiven Sperre beteiligt ist.
Um dies zu gewährleisten, muss lediglich sichergestellt werden, dass die Instanz nach einem Ausfall für einen Zeitraum, der etwas über dem maximalen TTL liegt, nicht verfügbar bleibt. So warten wir auf das Ablaufen der Frist und die automatische Freigabe aller Schlüssel, die zum Zeitpunkt des Ausfalls aktiv waren.
Durch die Verwendung von verzögerten Neustarts ist es im Prinzip möglich, Sicherheit auch ohne eine dauerhafte Speicherung in Redis zu erreichen. Allerdings sollte angemerkt werden, dass dies zu einem Verstoß gegen die Verfügbarkeit führen kann. Zum Beispiel wird das System bei einem Ausfall der meisten Instanzen während der TTL global nicht verfügbar sein (und in dieser Zeit kann kein Ressource gesperrt werden).
Erhöhung der Verfügbarkeit des Algorithmus: Verlängerung der Sperre
Wenn die von den Kunden ausgeführten Arbeiten aus kleinen Phasen bestehen, kann die standardmäßig festgelegte Blockierungszeit verkürzt und ein Mechanismus zur Verlängerung der Blockierungen implementiert werden. Grundsätzlich kann, wenn der Kunde mit Berechnungen beschäftigt ist und die Blockierungsdauer gefährlich abnimmt, ein Lua-Skript an alle Instanzen gesendet werden, das die TTL des Schlüssels verlängert, sofern der Schlüssel noch existiert und sein Wert weiterhin zufällig ist, wie er beim Erwerb der Blockierung war.
Der Kunde sollte die Blockierung nur dann als erneut erworben betrachten, wenn es ihm gelungen ist, die Mehrheit der Instanzen während der Gültigkeitsdauer zu blockieren.
Technisch gesehen ändert sich der Algorithmus dabei jedoch nicht, deshalb sollte die maximale Anzahl der erneuten Versuche zur Erlangung von Blockierungen begrenzt werden, da sonst die Verfügbarkeitseigenschaften beeinträchtigt werden.
Quelle: habr.com
