Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 2 Kapitel 2 Verwaltung des Hintergrundspeichers

UniversitätKarlsruhe (TH)

© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 2

Kapitel 2

Verwaltung des Hintergrundspeichers

2


Gegenstand des Kapitels

Mengenorientiertes Datenmodell

Datenmodell

Dateien

Dateiverwaltung

Geräteschnittstelle

Anfragebearbeitung

Satzorientiertes Datenmodell

Speicherstruktur

Schneller Transport zwischen Haupt- und Hintergrundspeicher

Hauptspeicherseiten u. Segmente

Segment- u. Pufferverwaltung Bevorratung von Daten im Hauptspeicher (rechtzeitige Bereitstellung vor Benutzung)

Transparenter homogener Speicher Datentypen:

Seite = feste Anzahl von BytesSegment = var. Anzahl von Seiten

Operatoren:Anforderung/Freigabe von SeitenSegmente anlegen/öffnen/schließen

Datentypen:Block = feste Anzahl von BytesDatei = variable Anzahl v. Blöcken

Operatoren: Dateien anlegen/öffnen/schließen Lesen/Schreiben von Blöcken

Geräte-E/A

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Vorschau auf zukünftig benötigte Daten

Vermeiden nicht aktuell benötigter Daten

Datentypen:Sätze und Satzmengen

Operatoren:Operatoren auf Sätzen

Datentypen:Satzmengen

Operatoren:Operatoren auf Mengen

Datentypen:phys. Zugriffsstrukturen auf Sätze

Operatoren:seq. Durchlauf, gezielte Suche

Optimaler Einsatz der logischen Ressourcen

Performanz

3


Kapitel 2.1Kapitel 2.1

MagnetplattenspeicherMagnetplattenspeicher

4


Kapitel 2.1.1Kapitel 2.1.1

Technische EigenschaftenTechnische Eigenschaften

5


Latenzzeit: Zeit von der Anforderung bis zum kompletten Erhalt der Daten

Latenzzeit

Hauptspeicher Disk-Array-Controller

Prozessor

Bus

vernachlässigbar

Latenzzeit daher hier bestimmt!

6


Speichertopologie

Plattenoberfläche eingeteilt in Spuren Spuren formatiert in durch Lücken getrennte

Sektoren fester Größe (Slots) von 1-8 kB Sektoren sind Schreib-/Lese-Einheit Adressierung: Zylinder-Nr/Spur-Nr/Sektor-

Nr

7


Technische Merkmale von Magnetplatten (1)

Beispiel (nach Garcia-Molina et al., 2002):

Plattendurchmesser 3,5 in

Zahl der Oberflächen 16 (24)

Zahl d. Zylinder (Spuren pro Oberfläche) 16.384 (214)

Mittl. Zahl der Sektoren pro Spur 128 (27)

Sektorkapazität 4.096 B (212)

Spurkapazität 512 kB (219)

Gerätekapazität 128 GB (237)

8



Suchzeit (nach Garcia-Molina et al.):

Zugriff selber Zylinder 0 ms

Zugriffsbewegung (min) tsmin 3 ms

Zugriffsbewegung (mittel) tsav 8 ms

Zugriffsbewegung (max) tsmax 17 ms

Suchzeit[ms]

Anzahltraversier-ter Zylinder

Ndev1

4

8

12

16

9



Rotationsverzögerung (nach Garcia-Molina et al.):

Rotationsgeschwindigkeit 7.200 Upm (120 Ups)

Rotationszeit 8,33 ms (1/120)

Min. Verzögerung 0 ms

Max. Verzögerung 8,33 ms

Mittl. Verzögerung 4,16 ms

Verzögerung[ms]

Spuranteil bevor Sektor erreicht ist

10

4,16

8,33

0,5

10



Übertragungszeit (nach Garcia-Molina et al.):

Mittl. Zahl der Sektoren pro Spur 128

Nutzanteil pro Sektor 90%

Rotationszeit 8,33 ms (1/120)

Rotationswinkel pro Sektor (3600,9)/128 = 2,53125o

Transferzeit pro Sektor 8,332,53125/360 = 0,0586 ms

Übertragungsrate 60 MB (512kB120)

Fazit:Positionierungen (Suchzeit und Rotationsverzögerung) dominieren die Latenzzeit.Sie stellen die Engpassressource dar.

11


RAM: Eine Alternative?

Jahr Plattenkosten pro MB in Dollar

RAM-Kosten pro MB in Dollar

Kostenverhältnis

1956 10.000 ? ?

1980 250 ? ?

1985 100 ? ?

1990 10 ? ?

1995 1 ? ?

