TIS-Workshop 2023/24

Vortragsmitschrift von A. Schollmeyer.

Komplexität der Verfahren zur Herstellung der Atomarität

Logging
- Logbuch
  - Änderungen persistent schreiben
  - bei Absturz nachvollziehbar, welche Änderungen geschrieben wurden und welche noch (rückgängig) gemacht werden müsse
  - zwei Arten zu schreiben:
    - physisch: komplette seite speichern
    - logisch: nur änderungen speichern
- Recovery-Arten:
  - Deferred Update
  - Immediate Update
  - Checkpoint
- Write-Ahead-Logging (WAL)
  - wird hauptsächlich eingesetzt
Shadow Paging
- Zeiger auf Speicherseiten
- bei Transaktion neue Shadow Page erzeugen, auf der gearbeitet wird
- bei Commit Zeiger auf veränderte Seite umbiegen
- Ansätze zur Kostensenkung:
  - Copy-On-Write, Copy-On-Modify (erst physische Kopie erstellen, wenn nötig)
  - …
Komplexität
- Logging
  - Undo/Redo sehr teuer
  - Transaktionen O(k · n)
  - Recovery jedes mal merken, wo man ist und Log einspielen, O(k · n)
- Shadow Paging
  - viele Kopien der Seiten müssen verwaltet werden
  - Recovery O(l)
  - Transaktionen O(m)
Analysen:
- stochastisch modelliert
- konkrete Simulationsergebnisse
- allgemein schwer präzise abzuschätzen
  - viele versch. Arten von Verfahren
- Shadow Paging viel Fragmentieru
- Garbage Collection bei Shadow Paging teuer
- Logging starker Overhead bei Commits

Antworten in Q&A
- Logging weiter verbreitet, in versch. Varianten
- Komplexität schwierig abzuschätzen
  - formal kaum untersucht, hauptsächlich Simulationen und stochastische Modelle
  - angegebene Komplexitäten eher Abschätzungen

Praktische Realisierung von MVCC in DBMS

MVCC vermeidet Sperren durch Behalten mehrerer Versionen je Datum plus Gültigkeit
- regelt Sichtbarkeit für die einzelnen Transaktionen
- aktualisierung zwei Schritte nötig:
  1. altes Tupel invalidieren
  2. neues Tupel einfügen
Beispiel Postgres
- an Tupeln jeweils Metadaten dran
- `t_xmin` und `t_xmax` TX-IDs
- Sichtbarkeit über ganze Reihe versch. Funktionen implementiert für versch. Zwecke
  - interessant: Prüfung, ob eigene Transaktion älter als `t_xmin`, dann dürfen wir Datensatz sehen
- Transaktionen
  - viele Funktioinen dafür vorhanden
  - keine Funktionen zum Löschen von Tupeln gefunden
  - Tupel haben Flag, ob/wann die committet (für `t_xmin` und `t_xmax`) sind
  - Tupel können als dead geflaggt werden, werden dann durch keine noch offene Transaktion mehr gelesen
    - muss man prüfen, ob es noch eine Transaktion gibt, die das Tupel sehen könnte
    - ansonsten kann weggeschmissen werden
  - HTSV
    - Checks, ob Tupel als dead markiert werden können
    - trifft u.A. auf nicht committete ungültige Tupel zu
- Vacuum
  - Befehl zum Aufräumen
  - `VACUUM FULL` baut Tabellen neu auf und übernimmt nur noch sichtbare Tupel
  - normales `VACUUM` gibt nur den Speicher frei
  - kann automatisch durch Postgres ausgeführt werden

Lock Coupling

ausgehend vom Baumprotokoll
- o nur dann von T sperrbar, wenn direkter vorgänger bereits von T gesperrt
- Sperren können jederzeit freigegeben werden
- aber niemals zweimal sperren
sperre auf einen knoten nur dann freigeben, wenn man eine sperre für den nachfolgeknoten hat
- verhindert invalidierung des gelesenen pointers für den nachfolgeknoten
- lesen: max. 2 sperren gleichzeit
- schreiben: geht nicht unbedingt
  - einfüge- und löschoperationen können zu strukturveränderungen führen
  - bspw. wenn knoten nen split/merge erfahren…
  - kann sich auch im baum nach oben propagieren
