<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta>
      <journal-title-group>
        <journal-title>Series</journal-title>
      </journal-title-group>
      <issn pub-type="ppub">1613-0073</issn>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.1007/978-3-642-32524-3_19</article-id>
      <title-group>
        <article-title>Dosiahnutie vysokej dostupnosti v D-Boboxe</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Miroslav Cˇermák a Filip Zavoral</string-name>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Univerzita Karlova v Praze</string-name>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Cˇ eská Republika</string-name>
        </contrib>
        <contrib contrib-type="author">
          <string-name>cermak</string-name>
        </contrib>
        <contrib contrib-type="author">
          <string-name>zavoral}@ksi.mff.cuni.cz</string-name>
        </contrib>
      </contrib-group>
      <pub-date>
        <year>2013</year>
      </pub-date>
      <volume>1003</volume>
      <fpage>69</fpage>
      <lpage>74</lpage>
      <abstract>
        <p>Abstrakt: Prúdové spracovanie vel'kých dát v distribuovanom prostredí prináša radu rôznych výziev. Jednou z nich je dosiahnutie vysokej dostupnosti (high availability), cˇo predstavuje zabezpecˇenie odolnosti distribuovaného výpocˇtu proti výpadku uzlov z dôvodu hardvérovej, cˇi softvérovej chyby, alebo výpadku spojenia medzi uzlami. Výpadky sú problematické, pretože ich následkom dochádza k narušeniu výpocˇtu - strate cˇasti medzivýsledkov a strate stavu havarovaného uzlu. To je vo väcˇšine prípadov neakceptovatel'né a je nutné za cˇat' spracovanie od za cˇiatku, cˇo predlžuje výslednú dobu spracovania a spotrebováva hardvérové prostriedky. V tomto cˇlánku zhrnieme súcˇasný stav poznania v oblasti dosiahnutia vysokej spol'ahlivosti pri prúdovom spracovaní dát a navrhneme spôsob rozšírenia systému D-Bobox o podporu vysokej dostupnosti. V poslednom cˇase je venovaná vel'ká pozornost' novej triede aplikácií - systémom pre spracovanie prúdových dát (stream processing systems - SPS) [ 1, 2, 3], ktoré musia spracovávat' obrovské objemy neustále prúdiacich dát s nízkou latenciou. Medzi takéto systémy môžeme zaradit' napr. spracovanie financˇných dát v reálnom cˇase, monitorovanie pacientov pomocou rôznych senzorov, sledovanie a vyhodnocovanie stavu dopravy atd'. Prúdové spracovanie sa ukazuje ako efektívny nástroj nielen pre spracovanie priebežne generovaných dát, ale aj vel'kých statických dát, ako napríklad sémantické databázy [4]. Zdroje dát SPS systémov a spracovanie jednotlivých prúdov dát môžu byt' distribuované, cˇo poskytuje priestor na škálovanie ich výkonu. Takéto systémy nazveme distribuované SPS - DSPS. Typickým postupom zvýšenia výkonu v distribuovanom systéme prúdového spracovania dát je pridanie d'alších serverov. To avšak zvyšuje riziko výpadku, ktorý negatívne ovplyvnˇuje výkon a spol'ahlivost' celého distribuovaného systému, pretože mnoho systémov požaduje presné (databáze) a pravidelné výsledky (vyhodnocovanie financˇných operácií, sledovanie pacientov). V efektívnom systéme sa preto stáva nevyhnutná prítomnost' komponenty pre vysokú dostupnost' (high availability - HA), ktorá umož nˇuje rýchle a korektné obnovenie a má minimálny dopad na bezvýpadkové spracovanie. K dosiahnutiu HA v distribuovaných systémoch prúdového spracovania dát je nutné poskytnút' sadu algoritmov, ktoré vykonávajú nasledujúce úlohy:</p>
      </abstract>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>1. periodická a inkrementálna záloha (alebo replikácia)
stavu uzlov, na ktorých prebieha výpocˇet</p>
    </sec>
    <sec id="sec-2">
      <title>2. detekcia chyby</title>
    </sec>
    <sec id="sec-3">
      <title>3. výber uzlu ktorý preberie úlohy havarovaného</title>
    </sec>
    <sec id="sec-4">
      <title>4. obnovenie strateného stavu po výpadku</title>
    </sec>
    <sec id="sec-5">
      <title>5. zvládnut’ rozdelenie siete</title>
      <p>
        V tejto práci najprv v kapitole 2 definujeme typy
zotavenia podl’a [
        <xref ref-type="bibr" rid="ref5">5</xref>
        ], následne v kapitole 3 predstavíme
základné HA metódy zamerané primárne na body (1) a (4).
Následne predstavíme systém D-Bobox 4 a v kapitole 5
možnosti nasadenia HA v nˇom.
2
      </p>
      <sec id="sec-5-1">
        <title>Typy zotavenia</title>
        <p>
          Základná požiadavka kladená na algoritmy zotavenia je
