In-Memory-Datenbank Theorie und Algorithmen Teil II

SanssouciDB ist ein Entwurf eines Datenbanksystems, das sowohl AnalyticSuche als auch transaktionale Datenverarbeitung auf derselben Datenbasis ermöglicht. Die Konzepte von SanssouciDB bauen auf Prototypen, die am HPI (Hasso Plattner Institut) entwickelt wurden, und einem bestehenden SAP-Datenbank-System auf. SanssouciDB ist eine SQL-Datenbank und enthält die typischen Datenbankkomponenten , wie bespielsweise einen Query Builder, einen Plan Executer, Metadaten und einen Transaktions-Manager.

Datenspeicherung im Hauptspeicher

Im Gegensatz zu den meisten anderen Datenbanken werden Daten in SanssouciDB permanent im Hauptspeicher vorgehalten. Für die primäre Persistenz von Daten kommt zwar ausschließlich Hauptspeicher zum Einsatz, trotzdem sind noch Festplatten für nichtflüchtige Datenspeicherung notwendig. Alle Operationen, wie z.B. Find, Join oder Aggregation, können davon ausgehen, dass sich die Daten im Hauptspeicher befinden. Dadurch können Operationen, frei von jeglichen Problemen, die bei der Optimierung für den festplattenzugriff entstehen können Operationen, frei von jeglichen Problemen, die bei der Optimierung für den Festplattenzugriff entstehen könnten, programmiert werden. Wird der Hauptspeicher als primäre Persistenz genutzt, führt dies zu einer anderen Datenorganisation , die nur dann optimal funktioniert , wenn sie Daten immer im Speicher verfügbar sind.

Spaltenorientierung

Ein weiteres Konzept, das in SanssouciDB zum Einsatz kommt, wurde bereits vor mehr als zwei Jahrzehnten erfunden: die spaltenweise Datenspeicherung. Bei der Spaltenorientierung werden komplette Spalten in aufeinanderfolgenden Blöcken gespeichert. Dies unterscheidet sie von der zeilenorientierten Speicherung, bei der komplette Tupel (Zeilen) in aufeinanderfolgenden Blöcken gespeichert werden. Spaltenorientierte Speicherung ist im Gegensatz zu zeilenorientierter Speicherung, gut geeignet , um aufeinanderfolgende Einträge aus einer einzigen Spalten zu lesen. Dies kann für Aggregationen und Spalten-Scans von großem Nutzen sein. Um die Menge der Daten, die zwischen Speicher und Prozessor übertragen werden müssen, zu minimieren, verwendet SanssouciDB verschiedene Techniken zur Datenkompression die im Verlauf beschrieben werden.

Auswirkung der Spaltenorientierung

Die spaltenorientierte Speicherung ist bei Datenbanksystemen, die speziell für OLAP-Abfragen optimiert wurden, inzwischen weit verbreitet, da der Vorteil der spaltenorientierten Speicherung im Fall von quasi-sequentiellen Lesen bzw. Scannen einzelner Attribute oder der Verarbeitung einer Menge von aggregierten Attributen offensichtlich ist. Wenn nicht alle Felder in einer Tabelle abgefragt werden, kann auch bei transaktionaler Verarbeitung Spaltenorientierung ohne größere Nachteile genutzt werden. Eine Analyse von UNternehmensanwendungen zeigte dass es gegenwärtig keine Anwendung gibt, die alle Felder eines gegebenen Tupel verwendet. Zum Beispiel sind für eine Mahnung nur 17 von 300 Attributen aus einer Tabelle notwendig . Wenn nur die 17-benötigten Attribute anstelle der vollständigen Darstellung des Tupels mit seinen 300 Attributen abgefragt werden, ergibt sich durch das geringere Datenvolumen umgehend ein Performancevorteil um den Faktor 8 bis 20. Seitdem bei Hauptspeicherdatenbanken nicht mehr Festplatten der Engpass sind, der Zugriff auf den Hauptspeicher aber berücksichtigt werden muss, ist es besonders wichtig , mit einer minimalen Menge an Daten zu arbeiten. Bisher hatten Anwendungsprogrammierer eine große Vorliebe für „Select*“ - Statement. Bei zeilenorientierter Speicherung ist der Laufzeitunterschied zwischen der Anwendungsseite bereits vorhanden (was jedoch auch nur ein schwaches Argument ihr die Verwendung von SELECT* und das Abrufen unnötiger Daten ist). Bei Nutzung von Spaltenorientierung wirken sich jedoch die negativen Einflüsse bei der Verwendung von „Select*“-Statement bei hoher Tabellenbreite bedeutend stärker aus.

Aktive und passive Daten

In SanssouciDB werden Daten in aktive (Daten von Geschäftsprozessen, die noch nicht abgeschlossen sind) und passive Daten (Daten von Geschäftsprozessen, die vollständig abgeschlossen sind und nicht mehr geändert werden) aufgeteilt . Aktive Daten werden im Hauptspeicher abgelegt. Passive Daten können auf langsamerer Speichermedien wie z.B. Flash verschoben werden, da auf sie weniger häufig zugegriffen wird. Die Trennung der passiven von den aktiven Daten verringert die Menge an Hauptspeicher , die benötigt wird , um den gesamten Datensatz eines Unternehmens zu speichern.

