![]() |
![]() |
Prefetch - aneb proč číst data do zásoby
V posledních letech, kdy každý výrobce databázového software usiluje o jeho největší výkon, se můžeme setkat s poněkud tajemným výrazem prefetch. Těžko říci, jak se s tímto slovem vyrovnat v češtině. Přitom jde v podstatě pouze o to, že pro některé dotazy načte SŘBD z disku více stránek než jednu. Zkrátka, čte si data “do zásoby”. Abychom pochopili, k čemu je dobré, je třeba se podívat trochu blíže na nejmocnějšího nepřítele rychlého zpracování databázových dotazů, tj. na diskové zařízení. O magnetickém disku (MD) se říká, že jde o médium s přímým přístupem. Firma IBM ho uvedla na trh v r. 1956. Měl průměr dvě stopy a možnost uložit na krychlový centimetr 2,5 znaku s dobou přístupu 100 ms. V roce 1963 byl průměr disku redukován na 14 palců a výsledné zařízení se stalo základem velkokapacitních disků na dobu více než 30 let. Dnešní nejpokročilejší pevné disky mají průměr 3,5 palce a jsou schopny udržet 6 milionů znaků na krychlový centimetr s dobou přístupu 12 milisekund. Přímý přístup znamená, že lze přímo přečíst nebo zapsat stránku, známe-li její adresu na disku. MD, či lépe diskový svazek, je soustava kotoučů na společné ose, otáčející se konstantní rychlostí t. K MD lze přibližovat ramínko s čtecími a zápisovými hlavami. Hlavy existují pro každý kotouč, pro každý z jeho dvou povrchů. Data na povrchu kotouče se ukládají na soustředné kružnice - stopy. Podstatné je, že stopy, ač různých průměrů, mají na konkrétním MD stejnou kapacitu. Protože ramínko s hlavami dosáhne umístění vždy tak, že hlavy jsou schopny být aktivní na stopách o stejném průměru, je výhodné zavést jednotku - cylindr (nebo válec). Cylindr se skládá ze všech stop o stejném průměru. Pro zápis a čtení je podstatné, že vždy jedna hlava může být v daném čase aktivní, tj. na MD lze zapisovat nebo číst stránku vždy na jedné stopě. Nárys diskového zařízení je na obrázku 1. Fyzická adresa stránky je u standardních diskových zařízeních dána trojicí (číslo cylindru, číslo stopy, číslo stránky). Vhodnější je ovšem používat transformaci těchto adres do lineárního prostoru relativních adres 0,1,...,M-1. Velikost stránky je volitelná. Pro provoz MD jsou rozhodující tři parametry: s (seek) - průměrný čas přesunu ramínka z cylindru k nějakému jinému cylindru r (rotational delay) - čas rovný polovině otáčky disku (průměrné rotační zpoždění) btt (block transfer time) - čas potřebný k přenosu stránky z MD do vnitřní paměti nebo z vnitřní paměti na MD. Např. čtení stránky si můžeme představit tak, že ramínko musí najet k cylindru, na jehož stopě je umístěna hledaná stránka, systém vyčká v průměru polovinu otáčky k najetí začátku stránky na určité stopě na příslušnou hlavičku, systém čte stránku z daného místa a přenáší ji do bufferu ve vnitřní paměti. povrchy
stopa 0 READ/WRITE hlavy stopa 1 a) pohled na povrch disku ramínka přístupový mechanismus osa Obr. 1: Model diskového zařízení Běžná rychlost otáčení disku je 60 otáček/s, standardem se však stávají disky dokonce s 90 otáčkami/s. Co se týče velikosti disků, u zařízení schopného nést GByte dat se můžeme s deseti povrchy a stopami pro 40.000 Byte. Jeden cylindr tedy může pojmout 400.000 Byte. Disková jednotka pak obsahuje 2.500 cylindrů. Náhodné přečtení jedné stránky o velikosti 4000 Byte vyžaduje cca 0.025 s, tj. za jednu vteřinu lze provést 40 I/O operací. Tento údaj získáme z typických hodnot s = 0,016, r = 0,008 a btt = 0,001 (pro 4000 Byte). Je zřejmé, že jde o velké hodnoty, speciálně u parametrů s a r. Běžnou strategií ukládání na disk tedy je ukládat data na po sobě následujících cylindrech. Další roli při zpracování bude zřejmě hrát velikost stránky. Ta je dnes u databázových serverů nastavitelná. Běžné jsou hodnoty 4 KByte, existují však i 2KBytové stránky, v poslední době není vzácností velikost více něž 8 KByte. Např. u SYBASE Sever 11 lze používat stránky velikosti 2 - 16 KByte. Uvažujme nyní příklad tabulky ZAMĚSTNANEC obsahující 200.000 řádků, z nichž každý má 200 Byte. Při velikosti stránek 4 KByte a jejich 70% naplnění, je třeba pro celou tabulku vyhradit 14.286 stránek. V případě i těch nejednodušších dotazů, není-li pro tabulku vytvořen žádný index, je nevyhnutelné použít sekvenční prohledávání, tj. je nutné přečíst v nejhorším případě 14.286 stránek. Kolik takové čtení stojí, lze snadno spočíst jako 14.286/40 = 357,15 s, což je jistě dost neúnosné. Ve skutečnosti ale situace není tak tragická. Předpokládáme-li stránky uložené za sebou, pak není nutné použít odhad pro náhodný přístup. Parametr s=0 (byl nastaven na počátku čtení) a dále by se zdálo, že stačí číst stránky tak, že se plně využije celá otáčka disku, tj. že vlastně stačí vzít btt, přičemž celkový čas by byl 14.286 * btt = 14 s. Tato úvaha ovšem není správná, protože čtení dvou po sobě jdoucích stránek zvlášť nelze technicky zařídit. Dokončení operace čtení totiž potřebuje jistou dobu, v níž se ovšem disk o kousek pootočí. Je tedy nutné číst další stránku až po provedení celé otáčky. Přečtení stránky tedy stojí 2r + btt, tj. 0,017 s. Tabulka ZAMĚSTNANEC tedy požaduje pro přečtení 242,86 s, což je pořád moc. Každého jistě napadne možnost číst stránky “ob jednu”. Jistě, i to je možné, nicméně efekt nemusí být vždy dostatečný. Při paralelním zpracování transakcí může být ramínko disku v průběhu čtení posunuto k přečtení jiné stránky. Jinou možnost nabízí jistá paralelizace I/O operací, kterou docílíme rozmístěním tabulky na více disků. Hovoří se o “páskování disků” (disk striping). Představme si 10 disků, na které rozložíme stránky s řádky relace zaměstnanec způsobem X MOD Y, tj. do skupin { 1, 11, 21, ...} na 1. disk, { 2, 12, 22, ... } na 2. disk, atd., tj. na 10. disku jsou stránky { 10, 20, 30, ...} . Pak při paralelním čtení z 10. disků by se původní čas čtení celé tabulky redukoval na 1/10. Přestože z hlediska našeho dotazu vypadá dané řešení atraktivně, a nekteré SŘBD je nabízejí, nejde o univerzální běžně používaný přístup. Složité může totiž být vyvážení systému u jiných typů dotazů. Větší zátěž jednoho z disků se stává brzdou pro další. Dobrým kompromisem mezi páskováním a jednouchým sekvenčním čtením se stává metoda nazvaná angl. prefetch, nebo též vícestránkové I/O. Jde o to, že lze přečíst několik po sobě jdoucích stránek najednou tak, jakoby tvořily jeden blok. Např. SŘBD DB/2 takto může přečíst 32 stránek (maximálně dokonce 64 stránek). Při náhodném čtení 32 stránek bychom potřebovali řas 32(0,016 + 0,008 + 0,001) = 32 * 0, 25 = 0, 8 s. Při přečtení 32 stránek jako jeden celek však stačí 0,016 + 0,008 + 32 * 0,001 = 0,056 s. Za vteřinu lze tedy přečíst 571 stránek. Aplikujeme-li metodu na tabulku ZAMĚSTNANEC, obdržíme čas 14.286/571 = 25 s. A toto je již skutečná úspora. Potřebujeme pouze dostatečně velkou vnitřní paměť, tj. pro sekvenční prefetch 32 stránek se předpokládá více než 1000 stránek (4 MByte) jako prostor pro buffery. Při menším prostoru pro buffery lze místo 32 stránek použít odpovídající menší množství (např. 16 nebo 8). Všimněme si. že prefetch může být kombinován s páskováním, tj. čteme-li n-tou stránku lze přečíst k následujících n + 1, n + 2, ..., n + k (pro vhodné k) z k disků vlastně najednou. Důležitá je dále velikost stránek. Závěrem se krátce zmíníme ještě o jedné variantě “rychlého” čtení stránek. Jde o tzv. list prefetch. kdy se přečte seznam stránek ne nutně po sobě jdoucích ovšem čtení sekvence je naprogramováno tak, aby se co nejlépe využily pohyby ramínka. Tento prefetch je pomalejší než sekvenční prefetch, ale rychlejší než pouhé náhodné čtení stránek. Opravdové využití tohoto zajímavého způsobu čtení stránek ocení v SŘBD až jeho optimalizátor. Ten na základě jistých znalostí o požadavcích na vyhodnocení dotazu může rozhodnout, kolik stránek a zdali vůbec se nějaký prefetch uskuteční. Pamětníci nakonec poznávají, že ideu prefetch znají již ze 70. let, tj. z období návrhů virtuálních pamětí. Dnes nabývá v souvislosti s databázemi na novém významu. Zvětšuje možnosti optimalizace, protože lze využít znalostí o tom, které stránky bude aplikace potřebovat na základě stavu aplikace samé. Výzkum predikce a jejího použití pro čtení stránek aplikaci “do zásoby” se tak stává další atraktivní alternativou v databázové technologii. <seznam dílů seriálu> <COMPUTERWORLD> |