schopnost’ maskovat’ výpadky z pohl’adu dát te cˇúcich
havarovaným uzlom. Majme uzol U, ktorý má množinu
obsahujúcu n vstupných prúdov dát (I1, .., In) a produkuje
výstupný prúd O. Výpocˇet e je postupnost’ udalostí ako
prijatie, spracovanie alebo vyprodukovanie n-tice dát.
Výsledkom výpocˇtu e na uzle U je prúd dát Oe. Typy
zotavenia [
          <xref ref-type="bibr" rid="ref5">5</xref>
          ] môžeme následne rozdelit’ podl’a spôsobu, akým
sa snažia o dosiahnutie rovnosti O f +O’=O , kde O f je
výsledok výpocˇtu pred haváriou, O’ je výstup výpocˇtu po
zotavení z výpadku a O prúd dát pri behu bez výpadku.
Gap recovery je najjednoduchším a zárovenˇ najmenej
nárocˇným spôsobom zotavenia. Po detekcii výpadku uzlu
zabezpecˇí jeho nahradenie, avšak negarantuje zachovanie
vstupov a výstupov cˇo môže viest’ k strate dát. Výhodou je
rýchly cˇas zotavenia a minimálny vplyv na bezporuchový
beh výpocˇtu.
        </p>
        <p>Rollback recovery zarucˇuje, že výpadok nespôsobí stratu
informácie. Podl’a typu dotknutých operátorov delíme
rollback recovery d’alej na:
• opakujúci pokial’ sa pri obnove opakovane generujú
n-tice, ktoré sú zhodné s pôvodne odoslanými.
• konvergujúci ak sú opakovane generované n-tice (z
rovnakých dát), avšak tieto nie sú zhodné s
pôvodnými, ale postupom cˇasu skonvergujú k n-ticiam behu
bez výpadku.
• divergujúci pokial’ sa n-tice generované po zotavení
nikdy neskonvergujú k n-ticiam ktoré by boli
generované pocˇas behu bez výpadku. Tento prípad typicky
nastáva u nedeterministických operátorov.
Precise recovery poskytuje najsilnejší spôsob zotavenia.
Kompletne maskuje výpadok a zarucˇuje že výstup je
rovnaký ako v prípade bezchybného behu.
2.1</p>
        <sec id="sec-5-1-1">
          <title>Klasifikácia operátorov</title>
          <p>Podl’a vplyvu na sémantiku obnovenia rozlišujeme štyri
typy operátorov: obecný, deterministický, konvergujúci a
opakovatel’ný . Typ plánu spracovania urcˇuje najobecnejší
operátor, ktorý sa v nˇom vyskytuje.</p>
          <p>Operátor nazveme deterministický ak produkuje
rovnaký výstup stále, ked’ sa za cˇne výpocˇet v rovnakom stave
a na rovnakej postupnosti vstupných dát na každom zo
vstupov. Zdrojom nedeterminizmu môže byt’ napríklad
závislost’ na cˇase, poradí príchodu dát medzi jednotlivými
vstupmi, alebo použití nedeterministického spracovania
(napríklad použitie náhodných veli cˇín).</p>
          <p>Deterministický operátor je konvergentný pokial’ je
schopný po reštarte schopný konvergentného zotavenia, ak
obnovu zacˇína z prázdneho stavu a za pomoci
opakovaného spracovania vstupných dát od urcˇitého bodu v cˇase.</p>
          <p>Konvergentný operátor je opakovatel’ný ak je schopný
po reštarte schopný opakovatel’ného zotavenia, ak obnovu
zacˇína z prázdneho stavu a za pomoci opakovaného
spracovania vstupných dát od urcˇitého bodu v cˇase.
3</p>
          <p>Metódy HA
Medzi základné prístupy dosiahnutia spol’ahlivosti
spracovania v distribuovaných systémoch patria procesné páry
(process-pairs) , logovanie a checkpointing. V
nasledujúcich podkapitolách predstavíme základné algoritmy
založené na týchto postupoch. Aj ked’ v základných variantoch
nedosahujú všetky uvedené postupy precíznej obnovy, je
možné ich na takúto úrove nˇ rozšírit’. Jedná sa hlavne o
ošetrenie duplicitných stavov a zarucˇenie, že nedôjde k
strate správ. Zabezpecˇenie proti strate riešia všetky
metódy logovaním správ vo výstupných frontách dovtedy,
kým nie je zarucˇené, že správa bola uložená alebo
spracovaná. V prípade výpadku sa znovu posielajú takto
zalogované správy. Ošetrenie duplicitných správ sa rôzni a preto
je spomenuté podrobnejšie pri jednotlivých metódach.</p>
        </sec>
        <sec id="sec-5-1-2">
          <title>3.1 Passive standby</title>
          <p>
            Metóda passive standby [
            <xref ref-type="bibr" rid="ref5 ref6">6, 5</xref>
            ] je založená na
processpairs prístupe. Ku každému primárnemu uzlu je
priradený záložný uzol. Primárny uzol v pravidelných
intervaloch posiela aktualizáciu stavu na záložný. V prípade
výpadku preberá záložný uzol výpo cˇet a pokracˇuje od
posledného checkpointu. Pre dosiahnutie precízneho
obnovenia je nutné zabezpecˇit’, aby neboli vygenerované
duplicitné dáta a opakovane spracovat’ správy prijaté
havarovaným uzlom, ktoré nestihol reflektovat’ v zálohe. Prvý
problém je riešený opýtaním sa nasledujúcich uzlov na správy,
ktoré prijali a tieto sa už nebudú posielat’. Druhý problém
riešia výstupné fronty, ktoré ukladajú správy dovtedy, kým
nie je potvrdená záloha stavu, ktorý ich obsahuje.
          </p>
          <p>Výhodou tohto prístupu je krátky cˇas potrebný na
