NDBI007
Organizace a zpracov´ an´ı dat I ´ loˇ U ziˇ stˇ e, sloˇ zen´ a ´ uloˇ ziˇ stˇ e, z´ aznamy, soubory
ˇ emliˇ RNDr. Michal Z cka, Ph.D.
Hierarchie pamˇ et´ı poˇ c´ıtaˇ ce V poˇ c´ıtaˇ c´ıch najdeme mnoho r˚ uzn´ ych pamˇ et´ı: + Registry − Vyrovn´ avac´ı pamˇ et’ procesoru – pamˇ et’ova cache + Operaˇ cn´ı pamˇ et’ − Vyrovn´ avac´ı pamˇ et’ pro disky – diskov´ a cache + Sekund´ an´ı pamˇ et’ (disky)
C´ıl – zjednoduˇ senˇ e Chceme se nauˇ cit pracovat se sekund´ arn´ı pamˇ et´ı efektivnˇ e. V´ıme, ˇ ze mnoh´ e z algoritm˚ u zn´ am´ ych z pr´ ace v operaˇ cn´ı pamˇ eti je nepouˇ ziteln´ ych, ale my uˇ z si porad´ıme – nauˇ c´ıme se postupy jin´ e.
Zpracov´ an´ı dat ³
³³
³³
³³
³ ³³
³ ³³
PP P
PP PP
PP
PP
PP P
³ )³
q P
interpretace dat
organizace dat na vnˇ ejˇ s´ıch pamˇ etech pro efektivn´ı zpracov´ an´ı
uˇ zivatelem ?
?
konceptu´ aln´ı model dotazovac´ı jazyky
techniky organizace dat ve formˇ e soubor˚ u PP
PP
³
PP
PP
PP
PP
³ ³³ ³³
³³
PP
P q
³ ³³ ³³
³³ )
vrsty struktur + zobrazen´ı mezi nimi
Hardware Magnetick´ e p´ asky Optick´ e disky Jukeboxy Magnetick´ e disky Flash pamˇ eti RAID-y
Magnetick´ a p´ aska • umoˇ zˇ nuje sekvenˇ cn´ı ˇ cten´ı i rychl´ e pˇ rev´ıjen´ı • existuj´ı speci´ aln´ı zaˇ r´ızen´ı pro kontrolu kvality z´ aznamu • aplikace: – z´ alohov´ an´ı – proudov´ a data – vz´ acnˇ eji pˇ ristupovan´ a rozs´ ahl´ a data (spolu s optick´ ymi disky)
Magnetick´ e p´ asky – parametry Pˇ r´ıklady syst´ em˚ u liˇ s´ıc´ıch se sv´ ymi parametry: low-end (USB) • kapacita 36 (72) GB • z´ alohov´ an´ı 180MB/min (21,6 GB/hod) • hled´ an´ı 60s lepˇ s´ı (SCSI) • kapacita 400 (1040) GB • rychlost ˇ cten´ı/z´ apisu 24 (62) MB/s tj. 86,4 (224,6) GB/hod
Magnetick´ y disk – pohled z boku osa
povrchy
hlavy
Hardware – probl´ emy Pohybliv´ a m´ edia mohou podl´ ehat r˚ uzn´ ym deformac´ım, a tak je tˇ reba pr˚ ubˇ eˇ znˇ e ”dolad’ovat” nastaven´ı ˇ ctec´ıch/z´ aznamov´ ych ˇ c´ ast´ı. Tato m´ edia mohou b´ yt i mechanicky poˇ skozena; mus´ı se to umˇ et zdetekovat, pˇ r´ıpadnˇ e (v pˇ r´ıpadˇ e menˇ s´ıho poˇ skozen´ı) i opravit.
Bloky – moˇ zn´ a implementace znaˇ cka zaˇ c´ atek bloku ˇ c´ıslo bloku na stopˇ e/p´ asce znaˇ cka zaˇ c´ atku dat vlastn´ı data znaˇ cka konce dat pomocn´ e k´ ody na detekeci chyb a pˇ r´ıpadn´ e opravy znaˇ cka konce bloku Samotn´ e bloky maj´ı mezi sebou mezery – jednak aby se stihl blok zpracovat, neˇ z se bude ˇ c´ıst dalˇ s´ı, jednak aby se pˇ r´ıpadn´ ym nepˇ resn´ ym um´ıstˇ en´ım bloku nepˇ repsal blok sousedn´ı
Diskov´ a pole – RAID • Redundant Array of Inexpensive Disks • Slouˇ z´ı ke zv´ yˇ sen´ı kapacity, rychlosti, nebo bezpeˇ cnosti disk˚ u. • Navenek se chov´ a jako jedin´ a diskov´ a jednotka s pozmˇ enˇ en´ ymi vlastnostmi. • Existuje cel´ aˇ rada r˚ uzn´ ych uspoˇ r´ ad´ an´ı. Kaˇ zd´ e z nich je vhodn´ e pro jinou aplikaci.
RAID 0 – schema '
?
&
$
'
%
&
A1 &
%
B2 %
&
C1
%
C2 %
&
D1 &
%
&
B1
&
$
A2 %
&
?
%
D2 %
&
%
RAID 0 – Striping • Data rozloˇ zena na v´ıce disk˚ u • Nen´ı to klasick´ y RAID – nedoch´ az´ı k redundanci • Pˇ ri v´ ypadku jedin´ eho disku m˚ uˇ zeme pˇ rij´ıt o veˇ sker´ a data • Zvyˇ suje v´ ykon jak pro ˇ cten´ı, tak pro z´ apis • Podporov´ ano i velmi levn´ ymi ˇ radiˇ ci
RAID 1 – Zrcadlen´ı '
?
&
$
'
%
&
A &
%
B %
&
C
%
C %
&
D &
%
&
B
&
$
A %
&
?
%
D %
&
%
RAID 1 – Mirroring • Disky instalov´ any ve dvojic´ıch. • Vˇ zdy se zapisuje na oba disky v p´ aru. ˇ ten´ı se ralizuje tam, kde to jde rychleji. • C • Pˇ ri v´ ypadku jedin´ eho disku jej staˇ c´ı vymˇ enit a nakop´ırovat na nˇ ej data z jeho partnera. • M˚ uˇ ze ”pˇ reˇ z´ıt” i v´ ypadek aˇ z n disk˚ u z 2n – za pˇ redpokladu, ˇ ze z kaˇ zd´ e dvojice vypadne nejv´ yˇ se jeden.
RAID 0+1, 1+0 • Kombinace princip˚ u RAID 0 a 1 pro alespoˇ n 4 disky • 0+1: stripe + mirror ... levn´ e souborov´ e syst´ emy • 1+0: mirror + stripe ... datab´ aze • podpora jiˇ z u relativnˇ e levn´ ych a jednoduch´ ych ˇ radiˇ c˚ u (0,1,0+1) – dostupn´ e na mnoha z´ akladn´ıch desk´ ach
RAID 3 • Pracuje po bitech – disky mus´ı b´ yt synchronizov´ any • Jeden z disk˚ u je vyhrazen pro paritu • Rychl´ e I/O pro sekvenˇ cn´ı data • Neum´ı z´ aroveˇ nˇ c´ıst i zapisovat • Syst´ em je odoln´ y proti selh´ an´ı jednoho disku – data je moˇ zn´ e dopoˇ c´ıtat
RAID 4 • Data jsou zapisov´ ana po bloc´ıch na jednotliv´ e disky • Jeden z disk˚ u je vyhrazen pro paritu • Rychl´ e I/O pro sekvenˇ cn´ı data • Neum´ı z´ aroveˇ nˇ c´ıst i zapisovat • Syst´ em je odoln´ y proti selh´ an´ı jednoho disku – data je moˇ zn´ e dopoˇ c´ıtat ´ zk´ • U ym hrdlem je paritn´ı disk – pomal´ y z´ apis
RAID 5 • Parita zapisov´ ana postupnˇ e na r˚ uzn´ e disky • Pouˇ ziteln´ y od 3 disk˚ u v´ yˇ se • Rozumn´ y kompromis mezi bezpeˇ cnost´ı dat, kapacitou a v´ ykonem • vyˇ zaduje sloˇ zitˇ ekˇ s´ı elektroniku (b´ yv´ a na ˇ radiˇ c´ıch s procesorem a vˇ etˇ s´ı pamˇ et´ı)
RAID 6 • Odoln´ y proti v´ ypadku aˇ z dvou disk˚ u • Zv´ yˇ sen´ a redundance • Menˇ s´ı vyuˇ zit´ı kapacity • Potˇ rebuje sloˇ zitˇ ejˇ s´ı ˇ radiˇ c • Vhodn´ e pro mission-critical aplikace
Optick´ e disky • CD, DVD, blue-ray, ... • Informace uchov´ av´ ana prostˇ rednictv´ım rozd´ıln´ e odrazivosti svˇ etla • Lisovan´ e – velk´ e s´ erie disk˚ u se stejn´ ym obsahem → velmi spolehliv´ e • Modifikovateln´ e m´ edium (R, RW, RAM) – mal´ e s´ erie + z´ alohov´ an´ı + pˇ renos dat (pouze RW a RAM)
Optick´ e disky (2) • U levn´ ych m´ edi´ı zat´ım relativnˇ e mal´ e kapacity (650MB, 4,7GB). • U m´ edi´ı s ”rozumnou kapacitou” (15GB, 25GB) zas nevyhovuje cena. • RW m´ edia nejsou urˇ cena pro velk´ y poˇ cet pˇ reps´ an´ı → prostor pro DVD-RAM. • DVD-RAM zat´ım m´ alo rozˇ s´ıˇ rena a pomˇ ernˇ e drah´ a a pomal´ a – vyuˇ z´ıv´ ana sp´ıˇ se pro multim´ edia neˇ z pro data.
Jukeboxy
• P´ asky i optick´ e disky mohou m´ıt menˇ s´ı kapacitu, neˇ z je tˇ reba – poˇ zadovan´ a data jsou pak uloˇ zena na v´ıce m´ edi´ıch
• Jednoduch´ a m´ edia je moˇ zn´ e automaticky vymˇ eˇ novat (staˇ c´ı jedna ˇ ci nˇ ekolik m´ alo mechanik + v´ ymˇ enn´ y mechanismus + prostor na des´ıtky ˇ ci stovky m´ edi´ı)
Jukeboxy (2)
• Poskytuj´ı obrovskou ´ uloˇ znou kapacitu s pomal´ ym pˇ r´ıstupem (sekundy) • Vˇ etˇ sinou vyuˇ zity jako terci´ aln´ı pamˇ et’ – jsou tam ukl´ ad´ ana data, co se nepotˇ rebuj´ı pˇ r´ıliˇ sˇ casto, ale pˇ resto by mˇ ela b´ yt dostupn´ a • Z´ alohov´ an´ı dat ze sekund´ arn´ıch pamˇ et´ı
Syst´ emy v´ ymˇ enn´ ych disk˚ u • Zaˇ r´ızen´ı umoˇ zˇ nuj´ıc´ı bezobsluˇ zn´ y pˇ r´ıstup k v´ıce CD nebo DVD disk˚ um • Nˇ ekdy vˇ cetnˇ e podpory z´ apisu • Nˇ ekolik r˚ uzn´ ych forem: – mechanika na v´ıce CD – stojan s mnoha mechanikami po jednom CD – mechanika s pˇ r´ıdavn´ ym zaˇ r´ızen´ım na v´ ymˇ enu CD (jukebox)
Parametry Jukeboxu • Aˇ z stovky CD/DVD (tj. aˇ z 5,5 TB)
• M˚ uˇ ze obsahovat i v´ıce mechanik
• Doba v´ ymˇ eny disk˚ u 2,5 – 10 s
• Nˇ ekdy i moˇ znost ot´ aˇ cet m´ edia (u oboustrann´ ych)
P´ askov´ e v´ ymˇ enn´ e syst´ emy
• Obdobnˇ e jako u CD/DVD existuj´ı i bezobsluˇ zn´ e syst´ emy s jednou ˇ ci nˇ ekolika m´ alo mechanikami a mnoha p´ askami
• Kapacita aˇ z des´ıtky TB
Flash pamˇ eti, SSD • Velmi rychl´ e • Drah´ e (vˇ etˇ s´ı kapacity i 100.000,-) ˇ asto jen omezen´ • C y poˇ cet pˇ reps´ an´ı • Dnes bˇ eˇ znˇ e dod´ avan´ e kapacity v jednotk´ ach GB (”kl´ıˇ cenky”) nebo des´ıtk´ ach GB (”SSD – solid-state disky”); pˇ r´ıpadnˇ e TB • K maxim´ aln´ımu vyuˇ zit´ı vyˇ zaduj´ı jin´ y pˇ r´ıstup neˇ z klasick´ e disky
Pˇ ripojov´ an´ı vnˇ ejˇ s´ıch pamˇ et´ı
• Disky pˇ ripojov´ any vˇ etˇ sinou pˇ r´ımo (DAS – disrect attached storage), nebo pˇ res s´ıt’ (NAS – network atatched storage), pˇ r´ıpadnˇ e se chovaj´ı jako blokov´ a´ uloˇ ziˇ stˇ e (SAN – storage area network)
• SAN i NAS se daj´ı poˇ r´ıdit jak velk´ a, tak SOHO; pozor, nˇ ekdy je v´ ykon SOHO zaˇ r´ızen´ı velmi n´ızk´ y
Bezpeˇ cnost dat • RAID b´ yv´ a bezpeˇ cnˇ ejˇ s´ı neˇ z samotn´ e disky (s v´ yjimkou RAID 0), ale i zde m˚ uˇ ze doj´ıt ke ztr´ at´ am dat =⇒ je tˇ reba z´ alohovat, pˇ r´ıpadnˇ e vyuˇ z´ıvat dalˇ s´ı typy pamˇ et´ı (diskov´ e a p´ askov´ e jukeboxy)
• Kritick´ e syst´ emy i jejich z´ aloˇ zn´ı kopie je d˚ uleˇ zit´ e m´ıt um´ıstˇ en´ e na dostateˇ cnˇ e vzd´ alen´ ych a r˚ uzn´ ych m´ıstech (poˇ z´ ary, povodnˇ e)
Vnˇ ejˇ s´ı pamˇ eti
• Mnoho druh˚ u liˇ s´ıc´ıch se rychlost´ı, dod´ avanou kapacitou i cenou
• Plat´ı, ˇ ze velk´ e kapacity b´ yvaj´ı dostupn´ e pomalu, mal´ e kapacity rychleji nebo jsou silnˇ e miniaturizov´ any
• Je moˇ zn´ e vytv´ aˇ ret kask´ ady pamˇ et´ı
Z´ aznam
Logick´ y • kolekce souvisej´ıc´ıch poloˇ zek – hodnot atribut˚ u Fyzick´ y • logick´ y z´ aznam doplnˇ en´ y o oddˇ elovaˇ ce, definice d´ elek, zar´ aˇ zky, ... • d´ elka fyzick´ eho z´ aznamu – R
Typ z´ aznamu
d´ an jm´ eny a dom´ enami atribut˚ u
Aj : dom(Aj )
A1 : D1, . . . , An : Dn
Fyzick´ y a logick´ y z´ aznam Logick´ y z´ aznam – mnoˇ zina atribut˚ u Fyzick´ y z´ aznam (d´ elky R) – fyzick´ a reprezentace logick´ eho z´ aznamu na m´ ediu (m˚ uˇ ze obsahovat pomocn´ a data nav´ıc) Fyzick´ e z´ aznamy se ukl´ adaj´ı do fyzick´ ych str´ anek (blok˚ u – jejich velikost znaˇ c´ıme B) Bloky jsou minim´ aln´ı entitou pˇ ren´ aˇ senou mezi prim´ arn´ı a sekund´ arn´ı pamˇ et´ı
Blokovac´ı faktor, blokov´ an´ı Blokovac´ı faktor (b) – pomˇ er B/R Blokov´ an´ı (um´ıst’ov´ an´ı z´ aznam˚ u do blok˚ u); ˇ r´ık´ ame, ˇ ze z´ aznamy jsou: neblokovan´ e ⇐⇒ b = 1, B = R; blokovan´ e ⇐⇒ b > 1; pˇ rerostl´ e ⇐⇒ b < 1; Pro implementaci je d˚ uleˇ zit´ e, zda se R mˇ en´ı, ˇ ci nikoliv −→ budeme pˇ redpokl´ adat, ˇ ze se nemˇ en´ı.
Soubor Soubor je identifikovan´ a kolekce logicky souvisej´ıc´ıch z´ aznam˚ u. Jsou-li z´ aznamy stejn´ eho typu a velikosti, ˇ r´ık´ ame, ˇ ze soubor je homogenn´ı. V opaˇ cn´ em pˇ r´ıpade je nehomogenn´ı.
Kl´ıˇ c
Kl´ıˇ c souboru je mnoˇ zina atribut˚ u Ai1 ..Aik , k ≤ n, takov´ a, ˇ ze k-tice atribut˚ u < a1..ak > (kl´ıˇ ce z´ aznamu) jednoznaˇ cnˇ e identifikuj´ı z´ aznamy.
Vyhled´ avac´ı kl´ıˇ c je atribut (ˇ ci mnoˇ zina atribut˚ u), k jehoˇ z hodnotˇ e vyhled´ av´ ame mnoˇ zinu z´ aznam˚ u obsahuj´ıc´ıch pro dan´ y atribut pr´ avˇ e uvedenou hodnotu
Typy vyhled´ avac´ıch kl´ıˇ c˚ u
Hodnotov´ e – hodnoty z dom(Ai)
Haˇ sovan´ e – algoritmick´ a transformace hodnot
Relativn´ı – ud´ ana pozice od zaˇ c´ atku souboru
Operace nad soubory INSERT – vloˇ zen´ı z´ aznamu do souboru DELETE – ruˇ sen´ı z´ aznamu v souboru UPDATE – zmˇ ena nˇ ekter´ ych poloˇ zek z´ aznamu v souboru Aktualizace souboru – posloupnost operac´ı INSERT, DELETE a UPDATE FETCH – z´ısk´ an´ı z´ aznamu ze souboru do vnitˇ rn´ı pamˇ eti
Sch´ ema organizace souboru • popis logick´ e pamˇ et’ov´ e struktury, co n´ıˇ z m˚ uˇ ze b´ yt p˚ uvodn´ı soubor zobrazen, spolu s algoritmy prov´ adˇ ej´ıc´ımi operace nad touto strukturou • m˚ uˇ ze popisovat v´ıce logick´ ych soubor˚ u sv´ azan´ ych dohromady • prim´ arn´ı soubor – soubor obsahuj´ıc´ı uˇ zivatelsk´ a data; N – poˇ cet z´ aznam˚ u v nˇ em
Fyzick´ a ´ uroveˇ n • Abstrakce fyzick´ eho zaˇ r´ızen´ı – fyzick´ e sch´ ema souboru – fyzick´ y soubor
• Re´ aln´ e fyzick´ e zaˇ r´ızen´ı – implementaˇ cn´ı sch´ ema souboru
Abstrakce pˇ r´ıtupu k soubor˚ um
sch´ ema organizace souboru
logick´ e soubory
?
fyzick´ e sch´ ema souboru
?
implementaˇ cn´ı sch´ ema ´ uroveˇ n typu
fyzick´ e soubory
implementace fyzick´ ych soubor˚ u ´ uroveˇ n v´ yskytu
Operace SOS • operace nad soubory (insert, delete, update) • BUILD – vytvoˇ ren´ı struktury • REORGANIZATION – uveden´ı SOS do nov´ eho v´ ychoz´ıho stavu • Stav souboru S (S ∗; extenze souboru S) – podoba SOS mezi dvˇ ema ukonˇ cen´ ymi aktualizacemi • CLOSE – aktualizuje nˇ ekter´ a data o souboru
Souborov´ e syst´ emy
• podpora pr´ ace se soubory na ´ urovni z´ akladn´ıho SW
• uchov´ avaj´ı metadata o souborech
• umoˇ zˇ nuj´ı spr´ avu soubor˚ u vˇ cetnˇ e mapov´ an´ı soubor˚ u na m´ edium
Dotazy nad soubory
dotaz nad sch´ ematem souboru S – jak´ akoliv tot´ aln´ı funkce vyj´ adˇ riteln´ a programem definovan´ a nad mnoˇ zinou US . kter´ a kaˇ zd´ emu stavu pˇ riˇ rad´ı odpovˇ ed’ – zpravidla mnoˇ zinu z´ aznam˚ u
hity – prvky odpovˇ edi v pˇ r´ıpadˇ e dokument˚ u
V´ıcerozmˇ ern´ e/ortogon´ aln´ı dotazy • dotaz na ´ uplnou shodu – zad´ any hodnoty vˇ sech atribut˚ u • dotaz na ˇ c´ asteˇ cnou shodu – zad´ any hodnoty jen nˇ ekter´ ych atribut˚ u • dotaz na ´ uplnou intervalovou shodu – zad´ an interval hodnot pro kaˇ zd´ y z atribut˚ u • dotaz na ˇ c´ asteˇ cnou intervalovou shodu – zad´ any intervaly pro vybran´ e atributy
Dalˇ s´ı operace
READ ENTIRE FILE – ˇ cten´ı cel´ eho souboru • s´ eriovˇ e – podle zadan´ eho uspoˇ r´ ad´ an´ı • sekvenˇ cnˇ e – podle fyzick´ eho upoˇ r´ ad´ an´ı z´ aznam˚ u v souboru
Vyv´ aˇ zenost struktury • omezen´ı d´ elky cesty ve struktuˇ re pˇ ri vyhled´ an´ı z´ aznamu (napˇ r. O(log M ), kde M je poˇ cet logick´ ych str´ anek)
• rovnomˇ ern´ a naplnˇ enost str´ anek – faktor naplnˇ en´ı str´ anky λ (0 ≤ α < λ < β ≤ 1) – nˇ ekdy se λ oznaˇ cuje pr˚ umˇ ern´ e naplnˇ en´ı str´ anek • SOS splˇ nuj´ıc´ı obˇ e podm´ınky → dynamick´ e, ostatn´ı → statick´ e