Immer wenn neue Daten in die Datenbank geschrieben oder bestehende Daten geändert werden, ist eine Protokolierung im nichtflüchtigen Speicher notwendig. Während des Merge-Prozesses vom Differential Buffer in den Main Store werden Schnappschüsse gemacht und diese ebenfalls im nichtflüchtigen Speicher abgelegt. Logs und Schnappschüsse sind notwendig , um die Datenbank im Fehlerfall wiederherzustellen.

Der große Vorteil liegt darin, dass der Zugriff auf den Hauptspeicher von zeitdeterminitischen Prozessen abhängig sind. Durch diese Prozesse können Laufzeiten der In-Memory-Verarbeitung

berechnet werden (was allerdings schwierig sein kann) . Beobachtungen bei der Nutzung von In-Memory-Datenbanken zeigen, dass die Antwortzeiten gleichmäßig sind und nicht stark schwanken, wie es bei Festplatten aufgrund ihrer variierenden Suchvorgänge der Fall ist.

Überblick über die Architektur

Die in der Abbildung dargestellte Architektur gibt einen Überblick über die Komponenten von SanssouciDB.

SanssouciDB ist in drei verschiedene logische Schichten aufgeteilt , die spezifische Aufgaben innerhalb des Datenbanksystems erfüllen.

Die "Distributionsschicht" übernimmt die Kommunikation mit den Anwendungen , erstellt Pläne zur Abfrageausführung (sog. Query Execution Plans), speichert Metadaten und enthält die Logik für die Datenbank-Transaktionen.

Die Daten im Main Store werden, abhängig vom Workload entweder in einem Zeilenorientierten , spaltenorientierten oder hybriden Daten-Layout gespeichert. Der nichtflüchtige Speicher wird sowohl für die Protokollierung und Wiederherstellung als auch für Datenaltering und Time Travel verwendet.

Wörterbuch-Codierung

Weil Speicher bzw. die Speicherbandbreite der neue Flaschenhals ist, muss der Zugriff auf Speicher und die Übertragung von Daten minimiert werden. Einerseits kann man dies durch Zugriff auf eine geringere Anzahl von Spalten erreichen, sodass nur die benötigten Attribute abgefragt werden. Andererseits kann man durch Verringerung der Anzahl von Bits, die für die Repräsentation der Daten verwendet werden, sowohl den Speicherverbrauch als auch die Übertragungszeiten reduzieren.

Wörterbuch-Codierung (engl. dictionary encoding) bildet die Grundlage für mehrere andere Kompressionstechniken, die auf Basis der wörterbuch-codierten Spalten angewendet werden können. Der wesentliche Effekt der Wörterbuch-Codierung liegt darin, dass lange Werte , wie z.B. Texte , durch kurze , ganzzahlige Werte dargestellt werden.

Wörterbuch-Codierung ist eine relativ einfache Komprimierungstechnik. Dies bedeutet nicht nur , dass sie leicht zu verstehen ist, sondern auch einfach zu implementieren ist. Sie benötigt keine komplexen mehrstufige Verfahren , die den Zugewinn am Leistung begrenzen oder vermindern würden. Zunächst erklären wir den allgemeinen Algorithmus , wie die Originalwerte in ganze Zahlen übersetzt werden.

Wörterbuch-Codierung arbeitet auf den einzelnen Spalten der Tabellen. Im Beispiel wird jeder einmalige Wert in der Vorname-Spalte "fname" durch einen einmaligen Integer-Wert ersetzt. Die Position eines Text-Wertes (z.B, Mary) im Wörterbuch stellt die den Text repräsentierende Zahl (hier "24" für Mary) dar. Bis jetzt haben wir noch keinen Speicherplatz eingespart. Doch sobald Werte mehr als einmal in einer Spalte auftreten ergeben sich Vorteile . In unserem kleinen Beipiel kann man den Wert "john" zweimal in der 'Spalte "fname" finden, nämlich auf den Positionen 39 und 42. Durch Wörterbuch-Codierung wird der lange Text-Wert (wir nehmen 49 Byte pro Eintrag in der Vornamen-Spalte an) durch den kurzen Integer-Wert repräsentiert (23-Bit sind notwendig, um alle von uns angenommenen 5 Millionen verschiedenen Vornamen weltweit zu codieren). Je öfter identische Werte erscheinen, desto größer ist der Nutzen .

Daher ist Wörterbuch-Codierung daher gut geeignet und erreicht ein gute Kompressionsrate .

Kompression

