Matematický model zálohování a obnovy dat

Rok / Year: 2014

Svazek / Volume: 16

Číslo / Number: 1

Matematický model zálohování a obnovy dat Mathematical model of data backup and recovery Karel Burda [email protected] Fakulta elektrotechniky a komunikačních technologií VUT v Brně

Abstrakt: V článku je odvozen matematický model zálohování a obnovy dat. Pomocí tohoto modelu lze zjišťovat objemy dat jednotlivých záloh, kvantitativně hodnotit vlastnosti různých typů zálohovacích strategií a také kalkulovat potřebné kapacity zálohovacích úložišť. V článku je rovněž upřesněna terminologie problematiky zálohování a je navržena systematická klasifikace typů zálohování.

Abstract: In the paper, the mathematical model of data backup and recovery is derived. Using this model, we can establish the amount of data of individual backups, quantitatively evaluate the properties of different types of backup strategies and calculate the required capacities of backup repositories too. In the paper, the terminology in the field of backing up is specified and a systematic classification of backup types is proposed.

VOL.16, NO.1, FEBRUARY 2014

Matematický model zálohování a obnovy dat Karel Burda Fakulta elektrotechniky a komunikačních technologií VUT v Brně Email: [email protected]

Abstrakt – V článku je odvozen matematický model zálohování a obnovy dat. Pomocí tohoto modelu lze zjišťovat objemy dat jednotlivých záloh, kvantitativně hodnotit vlastnosti různých typů zálohovacích strategií a také kalkulovat potřebné kapacity zálohovacích úložišť. V článku je rovněž upřesněna terminologie problematiky zálohování a je navržena systematická klasifikace typů zálohování.

tento model aplikován na různé způsoby zálohování dat a získané výsledky jsou diskutovány.

2 Formalizace zálohování Terminologie používaná v souvislosti se zálohováním není ustálená, a proto si v této kapitole nejprve upřesníme základní pojmy. Prvním důležitým pojmem je paměťové médium, což je určité fyzikální těleso, jehož elementární prostorové oblasti (tzv. domény) se mohou nacházet v jednom z více možných stavů. Příkladem paměťového média je deska pevného disku pokrytá magneticky měkkým materiálem. V takovémto případě jsou doménami elementární plošky na povrchu desky, které mohou mít jednu ze dvou různých magnetických orientací. Stavy domén se označují abstraktními značkami, které se nazývají symboly. V našem příkladu s pevným diskem všechny domény s určitým směrem magnetické orientace reprezentují symboly 0 a domény s opačným směrem magnetické orientace pak reprezentují symboly 1. Symbolům a jejich posloupnostem lze pomocí vhodného kódování přiřadit informaci a tímto způsobem tak můžeme do paměťových médií ukládat informace. Zařízení s paměťovým médiem, které je určeno k zapisování a ke čtení posloupností symbolů, nazveme paměťové úložiště a ukládané posloupnosti symbolů budeme nazývat data D. Data jsou v paměťovém úložišti strukturována do určitých elementárních (tj. dále nedělitelných) posloupností symbolů, jako jsou například sektory pevného disku. Elementární posloupnost symbolů d budeme nazývat datovou jednotkou, přičemž x-tou datovou jednotku budeme značit dx. Datová jednotka dx může v průběhu času reprezentovat odlišné posloupnosti symbolů, které budeme nazývat verzemi datové jednotky dx. Prázdnou datovou jednotku, tj. jednotku dx, která neobsahuje žádná data, budeme formálně zapisovat jako dx = 0. Objem režijních dat (tzv. metadat) datových jednotek (např. čas zápisu dat) nebudeme v modelu uvažovat. Jak již bylo uvedeno, datové jednotky i data se v průběhu času t mění. Z hlediska zálohování jsou významnými událostmi změna datové jednotky a vzetí zálohy. Ke zjednodušení popisu předpokládáme, že uvedené události nemohou nastávat současně a také předpokládáme, že změna datové jednotky i vzetí zálohy mají nulovou dobu trvání, tj. jsou provedeny okamžitě. Pokud v čase ti došlo ke změně datové jednotky dx, tak tuto verzi datové jednotky budeme značit dx(ti), přičemž tato verze je aktuální v časovém intervalu 〈ti, tj), kde tj je okamžik následující změny datové jednotky dx. Pokud došlo v okamžiku ti ke vzetí zálohy, tak dx(ti) bude reprezentovat verzi datové jednotky, která je v okamžiku vzetí zálohy aktuální. Nyní můžeme definovat obnovu dat ("Data Recovery") jako proces rekonstrukce dat do stavu, ve kterém se nacházela

1 Úvod Data jsou jedním z nejcennějších aktiv osob i organizací. V důsledku poruch technických zařízení nebo chyb obsluhy však může dojít k jejich zničení. Z tohoto důvodu se data průběžně kopírují do záložního datového úložiště (tzv. zálohování), aby se v případě potřeby dala tato data rekonstruovat (tzv. obnova dat). Kopie dat byly vytvářeny již od samotných počátků vývoje počítačů, přičemž se k jejich ukládání používala paměťová média, která v dané době byla běžně používána. Podle [1] se od 50. let 20. století nejprve vytvářely kopie děrných štítků a od 60. let se k zálohování dat začaly používat magnetické pásky. Přibližně od poloviny 80. let se začaly používat také pevné disky a později celá pole pevných disků ("Redundant Array of Independent Disks" – RAID) [2]. Pro menší objemy dat se od 70. let používaly k zálohování dat především diskety, které však byly v polovině 90. let vytlačeny optickými disky. V současné době se pro malé objemy dat používají i USB flash disky. S rozvojem počítačových sítí v 80. letech se objevila možnost zálohovat data nejen lokálně, ale také vzdáleně. Vznikala vysokokapacitní úložiště dat, na která bylo možno zasílat kopie dat prostřednictvím počítačových sítí (tzv. technika online zálohování). Příslušná úložiště se nazývají buď síťově připojená úložiště ("Network Attached Storage" – NAS) nebo síť lokálních úložišť ("Storage Area Network" – SAN) [2]. V prvém případě se jedná o jediné paměťové úložiště dostupné prostřednictvím síťového připojení a ve druhém případě se jedná o několik paměťových úložišť dostupných prostřednictvím vysokorychlostní lokální sítě. I přes velký význam zálohování v současné době neexistuje dostatečně obecný matematický model zálohování a obnovy dat, přičemž publikované modely jsou vesměs orientovány na určování míry rizika ztráty dat [3]. Předkládaný článek uvádí matematický model popisu zálohování, který dovoluje kvantitativní porovnání různých způsobů zálohování. V následující kapitole jsou formulovány základní pojmy a formalizován proces zálohování a obnovy dat. Třetí kapitola je věnována popisu modelu zálohování a obnovy dat, ve čtvrté kapitole je

