Upravljanje z diskom in pomnilnikom...9.marec 2010

Upravljanje z diskom in pomnilnikom
 Za upravljanje z diskom skrbi najnižji nivo v SUPB arhitekturi – upravljalec z diskom (Disk Space Manager).
 Lastnosti:
– Podpira koncept “strani”;
– Izvaja ukaze za dodeljevanje in sproščanje prostora na disku ter branje in pisanje strani.
– Velikost strani je enaka velikosti bloka na disku. Strani se shranjujejo kot bloki. Branje ali pisanje strani se lahko izvede v okviru ene I/O operacije.
– Skrije podrobnosti strojne opreme (in OS); ostalim komponentam SUPB omogoči, da vidijo podatke kot zbirko strani.

 Upravljalec z diskom vzdržuje stanje zasedenih in prostih blokov na disku.

 Obstajata dva načina:
– Vzdrževanje seznama prostih blokov (kazalec na prvi blok seznama se shrani na znano lokacijo na disku),
– Vzdrževanje bitne mape (za vsak blok je v bitni mapi bit, ki označuje, ali je blok zaseden ali ne),

 Uporaba datotečnega sistema za upravljanje s prostorom:
– Upravljalec z diskom lahko uporablja datoteke operacijskega sistema  celotna PB se nahaja v eni ali več datotekah.
– V tem primeru je zadolžen za upravljanje prostora v teh datotekah.
– Veliko PB ne uporablja datotečnega sistema, ampak svoj lastni sistem za upravljanje z diskom (popolnoma svoj ali pa razširja funkcionalnost datotečnega sistema OS). Razlogi:
 PRAKTIČNI: bazo lahko uporabimo na več platformah,
 TEHNIČNI: pri 32 bitnem naslavljanju se pojavi omejitev v velikosti datoteke.



Upravljalec medpomnilnika

 Upravljalec medpomnilnika je programska plast, ki skrbi za prenašanje ustreznih strani v pomnilnik.
– upravlja z razpoložljivim pomnilnikom (buffer pool).
– višjim plastem SUPB-ja zagotavlja strani, ki jih te rabijo za svoje delo.
– V medpomnilnik prenese tisto stran, ki jo višja plast zahteva.
– Višja plast SUPB-ja upravljalca medpomnilnika obvešča o straneh, ki se sprostijo oziroma se jim spremeni vsebina.
– Obstajajo različne strategije, ki določijo, katere strani se v medpomnilniku zamenjajo.
 Za vsak okvir v medpomnilniku se hranita dve spremenljivki:
– pin_count: kolikokrat je bila stran v okvirju zahtevana, vendar ne sproščena (število trenutnih uporabnikov strani).
– dirty: logična vrednost, ki označuje, ali je bila stran spremenjena ali ne.

 Začetno stanje okvirja:
– pin_count = 0
– dirty = off







. Ko se pojavi zahteva po določeni strani, upravljalec z medpomnilnikom izvede naslednje:
– če se stran nahaja v kakšnem od okvirjev, vrne pomnilniški naslov okvirja in poveča pin_count za 1,
– sicer izvede naslednje:
 izbere okvir za zamenjavo (z uporabo strategije za zamenjavo) in poveča pin_count.
 če je dirty bit okvirja, ki bo zamenjan, postavljen na “on”, se stran prepiše na disk.
 stran se prenese iz diska v okvir, ki je določen za zamenjavo.



 Dodatna pravila:
– Če se zahtevana stran ne nahaja v medpomnilniku in če so vsi okvirji zasedeni, se za zamenjavo izbere okvir, katerega pin_count=0. V primeru več takih okvirjev se izmed njih izbere okvir po določeni strategiji.
– Če v medpomnilniku ni nobene strani, ki bi imela pin_count=0 in hkrati iskane strani ni v medpomnilniku, potem upravljalec medpomnilnika čaka, da se kakšna stran sprosti.
– V praksi to pomeni, da je transakcija, ki zahteva tako stran, lahko razveljavljena.
 Nevarnost: če neko stran zahteva več neodvisnih transakcij, lahko pride do konfliktnih sprememb...
 Reševanje z zaklepanjem:
– Obstaja protokol zaklepanja, za katerega skrbijo višje ravni SUPB (posebej upravljalec transakcij).
– Vsaka transakcija lahko pridobi deljeno (shared) ali ekskluzivno zaklepanje preden lahko stran bere ali spreminja.
Ekskluzivno zaklepanje iste strani ne sme biti odobreno dvem transakcijam istočasno!
 Strategija zamenjave strani v medpomnilniku močno vpliva na učinkovitost SUPB.

