Wiki{IN}

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== 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:
      - altes Tupel invalidieren
      - 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