SanssouciDB stellt eine Datenbank-Architektur dar, die entworfen wurde, um transaktionale und analytische Workloads innerhalb der Unternehmensdatenverarbeitung zu bearbeiten. In großen Unternehmen kann die Datenmenge leicht eine Größe von mehreren Terrabyte erreichen. Obwohl die Speicherkapazitäten von Standard-Servern weiter wachsen, ist es immer noch teuer , diese riesigen Datenmengen vollständig im Hauptspeicher zu halten. Daher verwenden SanssouciDB und die meisten modernen In-Memory-Engines zusätzliche Kompressionsverfahren auf der Basis von Wörterbuch-Codierung, um den Speicherbedarf zu verringern. Die spaltenorientierte Speicherung von Daten ist für Kompressionsverfahren sehr gut geeignet , weil Daten gleichen Typs und gleicher Domäne fortlaufend abgespeichert werden.

Ein weiterer Vorteil der Kompression ist die Reduktion der Datenmenge , die zwischen Hauptspeicher und CPUs transportiert werden muss, was zu einer verbesserten Abfrageleistung führt.

Präfix-Encoding

In realen Datenbanken findet man oft den Fall vor, dass eine Spalte einen vorherrschenden Wert enthält und die restlichen Werte sehr oft in einem unkomprimiertes Format speichern. Präfix-Encoding ist ein einfeicher Weg, um dies effizienter zu bewältigen. Um Präfix-Encoding anzuwenden , müssen die Datensätze noch der Spalte mit dem vorherrschenden Wert sortiert werden , und der Attribut-Vektor muss mit dem vorherrschenden Wert beginnen.

Um die Spalte zu komprimieren , sollte der vorherschende Wert nicht jedes Mal , wenn er auftritt , explizit gespeichert werden müssen. Dies wird erreicht , indem man im Attribut-Vektor sowohl den vorherrschenden Wert selbst abspeichern als auch die Anzahl, wie häufig er auftritt. So enthält ein Präfix-codierter Attribut-Vektor die folgenden Informationen:

=> Anzahl des Auftretens des vorherrschenden Wertes

=> WertID des vorherrschenden Wertes aus dem Wörterbuch

=> WertID der übrigen Werte

Run-Length-Encoding

Lauflängenkomprimierung (engl. Run-Length-Encoding) ist ein Kompressionsverfahren, das am besten funktioniert , wenn der Attribut-Vektor aus wenigen einmaligen Werten besteht, die sehr oft vorkommen. Für maximale Kompressionsraten muss die Spalte sortiert sein, sodass alle gleichen Werte hintereinander stehen. Für Run-Length-Encoding gilt: Wert-Sequenzen mit dem gleichen Wert werden durch eine einzige Instanz des Wertes ersetzt und

A) entweder die Anzahl ihres Vorkommens oder

B) ihrer Startposition als Offset gespeichert.

Cluster-Encoding

Cluster.Encoding, arbeitet mit gleich großen Blöcken einer Spalte. Der Attribut-Vektor wird in A/Blöcke fester Größe (in der Regel 1024 Elemente) aufgeteilt . Wenn ein Cluster nur einen einzigen Wert enthält , wird er durch ein einziges Auftreten dieses Wertes ersetzt. Andernfalls bleibt der Cluster unkomprimiert. Ein zusätzlicher Bit-Vektor der Länge N zeigt an, welche Blöcke durch einen einzigen Wert ersetzt wurden.

Indirect-Encoding

Wie Cluster-Encoding , arbeitet auch Indirect-Encoding mit Datenblöcken mit N Elementen (typischerweise 1024). Wenn Datenblöcke nur ein paar einmalige Werte enthalten, kann Indirect-Encoding effizient angewandt werden. Dies ist oft der Fall , wenn eine Tabelle nach einer anderen Spalte sortiert ist und dabei eine Korrelation zwischen diesen beiden Spalten existiert (z.B. Namen-Spalten, wen die Tabelle nach Ländern sortiert ist).

Neben einem globalen Wörterbuch , das bei der Wörterbuch-Codierung generell verwendet wird, werden zusätzliche lokale Wörterbücher für Blöcke eingeführt, die nur ein paar einmalige Werte enthalten. Ein lokales Wörterbuch für einen Block enthält alle (und nur diese) einmaligen Werte, die in diesem Block auftauchen . Somit kann durch die Zuordnung zu noch kleineren WertIDs Platz gespart werden. Direkter Zugriff ist immer noch möglich, jedoch wird wegen des lokalen Wörterbuches ein Zwischenschritt eingeführt.

Delta-Encoding

Die bisher vorgestellten Kompressionsverfahren verringern die Größe des Attribut-Vektors. Es existieren aber ebenfalls einige Kompressionsverfahren, die auch die Datenmenge in einem Wörterbuch selbst reduzieren.

Angenommen, dass die Daten in einem Wörterbuch alphanumerisch sortiert sind und eine große Anzahl von Werten mit den gleichen Präfixen vorhanden ist. Delta-Encoding nutzt dies und speichert gemeinsame Präfixe nur einmal.

Delta Encoding verwendet , wie id ein den vorangegangenen Abschnitten beschriebenen Methoden , eine blockweise Kompression mit typischerweise 16 Zeichenketten pro Block. Zu Beginn eines jeden Blocks werden die Länge der ersten Zeichenkette und die Zeichenkette selbst gespeichert. Für jeden folgenden Wert werden die Anzahl der Zeichen , die diesem Präfix hinzugefügt wurden, und die hinzugefügten Zeichen gespeichert. Somit kann jede folgende Zeichenkette aus den Zeichen. Die sie sich mit der vorherigen Zeichenkette teilt, und deren restlichem Teil aufgebaut werden.

