Abstrakt: Metody externího trˇídeˇní, tedy trˇídeˇní využívajícího vneˇjší pameˇt', jsou velmi dobrˇe známy již mnoho desetiletí. Tyto metody byly pu˚ vodneˇ navrženy pro systémy s malým množstvím interní pameˇti a magnetickými páskami coby vneˇjší pameˇtí. Magnetické pásky jsou specifické cˇisteˇ sekvencˇním prˇístupem k datu˚ m, který také ovlivnil návrh metod externího trˇídeˇní. Pásky byly nahrazeny pevnými disky s magnetickými plotnami, které prˇinesly možnost náhodného prˇístupu k datu˚ m, avšak sekvencˇní prˇístup zu˚ stal nadále výrazneˇ výkonneˇjší. Veˇtšina hardwarových prˇedpokladu˚ , na kterých je externí trˇídeˇní postaveno se za poslední desetiletí výrazneˇ zmeˇnila, zejména s prˇíchodem SSD disku˚ a vývojem nonvolatilních pameˇtí. V tomto cˇlánku prˇedstavujeme nový prˇístup k externímu trˇídeˇní, který reflektuje parametry soucˇasného hardware. Dále prˇedkládáme empirické srovnání s již existujícími metodami, které se hojneˇ používají v soudobých systémech. Trˇídeˇní patrˇí k základním stavebním kamenu˚ m rˇady algoritmu˚ a aplikací. V databázových systémech patrˇí spolecˇneˇ s operací JOIN k nejpoužívaneˇjším operacím vu˚ bec. I prˇes rostoucí kapacity a klesající ceny operacˇních pameˇtí není vždy možné rˇešit tuto úlohu cˇisteˇ v rámci vnitrˇní pameˇti pocˇítacˇe. Pro tyto situace máme k dispozici algoritmy externího trˇídeˇní, které využívají diskové úložišteˇ k odkládání mezivýsledku˚ . Algoritmy vneˇjšího trˇídeˇní byly navrženy a zmapovány již v dobách, kdy se jako externí pameˇt' používaly magnetické pásky. I prˇes jejich pu˚ vodní cíle se tyto algoritmy s drobnými úpravami používají dodnes. Jejich hlavní nevýhodou je, že prˇedpoklady, ze kterých tyto algoritmy vychází dnes již neplatí. Nejvýznamneˇjší prˇedpoklady mu˚ žeme shrnout takto: • Externí pameˇt' je organizována sekvencˇneˇ, nebo je sekvencˇní prˇístup výrazneˇ výkonneˇjší. Máme k dispozici pouze malé množství externích pásek, resp. mu˚ žeme rozumneˇ pracovat pouze s malým množstvím otevrˇených souboru˚ .
Klícˇová slova: trˇídeˇní, vneˇjší pameˇt’, algoritmus, optimalizace, moderní hardware • Externí pameˇt’ je o mnoho rˇádu˚ pomalejší než interní pameˇt’, takže dominantní složkou vyjadrˇující cˇasovou složitost je pocˇet operací s externí pameˇtí.
V tomto cˇlánku bychom rádi vyvrátili tyto prˇedpoklady pomocí empirických experimentu˚ , jejichž cílem je identifikovat vlastnosti soudobých pevných disku˚ s magnetickými plotnami a SSD pevných disku˚ . Na základeˇ opravených prˇedpokladu˚ pak navrhujeme zmeˇny pro algoritmy vneˇjšího trˇídeˇní, které by meˇly znacˇneˇ vylepšit jejich výkon.
Tento cˇlánek je organizován následovneˇ. Sekce 2 shrnuje prˇehled souvisejících prací zameˇrˇených na externího trˇídeˇní. Popis soucˇasných algoritmu˚ se nachází v sekci 3. Sekce 4 definuje nové prˇedpoklady o soucˇasném hardware a na jejich základeˇ navrhuje zmeˇny v metodách externího trˇídeˇní. Výsledky experimentu˚ , které podporují naše záveˇry, se nachází v sekci 5 a sekce 6 uzavírá cˇlánek. 2
Problém externího trˇídeˇní, tedy trˇídeˇní za použité vneˇjší
pameˇti, je jedním z hlavních problému˚ v oblasti algoritmu˚
pro externí pameˇt’. Cˇ ástecˇneˇ je tomu tak proto, že trˇídicí
operace tvorˇí signifikantní cˇást pocˇítacˇových operací [
Datová komunikace mezi rychlou interní pameˇtí a
pomalejší externí pameˇtí je považována za úzké hrdlo prˇi
zpracování velikých dát [
Veˇtšina algoritmu˚ externího trˇídeˇní má dveˇ cˇásti. V první cˇásti se generují takzvané beˇhy, tedy sekvence setrˇídeˇných dat. Druhá cˇást pak provádí postupné slévání teˇchto beˇhu˚, dokud nevznikne beˇh jediný, který reprezentuje setrˇídeˇná data. Algoritmy se však liší tím, jakým zpu˚sobem beˇhy generují a jak je slévají. 3.1
Nejjednodušší metodou je prˇímocˇaré generování beˇhu˚
pomocí jednoho bufferu1, jehož velikost je zvolena tak, aby
využíval veškerou dostupnou interní pameˇt’. Buffer je poté
naplneˇn vstupními daty a setrˇídeˇn vhodnou metodou
interního trˇídeˇní, naprˇíklad Quicksortem [
Na první pohled by se mohlo zdát, že není možné generovat beˇhy delší, než je velikost vnitrˇní pameˇti. Existuje drobné vylepšení, které zajišt’uje generování beˇhu˚ veˇtších délek, pokud jsou vstupní data vhodneˇ koncipována. Tato metoda používá dveˇ prioritní fronty (typicky reprezentované 2-regulárními haldami), které se deˇlí o veškerou dostupnou pameˇt’.
Na pocˇátku zabírá první halda veškerou pameˇt’ a je zcela naplneˇna daty ze vstupního souboru. V každém kroku je z haldy odebráno minimum a zapsáno do práveˇ generovaného beˇhu na disku. Jako náhrada za toto minimum je ze vstupního souboru nacˇten další prvek. Pokud je tento prvek veˇtší nebo roven prvku práveˇ zapsanému do výstupního beˇhu, mu˚že být nový prvek zacˇleneˇn do první haldy. Pokud je veˇtší, první halda zmenší svou velikost o jedna a prvek je vložen do haldy druhé, která se tím zárovenˇ zveˇtší. Generování beˇhu koncˇí v okamžiku, kdy je první halda vycˇerpána a druhá zabírá celou pameˇt’. V tomto okamžiku se prohodí význam obou hald a mu˚že zacˇít generování dalšího beˇhu.
Experimenty na náhodneˇ usporˇádaných datech s uniformním rozložením ukazují, že beˇhy generované pomocí dvou hald mají v pru˚meˇru dvojnásobnou délku, než je velikost dostupné pameˇti. 3.2
Prˇedpokládejme, že daný systém je schopen otevrˇít nejvýše N souboru˚, resp. mu˚že soucˇasneˇ používat nejvýše N 1Z du˚vodu nedostatku vhodné terminologie budeme v tomto cˇlánku používat anglický termín buffer v jeho pocˇešteˇné podobeˇ.
Obrázek 1: Princip dvoufázového trˇídeˇní pásek. Nejjednodušší implementace slévání beˇhu˚ potom využívá N − 1 souboru˚ jako vstup a jeden soubor pro uchování výstupu. Na pocˇátku jsou prˇi generování beˇhy rozdistribuovány rovnomeˇrneˇ mezi vstupní soubory. Proces slévání pak pracuje iterativneˇ a každá iterace má dveˇ fáze. V první fázi slévá soucˇasneˇ beˇhy z N − 1 souboru˚ a výsledné beˇhy zapisuje do výstupního souboru. V druhé fázi je prˇecˇten celý výstupní soubor a beˇhy z neˇj jsou rovnomeˇrneˇ rozdistribuovány mezi vstupní soubory. Algoritmus koncˇí, když ve výstupním souboru zu˚stane pouze jeden beˇh.
Proces slévání je znázorneˇn na obrázku 1. Samotné slévání probíhá ve vnitrˇní pameˇti a je možné jej implementovat naprˇíklad pomocí prioritní fronty (tzn. haldy), která si udržuje první dosud nezpracovaný prvek z každého beˇhu.
Hlavní nevýhodou tohoto postupu je nutnost provádeˇt opeˇtovnou redistribuci beˇhu˚ ve druhé fázi každé iterace. Jedním z možných rˇešení, je použít pouze N/2 souboru˚ jako vstupních a generované beˇhy distribuovat rovnou mezi N/2 výstupních souboru˚. Tento postup má ale nevýhodu v tom, že slévá vždy pouze N/2 beˇhu˚ místo N − 1 beˇhu˚, díky cˇemuž mu˚že potrˇebovat veˇtší množství iterací.
Hlavní nevýhodu dvoufázového trˇídeˇní do jisté míry rˇeší polyfázové trˇídeˇní. Jeho idea spocˇívá v nerovnomeˇrné distribuci beˇhu˚, která je chytrˇe navržena tak, aby bylo možné beˇhy neustále slévat bez jejich opeˇtovného rozhazování. Prˇitom je vždy N − 1 souboru˚ používáno jako vstupních a výsledné beˇhy se ukládají do jednoho souboru.
Cílem je, aby prˇi posledním slévání byl v každém z N − 1 vstupních souboru˚ práveˇ jeden beˇh. V takovém prˇípadeˇ probeˇhne poslední krok slévání optimálním zpu˚sobem. Pocˇátecˇní rozložení beˇhu˚ lze dopocˇítat reverzním naplánováním všech iterací slévání od optimální koncové konfigurace. Situace pro N = 3 a 21 pocˇátecˇních beˇhu˚ je znázorneˇna v následující tabulce.
soubor zacˇ. #1 #2 #3 #4 #5 #6 #1 #2 #3 13 8 0 5 0 8 0 5 3 3 2 0 1 0 2 0 1 1 1 0 0
Tabulka 1: Optimální slévání 21 beˇhu˚ pro N = 3 Na pocˇátku je v prvním souboru 13 beˇhu˚ a ve druhém 8. V každém kroku se vezme nejvyšší možný pocˇet beˇhu˚, který je možný slít prˇímo (naprˇ. v prvním kroku 8), cˇímž se Revize metod externího trˇídeˇní pro moderní hadware vždy práveˇ jeden soubor uvolní. V prˇípadeˇ dvou vstupních a jednoho výstupního souboru je rozložení beˇhu˚ založeno na Fibonacciho cˇíslech. 4
V této sekci nastíníme nové prˇedpoklady o hardware, zejména o pevných discích, a na jejich základeˇ opravíme existující algoritmy vneˇjšího trˇídeˇní. 4.1
Na základeˇ empirických pozorování, jejichž nejdu˚ležiteˇjší výsledky jsou shrnuty v sekci 5, mu˚žeme postulovat následující prˇedpoklady: • Soudobé magnetické disky sice stále preferují sekvencˇní prˇístup, avšak pokud je k datu˚m prˇistupováno po dostatecˇneˇ velkých blocích (rˇádoveˇ jednotky až desítky MB), je možné aplikovat nad teˇmito bloky náhodný prˇístup bez výrazného poklesu výkonu. U SSD disku˚ je možné používat i bloky menší. • Pru˚meˇrná rychlost cˇtení a zápisu výrazneˇ pˇrevyšuje rychlost vnitrˇního sériového trˇídeˇní a je srovnatelná s rychlostí paralelního vnitrˇního trˇídeˇní (na beˇžneˇ dostupném hardware). • Použití prioritní fronty (resp. haldy) k vnitrˇnímu trˇídeˇní je výrazneˇ pomalejší než použití Quicksortu. • Soudobé operacˇní systémy zvládají bez problému˚ pracovat i s tisíci otevrˇenými soubory soucˇasneˇ. • Pomeˇr velikosti vnitrˇní a vneˇjší pameˇti je na beˇžných hardwarových konfiguracích menší než 1 : 1000.
Z výše uvedených prˇedpokladu˚ vyplývají dveˇ veˇci. Externí trˇídeˇní již není potrˇeba optimalizovat na pocˇet diskových operací, nebot’ za beˇžných podmínek je možné provést slévání všech vygenerovaných beˇhu˚ najednou. Díky tomu je každý prvek práveˇ dvakrát cˇten z disku a práveˇ dvakrát na disk zapsán. Za druhé, možnost paralelního zpracování trˇídeˇných dat ve vnitrˇní pameˇti je výrazneˇ du˚ležiteˇjší pro budoucí škálovatelnost, protože rychlost pevných disku˚ již prˇesáhla propustnost trˇídicích algoritmu˚ pro vnitrˇní pameˇt’.
Základní koncept externího trˇídeˇní zu˚stává nadále nezmeˇneˇn. Každý algoritmus má tedy dveˇ cˇásti – generování beˇhu˚ a jejich následné slévání. Tyto cˇásti jsou do jisté míry nezávislé, a proto se jim mu˚žeme veˇnovat samostatneˇ.
Prˇi generování beˇhu˚ jsme empiricky oveˇrˇili, že použití dvou hald sice vede k vytvorˇení menšího pocˇtu delších beˇhu˚, avšak tento proces je výrazneˇ pomalejší než použití optimalizovaných algoritmu˚. Hledání minima pomocí haldy navíc není možné (na rozdíl od ostatních trˇídicích algoritmu˚) jednoduše paralelizovat. V tomto okamžiku se jako nejvíce vhodný algoritmus jeví rozdeˇlení pameˇti na dva (prˇípadneˇ trˇi) stejneˇ velké úseky, prˇicˇemž data v jednom úseku jsou trˇídeˇna zatím co data ve druhém (a prˇípadneˇ trˇetím) úseku jsou prˇenášena z disku nebo na disk. Jako algoritmus vnitrˇního trˇídeˇní poslouží nejlépe paralelní verze Quicksortu.
Jak jsme již naznacˇili, samotný proces slévání je za
beˇžných okolností možné provést v jediném kroku. Pokud je
vnitrˇní pameˇt’ rˇádoveˇ prˇibližneˇ tisíckrát menší než nejveˇtší
možná data ve vneˇjší pameˇti, pak první cˇást trˇídeˇní
vygeneruje nejvýše tisíc beˇhu˚, které mu˚žeme mít uloženy v
tisíci nezávislých souborech. K samotnému slévání potom
mu˚žeme použít bud’ prioritní frontu, jak navrhuje Knuth
[
Experimenty byly provádeˇny na beˇžném PC s procesorem Core i7 (4 fyzická, 8 logických jader) vybaveném 16 GB RAM. Data byla uložena na samostatném disku (1 TB, 7200 otácˇek) a druhý (identický) disk byl použit pro docˇasné soubory s vygenerovanými beˇhy. Testovací data reprezentoval soubor 32 bitových celocˇíselných hodnot, které byly náhodneˇ vygenerovány s uniformním rozdeˇlením.
První sada experimentu˚ zkoumá pomeˇr cˇasu˚ potrˇebných k setrˇídeˇní bloku dat pomocí interního trˇídeˇní a cˇasy potrˇebné k prˇecˇtení resp. zapsaní teˇchto dat na disk. Obrázek 2 prezentuje nameˇrˇené cˇasy pro ru˚zneˇ velké bloky dat a srovnává jednovláknové trˇídeˇní Quicksortem s jeho paralelní verzí. Z výsledku˚ je patrné, že cˇasy diskových operací jsou výrazneˇ nižší, než doba potrˇebná k setrˇídeˇní dat pomocí jednoho jádra a prˇibližneˇ srovnatelné s trˇídeˇním, které využívá všech 8 logických jader procesoru. Další experimenty se týkají generování beˇhu˚. V teˇchto experimentech byl použit vstupní soubor o velikosti 64 GB (16 miliard cˇísel) a buffer pro vnitrˇní trˇídeˇní o velikosti 1 GB (tedy pro 256 milionu˚ cˇísel). Tyto experimenty srovnávají sériový prˇístup, který realizuje všechny diskové operace i trˇídeˇní v jediném vlákneˇ, paralelní prˇístup, který provádí diskové operace sérioveˇ, ale ke trˇídeˇní dat využívá všechna dostupná vlákna, prˇístup založený na pipeline, který provádí diskové operace asynchronneˇ a zárovenˇ trˇídí paralelneˇ, a konecˇneˇ generování beˇhu˚ pomocí dvou hald. 19738.6 2119.51 5243.34 3194.01
1250 serial I/O serial parallel pipeline 2−heap
Obrázek 3: Cˇ asy potrˇebné pro generování beˇhu˚
Metoda generování beˇhu˚ pomocí dvou hald má sice
pozitivní dopad na délku (a tedy i pocˇet) beˇhu˚ [
Obrázek 4: Celkové cˇasy externího trˇídeˇní
Celkové cˇasy trˇídeˇní potom prezentuje obrázek 4. Ke slévání beˇhu˚ byl použit mechanismus vícecestného slévání pomocí 2-regulární haldy. Slévání 128 beˇhu˚ , které vygenerovaly první trˇi metody trvalo prˇibližneˇ 2400 sekund, zatímco slévání 64 beˇhu˚ vygenerovaných pomocí dvou hald trvalo 3100 sekund. Tento prˇekvapivý výsledek se nám zatím nepodarˇilo uspokojiveˇ vysveˇtlit. 6
Záveˇr V tomto cˇlánku jsme aktualizovali neˇkteré zažité prˇedpoklady týkající se vneˇjších pameˇtí a na jejich základeˇ jsme navrhli zmeˇny trˇídicích algoritmu˚ , které meˇly pozitivní dopad na výkon a budoucí škálovatelnost. Prokázali jsme, že pocˇet diskových operací již není hlavním kritériem optimalizace teˇchto algoritmu˚ , ale vývoj je trˇeba smeˇrˇovat do paralelních implementací. V pokracˇování této práce se chceme zameˇrˇit na vylepšení vícecestného slévání pro paralelní systémy a provést rozsáhlejší testy zejména za použití diskových polí a SSD disku˚ .