67
Hauptspeicher- Datenbanksysteme Hardware-Entwicklungen Anwendungsstudie: Handelsunternehmen Column- versus Row-Store OLAP&OLTP: Snapshotting Kompaktifizierung Mehrbenutzersynchronisation Indexierung Multi-Core Anfragebearbeitung

Hauptspeicher- Datenbanksysteme

  • Upload
    maris

  • View
    36

  • Download
    0

Embed Size (px)

DESCRIPTION

Hauptspeicher- Datenbanksysteme. Hardware-Entwicklungen Column - versus Row -Store . Hauptspeicher-Datenbanksysteme. Disk is Tape, Tape is dead … Jim Gray Die Zeit ist reif für ein Re- engineering der Datenbanksysteme - PowerPoint PPT Presentation

Citation preview

Page 1: Hauptspeicher- Datenbanksysteme

Hauptspeicher-Datenbanksysteme• Hardware-Entwicklungen• Anwendungsstudie: Handelsunternehmen• Column- versus Row-Store• OLAP&OLTP: Snapshotting• Kompaktifizierung• Mehrbenutzersynchronisation• Indexierung• Multi-Core Anfragebearbeitung

Page 2: Hauptspeicher- Datenbanksysteme

Vortrag am Freitag Marcel Kornacker Cloudera Impala 13 Uhr

Page 3: Hauptspeicher- Datenbanksysteme

Hauptspeicher-Datenbanksysteme Disk is Tape, Tape is dead … Jim Gray

Die Zeit ist reif für ein Re-engineering der Datenbanksysteme

Man kann heute für 25000 Euro einen Datenbankserver mit 1 TeraByte Hauptspeicher und 32 Rechenkernen kaufen

Page 4: Hauptspeicher- Datenbanksysteme
Page 5: Hauptspeicher- Datenbanksysteme

Network in the small and in the large

Page 6: Hauptspeicher- Datenbanksysteme

Einsatz von Hauptspeicher-Datenbanksystemen

Page 7: Hauptspeicher- Datenbanksysteme

Feasibility: Main Memory DBMS Amazon

Data VolumeRevenue: 15 billion

EuroAvg. Item Price: 15

Euro1 billion order lines

per year 54 Bytes per order

line 54 GB per year + additional data - compression

Transaction RateAvg: 32 orders per s Peak rate:

Thousands/s+ inquiries

IntelTera Scale InitiativeServer with several

TB main memoryWe just ordered one

from Dell for 49 K Euro

Main Memory capacity will grow faster than Customers‘ Needs

Cf. RAMcloud-project at StanfordOusterhoud et al.

Page 8: Hauptspeicher- Datenbanksysteme

Leistungsengpässe: Profiling eines klassischen Datenbanksystems

Page 9: Hauptspeicher- Datenbanksysteme

9

Widerholung: Speicherhierarchie

Register(L1/L2/L3)

Cache

Hauptspeicher

Plattenspeicher

Archivspeicher

Page 10: Hauptspeicher- Datenbanksysteme

10

Überblick: Speicherhierarchie

Register

Cache

Hauptspeicher

Plattenspeicher

Archivspeicher

1 – 8 ByteCompiler

8 – 128 ByteCache-Controller

4 – 64 KBBetriebssystem

Benutzer

Page 11: Hauptspeicher- Datenbanksysteme

11

Überblick: Speicherhierarchie

1-10nsRegister10-100ns

Cache100-1000ns

Hauptspeicher10 ms

Plattenspeicher

secArchivspeicher

Zugriffslücke105

Page 12: Hauptspeicher- Datenbanksysteme

12

Überblick: Speicherhierarchie

1-10nsRegister10-100ns

Cache100-1000ns

Hauptspeicher10 ms

Plattenspeicher

secArchivspeicher

Zugriffslück

e

105

Kopf (1min)

Raum (10 min)

München (1.5h)

Pluto (2 Jahre)

Andromeda

(2000 Jahre)

Page 13: Hauptspeicher- Datenbanksysteme
Page 14: Hauptspeicher- Datenbanksysteme
Page 15: Hauptspeicher- Datenbanksysteme

Row Store versus Column Store

15

Page 16: Hauptspeicher- Datenbanksysteme

Row Store versus Column Store

16

Page 17: Hauptspeicher- Datenbanksysteme

Anfragebearbeitung

17

Page 18: Hauptspeicher- Datenbanksysteme

Komprimierung

18

Page 19: Hauptspeicher- Datenbanksysteme

Datenstrukturen einer Hauptspeicher-Datenbank

Page 20: Hauptspeicher- Datenbanksysteme

Row-Store-Format

Page 21: Hauptspeicher- Datenbanksysteme

Column-Store-Format

Page 22: Hauptspeicher- Datenbanksysteme

Column-Store-Format (cont‘d)

Page 23: Hauptspeicher- Datenbanksysteme

Einfügeoperation eines Tupels

Insert into Verkaeufe values (12, 007, 4711, 27.50)

Page 24: Hauptspeicher- Datenbanksysteme

Anfragen

Page 25: Hauptspeicher- Datenbanksysteme

Hybrides Speichermodell

Page 26: Hauptspeicher- Datenbanksysteme

Anfragebearbeitung

