Kapitel 18: Hauptspeicherdatenbanken Flashcards
Wie können Hauptspeicherdatenbanken eingesetzt werden?
OLAP, OLTP und hybride OLTP&OLAP DB
Speicherhirarchie und Zugriffszeit
- Register 1-10ns (Suche 1 min)
- Cache 10-100ns (Suche 10 min)
- Hauptspeicher 100-1000ns (Suche 1.5h)
- Plattenspeicher 10ms (Suche 2 Jahre)
- Archivspeicher sekunden (Suche 2000 Jahre)
Was ist Kompaktifizierung?
- Heiß: Working Set, umkomprimierte, kleine Seiten
- Abkühlen: Heiße, aufgewärmte, kalte Objekte
- Kalt: Noch umkomprimiert
- Gefroren: Komprimierte Objekte
was ist der ART?
Adaptiver radix-baum als Indexstruktur für Hauptspeicherdatenbanken.
Berechnen Sie, wie groß ein Data Warehouse für ein Handelsunternehmen wie Zalando oder Amazon.com wäre, wenn die Bestelldaten der letzten 3 Jahre enthalten sind. Versuchen sie ihre Schätzung basierend auf öffentlichen Daten wie Umsatz o.Ä. durchzufu ̈hren.
Berechne: Umsatz, wie viele Artikel Pro Kunde. Wie Teuer sind die Artikel? Wie viele Transaktionen, wie viel speicher hat ein Artikel –> sollte so bei
HyPer schafft 120.000 Transaktionen pro Sekunde. Pro Transaktion werden 120 Byte in die Log geschrieben. Berechnen Sie den beno ̈tigten Durchsatz zum Schreiben der Log.
Die Datenbank la ̈uft fu ̈r einen Monat und stu ̈rzt dann ab. Es wurde kein Snapshot er- stellt. Berechnen Sie die Recoveryzeit. Gehen Sie davon aus, dass die Recovery durch die Festplatte limitiert ist (100 Mbyte / s). Wieviel Log Eintra ̈ge werden pro Sekunde recovert?
Durchsatz = 120.000 \* 120 = 14400000 = 13,7 MBytes/s. LogEintr ̈age =120.000\*60\*60\*24\*30=311040000000 LogGro ̈ße = LogEintra ̈ge\*120 = 33 TB RecoveryZeit = 4,1 Tage
RecoveryDurchsatz = 873813 tx / s.
Wie ändert sich die Bedeutung des Redo-Log und Undo-Log in Hauptspeicherdatenbanken im Vergleich zu klassischen Datenbanken? Wo werden sie gespeichert?
Da die Daten nicht mehr auf der Festplatte gespeichert werden, mu ̈ssen sie (falls es keine Snapshots gibt) bei einem Neustart komplett auf Basis des Redo-Logs wiederhergestellt werden. Da nie die Daten einer nicht comitteten Transaktion auf der Platte landen wird die Undo-Log nur beno ̈tigt um im Fall eines Abort die A ̃”nderungen der Transaktion zuru ̈ck- zusetzen. Außerdem reicht es aus die Redo Log Daten erst beim Commit zu schreiben. Aus diesem Grund sind die Daten der Undo-Log nur zur Laufzeit der Transaktion notwendig und mu ̈ssen nicht auf die Festplatte geschrieben werden. Wa ̈hrend der Wiederherstellung der Datenbank ko ̈nnen dann einfach alle Redo Log Eintra ̈ge wiederhergestellt werden.
In traditionellen Datenbanksystemen sind die Festplatte und der Buffermanager oft der Hauptgrund fu ̈r Performanceengpa ̈sse. Wie a ̈ndert sich dies in Hauptspeicherdatenban- ken, wo sind die neuen Flaschenha ̈lse? Unterscheiden Sie auch zwischen Analytischen und Transaktionalen Workloads.
Der Unterschied zwischen traditionellen Datenbanksystemen und Hauptspeicherdatenban- ke ist, dass wir in der Speicherhierarchie ein paar Stufen nach oben gehen. Hauptspeicher ist teurer, aber gleichzeitig auch schneller und hat eine geringere Latenz. Genauso wich- tig ist aber auch, dass die Daten nun alle in einem Adressraum liegen. Bei der Nutzung von Festplatten muss das Datenbanksystem explizit die Daten von der Festplatte in den Speicher laden. Beim Hauptspeicher ist der Wechsel zwisch RAM, L3 und L1 Cache trans- parent fu ̈r das System. Das heißt ein Buffermanager wird nicht mehr beno ̈tigt. Auch wenn der Wechsel zwischen den verschiedenen Hauptspeicherhierarchien fu ̈r das System nicht explizit sichtbar ist, so ist es doch in der Performance bemerkbar. Der Latenzunterschied zwischen RAM und L3 ist a ̈hnlich groß wie zwischen Festplatten und RAM. Die Daten- bank muss nun so strukturiert werden, dass mo ̈glichst viele Operationen auf Daten in den schnelleren Speicherschichten ausgefu ̈hrt werden. Ein weiterer neuerer Flaschenhals sind die Lockingverfahren. Im Vergleich zu einfachen Operationen wie Lesen, Schreiben, Addi- tion, etc. ist ein Lock zu erstellen viel teurer. Viele Hauptspeichersystem versuchen daher Locks zu vermeiden. Ein Problem, dass hauptsa ̈chlich nur Transaktionale Workloads be- trifft ist, dass beim A ̈ndern von Daten die A ̈nderung immer noch persistiert werden muss (Logging). Es reicht nicht aus, die Daten nur im Hauptspeicher zu halten, da diese dann nach einem Systemabsturz verloren wa ̈ren. Das Schreiben auf Festplatte ist selbst mit SSDs noch wesentlich teurer als A ̈nderungen im Hauptspeicher vorzunehmen. Auch ein Problem in Transaktionale Workloads ist die Annahme der Anfragen. Transaktionale An- fragen sind typischerweiße sehr schnell. Ein einzelner Rechner kann sehr einfach mehrere Hunderttausend Anfragen verarbeiten. Hier ist die Netzwerklatenz auch wesentlich gro ̈ßer als die Verarbeitungszeit der Anfragen. Daher kann ein einzelner Client die Datenbank garnicht auslasten wenn er jede Anfrage einzeln abschickt.
Sie sollen fu ̈r ein Versandhaus die Datenbank fu ̈r ein Hauptspeicherdatenbanksystem op- timieren. In dem System sind die Daten der letzten drei Jahre gespeichert. Das Schema der verschiedenen Relation ist unten beschrieben.Wa ̈hlen sie jeweils eine Repra ̈sentation der Daten fu ̈r die Relationen (z.B. Spalten- oder Zeilenorientert), so dass zur Beantwor- tung der unten beschriebenen Anfragen mo ̈glichst wenig Daten in den CPU-Cache geladen werden mu ̈ssen. Es existieren Indexe auf VerkaufsId in Verkauf, (KundenId, VerkaufsId) in KundenKa ̈ufe und KundenId in Kunde. Es ko ̈nnen aber keine neuen Indexe definiert werden. Text wird direkt innerhalb der jeweiligen Spalte / Zeile gespeichert. ’
Relationen
Verkauf
VerkaufsId (8 byte), Datum (16 byte), Uhrzeit (16 byte), IP (16 byte), Betrag (16 byte), Versandart (8 byte), Kommentar (48 byte)
KundenKäufe
KundenId (8 byte), VerkaufsId (8 byte)
Kunde
KundenId (8 byte), Anrede(8 byte), Vorname(8 byte), Nachname(8 byte), Einstufung(8 Byte), Anschrift(256 byte), Land(64 byte), Email (16 Byte), Facebook(32 byte), GPlus(32 Byte), WerbungsFrequenz(8 byte)
Anfragen mit Ausführungshäufigkeit:
10000x select * from Verkauf
where Datum > ’%d’::date and Datum < ’%d’::date + interval ’1’ month;
100x select * from Verkauf;
100x select count(*) from KundenKa ̈ufe group by KundenId;
10000x select Anrede, Vorname, Nachname, Einstufung, Email, WerbungsFrequenz from Kunde where KundenId = ’%id’;
Wu ̈rden Sie ihre Entscheidung a ̈ndern, wenn zusa ̈tzlich noch die folgenden Anfragen aus- gefu ̈hrt werden mu ̈ssten?
- 5000x insert into Verkauf VALUES (…);
- 5000x insert into KundenKa ̈ufe VALUES (…); 3. 100x insert into Kunde VALUES (…);
Verkaufs Relation SIEHE LÖSUNG
Diese Relation betreffen drei Anfragen. Die Anfragen 1 und 2 und die Insert Anfrage 1. Eine Tupel beno ̈tigt 128 byte Speicherplatz, somit 2 Cachelines.
1. Anfrage:
- Keiner der existierenden Indexe hilft, um die where Bedingung auszuwerten. Daher müssen alle Einträge in der Tabelle überprüft werden (Tablescan). Die Selektivität des Prädikats kann mit 1 / AnzahlMOnateInDb 1/36 abeschätzt werden.
- Row store Zur Auswertung des Prädikats muss für jedes Tupel die Cacheline mit der Datumsinformation geladen werden. Für alle zutreffenden Tupel müssen zur Ausgabe auch die restlichen Felder und somit auch die zweite Cacheline geladen werden. Daraus ergibt sich folgende Formel (|V | = Gro ̈ße der Verkaufsrelation).
Kosten=|V| / 4 +|V| * 6 / 36 =|V|∗15/ 36
Indexstrukturen fu ̈r Hauptspeicherdatenbanken
Scha ̈tzen sie die Anzahl der Cache Misses die entstehen, wenn man 1000 32-bit Integer Werte (0-1000) in aufeinanderfolgender Reihenfolge in einen ART Baum einfu ̈gt. Wa ̈re ein B+ Baum besser oder schlechter?
Gro ̈ße der einzelnen ART Knoten (mit 64bit Pointern und ohne Header):
Node4 4+4∗8=36Byte
Node48 256+48∗8=640Byte
Node256 256 ∗ 8 = 2048 Byte
Die Höhe eines ART-Baums ist durch die Schlu ̈ssella ̈nge beschra ̈nkt (in unserem Fall maximal Ho ̈he 4), da in jedem Knoten ein Byte des Schlu ̈ssels gespeichert wird. Da die Integerzahlen aufeinanderfolgend sind, unterscheiden sie sich maximal in den letzten zwei Bytes (die werte zwischen 0 und 1000 haben immer 0x00 0x00 als prefix). Fu ̈r die ersten zwei Bytes reicht es einen Node4 zu nehmen, da hier alle Eintra ̈ge den selben Wert besitzen. Auf dem letzten Level reichen 4 Node256 um die letzten Bytes der 1000 Integer Werte einzufu ̈gen. Da es nur vier Kindnoten gibt reicht auf Level drei auch ein Node4. Die Gesamtgro ̈ße des Baums ist somit 4 ∗ 2048 + 3 ∗ 36 = 8300 Byte. Dies passt locker in den L1 Cache heutiger CPUs der typischerweiße 64 KB groß ist. Somit gibt es keine Cache Misses.
Ein B+ Baum ist schlechter, da bei sequentiellen Einfu ̈gen die Knoten nur halb gefu ̈llt sind. Außerdem werden in den Knoten jeweils pro Pointer auch noch ein ein kompletter 32 bit Rangeschlu ̈ssel gespeichert was den Speicherbedarf zusa ̈tzlich erho ̈ht.