obnovenie výpocˇtu, ktorý zodpovedá opakovanému
spracovaniu správ prijatých od posledného checkpointu, avšak
za cenu spomalenia riadneho behu bez výpadkov z
dôvodu vycˇlenenia (minimálne) polovice uzlov ako
záložných a zvýšenej komunikácie primárnych ulov so
záložnými. Dˇalšie zdržanie výpo cˇtu nastáva pri synchrónnom
zálohovaní (primárny uzol neodosiela dáta dovtedy, kým
nie sú uložene aj na záložnom uzle). Pri asynchrónnom
zálohovaní naproti tomu hrozí strata dát a nekonzistentný
stav ak nie je použitá dopl nˇujúca metóda na prevenciu
straty dát.
3.2</p>
        </sec>
        <sec id="sec-5-1-3">
          <title>Active standby</title>
          <p>
            Active standby je d’alším variantom process-pairs [
            <xref ref-type="bibr" rid="ref5 ref6 ref7">6, 5,
7</xref>
            ], ale na rozdiel od passive standby necˇaká záložný uzol
pasívne, ale dostáva rovnaké dáta ako primárny uzol a
aktívne tieto dáta spracováva. Výstup záložného uzlu je
namiesto odosielania logovaný. Pre dosiahnutie precízneho
obnovenia musí záložný uzol zistit’ identifikátory
posledných správ, ktoré boli prijaté nasledujúcimi uzlami, aby
nedošlo k duplicitnému poslaniu správ. Ak plán obsahuje
nedeterministické operátory je navyše nutné doplnit’
logovanie rozhodnutí týchto operátorov a toto následne
odosielat’ na záložný uzol za cenu extra komunikácie.
          </p>
          <p>Výhodou active standby oproti passive variante je
minimálny potrebný cˇas na obnovenie, pretože záložný uzol
dostáva rovnaké správy, ktoré paralelne spracováva. To má
avšak za následok nárast komunikácie o 100% . Dˇalšiu
extra komunikáciu znamená potvrdzovanie prijatých správ,
slúžiacich pre orezanie výstupných zásobníkov a v prípade
nedeterministických operátorov posielanie rozhodovacích
záznamov.
3.3</p>
        </sec>
        <sec id="sec-5-1-4">
          <title>Upstream backup</title>
          <p>
            Klasické process pair prístupy majú vel’ký runtime
overhead (je nutné vycˇlenit’ aspo nˇ polovicu uzlov ako záložné
uzly) a vyžadujú nezanedbatel’né navýšenie komunikácie.
Upstream backup [
            <xref ref-type="bibr" rid="ref5 ref6">6, 5</xref>
            ] je naproti tomu navrhnutý tak,
aby lepšie využil distribuovaný charakter prúdového
spracovania dát. Upstream uzly (uzly umiestnené proti prúdu
dát) slúžia ako zálohy pre downstream uzly (uzly d’alej po
prúde dát), pricˇom sa zálohujú iba n-tice posielané týmto
uzlom. V prípade výpadku uzlu, je tento nahradený novým
uzlom s prázdnym stavom. Znovu spracovaním n-tic
uložených na upstream uzloch dôjde k obnoveniu stavu uzlu.
          </p>
          <p>Hlavným problémom tohto prístupu je narastajúca
vel’kost’ výstupných front, ktoré slúžia ako zálohy. Pre ich
zmenšenie je definovaný ich orezávací protokol (queue
trimming protocol), ktorý popisuje kedy môžu byt’ n-tice z
jednotlivých výstupných front odstránené. Ciel’om je
dosiahnut’ minimálnu množinu, ktorá bude dosta cˇujúca pre
obnovenie stavu havarovaného uzlu. Orezávací protokol je
založený na potvrdzovaní doru cˇenia, resp. spracovania
ntic. Informácie o prijatí sú šírené spätne pomocou
potvrdzovacích správ, pricˇom existuje niekol’ko úrovní týchto
správ. Základná nultá úrovenˇ oznamuje, že daná n-tica
bola prijatá príjemcom. Uzol, ktorý prijme potvrdenie
nultej úrovne, spätne vyráta ktoré vstupné n-tice sa
podiel’ali na vytvorení potvrdenej n-tice a pošle potvrdenie
prvej úrovne. Uzol ktorý prijme potvrdenie prvej úrovne pre
konkrétnu n-ticu od všetkých uzlov, kam bola odoslaná,
môže následne odstránit’ túto a všetky logicky
predchádzajúce n-tice. Pokial’ sa požaduje vyšší stupe nˇ
zabezpecˇenia, iteratívne sa zvyšuje úrovenˇ potvrdenia a orezávanie
prebieha pri prijatí najvyššej požadovanej úrovne.</p>
          <p>Výhodou tohto prístupu je zmenšenie nadmerného
