Distribuované transakce

Distribuovane´ transakce Luka´sˇ Petrlı´k? [email protected]

1

´ vod U

Pojem transakce pocha´zı´ pu˚vodneˇ z obchodnı´ho sveˇta. Prˇedpokla´dejme, zˇe firma A hleda´ dodavatele pro jistou zaka´zku. V u´vahu prˇicha´zı´ firma B, ovsˇem k podmı´nka´m doda´vky ma´ jiste´ vy´hrady. Po neˇjake´ dobeˇ dohadova´nı´ dojdou obeˇ strany ke konsensu a podepı´sˇ´ı kontrakt. Do podepsa´nı´ kontraktu majı´ obeˇ strany svobodu ukoncˇit vyjedna´va´nı´ a chovat se, jako by se nic nestalo. Po podepsa´nı´ jsou ovsˇem obeˇ strany va´za´ny splnit svou cˇa´st u´mluvy. Databa´zove´ transakce se chovajı´ podobneˇ. Proces A ozna´mı´, zˇe chce prove´st transakci s jednı´m nebo vı´ce dalsˇ´ımi procesy. Procesy pak mohou prova´deˇt operace – vytva´rˇet, rusˇit a modifikovat objekty. Nakonec inicia´tor ozna´mı´ prˇa´nı´, aby se vsˇechny strany zava´zaly (to commit – zava´zat se) k provedeny´m zmeˇna´m. Pokud neˇktery´ z procesu˚ odmı´tne (nebo havaruje prˇed potvrzenı´m transakce), situace se vra´tı´ prˇesneˇ do stavu prˇed zapocˇetı´m transakce, tj. vsˇechny zmeˇny na objektech jsou zrusˇeny. 1.1 Primitiva pro programova´nı´ transakcı´ Jazyky pro manipulaci dat musejı´ obsahovat za´kladnı´ primitiva pro programova´nı´ transakcı´. Konkre´tnı´ seznam primitiv samozrˇejmeˇ za´visı´ na jazyce. Jako prˇ´ıklad pro dalsˇ´ı diskusi zvolı´me teˇchto 5 primitiv: START – zacˇa´tek transakce, na´sledujı´cı´ prˇ´ıkazy budou tvorˇit transakci. Prˇ´ıkaz pro start transakce mu˚zˇe by´t zada´n explicitneˇ nebo je implicitneˇ prˇedpokla´da´n. COMMIT – ukoncˇenı´ transakce a pokus o zajisˇteˇnı´ skutecˇne´ho provedenı´ zmeˇn v databa´zi. ABORT – zrusˇenı´ transakce, na´vrat do stavu prˇed zapocˇetı´m transakce READ – prˇecˇtenı´ dat WRITE – za´pis dat Uvnitrˇ transakce je mozˇne´ pouzˇ´ıt libovolny´ prˇ´ıkaz pro modifikaci databa´ze, v nasˇem jednoduche´m modelu vsˇak budeme prˇedpokla´dat, zˇe se slozˇiteˇjsˇ´ı operace skla´dajı´ z primitivnı´ch operacı´ cˇtenı´ a za´pisu. Prova´deˇnı´ aplikacˇnı´ho programu v databa´zove´m prostrˇedı´ mu˚zˇeme cha´pat jako posloupnost atomicky´ch transakcı´, mezi ktery´mi se prova´dı´ nedataba´zove´ operace. Prˇ´ıklad: Meˇjme bankovnı´ aplikaci, ve ktere´ chceme prˇesunout jistou cˇa´stku mezi dveˇma u´cˇty. Operace bude provedena v teˇchto krocı´ch: ?

Napsa´no v prosinci 1996, poslednı´ u´prava: leden 2003. Sazba TEXem.

–1–

 

  

Program 1

  

Program 2

  

Program 3

  



  

  

  




Obra´zek 1: Transakce (tlustou cˇarou) jsou prokla´da´ny nedataba´zovy´mi operacemi.

START T1 READ KONTO1 ˇA ´STKA KONTO1 := KONTO1 - C WRITE KONTO1 READ KONTO2 ˇA ´STKA KONTO2 := KONTO2 + C WRITE KONTO2 COMMIT T1 Je zrˇejme´, zˇe transakce musı´ by´t provedena atomicky, jinak by mohlo dojı´t ke „ztra´cenı´“ peneˇz. 1.2

Vlastnosti transakcı´

Transakce musı´ mı´t tyto vlastnosti:1 1. atomicˇnost (atomicity) – pro „vneˇjsˇ´ı sveˇt“ je transakce atomicka´, tj. tvorˇ´ı nedeˇlitelnou jednotku 2. izolovana´ vratnost – vra´cenı´ (zrusˇenı´) transakce nema´ vliv na jine´ transakce 3. trvalost (durability) – u´speˇsˇna´ transakce zpu˚sobı´ ulozˇenı´ zmeˇn v ba´zi dat. 4. uporˇa´datelnost (serializability) – vy´sledek soubeˇzˇneˇ prova´deˇny´ch transakcı´ je stejny´ jako neˇktere´ (syste´moveˇ za´visle´) se´riove´ provedenı´ teˇchto transakcı´. 1.3

Stavy transakce

Transakce se po dobu sve´ho zˇivota mu˚zˇe dostat do jednoho z peˇti stavu˚: – – – – – 1