2000 0.02 1 50

2005 0.001 0.1 100

2007 0.0003 0.03 100

Quelle: http://www.littletechshoppe.com/ns1625/winchest.htmlc‘t Oktober 2007

Auch im laufenden Betrieb kann nur ein kleiner Teil der Datenbasis im RAM geführt werden!

12


Flash-Speicher: Eine Alternative?

Merkmal Flash-Speicher Plattenspeicher

Kapazität in GB 32 250

Zugriffszeit in ms 0,1 10

Übertragungsbandbreite in MB/s 66 300

Energiebedarf (aktiv/Leerlauf/Schlaf) in W 1 / 0,1 / 0,1 10 / 8 / 1

Preis pro GB in US$ 31,20 0,32

Lesezeit für 4kB/256kB-Block in ms 0,16 / 3,98 12,01 / 12,85

Quelle: Comm. ACM, Juli 2009, Seite 50

Schreiben immer noch problematisch: Überschreiben: Löschen+Schreiben 1-2 ms + 0,25 ms

Löschzeit durch Vorratshaltung vermeidbar Überschreiben max. 10.000 bis 100.000 mal

Sinnvoll: Teil der Speicherhierarchie

13



PerformanzPerformanz

14


Latenzzeit (1)

Gleichzeitiger Zugriff auf mehrere Speicher, somit innerhalb eines Zeitintervalls mehrere Positionierungen gleichzeitig.

Ziel: Verkürzung der mittl. (Suchzeit + Rotationsverzögerung).

Ansatz Datenparallelität: Überlappe Speicherzugriffe.

Disk-Array-Controller

15


Parallelität (1)

© Prof. Kemper, TUM

Bei einfacher Positionierungszeit steigt die Übertragungsbandbreite linear mit der Anzahl der Zugriffsarme Verbindungsweg muss für die höhere Übertragungsrate ausgelegt werden.

16


Platten-Felder (1)

Gängige Realisierung durch Hunderte kleinerer, über ein einziges Steuerwerk eng gekoppelter Platten = Verteilung derselben Speicherkapazität auf mehrere, kleinere Platten.

Wirtschaftliche Lösung für die Hintergrundspeicherung, weil diese Platten aufgrund hoher Stückzahlen nur noch geringe Speicherkosten verursachen (man spricht dann auch von Redundant Arrays of Inexpensive Disks (RAID)).

Heute sehr verbreitet!

17


Platten-Felder (2)

Partitionierung der Daten: Declustering: Anwendungsspezifische Partitionierung.

Voraussetzung: Vorwissen über Nutzung der Daten. Striping: Auffassung der Daten als Bytesequenzen und

Verteilung nach einem regelmäßigen Muster.

Disk-Array-Controller

B13

B11B12

Spiegelung: Replikation auf allen Platten. Lesen beschleunigt, Schreibdauer unverändert.

18


Latenzzeit (2)

Ziel: Verkürzung der mittl. Suchzeit.Ansatz Aufzugstrategie: Sammle und optimiere.

Minimiere Kopfbewegungen: Bleibe im unteren Teil der Kurve.

Suchzeit[ms]

Anzahltraversier-ter Zylinder

Ndev1

4

8

12

16

Controller: Sammle dazu mehrere Zugriffswünsche und arbeite sie in der Reihenfolge des Überstreichens der Oberflächen ab.

19


Aufzugstrategie

Adr. Zylinder2000600014000



Kopf





0 5000 10000 15000 20000


Kopf

0 5000 10000 15000 20000


Adr. Zylinder4000

Adr. Zylinder

20



DateienDateien

21



FunktionalitätFunktionalität

22


Funktionale Sicht auf Hintergrundspeicher

Adressierung eines Slot:

Bezeichnungder Platte

Nummerdes Zylinders

Nummerder Spur

Nummerdes Slots

Speichergeräte (Technologie)Formatierung in Sektoren

Funktionalität: Einheitliche Sicht auf alle Geräte als Menge von Sektoren (Slots) unveränderlicher Position und Länge

23


Funktionserweiterung zu Dateien (1)



Von der Struktur zum inhaltstragenden Behälter Physischer Block:

Einbezug von Vorwissen Physische Datei: Gruppierung (irgendwie) als zusammengehörig betrachteter Blöcke (Unterteilung der Blockmenge)

24


Funktionserweiterung zu Dateien (2)

Physische Dateien

Funktionalität: Sammlung von als zusammengehörig betrachteten BlöckenAbstraktion von der physischen Position von Blöcken: Die Blöcke werden über eine laufende Nummer adressiert.Datei: Unabhängigkeit von Geräten und deren Eigenschaften