využívania prenosového pásma, ked’že navyše používa iba
potvrdzovacie správy, ktoré sú menšie než správy dátové a
k extra prenosu dát dochádza len pri zasielaní n-tic po
výpadku. Nevýhodou je neúmerne dlhšia doba potrebná na
zotavenie, ked’že nový uzol musí znovu spracovat’
dostatok n-tic pre obnovenie svojho vnútorného stavu a náro
cˇnost’ výpo cˇtu potvrdení vyšších úrovní.
3.4</p>
        </sec>
        <sec id="sec-5-1-5">
          <title>Cooperative passive standby</title>
          <p>
            Cooperative passive standby [
            <xref ref-type="bibr" rid="ref8">8</xref>
            ] je prístup založený na
jemne cˇlenenom checkpointovaciom modeli. Ten je
použitý, pretože efektívne funguje pre vä cˇšiu skupinu úloh a
prípadov než ostatné alternatívy ako znovu spracovanie, cˇi
redundantné spracovanie.
          </p>
          <p>Plán(y) spracovania každého uzlu sú rozdelené do
viacerých nezávislých HA jednotiek. Tieto sú následne
rozdistribuované a vybalansované medzi viacerými servermi.
Toto rozdelenie umož nˇuje rozložit’ zát’až zálohy jedného
uzlu medzi skupinu uzlov a týmto docielit’ rýchlejšiu
obnovu v prípade výpadku.</p>
          <p>Zálohovanie prebieha po jednotlivých HA jednotkách
na danom uzle, cˇo redukuje d´lžku blokovania výpo cˇtu
spôsobené zálohovaním HA jednotky. Jemnejšia granularita
záloh umož nˇuje využit’ vol’né cykly CPU daného uzlu,
ked’ práve neprebieha výpo cˇet (napr. z dôvodu cˇakania na
dáta) a týmto optimalizovat’ celkový výkon. Samotná
záloha prebieha v dvoch krokoch: capture a paste. Pocˇas fázy
capture dôjde na uzle k výberu HA jednotky, ktorá sa bude
zálohovat’ a odoslaniu správy na záložný uzol s
aktualizáciou stavu danej HA jednotky. Paste fáza prebieha na
záložnom uzle, ktorý spracúva doru cˇené zálohovacie správy
tak, že aktualizuje zodpovedajúci obraz checkpointu
aplikovaním rozdielových informácii. Po ukoncˇení fázy paste
je upovedomený odosielatel’ a môže dôjst’ k d’alšiemu
kolu zálohy tejto HA jednotky.</p>
          <p>Po výpadku uzlu preberú jeho úlohu uzly obsahujúce
zálohy jeho jednotlivých HA jednotiek. Pocˇas obnovy
dôjde k operácii paste a spracovaniu nespracovaných
aktualizácii, pokial’ také sú. Dˇalej sú prepojeé vstupy z
havarovaného uzla na záložné a spracované správy z výstupných
front, ktoré boli odoslané havarovanému uzlu ale
neobsahuje ich záloha. Rozdelenie úlohy havarovaného uzlu
medzi viacero záložných znamená, že o cˇakávaný nárast
zát’aže týchto záložných uzlov bude malý a oneskorenie
výpocˇtu bude pod kontrolou.</p>
          <p>Ak dôjde k obnoveniu havarovaného uzlu, tento je
pripojený ako nový prázdny uzol a v rámci automatického
vyvažovania zát’aže môže byt’ na neho prevedená cˇast’
úloh. Vytváranie jednotlivých HA jednotiek a ich
rozdelenie na záložne servery môže prebiehat’ automaticky,
bez nutnosti pevnej konfigurácie, cˇo umož nˇuje dynamické
prispôsobenie sa aktuálnej situácii a rozloženiu zát’aže.
4</p>
        </sec>
      </sec>
      <sec id="sec-5-2">
        <title>D-Bobox</title>
        <p>
          Bobox [
          <xref ref-type="bibr" rid="ref3 ref9">9, 3</xref>
          ] je framework pre vytváranie aplikácií
urcˇených k spracovaniu vel’kých dát v paralelnom
prostredí. Základný princíp spracovania je založený na
rozdelení úlohy na menšie, vzájomne prepojené cˇasti, ktoré
môžu byt’ vykonávané nezávisle. Toto rozdelenie
definuje plán spracovania a je reprezentovaný ako acyklický
orientovaný graf, v ktorom uzly (v Boboxe nazývané
krabicˇky) reprezentujú jednotlivé dielcˇie výpocˇty a
orientované hrany reprezentujú tok dát. Dáta prúdia z
jednotlivých zdrojových krabicˇiek do výstupnej krabicˇky. Zdroje
dát môžu byt’ nielen statického charakteru, ako napríklad
databáze, ale aj dynamické ako rôzne senzory, kamery
atd’. Táto univerzálnost’ umož nˇuje nasadenia Boboxu na
široké spektrum úloh.
        </p>
      </sec>
    </sec>
    <sec id="sec-6">
      <title>Obr. 1: Architektúra systému D-Bobox.</title>
      <p>D-Bobox [ 10] je d’alším evolu cˇným krokom systému