- frage: ab wann müssen wir nun sperren?
Lösungen:
- sperre wurzelknoten und halte die sperre
  - bottleneck…
- lesesperren für alle vorgänger halten und bei bedarf zu schreibsperren erweitern
  - kann fehlschlagen
  - evtl. Neustart der Operation nötig (alle locks freigeben, neu anfangen)
- bei traversieren des baums „sichere“ knoten finden, die strukturveränderungen abfangen können
  - Löschoperationen: über mindestkapazität (können nicht kollabieren)
  - Schreiboperationen: weit genug unter maximalkapazität (können nicht gesplittet werden)
- Proaktiv Knoten splitten
  - Platz für Einfüge-Operationen
  - Ineffizient im Speicherverbrauch
  - regelmäßiges Neu-Balancieren nötig, weil sonst der Baum immer größer wird
  - nicht gut, wenn man Zeitgarantien braucht
- Andere Baumstrukturen nutzen
  - z.B. Adaptive Radix Tree
    - jegliche Schreiboperationen maximal Änderungen im Vorgängerknoten
    - damit auch max. 2 Sperren gleichzeitig nötig
Optimistic Lock Coupling
- Lese-Sperren keine tatsächlichen Sperren, stattdessen Versionsnummer an jedem Knoten
- bei Freigabe der Sperre Prüfung, ob sich die Versionsnummer geändert hat
- Schreibsperren erhöhen Versionsnummer
ROWEX (Read-Optimized Write Exclusion)
- Lesen: keine Sperren setzen/prüfen
- Schreiben:
  - Sperre nur veränderte Knoten
  - müssen atomar sein
- erfordert Veränderungen an der genutzten Datenstruktur und kann für manche Datenstrukturen nicht anwendbar sein
- funktioniert nicht auf allen Baumdatenstrukturen

Paxos vs. Raft

in verteilten Netzwerken notwendigkeit, Konsens über Werte/Operationen zu erzielen
Paxos und Raft bekannteste Algorithmen dafür
Paxos
- resistent gegen Ausfälle und Netzwerkpartitionen
- drei Phasen
  - Prepare: Anfrage mit Vorschlag für einen Wert
    - schickt der Leader
  - Accept: Antwort auf die Anfrage, akzeptiert oder nicht
    - Leader sagt, welcher Wert akzeptiert werden soll
    - Acceptor sagen, ob Wert akzeptiert wird
  - Learn: Wert eintragen
    - Leader sagt, ob der Wert akzeptiert wurde
    - Acceptor übernehmen akzeptierten Wert
Raft
- einfacher als Paxos
- dennoch robust
- drei Rollen:
  - Leader: Verwaltung des Konsens
  - Follower: Folgt Anweisungen des Leaders
  - Candidate: Möchte Leader werden
- Funktion:
  - Knoten wird zufällig Candidate und dann zum Leader gewählt
  - Leader sendet Logeinträge an Follower
  - Follower akzeptieren Logeinträge
- Ausfälle/Partitionierung wird über Hearbeats erkannt
  - Leader kann nur Logeinträge schicken, wenn mehr als 50% der Knoten erreicht werden
  - zu jeder Runde wird ne Versionsnummer erhöht
    - dadurch erkennbar, wenn ein Knoten abgeschnitten war und jetzt erstmal bei sich den neuen Zustand importieren muss
Vergleich
- Paxos robuster als Raft
- Paxos kann trotz Ausfällen und Partitionierungen Konsens sicherstellen
- Raft kann das auch bei Partitionen, aber nicht so robust wie Paxos
- Paxis komplexer als Raft
- Paxos hat drei Phasen mit vielen Schritten
- Raft hat drei Rollen und wenige Schritte
- Raft lesbarer als Paxos
- Raft leichter implementierbar
Fazit
- beide zuverlässig
- Wahl hängt von den Anforderungen ab
- hohe Robustheit und Fehlertoleranz besser durch Paxos gegeben
  - sonst Raft
- Anwendung in verteilten Datenbanken, Transaktionalen Systemen

Paxos-Commit

