PA152: Efektivní využívání DB
2. Datová úložiště
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2016 2
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2016 3
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ání požadavků na disk
 Při zápisu použití zálohované cache (nebo žurnálu)
 Prefetching, double buffering
PA152, Vlastislav Dohnal, FI MUNI, 2016 4
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, 2016 5
Double Buffering
 Dva buffery v paměti, používané střídavě
A B C D GE F
Paměť
Disk
PA152, Vlastislav Dohnal, FI MUNI, 2016 6
Double Buffering
A
A B C D GE F
Paměť
Disk
načítání
PA152, Vlastislav Dohnal, FI MUNI, 2016 7
Double Buffering
A B
A B C D GE F
Paměť
Disk
zpracování
načítání
PA152, Vlastislav Dohnal, FI MUNI, 2016 8
Double Buffering
C B
A B C D GE F
Paměť
Disk
zpracování
načítání
PA152, Vlastislav Dohnal, FI MUNI, 2016 9
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, 2016 10
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2016 11
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á, data rostou, bloky se
zvětšují
Velikost bloku
 ATTO Disk Benchmark
256MB read sequentially block by block
No caching
Queue length 4
PA152, Vlastislav Dohnal, FI MUNI, 2016 12
Western Digital 10EZEX 1TB, SATA3, 7200 RPM, sustained transfer rate 150 MB/s
KiB
IO za sekundu
 IOPS dle HD Tune Pro 5.50
Reading 4KiB blocks
PA152, Vlastislav Dohnal, FI MUNI, 2016 13
Western Digital 10EZEX 1TB, SATA3, 7200 RPM, sustained transfer rate 150 MB/s
Bloky a IOPS
 Stejné testy pro SSD
PA152, Vlastislav Dohnal, FI MUNI, 2016 14
Kingston V300 120GB
PA152, Vlastislav Dohnal, FI MUNI, 2016 15
Optimalizace přístupu na disk
 Omezení náhodných přístupů
 Velikost bloku
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2016 16
 Více disků uspořádaných do jednoho
logického
 Zvětšení kapacity
 Paralelní čtení / zápis
 Průměrná doba vystavení hlaviček typicky
zachována
 Metody
 rozdělování dat (data striping)
 zrcadlení dat (mirroring)
Diskové pole
Logical Physical
PA152, Vlastislav Dohnal, FI MUNI, 2016 17
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, 2016 18
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, 2016 19
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, 2016 20
RAID
 Redundant Arrays of
Independent Disks
 Různé varianty pro různé
požadavky
Různá výkonnost
Různá spolehlivost
 Kombinace variant
RAID1+0 (nebo RAID10)
 = RAID1, pak RAID0
PA152, Vlastislav Dohnal, FI MUNI, 2016 21
RAID0, RAID1
 RAID0
Block striping, neredundantní
Velmi vysoký výkon, nezvýšená spolehlivost
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, 2016 22
RAID2, RAID3
 RAID2
 Bit-striping, Hamming Error-Correcting-Code
 Zotavení z výpadku 1 disku
 RAID3
 Byte-striping with parity
 1 paritní disk
 Zápis: spočítání a uložení parity
 Obnova jednoho disku
 XOR bajtů z ostatních disků
PA152, Vlastislav Dohnal, FI MUNI, 2016 23
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 bloků z ostatních disků
Vyšší rychlost než RAID3
 Blok je čtený pouze z 1 disku  paralelizace
 Disky nemusí být plně synchronizované
PA152, Vlastislav Dohnal, FI MUNI, 2016 24
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, 2016 25
RAID5
 Block-Interleaved Distributed Parity
Rozděluje data i paritu mezi n disků
Odstranění zátěže na paritním disku RAID4
Paritní blok pro i-tý blok je uložen na disku
𝑖
𝑛−1 mod 𝑛
 Příklad (5 disků)
Parita pro blok i je na:
𝑖
4 mod 5
PA152, Vlastislav Dohnal, FI MUNI, 2016 26
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 jednoho
paritního disku
 Často používané řešení
PA152, Vlastislav Dohnal, FI MUNI, 2016 27
RAID6
 P+Q Redundancy scheme
Podobné RAID5, ale ukládá extra informace
pro obnovu při výpadku více disků
Dva disky pro paritu (dual distributed parity)
 Min. 4 disky v poli (kapacita snížena o 2 disky)
Samoopravné Hammingovy kódy
 Opraví výpadek 2 disků
Vhodný pro vysokokapacitní disky
Q Q
Q
RAID – kombinace
 Jednotlivé varianty polí lze kombinovat
Z fyzických disků se vytvoří pole
Pak se z více polí vytvoří jedno 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, 2016 28
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, 2016 29
PA152, Vlastislav Dohnal, FI MUNI, 2016 30
RAID shrnutí
 RAID0 – dostupnost dat není podstatná
Data lze snadno a rychle obnovit (ze záloh,…)
 RAID2, 3 a 4 jsou nahrazeny RAID5
bit/byte-striping vede k využití všech disků při
zápisu/čtení 1 bloku; nedistribuovaná parita
 RAID6 – méně používaný než RAID5