Einschränkungen

Nicht vergessen werden sollte die Tatsache , dass die meisten Kompressionsverfahren sortierte Tabellen erfordern, um ihr volles Potenzial zu entfalten. Eine Datenbank-Tabelle kann jedoch grundlegend immer nur nach einer Spalte sortiert werden, bei Attributen die in Relation stehen ist allenfalls eine zusätzliche kaskadierende Sortierung möglich. Darüber hinaus erlauben einige der vorgestellten Kompressionsverfahren keinen direkten Zugriff . Vor allem im Hinblick auf die Anforderungen an die Antwortzeiten der Abfragen muss dies sorgfältig abgewägt werden.

Datenlayout im Hauptspeicher

In diesem Abschnitt beschäftigen wir uns mit der Frage , wie Daten im Arbeitsspeicher organisiert sind. Relationale Datenbanktabellen haben eine zweidimensionale Struktur , der Hauptspeicher dagegen ist eindimensional organisiert . Er stellt Speicherplatz-Adressen zur Verfügung , die bei Null beginnen und fortlaufend bis zur höchsten verfügbaren Speicherplatz-Adresse hin ansteigen. Die Datenbank- Speicherverwaltung muss entscheiden , wie die zweidimensionalen Tabellenstrukturen im linearen Speicheradressraum angeordnet werden. Wir werden zwei Möglichkeiten betrachten, wie eine Tabelle im Speicher dargestellt werden kann. Diese beiden Möglichkeiten werden als sogenanntes Zeilen bzw. Spalten-Layout bezeichnet , wobei es auch eine Kombination beider Möglichkeiten, das sogenannte Hybrid-Layout gibt.

Vorteile eines Spalten-Layouts

Es gibt Fälle, in denen ein Zeilenabständen Tabellen Layout effizienter ist. Dennoch sprechen viele Vorteile für die Nutzung eines Spalten-Layouts in einem Enterprise-Kontext.

Erstens stellt sich bei einer Analyse der Workloads , mit denen Unternehmens-Datenbanken konfrontiert sind, heraus, dass die tatsächlichen Workloads stärker leseorientiert sind und von komplexen Mengenoperationen dominiert werden.

Zweitens ist trotz der sich schnell weiterentwickelnden Hardware und der ständig steigenden Menge an verfügbaren Hauptspeicher der Einsatz effizienter Kompressionsverfahren immer noch wichtig, um (a) so viele Daten wie möglich im Hauptspeicher zu halten , und (b) die Datenmenge zu minimieren, die für Abfragen aus dem Hauptspeicher gelesen werden muss.

Spaltenbasierte Tabellen-Layouts ermöglichen den Einsatz effizienter Kompressionsverfahren, indem sie die hohe Datenlokalität von Spalten ausnutzen . Dabei nutzen sie hauptsächlich die Ähnlichkeit der in einer Spalte gespeicherten Daten. Wörterbuch-Codierung kann sowohl auf Zeilen- als auch auf spaltenbasierten Tabellen-Layouts angewandt werden, wohingegen andere Techniken , wie Prefix-Encoding , Run-Length-Encoding, Cluster-Codierung oder indirekte Codierung , ihre Vorteile nur auf spaltenbasierten Tabellen-Layouts voll ausspielen können.

Drittens ermöglicht die Verwendung von spaltenbasierten Tabellen-Layouts sehr schnelle Spalten-Scans, da der Speicher in diesem Fall sequentiell ohne logische Sprünge gescannt werden kann. Dadurch lassen sich z.B. Berechnungen von Aggregaten „on-the-fly“, also auf Anfrage , realisieren . Auf das Speichern vorberechneter Aggregate in der Datenbank kann folglich verzichtet werden, wodurch die redundante Speicherung von Daten und die Komplexität der Datenbank minimiert werden.

Hybride Tabellen-Layouts

Wie zuvor erwähnt , dominieren bei Enterprise Workloads Operationen auf Mengen von gleichen Attributen. Dennoch ist jeder konkrete Workload unterschiedlich und kann teils auf einem zeilenbasierten , teils auf einem spaltenbasierten Layout eine bessere Performance aufweisen. Hybride Tabellen-Layouts kombinieren die Vorteile aus beiden Welten, indem sie das Speichern einzelner Attribute einer Tabelle spaltenorientiert zulassen, während andere Attribute in einem zeilenbasierten Layout angeordnet werden. Die im Einzelfall optimale Kombination hängt stark vom tatsächlichen Workload ab und kann durch Layout-Algorithmen berechnet und zur Laufzeit angepasst werden.

Partitionierung

Definition und Klassifikation