für commit wichtig:
- wenn in runde 0, kann phase 1 übersprungen werden
paxos-commit:
- mit mehreren koordinatoren
- objektmanager haben versch. zustände
- leader und mehrere akzeptoren daneben
- commit, falls sich jede instanz auf den wert „prepared“ einigt
ablauf:
- OM wechselt in „prepare“ und sendet „BeginCommit“ and leader
  - Optimierung: Co-Location von Leader und Akzeptoren
    - auf jeden OM einen Akzeptor
- Leader sendet „Prepare“ an OMs
- OMs müssen sich einigen, ob sie mitmachen wollen
  - starten paxos-instanz entweder mit „Prepared“ oder „Aborted“
- Optimierung:
  - sendet prepare nur an mehrheit der akzeptoren
- leader sammelt antworten der akzeptoren ein
- jede paxos-instanz einzeln ausgewertet
- commit-nachricht, sofern _jede_ paxos-instanz sich auf „prepared“ geeinigt hat
- abbruch:
  - 1: OM sendet „Aborted“ für Phase 2a
  - 2: eine paxos-instanz erreicht keinen konsens in runde 0
    - leader muss neue runde mit phase 1 starten
vergleich mit 2pc/3pc
- jeder akzeptor hat rolle des koordinators → toleranz von F ausfällen
- paxos-commit mit einem akzeptor äquivalent zu 2pc
- tolerant und robuster ggü. fehlern
- durch abbrüche/fehler z.T. mehr runden nötig → mehr latenz

was, wenn der leader ausfällt?
- dann übernimmt ein anderer akzeptor später die leader-rolle

Instant Recovery

verfahren zur schnellen Wiederherstellung und Neustart einer Datenbank nach Ausfall
- dient der Reduzierung der Reparaturzeit
heißt nicht, dass es „sofort“ wieder geht, sondern schneller als andere verfahren
- benutzt WAL, checkpoints, protokollarchivierung
- ermöglicht nurgeringe verzögerungen nach ausfällen
singe-page recovery
- für effizten zugriff auf relevante log-einträge
  - zeige auf neuesten log-eintrag einer seite
  - zeiger auf vorherigen log-eintrag innerhalb jedes protokolls
- jedes log zeit auf pagelsn des vorgängers
- im gegensatz zu ARIES zeigen rollbacks auf „do“ log-einträge
- vorteile:
  - reduzierung redundanter infos
  - einheitlich große log-einträge
self-repairing indexes
- verfahren zur detektion und sofortigen wiederherstellung von single-page fehlern
- self-repairing b-tree
  - besitzt +infty, -infty an den grenzen („fence keys“)
    - kinder erben die
  - eltern-zu-kind-zeiger beinhalten erwarteten pagelsn
  - bei fehler
    - lokalisierung über fence keys
    - wiederherstellung der einzelnen seite
  - keine großen veränderungen der datenstruktur nötig
wiederherstellungsprozess
- neue transaktionen bereits nach log-analyse möglich

WAL vs WBL

WAL
- bekanntester Vertreter ARIES
WBL
- erfordert schnellen, byte-adressierbaren nicht-volatilen Speicher (z.B. optane)
  - teure hardware
- Log immer minimal hinter Einträgen in DB
  - erst Daten speichern, dann Log schreiben
- Metadatenstruktur nur auf volatilem Speicher
  - änderungen vor commit immer nur in dirty tuple table eingetragen
  - bei commit änderung auf table heap (nvmem) speichern
    - zusätzlich log-eintrag mit timestamps, bis wohin committet (cp) und was dirty (cd) ist
    - im felerfall vermeiden die timestamps teure scans, weil man einfach alle änderungen zwischen cp und cd als dirty nehmen kann
- recovery
  - nur analyse-phase
  - änderungen zwischen cp und cd einfach ignorieren
  - änderungen committeter tx sind bereits in persistentem speicher
- replikation durch nachträglich erzeugte WAL-logs

Transaktionen in Persistent Memory

brücke zwischen dram und hdd/ssd
redo-logging
- während recovery-time transaktionsaktionen wiederholen
- WAL
- keine rollbacks möglich
undo-logging
- nur transaktionen rückgängig machen, die nicht committet sind
- kompletter log muss gelesen werden
- idempotent
kombination von redo- und undo-logging möglich
CoW
- speichereffizient
- snapshots und versionierung möglich
- speicherfragmentierung
- schlechtere schreibperformance

Software Transactional Memory

