chapter03.pdf

Anwendersoftware (AS) Anwendersoftware (AS)

Datenbanken und Informationssysteme

Kapitel 3: Externspeicherverwaltung

Bernhard Mitschang Universitt Stuttgart

Wintersemester 2013/2014

Teile zu diesem Folienskript beruhen auf einer hnlichen Vorlesung, gehalten von Prof. Dr. T. Hrder am Fachbereich Informatik der Universitt Kaiserslautern und Prof. Dr. N. Ritter am Fachbereich Informatik der Universitt Hamburg. Fr dieses Skriptum verbleiben alle Rechte (insbesondere fr Nachdruck) bei den Autoren.

Externspeicherverwaltung

2

bersicht

Externspeicherverwaltung Allgemeine Aufgaben Speicherhierarchie

Speicherzuordnungsstrukturen (Dateien und Blcke) Dateikonzept Verfahren der Blockzuordnung

Manahmen zur Fehlertoleranz Lesen und Schreiben von Blcken Nutzung von Speicherredundanz

Seitenzuordnungsstrukturen (Segmente und Seiten) Segmentkonzept verzgerte Einbringstrategien Bewertung der Seitenzuordnungsverfahren


3

Adressierungseinheiten: Relationen, Sichten, Tupel Hilfsstrukturen: externe Schemabeschreibung, Integrittsregeln Adressierungseinheiten: externe Stze, Sets, Schlssel, Zugriffspfade

Logische Datenstrukturen

Mengenorientierte DB-Schnittstelle Sprachen wie SQL, QBW, etc.

Adressierungseinheiten: externe Stze, Sets, Schlssel, Zugriffspfade Hilfsstrukturen: Zugriffspfaddaten, interne Schemabeschreibung Adressierungseinheiten: interne Stze, B*-Bume, Hash-Tabellen, usw.

Logische Zugriffspfad- strukturen

Satzorientierte DB-Schnittstelle FIND NEXT Satzname, STORE Satzname, etc.

Speicherungs- strukturen

Interne Satzschnittstelle Speichere Satz, Fge Eintrag in B*-Baum ein, etc.

Adressierungseinheiten: Seiten, Segmente

Hilfsstrukturen: Seitentabellen, Blocktabellen, etc.

Adressierungseinheiten: Blcke, Dateien

Seitenzuordnungs- strukturen

DB-Pufferschnittstelle Stelle Seite j bereit, Gib Seite j frei

Adressierungseinheiten: interne Stze, B*-Bume, Hash-Tabellen, usw. Hilfsstrukturen: Freispeicher-Info., Adretab., Seitenindices, usw. Adressierungseinheiten: Seiten, Segmente

Gerteschnittstelle


Hilfsstrukturen: Freispeicher-Info Extent-Tabellen, Dateikataloge, etc.

Adressierungseinheiten: Spuren, Zylinder, Kanle, etc.

Dateischnittstelle Lies Block k, Schreibe Block k

Speicherzuordnungs-strukturen


4

Allgemeine Aufgaben der Externspeicherverwaltung

Verwaltung externer Speichermedien Verbergen von Gerteeigenschaften Abbildung von physischen Blcken auf externen Speicher Kontrolle des Datentransports von/zum Hauptspeicher ggf. Realisierung einer mehrstufigen Speicherhierarchie Fehlertoleranzmanahmen (stabiler Speicher, Spiegelplatten etc.)


5

Speicherhierarchie

Hauptspeicher

Externer Speicher (Online)

Archivspeicher (Nearline)

Archivspeicher (Offline)

Cache

Speicherkapazitt

aktuelle Daten

Register

Cache

Prozessor

Preis, Geschwindigkeit


6

Modell einer zweistufigen Speicherhierarchie

Vereinfachte E/A-Architektur: Modell fr Externspeicheranbindung vor Bearbeitung sind die Seiten in den DB-Puffer zu kopieren genderte Seiten mssen zurck geschrieben werden

Magnetplattenspeicher < 10 ms

Hauptspeicher < 100 ns

Zugriffslcke > 105

P1

P4

P2 P5

P3

Betriebssystem

DB-Puffer im HSP

DBMS

Datei-Puffer

P1

P2 P3 P4

P5

Steuer- einheit


7

bersicht






8

Abbildung von Dateien und Blcken

Beispiele fr Aufrufe von Operation an der oberen Schnittstelle

Abbildungsfunktion:

Durchfhrung der E/A:

Eigenschaften der oberen Schnittstelle Menge durchnummerierter Blcke innerhalb von Dateien Lese- und Schreibzugriff ber die Blocknummer Blockzugriff kann auf Lesefehler fhren, Blcke knnen alte oder ungltige

Daten enthalten