25



Performanz und SkalierbarkeitPerformanz und Skalierbarkeit

26


Latenzzeit (3)

Umsetzung: Datenparallelität. Ablegen des logischen Blocks in physisch benachbarten

Sektoren.

Ziel: Verkürzung der mittl. (Suchzeit + Rotationsverzögerung).

Ansatz Mehr Daten pro Suchzeit und Rotationsverzögerung: Sofern Daten aus mehreren physischen Blöcken gemeinsam genutzt werden, übertrage sie gemeinsam Definiere logischen Block als Folge physischer Blöcke.

Definition: Wir bezeichnen zwei Sektoren S1 und S2 als benachbart, wenn der gemeinsame Zugriff von S1 zu S2 minimal mögliche Zeit in Anspruch nimmt.

27


Nachbarschaft (1)

S6S5 S4

S1

S3

S8S7

B1B6S6

S5 S4

S1

S3

S2S8

S7

B1B6S6

S5 S4

S1

S3

S2S8

S7

Blöcke sind physisch benachbart, wenn sie geeignet versetzt auf der selben Spur oder einer anderen Spur des selben Zylinders liegen (das Umschalten von einer Spur auf eine andere innerhalb eines Zylinders kostet keine Zeit).

28


Nachbarschaft (2)

Versetzte Zuordnung der Sektoren zu einem logischen Block: Versatz: Positionierung des benachbarten Sektors unter

dem Schreib-/Lesekopf muss die Bearbeitungszeit für einen übertragenen Sektor berücksichtigen.

Beispiel: Interleave (Versatz) -Faktor von 2:

S6

S5 S4

S1

S3

S2

S8

S7

B11

B12

B14

B13

29


Nachbarschaft (3)

Logischer Block als Übertragungseinheit: Beispiel: Übertragung eines logischen Blocks, gespeichert

in 4 physisch benachbarten Sektoren. Latenzzeit = mittl. Suchzeit+mittl. Rotationsverzögerung

+Transferzeit(4 Sektoren)+Wartezeit(3 Lücken) = 8+4,16+40,0586+30,0065 = 12,16+0,254 = 12,21 ms

Beispiel: Übertragung eines logischen Blocks, gestreut gespeichert in 4 getrennten Sektoren. Latenzzeit = 4 Sektoren (mittl. Suchzeit+mittl.

Rotationsverzögerung+Transferzeit) = 4 (8+4,16+0,0586) = 48,64+0,234 = 48,9 ms

30


Blocklänge

Wie viele Sektoren soll ein logischer Block zweckmäßig umfassen? Obergrenze bei Nichtparallelität: Zylinder. Große Länge: Starke Reduktion von mittlerer Suchzeit und

Rotationsverzögerung, aber Gefahr des Übertragens vieler nicht benötigter Daten.

Geringe Länge: Gezielte Übertragung benötigter Daten, aber Gefahr hoher (gesamter) Suchzeit und Rotationsverzögerung.

Folgerung: Betrachte Auswirkungen auf den höheren Schichten der

Architektur. Mache Länge einen Parameter für die Administration.

31


Skalierbarkeit (1)

Aufgabe: Primitive Grundform der dynamischen Menge: Wachsen

und Schrumpfen muss möglich sein.

Lösung: Physische Platten werden in Partitionen eingeteilt. Eine

Partition ist ein zusammenhängender Bereich von Zylindern (Bsp.: Zylinder 102 bis Zylinder 201).

Einer Datei können eine oder mehrere (nicht notwendig zusammenhängende) Partitionen zugeordnet werden. Die Partitionen der Datei können zu einer oder mehreren

physischen Platten gehören.

Eine Datei kann beliebig wachsen und schrumpfen, indem Partitionen hinzugenommen bzw. wieder entfernt werden.

32


Skalierbarkeit (2)

Jede physische Platte besitzt eine Partitionstabelle, die die Partitionierung der Platte beschreibt. Sie ist auf einem ausgezeichneten Sektor der Platte abgelegt (bspw. dem ersten).

Partitionstabelle für physische Platte sda:Partitions-Nr. Start-Zylinder End-Zylinder Größe (Bytes)

sda1 1 316 666886

sda2 317 632 666918

sda3 633 674 88641

sda4 675 691 35847

sda5 692 730 82278

sda6 731 1020 612013

33


Skalierbarkeit (3)

Jede Datei wird durch eine Tabelle definiert, die die Partitionen angibt, die zu ihr gehören. Die Tabellen sind auf einer ausgezeichneten physischen Platte in einem ausgezeichneten Sektor abgelegt.

