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