PAM UPAMDAT, RD, FECB=ESTBLOCK, HP=1 UPAMDAT FCB FCBTYPE=PAM, LINK=EIN, IOAREA1=EINBER

Blocknummer cyl-#, track-#, rec-#

Armpositionierung: EXCP CCW Spurauswahl: EXCP CCW I/O-Prozessor Satzbertragung: EXCP CCW }


9

Dateikonzept

Dateien reprsentieren externe Speichermedien fr Anwendungsprogramme in einer gerteunabhngigen Weise. Das Dateisystem verdeckt die Eigenschaften physischer Speichergerte und bietet als abstrakte Sicht Dateien, die als lange Byte-Vektoren behandelt werden knnen.

Grnde fr ein Dateikonzept selektive Aktivierung von Dateien: on/offline-Problem dynamische Definition temporre Dateien Einsatz unterschiedlich schneller Speichermedien krzere Adresslngen

Dateisystem ist als lokales Dateisystem oder als eigenstndiger Datei-Server realisiert verwaltet typischerweise einen hierarchischen Namensraum bietet Operationen fr Dateiverwaltung und Dateizugriff

Operationen: CREATE/DELETE zum Anlegen und Lschen einer Datei OPEN/CLOSE zur Vorbereitung und Beendigung der Verarbeitung einer Datei READ/WRITE zum Lesen und Schreiben eines Blocks einer Datei

DateienvonMenge

SpeicherDB=


10

Realisierung eines Dateisystems

Dateikatalog fr alle Dateien feste Position effiziente Implementierung und

Verarbeitung

Objektbezogene Beschreibung durch Dateideskriptor Dateiname, OwnerID, . . . Zugriffskontrollliste Zeitinformation ber Erzeugung, letzter

Zugriff, letzte Archivierung, Dateigre, Blockzuordnung, ...

Freispeicherverwaltung fr Externspeicher formatierte Bitlisten hierarchische Struktur

Einheit des physischen Zugriffs: Block Blcke variabler Lnge? feste Blocklnge pro Datei chained I/O wichtig fr hohe E/A-

Leistung

Datei

Datei- Attribute

objektbezogene Beschreibung im Katalog

gertebezogene Freispeicher-Info

name

n Magnet- platten

D1


11

Dateiorganisationsformen

Datei in Einfgereihenfolge (entry-sequenced): Einfgen an Dateiende, Satzadresse ist RBA (relative Byteadresse), sequentieller Zugriff oder direkter Zugriff ber RBA

relative Datei: Organisationsform ist ARRAY OF RECORDS

wertbasierte Dateien erlauben Zugriff ber Satzschlssel

Datei in Schlsselreihenfolge (key-sequenced): Speicherung der Stze in Schlsselreihenfolge, direkter Zugriff ber Schlssel und sortiert-sequentieller Zugriff. Bezeichnungen in existierenden Systemen (logische Zugriffsmethoden): SAM, ISAM, VSAM, . . .

Hash-Datei: direkter Zugriff ber Schlsseltransformation

Datei

strukturiert unstrukturiert (byte stream)

direkt wertbasiert

Einfge- reihenfolge

relativ Schlssel- reihenfolge

Hash


12

Blockzuordnungsverfahren

Statische Datei-Zuordnung direkte Adressierung minimale Zugriffskosten keine Flexibilitt

Dynamische Extent-Zuordnung Adressierung ber eine

kleine Tabelle geringe Zugriffskosten mige Flexibilitt

Dynamische Block-Zuordnung Adressierung ber eine

groe Tabelle hohe Zugriffskosten maximale Flexibilitt

Katalog

Katalog

Katalog


13

Blockzuordnung durch Extent-Tabellen

Bj+1 Bj+2 Bj+3

Bl

B1 B2 B3

Bi

B4 B5

Bl+1

Bmk

Bi+1 Bi+2

Bj

Magnetplatte MP1, Typ A Magnetplatte MP2, Typ B

Bereich 1

Bereich 4

Magnetplatte MP2, Typ B Magnetplatte MP1, Typ A

DB-Puffer (Hauptspeicher)

Bereich 3

Bereich 2

Extent-Tabelle fr Datei Dk

Dargestellte Aktionen der Zugriffsprimitive: - Hole Block B5 - Hole Block Bj+3 Falls ein Block zum Schreiben in den DB-Puffer geholt wird, ist er nach Freigabe wieder zurckzuschreiben

Name Typ Bereichsanfang ZYL, SPUR

Anzahl Blcke

M P1 A Z201, S5 i M P2 B Z350, S1 j - i M P2 B Z105, S1 l - j M P1 A Z499, S7 mk - l

Directory