. Obstajajo različne strategije, ki so primerne za različne situacije.

 Nekatere strategije:

– LRU – least recently used
 Vrsta kazalcev na okvirje s pin_count = 0
 Ko stran postane kandidat za zamenjavo (pin_count = 0), okvir strani dodamo na konec vrste
 Za zamenjavo izberemo stran iz okvirja, na katerega kaže prvi kazalec v vrsti



– Clock replacement
 Različica LRU z manjšo časovno kompleksnostjo
 Okvirji so navidez organizirani v cikel (kot številke na uri)
 Vsak okvir ima dva podatka: reference_bit in pin_count.
 Reference_bit se postavi na ON, ko pin_count postane 0.
 Za zamenjavo najprej preverimo stran, na katero trenutno kaže posebna spremenljivka.
 Če okvir ne izberemo za zamenjavo, se kazalec pomakne naprej. To traja, dokler ne najdemo okvirja za zamenjavo.
 Izbira okvirja:
– Če pin_count > 0  okvir ne izberemo
– Če reference_bit = ON  okvirja ne izberemo, reference_bit postavimo na OFF.
– Če pin_count = 0 AND reference_bit = OFF  okvir izberemo!

.Primerjava z upravljanjem navideznega pomnilnika OS:
– obstaja podobnost med navideznim pomnilnikom operacijskega sistema in upravljanjem s pomnilnikom pri SUPB.
– Cilj obeh: zagotoviti dostop do več podatkov, kot jih lahko spravimo v pomnilnik. Strani iz diska se prenašajo v pomnilnik po potrebi, nadomeščajo strani, ki se jih v pomnilniku ne rabi več.

 Zakaj ne uporabimo navideznega pomnilnika v OS?
– SUPB lahko bolj natančno predvidi zaporedje (vzorce dostopanja) kot tipičen OS.
– SUPB rabi več nadzora nad stranmi, ki se zapisujejo na disk, kot ga omogoča tipičen OS.
– Najpomembneje: upravljalec medpomnilnika uporablja strategijo vnaprejšnjega branja (prefetching), ki na osnovi predvidevanja naslednjih zahtev v naprej prenese strani v pomnilnik.

Organizacija datotek in indeksiranje
Osnovni koncepti…
 Podatkovna baza je na sekundarnem pomnilniku organizirana v eno ali več datotek (file)
 Vsaka datoteka zajema enega ali več zapisov (record).
 Zapis sestavljajo polja (field).
 Zapisi običajno označujejo entitete, polja pa njihove atribute.

 Uporabnik zahteva zapis “A10” od SUPB:
– SUPB naredi preslikavo logičnega zapisa v fizični;
– Poišče fizični zapis in ga prepiše v primarni pomnilnik oziroma v medpomnilnik;

 Med fizičnim in logičnim zapisom ne velja vedno preslikava 1:1
– Fizični zapis je enota prenosa med diskom in primarnim pomnilnikom.
– Lahko zajema tudi več logičnih zapisov. Podobno je lahko tudi večji logični zapis zapisan čez več fizičnih zapisov.
 Fizični zapis ustreza konceptu, ki smo ga obravnavali kot stran.

Datotečna organizacija…
 Datotečna organizacija pove, kako so podatki v datoteki fizično urejeni v zapise in strani na sekundarnem pomnilniku.

 Osnovne vrste datotečnih organizacij:
– Kopica ali neurejena datoteka: zapisi so na disku shranjeni v nedefiniranem vrstnem redu.
– Zaporedno urejena datoteka: zapisi so urejeni po vrednosti določenega polja.
– Razpršena datoteka: zapisi so razpršeni z uporabo hash funkcije.
 Za delo z zapisi v datotekah obstajajo različne tehnike ali metode dostopa (access methods).
 Metode dostopa določajo korake, ki jih je potrebno izvesti za zapis ali iskanje nekega zapisa v datoteki.
 Metode dostopa so odvisne od datotečne organizacije.

Neurejene datoteke…
 Imenujemo tudi kopica (heap).
 Najenostavnejša datotečna organizacija:
– Zapisi so shranjeni v istem vrstnem redu, kot so bili dodani
– Nov zapis dodan na zadnjo stran datoteke
– Če ni dovolj prostora, se doda nova stran
 Dobra lastnost:
– Zelo učinkovito dodajanje zapisov
 Uporabljamo za masovni vnos.
– Ni potrebno računati, na katero stran bomo zapis vstavili.

Neurejene datoteke
 Slabosti:
– Neučinkovitost iskanja. Uporabiti moramo linearno iskanje (zapisi so neurejeni)
– Neizkoriščenost prostora: pri brisanju zapisa moramo najti stran z zapisom, zbrisati zapis ter stran shrani nazaj na disk. Spraznjen prostor na strani ostane neizkoriščen. Neurejene datoteke je potrebno občasno reorganizirati!


Urejene datoteke…
 Zapisi v datotekah so lahko urejeni po enem ali več poljih  urejena ali zaporedna datoteka.
 Za iskanje po poljih, po katerih je datoteka urejena, uporabimo binarno iskanje.
 Primer:
SELECT * FROM artikel
WHERE sifra = ‘BX1’

Urejene datoteke…
 Prednosti:
– Učinkovitost iskanja

 Problem
– Dodajanje in brisanje zapisov  potrebno vzdrževati vrstni red
– Če želimo nek zapis dodati, moramo poiskati stran, kamor bi zapis sodil glede na vrstni red. Če stran vsebuje dovolj praznega prostora, jo preuredimo in zapišemo nazaj na disk, sicer moramo nekaj zapisov premakniti na naslednjo stran itd.
 Dodajanje zapisa na začetek velike datoteke je posebej problematično.
 Možna rešitev: uporaba dodatne neurejene datoteke (overflow ali transakction file):
– Nov zapis je dodan v neurejeno datoteko
– Neurejena datoteka se periodično prepiše v urejeno
– Pri iskanju zapisa se najprej pogleda urejena datoteka. Če zapisa ne najdemo, se linearno pregleda še neurejena.

Razpršene datoteke…
 V razpršenih ali hash datotekah so zapisi razpršeni v skladu s hash funkcijo.
 Hash funkcija za vsak zapis izračuna naslov strani (naslov bloka na disku), kamor zapis sodi glede na vrednost določenega polja (hash polje).
fhash(P) = naslov strani;
P = vrednost hash polja.

 Iskanje zapisa na strani se izvede v primarnem pomnilniku. Za večino zapisov moramo prebrati le eno stran.
 Za hash funkcijo izberemo operacijo, ki zagotavlja enakomerno porazdeljenost zapisov po datoteki.
 Najpopularnejša hash funkcija je ostanek pri deljenju (MOD) z določenim številom (n)




 Primer:
– Vrednost polja, ki nastopa kot argument hash funkcije je 132
– n = 24
– 132/24 = 5, ostanek je 12  zapis se zapiše na 12 stran.

 Problem razpršenih datotek:
– Zaloga vrednosti hash polja navadno večja od števila naslovov, ki jih lahko vrne hash funkcija.
– Vsak naslov ustreza določeni strani (bucket), ki ima mesta za več zapisov.
– Znotraj strani so zapisi urejeni po vrsti, kot so bili vstavljeni.
– Ko hash funkcija za nek zapis vrne naslov strani, ki je polna, pride do kolizije.

 Za reševanje problemov z istim naslovnim prostorom so na voljo različne tehnike
– Odprto naslavljanje (open addressing)
– Nepovezane dodatne strani (unchained overflow)
– Povezane dodatne strani (chained overflow)
– Večkratno razprševanje (multiple hashing)
 Odprto naslavljanje
– Zapisovanje: če pride do kolizije, poiščemo prvo stran, ki ima še kakšno prosto mesto. Ko pridemo do zadnje strani, gremo na začetek.
– Iskanje: enako kot pri zapisovanju. S to razliko, da če naletimo na prazno mesto preden na iskani zapis, privzamemo, da zapisa ni v datoteki.

 Primer:
– dodajamo zapis SL41
– Hash funkcija MOD 3
– SL41 je razvrščen za stran 2
– Ker stran 2 nimam praznih mest, iščemo prvo stran s še prosim mestom. Rezultat: stran 1.

 Nepovezane dodatne strani:
– Namesto iskanja prostega mesta za primere kolizije vzdržujemo seznam dodatnih strani
– Rešitev na videz ne ponuja bistvenih izboljšav
– V resnici daje boljše rezultate  število kolizij je manjše (z odprtim naslavljanjem rešimo le trenutno kolizijo. Obenem odpremo možnosti za nove kolizije.)
 Povezane dodatne strani:
– Podobno kot nepovezane dodatne strani, le da so v tem primeru dodatne strani povezane z osnovnimi
– Vsaka stran ima dodatno polje, ki pove, ali je prišlo pri tej strani do kolizije ali ne. V polju je naslov dodatnega polja, kamor so razvrščeni zapisi, pri katerih pride do kolizije. Vrednost 0 pomeni, da kolizije ni bilo.
 Večkratna razpršitev:
– Eden od načinov reševanja kolizij je večkratno razprševanje.
– Če pride do kolizije, se uporabi drugačna hash funkcija, ki vrača drugačen naslov.
– Dodatna hash funkcija je navadno takšna, da razvršča v dodati prostor.

 Razprševanje v splošnem
– Prinaša dobre rezultate pri iskanju (ob uporabi ene izmed tehnik reševanja kolizij).
– Spreminjanje zapisov je tudi enostavno, razen v primerih, ko spremenimo hash polje.
–
Dinamične razpršene datoteke…
 Obravnavane hash tehnike so vse statične:
– ko zapisu določimo naslov, se ta ne spremeni, če se ne spremeni vrednost hash polja .
 Problem:
– Datoteka postane premajhna in zato vzamemo večjo. Določiti moramo novo hash funkcijo in vse zapise iz stare datoteke premestiti (z uporabo novega razprševanja) v novo datoteko.
 Alternativa:
– Uporaba dinamičnih razpršenih datotek: datoteko dinamično spreminjamo (večamo) po potrebi.
– Obstajajo številne tehnike realizacije dinamičnih razpršenih datotek.
Dinamične razpršene datoteke…
 Razširljivo razprševanje (extendible hashing)
– Strani kreiramo po potrebi. V začetku gredo zapisi v prvo stran.
– Ko je stran polna, jo razdelimo glede na prvih i bitov, kjer velja 0 ≤ i < b
– Izbranih i bitov določa naslov oziroma ofset v naslovni tabeli strani oziroma imeniku (BAT - Bucket Address Table). Vrednost i se spreminja z velikostjo datoteke
– V glavi imenika je zapisana trenutna vrednost i (globina) skupaj z 2i kazalci.
– Vsaka stran ima tudi lokalno globino, ki pove, pri katerem i dobimo naslov te strani.

Omejitve tehnike razprševanja
 Učinkovitost razpršenih datotek za iskanje je odvisna od hash polja.

 Uporaba razpršenih datotek ni primerna za:
– Iskanje po vzorcu
– Iskanje po nizu vrednosti
– Iskanje po polju, ki ni hash polje

Indeksi in indeksiranje…
 Indeks je podatkovna struktura, ki SUPB-ju omogoča hitrejše lociranje zapisov v datoteki.


 Analogija z indeksom knjige
– Indeks knjige vsebuje ključne besede (urejene po abecedi) ter za vsako pove, na kateri strani ali straneh se ključna beseda pojavlja.
– Indeks omogoča, da nam ni potrebno prelistati cele knjige, ko želimo najti določeno vsebino.

 Terminologija:
– Podatkovna datoteka: datoteka s podatki (imenujemo tudi osnovna datoteka)
– Indeksna datoteka: datoteka z indeksom. Indeks sestavlja iskalni ključ ter kazalec na zapis v podatkovni datoteki.
– Iskalni ključ: sestavljen iz vrednosti polj, po katerih je datoteka indeksirana. Imenujemo tudi indeksno polje.

 Indeksi gruče (clustered index)
– Z indeksom gruče označujemo indekse, ki temeljijo na poljih, po katerih je obenem urejena tudi podatkovna datoteka.

 Primarni in sekundarni indeksi
– Primarni indeks (Primary index): indeks po poljih, ki vsebujejo primarni ključ. Vsak iskalni ključ kaže natanko na en zapis v podatkovni datoteki. Datoteka je po ključu urejena.
– Sekundarni indeks (Secondary key): vsak indeks, ki ne temelji na poljih, ki bi vsebovala primarni ključ.
 Vsaka datoteka ima lahko:
– primarni indeks ali indeks gruče ter -več sekundarnih indeksov!
 Redki in gosti indeksi:
– Redki indeks (sparse index): indeksna datoteka vsebuje kazalce, ki kažejo le na določene zapise v podatkovni datoteki. Navadno vsebuje po en zapis za vsako stran v podatkovni datoteki;
– Gosti indeks (dense index): indeksna datoteka vsebuje kazalce na vse zapise v podatkovni datoteki.

 Indeksi s sestavljenim iskalnim ključem (composite key ali concatenated key):
– Indeksi po več kot enem polju
– Uporabljamo za kombinacije polj, po katerih pogosto iščemo

Drevesno indeksiranje…
 Drevesno indeksiranje učinkovito pri:
– intervalnem iskanju ter
– dodajanju in brisanju (za razliko od urejenih datotek).
 Iskanje po enakosti boljše pri hash indeksiranju.

 Pogledali bomo dve indeksni strukturi, ki temeljita na drevesni organizaciji:
