PA152: Efektivní využívání DB
2. Datová úložiště
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2012 2
Poděkování
 Zdrojem materiálů tohoto předmětu jsou:
Přednášky CS245, CS345, CS345
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 Stanford University, California
Přednášky dřívější verze PA152 (podzim 2008)
 Pavel Rychlý
 Fakulta informatiky, Masarykova Univerzita
PA152, Vlastislav Dohnal, FI MUNI, 2012 3
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2012 4
Omezení náhodných přístupů
 Defragmentace
 Uspořádání bloků do pořadí jejich zpracování
 Souborový systém
 Řeší na úrovni souborů
 Alokace více bloků naráz, nástroje pro defragmentaci
 Plánování přístupů (výtah)
 Pohyb hlavičky pouze jedním směrem
 Přeuspořádávání požadavků na disk
 Při zápisu použití zálohované cache (nebo logu)
 Prefetching, double buffering
PA152, Vlastislav Dohnal, FI MUNI, 2012 5
Single Buffer
 Úloha:
 Čti blok B1  buffer
 Zpracuj data v bufferu
 Čti blok B2  buffer
 Zpracuj data v bufferu
 …
 Náklady:
 P = čas zpracování bloku
 R = čas k přečtení 1 bloku
 n = počet bloků ke zpracování
 Single buffer time = n(R+P)
PA152, Vlastislav Dohnal, FI MUNI, 2012 6
Double Buffering
 Dva buffery v paměti, používané střídavě
A B C D GE F
Paměť
Disk
PA152, Vlastislav Dohnal, FI MUNI, 2012 7
Double Buffering
A
A B C D GE F
Paměť
Disk
PA152, Vlastislav Dohnal, FI MUNI, 2012 8
Double Buffering
A B
A B C D GE F
Paměť
Disk
zpracování
PA152, Vlastislav Dohnal, FI MUNI, 2012 9
Double Buffering
C B
A B C D GE F
Paměť
Disk
zpracování
PA152, Vlastislav Dohnal, FI MUNI, 2012 10
Double Buffering
 Náklady:
P = čas zpracování bloku
R = čas k přečtení 1 bloku
n = počet bloků ke zpracování
 Single buffer time = n(R+P)
 Double buffer time = R + nP
Předpokládáme P ≥ R
Jinak
 = nR + P
PA152, Vlastislav Dohnal, FI MUNI, 2012 11
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2012 12
Velikost bloku
 Velký blok  amortizace I/O nákladů
ALE
 Velký blok  čtení více „nepotřebných“
dat, čtení trvá déle
 Trend:
cena pamětí klesá, bloky se zvětšují
PA152, Vlastislav Dohnal, FI MUNI, 2012 13
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2012 14
 Více disků uspořádaných do jednoho
logického
Paralelní čtení / zápis
Snížení průměrné doby vystavení hlaviček
 Metody
rozdělování dat (block striping)
zrcadlení dat (mirroring)
Diskové pole
Logical Physical
PA152, Vlastislav Dohnal, FI MUNI, 2012 15
Zrcadlení
 Zvýšení spolehlivosti pomocí replikace
Logický disk je sestaven ze 2 fyzických disků
Zápis je proveden na každý z disků
Čtení lze provádět z libovolného disku
 Data dostupná při výpadku jednoho disku
Ztráta dat při výpadku obou  málo
pravděpodobné
 Pozor na závislé výpadky
Požár, elektrický zkrat, zničení HW řadiče
pole, …
PA152, Vlastislav Dohnal, FI MUNI, 2012 16
Rozdělování dat
 Cíle:
Zvýšení přenosové rychlosti rozdělením na
více disků
Paralelizace „velkého“ čtení ke snížení odezvy
Vyrovnání zátěže  zvýšení propustnosti
 Bit-level striping
Rozdělení každého bajtu na bity mezi disky
Přístupová doba je horší než u jednoho disku
Málo používané
PA152, Vlastislav Dohnal, FI MUNI, 2012 17
Rozdělování dat
 Block-level striping
n disků, blok i je uložen na disk (i mod n)+1
Čtení různých bloků lze paralelizovat
 Pokud jsou na různých discích
„Velké“ čtení může využít všechny disky
PA152, Vlastislav Dohnal, FI MUNI, 2012 18
RAID
 Redundant Arrays of
Independent Disks
 Různé varianty
Různé požadavky
Různá výkonnost
Různé vlastnosti
 Kombinace variant
RAID1+0
 = RAID1, pak RAID0
PA152, Vlastislav Dohnal, FI MUNI, 2012 19
RAID0, RAID1
 RAID0
Block striping, neredundantní
Velmi vysoký výkon, žádné zabezpečení dat
Nesnížená kapacita
 RAID1
Zrcadlení disků
 někdy omezeno na 2 disky