In typischen Implementierungen dieses Verfahrens kann ein Primrbereich (primary extent) angelegt werden, der um bis zu 15 Sekundrbereiche (secondary extents, mit jeweils gleicher Gre) erweitert werden kann.


14

bersicht






15

Manahmen zur Fehlertoleranz

MTTF von verschiedenen Plattenfehlern

Ziel: Fehler mglichst frhzeitig erkennen und behandeln Manahmen von Festplatten-Hardware und Controller Manahmen des DBS

Type of Error MTTF Recovery Consequences

Soft data read error 1 hour Retry or ECC None

Recoverable seek error 6 hours Retry None

Maskable hard data read error 3 days ECC Remap to new sector and rewrite good data

Unrecoverable data read error 1 year None Remap to new sector, old data lost

Device needs repair 5 years Repair Data unavailable

Miscorrected data read error 10 years None Read wrong data

Quelle: [GR93]


Lesen und Schreiben von Blcken

Einbringeinheit: 1 Block Fehlertoleranzmanahme fr einen Block gegen transiente Fehler,

Schreibfehler, Systemausfall, Block- (Spur-, Gerte-) Zerstrung

Einfaches Lesen Lesen kann durch transiente Fehler gestrt werden. Zusatzmanahme: erfolgloses Lesen wird n-mal wiederholt (sicheres Lesen)

Einfaches Schreiben Schreiben des Blocks als atomare Aktion (ganz oder berhaupt nicht) kann

nicht garantiert werden. Schreiben kann durch transiente und dauerhafte Fehler zu falschen Resultaten

fhren, z.B. - Controller liefert normalen Return-Code trotz fehlerhafter Schreiboperation

Crash kann teilweise geschriebenen Block zurcklassen.

16


17

Sicheres Schreiben (read-after-write)

Nach einem einfachen Schreiben wird der Block wieder gelesen und mit dem Originalblock verglichen.

Operationsfolge wird wiederholt, bis Block erfolgreich geschrieben ist. Schreiben ist gesichert gegen transiente Fehler. Crash kann teilweise geschriebenen Block zurcklassen.


18

Stabiles Schreiben (duplexed write)

Jeder Block hat eine Versionsnummer, die bei jedem stabilen Schreiben erhht wird.

Jeder Block wird in festgelegter Reihenfolge in zwei verschiedene Slots Sj und Sk geschrieben

Prinzip: Stabiler Speicher Annahme: Ein Block wird nicht in einen falschen

Slot geschrieben, sonst ist read-after-write erforderlich. Lesen von Bi erfolgt erst von Slot Sj.

Falls es erfolgreich ist, wird angenommen, dass es sich um die jngste gltige Version von Bi handelt.

Falls das Lesen von Slot Sj scheitert, wird Slot Sk gelesen.

Da ein Systemausfall nur einen Schreibvorgang unterbrechen kann, ist bei Wiederanlauf stets eine Version des Blockes verfgbar.

Schreiben ist somit gesichert gegen dauerhafte Fehler. Dass beide Versionen nicht lesbar sind, gilt als unerwartet.

einfaches Schreiben: dann (synchron) Atomaritt fr einen Block verschiedene Platten, Kontroller, E/A-Pfade

"weit entfernt"

Block

Slots

Bi

Sj Sk


19

Weitere Prinzipien der Speicherredundanz

Schreiben mit Logging (logged write) Nach dem Lesen wird ein Block Bi mit

seinem alten Inhalt auf einen sicheren Platz L geschrieben.

Nach Aktualisierung wird Bi mit einem einfachen Schreiben auf seinen alten Platz zurck geschrieben (ggf. read-after-write).

Falls das Schreiben erfolgreich war, wird die Kopie von Bi auf L nicht mehr gebraucht.

Prinzip: Spiegelplatten auf Platten- oder Dateibasis synchron oder asynchron gleichzeitig oder zeitlich versetzt

(Schattenprozess) keine Atomaritt automatisch durch

Algorithmus

Bi

Sj Sk


Erkennung fehlerhafter Blcke

Ziel: Unvollstndig geschriebene Blcke erkennen Manahmen der Platten-Hardware

mit Hilfe von Parity-Bits lsst sich herausfinden, ob ein Sektor vollstndig geschrieben wurde oder nicht

ausreichend, wenn ein Block ganz in einem Sektor (hier gleich Slot) gespeichert werden kann

Zustzliche Manahmen der DBS insbesondere fr den Fall, dass ein Block mehrere Sektoren umfasst Konsistenzbits:

- jeweils ein Bit im ersten und letzten Byte eines Blocks (DB2) - beiden Konsistenzbits werden jeweils identische Werte zugewiesen

20


Sequentielles Schreiben

Lsung: Schreiben von Prf-Bits in jeden Sektor

21


Schreiben auer der Reihe

