Data Warehousing

Datenbanksysteme II:
Implementation of Database
Systems
Storage, Discs, and Raid
Material von
Prof. Johann Christoph Freytag
Prof. Kai-Uwe Sattler
Prof. Alfons Kemper, Dr. Eickler
Content of this Lecture
•
•
•
•
Storage hierarchy
Seek times and throughput
RAID level
Some guidelines
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
2
Überblick: Speicherhierarchie
1-10ns
Register
10-100ns
Cache
100-1000ns
Hauptspeicher
10 ms
Plattenspeicher
Zugriffslücke
105
sec
Archivspeicher
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
3
5 Schichten Architektur
Mengenorientierter Zugriff
Datenmodellebene
Anfrageübersetzung, Zugriffspfadwahl,
Zugriffskontrolle, Integritätskontrolle
Satzorientierter Zugriff
Logischer Zugriff
Sortierung, Transaktionsverwaltung,
Cursorverwaltung
Interne Satzschnittstelle
W
ir
Speicherstrukturen
sin
d
Record Manager, Sperrverwaltung, Log /
Recovery
Systempufferschnittstelle
hi
e
Pufferverwaltung
r:
Speichermanagement, Puffermanagement,
Caching-Strategien
Dateischnittstelle
Betriebssystem
Externspeicherverwaltung
Geräteschnittstelle
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
4
Warum die Speicherhierarchie?
• Je schneller, desto teurer
• Platzbedarf – Chip, Platine, Gehäuse, eigenes Gerät, Bandroboter
• Begrenzung Adressraum: 32 bit = 4 Gigabyte
– Hat ein Ende: 64 bit ~ 2*10^10 Gigabyte
– Kostenunterschied bleibt bestehen
• Tertiärspeicher oft nicht mehr günstiger als Sekundärspeicher
– Aber beliebige Erweiterbarkeit durch Wechselmedien (CDs, Tape)
– Kein Controller-Engpass
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
5
Storage Area Networks (SAN)
•
•
•
•
Separate network providing storage (and only storage)
Virtualization of resources
Facilitates data management, storage assignment, backup, recovery
Storage as independent part of enterprise infrastructure
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
6
Caching
• Storage hierarchy
– Access time between level X and X+1 increases rapidly
• Caching
– Makes this difference disappear
– Buffer data from lower levels in higher levels
– Success depends on locality
• Few data items are access over and over again
– System catalog, central tables, most frequently sold items, …
– If access is purely random, caching becomes useless
– Cache hit ratio: # of blocks requested in cache
# of blocks requested
– Database buffers should reach >90% cache hit ratio
– Several issues discussed later
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
7
Magnet- bzw. Festplattenspeicher
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
8
Lesen von Daten von der Platte
• Seek Time: ts
– Arm positionieren
• Latenzzeit: tr
– Warten, bis gewünschter Sektor unter Lesekopf rotiert
– Im Durchschnitt ½ Plattenumdrehung
– Rotationsgeschwindigkeit: 10000 Umdrehungen/Minute
• Disc Controller beginnen, immer komplette Tracks zu cachen
• Dadurch reduziert sich Latenzzeit im Schnitt
– Wann genau??
• Transferrate: u
– Von der Platte zum Hauptspeicher / Buffer
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
9
2004
6 ms
5 ms
420
30-40
150
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
10
Random versus Sequential IO
• Aufgabe: 1000 Blöcke à 4KB sind zu lesen
– Ts= 5ms, Tr = 3ms, U = 15 MB/s
• Random I/O
–
–
–
–
Jedes mal Arm positionieren
Jedes mal Latenzzeit
Î 1000 * (5 ms + 3 ms) + Transferzeit von 4 MB
Î > 8000 ms + 300ms ~ 8s
• Sequential IO
– Einmal positionieren, dann nur noch sequentiell lesen
– Î 5 ms + 3ms + Transferzeit von 4 MB
– Î 8ms + 300 ms ~ 1/3 s
• Unterschied: ein bis zwei Größenordnungen
– Wichtige für Query Optimierung
– Index bei >5% Anfrageselektivität nicht mehr benutzen
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
11
Was kann man besser machen?
• Zugriff parallelisieren
– Blöcke auf verschiedenen Platten lagern
• Diese können parallel positionieren und parallel lesen
– Blöcke redundant auf einer Platte speichern
• Seek-zeit verkürzen bei geschickter Anordnung
• RAID: Redundant Array of Independent Discs
– Unabhängig (voneinander) und billig
– „Commodity Hardware“ mit Software zu schnellen und
fehlertoleranten Systemen zusammenbauen
– RAID-Software im Diskcontroller oder im Betriebssystem
– Auch: „Redundant array of inexpensive discs“
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
12
Disk Arrays Î RAID-Systeme
Oder Soft-Raid
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
13
Soft RAID in Windows XP
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
14
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
15
RAID 0: Striping
A
Datei
B
C
D
A
B
C
D
• Doppelte Bandbreite beim sequentiellen Lesen der Datei
– Zyklische Verteilung der Blöcke, wenn alle Blöcke mit gleicher
Häufigkeit gelesen/geschrieben werden
– Alternative: Verteilung nach Zugriffshäufigkeit (Optimierungsproblem)
• Zugriffshäufigkeit aber i.d.R. nicht bekannt
• Doppelte Bandbreite??
• Keine Beschleunigung für Lesen eines einzelnen Blocks
• Aber: Datenverlust wird immer wahrscheinlicher, je mehr
Platten man verwendet (Stripingbreite = Anzahl der Platten,
hier
2) Datenbanksysteme II, Sommersemester 2005
Ulf Leser:
16
RAID 1: Spiegelung (mirroring)
A
B
A
B
C
D
C
D
• Datensicherheit: durch Redundanz aller Daten
– Keine Hilfe bei Bitfehlern – wer hat recht?
• Doppelter Speicherbedarf
• Lastbalancierung beim Lesen (wie RAID0)
• Außerdem „konkurrierendes“ Lesen einer 1-Block Datei
möglich – der schnellere Kopf gewinnt
• Beim Schreiben müssen beide Kopien geschrieben werden
– Kann parallel geschehen – der langsamere Kopf bestimmt
Seek+Latenz
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
17
Auswirkung von RAID1
• MTTF = Durchschnittliche Zeit bis zu einem Crash
• MTTR = Zeit benötigt für Reparatur
• MTTDL = Durchschnittliche Zeit bis zu einem
Zustand, bei dem Daten nicht zugreifbar sind
– Also z.B. von Band wiederhergestellt werden müssen
• Annahme: MTTF = 3650 Tage, MTTR = 2 Tage
– Eine Platte
• MTTDL1 = 3650/2 = 1825 Tage
– RAID1 mit 2 Platten
• MTTDL = MTTDL1*MTTDL1 ~ 9.000 Jahre
• Bei Annahme der Unabhängigkeit der Ereignisse
• Plattenfehler sind i.d.R. aber nicht unabhängig:
Spannungsspitzen, Wasserschaden, gleichzeitiges Altern, ...
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
18
RAID 0+1: Striping und Spiegelung
A
A
B
B
C
C
D
D
• Kombiniert RAID 0 und RAID 1 („RAID 10“)
• Doppelter Speicherbedarf, erhöhte Ausfallsicherheit (von RAID1)
• Weiter erhöhte Lesegeschwindigkeit für Dateien
– Datei kann von vier Platten parallel gelesen werden
• Lesen eines einzelnen Blocks kaum schneller als ohne RAID
• Schreibgeschwindigkeit einer Datei verdoppelt sich
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
19
RAID 2: Striping auf Bit-Ebene
Datei
1010 1101 1011 0110 0011 1100....
111001...
010101...
101110...
011010...
• Striping auf Bit- (oder Byte-) statt Blockebene
• Idealerweise höherer Durchsatz schon beim Lesen einzelner Blöcke
– Aber: Lesen eines Sektors dauert i.d.R. genauso lange wie Lesen 1/8
Sektors
– Also muss Aufteilung von Blöcken auf Sektoren beachtet werden
• Typisch: 8-16 KB Blöcke, 512 Byte Sektoren = 16-32 Sektoren pro DB Block
• Keine Beschleunigung für mehrere parallele Leseoperationen
– Jedes Lesen/Schreiben braucht alle Platten
• Verschlechterte Ausfallsicherheit
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
20
RAID 3: RAID2 + Paritätsinfo
Datei
1010 1101 1011 0110 0011 1100....
Parität
111001...
010101...
101110...
011010...
011000...
⊕
• Striping auf Bit- (oder Byte-) Ebene
• Zusätzliche Platte für Parität der anderen Platten
– Parität = bit-weise xor ⊕
– Ausfall einer Platte kann kompensiert werden
• Lesen/Schreiben eines Blocks erfordert Zugriff auf alle Platten
• Deutlich weniger Platzbedarf als RAID1, trotzdem Ausfallsicherheit
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
21
RAID 3: Plattenausfall
Datei
1010 1101 1011 0110 0011 1100....
Parität
111001...
010101...
101110...
011010...
011000...
⊕
Reparatur
011010...
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
22
RAID 4: Striping von Blöcken + Paritätsinfo
A
E
B
F
C
G
D
H
PA-D PE-H
• Bessere Lastbalancierung als bei RAID 3
– Verschiedene Prozesse können parallel von verschiedenen Platten lesen
• Damit: Paritätsplatte ist Flaschenhals
– Bei jedem Schreiben muss darauf zugegriffen werden
– Bei jedem Lesen muss u.U. darauf zugegriffen werden (zur Kontrolle)
– Bei Modifikation von Block A zu A‘: P‘A-D := PA-D ⊕ A ⊕ A‘
• D.h. bei einer Änderung von Block A muss der alte Zustand von A und
der alte Paritätsblock gelesen werden und der neue Paritätsblock und
der neue Block A‘ geschrieben werden
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
23
RAID 5: RAID4, Verteilung der Paritity
A
E
B
F
C
G
D
PE-H
PA-D
H
I
M
J
PM-P
PI-L
N
K
O
L
P
• Parityblock immer auf der Platte, die keinen der Par-Blöcke enthält
• Wesentlich bessere Lastbalancierung als bei RAID 4
– Paritätsplatte kein Flaschenhals mehr
– Schreiben erfordert X-1 Platten für die Daten und 1weitere Platte für Parity
– Zugriff erfolgt parallel
• Wird in der Praxis häufig eingesetzt
– Typischerweise langsamer als RAID10
– Dafür deutlich Platz sparender
• Guter
Ausgleich
zwischen
Platzbedarf
und Leistungsfähigkeit
Ulf Leser:
Datenbanksysteme
II, Sommersemester
2005
24
Übersicht
• Weitere RAID Level sind definiert: 6, Kombination 1+5, ...
• RAID 0 gut für Szenarien mit (nahezu) unveränderlichen Daten
– Leicht zu ersetzen bei Ausfall
• RAID 1 und vor allem 5 sind verbreitet
– RAID1: Einfach, schnell zu realisieren, erhöhte Ausfallsicherheit und
Geschwindigkeit, aber verdoppelter Platzbedarf (billig)
– RAID5: Relativ komplex, erhöhte Ausfallsicherheit und Geschwindigkeit,
nur geringfügig erhöhter Platzbedarf; benötigt mindestens 3 Platten
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
25
Storage in Oracle
Database
Tablespace
Logical
Data file
Segment
Physical
Extent
OracleBlock
OS Block
•
Data files are assigned to tablespaces
•
•
•
Extents are continuous sequences of blocks on disc
Space is allocated in extents (min, next, max, …)
Segments logically group all extents of an object
– Tablespaces may consist of multiple files
– All data from one object (table, index) are in one tablespace
– Unit of backup, offline, moveable tablespaces, quotas, access rights, …
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
26
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
27
In reality it is more complex
• Software / Hardware RAID, Database RAID, Volume
manager, SAN
• Parallelization by distributing tablespaces
– System tablespace on separate disk
• Or: locally, tablespace-managed data dictionary
– Separate data and index tablespaces
– Separate disk for REDO Logs
• Parallelization by distributing one tablespace
– Distribute different files in one tablespace on different discs
• Parallelization by distributing a single table
– Distribution of segments
– Partitioning - “semantic” distribution of table data
• All sales prior to 2005 on one disk, all sales this year on another disk
• One disk for sales in 2005, 2004, 2003, …
• Complex dependencies
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
28
Some guidelines (copyright by Oracle)
• „Tablespaces should stripe over at least as many devices as CPUs“
• “You should stripe tablespaces for tables, indexes, rollback segments,
and temporary tablespaces. You must also spread the devices over
controllers, I/O channels, and internal buses“
–
–
–
–
Queries can run in parallel (inter-query parallelization) on every processor
Processors need to be fed in parallel
Single disk is bottleneck – multiprocessors become useless
If table segment in tablespace is striped sufficiently, each disk becomes a
“feed” for a one processor
– How?
• Use RAID1 or above
• Place carefully data files, segments, and extents
– Disadvantages
• No simple backup of tablespace by file copying
• Increased failure rate – use redundant RAID levels
• Recovery of a single disk might stop operations (all other disks are involved)
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
29
Guidelines 2
• „In high-update OLTP systems, the redo logs are writeintensive. Moving the redo log files to disks that are
separate from other disks and from archived redo log files
has … benefits …“
– Every transaction generates REDO information
– REDO is written in batches before Commit, data blocks are written
sporadically by db-writer
– Both should not interfere (requires too much disk head moving)
• Hence: put REDO log files away from data files
– Redo data is extremely important (rollback, rollforward)
• Hence: spread REDO data redundantly over many disks (REDO groups)
– Also: Disk crash can only effect REDO or data files
– REDO disks are good places to invest RAID10
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
30
Guidelines 3
• Data bottlenecks
– Temporary tablespace – used for large SORTS
• And sorting is everywhere – sort-merge join, group by, order
by, distinct, ...
– System tablespace
• Holds data dictionary
• Required all the time – logs, latches, system log data, ...
• Especially logs can be a bottleneck
– „Managed tablespaces“
– REDO log files
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
31
Oracle flexible architecture (OFA)
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
32
OFA - Quote
• “The minimum configuration consists of seven data areas,
either disks, striped sets, RAID sets, ... The more heads
you have moving at one time, the faster your database will
be.”
– AREA1: Oracle executables and user areas, a control file, the
SYSTEM tablespace, redo logs
– AREA2: Data-data files, a control file, tool-data files, redo logs
– AREA3: Index-data files, a control file, redo logs
– AREA4: Rollback segment-data files
– AREA5: Archive log files
– AREA6: Export Files
– AREA7: Backup Staging
Ulf Leser: Datenbanksysteme II, Sommersemester 2005
33