Distributed Lock
Sperre über mehrere Prozesse hinweg
Die Idee und ihr Nutzen
Der Mahndienst einer Versicherung verschickt jede Nacht um 2 Uhr Mahnungen an Kunden mit offenen Beiträgen. Damit dieser Mahnlauf auch stattfindet, wenn ein Server ausfällt, läuft der Mahndienst in zwei Exemplaren auf verschiedenen Servern. Die Mahnungen dürfen aber nur einmal verschickt werden, sonst erhält jeder Kunde zwei Mahnbriefe. Deshalb versuchen beide Exemplare vor dem Start, beim Koordinationsdienst eine Sperre zu erhalten. Der Koordinationsdienst ist ein eigenes Programm, das sich merkt, welches Exemplar gerade die Sperre hält, und die Sperre nur an ein Exemplar vergibt. Nur das Exemplar, das die Sperre bekommt, verschickt die Mahnungen. Eine solche Sperre, die über mehrere Programme auf verschiedenen Rechnern hinweg gilt, heißt Distributed Lock, auf Deutsch verteilte Sperre.
Wie funktioniert es?
Um 2 Uhr fordern Exemplar 1 und Exemplar 2 des Mahndienstes beim Koordinationsdienst die Sperre mahnlauf an. Exemplar 1 ist schneller und erhält die Sperre mit der Sperrnummer 118. Bei jeder neuen Vergabe der Sperre erhöht der Koordinationsdienst diese Nummer. Exemplar 2 erhält „bereits vergeben“ und wartet. Exemplar 1 beginnt den Mahnlauf und schreibt die Mahnungen mit der Sperrnummer 118 in die Zieldatenbank, aus der später die Mahnbriefe gedruckt werden. Dabei verlängert Exemplar 1 die Sperre alle zehn Sekunden, damit sie nicht abläuft, solange Exemplar 1 arbeitet. Bleibt die Verlängerung 30 Sekunden lang aus, lässt der Koordinationsdienst die Sperre verfallen. In diesen 30 Sekunden können zwei Verlängerungen ausbleiben, etwa wegen hoher Last, ohne dass Exemplar 1 die Sperre verliert. Nach einem Absturz von Exemplar 1 wartet Exemplar 2 höchstens eine halbe Minute. Nach fünf Minuten bleibt Exemplar 1 wegen einer Netzstörung hängen und verlängert die Sperre nicht mehr. Nach 30 Sekunden läuft die Sperre ab. Exemplar 2 erhält die Sperre mit der höheren Sperrnummer 119. Exemplar 2 liest in der Zieldatenbank, bis zu welchem Kunden die Mahnungen schon erzeugt wurden, und setzt bei diesem Kunden fort. Eine Minute später ist die Netzstörung vorbei, und Exemplar 1 versucht, mit Sperrnummer 118 weitere Mahnungen in die Zieldatenbank zu schreiben. Die Zieldatenbank kennt bereits Nummer 119 und weist den Schreibversuch ab. Ist der Mahnlauf erledigt, gibt Exemplar 2 die Sperre frei.
Innerhalb eines Programms verhindert man doppelte Ausführung mit einer Sperre im Arbeitsspeicher. Beim Mahndienst hilft eine solche Sperre nicht, weil jedes Exemplar seinen eigenen Arbeitsspeicher auf seinem eigenen Server hat und von der Sperre des anderen Exemplars nichts weiß. Die beiden Exemplare sprechen nur über das Netz miteinander oder mit gemeinsamen Diensten. Der Koordinationsdienst kann auch eine gemeinsame Datenbank sein.
Die Ablaufzeit von 30 Sekunden ist nötig, damit nach einem Absturz des einen Exemplars das andere übernehmen kann. Ohne Ablaufzeit bliebe der Mahnlauf nach einem Absturz für immer gesperrt. Eine Ablaufzeit allein garantiert aber nicht, dass nie zwei Exemplare gleichzeitig arbeiten. Ein Exemplar kann hängen bleiben, ohne abzustürzen. Eine Ursache ist eine Netzstörung wie bei Exemplar 1. Eine andere Ursache ist eine längere Pause der Laufzeitumgebung, also der Software, in der der Mahndienst ausgeführt wird. In einer solchen Pause räumt die Laufzeitumgebung nicht mehr benötigten Speicher auf. Netzstörungen und solche Pausen lassen sich nicht ausschließen. Läuft das hängende Exemplar danach weiter, bemerkt es nicht, dass seine Sperre abgelaufen ist, und schreibt weiter. Dagegen hilft die Sperrnummer. Jedes Exemplar schickt seine Sperrnummer bei jedem Schreibvorgang mit, und die Zieldatenbank merkt sich die höchste bisher gesehene Nummer. Schreibvorgänge mit einer kleineren Nummer weist die Zieldatenbank ab. Der Koordinationsdienst vergibt also die Sperrnummer, geprüft wird sie aber in der Zieldatenbank. Auf Englisch heißt die Sperrnummer Fencing Token.
Erhält ein Exemplar beim Verlängern keine Antwort vom Koordinationsdienst, weiß das Exemplar nicht, ob die Sperre noch gilt. Es muss dann so handeln, als hätte es die Sperre verloren, und das Schreiben einstellen, bis es die Sperre erneut erhalten hat. Auch die Sperrnummer verhindert nicht jeden doppelten Brief. Kurz vor dem Hänger hat Exemplar 1 womöglich die Mahnung für einen Kunden schon geschrieben, aber noch nicht vermerkt, dass dieser Kunde erledigt ist. Exemplar 2 schreibt für diesen Kunden dann eine zweite Mahnung. Deshalb erhält jede Mahnung zusätzlich eine eindeutige Auftragskennung aus Kundennummer und Monat, und die Zieldatenbank nimmt jede Auftragskennung nur einmal an. So entsteht für diesen Kunden kein zweiter Brief.
Verteilte Sperre: nur ein Exemplar erstellt Mahnungen
Wann ist es sinnvoll und wann nicht?
Ein Distributed Lock lohnt sich
- Eine Aufgabe darf trotz mehrerer laufender Exemplare immer nur von einem Exemplar zur selben Zeit ausgeführt werden. Ohne gemeinsame Sperre starten um 2 Uhr beide Exemplare den Mahnlauf. Jeder Kunde mit offenem Beitrag erhält dann zwei Mahnbriefe, die Versicherung zahlt doppeltes Porto, und das Kundencenter wird am nächsten Tag mit Anrufen überhäuft.
- Die Aufgabe ist zeitgesteuert wie der nächtliche Mahnlauf. Eine verteilte Sperre eignet sich auch, wenn mehrere Exemplare Dateien aus demselben Ordner abholen und jede Datei nur einmal verarbeitet werden darf. Dasselbe gilt, wenn ein fremdes System nur einen Zugriff zur selben Zeit erlaubt. Ohne Sperre verarbeiten zwei Exemplare dieselbe Datei doppelt, und das fremde System weist den zweiten gleichzeitigen Zugriff ab.
- Schon der doppelte Mahnlauf soll vermieden werden, nicht erst der doppelte Brief. Mit einer Auftragskennung allein würden beide Exemplare den ganzen Mahnlauf ausführen.
Ein Distributed Lock ist nicht das Richtige
- Zwei Exemplare sollen nicht gleichzeitig denselben Datensatz ändern, und alle betroffenen Daten liegen in einer einzigen Datenbank. Diese Datenbank kann gleichzeitige Änderungen selbst verhindern oder erkennen, und eine Sperre beim Koordinationsdienst würde nur dasselbe noch einmal regeln. Dann nutzt das Entwicklungsteam die Sperren oder Versionsnummern dieser Datenbank. Die Datenbank prüft sie selbst bei jeder Änderung, und ein zusätzlicher Koordinationsdienst, der betrieben und überwacht werden muss, entfällt. Dafür gibt es Pessimistic Locking, das einen Datensatz während einer Änderung für andere blockiert, und Optimistic Locking, das gleichzeitige Änderungen über Versionsnummern erkennt, statt vorher zu sperren.
- Die Aufgabe lässt sich so gestalten, dass eine doppelte Ausführung keinen Schaden anrichtet. Dann verzichtet das Entwicklungsteam auf die Sperre, und der Koordinationsdienst entfällt. Beim Mahnlauf ginge das, weil die Zieldatenbank jede Auftragskennung aus Kundennummer und Monat nur einmal annimmt und eine zweite Mahnung für denselben Kunden und Monat abweist. Beide Exemplare arbeiten dann zwar doppelt, aber ohne Schaden. Diese Bauweise beschreibt Idempotency.
- Die Aufgabe schreibt in ein System, das keine Sperrnummer prüfen kann, und eine doppelte Ausführung hätte schwere Folgen. Die Sperre allein schützt dann nicht: Ein Exemplar kann nach einem Hänger weiterschreiben, obwohl das andere Exemplar die Sperre schon hält. Das Entwicklungsteam richtet dann in diesem System eine Prüfung ein, die jeden Auftrag an einer eindeutigen Auftragskennung erkennt und einen zweiten Auftrag mit derselben Kennung abweist. So führt das System keinen Auftrag doppelt aus, auch wenn zwei Exemplare gleichzeitig schreiben. Die Sperre kann zusätzlich bleiben, damit nicht beide Exemplare die ganze Aufgabe ausführen.
Nachteile und typische Fehler
Der Koordinationsdienst muss sehr zuverlässig erreichbar sein. Fällt er aus, kann kein Exemplar die Sperre erhalten, und der Mahnlauf findet nicht statt. Ein ausfallsicherer Koordinationsdienst läuft deshalb meist selbst in mehreren Exemplaren desselben Programms auf verschiedenen Rechnern. Die Exemplare stimmen sich über ein Einigungsverfahren ab, wie es Consensus beschreibt. So kennen alle Exemplare dieselbe Vergabe der Sperre, und fällt ein Rechner aus, vergeben die übrigen Exemplare die Sperre weiter. Der Koordinationsdienst muss wie jeder andere Dienst betrieben, überwacht und aktualisiert werden. Die Ablaufzeit muss lang genug für die normale Arbeit sein. Ist sie zu lang, wartet das andere Exemplar nach einem Absturz unnötig lange. Die Sperrnummer koppelt außerdem Koordinationsdienst und Zieldatenbank: Die Zieldatenbank muss die Nummer bei jedem Schreibvorgang prüfen, und alle Programme, die in die Zieldatenbank schreiben, müssen die Nummer mitschicken.
Typische Fehler und woran man sie erkennt:
- Keine Sperrnummer: Die Zieldatenbank nimmt Mahnungen ohne Sperrnummer an. Exemplar 1 bleibt hängen, und nach 30 Sekunden erhält Exemplar 2 die Sperre. Danach läuft Exemplar 1 weiter und schreibt weiter Mahnungen in die Zieldatenbank, weil Exemplar 1 nicht bemerkt, dass seine Sperre abgelaufen ist. Die Zieldatenbank nimmt die Mahnungen beider Exemplare an. Erkennbar ist das an doppelten Mahnungen für denselben Kunden und Monat nach Netzstörungen oder langen Pausen eines Exemplars.
- Ablaufzeit zu kurz: Die Ablaufzeit ist kaum länger als der Abstand der Verlängerungen, etwa zwölf Sekunden bei einer Verlängerung alle zehn Sekunden. Wegen hoher Last kommt eine Verlängerung von Exemplar 1 drei Sekunden zu spät. Die Sperre ist dann schon abgelaufen, obwohl Exemplar 1 fehlerfrei arbeitet. Exemplar 2 erhält die Sperre und übernimmt den Mahnlauf, und die Zieldatenbank weist die Schreibversuche von Exemplar 1 ab. Erkennbar ist das an häufigen Wechseln der Sperrnummer während eines einzigen Mahnlaufs.
- Ansturm auf die Sperre: Ein anderes Programm der Versicherung läuft in 50 Exemplaren auf verschiedenen Servern, und alle Exemplare fordern dieselbe Sperre beim Koordinationsdienst an. Jedes wartende Exemplar fragt alle zehn Millisekunden erneut nach, ob die Sperre frei ist. Solange ein Exemplar die Sperre hält, erhält der Koordinationsdienst von den 49 wartenden Exemplaren so 4.900 Anfragen in der Sekunde für eine einzige Sperre. Der Koordinationsdienst beantwortet dann auch die Anfragen anderer Programme langsamer, etwa die Verlängerungen anderer Sperren. Erkennbar ist das an steigenden Antwortzeiten des Koordinationsdienstes, sobald die Sperre vergeben ist.
- Freigabe einer fremden Sperre: Nach dem Hänger weist die Zieldatenbank den Schreibversuch von Exemplar 1 ab. Exemplar 1 bricht ab und schickt dem Koordinationsdienst die Freigabe der Sperre
mahnlauf, ohne vorher zu prüfen, ob es die Sperre noch hält. Der Koordinationsdienst prüft nicht, von welchem Exemplar die Freigabe kommt, und hebt die Sperre auf, die Exemplar 2 hält. Bei seiner nächsten Verlängerung erfährt Exemplar 2, dass es die Sperre nicht mehr hält. Exemplar 2 stellt das Schreiben ein, obwohl es fehlerfrei arbeitet, und der Mahnlauf stockt, bis Exemplar 2 die Sperre erneut erhalten hat. Erkennbar ist das an Freigaben im Protokoll des Koordinationsdienstes, die von einem anderen Exemplar stammen als die letzte Vergabe.
Weiterführend
Verwandte Ansätze
- Leader Election: bestimmt ein Exemplar dauerhaft zum Leiter, der die Rolle regelmäßig erneuert. Eine verteilte Sperre schützt dagegen meist eine einzelne, zeitlich begrenzte Aufgabe.
Werkzeuge und Umsetzungen
- etcd: Koordinationsdienst, der Sperren mit begrenzter Lebensdauer vergibt und fortlaufende Nummern liefert, die sich als Sperrnummer nutzen lassen.
- Apache ZooKeeper mit Apache Curator: bewährter Koordinationsdienst mit einer Java-Bibliothek, die fertige Bausteine für Sperren und Wahlen enthält.
- Redisson: Java-Bibliothek für Sperren auf Grundlage eines Datenspeichers im Arbeitsspeicher wie Valkey oder Redis. Ohne Sperrnummer schützt Redisson nicht vor einem Hänger wie dem von Exemplar 1.
- ShedLock: sorgt in Java-Anwendungen dafür, dass zeitgesteuerte Aufgaben nur von einem Exemplar ausgeführt werden, und nutzt dafür eine gemeinsame Datenbank.
- PostgreSQL: bietet mit Advisory Locks frei benennbare Sperren direkt in der Datenbank.
Quellen
- Martin Kleppmann: How to do distributed locking: zeigt, wie ein pausiertes Programm nach Ablauf der Sperre weiterschreibt, sodass zwei Programme sich für Halter der Sperre halten, und begründet die fortlaufende Sperrnummer, die die Zieldatenbank prüft.
- Apache ZooKeeper: Recipes and Solutions: beschreibt, wie ein Koordinationsdienst Sperren vergibt, wie wartende Programme nur ihren Vorgänger beobachten, damit nicht alle gleichzeitig nachfragen, und wie die Sperre beim Ausfall des Halters frei wird.