Page 27: Hauptspeicher- Datenbanksysteme

Anwendungsoperationen in der Datenbank: Stored Procedures

Page 28: Hauptspeicher- Datenbanksysteme
Page 29: Hauptspeicher- Datenbanksysteme

Snapshots für Anfragen

OLTP

Snapshot der Haupt-Datenbank

Haupt-Datenbank

OLAP

Page 30: Hauptspeicher- Datenbanksysteme

Update Staging: In vielen Systemen verwendet, zB. NewDB von SAP

Page 31: Hauptspeicher- Datenbanksysteme

Scan-only Datenbanken: ISAO von IBM oder Crescando von der ETHZ

Page 32: Hauptspeicher- Datenbanksysteme

Ursprüngliches Schattenspeicher-Verfahren: Lorie77 für IBM System R

Page 33: Hauptspeicher- Datenbanksysteme

Copy on Write

Update aa‘2 µs

Page 34: Hauptspeicher- Datenbanksysteme

Snapshotting via fork-ing: Details

Page 35: Hauptspeicher- Datenbanksysteme

Snapshot Maintenance: copy on write

Page 36: Hauptspeicher- Datenbanksysteme

Fast because of Hardware-Support: MMU

Page 37: Hauptspeicher- Datenbanksysteme

OLAP Queries on Tx-Consistent Snapshots

Page 38: Hauptspeicher- Datenbanksysteme

Multiple Query Sessions

Page 39: Hauptspeicher- Datenbanksysteme

Synchronization-Assertions Serializability of the OLTP Transactions

What else if executed serially We support full ACID see coming slides

Snapshot isolation of the OLAP queriesMulti-version mixed synchronization methodSeveral OLAP queries form one Tx = OLAP SessionBernstein, Hadzilacos, Goodman: Chapter 5.5

Page 40: Hauptspeicher- Datenbanksysteme

Kompaktifizierung: Motivation

Page 41: Hauptspeicher- Datenbanksysteme

Kompaktifizierung der Datenbank

Page 42: Hauptspeicher- Datenbanksysteme

Invalidierung gefrorener Datenobjekte

Page 43: Hauptspeicher- Datenbanksysteme

Transaktionsverwaltung: serielle Ausführung auf Partitionen

Page 44: Hauptspeicher- Datenbanksysteme

Snapshot used for Tx-consistentBackup

Page 45: Hauptspeicher- Datenbanksysteme

Logging the Transaction Processing

To Storage Server via 10 Gb/s rDMA Interface

(e.g. Myrinet or Infiniband)

Page 46: Hauptspeicher- Datenbanksysteme

Isolation von OLAP und OLTP

Page 47: Hauptspeicher- Datenbanksysteme

Tentative Ausführung langer Transaktionen

Page 48: Hauptspeicher- Datenbanksysteme

Multi-Version Concurrency Control

Page 49: Hauptspeicher- Datenbanksysteme

Validierung einer Update-Transaktion

Page 50: Hauptspeicher- Datenbanksysteme

Precision Locking: Prädikatprüfung

Page 51: Hauptspeicher- Datenbanksysteme

•Stand-By for OLTP•Active for OLAP•Possible for Backup

High Availability &Load Balancing

Page 52: Hauptspeicher- Datenbanksysteme

A B C D E F

A B CD E

F

Row-S

tore

Column-Store

Page 53: Hauptspeicher- Datenbanksysteme

Indexstrukturen für Hauptspeicher-Datenbanken Radix-Baum / Trie / Präfixbaum

Page 54: Hauptspeicher- Datenbanksysteme

Idee des Adaptiven Radix-Baums ART

Page 55: Hauptspeicher- Datenbanksysteme

Adaptive Knoten des ART-Baums

Page 56: Hauptspeicher- Datenbanksysteme

Join-Berechnung Cache-Lokalität

Mehrkern-Parallelität

NUMA-Berücksichtigung

Synchronisations-freie Parallelität

Page 57: Hauptspeicher- Datenbanksysteme

Grundidee des hoch-parallelen Sort/Merge-Joins

Page 58: Hauptspeicher- Datenbanksysteme

Bereichspartitionierung

Page 59: Hauptspeicher- Datenbanksysteme

Hochparallel Bereichs/Radix-Partitionierung

Page 60: Hauptspeicher- Datenbanksysteme

Real C hacker at work …

Page 61: Hauptspeicher- Datenbanksysteme

Paralleler Radix-Join

Page 62: Hauptspeicher- Datenbanksysteme

Mehrfache Partitionierung des Radix-Joins: Cache-Lokalität

Page 63: Hauptspeicher- Datenbanksysteme

Hash-Join-Teams: Globale Hashtabelle

Page 64: Hauptspeicher- Datenbanksysteme

NUMA-lokale Arbeitszuteilung:„Häppchen“-weise (morsel driven)

Page 65: Hauptspeicher- Datenbanksysteme

Adaptive Dynamische Parallelisierung

Page 66: Hauptspeicher- Datenbanksysteme

66

Page 67: Hauptspeicher- Datenbanksysteme

67

Algorithmen auf sehr großen Datenmengen

R23

445

789013174289

S44179756

272

139

R S

• Nested Loop: O(N2)• Sortieren: O(N log N)• Partitionieren und

Hashing