Bobox, ked’ k zvýšeniu efektivity spracovania vel’kých dát
už neposta cˇuje lokálny paralelizmus a je nutné
expandovat’ do distribuovaného prostredia. Zárove nˇ je snaha
zachovat’ širokú použitel’nost’ takto rozšíreného systému a
preto je budovaný s ohl’adom na efektívnu použitel’nost’
aj na bežne dostupnom hardvéri a nielen na
špecializovaných výpocˇtových clustroch.</p>
      <p>Základná schéma D-Boboxu je znázornená na obrázku
1. Uzly sú rozdelené na jeden hlavný - master uzol, ktorý
prijíma požiadavku na úlohu, vytvára plán jej
spracovania (frontend cˇast’), inicializuje podriadené - slave
jednotky na spracovanie a (typicky) je aj ciel’om výsledkov
spracovania. Podriadené uzly obsahujú štandardný
backend z Boboxu a sú rozšírené o potrebnú distribucˇnú
loObr. 2: Ukážka rozšírenia exeku cˇného plánu do distribuovaného prostredia pomocou hranicˇných krabicˇiek. a) Bobox plán
pre výpocˇet na jednom uzle. b) Plán D-Boboxu, rozšírený o hrani cˇné krabicˇky (Boundary Box), ktoré zaist’ujú vzdialenú
komunikáciu (prerušovane).
giku. Vzdialená komunikácia je riešená pridaním
špecializovaných hranicˇných krabicˇiek, ktoré sú do výsledného
plánu pridávané za behu, tesne pred inicializovaním
pracovných uzlov. Pridáva a konfiguruje ich distribucˇná
riadiaca jednotka na primárnom uzle podl’a aktuálnej
dostupnosti uzlov zúcˇastnˇujúcich sa výpocˇtu. Príklad takéhoto
rozšírenia exekucˇného plánu ilustruje obrázok 2.
5</p>
      <sec id="sec-6-1">
        <title>HA a D-Bobox</title>
        <sec id="sec-6-1-1">
          <title>5.1 Základné algoritmy a D-Bobox</title>
          <p>Každý z HA algoritmov spomenutých v predchádzajúcej
kapitole je nasaditelný v systéme D-Bobox, avšak kladie
rôzne požiadavky na samotný systém a poskytuje rôznu
úrovenˇ transparentnosti z pohl’adu tvorby nových
operátorov (krabicˇiek v systéme Bobox). V nasledujúcej
diskusii neberieme do úvahy nedeterministické plány, ktoré pre
všetky algoritmy vynucujú zo strany krabicˇiek podporu
logovania nedeterministických rozhodnutí a tieto vhodným
spôsobom reportovat’, cˇo znižuje požadovanú
transparentnost’.</p>
          <p>Upstream backup predstavuje najmenej blokujúci
prístup a vyžaduje najmenšiu extra komunikáciu po cˇas behu
bez výpadkov, avšak jeho nároky na ukladanie výstupných
front môžu byt’ neúnosne vel’ké a cena obnovy uzlu v
prípade výpadku je vel’ká z pohl’adu cˇasu aj potrebného
výpocˇtového výkonu. Navyše predstavuje najmenej
transparentný prístup, pretože jednotlivé operátory musia
implementovat’ cˇasto netriviálne mapovania medzi výstupnými
a vstupnými n-ticami, ktoré je potrené pre korektné
fungovanie potvrdzovania a orezávacieho algoritmu na výstupné
fronty. Preto je nevhodný pre Bobox, ktorý sa snaží
maximálne skryt’ paraleliza cˇnú a distribucˇnú logiku z krabicˇiek
za úcˇelom ich jednoduchého vývoja.</p>
          <p>Active standby je naproti tomu maximálne
transparentný a takéto spracovanie môže byt’ dokonca
zachytené upraveným plánom spracovania, kde budú jednotlivé
cˇasti spracovania zduplikované a výstupy paralelných
vetiev budú smerované na špeciálnu systémovú krabicˇku,
ktorá zabezpecˇí opätovné poslanie dát tak, aby po výpadku
nedošlo k strate dát (ak výpocˇet v primárnej vetve
zaostával za záložnou) a ani k produkcii duplicitných n-tic (ak
výpocˇet v záložnej vetve zaostával za primárnou vetvou).
Úlohou riadiacej cˇasti HA je v prípade výpadku nájst’
náhradný uzol za havarovaný, ktorý preberie úlohu záložného
uzlu, zreplikovat’ na neho stav zo záložnej vetvy (po
výpadku sa z nej stáva vetva primárna) a vhodne
presmerovat’ komunika cˇné kanály. Tento HA algoritmus môže
slúžit’ pre úlohy preferujúce minimálny cˇas zotavenia pred
výkonom, pretože je nutné obetovat’ polovicu uzlov ako
uzly záložné. Rovnaká nevýhoda platí pre passive standby
algoritmus, ktorý navyše nedosahuje podobne rýchle
obnovenia, z dôvodu opätovného spracovania správ ktoré
nezachytil posledný checkpoint a spomalenia výpocˇtu pocˇas
vykonávania zálohy. Z tohto dôvodu nie je táto možnost’
uvažovaná pre Bobox.</p>
          <p>Kooperatívny variant passive standby patrí takisto