Kapacita 1/n, rychlé čtení, zápis jako 1 disk
Vhodné pro databázové logy, atp.
 Zápis logů je sekvenční
…
PA152, Vlastislav Dohnal, FI MUNI, 2012 20
RAID2, RAID3
 RAID2
 Bit-striping, Hamming Error-Correcting-Code
 Zotavení z výpadku 1 disku
 RAID3
 Bit-Interleaved Parity
 1 paritní disk
 Zápis: spočítání a uložení parity
 Obnova jednoho disku
 XOR bitů z ostatních disků
PA152, Vlastislav Dohnal, FI MUNI, 2012 21
RAID4
 Oproti RAID3 používá block-striping
Paritní blok na zvláštním disku
Zápis: spočítání a uložení parity
Obnova jednoho disku
 XOR bitů z ostatních disků
Vyšší rychlost než RAID3
 Blok je čtený pouze z 1 disku  paralelizace
PA152, Vlastislav Dohnal, FI MUNI, 2012 22
RAID4 (pokrač.)
 Zápis bloku  výpočet paritního bloku
Vezmi původní paritu, původní blok a nový
blok (2 čtení a 2 zápisy)
Nebo přepočítej paritu ze všech bloků (n-1
čtení a 2 zápisy)
Efektivní pro sekvenční zápis velkých dat
 Paritní disk je úzké místo!
Zápis libovolného bloku vede k zápisu parity
 RAID3, RAID4 – minimálně 3 disky (2+1)
Kapacita snížena o paritní disk
PA152, Vlastislav Dohnal, FI MUNI, 2012 23
RAID5
 Block-Interleaved Distributed Parity
Rozděluje data i paritu mezi n disků
Odstranění zátěže na paritním disku RAID4
 Příklad (5 disků)
Paritní blok pro n bloků je uložen na disku
(n mod 5) + 1
Datové bloky uloženy
na ostatních 4 discích
PA152, Vlastislav Dohnal, FI MUNI, 2012 24
RAID5 (pokrač.)
 Vyšší výkon než RAID4
Zápis bloků je paralelní, pokud jsou na
různých discích
Nahrazuje RAID4
 má stejné výhody a ruší nevýhodu paritního disku
 Často používané řešení
PA152, Vlastislav Dohnal, FI MUNI, 2012 25
RAID6
 P+Q Redundancy scheme
Podobné RAID5, ale ukládá extra informace
pro obnovu při výpadku více disků
Více disků pro paritu (dual distributed parity)
 Min. 4 disky v poli (kapacity snížena o 2 disky)
Samoopravné Hammingovy kódy
 Opraví výpadek 2 disků
Není příliš používaný
RAID – kombinace
 Jednotlivé varianty polí lze kombinovat
Z fyzických disků se vytvoří pole
Pak z polí se vytvoří výsledné pole
 Vhodné k zvýšení výkonu / spolehlivosti
 Příklad:
RAID5+0 z 6 fyzických disků
 Po třech vytvoříme dvě RAID5 pole
 RAID5 pole spojíme do RAID0
PA152, Vlastislav Dohnal, FI MUNI, 2012 26
1TB 1TB 1TB
RAID5
1TB 1TB 1TB
RAID5
RAID0
Zdroj: Wikipedia
RAID1+0 vs. RAID0+1
 RAID1+0
odolnější proti výpadkům
výpadek 1 disku v libovolném
RAID1 ok
 RAID0+1
výpadek disku v prvním RAID0
výpadek lib. disk v druhém RAID0
 data ztracena
PA152, Vlastislav Dohnal, FI MUNI, 2012 27
PA152, Vlastislav Dohnal, FI MUNI, 2012 28
RAID shrnutí
 RAID0 – bezpečnost dat není podstatná
Data lze snadno a rychle obnovit (ze záloh,…)
 RAID2 a 4 jsou nahrazeny RAID3 a 5
RAID3 se nepoužívá – bit-striping vede k
využití všech disků při zápisu/čtení 1 bloku
 RAID6 – nepoužívaný
RAID1 a 5 poskytují dostatečnou spolehlivost
Spíše kombinace – RAID1+0, RAID5+0
 Vybíráme mezi RAID1 a RAID5
PA152, Vlastislav Dohnal, FI MUNI, 2012 29
RAID shrnutí (pokrač.)
 RAID1+0
 Mnohem rychlejší zápis než RAID5
 Použití pro aplikace s velkým množstvím zápisů
 Dražší než RAID5 (má nižší kapacitu)
 RAID5
 pro každý zápis vyžaduje min. 2 čtení a 2 zápisy
 RAID1+0 vyžaduje pouze 2 zápisy
 Vhodný pro aplikace s menším množstvím zápisů
 Nároky dnešních aplikací na počet I/O
 Velmi vysoké (např. WWW servery, …)
 Nákup množství disků pro splnění požadavků
 Mají dostatečnou volnou kapacitu, pak RAID1 (nic nás dále
nestojí)
 Nejlépe RAID1+0