RAID1 a 5 poskytují dostatečnou spolehlivost
 RAID6 spíše pro velmi velké disky
 Kombinace – RAID1+0, RAID5+0
 Vybíráme mezi RAID1 a RAID5
PA152, Vlastislav Dohnal, FI MUNI, 2016 31
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 typicky 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ů
 Pozor na velikost „stripy“
 Nároky dnešních aplikací na počet I/O
 Velmi vysoké (např. WWW servery, DBMS, …)
 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, 2016 32
RAID shrnutí (pokrač.)
 Nenahrazuje zálohování!!!
 Implementace
 SW – téměř každý OS podporuje, popř. BIOS
 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
 Přítomnost náhradních disků v poli
PA152, Vlastislav Dohnal, FI MUNI, 2016 33
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, 2016 34
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
 super-blok; pro data ZFS
 Žurnálování (log/záznam změn)
 Diskové pole
PA152, Vlastislav Dohnal, FI MUNI, 2016 35
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, 2016 36
Výpadky
 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%
  Annualized Failure Rate (AFR)
PA152, Vlastislav Dohnal, FI MUNI, 2016 37
Výpadky – pokračování
 Příklad:
MTTF 1 000 000 hours
 v populaci 2 000 000 disků
 každou hodinu vypadne jeden disk
 tj. 8 760 disků ročně
  pravděpodobnost výpadku za rok = 0,438%
PA152, Vlastislav Dohnal, FI MUNI, 2016 38
Výpadky – pokračování
 Alternative measure (e.g. Western Digital)
Annualized Failure Rate (AFR)
Component Design Life
 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, 2016 39
Výpadky a výrobci
 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 = hundreds of disks operating at
42ºC ambient temperature
Výpadky a výrobci
 Vliv teploty na MTTF pro první rok
Seagate:
PA152, Vlastislav Dohnal, FI MUNI, 2016 40
Adjusted MTTF
Výpadky a výrobci
 Seagate Barracuda ES.2 Near-Line Serial ATA drive
PA152, Vlastislav Dohnal, FI MUNI, 2016 41
Note1: Weibull – SW pro modelování průběhu chybovosti
Note2: 2400 hours/yr => 6.5 hrs a day!
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, 2016 42
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, 2016 43
HPC3: 3064x SCSI disk, 15k rpm, 146GB
144x SCSI disk, 15k rpm, 73GB
11000x SATA disk, 7200 rpm, 250GB
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, 2016 44
PA152, Vlastislav Dohnal, FI MUNI, 2016 45
Oprava chyby
 We know AFR = 1 / (2*MTTF)
 Mean Time To Repair (MTTR)
 Čas od výpadku do obnovení činnosti
 = čas výměny vadného disku + obnovení dat
 PFailure During Repair = PFDR = (2*MTTR) / 1 rok
 Předpoklad: velmi krátká doba
 Mean Time To Data Loss (MTTDL)
 Závisí na AFR a MTTR
 Průměrná doba do ztráty dat
 Pro jeden disk (tj. data ukládám na jednom disku)
 MTTDL = MTTF = 0.5 / AFR
PA152, Vlastislav Dohnal, FI MUNI, 2016 46
Oprava chyby – sada disků
 Předpoklad
 Chyba každého disku je stejně pravděpodobná a
nezávislá na ostatních
 Příklad
 Jeden disk
 AFR1 disk = 0,44% (MTTF = 1,000,000 hrs. = 114 yrs.)
 Systém se 100 disky (MTTF100 disků = MTTF1 disk / 100)
 AFR100 disků = 44% (MTTF = 10,000 hrs. = 1.14 yrs.)
 Průměrně každý rok cca jeden z disků vypadne
 Pravděpodobnost (právě 1 z n vs. alespoň 1 z n havaruje)
 Pvýpadek právě 1 ze 100 = 28,43% Pvýpadek alespoň 1 ze 100 = 35,66%
 Pvýpadek právě 1 z 10 = 4,23% Pvýpadek alespoň 1 z 10 = 4,31%
 AFRn disků = AFR1 disk * n
PA152, Vlastislav Dohnal, FI MUNI, 2016 47
Příklad výpadku RAID1
 2 zrcadlené 500GB disky
 každý AFR=3%
 Výměna vadného a obnova pole do 3 hodin
 MTTR = 3 hodiny (při 100MB/s je kopírování za 1,5h)
 Pravděpodobnost ztráty dat:
 Pvýpadku 1 disku = AFR = 0.03
 Pvýpadku 1 ze 2 = 0.06
 PFDR = 2 * MTTR / 1 rok = 2*3 / 8760 = 0,000 685
 Pztráty dat = Pvýpadku 1 ze 2 * PFDR * Pvýpadku 1 disku
= 0,000 001 233
 MTTDL = 0.5 / Pztráty dat = 405 515 let
PA152, Vlastislav Dohnal, FI MUNI, 2016 48
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
 Tj. AFRpole = 6%
PA152, Vlastislav Dohnal, FI MUNI, 2016 49
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
 PFDR = 2*3 / 8760 = 0,000 685