Als Partitionieren bezeichnet man das Unterteilen einer logischen Datenbank in einzelne voneinander unabhängige Teilmengen der Daten. Partitionen sind selbst Datenbank-Objekte und können unabhängig voneinander verwaltet werden. Hauptmotivation, Daten zu partitionieren , liegt darin , Parallelität auf Datenebene zu erreichen, was zusätzliche Leistungssteigerungen ermöglicht . Ein klassisches Beispiel für die Ausnutzung von Datenparallelität ist es, mehrere unterschiedliche Datenbereiche unter Verwendung einer Multi-Core-CPU parallel zu verarbeiten , wobei jeder Kern auf einer separaten Partition arbeitet . Da Partitionierung eine technische Optimierung darstellt , um die Abfragegeschwindigkeit zu erhöhen, sollte sie für den Benutzer transparent sein. Um die Transparenz der angewandten Partitionierung für den Endanwender zu gewährleisten , wird eine Ansicht benötigt , welche die komplette Tabelle als Übersicht aller Abfrage-Ergebnisse von allen beteiligten Partitionen zeigt. Mit Hilfe von Parallelität auf Datenebene ist es möglich , die Leistung , Verfügbarkeit oder Verwaltbarkeit von Datensätzen zu verbessern. Welches dieser sich teilweise widersprechen Ziele favorisiert wird, hängt in der Regel vom Anwendungsfall ab.

Vertikale Partitionierung

Vertikale Parittionierung führt zu einer Aufspaltung der Daten in Attribut-Gruppen mit replizierten Primärschlüsseln. Diese Gruppen werden dann auf zwei (oder mehr) Tabellen verteilt. Attribute , auf die ind er Regel gemeinsam zugegriffen wird, sollten sich in derselben Tabelle befinden , um die Leistung von Joins zu steigern.

Derartige Optimierungen können nur angewendet werden, wenn tatsächliche Nutzungsinformationen vorliegen. Dies ist ein weiterer Grund , weshalb Anwendungsentwicklung immer auf realen Kundendaten und Workloads basieren sollte.

Bei zeilenbasierten Datenbanken ist vertikale Partitionierung prinzipiell zwar möglich, wird jedoch nur selten eingesetzt . Performencevorteile durch vertikale Partitionierung sind bei einem zeilenbasierten Layout schwierig zu realisieren, da eine vertikale Aufteilung und Trennung der Attribute dem grundlegenden Konzept von Werte- Tupeln wiederspricht . Spaltenbasierte Datenbanken hingegen unterstützen implizit vertikale Partitionierung, die jede Spalte als mögliche Partition angesehen werden kann.

Horizontale Partitionierung

Horizontale Partitionierung wird häufig in klassischen zeilenorientierten Datenbanken angewandt. Bei dieser Partitionierung, wird die Tabelle nach bestimmten Bedingungen in disjunction Tupel-Gruppen aufgeteilt. Es existieren mehrere Strategien zur horizontalen Partitionierung:

Die erste Partitionierungsstrategie , die wir hier vorstellen, ist die Range-Partitionierung, welche Tabellen mit Hilfe eines vordefinierten PartitionierungsSchlüssels in Partitionierungsschlüssels in Partitionen aufteilt. Der Schlüssel bestimmt , wie die einzelnen Datensätze auf die verschiedenen Partitionen verteilt werden. Dabei kann’s er Partitionierungsschlüssel aus einer einzigen Schlüsselspalte oder mehreren Schlüsselspalten bestehen.

Die zweite horizontale Partitionierungsstrategie stellt die Round-Robin-Partitionierung dar. Beim Round-Robin-Verfahren verwendet ein Partitionierungsserver keine Tupel-Informationen als Kriterien für die Partitionierung. Daher existiert auch kein expliziter Partionierungsschlüssel. Der Algorithmus ordnet die Tupel streng der Reihe nach jeweils einer Partition zu, bis er bei der letzten Partition angekommen ist, woraufhin wieder bei der ersten Partition begonnen wird. Dies führt automatisch zu einer gleichmäßigen Verteilung der Einträge und begünstigt so bis zu einem gewissen Grad implizit auch eine gleichmäßige Lastverteilung (Load-Balancing).

Da es jedoch möglich ist, dass auf bestimmte Einträge häufiger als auf andere zugegriffen wird, kann ein gleichmäßiger Workload jedoch nicht garantiert werden. Verbesserungen durch intelligente Daten-Kollokation oder entsprechende Datenplazierung können beim Round-Robin nicht wirksam ausgenutzt werden, weil die Verteilung der Daten nicht von den Daten selbst , sondern nur von der Reihenfolge abhängig ist, in der sie eingefügt werden.

Den dritten horizontalen Partitionierungstyp stellt die Hash-basierte Partitionierung dar. Hash-basierte Partitionierung verwendet eine Hash-Funktion, um die Zuteilung der Tupel auf die einzelnen Partitionen festzulegen. Die größte Herausforderung für die Hash-basierte Partitionierung besteht ind er Wahl einer guten Hash-Funktion, die automatisch zu einer guten Aufteilung der Daten hinsichtlich der zu erwarteten Abfragen führt und so für Zugriffsverbesserungen sorgt.

Die letzte hier vorgestellte Partitionierungsstrategie stellt die semantische Partitionierung dar. Sie nutzt Wissen über die Anwendung , um die Daten aufzuteilen .