PA152, Vlastislav Dohnal, FI MUNI, 2012 30
RAID shrnutí (pokrač.)
 Nenahrazuje zálohování!!!
 Implementace
 SW – téměř každý OS podporuje
 HW – speciální řadič
 Nutné zálohování cache bateriemi nebo non-volatile RAM
 Pozor na výkonnost procesoru řadiče – může být pomalejší
než SW!!!
 Hot-swapping (výměna za provozu)
 HW implementace většinou podporují
 SW není problém, pokud HW podporuje
 Spare disks
 Existence náhradních disků v poli
PA152, Vlastislav Dohnal, FI MUNI, 2012 31
Výpadky disků
 Občasný výpadek
Chyba při čtení/zápisu  opakování  OK
 Vada média
Trvalá chyba nějakého sektoru
Moderní disky samy detekují a opraví
 z vlastní rezervní kapacity
 Zničení disku
Totální výpadek  výměna disku
PA152, Vlastislav Dohnal, FI MUNI, 2012 32
Ošetření výpadků disků
 Detekce
Kontrolní součty
 Opravy
Samoopravné kódy (ECC)
 Hammingovy kódy, …
Stabilní uložení
 Uložení na více místech stejného disku
 Např. super-blok
 Žurnálování (log změn)
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2012 33
Stabilní uložení v databázích
 Operační systém
 Databáze
Logický
blok
Kopie1 Kopie2
Současná
DB
zápis
Záložní
DB
log
PA152, Vlastislav Dohnal, FI MUNI, 2012 34
Zotavení ze zničení
 Mean Time To Failure (MTTF)
 Někdy také: Mean Time Between Failures (MTBF)
odpovídá pravděpodobnosti výpadku
průměrná doba fungování mezi výpadky
 polovina disků má výpadek během této doby
 předpokládá se rovnoměrné rozložení výpadků
snižuje s věkem disku
obvykle 1 000 000 a více hodin
  114 let
 tj. za 228 let vypadne 100%  Pvýpadku za rok=0,44%
PA152, Vlastislav Dohnal, FI MUNI, 2012 35
Výpadky – pokračování
 Příklad:
 MTTF 1 000 000 hours
  v populaci 2 000 000 disků
 vypadne každou hodinu jeden disk
 tj. 8 760 disků ročně
  pravděpodobnost výpadku za rok = 0,44%
 = Annualized Failure Rate (AFR)
 Annual Replacement Rate (ARR)
nebo Annualized Return Rate
 Ne všechny výpadky jsou způsobeny disky
 vadné kabely, atp.
 Uvádí se: 40% z ARR je “No Trouble Found”
(NTF)
 AFR = ARR*0.6 ARR = AFR / 0.6
PA152, Vlastislav Dohnal, FI MUNI, 2012 36
Výpadky – praxe
 Seagate http://www.seagate.com/docs/pdf/whitepaper/drive_reliability.pdf
(November 2000)
Savvio® 15K.2 Hard Drives – 73 GB
 AFR = 0,55%
Seagate estimates MTTF for a drive as the
number of power-on hours (POH) per year
divided by the first-year AFR.
AFR is derived from reliability-demonstration
tests (RDT)
 RDT at Seagate = hundereds of disks operating at
42ºC ambient temperature
Výpadky – praxe (2)
 Seagate
Vliv teploty na MTTF pro první rok
PA152, Vlastislav Dohnal, FI MUNI, 2012 37
Výpadky – praxe (3)
 Seagate
PA152, Vlastislav Dohnal, FI MUNI, 2012 38
Weibull – SW pro modelování průběhu chybovosti
Výpadky - realita
 Google http://research.google.com/archive/disk_failures.pdf (Konference FAST 2007)
Test na 100 000 discích
 SATA, PATA disky; 5400-7200 rpm; 80-400 GB
PA152, Vlastislav Dohnal, FI MUNI, 2012 39
Výpadky - realita
 Studie 100 000 disků SCSI, FC, SATA
http://www.cs.cmu.edu/~bianca/fast07.pdf (Konference FAST 2007)
PA152, Vlastislav Dohnal, FI MUNI, 2012 40
HPC3: 3064x SCSI disk, 15k rpm, 146GB
11000x SATA disk, 7200 rpm, 250GB
144x SCSI disk, 15k rpm, 73GB
Avg. ARR
AFR=0.88
AFR=0.58
Rate(%)
Výpadky - realita
 Závěry:
 Obvykle se AFR zvyšuje s teplotou prostředí
 Data z Google to nepotvrzují
 SMART parameters are well-correlated with higher
failure probabilities
 Google
 After the first scan error, a drive is 39 times more likely to fail within