aktivnı´ (A) – stav od pocˇa´tku prova´deˇnı´ transakce cˇa´stecˇneˇ potvrzeny´ (PC) – stav po provedenı´ poslednı´ operace transakce chybny´ (F) – v pru˚beˇhu transakce nelze pokracˇovat zrusˇeny´ (AB) – stav po skoncˇenı´ operace ABORT potvrzeny´ (C) – stav po u´speˇsˇne´m skoncˇenı´, tj. po dokoncˇenı´ operace COMMIT

Nutno poznamenat, zˇe ru˚znı´ autorˇi vycha´zejı´ prˇi diskuzi transakcı´ z poneˇkud odlisˇny´ch mnozˇin za´kladnı´ch vlastnostı´ – pravdeˇpodobneˇ neexistuje vsˇeobecneˇ uzna´vana´ minima´lnı´ mnozˇina.

–2–

START

A

PC

COMMIT

C

F

ABORT

AB

Obra´zek 2: Stavy transakce. 1.4

Loka´lnı´ a distribuovane´ transakce

V distribuovane´m databa´zove´m prostrˇedı´ mu˚zˇe transakce prˇistupovat k datu˚m ulozˇeny´m ve vı´ce uzlech. Takove´ transakci rˇ´ıka´me distribuovana´ nebo globa´lnı´. Naproti tomu loka´lnı´ transakce prˇistupuje pouze k datu˚m jedine´ho uzlu a nevyzˇaduje spolupra´ci s transakcemi v jiny´ch uzlech. Distribuovane´ transakce jsou spusˇteˇny z jednoho uzlu a podle potrˇeby spousˇteˇjı´ dalsˇ´ı, dı´lcˇ´ı transakce (sub-transactions). Pu˚vodnı´ (prima´rnı´) transakce veˇtsˇinou prˇebı´ra´ koordinaci distribuovane´ transakce. Tato koordinace zahrnuje synchronizaci se soubeˇzˇny´mi loka´lnı´mi transakcemi a s ostatnı´mi globa´lnı´mi transakcemi, ktere´ jsou v syste´mu aktivnı´. T1 T11

T12 T12

T12

1

A

B

2

C

D

E

Obra´zek 3: Spousˇteˇnı´ podtransakcı´ v distribuovane´m syste´mu. Z toho je zrˇejme´, zˇe distribuovanost podstatneˇ zvysˇuje slozˇitost koordinace transakcı´.

2

Implementace

Modul, ktery´ je v syste´mu rˇ´ızenı´ ba´ze dat (SRˇBD) zodpoveˇdny´ za synchronizaci se nazy´va´ pla´novacˇ (scheduler), protozˇe rozvrhuje transakce tak, aby nedosˇlo k jejich vza´jemne´mu ovlivneˇnı´. Aplikacˇnı´ programy komunikujı´ s pla´novacˇem prostrˇednictvı´m spra´vce transakcı´ (transaction manager), ktery´ pro aplikace prova´dı´ koordinaci databa´zovy´ch operacı´. Nynı´ se budeme zaby´vat tı´m, jak se vy´sˇe uvedene´ vlastnosti implementujı´. Nejprve budou strucˇneˇ popsa´ny mechanismy implementace loka´lnı´ch transakcı´ (v distribuovane´m syste´mu je prova´dı´ loka´lnı´ agent), pote´ budou popsa´ny mechanismy, pouzˇ´ıvane´ v distribuovane´m prostrˇedı´. 2.1

Loka´lnı´ transakce

V na´sledujı´cı´m oddı´le popı´sˇeme neˇktere´ mechanismy pro implementaci loka´lnı´ch transakcı´ – mechanismus soukrome´ pracovnı´ oblasti a tvorbu zˇurna´lu. Pro zajisˇteˇnı´ konzistence databa´ze i v prˇ´ıpadeˇ vy´padku se tyto metody cˇasto kombinujı´ s mechanismem stabilnı´ pameˇti. –3–

A

B

C

aplikace

spravce transakci planovac komunik. medium

lokalni spravce transakci

lok. agent

lok. agent

lok. agent

DB

DB

DB

lokalni planovac

Obra´zek 4: Zjednodusˇena´ koncepce distribuovane´ho SRˇBD. 2.1.1

Stabilnı´ pameˇt’

ˇ BD je zabezpecˇit zotavenı´ z prˇ´ıpadny´ch chyb. Neˇktere´ syste´my Prvorˇadou funkcı´ kvalitnı´ho SR proto pro uchova´nı´ kriticky´ch informacı´ o pru˚beˇhu transakce pouzˇ´ıvajı´ tzv. stabilnı´ pameˇt’. Stabilnı´ pameˇt’je mozˇne´ implementovat pomocı´ dvojice disku˚ (viz obr. 5), kde druhy´ disk je prˇesnou kopiı´ prvnı´ho. Kazˇdy´ blok se se nejprve zapı´sˇe na prvnı´ disk a prˇecˇtenı´m se oveˇrˇ´ı bezchybnost za´pisu, pak se provede tote´zˇ pro druhy´ disk. Prˇedpokla´dejme, zˇe syste´m havaruje po za´pisu bloku na prvnı´ disk. Prˇi zotavova´nı´ se z chyby syste´m porovna´ obsah obou disku˚. Pokud nalezne rozdı´l, bude prˇedpokla´dat zˇe blok na na prvnı´m disku je spra´vny´, protozˇe byl zapsa´n drˇ´ıve. Prˇi chybeˇ kontrolnı´ho soucˇtu mu˚zˇe by´t vadny´ blok regenerova´n z odpovı´dajı´cı´ho bloku na druhe´m disku. 2.1.2