medzi transparentné metódy a jeho výhodou je rozumne malý
vplyv na bezporuchový beh a rýchlost’ zotavenia z
výpadku. Preto poslúži ako základ pre integráciu HA v
systéme D-Bobox.</p>
        </sec>
        <sec id="sec-6-1-2">
          <title>5.2 Integrácia HA v D-Boboxe</title>
          <p>Podpora HA je z pohl’adu umiestnenia rozdelená na dva
cˇasti: lokálnu, umiestnenú na jednotlivých pracovných
uzloch a globálnu, nachadzajúcu sa na primárnom uzle.
Obe cˇasti sú reprezentované zodpovedajúcim managerom
a riešia odlišné úlohy: lokálny manager rieši správu HA v
kontexte jedného uzlu a globálny riadi HA na úrovni
celého systému.</p>
        </sec>
        <sec id="sec-6-1-3">
          <title>HA manager na primárnom uzle je tzv. globálny HA</title>
          <p>manager. Jeho zameraním je riešenie globálnych úloh
ohl’adne poskytnutia spol’ahlivosti a efektívneho výpo cˇtu:
riešenie výpadkov, rozvrhovanie záloh a spolupráca s
vyvažovaním zát’aže.</p>
          <p>V prípade výpadku je nutné informovat’ uzly držiace
zálohy jednotlivých HA jednotiek havarovaného uzlu, aby
vykonali paste operáciu dorucˇených aktualizácií, ak tak
ešte nevykonali a prebrali výpocˇet havarovaných
jednotiek. Pre pokracˇovanie výpocˇtu je ešte nutné presmerovat’
posielanie správ na záložné uzly a informovat’ upstream
uzly, aby odoslali uložené správy zo svojich výstupných
front pre obnovenie stavu výpocˇtu, ktorý nestihol byt’
zachytený posledným checkpointom.</p>
          <p>Vzhl’adom na snahu o rozdelenie úlohy jedného uzlu na
viac nezávislých HA jednotiek, ktoré sú distribuované na
rôzne fyzické uzly, môžeme o cˇakávat’, že nárast zát’aže
týchto uzlov po tom ako preberú úlohu havarovaného uzlu
bude v akceptovatel’ných medziach. Po obnovení
havarovaného uzlu je tento pripojený k výpocˇtu a môžu byt’ na
neho dynamicky preplánované úlohy a zálohy, typicky z
uzlov ktoré sú najviac vyt’ažené (avšak je možné nasadit’
rôzne stratégie zahr´nˇajúce napríklad lokalitu, cenu atd’.).
Hlavným dôvodom, precˇo by sa HA manager mal snažit’
o vyrovnávanie zát’aže, je snaha dosiahnut’ rozumne malé
a cˇasté zálohy všetkých uzlov. Pri nerovnomernej zát’aži
nevyt’ažené uzly produkujú zálohy cˇastejšie cˇím pridávajú
úlohy vyt’aženým uzlom. Tieto naopak, aby nezdržovali
výpocˇet redukujú interval svojich záloh a zálohy
vykonávané po dlhšom cˇase bývajú obecne drahšie a obnovenia
pomalšie, pretože došlo k vä cˇším zmenám stavu, ktoré je
treba pokryt’. Snaha o dynamické vyrovnanie zát’aže
znižuje cenu checkpointov, ked’že tieto sú menšie a tak sa
s väcˇšou pravdepodobnost’ou vojdú do vol’ných cyklov
CPU a sú cˇastejšie cˇo skracuje cˇas obnovy, ked’že je nutné
znovu spracovat’ menší po cˇet n-tic pre obnovenie stavu.
Vyrovnávanie zát’aže dociel’uje HA manager dvoma
spôsobmi: vhodným rozvrhovaním zálohovacích párov a
spoluprácou s riadiacou distribucˇnou jednotkou, ktorá riadi
vyvažovanie pomocou migrácie úloh.</p>
        </sec>
        <sec id="sec-6-1-4">
          <title>HA manager na sekundárnom uzle je lokálny manager.</title>
          <p>Má za úlohu riešit’ HA úlohy spojené s konkrétnym uzlom
medzi ktoré patrí: sledovanie dostupnosti susedov
(upstream a downstream uzlov), správa HA jednotiek (delenie,
zlucˇovanie) a plánovanie a vykonávanie operácií capture a
paste.</p>
          <p>Každý uzol sleduje dostupnost’ susedných uzlov s
ktorými komunikuje. Pokial’ s nejakým susedným uzlom
práve neprebieha komunikácia (netecˇú dáta), tak testuje
jeho dostupnost’ pomocou dotazov v pravidelných
intervaloch. Ak nejaký uzol prestane reagovat’, je po
niekol’kých pokusoch (podl’a nastavenej tolerancie) prehlásený
za havarovaný a jeho výpadok je oznámený globálnemu
HA managerovi, ktorý sa ujme riadenia nápravy tohto
výpadku.</p>
          <p>Pocˇas behu bez výpadkov sú vykonávané operácie
