=Paper=
{{Paper
|id=None
|storemode=property
|title=Dosiahnutie vysokej dostupnosti v D-Boboxe
|pdfUrl=https://ceur-ws.org/Vol-1003/69.pdf
|volume=Vol-1003
|dblpUrl=https://dblp.org/rec/conf/itat/CermakZ13
}}
==Dosiahnutie vysokej dostupnosti v D-Boboxe==
https://ceur-ws.org/Vol-1003/69.pdf
ITAT 2013 Proceedings, CEUR Workshop Proceedings Vol. 1003, pp. 69–74
http://ceur-ws.org/Vol-1003, Series ISSN 1613-0073, c 2013 M. Čermák, F. Zavoral
Dosiahnutie vysokej dostupnosti v D-Boboxe
Miroslav Čermák a Filip Zavoral
Univerzita Karlova v Praze, Česká Republika
{cermak, zavoral}@ksi.mff.cuni.cz
Abstrakt: Prúdové spracovanie vel’kých dát v distribuova- 2. detekcia chyby
nom prostredí prináša radu rôznych výziev. Jednou z nich
3. výber uzlu ktorý preberie úlohy havarovaného
je dosiahnutie vysokej dostupnosti (high availability), čo
predstavuje zabezpečenie odolnosti distribuovaného vý- 4. obnovenie strateného stavu po výpadku
počtu proti výpadku uzlov z dôvodu hardvérovej, či soft-
vérovej chyby, alebo výpadku spojenia medzi uzlami. Vý- 5. zvládnut’ rozdelenie siete
padky sú problematické, pretože ich následkom dochádza V tejto práci najprv v kapitole 2 definujeme typy zo-
k narušeniu výpočtu – strate časti medzivýsledkov a strate tavenia podl’a [5], následne v kapitole 3 predstavíme zá-
stavu havarovaného uzlu. To je vo väčšine prípadov neak- kladné HA metódy zamerané primárne na body (1) a (4).
ceptovatel’né a je nutné začat’ spracovanie od začiatku, čo Následne predstavíme systém D-Bobox 4 a v kapitole 5
predlžuje výslednú dobu spracovania a spotrebováva hard- možnosti nasadenia HA v ňom.
vérové prostriedky. V tomto článku zhrnieme súčasný stav
poznania v oblasti dosiahnutia vysokej spol’ahlivosti pri
prúdovom spracovaní dát a navrhneme spôsob rozšírenia 2 Typy zotavenia
systému D-Bobox o podporu vysokej dostupnosti.
Základná požiadavka kladená na algoritmy zotavenia je
schopnost’ maskovat’ výpadky z pohl’adu dát tečúcich ha-
1 Úvod varovaným uzlom. Majme uzol U, ktorý má množinu ob-
sahujúcu n vstupných prúdov dát (I1 , .., In ) a produkuje
V poslednom čase je venovaná vel’ká pozornost’ novej výstupný prúd O. Výpočet e je postupnost’ udalostí ako
triede aplikácií - systémom pre spracovanie prúdových dát prijatie, spracovanie alebo vyprodukovanie n-tice dát. Vý-
(stream processing systems - SPS) [1, 2, 3], ktoré musia sledkom výpočtu e na uzle U je prúd dát Oe . Typy zotave-
spracovávat’ obrovské objemy neustále prúdiacich dát s nia [5] môžeme následne rozdelit’ podl’a spôsobu, akým
nízkou latenciou. Medzi takéto systémy môžeme zaradit’ sa snažia o dosiahnutie rovnosti O f +O’=O, kde O f je vý-
napr. spracovanie finančných dát v reálnom čase, monito- sledok výpočtu pred haváriou, O’ je výstup výpočtu po
rovanie pacientov pomocou rôznych senzorov, sledovanie zotavení z výpadku a O prúd dát pri behu bez výpadku.
a vyhodnocovanie stavu dopravy atd’. Prúdové spracova-
nie sa ukazuje ako efektívny nástroj nielen pre spracovanie Gap recovery je najjednoduchším a zároveň najmenej
priebežne generovaných dát, ale aj vel’kých statických dát, náročným spôsobom zotavenia. Po detekcii výpadku uzlu
ako napríklad sémantické databázy [4]. Zdroje dát SPS zabezpečí jeho nahradenie, avšak negarantuje zachovanie
systémov a spracovanie jednotlivých prúdov dát môžu byt’ vstupov a výstupov čo môže viest’ k strate dát. Výhodou je
distribuované, čo poskytuje priestor na škálovanie ich vý- rýchly čas zotavenia a minimálny vplyv na bezporuchový
konu. Takéto systémy nazveme distribuované SPS - DSPS. beh výpočtu.
Typickým postupom zvýšenia výkonu v distribuova-
nom systéme prúdového spracovania dát je pridanie d’al-
ších serverov. To avšak zvyšuje riziko výpadku, ktorý ne- Rollback recovery zaručuje, že výpadok nespôsobí stratu
gatívne ovplyvňuje výkon a spol’ahlivost’ celého distri- informácie. Podl’a typu dotknutých operátorov delíme
buovaného systému, pretože mnoho systémov požaduje rollback recovery d’alej na:
presné (databáze) a pravidelné výsledky (vyhodnocova- • opakujúci pokial’ sa pri obnove opakovane generujú
nie finančných operácií, sledovanie pacientov). V efektív- n-tice, ktoré sú zhodné s pôvodne odoslanými.
nom systéme sa preto stáva nevyhnutná prítomnost’ kom-
ponenty pre vysokú dostupnost’ (high availability - HA), • konvergujúci ak sú opakovane generované n-tice (z
ktorá umožňuje rýchle a korektné obnovenie a má mini- rovnakých dát), avšak tieto nie sú zhodné s pôvod-
málny dopad na bezvýpadkové spracovanie. nými, ale postupom času skonvergujú k n-ticiam behu
K dosiahnutiu HA v distribuovaných systémoch prúdo- bez výpadku.
vého spracovania dát je nutné poskytnút’ sadu algoritmov, • divergujúci pokial’ sa n-tice generované po zotavení
ktoré vykonávajú nasledujúce úlohy: nikdy neskonvergujú k n-ticiam ktoré by boli genero-
1. periodická a inkrementálna záloha (alebo replikácia) vané počas behu bez výpadku. Tento prípad typicky
stavu uzlov, na ktorých prebieha výpočet nastáva u nedeterministických operátorov.
70 M. Čermák, F. Zavoral
Precise recovery poskytuje najsilnejší spôsob zotavenia. riešia výstupné fronty, ktoré ukladajú správy dovtedy, kým
Kompletne maskuje výpadok a zaručuje že výstup je rov- nie je potvrdená záloha stavu, ktorý ich obsahuje.
naký ako v prípade bezchybného behu. Výhodou tohto prístupu je krátky čas potrebný na ob-
novenie výpočtu, ktorý zodpovedá opakovanému spraco-
vaniu správ prijatých od posledného checkpointu, avšak
2.1 Klasifikácia operátorov
za cenu spomalenia riadneho behu bez výpadkov z dô-
Podl’a vplyvu na sémantiku obnovenia rozlišujeme štyri vodu vyčlenenia (minimálne) polovice uzlov ako zálož-
typy operátorov: obecný, deterministický, konvergujúci a ných a zvýšenej komunikácie primárnych ulov so zálož-
opakovatel’ný. Typ plánu spracovania určuje najobecnejší nými. Ďalšie zdržanie výpočtu nastáva pri synchrónnom
operátor, ktorý sa v ňom vyskytuje. zálohovaní (primárny uzol neodosiela dáta dovtedy, kým
Operátor nazveme deterministický ak produkuje rov- nie sú uložene aj na záložnom uzle). Pri asynchrónnom
naký výstup stále, ked’ sa začne výpočet v rovnakom stave zálohovaní naproti tomu hrozí strata dát a nekonzistentný
a na rovnakej postupnosti vstupných dát na každom zo stav ak nie je použitá doplňujúca metóda na prevenciu
vstupov. Zdrojom nedeterminizmu môže byt’ napríklad zá- straty dát.
vislost’ na čase, poradí príchodu dát medzi jednotlivými
vstupmi, alebo použití nedeterministického spracovania 3.2 Active standby
(napríklad použitie náhodných veličín).
Deterministický operátor je konvergentný pokial’ je Active standby je d’alším variantom process-pairs [6, 5,
schopný po reštarte schopný konvergentného zotavenia, ak 7], ale na rozdiel od passive standby nečaká záložný uzol
obnovu začína z prázdneho stavu a za pomoci opakova- pasívne, ale dostáva rovnaké dáta ako primárny uzol a ak-
ného spracovania vstupných dát od určitého bodu v čase. tívne tieto dáta spracováva. Výstup záložného uzlu je na-
Konvergentný operátor je opakovatel’ný ak je schopný miesto odosielania logovaný. Pre dosiahnutie precízneho
po reštarte schopný opakovatel’ného zotavenia, ak obnovu obnovenia musí záložný uzol zistit’ identifikátory posled-
začína z prázdneho stavu a za pomoci opakovaného spra- ných správ, ktoré boli prijaté nasledujúcimi uzlami, aby
covania vstupných dát od určitého bodu v čase. nedošlo k duplicitnému poslaniu správ. Ak plán obsahuje
nedeterministické operátory je navyše nutné doplnit’ logo-
vanie rozhodnutí týchto operátorov a toto následne odosie-
3 Metódy HA lat’ na záložný uzol za cenu extra komunikácie.
Výhodou active standby oproti passive variante je mi-
Medzi základné prístupy dosiahnutia spol’ahlivosti spra- nimálny potrebný čas na obnovenie, pretože záložný uzol
covania v distribuovaných systémoch patria procesné páry dostáva rovnaké správy, ktoré paralelne spracováva. To má
(process-pairs), logovanie a checkpointing. V nasledujú- avšak za následok nárast komunikácie o 100% . Ďalšiu ex-
cich podkapitolách predstavíme základné algoritmy zalo- tra komunikáciu znamená potvrdzovanie prijatých správ,
žené na týchto postupoch. Aj ked’ v základných variantoch slúžiacich pre orezanie výstupných zásobníkov a v prípade
nedosahujú všetky uvedené postupy precíznej obnovy, je nedeterministických operátorov posielanie rozhodovacích
možné ich na takúto úroveň rozšírit’. Jedná sa hlavne o záznamov.
ošetrenie duplicitných stavov a zaručenie, že nedôjde k
strate správ. Zabezpečenie proti strate riešia všetky me-
tódy logovaním správ vo výstupných frontách dovtedy, 3.3 Upstream backup
kým nie je zaručené, že správa bola uložená alebo spraco- Klasické process pair prístupy majú vel’ký runtime over-
vaná. V prípade výpadku sa znovu posielajú takto zalogo- head (je nutné vyčlenit’ aspoň polovicu uzlov ako záložné
vané správy. Ošetrenie duplicitných správ sa rôzni a preto uzly) a vyžadujú nezanedbatel’né navýšenie komunikácie.
je spomenuté podrobnejšie pri jednotlivých metódach. Upstream backup [6, 5] je naproti tomu navrhnutý tak,
aby lepšie využil distribuovaný charakter prúdového spra-
3.1 Passive standby covania dát. Upstream uzly (uzly umiestnené proti prúdu
dát) slúžia ako zálohy pre downstream uzly (uzly d’alej po
Metóda passive standby [6, 5] je založená na process- prúde dát), pričom sa zálohujú iba n-tice posielané týmto
pairs prístupe. Ku každému primárnemu uzlu je prira- uzlom. V prípade výpadku uzlu, je tento nahradený novým
dený záložný uzol. Primárny uzol v pravidelných inter- uzlom s prázdnym stavom. Znovu spracovaním n-tic ulo-
valoch posiela aktualizáciu stavu na záložný. V prípade žených na upstream uzloch dôjde k obnoveniu stavu uzlu.
výpadku preberá záložný uzol výpočet a pokračuje od po- Hlavným problémom tohto prístupu je narastajúca vel’-
sledného checkpointu. Pre dosiahnutie precízneho obno- kost’ výstupných front, ktoré slúžia ako zálohy. Pre ich
venia je nutné zabezpečit’, aby neboli vygenerované dupli- zmenšenie je definovaný ich orezávací protokol (queue
citné dáta a opakovane spracovat’ správy prijaté havarova- trimming protocol), ktorý popisuje kedy môžu byt’ n-tice z
ným uzlom, ktoré nestihol reflektovat’ v zálohe. Prvý prob- jednotlivých výstupných front odstránené. Ciel’om je do-
lém je riešený opýtaním sa nasledujúcich uzlov na správy, siahnut’ minimálnu množinu, ktorá bude dostačujúca pre
ktoré prijali a tieto sa už nebudú posielat’. Druhý problém obnovenie stavu havarovaného uzlu. Orezávací protokol je
Dosiahnutie vysokej dostupnosti v D-Boboxe 71
založený na potvrdzovaní doručenia, resp. spracovania n- dzi viacero záložných znamená, že očakávaný nárast zá-
tic. Informácie o prijatí sú šírené spätne pomocou potvr- t’aže týchto záložných uzlov bude malý a oneskorenie vý-
dzovacích správ, pričom existuje niekol’ko úrovní týchto počtu bude pod kontrolou.
správ. Základná nultá úroveň oznamuje, že daná n-tica Ak dôjde k obnoveniu havarovaného uzlu, tento je pri-
bola prijatá príjemcom. Uzol, ktorý prijme potvrdenie nul- pojený ako nový prázdny uzol a v rámci automatického
tej úrovne, spätne vyráta ktoré vstupné n-tice sa podie- vyvažovania zát’aže môže byt’ na neho prevedená čast’
l’ali na vytvorení potvrdenej n-tice a pošle potvrdenie pr- úloh. Vytváranie jednotlivých HA jednotiek a ich roz-
vej úrovne. Uzol ktorý prijme potvrdenie prvej úrovne pre delenie na záložne servery môže prebiehat’ automaticky,
konkrétnu n-ticu od všetkých uzlov, kam bola odoslaná, bez nutnosti pevnej konfigurácie, čo umožňuje dynamické
môže následne odstránit’ túto a všetky logicky predchá- prispôsobenie sa aktuálnej situácii a rozloženiu zát’aže.
dzajúce n-tice. Pokial’ sa požaduje vyšší stupeň zabezpe-
čenia, iteratívne sa zvyšuje úroveň potvrdenia a orezávanie
prebieha pri prijatí najvyššej požadovanej úrovne. 4 D-Bobox
Výhodou tohto prístupu je zmenšenie nadmerného vy-
užívania prenosového pásma, ked’že navyše používa iba Bobox [9, 3] je framework pre vytváranie aplikácií ur-
potvrdzovacie správy, ktoré sú menšie než správy dátové a čených k spracovaniu vel’kých dát v paralelnom pro-
k extra prenosu dát dochádza len pri zasielaní n-tic po vý- stredí. Základný princíp spracovania je založený na roz-
padku. Nevýhodou je neúmerne dlhšia doba potrebná na delení úlohy na menšie, vzájomne prepojené časti, ktoré
zotavenie, ked’že nový uzol musí znovu spracovat’ dosta- môžu byt’ vykonávané nezávisle. Toto rozdelenie defi-
tok n-tic pre obnovenie svojho vnútorného stavu a nároč- nuje plán spracovania a je reprezentovaný ako acyklický
nost’ výpočtu potvrdení vyšších úrovní. orientovaný graf, v ktorom uzly (v Boboxe nazývané kra-
bičky) reprezentujú jednotlivé dielčie výpočty a oriento-
vané hrany reprezentujú tok dát. Dáta prúdia z jednotli-
3.4 Cooperative passive standby vých zdrojových krabičiek do výstupnej krabičky. Zdroje
Cooperative passive standby [8] je prístup založený na dát môžu byt’ nielen statického charakteru, ako napríklad
jemne členenom checkpointovaciom modeli. Ten je pou- databáze, ale aj dynamické ako rôzne senzory, kamery
žitý, pretože efektívne funguje pre väčšiu skupinu úloh a atd’. Táto univerzálnost’ umožňuje nasadenia Boboxu na
prípadov než ostatné alternatívy ako znovu spracovanie, či široké spektrum úloh.
redundantné spracovanie.
Plán(y) spracovania každého uzlu sú rozdelené do via-
cerých nezávislých HA jednotiek. Tieto sú následne roz-
distribuované a vybalansované medzi viacerými servermi.
Toto rozdelenie umožňuje rozložit’ zát’až zálohy jedného
uzlu medzi skupinu uzlov a týmto docielit’ rýchlejšiu ob-
novu v prípade výpadku.
Zálohovanie prebieha po jednotlivých HA jednotkách
na danom uzle, čo redukuje dĺžku blokovania výpočtu spô-
sobené zálohovaním HA jednotky. Jemnejšia granularita
záloh umožňuje využit’ vol’né cykly CPU daného uzlu,
ked’ práve neprebieha výpočet (napr. z dôvodu čakania na
dáta) a týmto optimalizovat’ celkový výkon. Samotná zá- Obr. 1: Architektúra systému D-Bobox.
loha prebieha v dvoch krokoch: capture a paste. Počas fázy
capture dôjde na uzle k výberu HA jednotky, ktorá sa bude D-Bobox [10] je d’alším evolučným krokom systému
zálohovat’ a odoslaniu správy na záložný uzol s aktualizá- Bobox, ked’ k zvýšeniu efektivity spracovania vel’kých dát
ciou stavu danej HA jednotky. Paste fáza prebieha na zá- už nepostačuje lokálny paralelizmus a je nutné expando-
ložnom uzle, ktorý spracúva doručené zálohovacie správy vat’ do distribuovaného prostredia. Zároveň je snaha za-
tak, že aktualizuje zodpovedajúci obraz checkpointu apli- chovat’ širokú použitel’nost’ takto rozšíreného systému a
kovaním rozdielových informácii. Po ukončení fázy paste preto je budovaný s ohl’adom na efektívnu použitel’nost’
je upovedomený odosielatel’ a môže dôjst’ k d’alšiemu aj na bežne dostupnom hardvéri a nielen na špecializova-
kolu zálohy tejto HA jednotky. ných výpočtových clustroch.
Po výpadku uzlu preberú jeho úlohu uzly obsahujúce Základná schéma D-Boboxu je znázornená na obrázku
zálohy jeho jednotlivých HA jednotiek. Počas obnovy 1. Uzly sú rozdelené na jeden hlavný - master uzol, ktorý
dôjde k operácii paste a spracovaniu nespracovaných aktu- prijíma požiadavku na úlohu, vytvára plán jej spracova-
alizácii, pokial’ také sú. Ďalej sú prepojeé vstupy z havaro- nia (frontend čast’), inicializuje podriadené - slave jed-
vaného uzla na záložné a spracované správy z výstupných notky na spracovanie a (typicky) je aj ciel’om výsledkov
front, ktoré boli odoslané havarovanému uzlu ale neobsa- spracovania. Podriadené uzly obsahujú štandardný bac-
huje ich záloha. Rozdelenie úlohy havarovaného uzlu me- kend z Boboxu a sú rozšírené o potrebnú distribučnú lo-
72 M. Čermák, F. Zavoral
a)
b)
Obr. 2: Ukážka rozšírenia exekučného plánu do distribuovaného prostredia pomocou hraničných krabičiek. a) Bobox plán
pre výpočet na jednom uzle. b) Plán D-Boboxu, rozšírený o hraničné krabičky (Boundary Box), ktoré zaist’ujú vzdialenú
komunikáciu (prerušovane).
giku. Vzdialená komunikácia je riešená pridaním špecia- Active standby je naproti tomu maximálne transpa-
lizovaných hraničných krabičiek, ktoré sú do výsledného rentný a takéto spracovanie môže byt’ dokonca zachy-
plánu pridávané za behu, tesne pred inicializovaním pra- tené upraveným plánom spracovania, kde budú jednotlivé
covných uzlov. Pridáva a konfiguruje ich distribučná ria- časti spracovania zduplikované a výstupy paralelných ve-
diaca jednotka na primárnom uzle podl’a aktuálnej dostup- tiev budú smerované na špeciálnu systémovú krabičku,
nosti uzlov zúčastňujúcich sa výpočtu. Príklad takéhoto ktorá zabezpečí opätovné poslanie dát tak, aby po výpadku
rozšírenia exekučného plánu ilustruje obrázok 2. nedošlo k strate dát (ak výpočet v primárnej vetve zaostá-
val za záložnou) a ani k produkcii duplicitných n-tic (ak
výpočet v záložnej vetve zaostával za primárnou vetvou).
5 HA a D-Bobox Úlohou riadiacej časti HA je v prípade výpadku nájst’ náh-
radný uzol za havarovaný, ktorý preberie úlohu záložného
5.1 Základné algoritmy a D-Bobox
uzlu, zreplikovat’ na neho stav zo záložnej vetvy (po vý-
Každý z HA algoritmov spomenutých v predchádzajúcej padku sa z nej stáva vetva primárna) a vhodne presmero-
kapitole je nasaditelný v systéme D-Bobox, avšak kladie vat’ komunikačné kanály. Tento HA algoritmus môže slú-
rôzne požiadavky na samotný systém a poskytuje rôznu žit’ pre úlohy preferujúce minimálny čas zotavenia pred
úroveň transparentnosti z pohl’adu tvorby nových operá- výkonom, pretože je nutné obetovat’ polovicu uzlov ako
torov (krabičiek v systéme Bobox). V nasledujúcej disku- uzly záložné. Rovnaká nevýhoda platí pre passive standby
sii neberieme do úvahy nedeterministické plány, ktoré pre algoritmus, ktorý navyše nedosahuje podobne rýchle ob-
všetky algoritmy vynucujú zo strany krabičiek podporu lo- novenia, z dôvodu opätovného spracovania správ ktoré ne-
govania nedeterministických rozhodnutí a tieto vhodným zachytil posledný checkpoint a spomalenia výpočtu počas
spôsobom reportovat’, čo znižuje požadovanú transparen- vykonávania zálohy. Z tohto dôvodu nie je táto možnost’
tnost’. uvažovaná pre Bobox.
Upstream backup predstavuje najmenej blokujúci prí- Kooperatívny variant passive standby patrí takisto me-
stup a vyžaduje najmenšiu extra komunikáciu počas behu dzi transparentné metódy a jeho výhodou je rozumne malý
bez výpadkov, avšak jeho nároky na ukladanie výstupných vplyv na bezporuchový beh a rýchlost’ zotavenia z vý-
front môžu byt’ neúnosne vel’ké a cena obnovy uzlu v prí- padku. Preto poslúži ako základ pre integráciu HA v sys-
pade výpadku je vel’ká z pohl’adu času aj potrebného vý- téme D-Bobox.
počtového výkonu. Navyše predstavuje najmenej transpa-
rentný prístup, pretože jednotlivé operátory musia imple- 5.2 Integrácia HA v D-Boboxe
mentovat’ často netriviálne mapovania medzi výstupnými
a vstupnými n-ticami, ktoré je potrené pre korektné fungo- Podpora HA je z pohl’adu umiestnenia rozdelená na dva
vanie potvrdzovania a orezávacieho algoritmu na výstupné časti: lokálnu, umiestnenú na jednotlivých pracovných
fronty. Preto je nevhodný pre Bobox, ktorý sa snaží maxi- uzloch a globálnu, nachadzajúcu sa na primárnom uzle.
málne skryt’ paralelizačnú a distribučnú logiku z krabičiek Obe časti sú reprezentované zodpovedajúcim managerom
za účelom ich jednoduchého vývoja. a riešia odlišné úlohy: lokálny manager rieši správu HA v
Dosiahnutie vysokej dostupnosti v D-Boboxe 73
kontexte jedného uzlu a globálny riadi HA na úrovni ce- za havarovaný a jeho výpadok je oznámený globálnemu
lého systému. HA managerovi, ktorý sa ujme riadenia nápravy tohto vý-
padku.
Počas behu bez výpadkov sú vykonávané operácie cap-
HA manager na primárnom uzle je tzv. globálny HA
ture a paste. Capture má za úlohu zachytit’ zmenu stavu
manager. Jeho zameraním je riešenie globálnych úloh
konkrétnej HA jednotky a jej odoslanie na záložný ser-
ohl’adne poskytnutia spol’ahlivosti a efektívneho výpočtu:
ver. Operácia paste ma za úlohu aktualizovat’ obrazy záloh
riešenie výpadkov, rozvrhovanie záloh a spolupráca s vy-
pomocou doručených správ. Jednotlivé HA jednotky sú
važovaním zát’aže.
zálohované pomocou operácie capture nezávisle na sebe,
V prípade výpadku je nutné informovat’ uzly držiace zá-
zatial’ čo počas operácie paste sa zálohy aktualizujú po-
lohy jednotlivých HA jednotiek havarovaného uzlu, aby
stupne podl’a poradia prijatých správ dovtedy, kým sú ne-
vykonali paste operáciu doručených aktualizácií, ak tak
jaké nespracované aktualizačné správy, alebo pokial’ ne-
ešte nevykonali a prebrali výpočet havarovaných jedno-
dôjde k preplánovaniu. Plánovanie operácií capture a paste
tiek. Pre pokračovanie výpočtu je ešte nutné presmerovat’
má na starosti lokálny plánovač. Tento môže implemento-
posielanie správ na záložné uzly a informovat’ upstream
vat’ rôzne stratégie za účelom rozumne zálohovat’, alebo
uzly, aby odoslali uložené správy zo svojich výstupných
minimalizovat’ blokovanie výpočtu.
front pre obnovenie stavu výpočtu, ktorý nestihol byt’ za-
Pre úpravu granularity checkpointingu umožnuje lo-
chytený posledným checkpointom.
kálny HA manager delenie, resp. zlučovanie HA jedno-
Vzhl’adom na snahu o rozdelenie úlohy jedného uzlu na
tiek. Delenie je možné v prípade, ak uzol pracuje s viace-
viac nezávislých HA jednotiek, ktoré sú distribuované na
rými krabičkami (nie nutne priamo prepojenými). Zjem-
rôzne fyzické uzly, môžeme očakávat’, že nárast zát’aže
nením granularity, hlavne u plánov obsahujúcich viacero
týchto uzlov po tom ako preberú úlohu havarovaného uzlu
netriviálnych operácií, dôjde k rozdeleniu zát’aže zálohy
bude v akceptovatel’ných medziach. Po obnovení havaro-
a obnovenia na viacero záložných serverov. Naopak zlú-
vaného uzlu je tento pripojený k výpočtu a môžu byt’ na
čenie je vhodné pokial’ sa na uzle ocitne niekol’ko za se-
neho dynamicky preplánované úlohy a zálohy, typicky z
bou idúcich výpočtovo jednoduchých krabičiek, ktorých
uzlov ktoré sú najviac vyt’ažené (avšak je možné nasadit’
spojené vykonávanie nepredstavuje výrazný nárast zát’aže
rôzne stratégie zahŕňajúce napríklad lokalitu, cenu atd’.).
(skôr dôjde k rýchlejšiemu spracovaniu vd’aka lokalite vy-
Hlavným dôvodom, prečo by sa HA manager mal snažit’
konávania) a zmenši počet HA jednotiek, ktoré je potrebné
o vyrovnávanie zát’aže, je snaha dosiahnut’ rozumne malé
plánovat’. Tieto zmeny granularity sa musia vykonávat’ v
a časté zálohy všetkých uzlov. Pri nerovnomernej zát’aži
spolupráci s globálnym HA managerom, ktorý musí no-
nevyt’ažené uzly produkujú zálohy častejšie čím pridávajú
vým HA jednotkám priradit’ uzly, kam sa budú zálohovat’
úlohy vyt’aženým uzlom. Tieto naopak, aby nezdržovali
a naopak zabezpečit’ odstránenie záloh zrušených HA jed-
výpočet redukujú interval svojich záloh a zálohy vykoná-
notiek.
vané po dlhšom čase bývajú obecne drahšie a obnovenia
pomalšie, pretože došlo k väčším zmenám stavu, ktoré je
treba pokryt’. Snaha o dynamické vyrovnanie zát’aže zni- HA na hraničných krabičkách musí pre garanciu pre-
žuje cenu checkpointov, ked’že tieto sú menšie a tak sa cíznej obnovy podporovat’ logovanie výstupných správ a
s väčšou pravdepodobnost’ou vojdú do vol’ných cyklov elimináciu duplicitných správ. Odchádzajúce správy sa lo-
CPU a sú častejšie čo skracuje čas obnovy, ked’že je nutné gujú do doby, než je potvrdená ich záloha v HA jednot-
znovu spracovat’ menší počet n-tic pre obnovenie stavu. kách ktorým boli odoslané. Toto je nutné pre obnovenie
Vyrovnávanie zát’aže dociel’uje HA manager dvoma spô- stavu výpočtu po obnove z posledného checkpointu pomo-
sobmi: vhodným rozvrhovaním zálohovacích párov a spo- cou ich opakovaného spracovania. Vstupné hraničné kra-
luprácou s riadiacou distribučnou jednotkou, ktorá riadi bičky musia taktiež pomocou identifikátorov správ filtro-
vyvažovanie pomocou migrácie úloh. vat’ správy duplicitné, ktoré mohli pri opakovanom spra-
covaní vzniknút’ (havarovaný uzol mohol a nemusel vy-
produkovat’ pôvodné správy pred svojím pádom).
HA manager na sekundárnom uzle je lokálny manager. Integrovanie spomenutých častí poskytne základnú pod-
Má za úlohu riešit’ HA úlohy spojené s konkrétnym uzlom poru vysokej dostupnosti v systéme D-Bobox. Táto môže
medzi ktoré patrí: sledovanie dostupnosti susedov (ups- byt’ následne rozširená o podporu nedeterministických
tream a downstream uzlov), správa HA jednotiek (delenie, operátorov za pomoci logovania ich rozhodnutí, alebo na-
zlučovanie) a plánovanie a vykonávanie operácií capture a príklad vylepšovaná pridaním rôznych stratégií pri pláno-
paste. vaní záloh, či vyvažovaní zát’aže.
Každý uzol sleduje dostupnost’ susedných uzlov s kto-
rými komunikuje. Pokial’ s nejakým susedným uzlom
práve neprebieha komunikácia (netečú dáta), tak testuje 6 Záver
jeho dostupnost’ pomocou dotazov v pravidelných inter-
valoch. Ak nejaký uzol prestane reagovat’, je po niekol’- V tomto článku sme prezentovali problém výpadku uzlu
kých pokusoch (podl’a nastavenej tolerancie) prehlásený v distribuovaných systémoch prúdového spracovania dát,
74 M. Čermák, F. Zavoral
definovali typy obnovenia a prezentovali súčasné základné M. Malgeri, and R. Unland, Eds. Springer Berlin Hei-
prístupy k dosiahnutiu vysokej dostupnosti týchto systé- delberg, 2013, vol. 446, pp. 149–154. [Online]. Available:
mov. Následne sme rozobrali vhodnost’ jednotlivých prí- http://dx.doi.org/10.1007/978-3-642-32524-3_19
stupov pre systém D-Bobox a zvolili jeden z prístupov ako [10] M. Cermak, Z. Falt, and F. Zavoral, “D-bobox: O distribu-
základný kameň, na ktorom bude zavedená podpora vyso- ovatelnosti boboxu,” in Informačné Technológie - Aplikácie
kej dostupnosti v D-Boboxe a načrtli možnosti jej integrá- a Teória. PONT s. r. o., 2012, pp. 41–46.
cie do jednotlivých časti D-Boboxu.
7 Pod’akovanie
Článok bol podporovaný Grantovou agentúrou Univerzity
Karlovy, projekt č. 472313, grantom SVV-2013-267312, a
projektom GAČR č. P103/13/08195S.
Literatúra
[1] D. J. Abadi, Y. Ahmad, M. Balazinska, U. Cetintemel,
M. Cherniack, J.-H. Hwang, W. Lindner, A. S. Maskey,
A. Rasin, E. Ryvkina et al., “The design of the borealis
stream processing engine.” CIDR, 2005.
[2] D. Abadi, D. Carney, U. Cetintemel, M. Cherniack, C. Con-
vey, C. Erwin, E. Galvez, M. Hatoun, A. Maskey, A. Rasin
et al., “Aurora: a data stream management system,” in Pro-
ceedings of the 2003 ACM SIGMOD international confe-
rence on Management of data. ACM, 2003, pp. 666–666.
[3] D. Bednarek, J. Dokulil, J. Yaghob, and F. Zavoral, “Bo-
box: Parallelization Framework for Data Processing,” in
Advances in Information Technology and Applied Compu-
ting, 2012.
[4] Z. Falt, J. Dokulil, M. Cermak, and F. Zavoral, “Parallel
sparql query processing using bobox,” International Jour-
nal On Advances in Intelligent Systems, vol. 5, no. 3, pp.
302–314, 2012.
[5] J.-H. Hwang, M. Balazinska, A. Rasin, U. Cetintemel,
M. Stonebraker, and S. Zdonik, “High-availability algo-
rithms for distributed stream processing,” in Data Engine-
ering, 2005. ICDE 2005. Proceedings. 21st International
Conference on, 2005, pp. 779–790.
[6] J. hyon Hwang, M. Balazinska, A. Rasin, U. Çetintemel,
M. Stonebraker, and S. Zdonik, “A comparison of stream-
oriented high-availability algorithms,” Brown CS, Tech.
Rep., 2003.
[7] M. A. Shah, J. M. Hellerstein, and E. Brewer, “Highly
available, fault-tolerant, parallel dataflows,” in Proceedings
of the 2004 ACM SIGMOD international conference on
Management of data, ser. SIGMOD ’04. New York,
NY, USA: ACM, 2004, pp. 827–838. [Online]. Available:
http://doi.acm.org/10.1145/1007568.1007662
[8] J.-H. Hwang, Y. Xing, U. Cetintemel, and S. Zdonik,
“A cooperative, self-configuring high-availability solution
for stream processing,” in Data Engineering, 2007. ICDE
2007. IEEE 23rd International Conference on. IEEE,
2007, pp. 176–185.
[9] D. Bednárek, J. Dokulil, J. Yaghob, and F. Zavo-
ral, “Data-flow awareness in parallel data processing,”
in Intelligent Distributed Computing VI, ser. Studies
in Computational Intelligence, G. Fortino, C. Badica,