Wahl einer geeigneten Partitionierungsstrategie

Bei der Auswahl einer geeigneten Partionierungsstrategie gibt es eine Reihe von Optimierungszielen zu beachten. Will man beispielsweise auf Leistung optimieren , ist es sinnvoll, Tupel verschiedener Tabellen, die wahrscheinlich für die weitere Bearbeitung durch Joins verbunden werden, auf einen Server legen. Auf diese Weise kann der Join durch optimale Datenlokalität schneller durchgeführt werden, da keine Verzögerung durch die Übertragung der Daten über das Netzwerk auftritt. Im GegeSatz dazu sollten für statistische Abfragen , wie zum Beispiel Summenbildungen , die Tupel aus einer Tabelle auf so viele Knoten wie möglich verteilt werden, um von er parallele Datenverarbeitung profitieren zu können.

Zusammenfassend lässt sich sagen: Es hängt stark vom jeweiligen Anwendungsfall ab, welche Partionierungsstrategie am besten geeignet ist.

Parallele Datenverarbeitung

Betrachten wir, wie Parallelität bei In-Memory - und traditionellen Datenbankmanagementsystemen erreicht werden kann. Dabei stellen Pipeline-Parallelität und Datenparallelität zwei Ansätze zur Beschleunigung der Abfrageverarbeitung dar.

Bei Pipeline-Parallelität beginnt der nächste Operator bereits, bevor der aktuelle Operator fertig ist. Der aktuelle Operator hat zum Startzeitpunkt des nächsten Operators allerdings bereits Teilergebnisse berechnet. Somit überlappen sich die Ausführungszeichen der Operatoren teilweise . Betrachten wir zum Beispiel einen SCAN- und einen SORT-Operator bei der Auswertung eines Ausdrucks. Wenn für den Scan erste Ergebnisse vorliegen , werden sie vom nächsten Operator bereits sortiert. Diese Hintereinanderschaltung von Operatoren wird als Pipeline bezeichnet und ist prinzipiel beliebig weit möglich.

Durch Datenparallelität wird der Datensatz partitioniert, sodass die Operatoren einer Abfrage an unterschiedlichen Teilen des Datensatzes parallel arbeiten. Anschließend werden die Ergebnisse der parallelen Operatonen in eine gemeinsame Ergebnismenge überführt. Der Abfrageplan wird komplexer, da alle Operatoren in jeder Datenpartition individuell ausgeführt werden müssen und eine zusätzliche Merge-Operation notwendig wird.

In Datenbankmanagementsystemen können noch weitere Aspekte der Parallelisierung berücksichtigt werden. So unterscheiden wir zwischen Intra- und Inter-Query-Parallelität.

Intra-Query-Parallelität bezeichnet die Parallelisierung von Operatoren innerhalb einer Abfrage.

Dies bedeutet: Von außen betrachtet sieht die Abfrage wie eine einzige Operation aus. Intern wird sie hingegen parallelisiert , z.B. durch das Starten mehrerer Threads und die Verwendung von Datenparallelität. Inter-Query-Parallelität zielt darauf ab, Pläne für unterschiedliche Abfragen auf identische Teilstücke zu untersuchen, um diese dann für mehrere Abfragen gemeinsam auszuführen. Dies führt allgemein zu einer effizienteren Nutzung der Caches und minimiert den notwendigen Datentransfer.

Hardware-Schicht

Parallele Datenverarbeitung ist ein wesentlicher Aspekt dafür , dass In-Memory-DatenbankSysteme eine hohe Leistung erzielen. Doch welche Gründe sprechen für den Einsatz von Parallelisierung anstelle der Verwendung eines einzigen CPU-Kerns, der mit einer enorm hohen Frequenz , wie z.B. 1 PHz, läuft?

Multi-Core-CPUs

Im Idealfall würde ein moderner Computer aus einem einzigen CPU-Kern, der mit 1 PHz läuft, und aus einem riesigen persistenten integrierten Hauptspeicher bestehen. Die Realität sieht jedoch anders aus. Heutzutage gibt es in der Regel mehrere CPU-Kerne auf einer Platine. Darüber hinaus bestehen moderne Server-Systeme aus mehreren CPUs, wodurch sich die Anzahl der Kerne vervielfacht.

Die Gründe für die Entwicklung von Multi-Core-Systemen beruhen auf den Hardware-Entwicklungen des letzten Jahrzehnts. Die als Moores Gesetz bekannte Annahme von 1975, dass sich die Anzahl der Transistoren alle 18 Monate verdoppelt , ist immer noch gültig das sich die Anzahl der Transistoren alle 18 Monate verdoppelt , ist immer noch gültig . Jedoch kann man die Taktrate der Transistoren nicht unendlich erhöhen. Zum Beispiel steigt das Verhältnis des Wärmeverlustes zur Leistung mit zunehmender Taktrate an.