10

VOL.16, NO.1, FEBRUARY 2014

v určitém časovém okamžiku ti. K této rekonstrukci jsou zapotřebí záznamy o původních datech, které se nazývají zálohy dat ("Data Backup"). Data v okamžiku ti budeme značit D(ti) a budeme předpokládat, že sestávají celkově z n datových jednotek d1(ti) až dn(ti). Data potom můžeme formálně vyjadřovat jako vektor datových jednotek: (1) D(t i ) = [d1 (t i ), d 2 (t i ),K, d n (t i )] = [d x (t i )] nx=1.

jí zálohy B(tj) a B(ti) a orientovaná hrana (j, i) vyjadřuje, že při obnově dat je nutné nejprve obnovit data ze zálohy B(tj) a následně je aktualizovat daty ze zálohy B(ti). Tento vztah mezi zálohami nazveme návaznost záloh. Zálohu B(tj) budeme v takovémto případě nazývat referenční zálohou a zálohu B(ti) budeme nazývat navazující zálohou. Na obr. 1 je uveden příklad schématu obnovy pro pět po sobě jdoucích záloh B(t1) až B(t5). Záloha B(t1), tj. uzel 1, je úplná záloha, která obsahuje veškerá data z okamžiku t1. Zároveň je tato záloha referenční zálohou pro zálohy B(t2) a B(t4) a ty jsou referenčními zálohami pro dílčí zálohy B(t3) a B(t5). Intervalové zálohy B(t2), B(t3) a B(t5) obsahují záznamy dat, která se změnila od nejbližší předchozí zálohy a intervalová záloha B(t4) obsahuje záznamy dat, která se změnila v intervalu (t1, t4〉.

Základem jakéhokoliv typu zálohování je úplná záloha. Úplná záloha F(ti) je záznam veškerých dat, která existovala v okamžiku ti, tj. platí, že: F(ti) = D(ti). (2) Úplné zálohy jsou značně objemné, neboť obsahují také data, která se od poslední zálohy nezměnila. Proto se tyto zálohy často kombinují s dílčími zálohami, které obsahují jen data změněná od některé z předchozích záloh. Dílčí zálohu P(tj, ti) budeme definovat jako záznam všech dat, která se změnila v intervalu (tj, ti〉. Pokud změnu datové jednotky dx v uvedeném intervalu budeme označovat bx(tj, ti), tak pro tuto změnu platí: 0, když d x (ti ) = d x (t j ),  (3) bx (t j , ti ) = − d x , když d x byla vymazána, d (t ), jinak.  x i

První řádek vyjadřuje situaci, kdy v daném intervalu nedošlo k žádné změně datové jednotky dx, druhý řádek reprezentuje situaci, kdy datová jednotka dx byla v intervalu (tj, ti〉 vymazána a třetí řádek odpovídá situaci, kdy datová jednotka dx byla v daném intervalu buď vytvořena, nebo modifikována. Dílčí zálohu P(tj, ti) potom můžeme formálně zapsat: (4) P(t j , t i ) = bx (t j , t i ) nx =1.

[

Obrázek 1: Příklad schématu obnovy. Z obr. 1 je zřejmé, že k obnově dat například z okamžiku t3 je zapotřebí do hlavního paměťového úložiště zapsat úplnou zálohu B(t1), tato data aktualizovat zálohou B(t2) a následně ještě aktualizovat zálohou B(t3). Operaci, ve které jsou data D(ti) obnovena z dat D(tj) pomocí navazující dílčí zálohy P(tj, ti), budeme nazývat aktualizací dat a zapisovat: (5) D(tj) ⊕ P(tj, ti) = D(ti),

]

Pokud nebude zapotřebí rozlišovat úplnou zálohu F(ti) a dílčí zálohu P(tj, ti), tak budeme zálohu obecně označovat jako B(ti). Dílčí zálohy budeme klasifikovat na intervalové a atomické. Intervalová záloha I(tj, ti) je dílčí záloha, která obsahuje poslední verze těch datových jednotek, u nichž v intervalu (tj, ti〉 došlo ke změně. To znamená, že pokud se v intervalu mezi tj a ti změní datová jednotka vícekrát, tak daná intervalová záloha bude obsahovat pouze tu verzi datové jednotky, která byla aktuální v čase ti. Důsledkem je skutečnost, že v případě intervalového zálohování lze obnovit stav dat pouze k okamžikům vzetí zálohy. Příkladem jsou denní zálohy, kdy lze data obnovit do stavu, který měla například o půlnoci každého dne. Tento typ zálohování je historicky nejstarší a vytvořené zálohy mají menší objem. Atomické zálohování je moderní metoda, kterou umožnila technika tzv. snímkování (např. [4]). Uvedená technika funguje tak, že při zápisu nových dat se v úložišti ponechávají původní data (tzv. snímek, anglicky "snapshot"). V případě atomického zálohování se zálohují veškeré snímky a tak lze data obnovit do stavu z libovolného časového okamžiku. Nevýhodou tohoto typu zálohování jsou velké objemy záloh. Než si atomické zálohy vysvětlíme podrobněji, tak nejprve prodiskutujeme schémata obnovy dat. Schéma obnovy dat definuje postup rekonstrukce dat z pořízených záloh. V tomto článku budeme schémata obnovy vyjadřovat pomocí grafu. Uzly grafu označené j a i reprezentu-

přičemž aktualizaci každé jednotlivé datové jednotky formálně vyjádříme: d x ( t i ) = d x ( t j ) ⊕ bx ( t j , t i ) =

d x (t j ), pro bx ( t j , ti ) = 0, (6)  = 0, pro bx (t j , ti ) = −d x , d (t ), jinak.  x i První řádek vyjadřuje situaci, kdy je v záloze uvedeno, že v průběhu daného intervalu nedošlo k žádné změně datové jednotky dx, druhý řádek reprezentuje situaci, kdy je v záloze uvedeno, že datová jednotka dx byla vymazána a třetí řádek odpovídá situaci, kdy záloha obsahuje datovou jednotku dx(ti), tj. situaci, kdy uvedená jednotka je oproti okamžiku tj buď vytvořena, nebo modifikována. Pro operaci aktualizace dat platí, že není komutativní, tj. její výsledek závisí na pořadí operandů. Rovněž je zapotřebí si uvědomit, že každá záloha jsou v podstatě určitá data a tak v operaci aktualizace dat může být daty D libovolná záloha B. Nyní můžeme přejít k podrobnějšímu popisu schémat obnovy. Významné postavení mezi schématy obnovy mají milníkové, rozdílové a inkrementální schéma obnovy. V soudobé

11

VOL.16, NO.1, FEBRUARY 2014 literatuře se také často označují jako úplná, rozdílová a inkrementální zálohovací strategie [5]. Pro náš příklad pěti záloh jsou uvedená schémata ilustrována na obr. 2 až 4. Obrázek 2 zobrazuje milníkové schéma obnovy. Toto schéma se vyznačuje tím, že sestává výhradně z úplných záloh (milníků), tj. B(ti) = F(ti). Nevýhodou tohoto schématu obnovy je značný objem záloh (tj. na kapacitu zálohovacích úložišť jsou kladeny vysoké požadavky), ale výhodou je jednoduchá obnova. Data D(ti) obnovíme jednoduše tak, že do hlavního úložiště zapíšeme zálohu F(ti), tj.: D(ti) = F(ti). (7)

Obrázek 4: Příklad inkrementálního schématu obnovy. Nyní se můžeme vrátit k popisu atomického zálohování. V úložištích, která využívají techniku snímkování, se při zápisu nové datové jednotky ponechává původní verze datové jednotky, tzv. snímek. Zálohovací program po svém spuštění vyhledává v úložišti aktuální data i snímky, které doposud nebyly zálohovány. Pomocí časových údajů vedených o datových jednotkách lze výskyt verzí datových jednotek v úložišti uspořádat v čase, přičemž uvedená posloupnost dovoluje obnovit data v úložišti do stavu z libovolného časového okamžiku. Z hlediska zálohování můžeme posloupnost výskytu jednotlivých datových jednotek dx(ti) v čase chápat jako posloupnost záloh A(tj, ti), které jsou uspořádány v inkrementálním schématu obnovy dat. Atomické zálohy A(tj, ti) jsou sice formálně dílčí zálohou v intervalu (tj, ti〉, ale na rozdíl od intervalových záloh se vyznačují tím, že obsahují vždy pouze jedinou nenulovou datovou jednotku. Pro atomickou zálohu, která popisuje změnu datové jednotky dy v okamžiku ti, tj. pro atomickou zálohu s nenulovou datovou jednotkou dy(ti) platí: (10) A(t j , t i ) = bx (t j , t i ) nx =1 ,

Obrázek 2: Příklad milníkového schématu obnovy. Rozdílové schéma obnovy ilustruje obr. 3. Uvedené schéma je založeno na tom, že první záloha B(t1) je úplnou zálohou a všechny ostatní zálohy jsou intervalové, přičemž je pro ně referenční zálohou první záloha. Formálně toto schéma můžeme zapsat, že B(t1) = F(t1) a B(ti) = I(t1, ti), kde i = 2 až 5. Výhodou oproti předchozímu schématu je celkově menší objem záloh, avšak obnova dat D(ti) pro i > 1 je poněkud složitější. Postup je takový, že do úložiště nejprve zapíšeme data ze zálohy F(t1) a ta následně aktualizujeme zálohou I(t1, ti). Pro obnovu dat v rozdílovém schématu obnovy tedy platí, že:

 F (t1 ), pro i = 1, D(ti ) =   F (t1 ) ⊕ I (t1 , ti ), jinak.

(8)

přičemž

]

d y ( t i ), pro x = y , bx ( t j , ti ) =  (11) 0, jinak. Operace aktualizace dat platí samozřejmě i pro atomickou zálohu. Atomické zálohování budeme ilustrovat na scénáři, který je dán tabulkou Tab. 1. V tomto scénáři data sestávají ze tří datových jednotek dx, kde x ∈ {1, 2, 3}. V čase t1 byly do úložiště nahrány datové jednotky d1(t1), d2(t1) a d3(t1) a z těchto verzí datových jednotek byla současně vytvořena úplná záloha F(t1). V okamžiku t2 došlo ke změně datové jednotky d2(t1) na verzi d2(t2), v čase t3 pak došlo ke změně datové jednotky d3(t1) na verzi d3(t3) a nakonec v okamžiku t4 došlo ke změně datové jednotky d2(t2) na verzi d2(t4). Pokud je v okamžiku t5 spuštěno další zálohování, tak aktuálními daty budou datové jednotky d1(t1), d2(t4) a d3(t3). V úložišti se dále nacházejí snímky d2(t1), d2(t2) a d3(t1). Zálohovací program podle časových údajů u jednotlivých datových jednotek a snímků zjistí, že oproti úplné záloze B(t1) = F(t1) = [d1(t1), d2(t1), d3(t1)] se nejdříve změnila druhá datová jednotka na verzi d2(t2) a tu zapíše jako atomickou zálohu B(t2) = A(t1, t2) = [0, d2(t2), 0]. Analogicky vytvoří dvě zbývající zálohy B(t3) = A(t2, t3) = [0, 0, d3(t3)] a B(t4) = A(t3, t4) = [0, d2(t4), 0]. Snímky starých verzí datových jednotek pak mohou být z hlavního úložiště vymazány a vytvořené zálohy je možné podle inkre-

Obrázek 3: Příklad rozdílového schématu obnovy. Obr. 4 ilustruje inkrementální schéma obnovy. Uvedené schéma je založeno na tom, že první záloha B(t1) je úplnou zálohou a všechny ostatní zálohy jsou intervalové, přičemž pro všechny je referenční zálohou nejbližší předchozí záloha. Formálně toto schéma můžeme zapsat, že B(t1) = F(t1) a B(i) = I(ti–1, ti), kde i = 2 až 5. Výhodou oproti všem předešlým schématům je celkově nejmenší objem záloh, avšak obnova dat D(ti) pro i > 1 je v průměru nejsložitější. Je to dáno tím, že data ze zálohy B(t1) musí být postupně aktualizována všemi zálohami B(t2) až B(ti). Pro obnovu dat v inkrementálním schématu obnovy tedy můžeme psát, že:

 F (t1 ), pro i = 1,  i D(ti ) =   F (t1 ) ⊕ ∑ I (t j −1 , t j ), jinak. j =2 

[

(9)

12

VOL.16, NO.1, FEBRUARY 2014 mentálního schématu obnovy (viz obr. 5) využít k obnově dat do libovolné podoby, v níž se nacházela v časovém intervalu 〈t1, t5〉. K poslednímu řádku Tab. 1 poznamenáváme, že v okamžiku t5 nedošlo k žádné změně dat a tak atomická záloha pro tento okamžik neexistuje.

losti, tak můžeme využít kombinace techniky zrcadlení a snímkování. Princip uvedené kombinace spočívá v tom, že v případě změny datové jednotky v hlavním úložišti z verze dx(ti–1) na verzi dx(ti) se tato změna provede také na záložním úložišti, avšak původní verze datové jednotky dx(ti–1) je uložena jako atomická záloha A(ti, ti–1). Povšimněme si, že u tohoto typu zálohování platí, že ti > ti–1 a že tato atomická záloha pokrývá interval 〈ti–1, ti). Atomické zálohy uspořádané podle času dovolují podle inkrementálního schématu obnovy návrat do stavu v libovolném okamžiku minulosti. Pokud je například zapotřebí obnovit data D(tj), tak tuto obnovu provedeme jako:

Tabulka 1: Scénář pro ilustraci atomického zálohování.

ti t1

d1(ti) d1(t1)

d2(ti) d2(t1)

d3(ti) d3(t1)

t2

d1(t1)

d2(t2)

d3(t1)

t3

d1(t1)

d2(t2)

d3(t3)

t4

d1(t1)

d2(t4)

d3(t3)

t5

d1(t1)

d2(t4)

d3(t3)

Zálohy B B(t1) = F(t1) = [d1(t1), d2(t1), d3(t1)] B(t2) = A(t1, t2) = [0, d2(t2), 0] B(t3) = A(t2, t3) = [0, 0, d3(t3)] B(t4) = A(t3, t4) = [0, d2(t4), 0] −

D(t j ) = D(t i ) ⊕ ∑ A(t k , t k −1 ) . j +1

k =i

V tomto vztahu si povšimněme, že vzhledem k nekomutativnosti operace aktualizace dat musíme data aktualizovat od nejmladší zálohy až po tu nejstarší. Na obr. 6 a v Tab. 2 je uveden příklad schématu obnovy pro zálohování založené na výše uvedené kombinaci techniky zrcadlení a snímkování pro scénář událostí z obr. 5. Základem jsou aktuální data D(ti) záložního úložiště, což je prakticky úplná záloha F(ti) aktuálního stavu hlavního paměťového úložiště. V okamžiku t5 platí, že F(t5) = [d1(t1), d2(t4), d3(t3)]. Tento aktuální stav je zároveň roven stavu z okamžiku poslední změny dat, tj. z okamžiku t4. Můžeme tedy psát, že F(t5) = D(t5) = D(t4). Na tento stav dat podle inkrementálního schématu navazují atomické zálohy A(t4, t3) = [0, d2(t3) = d2(t2), 0], A(t3, t2) = [0, 0, d3(t2) = d3(t1)] a nakonec A(t2, t1) = [0, d2(t1), 0].

Obrázek 5: Příklad atomického zálohování.

Tabulka 2: Scénář pro ilustraci regresivního atomického zálohování.

Pokud by souhrn atomických záloh byl příliš objemný, tak je možné atomické zálohy převést na vhodné intervalové zálohy. Omezí se tak sice počet časových okamžiků, ke kterým lze data obnovit, ale na druhou stranu může dojít k redukci celkového objemu záloh, protože se z každé změněné datové jednotky ponechává vždy jen její poslední verze. Z atomických záloh lze pomocí operace aktualizace dat odvodit intervalovou zálohu následovně: I (t j , t i ) = ∑ A(t k , t k +1 ) .

ti

d1(ti)

d2(ti)

d3(ti)

Zálohy B

t1 t2

d1(t1) d1(t1)

d2(t1) d2(t2)

d3(t1) d3(t1)

t3

d1(t1)

d2(t2)

d3(t3)

t4

d1(t1)

d2(t4)

d3(t3)

t5

d1(t1)

d2(t4)

d3(t3)

− B(t1) = A(t2, t1) = [0, d2(t1), 0] B(t2) = A(t3, t2) = [0, 0, d3(t1)] B(t3) = A(t4, t3) = [0, d2(t2), 0] D(t5) = B(t4) = [d1(t1), d2(t4), d3(t3)]

i −1

k= j

(13)

(12)

Pro náš příklad pak můžeme psát, že I(t1, t4) = A(t1, t2) ⊕ A(t2, t3) ⊕ A(t3, t4) = [0, d2(t2), 0] ⊕ [0, 0, d3(t3)] ⊕ [0, d2(t4), 0] = [0 ⊕ 0 ⊕ 0, d2(t2) ⊕ 0 ⊕ d2(t4), 0 ⊕ d3(t3) ⊕ 0] = [0, d2(t4), d3(t3)]. Vidíme, že naše atomické zálohy celkově obsahovaly tři nenulové datové jednotky, ale vytvořená intervalová záloha už obsahuje pouze dvě nenulové datové jednotky. Došlo tedy k redukci objemu záloh, ale nyní jsme schopni obnovit pouze stav dat z okamžiku t4. Další technikou, která ovlivnila způsoby zálohování dat je technika zrcadlení ("Mirroring", např. [2]). Technika zrcadlení spočívá v tom, že každá změna dat v hlavním úložišti je prakticky okamžitě provedena i v záložním úložišti. Data v obou úložištích jsou potom totožná a záložní úložiště je možné v případě havárie hlavního úložiště použít jako plnohodnotnou náhradu vyřazeného úložiště. Nevýhodou popsané techniky je skutečnost, že nelze obnovit stav dat v některém okamžiku z minulosti. Pokud vyžadujeme možnost obnovit data z minu-

Obrázek 6: Příklad regresivního schématu obnovy. Povšimněme si, že toto schéma je analogické atomickému inkrementálnímu schématu z obr. 5. Rozdíl mezi těmito sché-

13

VOL.16, NO.1, FEBRUARY 2014 maty spočívá pouze v tom, že u schématu podle obr. 5 se obnovují stavy, které následovaly po pořízení úplné zálohy B(t1) a ve schématu podle obr. 6 se obnovují stavy, které předcházely úplné záloze (a současně aktuálním datům záložního úložiště), tj. B(t4) = D(t5). Schémata obnovy, kde se obnovují stavy, které následovaly po vzetí úplné zálohy, budeme nazývat progresivní schémata. Schémata pro obnovu stavů, které předcházely okamžiku vzetí úplné zálohy, budeme nazývat regresivní schémata obnovy. Regresivní i progresivní schémata obnovy s ekvivalentními grafy obnovy, jako jsou ty na obr. 5 a 6, mají z hlediska celkového objemu záloh i doby obnovy stejné parametry, protože odrážejí stejný proces změn datových jednotek. V této souvislosti je ještě vhodné poznamenat, že regresivní schémata obnovy nemusí být pouze typu inkrementální atomické zálohy. Jak již bylo uvedeno, z atomických záloh lze odvodit pomocí vztahu (12) libovolné intervalové zálohy. To dovoluje konstruovat regresivní intervalová schémata libovolného typu. Nyní si výše zavedené pojmy zrekapitulujeme. Zálohy budeme klasifikovat následovně: • úplná, • dílčí - intervalová, - atomická. Schémata obnovy budeme třídit na: • milníkové, • referenční - progresivní, - regresivní a referenční schémata obnovy budeme klasifikovat na: • rozdílové, • inkrementální, • kombinované.

mezi po sobě následujícími změnami datové jednotky je pro všechny datové jednotky stejná. Veličina λ = 1/∆ potom vyjadřuje intenzitu změn datové jednotky v čase. Dále v našem modelu předpokládáme, že pravděpodobnostní rozdělení dob mezi změnami datové jednotky se řídí exponenciálním rozdělením, tj. pro distribuční funkci G náhodné veličiny U platí: (15) G (u ) = P(U ≤ u ) = 1 − e − λu .

Nyní si matematicky popíšeme intervalové zálohy, k čemuž použijeme veličiny uvedené na obr. 7. Podle tohoto obrázku došlo v okamžicích t1 a t4 ke změně datové jednotky a v okamžicích t2 a t3 bylo provedeno zálohování dat. Veličina T = (t3 – t2) je doba mezi těmito zálohami, proměnná u = (t4 – t1) je realizací náhodné veličiny U, což je doba mezi změnami datové jednotky a veličina r = (t2 – t1) je doba mezi změnou datové jednotky a následující zálohou. Změna datové jednotky, která se uskutečnila v čase t1, je pochopitelně zaznamenána v záloze z okamžiku t2. Nás nyní zajímá pravděpodobnost q, že pokud se datová jednotka do první zálohy (tj. do t2) nezmění, tak se nezmění ani do okamžiku t3, tj. do okamžiku další zálohy. Formálně tuto pravděpodobnost můžeme vyjádřit jako podmíněnou pravděpodobnost: q = P(U > r + T | U > r). (16)

Obrázek 7: Veličiny pro popis matematického modelu intervalové zálohy. Exponenciální rozdělení je tzv. rozdělením bez paměti, což formálně vyjadřuje vztah (např. [6], s. 40): P(U > r + T | U > r) = P(U > T). (17)

V další kapitole ukážeme, jak můžeme zálohy a schémata obnovy kvantitativně hodnotit.

Pro náš případ z této vlastnosti vyplývá, že pokud za dobu r nedošlo ke změně datové jednotky (podmínka U > r), tak pravděpodobnost, že ke změně nedojde za dobu (r + T) je stejná jako pravděpodobnost, že ke změně nedojde za dobu T. Z toho plyne, že: q = P(U > r + T U > r ) = P(U > T ) = (18)

3 Matematický model Obsahem této kapitoly je matematický model, který umožňuje kvantifikovat objemy různých záloh a tak hodnotit vlastnosti různých schémat obnovy. V našem modelu předpokládáme, že všechny datové jednotky dx sestávají ze stejného počtu symbolů. Počet symbolů datové jednotky budeme nazývat objem datové jednotky a značit d. Pesimisticky předpokládáme, že se v hlavním úložišti nevyskytují žádné prázdné jednotky, tj. všechny datové jednotky obsahují ve kterémkoliv okamžiku nějaká data. Pro celkový objem dat v paměťovém úložišti potom evidentně platí, že D = n ⋅d. Tentýž vztah samozřejmě platí i pro objem úplné zálohy vzaté v libovolném okamžiku ti, takže pro objem úplné zálohy můžeme psát: (14) F (t i ) = D = d ⋅ n .

= 1 − P(U ≤ T ) = 1 − G (T ). Z uvedené rovnice pak pro pravděpodobnost q plyne: q = 1 − G (T ) = e − λT . (19)

Veličina q vyjadřuje pravděpodobnost, že v době T mezi po sobě jdoucími zálohami nedojde ke změně datové jednotky. Pro komplementární pravděpodobnost p, tj. pravděpodobnost, že v době T mezi po sobě jdoucími zálohami dojde alespoň k jedné změně sledované datové jednotky, pak plyne: p = 1 − q = 1 − e −λT = G (T ). (20)

Nyní řešme objem dílčích záloh. Předpokládejme, že k (i– 1)-ní změně datové jednotky dx došlo v čase ti–1 a k i-té změně datové jednotky došlo v čase ti. Označme dobu mezi po sobě následujícími změnami datové jednotky ui = (ti – ti–1). Doby ui jsou v modelu reprezentovány náhodnou veličinou U se střední hodnotou ∆, přičemž předpokládáme, že střední doba ∆

Pokud data sestávají z n datových jednotek a pokud je pravděpodobnost změny datové jednotky v čase od (ti – T) po ti rovna hodnotě p, tak intervalová záloha I(ti − T, ti) bude v průměru obsahovat n⋅p změněných datových jednotek. Pro objem I(ti − T, ti) takovéto zálohy potom můžeme psát:

14

VOL.16, NO.1, FEBRUARY 2014

I (ti − T , ti ) = d ⋅ n ⋅ (1 − e − λT ) =

zapsat zálohy B(t1), B(t4) a B(t5). Zálohy potřebné k obnově dat D(ti) nazveme obnovovací zálohy a jejich celkový objem budeme značit Ri. Pro formální popis této veličiny si označme množinu uzlů na cestě z uzlu úplné zálohy do uzlu i jako množinu Ui. Například pro D(t1) je uvedená cesta tvořena pouze uzlem 1 a tak U1 = {1} a v případě dat D(t5) je zmiňovaná cesta tvořena posloupností uzlů 1-4-5 a tedy U5 = {1, 4, 5}. Pro Ri potom platí: Ri = ∑ B(t k ) , (24)

(21)

= D ⋅ (1 − e −λT ) = D ⋅ p. Uvedený vztah nám umožňuje zjistit objem každé navazující intervalové zálohy, která je vykonána po uplynutí doby T od příslušné referenční zálohy. V této souvislosti připomínáme, že pokud mezi oběma zálohami došlo u datové jednotky k více změnám, tak v případě intervalového zálohování se zaznamenává pouze poslední verze změněné jednotky. Nyní vyřešme celkový objem S atomických záloh za dobu T. Jak jsme již uvedli, tak intenzita změn datové jednotky je rovna hodnotě λ. Za dobu T tak dojde u n datových jednotek celkem k N = n⋅λ⋅T změnám datových jednotek. Každá tato změna je zaznamenána v jedné atomické záloze o objemu d symbolů. Za dobu T tedy vznikne N atomických záloh, jejichž celkový objem S(ti − T, ti) formálně vyjádříme následovně: S (t i − T , t i ) = d ⋅ n ⋅ λ ⋅ T = (22) 1 , = D ⋅ λ ⋅ T = D ⋅ ln 1− p přičemž k poslednímu vyjádření celkového objemu atomických záloh jsme využili inverzi vztahu (20). Získané vztahy nám dovolují zjistit celkový objem atomických záloh vytvořených za dobu T. Tímto jsme dokončili kvantifikaci objemu různých typů záloh a nyní můžeme přistoupit ke kvantitativní analýze různých schémat obnovy.

k ∈U i

tj. například pro D(t5) je pak R5 =B(t1)+B(t4)+B(t5). Střední hodnotu ze všech hodnot R1 až RM nazveme střední objem obnovovacích záloh a budeme ji značit symbolem R. Formálně můžeme psát: 1 M R = ⋅ ∑ Ri . (25) M i =1 Jak již bylo uvedeno, veličina R úměrně souvisí se střední dobu obnovy dat, a proto usilujeme o její nejmenší možnou hodnotu. Obnova dat pak bude v průměru nejrychlejší. Nyní si odvodíme hodnoty obou kritérií pro všechna zkoumaná schémata, přičemž začneme s milníkovým schématem obnovy. V tomto případě z obr. 2 vidíme, že celkový objem záloh je roven součtu všech M = 5 úplných záloh, tj. platí:

C = ∑ F (t i ) = D ⋅ M . M

Objemy obnovovacích záloh Ri jsou u všech dat D(ti) stejná, přičemž Ri = D. Pro střední objem záloh R proto jednoduše platí: R= D. (27)

4 Diskuse Využití výše uvedeného modelu budeme ilustrovat na schématech obnovy z obr. 1 až 4. Na obr. 2 je milníkové schéma, na obr. 3 rozdílové schéma, na obr. 4 inkrementální a na obr. 1 kombinované schéma obnovy. Poznamenáváme, že uvedená schémata jsou srovnatelná, neboť všechna sestávají z M = 5 záloh. V této části se omezíme jen na referenční progresivní schémata, protože získané výsledky zcela samozřejmě platí také pro ekvivalentní regresivní schémata obnovy. U všech schémat obnovy předpokládáme, že zálohy se provádějí pravidelně po intervalech o délce T. K porovnání schémat použijeme dva parametry. Prvním parametrem je celkový objem záloh C, který jednoduše určíme jako součet objemů všech záloh v daném schématu, tj.

C = ∑ B(t i ) .

(26)

i =1

U rozdílového schématu obnovy (viz obr. 3) pro jednotlivé zálohy platí, že:  D , i = 1, B (t i ) =  (28) −λ ⋅( i −1)⋅T ), i = 2,3,...M .  D ⋅ (1 − e Ze vztahu (19) víme, že veličina e–λ⋅T je rovna pravděpodobnosti q. Potom pro objemy záloh rozdílového schématu záloh můžeme psát:  D , i = 1, B (t i ) =  (29) i −1  D ⋅ (1 − q ), i = 2,3,...M . Po dosazení těchto hodnot do definičních vztahů pro parametry C a R a po jednoduchých úpravách nakonec získáváme:  q − qM  (30) C = D ⋅  M −  1 − q   a D  q − qM  (31) . R = ⋅  2 ⋅ M − 1 − M  1 − q  U inkrementálního schématu obnovy (viz obr. 4) pro jednotlivé zálohy platí, že:  D , i = 1, B (t i ) =  (32) −λ ⋅T  D ⋅ (1 − e ), i = 2,3,...M .

M

(23)

i =1

Uvedený parametr prakticky reprezentuje paměťové nároky daného schématu obnovy, přičemž usilujeme o jeho minimální hodnotu. Důvodem je skutečnost, že vyšší hodnota celkového objemu záloh znamená potřebu záložního úložiště s vyšší paměťovou kapacitou a tudíž i vyšší cenou. Dalším hlediskem pro hodnocení schématu obnovy je doba obnovy. Pokud předpokládáme konstantní rychlost zápisu dat ze záložního do hlavního úložiště, tak doba obnovy bude záviset na objemu záloh, které musíme k obnovení dat D(ti) do hlavního úložiště zapsat. K obnově dat D(t1) až D(tM) je však nutné do úložiště pokaždé zapsat různé zálohy o různých objemech. Například pro schéma z obr. 1 potřebujeme k obnově dat D(t1) zapsat pouze úplnou zálohu B(t1), avšak na druhou stranu k obnově dat D(t5) potřebujeme do hlavního úložiště

Po substituci e–λ⋅T = q můžeme pro objemy záloh inkrementálního schématu záloh psát:

15

VOL.16, NO.1, FEBRUARY 2014 nějakou kombinací obou výše uvedených hraničních schémat obnovy.

 D , i = 1, B(ti ) =  (33)  D ⋅ (1 − q), i = 2,3,...M . Po dosazení těchto hodnot do definičních vztahů pro parametry C a R a po jednoduchých úpravách nakonec získáváme: C = D ⋅ [M − (M − 1) ⋅ q] (34) a

(35) ⋅ [(M + 1) − (M −1) ⋅ q]. 2 Pro porovnání s výše uvedenými schématy ještě odvodíme hodnoty parametrů C a R pro kombinované schéma obnovy z obr. 1. První záloha je úplná, tj. B(t1)= D. Druhá, třetí a pátá záloha jsou od jim příslušné referenční zálohy vzdáleny dobu T a tak můžeme psát, žeB(t2)=B(t3)=B(t5)= D⋅ (1 – q). Čtvrtá záloha je od své referenční zálohy vzdálena dobu 3⋅T a tak platí, že B(t4)= D⋅ (1 – q3). Dosazením výše uvedených hodnot záloh do definičních vztahů parametrů C a R a po jednoduchých úpravách získáme: C = D ⋅ 5 − 3 ⋅ q − q3 (36) R=

D

(

a D

(

Obrázek 8: Celkový objem záloh C pro různá schémata obnovy. Obr. 9 ilustruje závislosti středního objemu R záloh potřebných k obnově konkrétního stavu dat v závislosti na proměnné p. Z obrázku je zřejmé, že minimální hodnotu parametru R, tj. Rmin = D (40)

)

)

(37) ⋅ 11− 4 ⋅ q − 2 ⋅ q 3 . 5 Závislosti parametrů C a R si pro zkoumaná schémata obnovy zobrazíme pro proměnnou p = (1 – q), což je pravděpodobnost, že u datové jednotky dojde mezi po sobě následujícími zálohami (tj. za dobu T) ke změně. Závislost celkového objemu záloh C v násobcích veličiny D na hodnotě p pro různá schémata obnovy ilustruje obr. 8. Z obrázku vidíme, že u milníkového zálohování je hodnota parametru C konstantní a rovna hodnotě 5⋅D nebo obecněji M⋅D. U referenčních schémat obnovy platí, že pro hodnotu p = 0, je celkový objem záloh u všech schémat roven minimu, tj. hodnotě D. Tato hodnota je dána daty první úplné zálohy. Ostatní zálohy jsou totiž v případě p = 0 prázdné, protože nedochází k žádným změnám dat. Druhým extrémem všech referenčních schémat je hodnota C pro případ, kdy intenzita změn datové jednotky λ → ∞. V tomto případě je pravděpodobnost p = 1, tj. za dobu T se změní všechna data. V takovémto případě je celkový objem záloh C roven hodnotě M⋅D, tj. paměťové nároky referenčních schémat jsou stejné jako u milníkového schématu. Z průběhu parametru C pro hodnoty p ∈ 〈0, 1〉 vidíme, že extrémy pro schémata obnovy jsou milníkové schéma a inkrementální schéma. Milníkové schéma má nejvyšší nároky na paměťové kapacity pro zálohování Cmax = D ⋅ M (38) R=

poskytuje milníkové schéma obnovy. Naopak inkrementální schéma tvoří horní hranici hodnoty parametru R, kterou můžeme vyjádřit lineární závislostí:  M −1  Rmax = D ⋅  ⋅ p + 1 . (41)  2 

Obrázek 9: Střední objem záloh R potřebných k obnově dat pro různá schémata. Z obou výše uvedených obrázků vidíme, že milníkové a inkrementální schéma jsou hraničními extrémy jak pro parametr C, tak i pro parametr R. Milníkové schéma je z hlediska parametru C nejhorší ze všech schémat a inkrementální je nejlepší. V případě parametru R je tomu přesně naopak. Rozdílové schéma a kombinovaná schémata potom lze chápat jako kompromisy, které se nacházejí mezi oběma uvedenými extrémy. Nyní nám zbývá ještě porovnat objem zálohy pro intervalové a atomické zálohování. V případě intervalové zálohy jsme odvodili, že pro její objem za dobu T platí: I (t i − T , t i ) = D ⋅ (1 − e −λT ) = D ⋅ p , (42)

a naopak inkrementální schéma má paměťové nároky nejnižší: Cmin = D ⋅ [(M − 1) ⋅ p + 1 ]. (39)

Paměťové nároky ostatních schémat se pohybují mezi hranicemi, které jsou vymezeny milníkovým a inkrementálním schématem obnovy. Z obrázku dále vidíme, že speciálně pro referenční schémata jsou hraničními případy rozdílové a inkrementální schéma. Závislost celkového objemu záloh C pro libovolné kombinované schéma se totiž vždy nachází mezi odpovídajícími závislostmi rozdílového a inkrementálního schématu. Je to dáno tím, že kombinované schéma je vždy

16

VOL.16, NO.1, FEBRUARY 2014 jem libovolného typu zálohy. To dovoluje určit celkový objem záloh libovolného schématu obnovy a také střední objem záloh potřebných k obnově konkrétního stavu dat. Uvedené parametry umožňují porovnávat různá schémata obnovy dat a umožňují i kalkulovat potřebné kapacity zálohovacích úložišť. Popsaný model vychází z předpokladů, že pravděpodobnost p je pro všechny datové jednotky stejná a že změna datové jednotky je událost, která nemá vliv na změnu ostatních datových jednotek, tj. jedná se o navzájem nezávislé události. Dalšími předpoklady jsou, že celkový objem dat je konstantní a žádná datová jednotka není prázdná. Uvedené předpoklady nejsou obecné a tak je žádoucí vytvořit obecnější modely. V každém případě je však popsaný model vhodný pro teoretický popis různých schémat obnovy dat a z hlediska praxe je využitelný alespoň pro hrubé kalkulace kapacit zařízení potřebných pro zálohování.

kde p je pravděpodobnost, že za dobu T dojde alespoň k jedné změně datové jednotky. Dále jsme si odvodili, že pro celkový objem atomických záloh za dobu T platí: 1 S (t i − T , t i ) = D ⋅ λ ⋅ T = D ⋅ ln . (43) 1− p Na obr. 10 jsou uvedeny závislosti objemu intervalové a celkové atomické zálohy na veličině p. Z obrázku je zřejmé, že obecně vždy platíS(ti, ti − T)≥I(ti, ti − T), tj. objem intervalové zálohy za dobu T není nikdy větší než souhrn všech atomických záloh za tutéž dobu. Tato skutečnost je dána tím, že celková atomická záloha stejně jako intervalová záloha vždy obsahuje všechny poslední verze změněných datových jednotek, ale navíc obsahuje i případné starší verze těchto datových jednotek. Z grafu vidíme, že pro malé hodnoty pravděpodobnosti p nejsou rozdíly mezi objemy obou záloh velké, ale pro větší hodnoty pravděpodobnosti p jsou uvedené rozdíly značné. Přednost atomických záloh, kterou je možnost obnovy stavu dat z libovolného okamžiku, je tak vykoupena značnými požadavky na paměťovou kapacitu záložního úložiště.

Literatura [1] YURIN, Maxim. SOFTLOGICA. The history of backup [online]. [cit. 2014-01-13]. Dostupné z: http://www.backuphistory.com [2] LIOTINE, Matthew. Mission-Critical Network Planning. London: Artech House, 2003. ISBN 158053516X. [3] FRISCH, Æleen. Handbook of Network and System Administration: System Backup: Methodologies, Algorithms and Efficiency Models. Amsterdam: Elsevier, 2008. ISBN 0444521984. [4] NELSON, Steven. Pro Data Backup and Recovery. New York City: Apress, 2011. ISBN 1430226625.

Obrázek 10: Objem inkrementální ( I ) a celkové atomické (S ) zálohy za dobu T.

[5] DE GUISE, Preston. Enterprise Systems Backup and Recovery. Boca Raton: CRC Press, 2008. ISBN 1420076396.

5 Závěr Závěrem lze konstatovat, že v článku je upřesněna terminologie a klasifikace zálohování. Jádrem článku je matematický model, který umožňuje na základě hodnoty pravděpodobnosti p, že za dobu T se datová jednotka změní, zjistit celkový ob-

[6] LAKATOS, Laszlo, Laszlo SZEIDL a Miklos TELEK. Introduction to Queueing Systems with Telecommunication Applications. New York: Springer, 2013. ISBN 146145316X.

17