Soukroma´ pracovnı´ oblast

Prˇi zapocˇetı´ transakce je procesu koncepcˇneˇ da´n k dispozici soukromy´ pracovnı´ prostor, obsahujı´cı´ vsˇechny objekty, ke ktery´m ma´ proces prˇ´ıstup. Vesˇkere´ operace pak prova´dı´ v tomto pracovnı´m prostoru azˇ do dokoncˇenı´ transakce. Toto pozorova´nı´ vede k prvnı´ implementacˇnı´ metodeˇ, totizˇ vytvorˇenı´ skutecˇne´ho soukrome´ho pracovnı´ho prostoru pro transakci. Ve skutecˇnosti by ovsˇem cena takove´ operace byla prˇ´ılisˇ vysoka´, proto se pouzˇ´ıva´ neˇkolik optimalizacı´. Prˇi spusˇteˇnı´ transakce je vytvorˇena pra´zdna´ pracovnı´ oblast (viz obr. 6), ktera´ obsahuje pouze odkaz na skutecˇnou databa´zi (nebo – pro podtransakci – na rodicˇovskou pracovnı´ oblast). Pokud je za´znam pozˇ´ıva´n pouze pro cˇtenı´, nenı´ nutno vytva´rˇet jeho kopii. Syste´m sleduje odkazy, dokud nedojde k za´znamu v pracovnı´ oblasti neˇktere´ho prˇedka. V prˇ´ıpadeˇ za´pisu je za´znam nalezen stejny´m zpu˚sobem jako pro cˇtenı´ a jeho kopie je vlozˇena do soukrome´ho pracovnı´ho prostoru spolu s indexem prˇ´ıslusˇne´ databa´ze. Dı´ky soukrome´mu indexu je mozˇne´ cˇ´ıst data obvykly´m zpu˚sobem, protozˇe obsahuje odkazy na pu˚vodnı´ za´znamy. Prˇi pokusu o za´pis je vytvorˇena nova´ kopie za´znamu a odkaz na nı´ je vlozˇen do indexu. –4–

WRITE 1 verify 1

Disk 1 7

Disk 1 7

0

6

1

6

5

2

5

4

Disk 1

3

Disk 2 7

7

0

6

1

6

5

2

5

4

3

a)

3

0

4

3

7

0

6

chyba sektoru

1

5

2 3

b)

2

Disk 2

1

4

1

5

2

WRITE 1 verify 1

0

6

1

4

Disk 2

7

0

2 4

3

c)

Obra´zek 5: Za´pis a zotavenı´ stabilnı´ pameˇti. Prˇi zrusˇenı´ transakce stacˇ´ı zrusˇit soukromou pracovnı´ oblast. Dokoncˇenı´ transakce znamena´ atomicky´ za´pis soukrome´ho indexu do rodicˇovske´ho pracovnı´ho prostoru. Stejny´m zpu˚sobem se neˇkdy implementujı´ transakcˇnı´ souborove´ syste´my. Jako index zde slouzˇ´ı i-uzel souboru (nebo obdobna´ datova´ struktura) a jako za´znamy se cha´pou logicke´ bloky souboru. 2.1.3

Tvorba zˇurna´lu

Dalsˇ´ı zna´me´ strategie vyuzˇ´ıvajı´ tvorby zˇurna´lu, a to s bezprostrˇednı´ nebo odlozˇenou realizacı´ zmeˇn. Zˇurna´l (log) je obvykle zapisova´n do stabilnı´ pameˇti. Inkrementa´lnı´ tvorba zˇurna´lu s bezprostrˇednı´ realizacı´ zmeˇn. V te´to metodeˇ je databa´ze modifikova´na na mı´steˇ, ale prˇed kazˇdou fyzickou zmeˇnou databa´ze je do zˇurna´lu zapsa´n za´znam obsahujı´cı´ cˇtverˇici: Prˇi startu a dokoncˇenı´ transakce jsou do zˇurna´lu zapsa´ny za´znamy resp. . Prˇi dokoncˇenı´ transakce nenı´ trˇeba databa´zi modifikovat. V prˇ´ıpadeˇ zrusˇenı´ transakce je mozˇne´ pomocı´ zˇurna´lu dojı´t k pu˚vodnı´mu stavu. Syste´m procha´zı´ zˇurna´l od konce a rusˇ´ı zmeˇny, ktere´ transakce provedla v databa´zi. Tato akce se nazy´va´ zpeˇtny´ chod (rollback). –5–

index

index

1 2 3 4 5 START T

soukr. prac. prostor

1 2 3 4 5 3’ WRITE 3

1

index

4 5 3

1 2 COMMIT T

1