Konsistenzbits: 1

B 1 B 1 B 1 B 1

1

2K

B 1 B 1 B 1 B 1

2K 2K 2K

Konsistenzbits: 1

fr sequentielles Schreiben ok!

1

Prf-Bits:

0

System Benutzer System

Ausgangs- situation

1 0

0 0

1 1

1

1 1 1 1 1

Quelle: [Moh95]


22


Multi-Sektoren-Blcke Fehlerhafter Block wird nur erkannt, wenn beim Schreiben der Sektoren

die durch den Block vorgegebene Reihenfolge eingehalten wird SCSI-Laufwerke nehmen selbstndig zur Leistungsoptimierung eine

Umordnung der Schreibvorgnge auf den Sektoren vor Prfsumme ber den gesamten Block reduziert die Wahrscheinlichkeit

erheblich, ein partielles Schreiben zu bersehen, kann dies jedoch nicht ausschlieen (enorm teuer)

Entsprechend den n Sektoren wird ein Block (logisch) unterteilt; aus jedem dieser Teile wird ein Bit genommen und als Prfbit betrachtet. Diese n Bits werden mit identischen Werten belegt und bei jedem Schreiben invertiert.

- Wie lsst sich erreichen, dass diese n Bits nicht die Benutzerdaten im Block verflschen?


23

bersicht






24

Adressierungseinheiten: Relationen, Sichten, Tupel Hilfsstrukturen: externe Schemabeschreibung, Integrittsregeln Adressierungseinheiten: externe Stze, Sets, Schlssel, Zugriffspfade

Logische Datenstrukturen

Mengenorientierte DB-Schnittstelle Sprachen wie SQL, QBW, etc.

Adressierungseinheiten: externe Stze, Sets, Schlssel, Zugriffspfade Hilfsstrukturen: Zugriffspfaddaten, interne Schemabeschreibung Adressierungseinheiten: interne Stze, B*-Bume, Hash-Tabellen, usw.

Logische Zugriffspfad- strukturen

Satzorientierte DB-Schnittstelle FIND NEXT Satzname, STORE Satzname, etc.

Speicherungs- strukturen

Interne Satzschnittstelle Speichere Satz, Fge Eintrag in B*-Baum ein, etc.

Adressierungseinheiten: Seiten, Segmente

Hilfsstrukturen: Seitentabellen, Blocktabellen, etc.


Seitenzuordnungs- strukturen

DB-Pufferschnittstelle Stelle Seite j bereit, Gib Seite j frei

Adressierungseinheiten: interne Stze, B*-Bume, Hash-Tabellen, usw. Hilfsstrukturen: Freispeicher-Info., Adretab., Seitenindices, usw. Adressierungseinheiten: Seiten, Segmente

Gerteschnittstelle


Hilfsstrukturen: Freispeicher-Info Extent-Tabellen, Dateikataloge, etc.

Adressierungseinheiten: Spuren, Zylinder, Kanle, etc.

Dateischnittstelle Lies Block k, Schreibe Block k

Speicherzuordnungs-strukturen


25

Abbildung von Segmenten und Seiten

Vorteile eines Segmentkonzeptes Ermglichung verzgerter Einbringstrategien selektive Einfhrung von zustzlichen Attributen, z.B. zur Erhhung der Fehlertoleranz Segmente als Einheiten des Sperrens, der Recovery und der Zugriffskontrolle Bei geeigneter Abbildung auf Dateien bleiben Vorteile des Dateikonzeptes erhalten

Zusammen mit der DB-Pufferverwaltung Aufteilung des logischen DB-Adressraumes in Segmente mit sichtbaren Seitengrenzen Bereitstellen und Freigeben von Seiten im DB-Puffer Vorbereitung von E/A-Anforderungen an die Dateiverwaltung Optimierung von Ersetzungsstrategien Untersttzung von Segmenten verschiedenen Typs Neue Aufgaben: Verwaltung von Seiten variabler Lnge und von langen Objekten


26

Beispiel: Operationen an der oberen Schnittstelle

Abbildungsfunktion:

Aufgaben:

Eigenschaften der oberen Schnittstelle Linearer Adressraum, aufgeteilt in Seiten fester Lnge Innerhalb eines Segmentes knnen die Moduln der nchst hheren

Schicht frei adressieren wie in einem virtuellen Adressraum Ein DB-Segment ist nicht-flchtig (wenn nicht explizit anders vereinbart)

Seitenzuordnungsstrukturen Abbildung von Segmenten und Seiten

FIX Pi logische Seitennummer UNFIX Pi

Seitennummer Blocknummer Hauptspeicher Externspeicher

Ersetzen eines alten Blocks Lesen des Blocks mit Seite Pi }

} PAM UPAMDAT, WR, ... PAM UPAMDAT, RD, ...


