Modul 10: In Memory Datenbanken Flashcards
Agenda
- Motivationsübung
- Gründe/Motivation für
In-Memory Datenbanken - Fortschritte bei der
Hardware Entwicklung - Partitionierung
- Kompression
- Tupel Rekonstruktion
- Scan Performance
- Auswirkungen von DML Statements
- Re-Merge des Differential Buffers
- Indizes
- Aggregate
- Logging und Recovery
- Data Aging
- Reorganisation
Was bedeutet der Begriff Dictionary Encoding im Column Store?
• Spalte wird in ein Dictionary und einen Attributvektor geteilt
• Dictionary speichert alle vorkommenden Werte genau einmal und versieht
sie mit einer ValueID
• Attributvektor speichert für jedes Element in der Spalte die entsprechende
ValueID
• Keine Zeilen mehr!
Was spricht für In Memory Datenbanken?
Unterpunkt: Was sind typische Applikationen in Unternehmen?
1. Transactional o Transaktionale Applikationen o User Interaktionen o Maschinen 2. Analytics o Reporting o Planung o Simulation 3. Event Processing o Maschinen o Sensoren 4. Text Analyse / Unstrukturierte Daten o Web o Social media o Logfiles o Support Systeme
Konsequenz:
Spezifische (Datenbank-) Applikationen in Unternehmen gehen unterschiedlich mit Datenerfassung, -speicherung und –verarbeitung
um und sind meist entweder für Transaktionen oder Analyse optimiert.
Gründe für IMDB
Gegenüberstellung OLTP vs. OLAP Systeme
OLTP:
- Hohe Anzahl meist einfacher Adhoc Transaktionen
- Viele parallele Nutzer
- Viele Schreib- und Lesezugriffe
- Rollenbasiert
- Kurze Transaktionen
- Kleine Ergebnismenge
OLAP:
- Weniger Transaktionen dafür komplexe Rechenoperationen
- Weniger parallele Nutzer
- Hauptsächlich Lesezugriffe meist für umfassende Berichte
- Für bestimmte Nutzer (Sales Account Executive, Executive Board)
- Lange Transaktionen
- Sehr grosse Ergebnismenge
Gründe für IMDB
Konsequenzen aus der Zusammenarbeit von OLTP und OLAP Systemen nach der Gegenüberstellung OLTP vs. OLAP Systemen
- Hoher Synchronisations Aufwand zwischen Systemen, meist OLTP → OLAP
- Zeitverzug, oft nicht die neusten Daten im OLAP System
- Redundanzen
- Inkonsistenzen
- Unterschiedliche Datenschemas
- Erhöhte Kosten durch Beschaffung und Betrieb
- Hoher Aufwand für Aggregate
- Günstigere Hardware mit grossem Hauptspeicher
Gründe für IMDB
Weshalb ausgerechnet ein Column Store?
- Viele Spalten werden gar nicht genutzt (~50% aller Spalten)
- Viele Spalten haben sehr niedrige Kardinalität (z.B. Land, Geschlecht, …)
- Viele NULL / DEFAULT Werte
- Niedrige statistische Verteilung der Dateninhalte unterstützen Kompression
Gründe für IMDB
Fazit
Sind OLTP und OLAP wirklich so unterschiedlich?
• Analyse über sehr viele Kundensysteme zeigt, dass Schreib- und Lesezugriffe sich nicht
signifikant unterscheiden
• Je nach Industrie sind die Schreibzugriffe sogar sehr gering (Bsp: Banking)
Wunsch der Kunden
• nach EINEM System
• ohne Redundanzen und Inkonsistenzen
Idee/Vision • keine Aggregate • keine Views • alles wird zur Laufzeit errechnet • alle Daten befinden sich im Hauptspeicher / Cache
Fortschritte bei der Hardware
Entwicklung
• Multi-Core Architektur mit bis zu 8 x 28 Core CPU per Blade • Paralle Verarbeitung über Blades hinweg • Blade Server Preis schon unter 50.000€ • Bis zu 24 TB RAM pro Board • Durchsatz > 100 GB/s (Skylake SP, Xeon 8180M, 8-socket) • Kosten / Performance Verhältnis extrem stark fallend • Kopierzeit von 5GB/s mit Infiniband
Blade Server
Blades nutzen eigene Platine mit Mikroprozessor, Arbeisspeicher und
Plattenspeicher
• Zusätzlicher Plattenspeicher kann über SAN oder NAS angedockt werden
• Lüftung nicht zentral sondern über Rückwand
Infiniband
• Bidirektionaler serielles Bus System • Latenzarme Datenübertragung (< 2µs) • Kann Hauptspeicher mehrerer Cores miteinander verknüpfen • Übertragung bis 2,5 GB/s
ermöglicht verteilten Hauptspeicher Zugriff
und Tabellen können somit über
Knoten verteilt werden
Partitionierung von Tabellen
• Parallele Ausnutzung mehrerer Core CPUs, die auf ein Shared Memory
zugreifen, erhöht Verarbeitungsgeschwindigkeit signifikant (→ Blade Server)
• Partitionierung legt Methode fest nach der die Daten verteilt werden und
unabhängige und distinkte Teile
• Kenntnis der Anfrage ist notwendig
Partitionierungsarten
Vertikale Partitionierung
• Aufteilung der Tabelle entlang einer Spalte in Attributgruppen
• Verbindung über Primärschlüssel
Bereichspartitionierung • Auftrennung der Tupel in Bereiche z.B. o In 5 Bereiche nach Kontinent o In 200 Bereiche nach Land o In 5 Bereiche nach Geburtstag: < 1925 < 1950 < 1975 < 2000 < 2025
Hash Partitionierung • Wähle ein Attribut als Hash Kriterium • Lege Anzahl bits fest für Partitionierung (Bsp: 3 bits für 8 Partitionen) • Verteile die Daten gleichmäßig
Applikations Partitionierung • Wähle Kriterien aus der Applikation zur Verteilung • Beispiele: • Bestellzeitraum • Versionen eines Artikels • ....
Datenkompression im Kontext von In Memory Datenbanken und Column Stores
• Für Attributvektoren o Prefix Verschlüsselung o Run Length Verschlüsselung o Cluster Verschlüsselung o Sparse Verschlüsselung o Indirekte Verschlüsselung • Für Dictionary o Delta Kompression o Sortierte Arrays
Prefix Komprimierung
Ersparnis wenn eine Spalte mit einer langen Reihe desselben Wertes beginnt
oder
• ein bestimmter Wert kommt sehr häufig vor und die anderen Werte seltener
• Wert wird nur einmal gespeichert inkl. der Anzahl der Vorkommen
• Voraussetzung: Tabelle sortiert nach Spalte
• Direkter oder nur indirekter Zugriff möglich? → Direkt!
Run Length Komprimierung
Ersetze Sequenz desselben Wertes mit einer einzelnen Instanz des Wertes
und
o Der Anzahl des Auftretens
o Der Startposition
• Direkter oder nur indirekter Zugriff möglich? → Direkt
Cluster Komprimierung
Attributvektor wird aufgeteilt in N Blöcke gleicher Größe (z.B. 512 Byte)
• Wenn das Cluster immer nur einen Wert enthält, erscheint der Wert nur
einmal
• Wenn das Cluster unterschiedliche Werte enthält, werden diese 1:1 dort
abgelgt
• Ein Bitvektor zeigt an, ob Fall 1 oder Fall 2
• Direkter oder nur indirekter Zugriff möglich? → Indirekt, nur über Bitvektor
möglich!
Verstreute (Sparse) Komprimierung
• Attributvektor wird nach häufigstem Wert durchsucht
• Ein Bitvektor zeigt an an welcher Stelle der Wert entfernt wurde
• Direkter oder nur indirekter Zugriff möglich? → Indirekt, nur über Bitvektor
möglich!
Indirekte Komprimierung
AV ist partitioniert in N Blöcke der Größe S (z.B. 512)
• Wenn der Block viele verschiedene Einträge enthält → keine Aktion
• Wenn Block wenige unterschiedliche Einträge enthält → Block wird mit
Dictionary Encoding komprimiert
• Direkter oder nur indirekter Zugriff möglich? → Direkt!
Delta Komprimierung
Für Dictionary Tabelle
• Macht Sinn bei Sortierung
• Blockweise Komprimierung
Fazit aus der Beschreibung der verschiedenen Komprimierungsarten
• Unterschiede zwischen Attributvektor und Dictionary Komprimierung
• Direkt oder nur indirekter Zugriff möglich
• Meist sortierte Spalten nötig, Tabellen können nur nach einer Spalte sortiert
werden
INSERT im Column Store
• INSERT INTO Weltbevoelkerung
VALUES („Bernd“, „Schulze“, m, „GER“, „Niedertupfingen“, 08.08.1988)
• Spaltenweises Einfügen
• Jeweiliges Prüfen ob Wert im Dictionary vorhanden ist oder nicht
Ist der Wert im Dictionary vorhanden -> Wert im Attributvektoraufnehmen
Ist der Wert im Dictionary nicht vorhanden -> Wert in Dictionary einfügen und entsprechenden Wert im Attributvektor einfügen
UPDATE im Column Store
• UPDATE = DELETE + INSERT
• 3 Arten von Updates
o Unverschlüsselt
o Verschlüsselt mit unsortiertem Dictionary
o Verschlüsselt mit sortiertem Dictionary häufigster Fall
DELETE im Column Store
Lösche Eintrag im Attributvektor • Sortiere AV neu • Falls nicht letzter Eintrag im Dictionary: evtl. Dictionary neu aufbauen
Ursachen Reorganisation im
Column Store
Gründe für Reorganisation des Dictionary oder des Attributvektors
• Einfügen/Ändern neuer Werte ins Dictionary
→ Reorg Dictionary → Reorg Attributvektor
• Breite des Dictionary verlängert sich
→ Komplettumbau Dictionary → Reorg Attributvektor
• Löschen einer Zeile (ohne Dictionary Auswirkung)
→ Zusammenschieben des Attributvektors
• Einfügen einer Zeile (ohne Dictionary Auswirkung)
→ Auseinanderziehen des Attributvektors
Vermeidung Reorg im Column Store
Reorganisation des Dictionary und des Attributvektors sehr aufwändig! • Vermeidungsansatz 1 o Datensätze nie löschen o Gültigkeit mit Zeitstempel kenntlich machen • Vorteil o Integrierte Historie o Automatisches Logging o Einfache Snapshots o Keine Reorgs mehr • Nachteil o Anstieg Speicherbedarf
Vermeidung Reorg im Column Store 1: Zeitstempel
• Einführung einer extra Spalte „Gueltig_ab“ (oder „Gueltig_bis“)
• INSERT / UPDATE hat keinen Effekt auf alte Tupel
• SELECT Operationen müssen immer das letzte Tupel ausfindig machen
→ kann mit Bitvektor entschärft werden
Vermeidung Reorg im Column Store 2: Bereiche ?
Vermeidungsansatz 2
o Einführung eines separaten Bereichs, der alle Änderungen beinhaltet → Delta- / Differential Buffer
o Lesen zuerst aus DiffBuff, wenn nicht vorhanden dann aus Hauptspeicher
o Schreiben nur in DiffBuff
• Vorteil
o Inserts schnell, da kein Reorg oder Re-Sort
• Nachteil
o Differential Buffer braucht zusätzlichen Speicher
o Range SELECT über DiffBuff und Hauptspeicher aufwändiger und damit langsamer
o Zusätzlicher Gültigkeitsvektor notwendig
o Regelmäßiger Re-Merge von DiffBuff und Hauptspeicher nötig
Was bedeutet es den Differential Buffer mit dem Hauptspeicher zu verschmelzen?
Welchen Grund hat die Verschmelzung?
Alle Schreiboperationen (INSERT, UPDATE, DELETE) werden immer
zunächst im Differential Buffer eingetragen
• Veränderte Werte im Hauptspeicher werden mit Gültigkeitsvektor
ungültig geflagged
• Es werden immer nur die „gültigen“ Datensätze auf Differential Buffer
und Hauptspeicher gelesen
• Problem: Lesen auf Differential Buffer und Hauptspeicher verlangsamt
Performance
• Abhilfe: regelmäßiges Zurückschreiben des Differential Buffers in den
Hauptspeicher, sowohl Dictionary als auch Attributvektor
Verschmelzung des Differential Buffers mit Anleitung
Vorüberlegungen:
Bevor damit begonnen werden kann einen Differentialbuffer mit dem Hauptspeicher zu verschmelzen ist es notwendig, über einen Differentialbuffer zu verfügen den man Mergen kann.
Mit anderen Worten heißt das, man benötigt Änderungen in der der Datenbank zugrunde liegenden Relationen.
Sind Änderungen vorhanden kann der Mergeprozess wie folgt durchgeführt werden.
Schritt 1: Gültigkeitscheck
alle ungültigen Records landen im History File
Schritt 2: Dictionary kombinieren
Der Inhalt der beiden Dictionnaires wird lexografisch korrekt miteinander kombiniert.
Schritt 3: Mapping von altem Diffbuff + HSP Dictionary auf das neue Dictionary
Es wird eine Mapping Tabelle die beschreibt in wiefern der Kombinationsprozess aus Schritt 2 die einzelnen Tupel in der Relationsstruktur vertikal verschoben hat.
Schritt 4: Aktualisierung des Attributvektors
Mithilfe des Mapping aus Schritt 3 kann nun der entprechende Attributvektor aktualisiert werden
5.Schritt: Differential Buffer auflösen und neue HSP Attributvektor und Dictionary aufbauen
Kombination der gerade aktualisierten Attributvektoren aus Schritt 4.
Dictionary Indexierung eine Einführung:
Was ist der Hintergrund zur Dictionary Indexierung.
Was ist ein Delta Index?
• Delta ist klein, braucht aber schnelle Performance bei INSERT
• Wie finde ich schnell den Wert zu einer Value ID im Dictionary? Oder
umgekehrt?
• Nutze B+ Bäume
o Value ID = Knoten
o Werte = Verweis auf sortiertes Dictionary
Wie wird die Dictionary Indexierung umgesetzt?
Schritt 1: Sortieren des Attributvektors in festgelegter lex. Reihenfolge von Dictionary
Schritt 2: Run Length Encoding des sortierten Attributvektors aus Schritt 1
Verlauf einer typischen Attributleseprozesses aus Attributvektor
- Finde gesuchtes Attribut in Dictionary
- Finde die Row Id des Attributs
- Finde den Offset in IO
- Hole Offset des nächsten Wertes
- Suche in diesem Intervall Offset 2 - Offset 1
- Hole Rowids
Aggregate
• Aggregate arbeiten auf Datenmengen und nicht auf einzelnen Records
• Mit HAVING kann die Datenmenge noch einmal eingeschränkt werden
Typische Aggregat Funktionen: COUNT, SUM, AVG, MAX, MIN,
MEDIAN, …
Aggregat Cache
• In RDBMS werden Aggregate auf unterschiedliche Weise vorgehalten
o OLAP: Materialisierte Views
o OLTP: Applikation hält interne Tabellen oder Wertebereiche vor
• Nachteile
o Applikationslogik wird komplizierter
o Verlangsamung bei Schreiboperationen
o Erzeugung von Redundanzen
o Unflexible Analyse, da bei neuen Abfragen erst die Aggregat Tabellen angepasst werden müssen
• Ziel
o Vermeide vordefinierte materialisierte Aggregate und Summen Tabellen
o Ausführung von OLTP und OLAP Abfragen in einem System
o Komplexitätsreduktion
o Flexible Realtime Analyse
• Idee
o Lege Aggregat Ergebnisse in den Hauptspeicher
o Errechne neue Aggregate, die durch Änderungen entstehen, zur Laufzeit und lege sie um Differential
Buffer ab
o Für jedes SELECT xxx FROM yyy GROUP BY zzz HAVING wird ein eigener Eintrag erstellt
o Aggregat Erstellung wird verzögert bis zum Delta Merge
o Aggregate nach INSERTs werden durch Laufzeit Aggregation im DiffBuff aufgefangen
o Aggregate nach UPDATE und DELETE werden durch Bitvektoren im Hauptspeicher und DIffBuff
kenntlich gemacht und neu berechnet
Aggregat Cache Auflösung
• Ziel o Limitiere Cache Wachstum o Halte Maintenance niedrig • Kostenbasierte Ansätze o Anzahl Tupel o Anzahl Berechnungen o Ergebnismenge o Anzahl Invalidierungen des Hauptspeichers
Logging und Recovery
Was ist der Hintergrund von Recovery?
Wie ist Recovery definiert?
Welche Varianten von Recovery gibt es?
Hintergrund
• Ausfallsicherheit
• Notwendigkeit bei Rechnerausfall auf letzten „commited“ Zustand
zugreifen zu können
• Definition: Recovery ist der Prozess ein System nach dessen Ausfall auf
den letzten Stand vor Absturz zurück zu bringen
• Ziel dabei ist möglichst kurze Recoveryzeit ohne Datenverlust
• Varianten:
o Logfile auf Backup Medium Schreiben
o Replication des(r) kompletten Server(s) auf replizierte Datenbank
Logging
Aus welchen Verfahren setzt sich Logging zusammen?
Snapshots werden periodisch geschrieben • Logfiles für Updates werden zwischen den Snapshots geschrieben • Dictionary Änderungen werden separiert geschrieben
Logging
Wie sind die Verfahren im einzelnen definiert?
• Snapshots schreibt die Primärdaten periodisch auf persistenten Speicher
und werden meist nach Merge Prozess erstellt
• Im Logging werden Update/Delete/Insert Statements mit Parametern in
komprimierter Form im Logfile abgelegt
• Im Dictionary Log werden alle Dictionary Änderungen in komprimierter
Form abgelegt
Dictionary Logging
Wie findet Dictionary Logging im Detail statt?
Welche Logs werden während des Dictionary Logging erstellt?
Welche Vorteile hat das Dictionary Logging?
• Schreibe Dictionary Änderungsdaten entkoppelt von Transaktionen
• ValueID Vektor und Dictionary Daten können separat recovered werden
• Logfile Größe kleiner
• 3 unterschiedliche Logs:
o Dictionary Logs (d) für komplettes Dictionary (Tabellen ID, Spaltenindex, Value ID)
o Value Logs (v) für Value Vektor (Transaktions ID, Tabellen ID, Zeilen ID, Value ID Vektor)
o Transaction Logs (t) halten Transaktions ID, die nach jedem Flush erhöht wird
Hat Vorteile bei
• Langen Daten, die mehrfach eingetragen werden
• Anzahl distinct values ist niedrig
Recovery
Wie findet die Recovery einer Datenbank statt, gehen Sie insbesondere auf den mit dem Recovery Prozess verbundenen Auslesen der Inhaltsdaten ein?
- Lese Metadaten aus letztem Snapshot und Transaktions ID der letzten
Transaktion aus dem Snapshot - Lese Inhaltsdaten in parallelisierter Form
a) Hauptspeicherdaten vom Snapshot
b) Dictionary vom Differential Buffer durch Einspielen der Dictionary Logfiles
c) Einlesen der Value ID Vektoren aus dem Differential Buffer
Data Aging
Was ist der Unterschied zwischen Data Aging und Data Archiving?
In Bezug auf die Motivation, Methode, dem Umgang mit Daten die hinter den Verfahren steckt, sowie auf den Zeitpunkt seit dem die Verfahren eine Rolle spielen.
Data Aging vs Data Archiving Motivation Data Aging: Performance und Datenvolumen Optimierung Data Archiving: Legale und Compliance Anforderung
Methode Data Aging: Datenschema bleibt gleich Data Archiving: Transformation in Archivformat
Umgang mit Daten
Data Aging:
„Alte“ Daten bleiben erhalten und direkt
zugreifbar (Applikationstransparent)
Data Archiving:
Archivierte Daten werden explizit
wieder eingespielt. Nicht sichtbar für
Standard Abfragen
Seit Wann Data Aging: Neue Herausforderung Data Archiving: Schon immer
Data Aging
Was ist Data Aging und warum benötigt man es?
Relevante Daten (Hot Data) sollten nicht behandelt werden wie irrelevante Daten (Cold Data)
Grund:
• Daten „veralten“ immer schneller
• Datenmenge steigt rapide an (Bsp. IOT, …)
• Kosten für Hauptspeicher für Speicherung irrelevanter Daten viel zu hoch
• Performance - insbes. bei JOINs und Aggregaten (Potenzierung!)
o Buffer
o Pagelist
o Indizes
Wie lässt sich Data Aging umsetzen? Hat die Umsetzungidee Probleme ? Wenn Ja, wie lassen sich einige der Probleme lösen?
Idee:
• Identifiziere Hot Data als all die Daten, auf die zugegriffen wird und verankere sie
im Hauptspeicher
• Identifiziere Daten, die nicht mehr verwendet werden als Cold Data
• Verlagere Cold Data auf Sekundärspeicher bzw. Flash
• Applikation darf keine Abhängigkeit zu Datenalter und Speicherort haben
Problem:
• Vorab nicht immer klar wie sich alte und neue Daten unterscheiden
Lösung:
• Analyse der typischen SQL Abfragen und Datentreffer zur Laufzeit
• Erstellung Nutzungsstatistiken
• Festlegen von dynamischen Aging Regeln
• Horizontale (Projektion) und vertikale (Selektion) Datentrennung
Fazit zum Data Aging Verfahren
Zusammenfassung:
• Reduktion der Daten im Hauptspeicher auf Hot Data
• Identifikation der Daten durch Analyse der Applikation (Queries +
Statistiken)
• Verlagerung der Cold Data auf günstigeren Sekundärspeicher (z.B. Flash)
• Applikation selbst kennt keine Unterscheidung von Hot und Cold Data!
• Vorteil: bessere Performance und günstigere Kosten
• Nachteil: zusätzliche Intelligenz im DBMS
Datenbank Reorganisation
Was wird unter DB Reorg verstanden?
Was sind die Ursachen eines DB Reorg?
Häufiges Problem in DBMS
• DB Schema und Daten Layout ändern sich während des Betriebs
Ursachen
• Neue DB Version mit neuen Master Tabellen
• Anpassungen der Tabellen und Indizes wegen Performance Verbesserungen
• Schema Anpassung durch Applikationsänderung
Datenbank Reorganisation beim Rowstore
Row Store
• Datensätze liegen fast immer Seite an Seite auf DB Page
• Änderungen am Schema bspw. ALTER TABLE Add
bewirken komplette Neuverteilung der Datensätze auf die
einzelnen Seiten
• Während der Reorganisation ist die komplette Tabelle gesperrt!
• Je nach Tabelle muss u.U. die komplette Datenbank herunter gefahren
werden
• Schon kleine Änderungen wie bspw. Verlängerung eines Feldes können
extreme Auswirkungen haben
Wie können die Probleme, die bei der Datenbank Reorganisation des Row Stores auftreten gelöst werden?
Hat die Lösung Nachteile?
Mögliche Lösung für Row Store
• Es wird eine neue Tabelle angelegt, die nur die neuen bzw.
veränderten Datentypen enthält
• Über die ursprüngliche Tabelle sowie wird eine View gelegt
➔Nachteile:
• Ggfs. schlechtere Performance wegen verteilten Daten
• Overhead für Verwaltung
• Komplexität steigt
Datenbank Reorganisation beim Column Store
Column Store
• Jede einzelne Spalte wird völlig unabhängig von den Nachbarspalten
abgelegt!
• Hinzufügen oder Verlängern von Spalten, Ändern des Datentyps problemlos
möglich, da eigener Speicherbereich
• Kein Tabellenlock!
• Nur das DDIC muss kurze Zeit gesperrt werden