Das hat zur Folge, dass isch die Energieeffizienz verschlechtert, weil immer mehr zusätzliche Energie zur Kühlung der Transistoren benötigt wird. Hardware-Hersteller haben gezeigt, dass die Verwendung mehrerer CPU-Kerne , die bei einer niedrigeren Frequenz arbeiten, z.B. 2,4-2,7 GHz, die Effizienz erhöht, wobei der Bedarf an Kühlung auf einem angemessenen Niveau gehalten werden kann.

Logging

Datenbanken müssen bestimmte Eigenschaften bei der Verarbeitung von Daten garantieren, damit sie in produktiven UNternehmensanwendungen verwendet werden können. Um diese Eigenschaften garantieren zu können, müssen Fehlertoleranz und hohe Verfügbarkeit gewährleistet werden. Da jedoch Hardware-Ausfälle oder Stromausfälle nicht vermieden oder vorhergesehen werden können, müssen Maßnahmen getroffen werden, die es dem System ermöglichen nach einem Ausfall alle Daten wiederherzustellen.

Logging ist das Standardverfahren, mit dem eine verlässliche Wiederherstellung möglich ist. Mithilfe von Logging und Wiederherstellungsprotokollen können Datenbanken auf den letzten konsistenten Zustand vor dem Ausfall zurückgesetzt werden. Dies wird durch Checkpointing des aktuellen Systems und Logging nachfolgender Datenänderungen erreicht. Daten werden in Log-Dateien geschrieben, die auf persistenten Speicher , wie Festplatten (HDD) oder Solid-State-Laufwerken (SSD), gespeichert sind.

Logging-Infrastruktur

Ein entscheidendes Kriterium , wenn es um Logging geht, ist die Leistung , sowohl für das Schreiben der Logs als auch für das Lesen von Logs bei der Wiederherstellung. Wie bereits beschrieben wird der Leistungsunterschied zwischen -Festplatte und CPU ständig größer. Folglich muss Logging in erster Linie im Hinblick auf die Minimierung der I/O-Operationen optimiert werden.

Die Log-Daten, die auf die Festplatte geschrieben werden, bestehen aus drei Teile:

• Snapshot des Msin Stores

• Wert-Logs

• Wörterbuch-Logs

Checkpointing wird verwendet , um einen Snapshot der Datenbank zu einem bestimmten Zeitpunkt , zu dem die Daten in einem Zustand vorliegen, zu erstellen.

Eine Datenbank ist in einen konsistenten Zustand , „wenn und nur wenn sie die Ergebnisse aller abgeschlossenen Transaktionen enthält“. Der Snapshot ist eine direkte Kopie des leseoptimierten Main Stores und wird in regelmäßigen Abständen auf die Festplatte geschrieben. Der Zweck des Checkpointing ist die Beschleunigung des Wiederherstellungsprozesses, da nur Log-Einträge nach dem Snapshot in die Datenbank geladen werden kann. Um die Daten des Diffential Buffers , der nicht Teil des Snapshot ist, zu protokollieren , werden Wert-Logs sowie Wörterbuch-Logs verwendet, um durchgeführte Änderungen zu verfolgen.

Die Logging-Infrastruktur von SanssouciDB unterscheidet sich von den meisten traditionellen Datenbanken. SanssouciDB hat eine angepasste Infrastruktur , um spaltenoptimierte Datenstrukturen zu nutzen und I/O-Engpässe zu reduzieren. Zu diesen Optimierungen gehören:

• Snapshot-Format: An jedem Checkpoint wird ein Snapshot des Main Stores direkt im binärer Form auf die Festplatte geschrieben. Dies bedeutet , dass eine exakte Kopie des Main Stores aus dem Arbeitspeicher auf die Festplatte geschrieben wird. Diese Kopie kann im Fall einer Wiederherstellung später ohne zusätzlichen Transformationsaufwand direkt wiederhergestellt werden.

• Zeitpunkt eines Checkpoints: Der ideale Zeitpunkt für das Erstellen eines Checkpoints ist gegeben, wenn der Differential Buffer im Vergleich zum Main Store relativ klein ist. Das ist direkt nach dem Merge-Prozess der Fall.

• Speichern von Metadaten: Um den Wiederherstellungsprozess zu beschleunigen , werden zusätzliche Metadaten auf die Festplatte geschrieben. Anhand dieser Metadaten kann der benötigte Arbeitsspeicher bereits vor dem Laden allokiert werden. Dadurch können teure Reallokationen und Bewegungen der Daten sind z.B. die Anzahl der Tupel im Mian Store und die Anzahl der in jedem Wörterbuch verwendeten Bits.

• Trennung in Wert- und Wörterbuch-Logs: Die beiden großen Leistungs-Optimierung für Logging in SanssouciDB sind die Reduzierung der Log-Größe und die Parallelisierung des Logging. Dies wird durch die Verwendung von Wörterbuch-codiertem Logging erreicht, wie im folgenden Abschnitt ausführlich erklärt wird.

Wiederherstellung

Um die stetig wachsenden Datenmengen und Workloads bewältigen zu können , müssen moderne Unternehmenssysteme in der Lage sein , über mehrere Server innerhalb einer Unternehmenssystemlandschaft zu skalieren (eng. Scale out). Mit der wachsenden Anzahl von Servern und somit wachsenden Zahl von Hardwarekomponenten steigt die Wahrscheinlichkeit von Störungen.