27

Segmenttypen in einem DBMS

Klassifikation von Segmenttypen

Beispiele fr die Verwendung der Segmenttypen Typ 1: Katalog, Schema-Information, Log, alle gemeinsam benutzbaren DB-Teile Typ 2: Teile der DB, die fr bestimmte Benutzer bzw. Benutzergruppen reserviert sind Typ 3: Lokale Kopien von Teilen der DB (Sichten) fr einzelne Benutzer (Snapshots) Typ 4: Hilfsdateien fr Benutzerprogramme Typ 5: Temporrer Speicher z. B. fr Sortierprogramme

Eigen- schaften

Segment- Typen

Benutzung

Lebens- dauer

ffnen und Schlieen Wiederherstellung im Fehlerfall

Segment- Typ 1

Segment- Typ 2

Segment- Typ 3

Segment- Typ 4

Segment- Typ 5

ffentlich privat privat privat privat

perma- nent

perma- nent

perma- nent

perma- nent

temporr in Transak-

tion automatisch durch

System explizit durch Benutzer

automatisch durch System

explizit durch

Benutzer

kein Wiederherstellungs- mechanismus


Segmenttypen in einem DBMS

In verschiedenen DBS werden bestimmte Segmenttypen auch als Tablespaces bezeichnet. Sie dienen der Speicherung von Tabellen (Relationen) sowie ggf. Indexstrukturen.

In manchen DBS werden Indexstrukturen in eigenen Segmenttypen (sog. Indexspaces) verwaltet.

Die Abbildung von Tablespaces auf mehrere Dateien ist dabei mglich.

28


29

Warum sichtbare Seiten und Segmente?

Explizite Abbildung auf Blcke und Dateien erhht Fehlertoleranz

DB-Puffer mit Satzschnittstelle? lineare Hauptspeicherabbildung:

Probleme unsichtbarer Seitengrenzen spanned record facility benachbarte Seiten mssen im DB-Puffer

benachbart angeordnet sein erhebliche Abbildungs- und Ersetzungsprobleme

Sichtbare Seitengrenzen an der DB-Puffer-Schnittstelle

B A

A

B A A

P i

B j

Seiten

Blcke 1 2 3

Slot A Sektor

A B

P i P i+1 R

Puffer-Adr. + Lnge an Benutzer

P i R

Puffer-Adr. von P i an Benutzer (Ebene der Speicherungsstrukturen)


30

Verfahren zur Seitenzuordnung

Direkte Seitenzuordnung (update-in-place)

Indirekte Seitenzuordnung 1. Lesen vor nderung 2. Schreiben nach nderung 3. Lesen nach nderung

Zustand nach verzgertem Einbringen (mengenorientiert)

Seite i Block i

Schreiben nach nderung

Seite i Block j

Block k

Seitentabelle (neu) i

Seitentabelle (alt) i

1

2

3

Seite i Block j

Block k

Seitentabelle (alt) Seitentabelle (alt) i i

Lesen vor nderung


31

Abbildung von Seitennummer Blocknummer mit Hilfe der Seitentabelle

Prinzip der indirekten Seitenzuordnung

L Eintrge

Seitentabellen fr Segmente

logisch zusammenhngender Speicherbereich, z.B. durch Extent-Tabellen beschrieben

Bittabelle zur Freispeicherverwaltung

Menge von Blcken in einer Datei D

3 1 i 0 0 0 0

V1

2 0 j 0 0 0 0

V2

1 2 3 i j L

D

1 1 1 1 0 1 0 0 0 0 MAP

Segmente S1 S2

P1,1 P1,2 ... P2,1 P2,2 ...


32

direktes Einbringen: Pi Bj; Pi Bj Schreiben = Einbringen DB nach Crash: chaos-konsistent!

verzgertes Einbringen: Pi Bj; Pi Bk; j k Schreiben Einbringen DB nach Crash: aktionskonsistent (operationskonsistent)! geeignete Wahl der Sicherungspunkte SPi : Operationsgrenzen beachten!

Einbringen von Seiten Konsistenz der DB nach Crash

DB-Puffer D B A C A

DB A C {A, B, C, D}

Schreiben

{A, B, C, D}

DB-Puffer D B A C A

DB

A A

{A, B, C, D}

Schreiben Extern- speicher

{A, B, C, D}

SPi

{A, B, C, D}

SPi+1

Einbringen


33

Schattenspeicher-Verfahren: Prinzip

laufende Version

Datei

Bittabellen:

4' 3 k' 0 0 0 0

V10

1 5' i 0 0 0 0

V20

1 1 1 1 1 0 0 0 0 0 MAP1

2 3 j 0 0 0 0