capture a paste. Capture má za úlohu zachytit’ zmenu stavu
konkrétnej HA jednotky a jej odoslanie na záložný
server. Operácia paste ma za úlohu aktualizovat’ obrazy záloh
pomocou dorucˇených správ. Jednotlivé HA jednotky sú
zálohované pomocou operácie capture nezávisle na sebe,
zatial’ cˇo pocˇas operácie paste sa zálohy aktualizujú
postupne podl’a poradia prijatých správ dovtedy, kým sú
nejaké nespracované aktualizacˇné správy, alebo pokial’
nedôjde k preplánovaniu. Plánovanie operácií capture a paste
má na starosti lokálny plánovacˇ. Tento môže
implementovat’ rôzne stratégie za ú cˇelom rozumne zálohovat’, alebo
minimalizovat’ blokovanie výpo cˇtu.</p>
          <p>Pre úpravu granularity checkpointingu umožnuje
lokálny HA manager delenie, resp. zlucˇovanie HA
jednotiek. Delenie je možné v prípade, ak uzol pracuje s
viacerými krabicˇkami (nie nutne priamo prepojenými).
Zjemnením granularity, hlavne u plánov obsahujúcich viacero
netriviálnych operácií, dôjde k rozdeleniu zát’aže zálohy
a obnovenia na viacero záložných serverov. Naopak
zlúcˇenie je vhodné pokial’ sa na uzle ocitne niekol’ko za
sebou idúcich výpocˇtovo jednoduchých krabicˇiek, ktorých
spojené vykonávanie nepredstavuje výrazný nárast zát’aže
(skôr dôjde k rýchlejšiemu spracovaniu vd’aka lokalite
vykonávania) a zmenši pocˇet HA jednotiek, ktoré je potrebné
plánovat’. Tieto zmeny granularity sa musia vykonávat’ v
spolupráci s globálnym HA managerom, ktorý musí
novým HA jednotkám priradit’ uzly, kam sa budú zálohovat’
a naopak zabezpecˇit’ odstránenie záloh zrušených HA
jednotiek.</p>
          <p>HA na hranicˇných krabicˇkách musí pre garanciu
precíznej obnovy podporovat’ logovanie výstupných správ a
elimináciu duplicitných správ. Odchádzajúce správy sa
logujú do doby, než je potvrdená ich záloha v HA
jednotkách ktorým boli odoslané. Toto je nutné pre obnovenie
stavu výpocˇtu po obnove z posledného checkpointu
pomocou ich opakovaného spracovania. Vstupné hranicˇné
krabicˇky musia taktiež pomocou identifikátorov správ
filtrovat’ správy duplicitné, ktoré mohli pri opakovanom
spracovaní vzniknút’ (havarovaný uzol mohol a nemusel
vyprodukovat’ pôvodné správy pred svojím pádom).</p>
          <p>Integrovanie spomenutých cˇastí poskytne základnú
podporu vysokej dostupnosti v systéme D-Bobox. Táto môže
byt’ následne rozširená o podporu nedeterministických
operátorov za pomoci logovania ich rozhodnutí, alebo
napríklad vylepšovaná pridaním rôznych stratégií pri
plánovaní záloh, cˇi vyvažovaní zát’aže.
6</p>
          <p>Záver