Definitionstabelle für Datei 4711:

Phys. Platte Partition Partitionsgröße(Blöcke)

sda sda1 666

sda sda5 82

sdb sdb2 328

Performanz: Wenn – wie häufig – der sequenzielle Zugriff dominiert, sollten die Partitionen möglichst groß gewählt werden.

34


Adressierung von Blöcken (1)

Die Blockgröße soll innerhalb der Datei einheitlich sein, da ansonsten die Verwaltung zu kompliziert wird. Für die Nummerierung der (logischen) Blöcke einer Datei

wird eine Ordnung der Partitionen benötigt und in einer Datenstruktur verwaltet. Die Blöcke werden z.B. nach aufsteigenden Partitionsnummern und dort nach aufsteigenden Sektoradressen nummeriert.

Die Sektoradresse zu einer Blocknummer kann mittels der Definitionstabelle der Datei und den entsprechenden Partitionstabellen der physischen Platten berechnet werden.

35


Adressierung von Blöcken (2)

Phys. Platte Partition Partitionsgröße(Blöcke)

sda sda1 666

sda sda5 82

sdb sdb2 328

Partitions-Nr. Start-Zylinder End-Zylinder Größe (Bytes)

sda1 1 316 666886

sda2 317 632 666918

sda3 633 674 88641

sda4 675 691 35847

sda5 692 730 82278

sda6 731 1020 612013

Log. Block: Nr, Länge

Benötigte Partition und partitionsinterne Blocknummer

Spur(en) mit log. Block, daraus Sektornummern der phys. Blöcke

Datei 4711

Platte sda

36


Zusammenfassung (1)

Physische Dateien

Funktionalität: Dynamisch wachsende und schrumpfende Sammlung von als zusammengehörig betrachteten logischen BlöckenBlöcke haben feste und gleiche, für die Datei wählbare Länge.Abstraktion von der physischen Position von Blöcken: Die Blöcke werden über eine laufende Nummer adressiert.Datei: Unabhängigkeit von Geräten und deren Eigenschaften



37


1

liegt in▼

1..

Zusammenfassung (2)

Zusammenhang zwischen Dateien und physischen Platten:

Physische Platte

Partition

Zylinder Spur Sektor

umfasst

▼

Datei Log. Blockenthält ▶

1..

1..

1

1..

1

enthält ▶

1 1..enthält ▶

1 1..enthält ▶

1 1..

1

umfasst▼

▲gehört zu

▲gehört zu

38



FunktionalitätFunktionalität

39


Dateiverwaltung (1)

Schnittstelle für Dateien in der Betriebssteuersprache:

Erzeugen/Zerstören von Partitionen und Dateien.

Zuordnung von Partitionen zu Dateien.

Schnittstelle für Blöcke durch prozedurale Einbettung der Operationen:

Öffnen/Schließen von Dateien zum Lesen bzw. Lesen und Schreiben.

Operationen zum Lesen und Schreiben eines Blocks: Fetch, Write, Check, Wait. Hierbei sind sequenzielle oder direkte (wahlfreie) Blockzugriffe möglich.

40


Dateiverwaltung (2)

Reines Behälterprinzip: Logische Blöcke nehmen beliebige Inhalte auf.

Die Inhalte werden durch die Datei-Anwendung bestimmt.

Varianten der Behälter-Allokation: Behälter-Verwaltung durch die Anwendung: Die

Dateiverwaltung stellt dazu der Anwendung eine Behältermenge (z.B. alle Blöcke einer Datei) zur Verfügung.

Behälter-Verwaltung durch die Datei-Verwaltung: Die Dateiverwaltung stellt dazu der Anwendung einzelne Behälter zur Verfügung erfordert i. Allg. eine dateispezifische Freispeicherverwaltung.

Wahl für Datenbanksysteme: Kontrolle dorthin wo mehr Hintergrundwissen vorliegt.

41



ZuverlässigkeitZuverlässigkeit

42


Einzelne Platte

Hardware: Verwendung selbstkorrigierender Fehlercodes. Vorhalten von Ersatz-Sektoren bei fehlerhaften Sektoren.Steuerung bei Lesen: Einfaches Lesen: Abbruch bei Fehler und Fehlermeldung. Sicheres Lesen: Bei erfolglosem Lesen Wiederholung bis

zu 255-mal.Steuerung bei Schreiben: Einfaches Schreiben: Keinerlei Garantie für atomares

Schreiben katastrophale Auswirkung. Sicheres Schreiben: Garantiert atomares Schreiben durch

Lesen nach Schreiben und Vergleich. Stabiles Schreiben: Sicheres Schreiben + Sicherung gegen