V11

1 0 i 0 0 0 0

V21

Schattenversion

Seitentabellen:

'=Schattenbit

1 2 3 i j l

D

k 4 5

laufende Version

Schattenversion

1 1 1 1 1 1 1 1 0 0 MAP0

1 1 0 0 ...

Master

0

Status der Segmente

Mapswitch

Quelle: [Lor77]


34

Schattenspeicher-Verfahren: Speicherverwaltung

Prinzip der indirekten Seitenzuordnung Zerlegung von Seitentabelle Vk in einzelne Blcke

Auch die Seitentabelle muss im linearen Adressraum untergebracht und auf Blcke abgebildet werden.

Seitentabellen Vk fr Segment Sk

Speicherung von Vk in Blcken fester Lnge


35

Ablauf eines nderungsintervalls Ausgangszustand

Segmente ffnen Seitentabelle kopieren Segmentstatus ndern MASTER schreiben Arbeitskopie von MAPx erstellen

Seiten ndern Finde neuen Block fr Seite aktuelle Seitentabelle anpassen Seite als gendert markieren nderungen der Seite nur im neuen Block

Segmente schlieen Neue Bittabelle MAPy erstellen Genderte Seitentabelle schreiben Genderte Blcke schreiben Segmentstatus ndern MAPSWITCH umschalten MASTER schreiben

Segmente zurcksetzen aktuelle Seitentabelle zurcksetzen Segmentstatus ndern


36

Segment ffnen

Ausgangszustand: Status (i) enthlt den Erffnungszustand fr Segment i

(hier: alle Segmente geschlossen). MAPSWITCH zeigt an, welche der beiden (gleichberechtigten) Tabellen

Map0 und Map1 das aktuelle Verzeichnis belegter Blcke enthlt.

Wenn Segment k fr nderungen geffnet werden soll, sind folgende Schritte auszufhren: kopiere Vk0 nach Vk1 STATUS(k) := 1 Schreibe MASTER in einer ununterbrechbaren Operation aus Lege im Hauptspeicher eine Arbeitskopie CMAP von der aktuellen Bittabelle

MAPx an.


37

Ausgangszustand

laufende Version

Datei

Bittabellen:

2 0 0 j 0 0 0

V10

0 4 0 0 l 0 0

V20

MAP1

V11 V21

Schattenversion

Seitentabellen:

1 2 3 i j l

D

k 4 5

laufende Version

Schattenversion

0 1 0 0 1 1 0 0 0 1 MAP0

0 0 0 0 ...

Master

0

Status der Segmente

Mapswitch


38

Segment ffnen

laufende Version

Datei

Bittabellen:

2 0 0 j 0 0 0

V10

0 4 0 0 l 0 0

V20

MAP1

V11 V21

Schattenversion

Seitentabellen:

1 2 3 i j l

D

k 4 5

laufende Version

Schattenversion

0 1 0 0 1 1 0 0 0 1 MAP0

1 0 0 0 ...

Master

0

Status der Segmente

Mapswitch

0 1 0 0 1 1 0 0 0 1 CMAP

2 0 0 j 0 0 0


39

Seite ndern

Wenn eine Seite Pi erstmalig seit Erffnen des Segments gendert werden soll, sind folgende Aktionen auszufhren: Lies Seite Pi aus Block j = Vk0(i) Finde einen freien Block j in CMAP Vk0(i) = j Markiere Seite Pi in Vk0(i) als gendert Bei weiteren nderungen von Pi wird Block j verwendet.

Anmerkungen: Auf einer Blockmenge D knnen gleichzeitig mehrere Segmente fr den

nderungsbetrieb geffnet sein. Map0, Map1 und CMAP beziehen sich auf die Blockmenge D. CMAP enthlt

fr alle Segmente die mit Schatten- bzw. aktuellen Seiten belegten Blcke. Einer Seite wird nur bei der erstmaligen nderung nach Erffnen des

Segmentes ein neuer Block zugewiesen.


40

Seite ndern

laufende Version

Datei

Bittabellen:

3' 1' 0 j 0 0 0

V10

0 4 0 0 l 0 0

V20

MAP1

V11 V21

Schattenversion

Seitentabellen:

1 2 3 i j l

D

k 4 5

laufende Version

Schattenversion

0 1 0 0 1 1 0 0 0 1 MAP0

1 0 0 0 ...

Master

0

Status der Segmente

Mapswitch

1 1 1 0 1 1 0 0 0 1 CMAP

2 0 0 j 0 0 0


41

nderungsintervall beenden

Beenden eines nderungsintervalls fr Segment k: Erzeuge die Bitliste mit der aktuellen Speicherbelegung in der bisher nicht

