TIS-Workshop 2023/24

Vortragsmitschrift von A. Schollmeyer.

• 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

• 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

• 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

• 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

• 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

• 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
  • 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

• 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

• 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

• 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

• 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

• 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