Obra´zek 6: Implementace soukrome´ pracovnı´ oblasti. Zˇurna´l je take´ mozˇno pouzˇ´ıt pro zotavenı´ z chyb. Ve fa´zi zotavenı´ syste´m projde zˇurna´l, aby zjistil, zda v dobeˇ hava´rie nebyla neˇktera´ transakce aktivnı´ a nedokoncˇenou transakci odcˇinı´. Da´le je nutne´ prove´st znovu ty transakce, ktere´ byly prˇed hava´riı´ u´plne´ (existuje pro neˇ za´znam COMMIT), ale nebyly dokoncˇeny fyzicky (nebyl proveden za´pis vyrovna´vacı´ch pameˇtı´ na disk). Inkrementa´lnı´ tvorba zˇurna´lu s odlozˇeny´mi realizacemi zmeˇn. V te´to metodeˇ se vsˇechny zmeˇny zapisujı´ do zˇurna´lu, skutecˇne´ zmeˇny databa´ze jsou odlozˇeny azˇ do okamzˇiku dokoncˇenı´ transakce. Pro kazˇdou operaci zmeˇny je do zˇurna´lu zapsa´na trojice . Dokoncˇenı´ transakce zapı´sˇe za´znam COMMIT a spustı´ za´pis zmeˇn do databa´ze. Prˇedpokla´dejme, zˇe zhroucenı´ syste´mu nastalo po za´pisu za´znamu COMMIT do zˇurna´lu, ale prˇed provedenı´m fyzicke´ zmeˇny v databa´zi. V takove´m prˇ´ıpadeˇ stacˇ´ı znovu spustit za´pis operacı´, zaznamenany´ch v zˇurna´lu. Neˇktere´ syste´my mı´sto stabilnı´ pameˇti vyuzˇ´ıvajı´ mechanismus kontrolnı´ch bodu˚ (checkpoints), ktere´ se vytva´rˇejı´ automaticky v jisty´ch cˇasovy´ch intervalech v pru˚beˇhu prova´deˇnı´ transakce. Kontrolnı´ body zahrnujı´ za´pis vyrovna´vacı´ch pameˇtı´ na disk (flush) a za´pis kontrolnı´ho za´znamu (checkpoint record) do zˇurna´lu. V takove´m syste´mu lze prove´st zotavenı´ z chyb jen do poslednı´ho kontrolnı´ho bodu. 2.2

Dvoufa´zovy´ potvrzovacı´ protokol

Jizˇ bylo rˇecˇeno, zˇe z vneˇjsˇ´ıho pohledu musı´ by´t transakce atomicka´. V distribuovane´m databa´zove´m syste´mu vsˇak mu˚zˇe potvrzenı´ transakce vyzˇadovat spolupra´ci vı´ce podtransakcı´ beˇzˇ´ıcı´ch v ru˚zny´ch uzlech, kde kazˇdy´ proces vlastnı´ neˇktere´ objekty modifikovane´ transakcı´. Pro atomicke´ potvrzenı´ distribuovane´ transakce se nejcˇasteˇji pouzˇ´ıva´ dvoufa´zovy´ potvrzovacı´ protokol (viz obr. 7). –6–

Jeden z procesu˚ prˇebı´ra´ u´lohu koordina´tora globa´lnı´ transakce. Obvykle je to proces rˇ´ıdı´cı´ prima´rnı´ transakci. Potvrzovacı´ protokol zacˇ´ına´ koordina´tor za´pisem za´znamu o zacˇa´tku potvrzovacı´ho protokolu do zˇurna´lu. Pote´ koordina´tor posˇle vsˇem podrˇ´ızeny´m transakcı´m zpra´vu, zˇa´dajı´cı´ podrˇ´ızene´ transakce o potvrzenı´ jejich prˇipravenosti zverˇejnit provedene´ zmeˇny. Kazˇdy´ podrˇ´ızeny´ proces po prˇijetı´ zpra´vy rozhodne, zda mu˚zˇe potvrdit dokoncˇenı´ transakce a sve´ rozhodnutı´ zapı´sˇe do zˇurna´lu a posˇle o neˇm zpra´vu koordina´torovi. Ten po prˇijetı´ vsˇech zpra´v urcˇ´ı, zda ma´ globa´lnı´ transakci dokoncˇit nebo zrusˇit. Transakci je mozˇne´ dokoncˇit jen tehdy, jsou-li rozhodnutı´ vsˇech podrˇ´ızeny´ch kladna´. Pokud neˇktery´ proces rozhodnul za´porneˇ nebo neodpovı´-li ve stanovene´ lhu˚teˇ, koordina´tor transakci zrusˇ´ı. Koordina´tor zapı´sˇe do zˇurna´lu za´znam o sve´m rozhodnutı´ a posˇle zpra´vu vsˇem podrˇ´ızeny´m transakcı´m. Podrˇ´ızene´ procesy po prˇijetı´ zpra´vy zverˇejnı´ sve´ zmeˇny. podtransakce

koordin. "konec transakce" od aplikace "PREPARE" stabil. pam.

"REQUEST to PREPARE" "PREPARE"

paket

stabil. pam.

"YES" paket

"COMMIT" stabil. pam.

"COMMIT" pro aplikaci "COMMIT"

"DECIDED to COMMIT" paket

stabil. pam.

"DONE" paket

