Upload
miki-bundesmaca
View
14
Download
2
Embed Size (px)
Citation preview
Anwendersoftware (AS) Anwendersoftware (AS)
Datenbanken und Informationssysteme
Kapitel 4: Pufferverwaltung
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.
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
2
Pufferverwaltung
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
Adressierungseinheiten: Blcke, Dateien
Hilfsstrukturen: Freispeicher-Info Extent-Tabellen, Dateikataloge, etc.
Adressierungseinheiten: Spuren, Zylinder, Kanle, etc.
Dateischnittstelle Lies Block k, Schreibe Block k
Speicherzuordnungs-strukturen
3
Pufferverwaltung
Rolle der DB-Pufferverwaltung in einem DBS
Transaktionsprogramme, die auf die Datenbank zugreifen
FINDE PERSONAL WHERE ANR = K55
Plattenzugriffe
physische Seitenreferenzen
logische Seitenreferenzen
Transaktionsverwaltung und Zugriffspfadroutinen
DB-Pufferverwaltung DB-Puffer
Externspeicherverwaltung
FIXi: Stelle Seite Pi bereit UNFIXi: Gib Seite Pi frei
Lies Seite Pi Schreibe Seite Pi
Datenbanksystem (vereinfacht)
TA1 TAn TA2 ...
4
Pufferverwaltung
Seitenreferenzstrings
Jede Datenanforderung ist eine logische Seitenreferenz. Seitenreferenzstring (SRS)
R = mit ri = ( Ti, Di, Si) Ti zugreifende Transaktion Di referenzierte DB-Partition Si referenzierte DB-Seite
Aufgabe der DB-Pufferverwaltung: Minimierung der physischen Seitenreferenzen
Bestimmung von Ausschnitten aus R bezglich bestimmter Transaktionen, Transaktions-Typen und DB-Partitionen sinnvoll zur Analyse des Referenzverhaltens
Wie kann Referenzstring-Information verwendet werden fr Charakterisierung des Referenzverhaltens? Bestimmung von Lokalitt und Sequentialitt? Untersttzung einer effektiven Seitenersetzung?
5
Pufferverwaltung
Vergleich mit BS-Funktionen
Implementierung Ersetzungsalgorithmen im DB-Puffer in
Software implementiert Seitenersetzung in Adressrumen bei
virtuellem Speicher ist Hardware-gesttzt
Seitenreferenz vs. Adressierung nach einem FIX-Aufruf kann eine DB-Seite
mehrfach bis zum UNFIX referenziert werden
unterschiedliches Seitenreferenzverhalten andere Ersetzungsverfahren?
Wichtige Aspekte fr den Datenbankpuffer Bewertung der verfgbaren BS-Funktionalitt effizienter Pufferzugriff Zugriff auf Dateipuffer ist teuer (supervisor call)
DB-spezifische Referenzmuster sollen untersttzt werden BS-Ersetzungsverfahren sind z.B. nicht auf zyklisch sequentielle oder baumartige Zugriffsfolgen abgestimmt
In DBMS ist aufgrund von Seiteninhalten oder Referenzmustern eine Voraussage des Referenzverhaltens (z. B. bei Tabellen-Scans) mglich; Prefetching erzielt in solchen Fllen eine enorme Leistungssteigerung
Normale Dateisysteme bieten keine geeignete Schnittstelle fr Prefetching
Selektives Ausschreiben von Seiten zu bestimmten Zeitpunkten (z. B. fr Logging)
In existierenden Dateisystemen nicht immer mglich
DBMS muss eigene Pufferverwaltung realisieren
6
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
7
Pufferverwaltung
Eigenschaften von Referenzstrings
Typische Referenzmuster in DBS Sequentielle Suche:
Bsp.: Durchsuchen ganzer Satztypen (Relationen)
Hierarchische Pfade: Bsp.: Suchen mit Hilfe
von B*-Bumen
Zyklische Pfade: Bsp.: Abarbeiten von
Sets ((1:n)-Beziehungen), Suchen in DBTT-/Datenseiten
Si Sl Sk Sj
8
Pufferverwaltung
Sequentialitt
SRS weisen typischerweise Phasen von Sequentialitt und Lokalitt auf Sequentielle Zugriffsfolge (SZ):
Zwei aufeinander folgende Referenzen ri und ri+1 gehren zu einer sequentiellen Zugriffsfolge, falls Si+1 - Si = 0 oder Si+1 - Si = 1
d. h., aufeinander folgende Zugriffe referenzieren gleiche oder benachbarte DB-Seiten
Algorithmus Seitenreferenzstring wird vollstndig durchmustert; alternativ kann
die Folge der ankommenden Referenzen analysiert werden Solange obige Bedingung erfllt ist, gehren alle aufeinander folgenden
Referenzen zu einer SZ, sonst beginnt eine neue SZ
9
Pufferverwaltung
Sequentialitt
Lnge einer sequentiellen Zugriffsfolge (LSZ): LSZ ist die Anzahl der verschiedenen in SZ referenzierten Seiten Bsp.:
Referenzstring A A B B D E E F F H enthlt drei SZ: (A A B B)1 mit LSZ(1) = 2 (D E E F F)2 mit LSZ(2) = 3 (H)3 mit LSZ(3) = 1
Ma fr Sequentialitt: Die kumulative Verteilung der SZ-Lngen LSZ(i) wird berechnet
S(x) = Pr(SZ-Lnge
Pufferverwaltung
Lokalitt
Erhhte Wiederbenutzungswahrscheinlichkeit fr zuletzt referenzierte Seiten (gradueller Begriff)
Grundlegende Voraussetzung fr effektive DB-Pufferverwaltung (Seitenersetzung) Einsatz von Speicherhierarchien
Wie kann man Lokalitt messen? Working-Set-Modell LRU-Stacktiefenverteilung
11
Pufferverwaltung
Working-Set-Modell
Working-Set W(t,s): Seiten, die von der betrachteten Transaktion innerhalb der letzten s Referenzen (Fenstergre) bezogen auf Zeitpunkt t angesprochen wurden.
Working-Set-Gre w (t,s) = |W(t,s)|
Working sets W (t1, 8) = {A, B, C} W (t2, 8) = {A, B, C, D, E, F, G, H} w (t1,8) = 3 w (t2,8) = 8
Aktuelle Lokalitt: Mittlere Lokalitt: (n = Lnge des Referenzstrings)
sstwstAL ),(),( =
A
s = 8
s = 8
t1 t2
B A C A B B C D E F A G H Referenzstring
n
stALsL
n
t== 1
),()(
12
Pufferverwaltung
LRU-Stacktiefenverteilung
Wie lsst sich Lokalitt charakterisieren? LRU-Stacktiefenverteilung liefert Ma fr die Lokalitt (prziser als Working-Set-Ansatz) LRU-Stack enthlt alle bereits referenzierten Seiten in der Reihenfolge ihres Zugriffsalters
Bestimmung der Stacktiefenverteilung: pro Stackposition wird Zhler gefhrt Rereferenz einer Seite fhrt zur Zhlererhhung fr die jeweilige Stackposition
Zhlerwerte entsprechen der Wiederbenutzungshufigkeit Fr LRU-Seitenersetzung kann aus der Stacktiefenverteilung fr eine bestimmte Puffergre
unmittelbar die Trefferrate (bzw. Fehlseitenrate) bestimmt werden
Stacktiefe
Wieder- benutzungs- wahrscheinlichkeit (%)
Lokalitt
wahlfreie Zugriffsverteilung
13
Pufferverwaltung
Beispiel: Ermittlung der Stacktiefenverteilung
Referenzstring:
LRU-Stack
Stacktiefenverteilung
A B A C A A A B B B C D E B E
1 A A B A C A A A B B B C D E B E
2 B B A B A C C C A A A B C D E B
3 C C C C B B B B C C C A B C D D
4 D D D D D D D D D D D D A B C C
5 E E E E E E E E E E E E E A A A
012345
1 2 3 4 5
Anz
ahl
Stacktiefe
14
Pufferverwaltung
Reale LRU-Stacktiefenverteilungen
1 5 10 15 20 25 30 35 40 45 50 55
5
10
15
LRU-Stacktiefen-Verteilung von Mix40 Lnge des Strings: 130366 logische Referenzen Anzahl verschiedener Seiten im String: 3553
LRU-Stacktiefe
%
60 65 70 75 80
30
85 90 95 100
Rel
atie
Hf
igke
it de
r Sta
cktie
fe
1 5 10 15 20 25 30 35 40 45 50 55
5
10
15
LRU-Stacktiefen-Verteilung von Mix50 Lnge des Strings: 99975 logische Referenzen Anzahl verschiedener Seiten im String: 5245
LRU-Stacktiefe
%
Rel
atie
Hf
igke
it de
r Sta
cktie
fe
Quelle: [EH84] 15
Pufferverwaltung
Relative Referenzmatrix (DOA-Last)
TT1
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 Total
TT2 TT3 TT4 TT5 TT6 TT7 TT8 TT9 TT10 TT11 TT12
6.4
9.1 7.5
0.0 3.1 2.4 1.3 0.3 0.0 0.3
Total
3.5 6.9 1.3 3.4 4.1 2.5
30.3 26.6 11.0 9.4 8.3 4.9 4.1 3.3 1.4 0.6 0.0 0.0 0.0 100.0
2.3 1.4 0.1 0.9 0.1
3.3 0.4 2.8 0.3 0.4 0.6
0.2 0.0 0.3
2.6 0.0 6.8
5.0 0.0 2.6
0.0 0.7
0.0
0.9 0.5 0.2
1.0
0.4 0.8 0.7 0.6 0.5 0.9
0.1
0.1
0.1 1.0 0.1 0.4 0.0 0.3
1.1
0.2
0.3 1.1
0.2 0.4 0.0
22.3 20.3 15.6 11.6 8.2 7.4
2.9 2.6 1.8 1.1 0.1
2.6 2.3 0.1
0.0
0.0
0.0
0.0
0.0
partition size (%) 31.3 6.3 8.3 17.8 1.0 20.8 2.6 7.3 2.6 1.3 0.8 0.0 0.0 100.0
6.2
% refe- renced 11.1 16.6 8.0 2.5 18.1 1.5 9.5 4.4 5.2 2.7 0.2 13.5 5.0 6.9
ca. 17 500 Transaktionen, 1 Million Seitenreferenzen auf ca. 66 000 verschiedene Seiten
16
Pufferverwaltung
Referenzdichte-Kurven Referenzdichte-Kurven
-30 -60 -90
-120 -150 -180 -210 -240 -270 -300 -330 -360 -390 -420 -450 -480 -510 -540 -570 -600 -630 -660 -690 -720 -750 -780 -810 -840 -870 -900 -930 -960 -990
-1020
10 20 30 40 50 % 60 70 80 90 100 %
TA1
TA2
TA3
TA4
TA5
TA6
= Daten und Indexstrukturen: 93,8 % = Adressumsetztabellen: 6,1 % = Freispeicher-Verwaltung: 0,1 %
Relative Hufigkeit der Seitentypen im Beispiel
17
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
18
Pufferverwaltung
Speicherzuteilung im DB-Puffer
global
(ein gemeinsamer Pufferbereich) lokal /
partitionierte Pufferbereiche
statisch dynamisch
angepasste Partitionen
gleichfrmige Partitionen
Speicherzuteilung im DB-Puffer
Partitionierungsmglichkeiten: eigener Pufferbereich pro Transaktion TA-Typ-bezogene Pufferbereiche Seitentyp-bezogene Pufferbereiche DB-(Partitions)spezifische
Pufferbereiche
19
Pufferverwaltung
Dynamische Pufferallokation: Working-Set-Ansatz (WS)
Pro Pufferpartition P soll Working-Set im Puffer bleiben;
Seiten, die nicht zum Working-Set gehren, knnen ersetzt werden Bei Fehlseitenbedingung muss Working-Set bekannt sein,
um Ersetzungskandidat zu bestimmen Fenstergre pro Partition: s (P) Referenzzhler pro Partition: RZ (P) letzter Referenzzeitpunkt fr Seite i: LRZ (P, i) ersetzbar sind solche Seiten, fr die gilt: RZ (P) LRZ (P, i) > s (P)
Fenstergre kritischer Parameter Thrashing-Gefahr
Referenz- string
P1:
P2:
A
B
C
E F F
A A
D
A
E
G H A
20
Pufferverwaltung
Dynamische Pufferallokation: Page-Fault-Frequency-Ansatz (PFF)
Vorgabe einer Soll-Fehlseitenrate F Bei Fehlseitenbedingung wird aktuelle Fehlseitenrate FA(P) ausgewertet:
gilt FA(P)>F wird Partition um eine Seite erweitert gilt FA(P)
Pufferverwaltung
Direktes, sequentielles Durchsuchen der Pufferrahmen sehr hoher Suchaufwand Gefahr vieler Paging-Fehler bei virtuellem Speicher
Nutzung von Hilfsstrukturen (Eintrag pro Pufferrahmen) unsortierte oder sortierte Tabelle Tabelle mit verketteten Eintrgen
- geringere nderungskosten - Anordnung in LRU-Reihenfolge mglich
Suchbume (z.B. AVL-, m-Weg-Bume) Hash-Tabelle mit berlaufketten
- beste Lsung
Suche im DB-Puffer
1
k
H
h (Pi)=k
Pi B3 Pk B1 - Pj B2
22
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
23
Pufferverwaltung
Seitenersetzungsverfahren
Klassifikation:
Grundannahme bei Ersetzungsverfahren:
preplanning
Programmanalyse, Vorabuntersuchung des Datenbedarfs
demand fetching
physische Daten- strukturierung, Clusterbildung, Verarbeitungswissen
keine Vorausaktionen
groe Fehlrate, ungenaue Obermengen
datenmodellbezogen (hierarchisch), spekulative Entscheidungen
Lokalittserhaltung im DB-Puffer
prefetching
Verfahrensklassen
Referenzen jngste Vergangenheit nchste Zukunft
A B A C A B C A B B C D
Referenzverhalten hnlich 24
Pufferverwaltung
Referenzverhalten und Ersetzungsverfahren
Referenzverhalten in DBS typischerweise hohe Lokalitt:
Optimierung durch Ersetzungsverfahren
manchmal Sequentialitt oder zufllige Arbeitslast (RANDOM-Referenzen)
Grenzflle des Referenzverhaltens und der Ersetzungsverfahren zeigen Optimierungsmglichkeiten auf.
Kombinationen:
Prinzipielle Zusammenhnge, welche die Fehlseitenrate bestimmen
R/R ~ R/OPT
L/OPT L/R
D 1
100%
N
Fehlseiten- rate
D = DB-Gre in Blcken N = # Rahmen im DB-Puffer
Referenz
Random Lokalitt
Ersetzung
Random R/R L/R
OPT R/OPT L/OPT
25
Pufferverwaltung
Behandlung genderter Seiten im DB-Puffer
Ersetzung einer genderten Seite erfordert ihr vorheriges (synchrones) Zurckschreiben in die DB Antwortzeitverschlechterung
Abhngigkeit von der gewhlten Ausschreibstrategie:
FORCE NOFORCE
Alle nderungen einer Transaktion werden sptestens beim EOT in die DB zurckgeschrieben (write-through).
Kein Durchschreiben der nderungen bei EOT (verzgertes Ausschreiben, deferred write-back).
+ i.A. stets ungenderte Seiten zur Ersetzung vorhanden
+ Seite kann mehrfach gendert werden, bevor ein Ausschreiben erfolgt (geringerer E/A-Overhead, bessere Antwortzeiten)
+ vereinfachte Recovery (nach Rechnerausfall sind alle nderungen beendeter TA bereits in die DB eingebracht)
+ Vorausschauendes (asynchrones) Ausschreiben genderter Seiten erlaubt auch bei NOFORCE, vorwiegend ungenderte Seiten zu ersetzen
- hoher E/A-Overhead - aufwndigere Recovery nach Rechnerausfall
- starke Antwortzeiterhhung fr nderungstransaktionen
Synchrone DB-Schreibvorgnge lassen sich weitgehend vermeiden
26
Pufferverwaltung
Kriterien fr die Auswahl der zu ersetzenden Pufferseite
Verfahren Alter letzte Referenz
Referenz- hufigkeit
andere Kriterien
OPT - - - Vorauswissen
RANDOM - - - ---
LFU - - x
FIFO x - -
LRU x x -
CLOCK x x -
GCLOCK x x x
LRD(V1) x - x
LRD(V2) x - x
27
Pufferverwaltung
Least Frequently Used (LFU)
Pro Seite wird ein Referenzzhler (RZ) gefhrt (statt Bit) Initialisierung mit 1 bei der
Einlagerung der Seite Erhhung um 1 bei jeder Referenz
Fehlseitenbedingung: Ersetzung der Seite mit der
geringsten Referenzhufigkeit
Alter einer Seitenreferenz wird nicht bercksichtigt!
RZ Seite
2 A
4 B
1 C
3 D
3 E
6 F
1 G
3 H
t Seitenreferenzen fr A Seitenreferenzen fr B
Ersetzungskandidaten: C, G
Ersetzungskandidat: B
28
Pufferverwaltung
First-In First-Out (FIFO)
Die lteste Seite im DB-Puffer wird ersetzt Referenzen whrend des Pufferaufenthaltes werden nicht bercksichtigt Nur fr strikt sequentielles Referenzierungsverhalten geeignet
G
H F
E
D
C
B
A
Referenzstring: ABACADAEAFAGAHAI
Ersetzungskandidat: A
29
Pufferverwaltung
Least Recently Used (LRU)
Beispiel (Puffergre 4): Referenz der Seite C
Unterscheidung zwischen Least Recently Referenced und Least Recently Unfixed
Referenz der Seite E
LRU-Stack
D
B
A
C
D
B
A
C
D
B
A
C
E
B
A
C
FIX FIX UNFIX UNFIX A B B A
t
30
Pufferverwaltung
CLOCK (Second Chance)
Erweiterung von FIFO Pro Seite wird ein Referenzbit gefhrt
wird bei jeder Referenz gesetzt Fehlseitenbedingung:
zyklische Suche bis zur ersten Seite mit zurckgesetztem Bit
Zurcksetzen des Referenzbits fr alle besuchten Seiten mit gesetztem Bit
Annhernde Bercksichtigung des letzten Referenzierungszeitpunkts
0 F
0 G
1 H
0 A
0 B
0 C
1 E
0 D
0 F
0 G
1 H
1 A
1 B
1 C
1 E
0 D
Ersetzungskandidat: D
31
Pufferverwaltung
GCLOCK (Generalized CLOCK)
Pro Seite wird ein Referenzzhler (RZ) gefhrt (statt Bit) wird bei Erstreferenz auf Ei gesetzt wird bei jeder weiteren Referenz um Wi
erhht
Fehlseitenbedingung: zyklische Suche bis zur ersten
Seite mit RZ=0 Dekrementierung des Zhlers
fr alle besuchten Seiten mit RZ>0
Verfahrensparameter: Ei: Initialwerte fr Referenzzhler Wahl des Dekrementes Wi: Zhler-Inkrementierung bei
erneuter Referenz Vergabe von seitentyp- oder
seitenspezifischen Gewichten
0 F
0 G
5 H
0 A
1 B
2 C
0 E
1 D
0 F
0 G
5 H
1 A
2 B
3 C
1 E
2 D
Ersetzungskandidat: F 32
RZ
Pufferverwaltung
Least Reference Density (LRD): Variante 1
Algorithmus Wenn eine Seite ersetzt werden
muss, wird die Referenzdichte aller Seiten im DB-Puffer bestimmt
Referenzdichte = Referenzhufigkeit in einem bestimmten Referenzintervall
Ersetzungskandidat ist Seite mit geringster Referenzdichte
Variante 1: Referenzintervall entspricht Alter einer Seite
Berechnung der Referenzdichte: Globaler Zhler (GZ):
Gesamtanzahl aller Referenzen Referenzzhler (RZ) Einlagerungszeitpunkt (EZ):
GZ-Wert beim Einlesen der Seite
Referenzdichte:
Beispiel:
)()()(
jEZGZjRZjRD
=
33
t
A A A B C D D E F F F F
1 10
RZ EZ RD
A 3 1 3/(13-1) = 1/4
B 1 4 1/(13-4) = 1/9
C 1 5 1/8
D 2 6 2/7
E 1 8 1/5
F 4 9 1
Ersetzungskandidat
Pufferverwaltung
Least Reference Density (LRD): Variante 2
Variante 2: konstante Intervallgre Knstliches Altern von Seiten:
ltere Referenzen werden bei der Bestimmung der Referenzdichte geringer bewertet
Periodisches Reduzieren der Referenzzhler, um Gewicht frher Referenzen zu reduzieren
Reduzierung von RZ durch Division oder Subtraktion: oder
)11(1
)()( >= KK
iRZiRZ
>
=)03,02(332)(2)(
)(KKsonstK
KKiRZfallsKiRZiRZ
34
t
A A A B C D D E F F F F
t1 t2 t3
RZ(A) 3 2 2 1 1 0
RZ(B) 1 0 0 0 0 0
RZ(C) 0 0 1 0 0 0
RZ(D) 0 0 2 1 1 0
RZ(E) 0 0 1 0 1 0
RZ(F) 0 0 0 0 4 3
mit K2 = 1 K3 = 0
Pufferverwaltung
Simulationsergebnisse
Quelle: [EH84] 35
Pufferverwaltung
Simulationsergebnisse
Quelle: [EH84] 36
Pufferverwaltung
Simulationsergebnisse
Quelle: [EH84] 37
Pufferverwaltung
Simulationsergebnisse
Quelle: [EH84] 38
Pufferverwaltung
Simulationsergebnisse
Charakteristika der DB, der Transaktionslast und der logischen Seitenreferenzstrings
39
Pufferverwaltung
Seitenersetzung bei virtuellem Speicher
Page Fault: P1 in SP virtuell, aber nicht in SP real (HSP)
Database Fault: P2 nicht in SP virtuell, Seitenrahmen R2 fr P2 jedoch in SP real
Double Page Fault: P3 nicht in SP virtuell, ausgewhlter Seitenrahmen R3 fr P3 nicht in SP real
DB SP virtuell
SP real
Haupt- speicher
virtueller Speicher
Magnetplatte Magnetplatte H S P
P2 P1
P3
R2
R3
40
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
41
Pufferverwaltung
Probleme bei LRU-hnlichen Verfahren
Internes Thrashing: Zyklisches Referenzieren (Loop) einer Menge von Seiten
mit #Seiten > #Rahmen Auswirkung: Hufigkeit der Seitenersetzung steigt stark an
Externes Thrashing: T1: sehr schnelle Seitenanforderungen (wahlfrei oder sequentiell) Ti: langsame Seitenanforderungen fr eine Seitenmenge (#Seiten <
#Rahmen), die zyklisch referenziert wird Auswirkung: Seiten der Ti werden auch bei hoher Referenzlokalitt verdrngt
WS-Modell: Es wird versucht, w(t,s) Rahmen zu allokieren Bei sequentiellem Scan htte ein Rahmen gengt
42
Pufferverwaltung
Hot-Set-Modell
Ausnutzung von Kontextwissen bei mengenorientierten Anforderungen Verbesserung in relationalen DBS mglich
Prinzipieller Verlauf der Fehlseitenrate (FSR) bei der Verarbeitung von Hot Sets
Hot Set: Menge der Seiten im Referenzzyklus
Hot Point: abrupte Vernderung in der FSR, z. B. verursacht durch Schleife beim Verbund
FSR
# Rahmen
Hot Points
P1 P2
43
Pufferverwaltung
Hot Set Size (HSS): grter Hot Point kleiner als der verfgbare DB-Puffer
Anfrage-Optimierer berechnet HSS fr die verschiedenen Zugriffsplne (Abschtzung der #Rahmen)
Beispiel:
Anwendungscharakteristika: Bercksichtigung der HSS in den Gesamtkosten Auswahl abhngig von verfgbarer DB-Puffergre Bindung zur Laufzeit mglich
Hot-Set-Modell
Kosteneinheiten/103
# Rahmen 10 20
5
15
30
50
SELECT * FROM ABT X, PERS Y WHERE X.ANR = Y.ANR
AND ...
PERS in uerer Schleife
ABT in uerer Schleife Index-Scan fr beide Relationen
44
Pufferverwaltung
Ersetzungverfahren Einbezug von Kontextwissen
Zugriffsplne durch Anfrage-Optimierer Zugriffscharakteristik/Menge der referenzierten Seiten kann bei der Erstellung
von Plnen vorausgesagt/abgeschtzt werden Zugriffsmuster enthlt immer Zyklen/Loops (mindestens Kontrollseite
Datenseite, nested loop join etc.) Kostenvoranschlge fr Zugriffsplne knnen verfgbare Rahmen
bercksichtigen Bei Ausfhrung wird die Mindestrahmenzahl der Pufferverwaltung mitgeteilt
45
Pufferverwaltung
Priorittsgesteuerte Seitenersetzung
Bevorzugung bestimmter Transaktionstypen/DB-Partitionen vielfach wnschenswert (z.B. um Benachteiligungen durch sehr lange TA oder sequentielle Zugriffe zu vermeiden)
Bercksichtigung von Prioritten bei der Pufferverwaltung Verfahren PRIORITY-LRU:
pro Priorittsstufe eigene dynamische Pufferpartition LRU-Kette pro Partition Prioritt einer Seite bestimmt durch DB-Partition bzw. durch (maximale)
Prioritt referenzierender Transaktionen ersetzt wird Seite aus der Partition mit der geringsten Prioritt.
Ausnahme: die w zuletzt referenzierten Seiten sollen (unabhngig von ihrer Prioritt) nicht ersetzt werden
Kompromiss zwischen Prioritts- und absolutem LRU-Kriterium mglich
Quelle: [JC+90] 46
Pufferverwaltung
Priorittsgesteuerte Seitenersetzung
Seitenersetzung soll zum Referenzzeitpunkt RZ = 100 erfolgen
w = 30 zuletzt referenzierten Seiten drfen nicht ersetzt werden
LRZ = Zeitpunkt der letzten Referenz einer Seite
mglicheErsetzungskandidaten
S18 76
S60 99
Seiten-ID
LRZ
S10 93
S16 90
S17 56
S11 71
S45 65
S55 82
Prioritt 3 (hoch)
Prioritt 2
Prioritt 1
47
Pufferverwaltung
bersicht
Allgemeine Charakteristika Ablauf des Pufferzugriffs logische und physische Seitenreferenzen
Eigenschaften von DB-Referenzstrings Seitenreferenzstrings Lokalitt, Sequentialitt LRU-Stacktiefenverteilung Referenzdichte-Kurven
Speicherzuteilung und Suche im Puffer Seitenersetzungsverfahren
Klassifikation von Ersetzungsverfahren LRU, FIFO, CLOCK, GCLOCK, LRD ... Leistungsanalyse von Ersetzungsverfahren Seitenersetzung bei virtuellem Speicher
Ersetzungsverfahren - Einbezug von Kontextwissen Hot Set-Modell Priorittsgesteuerte Seitenersetzung
Pufferverwaltung bei Seiten variabler Gre zustzliche Anforderungen VAR-PAGE-LRU
48
Pufferverwaltung
Pufferverwaltung bei Seiten variabler Gre
Seitengre: keine beliebigen Seitengren
(Fragmentierung, Abbildung auf Externspeicher)
Seitenlnge (SL) als Vielfaches eines Einheitsrasters (Transporteinheit, Rahmengre im Puffer)
Beispiel: SL = 1, 2, 4, ..., 2n Rahmengre (n 8)
Trennung von Seite und Rahmen (Rastergre)
Schnittstellenforderung: Zusammenhngende Speicherung der Seite im Puffer
Buddy-System (BS-Algorithmus) (Verwaltung variabler Bereiche:
frei(f) / belegt(b) festes Raster, hierarchischer
Vergabemechanismus Suche nur in freien Bereichen
(belegte Bereiche knnen nicht verschoben werden)
Zusammenfassung von freien Neffen aufwendig
b f
b
f
b f
b b
2n-2
2n-1
2n
21
20
b
49
Pufferverwaltung
Seiten variabler Gre - Zustzliche Anforderungen
Zustnde von Seiten/Rahmen frei: keine Seite vorhanden unfixed: Seite ist ersetzbar/verschiebbar fixed: Seite muss Pufferadresse behalten
Vermeidung von Seitenersetzungen Umlagern von Seiten mit Unfix-Vermerk und hoher Wiederbenutzungswahrscheinlichkeit
Suche nach bestem Ersetzungskandidaten Was heit bester Ersetzungskandidat?
Wiederbenutzungs-Wahrscheinlichkeit: Anzahl der Referenzen, Alter, letzte Referenz einer Seite Fragmentierung/Lckenbenutzung: first fit, best fit Rahmeninhalte: Anteil ersetzbarer und freier Rahmen Anzahl der zu ersetzenden Seiten zur Platzbeschaffung fr eine neue Seite
Kombination von Ersetzung und Umlagern von Seiten sehr komplexe Entscheidungssituation
Alternative: Partitionierung des DB-Puffers fr Seiten gleicher Gre (und anwendungsabhngige Ersetzungsverfahren)
50
Pufferverwaltung
Seiten variabler Gre - Pufferverwaltung
Ziele: Maximierung der Pufferbelegung (Speicherplatzoptimierung) Minimierung der E/A durch Bercksichtigung von Lokalitt im Referenzverhalten
Vorschlag fr einen Algorithmus: VAR-PAGE-LRU Neue Aufgabenstellung:
Caching und spekulatives Prefetching von Dokumenten in Speicherhierarchien (Tertirspeicher)
Quellen: [Sik88][KW98]
Probleme:
- Ersetzung mehrerer Seiten zur Erfllung einer neuen Seitenanforderungen
- Puffer-Fragmentierung
51
Pufferverwaltung
Zusammenfassung Referenzmuster in DBS sind Mischformen
sequentielle, zyklische, wahlfreie Zugriff Lokalitt innerhalb und zwischen Transaktionen bekannte Seiten mit hoher Referenzdichte Erkennen von Scan-basierter Verarbeitung
Ohne Lokalitt ist jede Optimierung der Seitenersetzung sinnlos (~ RANDOM) Suche im Puffer durch Hash-Verfahren Speicherzuteilung:
global alle Pufferrahmen fr alle Transaktionen (Einfachheit, Stabilitt, ...) lokal Sonderbehandlung bestimmter TAs/Anfragen/ DB-Bereiche
Behandlung genderter Seiten: NOFORCE, asynchrones Ausschreiben Seitenersetzungsverfahren
Prefetching und Pipelining mit Wechselpuffer zu genaue Verfahren sind schwierig einzustellen ( instabil) Nutzung mehrerer Kriterien: Alter, letzte Referenz, Referenzhufigkeit Double-Paging sollte vermieden werden
Erweiterte Ersetzungsverfahren Nutzung von Zugriffsinformationen des Anfrage-Optimierers Hot Set Model Einsatz vieler Puffer zur Separierung von Lasten verschiedenen Typs, optimiert fr spezifische Datentypen
52
Pufferverwaltung
Literatur zu diesem Kapitel
[EH84] W. Effelsberg, T. Hrder: Principles of Database Buffer Management. In: ACM TODS Vol. 9, No. 4, 1984.
[JC+90] R. Jauhari, M.J. Carey, M. Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. In: Proc. 16th VLDB Conf., 1990.
[OO+93] E. J. ONeil, P. E. ONeil, G. Weikum: The LRU-K Page Replacement Algorithm for Database Disk Buffering. In: Proc. ACM SIGMOD Conf. Washington. D.C., 1993.
[Sik88] A. Sikeler: VAR-PAGE-LRUA Buffer Replacement Algorithm Supporting Different Page Sizes. In: Proc. Extending Database Technology, 1988.
[KW98] A. Kraiss, G. Weikum: Integrated Document Caching and Prefetching in Storage Hierarchies Based on Markov-Chain Predictions. VLDB Journal, 1998.
53
Datenbanken und InformationssystemebersichtSlide Number 3Rolle der DB-Pufferverwaltung in einem DBSSeitenreferenzstringsVergleich mit BS-FunktionenbersichtEigenschaften von ReferenzstringsSequentialittSequentialittLokalittWorking-Set-ModellLRU-StacktiefenverteilungBeispiel: Ermittlung der StacktiefenverteilungReale LRU-StacktiefenverteilungenRelative Referenzmatrix (DOA-Last)Referenzdichte-KurvenbersichtSpeicherzuteilung im DB-PufferDynamische Pufferallokation:Working-Set-Ansatz (WS)Dynamische Pufferallokation:Page-Fault-Frequency-Ansatz (PFF)Suche im DB-PufferbersichtSeitenersetzungsverfahrenReferenzverhalten und ErsetzungsverfahrenBehandlung genderter Seiten im DB-PufferKriterien fr die Auswahlder zu ersetzenden PufferseiteLeast Frequently Used (LFU)First-In First-Out (FIFO)Least Recently Used (LRU)CLOCK (Second Chance)GCLOCK (Generalized CLOCK)Least Reference Density (LRD): Variante 1Least Reference Density (LRD): Variante 2SimulationsergebnisseSimulationsergebnisseSimulationsergebnisseSimulationsergebnisseSimulationsergebnisseSeitenersetzung bei virtuellem SpeicherbersichtProbleme bei LRU-hnlichen VerfahrenHot-Set-ModellHot-Set-ModellErsetzungverfahren Einbezug von KontextwissenPriorittsgesteuerte SeitenersetzungPriorittsgesteuerte SeitenersetzungbersichtPufferverwaltung bei Seiten variabler GreSeiten variabler Gre - Zustzliche AnforderungenSeiten variabler Gre - PufferverwaltungZusammenfassungLiteratur zu diesem Kapitel