– ISAM (Indexed Sequential Access Method):
– B+ drevesna struktura

 ISAM:
– statičen indeks,
– učinkovit v primerih, ko se podatkovna datoteka ne spreminja pogosto,
– ni učinkovit pri datotekah, ki se hitro povečujejo ali krčijo.
 B+ drevo:
– dinamična struktura; se zelo dobro prilagaja spremembam v podatkovni datoteki,
– najbolj uporabljana vrsta indeksa; omogoča hitro iskanje zapisov, intervalno iskanje in se učinkovito prilagaja spremembam v podatkovni datoteki.

ISAM…
 Primer:
– Imamo datoteko oseb, urejeno po polju “starost”.
– Če želimo najti vse osebe starejše od 30 let, moramo najprej najti prvo (s pomočjo binarnega iskanja), ki je starejša od 30 in od te naprej prebrati preostale zapise datoteke.
 Možnost za pohitritev iskanja:
– Izdelamo dodatno datoteko, s po enim zapisom za vsako stran v podatkovni datoteki in jo uredimo po polju “starost”.
– Vsak zapis v dodatni datoteki vsebuje par

– Vsak ključ v indeksni datoteki predstavlja mejnik vsebine, na katero kažeta levi in desni kazalec  vsaka stran v indeksu vsebuje en kazalec več, kot je ključev.
– Binarno iskanje se izvede nad indeksno datoteko, ki je manjša od osnovne datoteke => hitrejše iskanje.
 Velikost indeksne datoteke poraja idejo o ISAM indeksu:
– Zakaj ne bi ponovili koraka in zgradili še eno dodatno datoteko, ki bi imela za vsako indeksno stran en zapis, tako da bi velikost končnega indeksa znašala samo eno stran?


 ISAM indeks sestavljajo dve vrsti strani:
– listi: strani s podatki (in dodatne strani - overflow) in
– vozlišča: nepodatkovne strani.
 Nekatere ISAM strukture temeljijo na skrbno oblikovanih straneh, ki ustrezajo fizični organizaciji datotek na sekundarnem mediju (IBM).
 ISAM je v celoti statična struktura (z izjemo dodatnih strani)
 Gradnja ISAM indeksa:
– Ko se indeksna datoteka kreira, so vse strani v listih urejene zaporedno in po iskalnem ključu.
– Vstavljanje novih podatkov lahko zahteva kreiranje dodatnih strani (če je stran, kamor podatek sodi, polna).

 ISAM podpira operacije iskanje, brisanje in vstavljanje.
 Iskanje:
– Začnemo v korenu
– Če vrednost, ki jo iščemo manjša ali enaka ključu korena, sledimo levemu kazalcu, sicer desnemu.
– Ponavljamo, dokler ne pridemo do listov drevesa. Če podatka, ki ga iščemo, ni v listu, iščemo v dodatnih straneh.
 Dodajanje
– Stran v listih, kamor zapis sodi, poiščemo enako kot pri iskanju
– Zapis dodamo na prvo prosto mesto
 Brisanje:
– Zapis, ki ga brišemo, poiščemo enako kot pri iskanju
 Če je zapis na dodatni strani in gre za zadnji zapis na strani, stran zbrišemo.
 Če je zapis na primarni strani in gre za zadnji zapis na strani, pustimo stran prazno. Služi kot mesto za kasnejšo rabo.
– Lahko se zgodi, da se iskalni ključ, ki nastopa v indeksnem delu, ne pojavi v listih.
 Primer izračuna stroškov iskanja zapisa v ISAM strukturi:
– Število I/O operacij = logFN, kjer je N število primarnih strani listov, F število otrok vsake indeksne strani.
– Število I/O operacij pri binarnem iskanju po urejeni datoteki je log2N. Pri iskanju po eno-nivojskem indeksu: log2(N/F)
– Primer: datoteka z 1.000.000 zapisi, 10 zapisov na stran v listih in 100 zapisov v indeksnih straneh
 Strošek branja cele datoteke: 100.000
 Strošek binarnega iskanja po urejeni datoteki: 17
 Strošek binarnega iskanja po eno-nivojskem indeksu: 10
 Strošek binarnega iskanja po ISAM strukturi: 3 (brez dodatnih strani)

 Problem ISAM strukture se pokaže, ko naraste število dodatnih strani
– Podatki v dodatnih straneh so načeloma lahko urejeni, običajno pa niso (zaradi učinkovitosti dodajanja zapisov)
– Problem omilimo tako, da v začetku, ko izgradimo indeks, pustimo nekaj praznega prostora v straneh listov.