genutzten Bittabelle MAPy (neue Blcke belegt, alte freigegeben) Schreibe MAPy Schreibe Vk0 Schreibe alle genderten Blcke Markiere Segment k als geschlossen (STATUS(k) := 0) MAPy wird aktuelle Bittabelle (MAPSWITCH = y) Schreibe MASTER in einer ununterbrechbaren Operation aus


42

nderungsintervall beenden

laufende Version

Datei

Bittabellen:

3 1 0 j 0 0 0

V10

0 4 0 0 l 0 0

V20

MAP1

V11 V21

Schattenversion

Seitentabellen:

1 2 3 i j l

D

k 4 5

MAP0

0 0 0 0 ...

Master

1

Status der Segmente

Mapswitch

1 0 1 0 1 1 0 0 0 1

Schattenversion

laufende Version


43

Segmente zurcksetzen

Zum Zurcksetzen geffneter Segmente muss lediglich Vk1 in Vk0 kopiert und STATUS(k) auf 0 gesetzt werden.


44

Segmente zurcksetzen

laufende Version

Datei

Bittabellen:

2 0 0 j 0 0 0

V10

0 4 0 0 l 0 0

V20

V11 V21

Schattenversion

Seitentabellen:

1 2 3 i j l

D

k 4 5 0 0 0 0 ...

Master

Status der Segmente

MAP1

0 1 0 0 1 1 0 0 0 1 MAP0

0 Mapswitch

laufende Version

Schattenversion


45

Erhaltung der physischen Clusterbildung

Wegen der dynamischen Neuzuordnung von Blcken knnen beim Schattenspeicherverfahren physische Nachbarschaften von logisch zusammengehrigen Seiten bei nderungen i.A. nicht aufrechterhalten werden. Bsp.: Die Seiten A, B, C, D mgen in allen Transaktionen in eben dieser Reihenfolge berhrt

werden:

Die nderung von A A und C C fhrt zu:

Eine Verbesserung kann durch Einteilung der Datei in physische Cluster der Gre p und der Segmente in logische Cluster der Gre l sowie deren gegenseitige Zuordnung erreicht werden. Beispiel mit p=6, l=4:

Bei Plattenspeichern wird ein physisches Cluster i.A. ein Zylinder sein

G E S J F R M A B C D L

G E S C' J F A' R M A B C D L

G E S J F R M A B C D L A' C'


46

Bewertung des Schattenspeicher-Verfahrens

Vorteile Rcksetzen auf letzten konsistenten

Zustand sehr einfach Flexiblere Schreibprotokolle fr Log-

Daten: Pufferung bis zum Umschalten auf einen neuen Zustand mglich

Logisches Logging mglich, da stets operationskonsistenter Zustand verfgbar ist

Bei katastrophalen Fehlern ist die Wahrscheinlichkeit hher, einen brauchbaren Zustand der DB zu rekonstruieren

Nachteile Hilfsstrukturen (MAP und

Seitentabellen Vi) werden so gro, dass Blockzerlegung notwendig wird

Die Seitentabellen Vi belegen etwa 0.1-0.2% der DB-Gre, was bei groen DB's ( n GB) zu einem hohen Anteil von Seitenfehlern im DB-Puffer fr die Zugriffe auf Vi fhren kann

Periodische Sicherungspunkte erzwingen Ausschreiben des gesamten DB-Puffers

Physische Clusterbildung logisch zusammengehriger Seiten wird beeintrchtigt bzw. zerstrt

Zustzlicher Speicherplatz fr die Doppelbelegung; lange Batch- (nderungs-)Programme werden dadurch schlecht untersttzt


47

Zusatzdatei-Verfahren

Idee: Wenn eine Datei fr nderungsbetrieb geffnet wird, wird eine zustzliche, temporre Datei angelegt, in welche whrend des nderungsintervalls alle modifizierten Blcke geschrieben werden. Die eigentliche Datei wird dabei nicht verndert. Am Ende des nderungsintervalls werden alle genderten Blcke aus der temporren in die permanente Datei kopiert. Das Einbringen der nderungen erfolgt also verzgert.

Prinzip: Das wesentliche Problem besteht darin, whrend des nderungsbetriebes fr eine gegebene Seiten-

Nummer zu entscheiden, ob die aktuelle Version in der temporren oder permanenten Datei steht. Nutzung einer Bitliste, die anzeigt, ob eine Seite mglicherweise gendert wurde Hashabbildung erlaubt Begrenzung des Speicherplatzbedarfs

D B

Bitliste

Read/ Write Zusatz- datei

0 1 0 0 1 0 ... 1 ... 1 ... 0

Read-only DB

D B V S

Quelle: [SL76]


48

Bloom-Filter

Wirkungsweise Bitliste B der Lnge M im

