Ist Two-Phase Locking nach 50 Jahren immer noch die beste Wahl?
(concurrencyfreaks.blogspot.com)- Two-Phase Locking (2PL), 1976 veröffentlicht, bietet die stärkere Eigenschaft Opacity statt nur Serialisierbarkeit, hat aber auch nach fast 50 Jahren weiterhin Grenzen bei Lese-Skalierbarkeit und Progress-Garantien
- Mit einfachen Regeln zum Erwerben und Freigeben von Locks verarbeitet es Transaktionen über mehrere Records hinweg und liefert starke Isolationsniveaus; deshalb wird es in kommerziellen Transaktionsdatenbanken und konkurrierenden Datenstrukturen noch immer breit eingesetzt
- Traditionelles 2PL kann wegen exklusiver Locks sogar Lese-Lese-Konflikte erzeugen, und selbst mit Reader-Writer-Locks entsteht an Hotspots mit vielen Lesezugriffen – etwa an der Wurzel eines binären Suchbaums – read-indicator contention
- 2PLSF verteilt Reader-Markierungen über Cache-Lines, um die Contention beim Erwerb von Read-Locks zu senken, und nutzt den zentralen atomaren Zähler per fetch_and_add() nur für tatsächlich kollidierende Transaktionen
- 2PL-Varianten wie No-Wait, Deadlock-detection und Wait-Or-Die lassen weiterhin Live-Lock- oder Skalierungsprobleme offen; 2PLSF ist eine Weiterentwicklung, die sowohl Lese-Skalierbarkeit als auch starvation-free Transaktionen anstrebt
Warum 2PL weiterhin wichtig ist
- Two-Phase Locking (2PL) gehört zu den ersten allgemeinen Verfahren zur Nebenläufigkeitskontrolle, die Serialisierbarkeit bieten, und liefert in der Praxis sogar das stärkere Isolationsniveau Opacity
- 2PL wurde 1976 mit einem Paper von Jim Gray und Kollegen veröffentlicht; die Idee selbst dürfte noch älter sein, daher gilt es heute als nahezu 50 Jahre alte Technik
- Allgemeine Nebenläufigkeitskontrolle bezeichnet Algorithmen, die Transaktionen mit all-or-nothing-Semantik über mehrere Datenobjekte wie Objekte, Records oder Tupel hinweg ermöglichen
- Die Stärken von 2PL sind seine Einfachheit und seine starke Isolation
- Vor dem Lesen oder Schreiben eines Records wird zuerst der Lock erworben, der diesen Record schützt
- Alle erworbenen Locks werden bis zum Ende der Transaktion gehalten, sodass eine konsistente Sicht entsteht
Isolation durch einfache Regeln
- Bei 2PL wird für jeden Zugriff innerhalb einer Transaktion ein Lock erworben, und alle Locks werden erst am Ende der Transaktion freigegeben, wenn feststeht, dass keine weiteren Zugriffe mehr erfolgen
- Zu diesem Endzeitpunkt sind alle Locks auf die berührten Daten gehalten, wodurch ein Linearization Point für die betreffende Transaktion entsteht
- Vor 50 Jahren gingen viele Datenbankforscher davon aus, man könne Locks direkt nach dem jeweiligen Record-Zugriff wieder freigeben, doch eine solche Nebenläufigkeitskontrolle ist nicht serialisierbar
- Bekannte kommerzielle Transaktionsdatenbanken verwenden 2PL oder T/O sowie Kombinationen mit MVCC
- Im Bereich konkurrierender Datenstrukturen ist Linearizability praktisch der Standard, und um konsistent über mehrere Knoten hinweg zu schreiben, ist für Schreibzugriffe meist ein Verfahren wie 2PL nötig
- Eine Ausnahme sind lock-free Datenstrukturen, wobei betont wird, wie schwierig korrekte lock-free Implementierungen sind
Die Engstellen von 2PL: Lese-Skalierbarkeit und Live-Lock
- Die großen Schwächen von 2PL sind mangelnde Lese-Skalierbarkeit und Live-Lock bei den Progress-Garantien
- Klassisches 2PL ist auf Basis exklusiver Locks entworfen, sodass schon zwei Threads, die denselben Record nur lesen, in Konflikt geraten können und einer oder beide nach Abort neu starten müssen
- Ersetzt man dies durch Reader-Writer-Locks, sinken die Lese-Lese-Konflikte, allerdings steigen Lock-Kosten und Speicherverbrauch
- Exklusive Locks lassen sich mit 1 Bit für gesperrt/entsperrt implementieren
- Reader-Writer-Locks benötigen zusätzlich zu diesem Bit einen Zähler für die Zahl der Reader, die den Lock aktuell im Lesemodus halten
- Ein 7-Bit-Zähler kann zum Beispiel bis zu 128 Threads darstellen, sodass jeder Lock 1 Byte belegen kann
- Bei Milliarden von Records in einer Datenbank können allein die Locks Milliarden von Bytes beanspruchen
- Das größere Problem ist jedoch die Contention auf diesem Zähler
- In read-non-disjoint Workloads konzentrieren sich viele Lesezugriffe auf dieselben Daten
- Ein typisches Beispiel ist der Wurzelknoten eines binären Suchbaums, der bei allen Operationen gelesen werden muss, bevor zu tieferen Knoten abgestiegen wird
- In 2PL muss bei jedem Zugriff auf die Wurzel ein Lock erworben werden; selbst mit Reader-Writer-Locks entsteht daher starke Contention auf dem Lock des Wurzelknotens
Bestehende Ansätze und ein skalierbarer Read-Indicator
- TLRW ist ein Ansatz von Dave Dice und Nir Shavit aus der SPAA 2010, der mit Reader-Writer-Locks eine bessere Performance als exklusive Locks erreicht, aber nicht so schnell wie optimistische Nebenläufigkeitskontrolle ist
- Wendet man – ähnlich wie bei TLRW – eine Implementierung an, bei der jeder Lesezugriff auf eine einzelne Variable des Reader-Writer-Locks konkurriert, auf einen Rank-based Relaxed AVL-Binärsuchbaum an, bleibt die Skalierung sowohl für Schreib- als auch für Lesetransaktionen weitgehend flach
- Read-indicator contention lässt sich mit einem skalierbaren Read-Indicator entschärfen
- Die bevorzugte Methode ist ein Reader-Writer-Lock, bei dem jeder Reader sein Kommen und Gehen in einer separaten Cache-Line markiert
- Beim Erwerb eines Read-Locks gibt es dann keine Contention mehr
- Ein Thread, der einen Write-Lock erwerben will, muss jedoch alle Cache-Lines scannen, um zu prüfen, ob das zulässig ist; dadurch steigen die Kosten für den Erwerb des Write-Locks
- NUMA-aware Reader-Writer-Locks behandeln Reader-Writer-Lock-Algorithmen, die diese Technik einsetzen
- Zwei der drei dort vorgestellten Reader-Writer-Lock-Algorithmen skalieren stark, sind aber nicht starvation-free
Das Reader-Writer-Lock-Design von 2PLSF
- Two-Phase Locking Starvation-Free (2PLSF) ist eine Nebenläufigkeitskontrolle, die mit einem Reader-Writer-Lock implementiert ist, der beim Erwerb von Read-Locks gut skaliert und zusätzliche Eigenschaften mitbringt
- Der Reader-Writer-Lock von 2PLSF reserviert für den Read-Lock 1 Bit pro Thread
- Diese Bits liegen in ihren eigenen Cache-Lines
- Sie werden zusammen mit den Read-Indicator-Bits benachbarter Locks angeordnet
- Wie schon im Paper zu NUMA-aware Reader-Writer-Locks wird der Aufwand auf den Erwerb des Write-Locks verlagert
- Ein Write-Lock muss mehrere Cache-Lines scannen
- Das ist keine magische Lösung, sondern ein Trade-off
- Dieser Trade-off ist nützlich, weil die meisten Workloads read-heavy sind und selbst write-intensive Workloads einen erheblichen Teil ihrer Zeit mit Lesezugriffen verbringen, etwa beim Nachschlagen von Records
- Mit dem verbesserten Reader-Writer-Lock lässt sich 2PL auch bei read-non-disjoint Workloads skalieren, doch das Live-Lock-Problem muss separat gelöst werden
Welche Progress-Probleme 2PL-Varianten offenlassen
- Klassisches 2PL kennt je nach Konfliktbehandlung typische Varianten wie No-Wait, Deadlock-detection und Wait-Or-Die
-
No-Wait
- Tritt ein Konflikt auf, wird entweder die eigene Transaktion oder die Gegen-Transaktion abgebrochen und erneut versucht
- Der Retry kann sofort erfolgen oder später mit exponentiellem Backoff
- Wenn eine Transaktion erst Record A und dann B ändern will und eine andere erst B und dann A, können beide immer wieder kollidieren und in einer Schleife aus Abort und Restart festhängen, ohne je zu committen; das ergibt nur Live-Lock-Progress
-
Deadlock-detection
- Dabei wird eine Liste wartender Threads pro Lock geführt und auf Zyklen, also Deadlocks, geprüft
- Bei Reader-Writer-Locks muss jeder Reader eine eigene Liste haben, zusätzlich braucht jede Liste wieder einen exklusiven Lock zu ihrem Schutz
- Beim Erwerb eines Locks im Read-Modus müssen alle Reader-Listen gescannt werden, was teuer ist
- Theoretisch könnte damit Starvation-Freedom erreichbar sein, praktisch kollidiert das aber mit dem Ziel, weil dafür starvation-free Locks nötig wären und keine veröffentlichten hochskalierenden starvation-free Reader-Writer-Locks existieren
- Eigene Listen pro Reader können außerdem den Speicherverbrauch deutlich erhöhen
-
Wait-Or-Die
- Allen Transaktionen wird eine Reihenfolge zugewiesen; bei Lock-Konflikten wird anhand des Transaktions-Timestamps und des Timestamps des Lock-Besitzers entschieden, ob gewartet oder abgebrochen wird
- Bei exklusiven Locks funktioniert das gut, weil sich der Besitzer mit einer eindeutigen Thread-ID im Lock selbst speichern lässt
- Um dasselbe bei Reader-Writer-Locks zu tun, wäre für jeden Reader eine Thread-ID nötig
- Für die Unterstützung von 256 Threads wären pro Reader-Writer-Lock 8 Bit × 256 = 256 Byte erforderlich
Der Flaschenhals eines zentralen atomaren Zählers und der Unterschied von 2PLSF
- Das größere Hindernis bei Wait-Or-Die ist, dass jede Transaktion eine eindeutige Transaktions-ID haben muss
- Diese Reihenfolge lässt sich zum Beispiel erzeugen, indem eine Nummer per fetch_and_add() aus einer zentralen atomaren Variable geholt wird
- Auf den meisten modernen CPUs ist es schwer, bei umkämpften atomaren Variablen mehr als 40 Millionen
fetch_and_add()-Operationen pro Sekunde zu erreichen- Verglichen mit den rund 660 Millionen täglichen Transaktionen von Visa mag das groß erscheinen
- Für In-Memory-DBMS oder konkurrierende Datenstrukturen ist es jedoch möglicherweise nicht groß genug
- Auf einer Testmaschine war es schwer, über 20 Millionen
fetch_and_add()pro Sekunde hinauszukommen
- Diese
fetch_and_add()-Operation ist nicht nur für Schreibtransaktionen nötig, sondern für alle Transaktionen einschließlich Lesetransaktionen, was die Skalierbarkeit begrenzt - TL2 führt für Lesetransaktionen kein atomisches
fetch_and_add()aus, sondern nutzt optimistische Reads- Damit kann es aus Sicht von Lesetransaktionen bis in den Bereich von Hunderten Millionen tps skalieren
- Ein auf Wait-Or-Die basierendes 2PL kommt dagegen nicht über 40M tps/sec hinaus
- 2PLSF versieht nur Transaktionen mit einer Reihenfolge, die tatsächlich in einen Konflikt geraten
- Dadurch sinkt die Zahl der Transaktionen, die auf der zentralen atomaren Variable
fetch_and_add()ausführen müssen - Konfliktfreie Transaktionen sind nicht an das Plateau von 40M tps gebunden
- Beispielsweise könnten 200M tps konfliktfrei laufen, während nur die 40M tps mit Konflikten an die
fetch_and_add()-Grenze stoßen - Der Algorithmus bietet starvation-freedom
- Dadurch sinkt die Zahl der Transaktionen, die auf der zentralen atomaren Variable
Materialien und abschließende Bewertung
- Auf den 2PLSF-Algorithmus selbst wird nicht im Detail eingegangen, er gilt jedoch für einen starvation-free Algorithmus als vergleichsweise einfach
- Als Referenzen werden ein Paper und der Source Code genannt
- 2PLSF wird außerdem mit einem ACM-Paper verknüpft und als Algorithmus von Pedro Ramalhete, Andreia und Pascal Felber beschrieben
- Das Ziel von 2PLSF liegt nahe an den Eigenschaften, die 2PL von Anfang an hätte haben sollen
- Es skaliert auch in read-non-disjoint Szenarien mit überlappenden Lesezugriffen gut
- Es bietet starvation-free Transaktionen als stärkste Form von Blocking-Progress
- Es kann auch in manchen Konfliktsituationen skalierbar bleiben
- 2PLSF ist nicht perfekt, wird bei der Konfliktauflösung aber als besser als TL2 bewertet; der Unterschied zu herkömmlichem 2PL wird mit dem Unterschied zwischen Spitzhacke und Presslufthammer verglichen
1 Kommentare
Hacker-News-Meinungen
Mich interessiert, was die Best Practices der Branche sind, wenn man in einer verteilten Microservices-Architektur mehrere Datenspeicher synchronisieren oder „konsistent“ halten will.
Vor ein paar Tagen habe ich versucht, Inkonsistenzen mit einem „settled timestamp“ zu lösen; das ist eher ein Multiversions-Ansatz, bei dem ein Speichern/Commit als gültig gilt, wenn Zeit vergeht, ohne dass Fehler gemeldet werden. Beim Two-Phase Commit ist die zweite Phase sozusagen die Zeit.
Der Ansatz war, die Uhren anderer Server zu überwachen und, wenn sie nicht aktualisiert werden, dem settled timestamp dieses Servers nicht zu vertrauen. Da man bei jedem Update nicht auf eine Antwort warten muss, sondern nur auf das nächste timestamp-Intervall, sollte sich Konsistenz damit auf viele Server skalieren lassen.
Ich habe Multithreading-/Multiprocessing-Code in Python geschrieben, der mit 10 Threads, die zufällige Updates austauschen, Nichtdeterminismus testet: https://replit.com/@Chronological/InconsistencySimulation#ma...
In dieser Simulation ist ein Read der kleinste aller von allen Servern gemeldeten timestamps; wenn man nach 10 Sekunden jeden Thread nach dem Zählerwert fragt, liefern manchmal alle denselben Wert, aber ziemlich oft entsteht ein Split-Brain-Zustand.
Mir ist klar, dass Wall-Clock-timestamps in verteilten Systemen nicht zur Ordnungsbestimmung geeignet sind und man logische Uhren oder Vektoruhren verwenden sollte.
Es wäre schön, die Simulation so hinzubekommen, dass sie zu jedem Zeitpunkt überall dieselbe Zahl meldet. Bloomlang versucht das Problem zu lösen, dass bei Eventual Consistency spät eintreffende Werte das Ergebnis beeinflussen und es damit nicht linearisierbar ist.
Mich interessiert besonders, wie man unter Wahrung der Konsistenz skaliert, aber das scheint ein ziemlich schwieriges Problem zu sein.
Mehrere Systeme schreiben sequenziell in ein zentrales Journal, und das Journal nimmt Anfragen wie ein Key-Value-Store entgegen. Dieses Journal wird auf alle Nodes repliziert, und die Nodes lesen das Journal, um die angeforderte komplexe Logik auszuführen.
Kubernetes verwendet etcd, daher skaliert es als stark konsistenter Key-Value-Store ziemlich gut.
Da du „mehrere Datenspeicher“ gesagt hast, nehme ich an, dass es um heterogene Daten geht und etwas wie CockroachDB keine Option ist.
Wenn du Anfänger bist, ist Selberbauen riskant. https://aphyr.com/ ist so etwas wie der Maßstab für Tests und auch als Lernmaterial hervorragend. Man kann verteilte Systeme mit Jepsen testen, aber besser ist es, einen Datenspeicher zu verwenden, den Kyle als robust gezeigt hat.
Ich bin mit diesen Techniken nicht sehr vertraut, aber als ich Datenbanken gelernt habe, wurde SSI als die künftig „bessere“ Variante von Two-Phase Locking vorgestellt. Mich interessiert, wie sich SSI von 2PLSF unterscheidet und warum es hier nicht erwähnt wurde.
Bei verteilten Effekten braucht man aber weiterhin Locks, Two-Phase Transactions usw. Persönlich sehe ich das eher als komplementäre Funktionen denn als Ersatz.
Bei In-Memory-Datenstrukturen ist das naheliegend, aber wenn man mit einer externen Datenbank oder einer anderen gemeinsam genutzten externen Ressource arbeitet, gibt es möglicherweise bessere Wege.
Oft kann man Anfragen batchweise verarbeiten und die externe Ressource mit geringerer Parallelität, aber größeren Payloads ansprechen. Wenn diese Ressource Batches gut verarbeitet, sinken die nötige Nebenläufigkeit und das Locking deutlich.
Wenn man zum Beispiel Postgres verwendet, sinkt die Zahl der Verbindungen, und man muss vielleicht kein PgBouncer hinzufügen, das zusätzliche Komplexität bringt.
Allerdings passen Request-Batches nicht gut zu den meisten Programmiersprachen. Sprachen, die für hohe Nebenläufigkeit optimiert sind, wie Go mit Channels oder Elixir mit Prozessen, können das gut, aber in Sprachen, die alles mit Threads erledigen, kann es schmerzhaft sein.
Bei Websites, die nicht auf HTTPS aktualisiert werden können, erscheint eine Warnung; Websites, die beides unterstützen, werden direkt auf die HTTPS-Version umgeleitet.
Und wenn der HTTP-Link von einem guten Nebenläufigkeitsalgorithmus handelt, würde ich ihn trotzdem lesen.
fetch_and_add, um eine Transaktions-ID zu bekommen? Ich frage mich sogar, ob man überhaupt eine Transaktions-ID braucht.Das Ziel klingt danach, zwischen aktiven Transaktionen eine beliebige, aber konsistente Reihenfolge festzulegen, damit sie sich bei Konflikten darauf einigen können, wer wartet und wer „stirbt“. Könnte man dafür nicht die Thread-ID verwenden?
Eine Zufallszahl könnte auch funktionieren. Wenn man Gleichstände als „Tod“ behandelt, werden im schlimmsten Fall beide Transaktionen unnötig abgebrochen und einfach mit einer neuen Zufallszahl erneut versucht.
Es wurde zwar nicht erwähnt, aber offenbar soll älteren Transaktionen Vorrang gegeben werden, damit lang laufende Transaktionen nicht von kurzen Transaktionen ausgehungert werden. Wenn zum Beispiel eine lange Transaktion im Schnitt mit drei kurzen Transaktionen kollidiert und der Gewinner bei jeder Kollision im Grunde zufällig ist, beträgt die Wahrscheinlichkeit, dass die lange Transaktion alle drei Male gewinnt und committen kann, nur 1/8.
Um Starvation zu verhindern, muss man aber nicht jedes Mal die ältere Transaktion bevorzugen; in den meisten Fällen reicht es. Insbesondere dann, wenn sie nur ganz geringfügig älter ist.
Daher könnte etwas wie ein Timestamp oder ein Cycle Counter gut funktionieren, selbst wenn es zwischen Threads Clock Skew oder andere Ungenauigkeiten gibt. Gleichstände kann man per Thread-ID auflösen oder ebenfalls beide Seiten abbrechen lassen.
Passt gut für diesen und viele andere Fälle.
Two-Phase Commit ist ein sinnvoller Vergleichskandidat zu Paxos, und beide fallen in die Kategorie der Konsensprotokolle.
Two-Phase Locking ist ein Mechanismus zur Concurrency Control.
Wenn die erste Lock-Nachricht verloren gegangen ist, lautet das Problem: Woher weiß man, dass nicht die Antwortnachricht verloren ging?
In einfachen Fällen kann man wie GitHub oder Dropbox einfach weitermachen und Konflikte später behandeln. Bei einer Datenbank braucht man Glück, bei einer Bank erst recht.
Bei Read-only-Transaktionen muss TL2 die globale Version sampeln und dann bei jedem Read prüfen, ob die lokale Version höchstens der gesampelten Version entspricht.
Daher ist schwer zu verstehen, warum der Graph sublinear ist und warum TL2 nicht so schnell ist wie andere STM-Implementierungen.
Nehmen wir zum Beispiel 1000 normale Jobs und 10–100 Hardware-Threads an.
Man erstellt eine sortierte Liste der 1000 Jobs, legt für jeden Thread eine Kopie davon an und randomisiert jedes Mal die Reihenfolge der Kopie.
Dann kann jeder Thread seine Liste lesen, die Jobs ausführen und anschließend eine Liste abonnieren, die als nicht blockierende Multi-Thread-Queue implementiert ist.
Im schlimmsten Fall führen einige Threads einen Job wiederholt aus.
Mit diesem Ansatz könnten atomare Operationen um bis zu den Faktor 1000 skalieren.