Obra´zek 7: Dvoufa´zove´ potvrzenı´. Prˇi hava´rii v ktere´mkoli kroku potvrzova´nı´ je mozˇne´ urcˇit z zˇurna´lu, ve ktere´m stavu se transakce v dobeˇ hava´rie nacha´zela a prˇ´ıpadeˇ prove´st prˇ´ıslusˇny´ krok znovu. Transakce je dokoncˇena jizˇ za´pisem za´znamu do zˇurna´lu, a to bez ohledu na dalsˇ´ı uda´losti. Pokud koordina´tor po za´pisu havaruje, ve fa´zi zotavenı´ pouze znovu posˇle sve´ rozhodnutı´ vsˇem podrˇ´ızeny´m. Pokud havaruje neˇktery´ podrˇ´ızeny´ po odesla´nı´ odpoveˇdi na prvnı´ zpra´vu, koordina´tor se bude bude opakovaneˇ pokousˇet zaslat mu zpra´vu o sve´m rozhodnutı´. V rea´lny´ch syste´mech se dvoufa´zove´ potvrzova´nı´ pouzˇ´ıva´ zrˇ´ıdka v te´to cˇiste´ podobeˇ. Obvyklou optimalizacı´ je, zˇe dvoufa´zove´ho protokolu se neu´cˇastnı´ transakce, skla´dajı´cı´ se pouze z operacı´ READ. –7–

3

Interference soubeˇzˇny´ch transakcı´

V dosavadnı´ diskusi jsme dosud neuvazˇovali soubeˇzˇne´ prova´deˇnı´ transakcı´. Je zrˇejme´, zˇe operace soubeˇzˇny´ch transakcı´ nelze prokla´dat libovolneˇ, protozˇe by mohlo dojı´t k porusˇenı´ konzistence databa´ze. Dva prˇ´ıklady takove´ interference je ztraceny´ za´pis a nekonzistentnı´ cˇtenı´. Ztra´ta za´pisu by nastala v prˇ´ıpadeˇ, zˇe by u´speˇsˇny´ za´pis byl zvra´cen za´pisem jine´ transakce. Nekonzistentnı´ cˇtenı´ by mohlo nastat v prˇ´ıpadeˇ, zˇe by transakci byly prˇ´ıstupne´ cˇa´stecˇne´ vy´sledky neˇktere´ nedokoncˇene´ transakce. Tyto proble´my by nemohly nastat, kdyby SRˇBD dovolil pouze se´riovy´ beˇh transakcı´. Cı´lem SRˇBD je vsˇak take´ zajistit co nejvysˇsˇ´ı pru˚chodnost, je trˇeba nale´zt takove´ usporˇa´da´nı´ operacı´, ktere´ dovolı´ soubeˇzˇny´ beˇh transakcı´ bez vza´jemne´ interference. 3.1

Usporˇadatelnost rozvrhu˚

Jednı´m ze za´kladnı´ch pozˇadavku˚ na prova´deˇnı´ posloupnosti transakcı´ je tedy usporˇadatelnost (serializability), tj. vy´sledek soubeˇzˇneˇ prova´deˇny´ch transakcı´ musı´ by´t stejny´ jako neˇktere´ se´riove´ provedenı´ teˇchto transakcı´. Stanovene´ porˇadı´ prova´deˇnı´ operacı´ vı´ce transakcı´ v cˇase nazy´va´me rozvrhem. Rozvrh S zapisujeme obecneˇ S = [O1 , O2 , O3 , . . . Om ] kde Oi znamena´ operaci READ nebo WRITE a Oi prˇedcha´zı´ v cˇase operaci O j , jestlizˇe i < j. Se´riovy´ rozvrh je takovy´ rozvrh, ktery´ zachova´va´ operace kazˇde´ transakce pohromadeˇ. Abychom potvrdili spra´vnost rozvrhu, stacˇ´ı uka´zat, zˇe vy´sledek jı´m urcˇene´ posloupnosti operacı´ je ekvivalentnı´ vy´sledku operacı´ neˇktere´ho se´riove´ho rozvrhu. Ma´me-li rozvrhy S1 a S2 pro transakce T1 , . . . , Tn , pak rozvrhy S1 a S2 jsou ekvivalentnı´, jsou-li splneˇny tyto podmı´nky: 1. Jestlizˇe v jenom rozvrhu je operace READ A v transakci Ti a jejı´ hodnota vznikla za´pisem WRITE A v T j , pak tote´zˇ musı´ by´t zachova´no ve druhe´m rozvrhu. 2. Jestlizˇe v jednom rozvrhu je poslednı´ instrukce WRITE A v transakci Ti , pak tote´zˇ musı´ by´t zachova´no ve druhe´m rozvrhu. Rozvrh je usporˇadatelny´, jestlizˇe pro neˇj existuje ekvivalentnı´ se´riovy´ rozvrh. Kazˇdy´ usporˇadatelny´ rozvrh je spra´vny´, mohou vsˇak existovat i spra´vne´ rozvrhy, ktere´ nejsou ekvivalentnı´ se zˇa´dny´m se´riovy´m rozvrhem. Testova´nı´ usporˇadatelnosti lze prova´deˇt algoritmicky, ale pro obecny´ rozvrh je to NP-u´plny´ proble´m. Prˇi zavedenı´ dodatecˇne´ podmı´nky, zˇe kazˇde´mu WRITE A prˇedcha´zı´ READ A, lze usporˇadatelnost otestovat v cˇase O(n2 ) konstrukcı´ grafu za´vislosti transakcı´. Graf za´vislosti transakcı´ konstruujeme takto: 1. Do grafu vlozˇ´ıme uzel pro kazˇdou transakci. 2. Jestlizˇe v rozvrhu je operace WRITE A transakce Ti drˇ´ıve nezˇ operace READ A transakce T j , vlozˇ´ıme hranu (T j , Ti ). 3. Jestlizˇe v rozvrhu je operace READ A transakce Ti drˇ´ıve nezˇ operace WRITE A transakce T j , vlozˇ´ıme hranu (Ti , T j ).