mutex nicht durch hardware oder locks, sondern software
grundidee: transaktionen ähnlich zu datenbanken, aber für speicher
alternative zu lock-basierter synchronisation
vorgehensweise:
- threads arbeiten optimistisch, ohne konflikte zu beachten
- konfliktprüfung bei commit, abort im konfliktfall
vorteile
- bessere wartbarkeit des codes
- keine manuelle betrachtung nötig, wann welche locks gesetzt werden müssen
nachteile
- threads können verhungern
- manche operationen nicht umkehrbar (z.B. I/O)
  - können in puffer gehalten und erst bei commit ausgeführt werden, verzögert aber dann die operationen
- geschachtelte transaktionen schwierig
bringt vor allem was, wenn man nur selten geschrieben wird bzw. wenige kollisionen auftreten, wenn geschrieben wird
laufzeitaufwand ist sonst eigentlich ähnlich zu logs
- verbesserung erst durch hardwareunterstützung

Hardware Transactional Memory

realisierung über caches als transaktionsbuffer
- notieren read- und write-sets jeder transaktion
- speicherung geänderter daten im cpu-cache
- konflikterkennung mit cache-kohärenz-protokoll
  - kommunikation zwischen cpus, dass deren caches zueinanderpassen
intel tsx
- erweiterung des cpu-befehlssatzes
- write-set in L1, read in l1 bis lowest-level-cache
- hardware lock elision
  - lock erstmal optimistisch umgehen
  - lock holen, wenn ein abort auftritt
    - dann serielle ausführung erzwingen
- restricted transactional memory
  - bei abort möglich, abort handler auszuführen (dem entwickler überlassen)
- gründe für abbruch
  - konflikte bei datenzugriffen
  - interrupts
  - verdrängung von cachelines aus dem read/write-set
    - z.B. bei zu vielen datenzugriffen
- abbrüche schränken nutzbarkeit ein
  - write-set durch L1 cachegröße beschränkt
  - read-set durch LLC-cachegröße beschränkt
  - auch durch cache-replacement-strategie beeinflusst
  - transaktionen dürfen nicht zu lange dauern (weil interrupts abbruch auslösen)
- serielle fallbacks immer noch nötig
  - keine garantien über die möglichkeit einer parallelen ausführung
- leistungsgewinne trotz einschränkungen
  - allerdings nicht ganz so viel
  - teilweise normales locking vergleichbar schnell
- HTM keine universallösung für synchronisation

Praktische Aspekte der Implementierung von Paxos

3 phasen
- auswahl koordinator
- koordinator sendet wert
- akzeptieren bestätigen wert
herausforderungen
- speicherkorruption
  - speicherversagen (z.B. hardwareprobleme)
  - verlust vergangener promises
  - lösung:
    - checksumme über daten zur erkennung von datenveränderung
    - speicherversagen behandeln wie neuer prozess mit leerem speicher
      - dann erstmal passives mitglied sein und log von anderen instanzen übernehmen
- master leases
  - problem: lesen benötigt eigentlich paxos, aber lesen passiert häufig (wird also insgesamt teuer)
  - lösung:
    - wenn prozess master lease hat, kann kein anderer paxos-knoten daten verändern
    - wird letztem koordinator übergeben
    - keepalive+timeout nötig für fall eines absturzes
- group memberships
  - systeme müssen mit wechselnder anzahl teilnehmer zurechtkommen
  - man muss wissen, was zu jedem zeitpunkt die gesamtzahl der teilnehmer ist

Hardwarebeschleunigte Konensverfahren

motivation
- performanceprobleme bei vielen teilnehmern
- optimierung von software nur in begrenztem maße möglich
paxos beschleunigt durch switche
rollen
- proposer
  - vertritt client
- leader
- acceptor
- learner
latenz ganz wichtig, wie schnell konsens hergestellt werden kann
CPU maßgebliches bottleneck bei software-paxos
p4xos in P4 auf hardware entwickelt
- innerhalb von switches eingesetzt
- geringe latenz
switches übernehmen rollen
- spine-switch ist immer leader
  - dadurch entfällt phase 1
- aggregate-switch ist akzeptor
  - müssen daten über konsens zwischenspeichern, um es später an den eigentlichen node weitergeben zu können
nur für spezialisierte hochleistungsnetze geeignet