60 days.
 First errors in reallocations, offline reallocations, and probational
counts are strongly correlated to higher failure probabilities.
 Vhodné ve výpočtech používat AFR 3-4%
 If you plan on AFR that is 50% higher than MTTF suggests,
you’ll be better prepared.
 Po 3 letech provozu disku být připraven na jeho
výměnu.
PA152, Vlastislav Dohnal, FI MUNI, 2012 41
PA152, Vlastislav Dohnal, FI MUNI, 2012 42
Oprava chyby
 Mean Time To Repair (MTTR)
Čas od výpadku do obnovení činnosti
= čas výměny vadného disku + obnovení dat
 Mean Time To Data Loss (MTTDL)
Závisí na MTTF a MTTR
Průměrná doba mezi ztrátou dat
Pro jeden disk (tj. data ukládám na jednom
disku)
 MTTDL = MTTF
PA152, Vlastislav Dohnal, FI MUNI, 2012 43
Oprava chyby – sada disků
 Sada disků
Předpoklad
 chyba každého disku je stejně pravděpodobná
 a nezávislá na ostatních
 Příklad
Jeden disk
 MTTF = 114 let, AFR = 0,44%
Systém se 114 disky
 MTTF = 1 rok, AFR = 50%
 Tj. průměrně každý rok jeden z disků vypadne
(50% pravděpodobnost)
PA152, Vlastislav Dohnal, FI MUNI, 2012 44
Příklad výpadku RAID1
 2 zrcadlené disky
 každý AFR=3%
 Výměna vadného a obnova pole do 3 hodin
 MTTR = 3 hodiny
 Pravděpodobnost ztráty dat:
 Pvýpadku 1 disku = AFR = 0.03, Pvýpadku 1 ze 2 = 0.06
 MTTR = 3 hod = 3/24 dne = 1/2920 roku
 Pztráty dat = Pvýpadku 1 ze 2 * MTTR * Pvýpadku 1 disku
=1 / 1 622 222 = 0,000 000 616
 MTTDL = 0.5 / Pztráty dat = 0.5 / (1/1622222) = 811 111 let
PA152, Vlastislav Dohnal, FI MUNI, 2012 45
Příklad výpadku RAID0
 AFR disku 3% (Pvýpadku 1 disku)
 RAID0 – dva disky, striping
Pztráty dat = Pvýpadku 1 ze 2 = 6%
MTTDL = 0.5 / (0.06) = 8,3 roku
PA152, Vlastislav Dohnal, FI MUNI, 2012 46
Příklad výpadku RAID4
 AFR disku 3% (Pvýpadku 1 disku)
 RAID4 – opravuje výpadek 1 disku
4 disky (3+1), MTTR = 3 hodiny
Pztráty dat = Pvýpadku 1 ze 4 * MTTR * Pvýpadku 1 ze 3
Pztráty dat = 4*0,03 * 1/2920 * 3*0,03
= 108 /2 920 000 = 0,000 003 698
MTTDL = 0.5 / Pztráty dat = 135 185 let
Příklad výpadku – kombinace RAID
 Kombinace polí
Spočítám MTTDL pro složky
 Toto použiji v dalším jako MTTF „virtuálního disku“
Pak vypočítám výsledné MTTDL
PA152, Vlastislav Dohnal, FI MUNI, 2012 47
1TB 1TB 1TB
RAID5
1TB 1TB 1TB
RAID5
RAID0
Příklad výpadku – kombinace RAID
 RAID5+0
1 disk má AFRdisk a MTTFdisk
1) Vypočítej MTTDL pro RAID5
 To dále použijeme jako MTTF
 AFRRAID5 = 8760/(2*MTTF)
2) Vypočítej MTTDL pro RAID0
MTTDL = 0.5 / Pvýpadku 1 ze 2
= 0.5 / (2*AFRRAID5)
PA152, Vlastislav Dohnal, FI MUNI, 2012 48
1TB 1TB 1TB
RAID5
1TB 1TB 1TB
RAID5
RAID0
1TB 1TB 1TB
RAID5
1TB 1TB 1TB
RAID5
RAID0
RAID5
RAID0
RAID5
Příklad výpadku – kombinace RAID
 RAID4+0 z 8 disků
1 disk AFR=3%
Vždy ze 4 disků vyrobíme 1x RAID4
 MTTDLRAID4 = 135 185 let, tj. AFRRAID4 = 1 / 270 370
2x RAID4 spojíme pomocí RAID0
 Pztráty dat RAID4+0 = Pvýpadku 1 ze 2 RAID4 polí = 2 * 1/270370
 MTTDL = 0.5 / (2 * 1/270370) = 67 592,5 let
PA152, Vlastislav Dohnal, FI MUNI, 2012 49
RAID0
RAID4
1TB 1TB 1TB 1TB
RAID4
1TB 1TB 1TB 1TB