Hauptspeicher Signatur des Satzes in B bei seiner

nderung Hash-Funktionen zur Satzabbildung

adressieren x Bits, die in B auf 1 gesetzt werden

Aufsuchen von Satz Si Erzeugen der charakteristischen x Bits

in temporrer Bitliste T AND-Operation von T und B in Erg wenn alle x Bits in Erg gesetzt

VIELLEICHT sonst NEIN

0 0 1 0 0 0 1 0 0 0 0 1 0 0 0

1. Write Si = 123 h(Si)

2. Write Sj = 456 h(Sj)

3. Read Sk = 345 h(Sk)

M

B

T

B

Wenn (B AND T) = T dann Antwort VIELLEICHT !

1 0 1 0 0 0 1 1 0 0 0 1 0 1 0

1 0 1 0 0 0 1 0 0 0 0 0 0 0 0


49

Zusammenfassung

Speicherzuordnungsstrukturen erfordern effizientes Dateikonzept viele Dateien variierender, nicht statisch festgelegter Gre Wachstum und Schrumpfung erforderlich permanente und temporre Dateien

Empfohlene Datei-Eigenschaften: direkter und sequentieller Blockzugriff Blockgre pro Datei definierbar Blockzuordnung ber dynamische Extents Dynamische Blockzuordnung (bei UNIX als mehrstufiger Baum) untauglich fr groe Dateien

Segmentkonzept erlaubt die Realisierung zustzlicher Attribute fr die DB-Verarbeitung (Recovery, Clusterbildung fr Relationen usw.)

Zweistufige Abbildung von Segment/Seite auf Datei/Block und diese auf Slots der Magnetplatte erlaubt Einfhrung von

Abbildungsredundanz durch verzgertes Einbringen

Verzgerte Einbringstrategien sind teurer als direkte, besitzen jedoch implizite Fehlertoleranz sie belasten den Normalbetrieb zugunsten der Recovery

Direkte Einbringstrategie (update-in-place) einfach zu implementieren keine Zusatzkosten zur Ausfhrungszeit fr die Seitenzuordnung Fehlertoleranz nur durch explizite Logging- u. Recovery-Funktionen


50

Ergnzende Literatur zu diesem Kapitel

[GR93] J. Gray, A. Reuter: Transaction Processing Concepts and Techniques, Morgan Kaufmann, 1993.

[PWB07] Eduardo Pinheiro, Wolf-Dietrich Weber, Luiz Andre Barroso: Failure Trends in a Large Disk Drive Population. In: Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST07), February 2007.

[Lor77] R. A. Lorie: Physical Integrity in a Large Segmented Database. In: ACM TODS, Vol. 2, No. 1, 1977.

[Moh95] C. Mohan: Disk read-write optimizations and data integrity in transaction systems using write-ahead logging. In: Proc. of the 11th International Conference on Data Engineering, Taipei, Taiwan, March 6-10, 1995.

[SL76] D. G. Severance, G. M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. In: ACM TODS, Vol. 1, No. 3, 1976.

Datenbanken und InformationssystemebersichtSlide Number 3Allgemeine Aufgaben der ExternspeicherverwaltungSpeicherhierarchieModell einer zweistufigen SpeicherhierarchiebersichtAbbildung von Dateien und Blcken DateikonzeptRealisierung eines DateisystemsDateiorganisationsformenBlockzuordnungsverfahrenBlockzuordnung durch Extent-TabellenbersichtManahmen zur FehlertoleranzLesen und Schreiben von BlckenSicheres Schreiben (read-after-write)Stabiles Schreiben (duplexed write)Weitere Prinzipien der SpeicherredundanzErkennung fehlerhafter BlckeErkennung fehlerhafter BlckeErkennung fehlerhafter BlckebersichtSlide Number 24Abbildung von Segmenten und SeitenSeitenzuordnungsstrukturen Abbildung von Segmenten und SeitenSegmenttypen in einem DBMSSegmenttypen in einem DBMSWarum sichtbare Seiten und Segmente?Verfahren zur SeitenzuordnungPrinzip der indirekten SeitenzuordnungEinbringen von Seiten Konsistenz der DB nach CrashSchattenspeicher-Verfahren: PrinzipSchattenspeicher-Verfahren:SpeicherverwaltungAblauf eines nderungsintervallsSegment ffnenAusgangszustandSegment ffnenSeite ndernSeite ndernnderungsintervall beendennderungsintervall beendenSegmente zurcksetzenSegmente zurcksetzenErhaltung der physischen ClusterbildungBewertung des Schattenspeicher-VerfahrensZusatzdatei-VerfahrenBloom-FilterZusammenfassungErgnzende Literatur zu diesem Kapitel

Documents

chapter03.pdf