So implementiert man verteiltes Locking (2016)
(martin.kleppmann.com)- Das Redis-basierte Redlock zielt auf fehlertolerante verteilte Locks ab, genauer gesagt Leases; für Aufgaben, bei denen Korrektheit auf dem Spiel steht, bietet es jedoch zu wenig Sicherheit, und als reine Effizienzoptimierung ist es übermäßig komplex
- Bei verteilten Locks muss man zuerst zwischen dem Zweck Effizienz zur Reduzierung doppelter Arbeit und dem Zweck Korrektheit zum Schutz gemeinsamen Zustands unterscheiden; entscheidend ist, ob ein Fehler nur Kosten erhöht oder Daten beschädigt
- Selbst mit einem perfekten Lock-Service können lange GC-Pausen, angehaltene Prozesse und Netzwerkverzögerungen dazu führen, dass nach Ablauf einer Lease veraltete Schreibvorgänge ausgeführt werden; dafür sind Fencing Tokens nötig
- Redlock kann bei jedem Lock-Erwerb kein monoton steigendes Token erzeugen, und der Ablauf von Redis-Keys hängt von der auf
gettimeofdaybasierenden Systemuhr ab, wodurch die Sicherheit bei Uhrzeitsprüngen oder Verzögerungen brechen kann - Für Locks, bei denen Korrektheit erforderlich ist, sollte man ein Konsenssystem wie ZooKeeper plus Prüfung von Fencing Tokens verwenden; Redis-Locks auf einem einzelnen Knoten sollten auf approximative, nicht kritische Zwecke beschränkt bleiben
Ausgangspunkt der Betrachtung von Redlock
- Redlock ist ein Algorithmus, der auf Redis fehlertolerante verteilte Locks implementiert, genauer gesagt Leases
- Es gibt bereits mehr als zehn unabhängige Implementierungen, und da nicht bekannt ist, wer sich auf diesen Algorithmus verlässt, lohnt sich eine öffentliche Prüfung
- Redis selbst eignet sich gut dafür, kurzlebige, approximative und schnell wechselnde Daten zwischen Servern zu teilen
- Beispiel: Request-Zähler pro IP-Adresse, Menge eindeutiger IPs pro Benutzer-ID
- Besorgniserregend ist die Entwicklung, dass Redis zunehmend in Bereichen des Datenmanagements eingesetzt wird, in denen stärkere Konsistenz und Dauerhaftigkeit erwartet werden; verteilte Locks gehören dazu
Zweck von Locks: Effizienz oder Korrektheit?
- In verteilten Anwendungen sind Locks ein Mechanismus, der sicherstellt, dass, wenn mehrere Knoten dieselbe Aufgabe versuchen, jeweils nur einer sie ausführt
- Die Gründe für den Einsatz von Locks lassen sich grob in zwei Kategorien einteilen
- Effizienz: eine Optimierung, um dieselbe teure Berechnung nicht zweimal auszuführen; bei einem Fehler steigen lediglich die AWS-Kosten etwas oder dieselbe E-Mail-Benachrichtigung wird zweimal versendet
- Korrektheit: ein Mechanismus, der verhindern soll, dass gleichzeitige Prozesse denselben Zustand beschädigen; ein Fehler kann schwerwiegende Probleme wie Dateibeschädigung, Datenverlust, permanente Inkonsistenz oder falsche Medikamentengabe verursachen
- Für Locks mit dem Zweck Effizienz sind Kosten und Komplexität von Redlock mit fünf Redis-Servern und Mehrheitsprüfung unnötig
- Eine einzelne Redis-Instanz und bei Bedarf asynchrone Replikation sind dafür besser geeignet
- In diesem Fall können bei Stromausfällen oder Problemen mit Redis-Knoten einige Locks verloren gehen, doch für eine nicht kritische Optimierung ist das ein akzeptabler Fehler
- Redlock wirkt wegen der fünf Replikas und der Mehrheitsentscheidung passend für Locks, bei denen Korrektheit wichtig ist, ist dafür in der Praxis aber ungeeignet
Leases allein können Ressourcen nicht sicher schützen
- Locks in verteilten Systemen unterscheiden sich von Mutexes in Multithread-Anwendungen und sind komplexer, weil Knoten und Netzwerk unabhängig voneinander ausfallen können
- Ein typischer Ablauf zum Aktualisieren einer Datei in gemeinsamem Storage ist: Lock erwerben, Datei lesen, ändern, zurückschreiben, Lock freigeben
- Das Lock soll verhindern, dass zwei Clients gleichzeitig ein Read-Modify-Write ausführen und dadurch Updates verloren gehen
- Wenn ein Client mit gehaltenem Lock lange stehen bleibt, kann die Lease ablaufen
- GC kann eingreifen und den Client für längere Zeit anhalten
- Leases sind ein gutes Design, um zu verhindern, dass ein abgestürzter Client ein Lock für immer hält; ist die Pause jedoch länger als die Ablaufzeit, kann der Client gefährliche Schreibvorgänge ausführen, ohne vom Ablauf zu wissen
- Dieses Problem ist kein theoretisches Beispiel; auch HBase hatte früher ein ähnliches Problem
- „Stop-the-world“-GC-Pausen dauerten in einigen Fällen mehrere Minuten
- Auch ein „concurrent“ GC wie CMS in der HotSpot JVM muss die Anwendung gelegentlich anhalten
- Es reicht nicht, unmittelbar vor dem Schreiben zu prüfen, ob das Lock abgelaufen ist
- GC kann laufende Threads an jeder Stelle anhalten, auch zwischen der letzten Prüfung und dem Schreibvorgang
Prozesspausen und Netzwerkverzögerungen sind ein normales Bedrohungsmodell
- Selbst wenn man eine Runtime ohne lange GC-Pausen verwendet, können Prozesse aus vielen Gründen anhalten
- Beim Lesen einer nicht im Speicher befindlichen Adresse kann ein Page Fault auftreten
- Liegt die Festplatte auf EBS, kann das Lesen einer Variable zu einer synchronen Anfrage über das Amazon-Netzwerk werden
- CPU-Konkurrenz, Scheduler-Verzögerungen oder ein versehentlich gesendetes
SIGSTOPkönnen Prozesse ebenfalls anhalten
- Netzwerkverzögerungen erzeugen dasselbe Problem
- Eine Anwendung hat eine Schreibanfrage gesendet, doch das Paket kann verzögert werden und erst nach Ablauf der Lease beim Storage-Server eintreffen
- Bei einem GitHub-Ausfall wurden Netzwerkpakete um etwa 90 Sekunden verzögert
- Paketnetzwerke wie Ethernet und IP können Pakete beliebig verzögern, und in der Praxis passiert das auch
- Daher kann man selbst in gut verwalteten Netzwerken keine Timing-Annahmen treffen; einfacher Lease-basierter Code ist unabhängig vom verwendeten Lock-Service grundsätzlich nicht sicher
Veraltete Schreibvorgänge müssen mit Fencing Tokens blockiert werden
- Die Lösung besteht darin, jede Schreibanfrage an den Storage mit einem Fencing Token zu versehen
- Ein Fencing Token ist eine Zahl, die jedes Mal steigt, wenn ein Client ein Lock erwirbt
- Beispiel: Client 1 erhält mit Token 33 eine Lease, hält dann lange an, und die Lease läuft ab
- Client 2 erhält mit Token 34 eine neue Lease und sendet eine Schreibanfrage an den Storage
- Wenn Client 1 später wieder aufwacht und mit Token 33 schreibt, lehnt der Storage die Anfrage mit Token 33 ab, da er bereits das höhere Token 34 verarbeitet hat
- Der Storage-Server muss Tokens aktiv prüfen und Schreibvorgänge ablehnen, deren Token-Wert zurückgeht, damit Sicherheit gewährleistet ist
- Wenn der Lock-Service strikt monoton steigende Tokens erzeugt, können Locks sicher gemacht werden
- Wird ZooKeeper als Lock-Service verwendet, kann man
zxidoder die Versionsnummer eines znodes als Fencing Token nutzen
- Wird ZooKeeper als Lock-Service verwendet, kann man
- Das große Problem von Redlock ist, dass es keine Funktion zur Erzeugung von Fencing Tokens hat
- Der eindeutige Zufallswert von Redlock bietet nicht die nötige Monotonie
- Ein Counter auf einem einzelnen Redis-Knoten reicht nicht aus, weil dieser Knoten ausfallen kann
- Counter auf mehreren Knoten können auseinanderlaufen
- Wahrscheinlich ist auch für die Erzeugung von Fencing Tokens ein Konsensalgorithmus nötig
Redlock stützt seine Sicherheit auf Timing-Annahmen
- Ein praktikables Modell für verteilte Algorithmen ist das asynchrone Modell mit unzuverlässigen Failure Detectors
- Prozesse können für beliebige Zeit anhalten
- Pakete können im Netzwerk beliebig verzögert werden
- Uhren können beliebig falsch gehen
- Trotzdem muss der Algorithmus korrekte Entscheidungen treffen
- Uhren dürfen nur zur Erzeugung von Timeouts verwendet werden, damit man nicht ewig wartet, wenn ein Knoten ausgefallen ist
- Timeouts müssen nicht exakt sein, und nur weil eine Anfrage ein Timeout erreicht hat, ist der andere Knoten nicht zwingend ausgefallen
- Es kann auch an Netzwerkverzögerung oder einem Fehler der lokalen Uhr liegen
- Redis verwendet zur Entscheidung über den Ablauf von Keys nicht eine monotonic clock, sondern
gettimeofdaygettimeofdaykann durch sprunghafte Änderungen der Systemzeit diskontinuierlich springen- Wenn NTP die Uhr anpasst oder ein Administrator die Zeit manuell ändert, können Redis-Keys viel früher oder später ablaufen als erwartet
- Algorithmen im asynchronen Modell erhalten üblicherweise Sicherheit ohne Timing-Annahmen aufrecht; Failure Detectors wie Timeouts wirken sich nur auf Liveness aus
- Wenn das Timing völlig durcheinandergerät, kann die Performance schlechter werden, aber es sollten keine falschen Entscheidungen getroffen werden
- Redlock ist anders: Seine Sicherheit hängt von mehreren Timing-Annahmen ab
- Alle Redis-Knoten müssen Keys ungefähr für die richtige Zeit halten
- Netzwerkverzögerungen müssen deutlich kleiner sein als die Ablaufzeit
- Prozesspausen müssen deutlich kürzer sein als die Ablaufzeit
Beispiele, wie Redlock bei schlechtem Timing bricht
- Bei fünf Redis-Knoten A, B, C, D, E und den Clients 1 und 2 können beide Clients glauben, das Lock zu halten, wenn die Uhr eines Knotens nach vorn springt
- Client 1 erhält das Lock auf A, B und C und erreicht wegen Netzwerkproblemen D und E nicht
- Die Uhr von C springt nach vorn, sodass das Lock abläuft
- Client 2 erhält das Lock auf C, D und E und erreicht wegen Netzwerkproblemen A und B nicht
- Ergebnis: Sowohl Client 1 als auch Client 2 halten sich für den Lock-Inhaber
- Ein ähnliches Problem kann entstehen, wenn C abstürzt, bevor das Lock auf die Festplatte persistiert wurde, und sofort neu startet
- Die Redlock-Dokumentation empfiehlt, den Neustart eines abgestürzten Knotens mindestens um die längste Lock-TTL zu verzögern
- Auch diese Neustartverzögerung hängt von ausreichend genauer Zeitmessung ab und kann bei Uhrzeitsprüngen scheitern
- Auch das Anhalten eines Client-Prozesses kann Redlock brechen
- Client 1 fordert auf A, B, C, D, E ein Lock an
- Während die Antworten unterwegs sind, gerät Client 1 in einen Stop-the-world-GC
- Auf allen Redis-Knoten laufen die Locks ab
- Client 2 erhält das Lock auf A, B, C, D, E
- Client 1 beendet den GC und erhält die erfolgreichen Antworten, die im Kernel-Netzwerkpuffer lagen
- Beide Clients glauben, das Lock zu halten
- Dass Redis in C geschrieben ist und keinen GC hat, hilft nicht
- Das Problem entsteht in Systemen, in denen der Client GC-Pausen erleben kann
- Sicher ist es nur, wenn man nach dem Lock-Erwerb von Client 2 die Arbeit von Client 1 beispielsweise mit Fencing Tokens blockiert
- Lange Netzwerkverzögerungen können denselben Effekt haben wie Prozesspausen
- Wenn das TCP user timeout viel kürzer als die Redis-TTL gesetzt wird, werden verzögerte Pakete möglicherweise ignoriert; sicher sagen lässt sich das aber nur nach Betrachtung der konkreten TCP-Implementierung
- Auch in diesem Fall landet man wieder beim Problem der Genauigkeit der Zeitmessung
Redlock verlangt Annahmen eines synchronen Systems
- Redlock funktioniert nur in einem synchronen Systemmodell mit den folgenden Eigenschaften korrekt
- Eine obere Grenze für Netzwerkverzögerungen ist garantiert
- Prozesspausen sind begrenzt
- Uhrabweichungen sind begrenzt
- Ein synchrones Modell bedeutet nicht, dass Uhren exakt synchronisiert sind, sondern dass es bekannte feste Obergrenzen für Netzwerkverzögerung, Pausen und Clock Drift gibt
- Redlock nimmt an, dass Verzögerung, Pausen und Drift im Vergleich zur Lock-TTL alle klein sind
- Werden Timing-Probleme so groß wie die TTL, schlägt der Algorithmus fehl
- In typischen Rechenzentrumsumgebungen können solche Timing-Annahmen die meiste Zeit erfüllt sein; das nennt man ein partiell synchrones System
- Wenn Korrektheit vom Lock abhängt, reicht „die meiste Zeit“ nicht aus
- Sobald Timing-Annahmen verletzt werden, kann Redlock die Sicherheit verletzen, etwa indem es einem anderen Client eine Lease gewährt, bevor die Lease eines Clients abgelaufen ist
- Der Fall von GitHub mit 90 Sekunden Paketverzögerung ist ein Beleg dafür, dass man in realen Umgebungen nur schwer ein synchrones Systemmodell annehmen kann
- Raft, Viewstamped Replication, Zab und Paxos gehören zu den Konsensalgorithmen, die für partiell synchrone Systemmodelle oder asynchrone Modelle mit Failure Detectors entwickelt wurden
- Solche Algorithmen müssen Timing-Annahmen vermeiden, und man muss darauf achten, Netzwerke, Prozesse und Uhren in verteilten Systemen nicht als zuverlässiger anzunehmen, als sie tatsächlich sind
Fazit und empfohlene Optionen
- Redlock ist für Locks zur Effizienzoptimierung unnötig schwergewichtig und teuer, und für Locks, bei denen Korrektheit auf dem Spiel steht, nicht sicher genug
- Insbesondere nimmt es faktisch ein synchrones System mit Obergrenzen für Netzwerkverzögerung und Ausführungszeit an; wenn diese Annahme bricht, kann die Sicherheit verletzt werden
- Zudem fehlt eine Funktion zur Erzeugung von Fencing Tokens, die das System vor langen Netzwerkverzögerungen oder angehaltenen Prozessen schützt
- Wenn ein Best-Effort-Lock zur Effizienzoptimierung gebraucht wird, ist der Single-Node-Lock-Algorithmus von Redis die bessere Wahl
- Das Lock wird per bedingtem set-if-not-exists erworben
- Das Lock wird nur dann atomar gelöscht und freigegeben, wenn der Wert übereinstimmt
- Im Code muss klar dokumentiert werden, dass das Lock approximativ ist und gelegentlich fehlschlagen kann
- Es ist nicht nötig, einen Cluster aus fünf Redis-Knoten aufzubauen
- Für Locks, die Korrektheit erfordern, sollte man nicht Redlock verwenden, sondern ein Konsenssystem wie ZooKeeper
- Wenn möglich, können die Curator recipes verwendet werden, die Locks implementieren
- Mindestens kann eine Datenbank wie PostgreSQL eingesetzt werden, die vernünftige Transaktionsgarantien bietet
- Für jeden Zugriff auf Ressourcen unter dem Lock muss die Prüfung von Fencing Tokens erzwungen werden
- Redis ist ein nützliches Werkzeug, wenn es für die vorgesehenen Zwecke eingesetzt wird; jedes Werkzeug hat Grenzen, und man sollte diese Grenzen kennen und einplanen
- In einem Update vom 9. Februar 2016 veröffentlichte Salvatore, der ursprüngliche Autor von Redlock, eine Erwiderung, die Schlussfolgerung bleibt jedoch bestehen
1 Kommentare
Meinungen auf Hacker News
Bei der Arbeit nutzen wir Temporal und haben einen Distributed Lock mit einem eigenen Workflow und Signalen implementiert.
Bisher funktioniert das gut, und weil wir den verteilten Teil des Lockings den Temporal-Funktionen überlassen, ist die Implementierung ziemlich einfach.
Ich frage mich, ob Temporal in diesem Bereich einzigartig ist oder ob es Alternativen auf ähnlichem Niveau gibt.
Dass es aus Uber ausgegliedert wurde und von großen Anbietern genutzt wird, klingt jedenfalls nach ausreichender Praxiserprobung.
Für Distributed Locks verwende ich normalerweise PostgreSQL advisory locks.
Auch wenn die Arbeit nichts mit der Datenbank zu tun hat: Man startet eine Transaktion und nimmt einen advisory lock; der Lock bleibt dann bestehen, bis die App ihn selbst freigibt oder die Transaktion etwa durch einen Crash endet.
Bisher fühlte sich das ziemlich sicher an, aber mir ist gerade klar geworden, dass ich nie überprüft habe, ob die Datenbankverbindung noch in Ordnung ist.
Wenn es sich um datenbankbezogene Arbeit handelt, würde die Query fehlschlagen und damit auch die Arbeit scheitern; andernfalls könnte man den Lock bereits verloren haben, ohne es zu merken.
Wenn man ohne Fencing Tokens oder atomare Operationen absolute Korrektheit will, frage ich mich, ob man am Ende für alles Two-Phase Commit braucht.
Um das, was vermutlich beabsichtigt war, korrekt zu tun, müsste man wohl „EXCLUSIVE“ oder „ACCESS EXCLUSIVE“ verwenden oder für die Arbeit Two-Phase Commit beziehungsweise Idempotenz sicherstellen.
[0] https://www.postgresql.org/docs/current/explicit-locking.htm...
Die meisten Libraries verwenden normalerweise Connection Pools, daher muss man eine dedizierte Verbindung für den Lock reservieren und auch die regelmäßige Lock-Prüfung unbedingt über genau diese Verbindung durchführen.
Es wäre gut, meinen früheren Kommentar zu diesem Blogbeitrag und meine Antwort in meinem eigenen Blog zu lesen.
In beliebiger Reihenfolge: Der Autor hat einen zentralen Punkt darüber verpasst, wie der Algorithmus funktioniert, und den Algorithmus dann mit den verbleibenden, schwächeren Argumenten abgelehnt.
Auch die Aussage, dass es auf modernen Computern und APIs unmöglich sei, ungefähr die richtige Zeitspanne zu warten, stimmt nicht. GC-Pausen sind bounded, und monotone Uhren funktionieren, also ist das eine akzeptable Annahme.
Es ist ein Unterschied, ob man kritisiert, dass ein Auto-Release-Mechanismus an sich potenzielle Race Conditions offenlegt, oder ob man innerhalb der Ziele und des Systemmodells des Algorithmus kritisiert.
Redlock wurde über Jahre in vielen Anwendungsfällen erfolgreich eingesetzt, und wenn man den Timeout deutlich größer wählt als die Zeit bis zum Abschluss der Arbeit und als beliebige Pausen, die in gewöhnlichen Betriebssystemen auftreten können, ist es sehr schwer, eine Race Condition auszulösen.
Natürlich ist es ein Designfehler, wenn man den Auto-Release-Timeout zu klein wählt und die Arbeit leicht so lange dauern kann; das ist aber kein Problem von Redlock selbst.
Würdest du RedLock verwenden, wenn der Timeout ziemlich kurz ist (z. B. 1–2 Sekunden), die Arbeit normalerweise etwa 90 % dieses Timeouts benötigt und die Arbeit, die während des RedLock-Locks ausgeführt wird, absolut niemals gleichzeitig mit einem anderen Lock-Inhaber laufen darf?
Meiner Ansicht nach lautet die richtige Antwort hier immer „nein“. Denn das Risiko ist sehr groß, dass die Lease abläuft, bevor der Client die Arbeit beendet.
RedLock kann nicht in allen Situationen Mutual Exclusion garantieren, daher muss man die Arbeit idempotent machen; solche Fälle setzt man besser mit optimistischem Locking um.
Ich frische gerade mein Low-Level- und Algorithmuswissen wieder auf; welche guten Bücher gibt es zu diesem Thema? Das Buch des Autors habe ich.
Ich würde gern zum Spaß etwas bauen, aber die Materialien sind entweder nur Spielzeugniveau oder viel zu komplex.
Such dir ein Thema aus und implementiere es tatsächlich.
Ich habe früher auf Basis dieses Materials einen Blogbeitrag über Distributed Locks geschrieben: https://medium.com/sahibinden-technology/an-easy-integration...
Die Erklärung „Locks haben einen Timeout (sind also Leases)“ klingt für mich seltsam.
Erstens: Wenn ein Client crasht, sollten OS oder Supervisor den Lock auch ohne timed lease freigeben; und wenn beide sterben, wird die Verbindung irgendwann getrennt, und das Netzwerksystem sollte das über Reset, Timeout, ausbleibende Heartbeats oder Ähnliches erkennen, die Verbindung ungültig machen und dann den Lock freigeben.
Zweitens: Wenn das Problem darin besteht, dass ein Client wegen eines Bugs nicht crasht, sondern den Lock zu lange hält, müsste dann nicht irgendein Supervisor das erkennen und den Client beenden, bevor er den Lock für andere freigibt?
Drittens: Wenn man Locks mit Timeout hat, um solche Corner Cases zu behandeln, müsste man das eigentliche Programm dann nicht über Exceptions, Signale, Beendigung oder Ähnliches informieren? Und müsste man nicht warten und verifizieren, dass das Programm benachrichtigt wurde, bevor der Lock freigegeben wird?
Die Idee, dass ein Programm nach einem Timeout ganz normal im Control Flow weiterlaufen darf, scheint mir die eigentliche Ursache des Problems zu sein; ich verstehe nicht, warum alle darüber hinweggehen. Übersehe ich etwas Offensichtliches?
Die Instanz, die den Lock auf ihrer Seite ungültig macht, ist der Storage-Service, und ohne zusätzliche Garantien, die Redlock nicht bietet, kann der Client sein eigenes Problem nicht selbst erkennen.
In manchen Fällen werden diese Pakete gedroppt, und der Client auf der entfernten Maschine ist bereits tot, während auf dem Server noch eine offene Verbindung übrig bleibt.
Nebenbei: Der Downvote war nicht von mir.
Deno und Deno KV, gehostet von Deno Deploy, wurden verwendet, um ein verteiltes Lock zu implementieren.
Intern wird FoundationDB, eine verteilte Datenbank, genutzt; Deno-Instanzen, die auf lokalen Geräten laufen, verbinden sich mit demselben Deno KV und erwerben dort das Lock.
Mit PostgreSQL funktioniert es über
SELECT FOR UPDATEebenfalls, aber die Datenbank selbst ist nicht verteilt.2018 haben wir Redis für unseren Anwendungsfall geprüft, uns am Ende aber für eine weniger schillernde Lösung entschieden, die tatsächlich kein einziges Mal versagt hat.
Der Use Case bestand darin, aus einer endlichen Menge von Tickets einer Kampagne identifizierbare Tickets einzeln auszugeben, ähnlich wie Ticketmaster Sitzplätze in einer Veranstaltungsstätte zuweist.
Wenn eine Anfrage kam, mussten wir ein verfügbares Ticket bereitstellen, die Metadaten der Anfrage an das zugewiesene Ticket hängen und es anschließend von weiteren Anfragen ausschließen.
In der Vergangenheit hatte es fehlgeschlagene Kampagnen mit Überzuteilung, Unterzuteilung und doppelter Zuteilung gegeben, daher war Korrektheit entscheidend.
Wir probierten auch eine einfache Implementierung mit Redis aus: Lock erwerben, Lock prüfen, Arbeit ausführen, Lock freigeben. Damals war der Betriebsaufwand für uns aber groß, und ich bin froh, dass wir diesen Weg nicht gegangen sind.
Die endgültige Wahl war Postgres. Unser „verteiltes Lock“ war eher ein zusammengesetztes
UPDATE-Statement mit Postgres-eigenen Funktionen; wir wandelten die Anfrage in eine Art Mengenoperation um, sodass die Datenbank einen Erfolgsdatensatz oder eine Fehlermarkierung zurückgab. ACID-Transaktionen haben gewonnen.Nachdem die Korrektheit gelöst war, betrachteten wir Skalierung und Performance. Wir brauchten keine Millionen Anfragen pro Sekunde, hatten aber Vorgaben für kurzfristige Spitzen.
Wir optimierten die Lese- und Schreib-Datenbankinstanzen im Cluster, platzierten größere oder stärker nachgefragte Kampagnen strategisch auf dafür vorgesehenen Systemen und optimierten zwei Jahre lang weiter; trotzdem gab es keine einzige Kampagne, bei der die Ticketverteilung fehlschlug.
Ich bin kein Experte für verteilte Locking-Technik; ich habe mich nur auf das zu lösende Problem konzentriert, ein paar Dinge ausprobiert und dann die passende Lösung gefunden.
Da eine
UPDATE-Transaktion nur wenige Mikrosekunden dauert, kann man das Problem zentralisieren; das ist einfacher, schneller und sicherer.Wie im Artikel beschrieben, ist das aber kein verteiltes Problem.
Locks in verteilten Systemen unterscheiden sich von Mutexes in Multi-Thread-Apps und sind komplexer, weil mehrere Nodes und Netzwerke auf unterschiedliche Weise unabhängig voneinander ausfallen können.
Verteilte Locks braucht man, wenn Transaktionen Sekunden bis Stunden dauern können und beteiligte Maschinen ausfallen können, während sie ein Lock halten.
In diesem Fall lautet die Constraint: „Verkaufe nicht mehr als N Tickets.“ Die meisten realistischen Traffic-Größenordnungen für solche Probleme lassen sich mit dem Transaktionsverhalten traditioneller relationaler Datenbanken lösen; die interne Lock-Verwaltung sollte man der Datenbank überlassen.
Ich hoffe, Entwickler springen nicht zu schnell zu „wir bauen ein verteiltes Lock“. Fast immer gibt es eine bessere Antwort, aber diese Antwort ist je nach Anwendung unterschiedlich.
Das könnte gut zu etwas wie dem neuen SQLite von Cloudflare passen.
Das erste Mal habe ich darüber hier gelesen: https://code.flickr.net/2010/02/08/ticket-servers-distribute...
Viele Engineers kümmern sich erst dann ernsthaft um Korrektheitsprobleme, wenn es zu spät ist. Das ist ähnlich wie bei Security.
Selbst wenn sie sich darum kümmern, prüfen sie oft nicht, ob das, was sie tun, wirklich korrekt ist.
In meinem Bereich etwa kommunizieren Microservices, Actors und Prozesse über das Netzwerk per Nachrichten; über 95 % der Implementierungen, die ich sehe, haben Edge Cases, in denen Nachrichten verloren gehen oder in anderer Reihenfolge verarbeitet werden können.
Aber die Anreize sind nicht so ausgerichtet, dass dieses Problem behoben wird. Die Vergütungsstrukturen von Führungskräften und Engineers passen nicht zu dem Ergebnis, das für Kunden und Aktionäre am besten wäre.
Man will ohne triftigen Grund Netzwerkgrenzen zwischen Funktionsaufrufe setzen und baut dann endlos HTTP-Server und -Clients sowie JSON-Serialisierung und -Deserialisierung für diesen Funktionsaufruf; mit etwas Glück nutzt man gRPC, und versucht anschließend, über diese Netzwerkgrenze hinweg Dinge wie verteilte Transaktionen neu zu implementieren.
Am Ende entsteht nur Beschäftigungstherapie, um die unvermeidlichen „unheimlichen Wechselwirkungen aus der Ferne“ zu behandeln.
Produkt- und Engineering-Teams müssen sich darauf einigen, und wenn SLOs verletzt werden, muss der Fokus auf Systemstabilität verschoben werden.
Es ist schwer, alle zu überzeugen, daher braucht es gute Führung.
Wenn Bugs auftreten und neue Features langsam oder kaum noch kommen, sodass Kunden abzuwandern beginnen, wird die Begründung sehr einfach, warum Qualität Teil des Prozesses sein muss.
Reife Führungskräfte handeln diesem Stadium so früh wie möglich voraus.
[0] https://en.wikipedia.org/wiki/British_Post_Office_scandal
Aber ich sehe keinen guten Weg, die Manager von gestern davon zu überzeugen, Zeit dafür zu geben, es richtig zu bauen.
Das macht die Sache viel zu kompliziert.
Wenn es so etwas wie die im Artikel erwähnten Fencing Tokens gibt, braucht man keinen Lock.
Der Token muss nicht einmal monoton steigen; es reicht ein passiver eindeutiger Wert, den Client und Storage gemeinsam besitzen.
Nennen wir ihn Version Token: Er kann ein monoton steigender Wert sein, aber auch eine meist einfacher zu erzeugende UUID funktioniert. Technisch wäre auch ein Hash aller Daten im Storage möglich, ist aber nicht praktikabel.
Der Ablauf sieht so aus: Der Client holt sich aus dem Storage den aktuellen Version Token zusammen mit den zu ändernden Daten, und der Storage liest Daten und Token atomar aus und garantiert, dass dieser Token zu dieser Datenversion gehört.
Danach sendet der Client die Änderungen zusammen mit dem Version Token zurück, und der Storage akzeptiert die Änderung nur, wenn der aktuelle Token mit dem übergebenen Token übereinstimmt, und erzeugt atomar einen neuen Version Token.
Man kann aus anderen Gründen Locks einführen, aber in einem verteilten System sollten sie unabhängig von der Integrität des Storage sein.
Auch den Begriff „Lock“ mag ich nicht besonders. Da er temporär und nicht garantiert ist, vermitteln Lease oder Reservierung die Bedeutung besser.
Dabei wird die Komplexität auf die Datenbankseite verlagert, aber hier muss man im Kopf behalten, dass es um verteiltes Locking geht.
Bei einer einzelnen Datenbank ist es einfach, bis die Datenbank abstürzt und man nicht mehr weiß, welcher CAS-Write tatsächlich übernommen wurde.
In großen Systemen, die hohe Verfügbarkeit und Backups über mehrere Rechenzentren hinweg brauchen, kann auch dieser Ansatz wegen Szenarien rund um Knotenausfälle brechen und ziemlich komplex werden.
Üblicherweise verwendet man ein Transaktionslog in der Art von Paxos. Man sollte nicht annehmen, dass es in verteilten Systemen einfache Lösungen gibt. Es ist immer mühsam.
Aus Effizienzsicht kann man durch das Halten eines Locks vermeiden, dieselbe Arbeit unnötig zweimal auszuführen, zum Beispiel eine teure Berechnung.
Wenn der Lock fehlschlägt und zwei Nodes dieselbe Arbeit ausführen, kann das harmlos sein, wenn es nur etwas höhere Kosten oder eine doppelte gleiche E-Mail-Benachrichtigung bedeutet.
Dass mehrere Nodes dieselbe Arbeit ausführen, halte ich aber für deutlich schlimmer als in den Beispielen beschrieben, weil es skalierbare verteilte Verarbeitung selbst behindern kann.
Nehmen wir an, das Storage-System hat zwei Nodes und es laufen zwei Read-Modify-Write-Prozesse. Prozess 1 und 2 erhalten beide den ersten Token
abc.Prozess 1 committet, wodurch der Token zu
cdewird, und die Änderung wird zu Node 2 gestreamt, kommt dort wegen Netzwerklatenz aber verzögert an.Wenn in der Zwischenzeit Prozess 2 mit Token
abcauf Node 2 committet, akzeptiert Node 2 die Änderung, weil er die Nachricht von Node 1 noch nicht erhalten hat, und das System gerät in einen inkonsistenten Zustand.Mit einem monoton steigenden Fencing Token passiert das nicht, weil diese Anforderung die Nodes dazu zwingt, sich auf eine globale Reihenfolge aller Operationen zu einigen, bevor sie einen Token ausgeben.