V tomto cˇlánku sme prezentovali problém výpadku uzlu
v distribuovaných systémoch prúdového spracovania dát,
definovali typy obnovenia a prezentovali súcˇasné základné
prístupy k dosiahnutiu vysokej dostupnosti týchto
systémov. Následne sme rozobrali vhodnost’ jednotlivých
prístupov pre systém D-Bobox a zvolili jeden z prístupov ako
základný kame nˇ, na ktorom bude zavedená podpora
vysokej dostupnosti v D-Boboxe a na cˇrtli možnosti jej
integrácie do jednotlivých cˇasti D-Boboxu.
7</p>
        </sec>
      </sec>
      <sec id="sec-6-2">
        <title>Pod’akovanie</title>
      </sec>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          [1]
          <string-name>
            <given-names>D. J.</given-names>
            <surname>Abadi</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Y.</given-names>
            <surname>Ahmad</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Balazinska</surname>
          </string-name>
          ,
          <string-name>
            <given-names>U.</given-names>
            <surname>Cetintemel</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Cherniack</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.-H.</given-names>
            <surname>Hwang</surname>
          </string-name>
          ,
          <string-name>
            <given-names>W.</given-names>
            <surname>Lindner</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A. S.</given-names>
            <surname>Maskey</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Rasin</surname>
          </string-name>
          , E. Ryvkina et al., “
          <article-title>The design of the borealis stream processing engine</article-title>
          .
          <source>” CIDR</source>
          ,
          <year>2005</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          [2]
          <string-name>
            <given-names>D.</given-names>
            <surname>Abadi</surname>
          </string-name>
          ,
          <string-name>
            <given-names>D.</given-names>
            <surname>Carney</surname>
          </string-name>
          ,
          <string-name>
            <given-names>U.</given-names>
            <surname>Cetintemel</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Cherniack</surname>
          </string-name>
          ,
          <string-name>
            <given-names>C.</given-names>
            <surname>Convey</surname>
          </string-name>
          ,
          <string-name>
            <given-names>C.</given-names>
            <surname>Erwin</surname>
          </string-name>
          , E. Galvez,
          <string-name>
            <given-names>M.</given-names>
            <surname>Hatoun</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Maskey</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Rasin</surname>
          </string-name>
          et al.,
          <article-title>“Aurora: a data stream management system,” in Proceedings of the 2003 ACM SIGMOD international conference on Management of data</article-title>
          .
          <source>ACM</source>
          ,
          <year>2003</year>
          , pp.
          <fpage>666</fpage>
          -
          <lpage>666</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          [3]
          <string-name>
            <given-names>D.</given-names>
            <surname>Bednarek</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Dokulil</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Yaghob</surname>
          </string-name>
          , and
          <string-name>
            <given-names>F.</given-names>
            <surname>Zavoral</surname>
          </string-name>
          , “
          <article-title>Bobox: Parallelization Framework for Data Processing</article-title>
          ,” in
          <source>Advances in Information Technology and Applied Computing</source>
          ,
          <year>2012</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          [4]
          <string-name>
            <given-names>Z.</given-names>
            <surname>Falt</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Dokulil</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Cermak</surname>
          </string-name>
          , and
          <string-name>
            <given-names>F.</given-names>
            <surname>Zavoral</surname>
          </string-name>
          , “
          <article-title>Parallel sparql query processing using bobox</article-title>
          ,”
          <source>International Journal On Advances in Intelligent Systems</source>
          , vol.
          <volume>5</volume>
          , no.
          <issue>3</issue>
          , pp.
          <fpage>302</fpage>
          -
          <lpage>314</lpage>
          ,
          <year>2012</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          [5]
          <string-name>
            <given-names>J.-H.</given-names>
            <surname>Hwang</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Balazinska</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Rasin</surname>
          </string-name>
          ,
          <string-name>
            <given-names>U.</given-names>
            <surname>Cetintemel</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Stonebraker</surname>
          </string-name>
          , and
          <string-name>
            <given-names>S.</given-names>
            <surname>Zdonik</surname>
          </string-name>
          , “
          <article-title>High-availability algorithms for distributed stream processing</article-title>
          ,” in Data Engineering,
          <year>2005</year>
          .
          <article-title>ICDE 2005</article-title>
          .
          <article-title>Proceedings</article-title>
          . 21st International Conference on,
          <year>2005</year>
          , pp.
          <fpage>779</fpage>
          -
          <lpage>790</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          [6]
          <string-name>
            <surname>J. hyon Hwang</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Balazinska</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Rasin</surname>
          </string-name>
          ,
          <string-name>
            <given-names>U.</given-names>
            <surname>Çetintemel</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Stonebraker</surname>
          </string-name>
          , and
          <string-name>
            <given-names>S.</given-names>
            <surname>Zdonik</surname>
          </string-name>
          , “
          <article-title>A comparison of streamoriented high-availability algorithms</article-title>
          ,”
          <string-name>
            <surname>Brown</surname>
            <given-names>CS</given-names>
          </string-name>
          ,
          <source>Tech. Rep.</source>
          ,
          <year>2003</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          [7]
          <string-name>
            <given-names>M. A.</given-names>
            <surname>Shah</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J. M.</given-names>
            <surname>Hellerstein</surname>
          </string-name>
          , and E. Brewer, “
          <article-title>Highly available, fault-tolerant, parallel dataflows,” in Proceedings of the 2004 ACM SIGMOD international conference on Management of data, ser</article-title>
          .
          <source>SIGMOD '04</source>
          . New York, NY, USA: ACM,
          <year>2004</year>
          , pp.
          <fpage>827</fpage>
          -
          <lpage>838</lpage>
          . [Online]. Available: http://doi.acm.
          <source>org/10</source>
          .1145/1007568.1007662
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          [8]
          <string-name>
            <given-names>J.-H.</given-names>
            <surname>Hwang</surname>
          </string-name>
          ,
          <string-name>
            <given-names>Y.</given-names>
            <surname>Xing</surname>
          </string-name>
          ,
          <string-name>
            <given-names>U.</given-names>
            <surname>Cetintemel</surname>
          </string-name>
          , and
          <string-name>
            <given-names>S.</given-names>
            <surname>Zdonik</surname>
          </string-name>
          , “
          <article-title>A cooperative, self-configuring high-availability solution for stream processing</article-title>
          ,” in Data Engineering,
          <year>2007</year>
          .
          <source>ICDE 2007. IEEE 23rd International Conference on. IEEE</source>
          ,
          <year>2007</year>
          , pp.
          <fpage>176</fpage>
          -
          <lpage>185</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          [9]
          <string-name>
            <given-names>D.</given-names>
            <surname>Bednárek</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Dokulil</surname>
          </string-name>
          ,
          <string-name>
            <given-names>J.</given-names>
            <surname>Yaghob</surname>
          </string-name>
          , and
          <string-name>
            <given-names>F.</given-names>
            <surname>Zavoral</surname>
          </string-name>
          , “
          <article-title>Data-flow awareness in parallel data processing,” in Intelligent Distributed Computing VI, ser</article-title>
          . Studies in Computational Intelligence, G. Fortino, C. Badica,
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>