Von produktiven Unternehmenssystemen wird erwartet , dass sie dauerhaft fehlerfrei arbeiten oder im Falle eines Defektes eine Ausfallsicherung gewährleistet ist. Wenn ein Server ausfällt, muss er ggf neu gestartet und wiederhergestellt werden, oder ein anderer Server muss den Workload des ausgefallenen Servers übernehmen. so oder so müssen Daten aus vorherige fehlerfreie Zustand des Servers vor dem Ausfall wiederhergestellt werden kann.

Dieser Vorgang wird als Wiederherstellung (engl. Recovery) bezeichnet. Durch die Verwerndung von Snapshots und Log-Daten, Datenbanken können wieder auf den letzten konsistenten Zustand zurückgesetzt werden.

Der Wiederherstellungsprozess stützt sich auf Wörterbuch-codiertes Logging. Der Prozess wird in zwei aufeinander folgenden Schritten ausgeführt: 1. Lesen der Metadaten und Vorbereiten der Datenstrukturen, 2. Lesen der Logging-Daten und Wiederherstellen der Datenbank.

Lesen der Metadaten

Neben dem Logging der abgeschlossenen Transaktionen protokolliert SanssouciDB auch Metadaten zur Beschleunigung des Wiederherstellungsprozesses. Mit dem zusätzlichen Wissen über die Datenstrukturen , die wiederhergestellt werden müssen, können teure Bewegungen der Daten und die Reallokation von Speicher vermieden werden. Beispiele für gespeicherte Metadaten sind z.B. die Position der letzten Snapshots, die Anzahl der Zeilen im Main Store oder die für die Wörterbuch-Codierung von Spalten benötigten Bits.

Nehmen wir als Beispiel einmal das Wiedereinspielen (engl. Replay) der Wörterbuch-Logs. Ohne im Voraus zu wissen, wie viele Elemente vor dem Systemausfall im Wörterbuch vorhanden waren, müsste der für das Wörterbuch zu allokierende Speicherbereich wahrscheinlich mehrmals vergrößert werden. Eine Vergrößerung des Soeicherbereichs erfordert in der Regel , dass die Daten komplett in den neu allokierten Bereich verschoben werden müssen. Wenn die Anzahl der Elemente und die Anzahl der erforderlichen Bits im Voraus bekannt ist, kann der zu allokierende Bereich entsprechend bemessen werden, ohne dass Reallokationen oder Bewegungen der Daten notwendig werden. Die Anzahl der Wörterbuch-Elemente wird gespeichert , da es nicht effizient ist, das Wörterbuch-Log nach dem letzten Eintrag zu durchsuchen, um die Größe des Wörterbuchs zu ermitteln. Auch wenn in umgekehrter Reihenfolge gescannt wird, um den letzten Wörterbucheintrag zu lesen, ist dieses Vorgehen nicht effizient , da Transaktionen nicht zwingend in der Rehinfolge in der sie eingegangen sind, protokolliert werden. Demzufolge kann die Suche nach der maximalen Wörterbuch-Position im Wörterbuch-Log zur Folge haben, dass große Teile der Wörterbuch-Log-Datei gelesen werden müssen.

Wiederherstellen der Datenbank

Nachdem die Allokation der Datenstruktur stattgefunden hat, werden die Datenbank-Logs eingespielt. Als Teil dieses Prozesses wird der Snapshot des Main Stores einer Tabelle wieder in den Arbeitsspeicher geladen. Gleichzeitig werden die Wörterbuch-Log-Dateien mit den Wörterbuch-Log-Einträgen un die Wert-Log-Dateien mit dem Wert- und Transaktion Log-Einträgen eingespielt.

Aufgrund des Wörterbuch-codierten Loggins , können die Dateien parallel verarbeitet werden. Der Import der Wörterbuch-Logs und des Main Stores ist relativ unkompliziert, wohingegen das Lesen der Wert- und Transaktions-Log-Einträge aus der Wert-Log-Datei ein komplexer ist. Um das Wiedereinspielen nicht abgeschlossener Transaktionen zu vermeiden, wird die Wert-Log-Datei in umgekehrter Reihenfolge gelesen. auf dieser Weise wird sichergestellt, dass nur Wert-Log-Einträge eingespielt werden, deren Transaktionen erfolgerichtigstes abgeschlossen wurden. Denken Sie daran , dass Wert- und Transaktions-Log-Einträge erfolgreich geschrieben worden sind.

Nach dem Import der Wert-Log Datei wird ein zweiter Lauf mit den importierten Tupeln auf leere Attribute überprüft und bei Bedarf vervollständigt werden. Der zweite Lauf ist demzufolge eine Iteration über die vorigen Versionen des Tupels beginnend mit dem zweit-aktuellsten Eintrag, bis für alle Attribute des Tupels die gültigen Werte festgestellt wurden.

Zugehöriger Post:

https://einsiedlerkreps.blogspot.com/2023/05/in-memory-data-management-teil-i.html