Datenverlust durch „Sektor-Pairing“.

43


Platten-Felder

Partitionierung der Daten: Declustering: Anwendungsspezifische Partitionierung.

Voraussetzung: Vorwissen über Nutzung der Daten. Striping: Auffassung der Daten als Bytesequenzen und

Verteilung nach einem regelmäßigen Muster. Spiegelung: Replikation auf allen Platten.

Lesen beschleunigt, Schreibdauer unverändert.

„The problem with many small disks: Many small faults“

Sei MTTF Erwartungswert für die Zeit zwischen zwei Ausfällen einer Platte (mean-time-to-failure).

Dann Erwartungswert für die Zeit zwischen zwei Ausfällen eines Feldes mit N Platten: MTTF/N.

44


RAID 0: Striping auf Block-Ebene

Lastbalancierung wenn alle Blöcke mit gleicher Häufigkeit gelesen/geschrieben werden

Doppelter Durchsatz beim sequentiellen Lesen der Datei bestehend aus den Blöcken ABCD...

Stripingbreite = Anzahl der Platten, hier 2 Nur Skalierbarkeit, keine erhöhte Zuverlässigkeit

AA

CC

BB

DD

AA BB CC DDDateiDatei

Quelle: Prof. Kemper, TUM u. Prof. Pfeifer, HHN

45


RAID 1: Spiegelung (mirroring) Zuverlässigkeit: durch Redundanz aller Daten (engl. mirror) Doppelter Speicherbedarf Lastbalancierung beim Lesen: z.B. kann Block A von der

linken oder der rechten Platte gelesen werden Aber beim Schreiben müssen beide Kopien geschrieben

werden Kann aber parallel geschehen Dauert also genauso lange wie das Schreiben nur eines

Blocks

AA

CC

BB

DD

BB

DD

AA

CC

AA BB CC DD

DateiDatei


46


RAID 0+1: Striping und Spiegelung

Kombiniert RAID 0 und RAID 1 Immer noch doppelter Speicherbedarf Zusätzlich zu RAID 1 erzielt man hierbei auch einen höheren

Durchsatz beim Lesen der gesamten Datei ABCD.... Wird manchmal auch als RAID 10 bezeichnet

AA

CC

BB

DD

AA

CC

BB

DD

AA BB CC DD DateiDatei


47


RAID 3: Striping auf Bit-Ebene Anstatt ganzer Blöcke, wie bei RAID 0 und RAID 0+1, wird das

Striping auf Bit- (oder Byte-) Ebene durchgeführt (RAID 2) Es wird auf einer Platte noch die Parität der anderen Platten

gespeichert. Parität = bit-weise xor (RAID 3) Dadurch lässt sich der Ausfall einer Platte kompensieren Das Lesen eines Blocks erfordert den Zugriff auf alle Platten

Verschwendung von Schreib/Leseköpfen Alle marschieren synchron

1010 1101 1011 0110 0011 1100....1010 1101 1011 0110 0011 1100.... DateiDatei

111001...111001... 010101...010101... 101110...101110... 011010...011010... 011000...011000...

Paritäts-platte

Paritäts-platte


48


RAID 3: Plattenausfall

1010 1101 1011 0110 0011 1100....1010 1101 1011 0110 0011 1100.... DateiDatei

111001...111001... 010101...010101... 101110...101110... 011010...011010... 011000...011000...

Paritäts-platte

Paritäts-platte

011010...011010...

ReparaturReparatur


49


RAID 4: Striping von Blöcken + Parität

RAID 3: Beim Schreiben muss auf jede Platte zugegriffen werden

Bessere Lastbalancierung durch Block-bezogene Parität Bei Modifikation von Block A zu A‘ wird die Parität PA-D wie folgt neu

berechnet:

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

Aber: Paritätsplatte bildet einen Flaschenhals

HH PA-DPA-D PE-HPE-HAA EE BB FF CC GG DD


50


HH

RAID 5: Striping v. Blöcken + verteilte Parität

Bessere Lastbalancierung als bei RAID 4 Die Paritätsplatte bildet jetzt keinen Flaschenhals mehr Wird in der Praxis häufig eingesetzt Guter Ausgleich zwischen Platzbedarf und Leistungsfähigkeit Versagt nur bei gleichzeitigem Versagen mehrerer Platten (

weitere RAID-Stufen).

AA EE BB FF CC GG DD PA-DPA-DPE-HPE-H

II MM JJ OO LLNN KK PPPI-LPI-LPM-PPM-P


Documents

Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 2 Kapitel 2 Verwaltung des Hintergrundspeichers