–8–

Hrana (Ti , T j ) v grafu indikuje, zˇe v ktere´mkoli ekvivalentnı´m se´riove´m rozvrhu musı´ Ti prˇedcha´zet T j . Rozvrh je usporˇadatelny´, jestlizˇe v jeho grafu za´vislosti transakcı´ nenı´ zˇa´dny´ cyklus. Prˇ´ıklad: S1 = [T1 , T2 ] S2 = [READ1 A, READ2 A, WRITE2 A, WRITE1 A] S1 :

S2 : T1

3.2

T2

T1

T2

Synchronizace prˇ´ıstupu k databa´zi

Protozˇe distribuovane´ transakce jsou prova´deˇny soubeˇzˇneˇ ru˚zny´mi procesy v ru˚zny´ch uzlech, vznika´ potrˇeba mechanismu synchronizace prˇ´ıstupu k databa´zi. V dalsˇ´ım textu popı´sˇeme trˇi beˇzˇneˇ pouzˇ´ıvane´ metody synchronizace – dvoufa´zove´ zamyka´nı´, optimisticke´ rˇ´ızenı´ a metodu cˇasovy´ch razı´tek. 3.2.1

Zamykacı´ protokoly

Zamyka´nı´ je akce, kterou si proces vyhrazuje prˇ´ıstup k objektu. Zamyka´nı´ a odemyka´nı´ objektu˚ je v databa´zovy´ch syste´mech prova´deˇno obvykle automaticky prostrˇednictvı´m spra´vce transakcı´, takzˇe nevyzˇaduje zˇa´dne´ u´silı´ ze strany aplikacˇnı´ho programa´tora. Kazˇdy´ objekt musı´ by´t uzamcˇen drˇ´ıve, nezˇ k neˇmu bude transakce prˇistupovat. Uzamykacı´ modul prohleda´ tabulku za´mku˚ a pokud objekt jizˇ nenı´ zamcˇen, jeho zamcˇenı´ provede. V prˇ´ıpadeˇ, zˇe objekt nelze uzamknout, mu˚zˇe proces cˇekat na uvolneˇnı´ za´mku (pak ale hrozı´ uvı´znutı´) nebo transakci zrusˇit. V distribuovany´ch syste´mech mu˚zˇe by´t spra´va za´mku˚ bud’ centra´lnı´ nebo v kazˇde´m uzlu pro loka´nı´ data. V prˇ´ıpadeˇ centra´lnı´ho uzamyka´nı´ je mozˇne´ uvı´znutı´ detekovat pomocı´ konstrukce grafu vza´jemny´ch za´vislostı´,2 nevy´hodou jsou vysoke´ komunikacˇnı´ na´klady a zranitelnost syste´mu vy´padkem uzlu spravujı´cı´ho za´mky. Obvykle vsˇak lze graf vza´jemny´ch za´vislostı´ konstruovat bez prˇ´ılisˇny´ch prˇ´ıdavny´ch na´kladu˚ alesponˇ pro loka´lnı´ podtransakce. Pro globa´lnı´ transakce se cˇasto urcˇuje cˇasovy´ limit, jehozˇ vyprsˇenı´ se povazˇuje za uvı´znutı´. Mnohem lepsˇ´ı metodou je dvoufa´zove´ zamyka´nı´, ve ktere´m za´mky alokujeme v neˇjake´m kanonicke´m porˇadı´.3 V prvnı´ fa´zi transakce uzamyka´ vsˇechny objekty, ke ktery´m bude prˇistupovat, ve druhe´ fa´zi za´mky pouze uvolnˇuje. V tomto za´kladnı´m schematu mu˚zˇeme zvy´sˇit stupenˇ paralelismu transakcı´, pokud budeme rozlisˇovat za´mky sdı´lene´ (pro operaci cˇtenı´) a vy´lucˇne´ (pro za´pis). Pokud je za´znam zamcˇen sdı´leny´m za´mkem a jina´ transakce k neˇmu potrˇebuje prˇ´ıstup pro cˇtenı´, mu˚zˇe jej take´ zamknout sdı´leny´m za´mkem. Sdı´lene´ za´mky zajistı´, zˇe za´znam nebude modifikova´n (vyloucˇ´ı vsˇechny snahy o za´pis), ale dovolı´ ostatnı´m transakcı´m za´znam cˇ´ıst. Pokud je za´znam zamcˇen vy´lucˇny´m za´mkem, zˇa´dne´ dalsˇ´ı zamcˇenı´ jizˇ nenı´ mozˇne´. Samotne´ dvoufa´zove´ zamyka´nı´ je poneˇkud silneˇjsˇ´ı, nezˇ je nutne´. Pokud transakce za´znam pouze cˇte, mu˚zˇe ho uvolnit, jakmile ho prˇestane potrˇebovat. Pokud byl za´znam naopak modifikova´n, jeho uvolneˇnı´ je mozˇne´ azˇ ve druhe´ fa´zi. 2 3