Pztráty dat = Pvýpadku 1 ze 4 * PFDR * Pvýpadku 1 ze 3
Pztráty dat = 4*0,03 * 2/2920 * 3*0,03
= 0,000 007 397
 což je AFR tohoto pole
MTTDL = 0.5 / Pztráty dat = 67 592 let
Spolehlivost pole
 n disků
celkem disků v poli (včetně paritních)
 1 paritní disk
zajišťují redundanci dat
 AFRpole = n*AFR1 disku * PFDR * (n-1)*AFR1 disku
 MTTDL = 0.5 / AFRpole
PA152, Vlastislav Dohnal, FI MUNI, 2016 50
Příklad výpadku – kombinace RAID
 Kombinace polí
Spočítám AFR pro složky
 Toto použiji v dalším jako AFR „virtuálního disku“
Pak vypočítám výsledné MTTDL
PA152, Vlastislav Dohnal, FI MUNI, 2016 51
1TB 1TB 1TB
RAID5
1TB 1TB 1TB
RAID5
RAID0
Příklad výpadku – kombinace RAID
 RAID5+0
1 disk má AFRdisk
1) Urči AFRRAID5
2) Urči AFRRAID0 = 2 * AFRRAID5
3) MTTDLRAID5+0 = 0.5 / AFRRAID0
PA152, Vlastislav Dohnal, FI MUNI, 2016 52
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ů v konfiguraci níže
1 disk AFR=3%, MTTR = 3 hodiny
Vždy ze 4 disků vyrobíme 1x RAID4
 AFRRAID4 = 4*AFR * PFDR * 3*AFR = … = 7.4*10-6
2x RAID4 spojíme pomocí RAID0
 AFRRAID4+0 = 2 * AFRRAID4 = 1.48*10-5
 MTTDL = 0.5 / AFRRAID4+0 = 33 796 let
PA152, Vlastislav Dohnal, FI MUNI, 2016 53
RAID0
RAID4
1TB 1TB 1TB 1TB
RAID4
1TB 1TB 1TB 1TB
Failures: „Write Hole“ Phenomenon
 = Data is not written to all disks.
 Severity
 Can be unnoticed
 Discoverable during array reconstruction
 Solution
 UPS
 Synchronize the array
 Journaling
 but with “data written” commit message (-:
 Special file system (ZFS)
 uses "copy-on-write" to provide write atomicity
 provides continuous integrity checking
PA152, Vlastislav Dohnal, FI MUNI, 2016 54
File Systems
 Storing a data block:
1. Add an unused block to list of used space
2. Write data block
3. Write file metadata referencing that data block
 More modern – use journaling
 Start transaction in journal
 Store info about steps 1.-3. to journal
 Do steps 1.-3.
 End transaction in journal
PA152, Vlastislav Dohnal, FI MUNI, 2016 55
File System Tuning
 FS block size  DB block size
 ZFS has 128KB by default!
 DB journal (WAL in PostgreSQL)
 ext2; ext3/4 with data=writeback
 DB data
 ext3/4 with data=ordered (only metadata journaled)
 Switch off file access times (noatime)
 Eliminate swapping (vm.swappiness = 0)
 Process memory allocation
(vm.overcommit_memory = 2)
 …
PA152, Vlastislav Dohnal, FI MUNI, 2016 56
RAID nad disky SSD
 SSD – problém opotřebení
Omezený počet zápisů se řešení přesuny do
jiných oblastí, tzv. wear-leveling
Důsledek: po jisté době dojde k totálnímu
výpadku
 RAID nad SSD
Zabezpečení dostupnosti dat horší
 Téměř jistota, že SSD vypadnou naráz
Diff-RAID
 Distributes parity unevenly
 After replacing a failed SSD with a brand new one,
parity is moved primarily to the most worn-out drive.
PA152, Vlastislav Dohnal, FI MUNI, 2016 57
Recommended Reading
 Dual parity
 https://www.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf
 Software RAID in SUSE
 https://www.suse.com/documentation/sles10/stor_admin/data/raidevms.html
 Sections:
 Managing Software RAIDs with EVMS
 Managing Software RAIDs 6 and 10 with mdadm
 SSD on Wikipedia
 https://en.wikipedia.org/wiki/Solid-state_drive
 Živě.cz: Ze světa: kolik reálně zapsaných dat
vydrží moderní SSD?
 http://m.zive.cz/ze-sveta-kolik-realne-zapsanych-dat-vydrzi-moderni-ssd/a-
177557/?textart=1
PA152, Vlastislav Dohnal, FI MUNI, 2016 58
Diplomové práce
 Cognitive Alerting
 adaptive analysis for monitoring several metrics
and alerting on changes of their values
 propose a system that will adapt automatically
and raise only a limited number of alerts
 Data Projections Adviser
 study column-oriented databases and query
monitoring commands
 create a tool capable of monitoring data statistics
and query logs and recommend steps to take
 e.g. to create new data projections or drop existing
ones
PA152, Vlastislav Dohnal, FI MUNI, 2016 59