Prevence a detekce uvı´znutı´ je klasicke´ te´ma operacˇnı´ch syste´mu˚, viz naprˇ. [6], kapitola 3. Kanonicke´ porˇadı´ alokace za´mku˚ je postacˇujı´cı´ podmı´nka pro zabra´neˇnı´ uvı´znutı´.

–9–

1



2






Obra´zek 8: Dvoufa´zove´ zamyka´nı´. Pocˇet za´mku˚ alokovany´ch procesem je nejveˇtsˇ´ı v bodeˇ tl , tzv. bodeˇ uzamcˇenı´. Prˇedpokla´dejme, zˇe by transakce za´mek uvolnila po provedenı´ za´pisu. Neˇktera´ jina´ transakce mohla za´znam zamknout, prove´st neˇjakou operaci a transakci potvrdit. Kdyby pak byla pu˚vodnı´ transakce zrusˇena, musela by by´t zrusˇena i druha´ (jizˇ potvrzena´) transakce, protozˇe prova´deˇla operaci nad hodnotami, ktere´ nemeˇly existovat. Te´to situaci se rˇ´ıka´ dominovy´ efekt (cascaded abort) a jejı´mu vzniku se snazˇ´ıme zamezit naprˇ. jizˇ popsany´m dvoufa´zovy´m zamyka´nı´m. Dvoufa´zove´ zamyka´nı´ se pouzˇ´ıva´ velmi cˇasto, mimo jine´ i proto, zˇe pokud vsˇechny transakce pouzˇ´ıvajı´ dvoufa´zove´ zamyka´nı´, je kazˇdy´ jejich lega´lnı´ rozvrh usporˇadatelny´. 3.2.2

Optimisticke´ rˇ´ızenı´

Mysˇlenka metody optimisticke´ho rˇ´ızenı´ je jednoducha´ – transakce prova´dı´ cˇtenı´ a za´pis podle potrˇeby, operace za´pisu se prova´deˇjı´ do soukrome´ pracovnı´ oblasti. Prˇ´ıpadne´ konflikty se rˇesˇ´ı azˇ ve fa´zi potvrzenı´. Kazˇda´ transakce musı´ uchova´vat informaci o mnozˇineˇ cˇteny´ch a zapisovany´ch za´znamu˚. Transakci je mozˇne´ potvrdit, jestlizˇe pro vsˇechny starsˇ´ı transakce platı´ alesponˇ jedna z na´sledujı´cı´ch podmı´nek: – Starsˇ´ı transakce skoncˇila prˇed spusˇteˇnı´m testovane´ transakce. – Starsˇ´ı transakce skoncˇila drˇ´ıve, nezˇ aktua´lnı´ transakce zverˇejnı´ sve´ zmeˇny a mnozˇina za´znamu˚ cˇteny´ch aktua´lnı´ transakcı´ je disjunktnı´ s mnozˇinou za´znamu˚, ktere´ zapsala starsˇ´ı transakce. To znamena´, zˇe aktua´lnı´ transakce nemohla prˇepsat starsˇ´ı transakci (starsˇ´ı transakce skoncˇila drˇ´ıve), a data zapsana´ starsˇ´ı transakcı´ neovlivnila aktua´lnı´ transakci. – Starsˇ´ı transakce prˇejde do fa´ze potvrzenı´ drˇ´ıve, nezˇ aktua´lnı´ transakce, a mnozˇina za´znamu˚ cˇteny´ch nebo zapisovany´ch aktua´lnı´ transakcı´ je disjunktnı´ s mnozˇinou za´znamu˚, zapsany´ch starsˇ´ı transakcı´. Pro testova´nı´ vy´sˇe uvedeny´ch podmı´nek se zava´dı´ cˇasova´ razı´tka. Prˇi spusˇteˇnı´ transakce a prˇi prˇechodu do fa´ze potvrzenı´ jsou transakci prˇirˇazena cˇasova´ razı´tka stn(T ) a fnt(T ), ktera´ se pouzˇ´ıvajı´ pouze v potvrzovacı´ fa´zi. Po potvrzenı´ je transakci prˇirˇazeno definitivnı´ cˇasove´ razı´tko tn(T ). Vy´sˇe uvedene´ podmı´nky pak mu˚zˇeme testovat podle na´sledujı´cı´ho algoritmu: Necht’ R(T ) a W (T ) je mnozˇina dat cˇteny´ch, resp. zapisovany´ch transakcı´ T . Pak aktua´lnı´ transakce Ta je platna´, platı´-li pro kazˇdou jizˇ potvrzenou transakci Ti alesponˇ jedna z na´sledujı´cı´ch podmı´nek: – 10 –

START T

A

stn(T)

RC

COMMIT

ftn(T)

tn(T)

Obra´zek 9: Cˇasova´ razı´tka prˇirˇazena´ transakci v metodeˇ optimisticke´ho rˇ´ızenı´. • tn(Ti ) ≺ stn(Ta ) • tn(Ti ) ≺ ftn(Ta ) ∧W (Ti ) ∩ R(Ta ) = 0/ • ftn(Ti ) ≺ ftn(Ta ) ∧W (Ti ) ∩ (R(Ta ) ∪W (Ta )) = 0/

V distribuovany´ch syste´mech se nejprve oveˇrˇujı´ loka´lnı´ podtransakce potvrzovane´ transakce. Pote´ je provedeno globa´lnı´ oveˇrˇenı´, zda je usporˇa´da´nı´ podtransakcı´ ve vsˇech loka´lnı´ch uzlech stejne´. Pokud nenastal konflikt, transakce zviditelnı´ sva´ data, v opacˇne´m prˇ´ıpadeˇ je pracovnı´ prostor zrusˇen a transakce spusˇteˇna znovu. Metoda optimisticke´ho rˇ´ızenı´ dovoluje maxima´lnı´ paralelismus, protozˇe transakce na sebe nemusı´ nikdy cˇekat. Metoda je vhodna´, pokud jsou transakce vzda´leny v cˇase a dominujı´ operace cˇtenı´. Se zvysˇujı´cı´m se zatı´zˇenı´m syste´mu vsˇak roste pravdeˇpodobnost konfliktu, cozˇ prudce zhorsˇuje vy´konnost syste´mu. Proto ji zˇa´dny´ z beˇzˇny´ch SRˇBD nepouzˇ´ıva´. 3.2.3

Metoda cˇasovy´ch razı´tek

Dalsˇ´ı optimistickou metodou je metoda cˇasovy´ch razı´tek. Kazˇde´ transakci T prˇirˇadı´me v okamzˇiku spusˇteˇnı´ jedinecˇne´ cˇasove´ razı´tko ts(T ), naprˇ. pomocı´ Lamportova algoritmu pro usporˇa´da´nı´ uda´lostı´ v distribuovane´m syste´mu. Transakce zapisujı´ do soukrome´ pracovnı´ oblasti. S kazˇdy´m za´znamem x je sdruzˇeno cˇasove´ razı´tko tsr (x) pro cˇtenı´ a tsw (x) pro za´pis, ktere´ rˇ´ıka´, ktera´ transakce za´znam cˇetla nebo zapisovala naposledy. Pokud chce transakce za´znam cˇ´ıst a za´znam byl modifikova´n neˇkterou mladsˇ´ı transakcı´ (tj. ts(Ta ) ≺ tsw (x)), je transakce zrusˇena. Pokud neˇktera´ starsˇ´ı nepotvrzena´ transakce za´znam modifikovala ve sve´m soukrome´m pracovnı´m prostoru, musı´ operace READ cˇekat do potvrzenı´ nebo zrusˇenı´ te´to starsˇ´ı transakce. Provedenı´ operace READ pak nastavı´ novou hodnotu cˇasove´ho razı´tka tsr (x). Prˇi pokusu o za´pis je transakce zrusˇena, pokud byl za´znam zapisova´n neˇkterou mladsˇ´ı transakcı´ (tj. pokud ts(Ta ) ≺ tsr (x) ∨ ts(Ta ) ≺ tsw (x)). Provedenı´ za´pisu nastavı´ novou hodnotu razı´tka tsw (x). Aby byl dodrzˇen pozˇadavek usporˇadatelnosti, musı´ by´t prˇi operaci COMMIT zviditelneˇnı´ dat z pracovnı´ oblasti provedeno v porˇadı´ cˇasovy´ch razı´tek transakcı´. Pokud ma´ potvrzovana´ transakce ve sve´ pracovnı´ oblasti za´znam, ktery´ ve sve´ pracovnı´ oblasti modifikovala neˇktera´ starsˇ´ı, dosud nepotvrzena´ transakce, musı´ transakce cˇekat na potvrzenı´ nebo zrusˇenı´ te´to starsˇ´ı transakce. Metoda cˇasovy´ch razı´tek produkuje usporˇadatelne´ rozvrhy, ekvivalentnı´ rozvrhu, definovane´mu posloupnostı´ potvrzeny´ch transakcı´ v porˇadı´ jejich cˇasovy´ch razı´tek.

4

Za´veˇr

Zpracova´nı´ transakcı´ je centra´lnı´ soucˇa´stı´ soucˇasny´ch databa´zovy´ch syste´mu˚. V tomto cˇla´nku jsme provedli diskusi neˇktery´ch metod, ktery´mi se transakcˇnı´ zpracova´nı´ implementuje. – 11 –

Literatura 1. Bell, David – Grimson, Jane: Distributed Database Systems. Addison Wesley, Reading 1992. 2. Lain, William A. – Johnson, James E. – Landau, Robert V.: Transaction Management Support in the VMS Operating System Kernel. Digital Technical Journal, vol. 3 no. 1 (Winter 1991): 33–44. 3. Oracle7 Server Distributed Systems, vol. I: Ditributed Data. On-line manua´l. April 1995. 4. Pokorny´, Jaroslav: Pocˇ´ıtacˇove´ databa´ze. Kancela´rˇske´ stroje, Praha 1991. 5. Sokolowsky, Peter – Pokorny´, Jaroslav – Peterka Jirˇ´ı: Distribuovane´ databa´zove´ syste´my. Skripta MFF UK, Praha 1992. 6. Tanenbaum, Andrew S.: Modern Operating Systems (2nd ed.). Prentice-Hall, Upper Saddle River 2001.

– 12 –