Transakce PA150 Principy operacnch systemu Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: podzim 2020 Pojem transakce 2 Jiz star Rmane ... transigo – prov´est 2 V IT: transakce (casto budeme uvadet pouze symbol T ){ logicka jednotka behu procesu (vlakna) ve ktere se zprstupnuj a prp. modi kuj datove polozky uchovavane v bazi(ch) dat, resp. posloupnost dlcch, samostatnych pozadavku klienta na server, 2 T zachovava jako celek dve zakladn vlastnosti: atomicita { cela se uspesne dokonc nebo nema zadny ucinek (nema ucinek pokud se nemuze uspesne dokoncit, napr. v prpade vypadku nektereho ze serveru (zdroju) podlejcch se na transakci) izolovanost { neovlivnuje se operacemi soubezne realizovanymi transakcemi Jan Staudek, FI MU Brno | PA150 { Transakce 1 Pojem transakce 2 Prklad transakce { objednavka a dodan zboz Zpracovan objednavky i dodavky se muze tykat napr. skladovych, fakturacnch a dodavatelskych zaznamu Zpracovan zaznamu mus byt synchronizovane, napr. nesm se dodat zboz zakaznkovi, aniz by probehla fakturace 2 Transakci vymezuj hranicn de nicn konstrukty zacatek transakce (transaction begin, t begin...) konec transakce (transaction end, t end, ...) (explicitne uvadme pouze v prpade nejednoznacnosti vyjadren) 2 Transakce se sklada ze vsech operac uzavrenych mezi zacatkem transakce a koncem transakce 2 Transakce je jednoznacne identi kovatelna Jan Staudek, FI MU Brno | PA150 { Transakce 2 Konceptualn schema proveden transakce Jan Staudek, FI MU Brno | PA150 { Transakce 3 Modelova transakce casto pouzvana pri vykladu 2 Prevod castky mezi ucty 2 Imperativn charakter vyjadren transakce: read (A); % A, B – DB promˇenn´e ˇcten´e/zapisovan´e do/z RAM A:=A{50; % A, B – kopie DB promˇenn´ych A, B v RAM write (A); read (B); B:=B+50; write (B); 2 Objektove vyjadren teze transakce: a.withdraw (50); % a, b objekty v datab´azi b.deposit (50); Jan Staudek, FI MU Brno | PA150 { Transakce 4 Pojem transakce a transakcnho zpracovan 2 Cl transakcnho zpracovan Objekty spravovane serverem jsou v konzistentnm stavu i v prpadech, kdy jsou tyto zprstupnovane vce transakcemi soubezne, a to i v prpadech obnovy po vypadku vypocetnho systemu Konzistentn stav { stav vyhovujc jistym integritnm omezenm Integrita { celistvost, soudrznost, neporusenost, ... 2 Server spravovane objekty udrzuje jako obnovitelne objekty Pro uchovavan informac o objektech, jejichz kopie server docasne uchovava v RAM, pouzva server permanentn pamet' (disk) Tyto informace server pouzva pri obnove po vypadku serveru Jan Staudek, FI MU Brno | PA150 { Transakce 5 Pojem transakce a transakcnho zpracovan 2 Transakci klient speci kuje jako mnozinu operac na objektech, kterou mus servery spravujc tyto objekty provadet jako logicky nedelitelnou jednotku zpracovan 2 Operace jedne transakce si nemohou zprstupnovat dlc (mezi)vysledky jinych transakc { transakce jsou atomicke jednotky 2 Rzen transakcnho zpracovan mus zarucit, ze bud'to se provede cela transakce a jej vysledek se trvale uchova v permanentn pameti nebo v prpade vypadku se ucinky nedokoncene transakce plne eliminuj Jan Staudek, FI MU Brno | PA150 { Transakce 6 Pojem transakce (T ) a transakcnho zpracovan 2 Transakcn zpracovan budeme studovat nejprve na prpadu transakc provadenych na v nedistribuovanem systemu (multitasking, prp. podporovany multiprocesorem), na prpadu distribuovanych transakc resenych v DS Jan Staudek, FI MU Brno | PA150 { Transakce 7 Prklad prostred transakcnho zpracovan Jan Staudek, FI MU Brno | PA150 { Transakce 8 Podpora transakcnho zpracovan { TPM 2 Transaction Processing Monitor, TPM { typicky cast middleware Vrstva sluzeb mezi aplikacn vrstvou a vrstvou ,,OS & st'ovan" { Typicky prklad prostred pro transakcn zpracovan { CORBA { TPM muze byt soucast systemu rzen baze dat 2 TPM zajist'uje, ze se kazda transakce ukonc a databazi zanecha v neporusenem (konzistentnm) stavu, 2 TPM podporuje provaden operac vymezujcch transakci t begin { start transakce, generovan id transakce t end { ukoncen transakce { radne, s vysledkem t commit, transakce je provedena, nebo { nasilne, po poruse/vypadku, na zadost, ..., s vysledkem t abort, transakce je zrusena, prp. zkrachovala nasilne ukoncen (zrusen, krach) transakce vyvola v TPM operaci rollback, tj. vracen transakcnho prostred do puvodnho stavu, ve kterem bylo pri startu transakce Jan Staudek, FI MU Brno | PA150 { Transakce 9 Podpora transakcnho zpracovan { TPM 2 Dals problemy, ktere musme vesmes pomoc TPM resit read (A); A:=A{50; write (A); read (B); B:=B+50; write (B); dopady poruch { vypadku hardware, systemu, ... a obnov po poruse { read (A); A:=A{50; write (A); V YPADEK { OBNOVA, resena opakovanym spustenm aplikace vyvolavajc transakci { read (A); A:=A{50; write (A); read (B); B:=B+50; write (B); dekrement A se opakuje, aniz by se navratila inicialn hodnota A Jan Staudek, FI MU Brno | PA150 { Transakce 10 Podpora transakcnho zpracovan { TPM dopady soubeznosti { provaden vce transakc soubezne (radky = cas) T1: T2: read (A); A:=A{50; read (A); % T2 cte z disku puvodn hodnotu A write (A); A:=A{100; read (B); write (A); % T2 eliminuje ucinek T1 na A B:=B+50; read (B); % T2 cte z disku puvodn hodnotu B write (B); B:=B+100; write (B); % T2 eliminuje ucinek T1 na B; Jan Staudek, FI MU Brno | PA150 { Transakce 11 Pojem transakce a transakcnho zpracovan 2 Clem podpory transakcnho zpracovan je zajistit, aby vsechny objekty, ktere jisty server (DB) ovlada (spravuje, rd), permanentne zustavaly v konzistentnm stavu, a to i v prpadech: vypadku serveru { jisty server nepokracuje v behu a ostatn procesy nemus byt schopne tento stav zjistit vypadku dorucen zprav { zprava vlozena do vystupnho bu eru nen dorucena do vstupnho bu eru soubezneho provaden vce transakc manipulujcch se sdlenymi daty 2 Histroricky puvod transakc { DBMS Data Base Management System, system rzen baze dat transakc se rozumelo proveden programu, ktery pristupuje do baze dat Jan Staudek, FI MU Brno | PA150 { Transakce 12 Pojem transakce a transakcnho zpracovan 2 Transakce v z pohledu serveru spravujcho zpracovavane objekty: identi kovatelne posloupnosti klientskych pozadavku na operace s objekty 2 Klientsky pohled na transakci: posloupnost operac formovanych de nic jejho pocatku a konce do "jednoho kroku\ transformujcho stav serveru { z jednoho konzistentnho stavu (pred spustenm transakce) { do jineho konzistentnho stavu (po dokoncen transakce) Jan Staudek, FI MU Brno | PA150 { Transakce 13 Pozadovane vlastnosti transakc { A, Atomicity 2 Bud' se provedou vsechny operace transakce nebo zadna z nich, pozadovana vlastnost { All or nothing 2 Transakce bud' skonc uspesne, pak ucinky vsech jejch operac jsou trvale zaznamenane v relevantnch objektech v permanentn pameti, nebo selze nebo je umyslne zrusena, pak nevykaze zadny ucinek 2 proveden A:=A{50; bez proveden B:=B+50; zpusob nekonzistentnost baze dat, dojde ke ,,ztrate"penez 2 TPM mus zajistit, aby castecne provedene transakce (tj. pri behu padnou nebo jsou zamerne zrusene) neovlivnily stav baze dat Jan Staudek, FI MU Brno | PA150 { Transakce 14 Pozadovane vlastnosti transakc { A, Atomicity 2 s kolekc operac transakce se mus zachazet jako s jednou jedinou operacn jednotkou | vzdy, za vsech podmnek 2 zajisten atomicity transakce kritickou sekc (serializac celych transakc) je nedostacujc resen, pozaduje se zajisten atomicity i v prpade poruch (vypadku) 2 Informace o modi kaci DB dat je zapisovana do souboru na disku { denk, log 2 Jestlize se transakce nedokonc, v DBS se z denku obnov puvodn hodnoty DB dat 2 Po uspesnem dokoncen transakce jsou vsechny jej ucinky trvale zapamatovane v permanentn pameti, tj. ulozene na disku ci na jinem, energeticky nezavislem mediu. Jan Staudek, FI MU Brno | PA150 { Transakce 15 Pozadovane vlastnosti transakc { C, Consistency 2 proveden transakce neporus konzistenci baze dat, vlastnost C, Consistency konzistentnost lze kontrolovat proverovanm plnen vhodnych pozadavku na konzistenci, napr.: { implicitn integritn omezen { A+B=const validn proveden T mus zachovat konzistenci baze dat { nove spoustena transakce vzdy mus videt konzistentn bazi dat chybne provedena T by mohla zpusobit nekonzistentnost baze dat plat: behem provaden T muze byt konzistence docasne narusena read (A); A:=A{50; write (A); nekonzistentn stav { A+B=const read (B); B:=B+50; write (B); konzistentn stav { A+B=const uz i izolovane proveden individualn transakce nesm narusit konzistenci baze dat idea zajist'ovan konzistentnosti: { odpovednost lez na programatorovi, ktery transakci navrhuje/koduje Jan Staudek, FI MU Brno | PA150 { Transakce 16 Pozadovane vlastnosti transakc { I, Isolation T1: read (A); A:=A{50; write (A); prerusen behu T1 T2: read (A); read (B); print (A+B); obnova behu T1: read (B); B:=B+50; write (B); 2 soubezne provaden vce transakc nesm ovlivnovat vysledek jednotlivych transakc, vlastnost I, Isolation v uvedenem prkladu vid T2 nekonzistentn bazi dat, zatmco proveden T2 po ,,write (B);"v T1 by bylo validn system (TPM) mus zajistit pro kazdy par soubezne resenych transakc Ti a Tj, aby se z hlediska kazde transakce soubeh jevil { jakoby Tj skoncila drve nez se spustila Ti { nebo jakoby se Tj spustila po dokoncen Ti trivialn/naivn idea zajist'ovan izolovanosti { plna serializace transakc je mnohdy neefektivn resen Jan Staudek, FI MU Brno | PA150 { Transakce 17 Pozadovane vlastnosti transakc { I, Isolation soubezne provaden vce transakc nesm ovlivnovat vysledek jednotlivych transakc Soubezne provaden transakc zanecha system ve stavu, ktery je rovnocenny stavu systemu v prpade, ze by se tyto transakce provadely jedna po druhe, sekvencne v nekterem z moznych porad Zajisten izolace je odpovednost funkcn slozky DBS prpadne monitoru transkacnho zpracovan, TPM, nazyvane system rzen soubeznosti, Concurrency-Control System Jan Staudek, FI MU Brno | PA150 { Transakce 18 Pozadovane vlastnosti transakc { D, Durability 2 vysledky transakce jsou stale, trvale, vlastnost D, Durability jakmile se T uspesne dokonc, zmeny provedene touto T jsou trvale, a to i prpade poruch/vypadku systemu idea zajist'ovan trvalosti: informace o zmenach provedenych T v DB se pred dokoncenm T vypisuj na disk a pri obnove systemu po poruse se tyto informace pouzij pro rekonstrukci zmen kdyz serverovy proces (neocekavane) padne dky poruse hardware nebo software, zmeny provedene vsemi uspesne ukoncenymi (provedenymi) transakcemi mus byt pamatovane v permanentn pameti, aby obnoveny (novy) serverovy proces mohl objekty obnovit, aby se vyhovelo podmnce All or nothing (atomicity) Jakmile se transakce uspesne provede, vsechny transakc provedene modi kace v DB pretrvavaj, a to i v prpade, ze system po dokoncen transakce selze. Jan Staudek, FI MU Brno | PA150 { Transakce 19 Pozadovane vlastnosti transakc { D, Durability Vypadek poctacoveho systemu muze zpusobit ztratu dat v hlavn pameti, ale data zapsana na disk se neztrat. Zajsten trvalosti ma na starosti funkcn cast DBS/TPM zvana spravce obnovy, Recovery Manager, zajist'ujc rovnez atomicitu Trvanlivost lze zarucit zajistenm { Modi kace provedene transakc byly zapsany na disk jeste pred ukoncenm transakce. { Informace o modi kacch provedenych transakc zapsana na disk je dostatecna k tomu, aby DBS pri restartovan systemu po poruse aktualizace zrekonstruoval Jan Staudek, FI MU Brno | PA150 { Transakce 20 Stavy transakce Jan Staudek, FI MU Brno | PA150 { Transakce 21 Genericka de nice transakce pro ucely studia 2 Transakci (T) charakterizujeme pouze posloupnost operac read a/nebo write pracujcch s objekty zpracovavanymi transakc koncc operac t end s vysledkem t commit nebo t abort aplikacn manipulace s objekty v transakci abstrahujeme implicitne predpokladame validn transakce zachovavajc konzistenci Jan Staudek, FI MU Brno | PA150 { Transakce 22 Hotova transakce, partially commited 2 hotovou (partially committed) transakci, tj. transakci hotovou se vsemi aplikacnmi operacemi, koordinator transakce konc pri aktivaci t end s vysledkem t commit hotova T v tom prpade prechaz do stavu provedena (commited) Jan Staudek, FI MU Brno | PA150 { Transakce 23 Zkrachovala transakce, failed 2 na krach, vypadek (z duvodu logicke chyby, poruchy hardware systemu apod.) reaguje TPM prevodem aktivn nebo hotove transakce T do stavu zkrachovala T prechodem do stavu zkrachovala konc T svoji cinnost predcasne zkrachovalou T koordinator konc pri aktivaci t end s vysledkem t abort neuspesne (predcasne) koncc T (zkrachovala) prechaz po vysledku t abort do stavu zrusena (aborted) pokud ke zrusen doslo z duvodu intern logicke chyby aplikace, aplikace konc, zjevne mus byt preprogramovana zrusen T z duvodu vypadku vyvola operaci vracen (rollback), aby se zrusily veskere zmeny, ke kterym dky jejmu dosavadnmu proveden doslo obnovu puvodnho stavu TPM dosahne provedenm operace undo ucinek provedene T zrusit/obnovit/vratit (provedenm t abort) nelze Jan Staudek, FI MU Brno | PA150 { Transakce 24 Zrusena transakce, aborted 2 neukoncila uspesne sve proveden 2 nesm mt zadny vliv na stav databaze zmeny v databazi provedene zrusenou transakc mus byt zruseny, provedenm undo zapisu do DB se transakce vrat zpet, roll-back za zrusen odpovda Recovery Manager, ktery udrzuje denk, log. Kazda modi kace provadena transakc je nejprve zaznamenana do denku. V zaznamu denku se uvede { identi kator transakce, { hodnota datove polozky pred modi kac a { hodnota po modi kaci. Pote se modi kuje promenna v DB Udrzovan denku umoznuje provest v prpade obnovy po poruse behem provaden transakc { jak redo k zajisten atomicity a trvalosti { tak i undo k zajisten atomicity Jan Staudek, FI MU Brno | PA150 { Transakce 25 Zrusena transakce, aborted. 2 Problem pozorovatelnych externch zapisu vypisy na obrazovku, zaslan e-mail, ... ciste resen { zapisy provadet jen ve stavu provedena transakce pro dlouhodobe transakce toto resen nemus vyhovovat 2 Problem nutnosti likvidace provedenych transakc lze provest pouze adekvatnmi kompenzacnmi transakcemi kompenzacn transakce nemuze resit DBS, TMP, ... mus byt reseny na aplikacn urovni, nemus to byt trivialn Jan Staudek, FI MU Brno | PA150 { Transakce 26 Izolovanost soubeznych transakc 2 Duvody k soubeznemu resen transakc vyss propustnost a ucinnejs vyuzit zdroju (mene prostoju CPU, disku, ...) snzen doby cekan proti seriovemu provaden transakc 2 analogie multiprogramovan na urovni OS 2 ne vsechna prokladan behu transakc jsou validn, DBS/TPM mus koordinovat prokladan behu soubeznych transakc tak, aby se zabranilo narusen konzistenci databaze. 2 Cin tak pomoc mechanismu rzen soubeznosti { spravou soubeznosti Jan Staudek, FI MU Brno | PA150 { Transakce 27 Podpora transakcnho zpracovan 2 Transakci vytvar a rd jej ukoncen koordinator transakce, komponenta TPM s rozhranm TPM { aplikace 2 Rozhran TPM { aplikace pouzva aplikacn klient openTransaction() → trans; { TPM startuje transakci a vrac jedinecny id transakce, trans; { strukturaln notace pouzvana v obrazcch { t begin closeTransaction(trans) → (commit, abort); TPM konc transakci a vrac zpusob ukoncen: { pokud byla operacn cast transakce hotova , transakce se stane provedena, funkce vrac commit { pokud transakce zkrachovala, stane se zrusena, funkce vrac abort, { strukturaln notace pouzvana v obrazcch, { t end abortTransaction(trans); explicitn zadost klienta o nasilne ukoncen (zrusen) transakce Jan Staudek, FI MU Brno | PA150 { Transakce 28 Podpora transakcnho zpracovan 2 Pozadavky klienta na server zadavane v ramci transakce mus byt identi kovane id transakce trans id transakce trans muze byt jednm z parametru pozadavku, napr. X.deposit(trans, amount) id transakce trans muze byt implicitne dodavane ke vsem pozadavkum prslusneho klienta mezi openTransaction a closeTransaction nebo abortTransaction { takto to res napr. middleware CORBA V prkladech id transakce trans explicitne neuvadme. Jan Staudek, FI MU Brno | PA150 { Transakce 29 Podpora transakcnho zpracovan 2 Transakci muze nasilne ukoncit i server, pak mus chybovy vysledek sdelit klientovi 2 Co dela server, kdyz neocekavane dojde k vypadku ? vypadne server a jeho cinnost je posleze obnovena novy proces serveru mus nasilne ukoncit vsechny transakce, ktere nejsou provedene a prostred vratit do stavu platneho po poslednch provedenych transakcch pouzije obnovovac operaci (recovery, redo), kterou obnov hodnoty objektu vytvorene provedenymi transakcemi vypadne klient behem resen jm spustene transakce, server nastavuje pro kazdou transakci expiracn dobu a pokud relevantn klient do n neprovede volan t end, ukonc server transakci nasilne Jan Staudek, FI MU Brno | PA150 { Transakce 30 Podpora transakcnho zpracovan 2 Co dela klient, kdyz vypadne server ? bud'to se klient dozv o vypadku serveru uplynutm casoveho limitu, transakci neukoncuje a povazuje ji za zkrachovalou, zkrachovale transakce se na urovni serveru automaticky likviduj, (princip atomicity) nebo je server jeste v prubehu transakce obnoveny, pak transakce nen validn a klient o tom mus byt informovany napr. pri zadan prst operace transakce (vyjimkou, ...) v obou prpadech klient formuluje plan dokoncen nebo zanechan aplikace, jejz soucast byla postizena transakce (formulaci muze konzultovat s lidskym uzivatelem) Jan Staudek, FI MU Brno | PA150 { Transakce 31 Soubezne resen transakc, problem dosazen izolovanosti 2 prnos soubezneho resen transakc lepe se vyuzva vykon procesoru a disku a tm se dosahuje vyss propustnosti transakc { v dobe kdy jedna T ceka na konec IO operace a nepouzva procesor, vyuzva procesor jina T 2 mechanismy podporovane v TPM pro dosazen izolovanosti jednotlivych soubezne provadenych transakc nazyvame schemata rzen soubeznosti transakc (Concurrency control schemes) zajist'uj rzen interakc mezi soubeznymi T, jejich clem je zabranit narusen konzistentnosti baze dat pri soubeznem resen vce T soubezne proveden vce T mus byt ekvivalentn jejich seriovemu (postupnemu) proveden v nekterem ze vsech moznych porad tato vlastnost resen soubehu transakc se nazyva serializovatelnost (serializability) Jan Staudek, FI MU Brno | PA150 { Transakce 32 Soubezne transakce, serializovatelnost, seriovy plan 2 Hledame nastroj pro zachovan konzistence baze dat pri soubeznem resen transakcch 2 Necht' kazda T jiste skupiny transakc zachovava izolovanym provedenm konzistenci baze dat ( T je validn ) 2 Pak kazde postupne (seriove) proveden techto transakc rovnez zachovava konzistenci baze dat 2 Postupne (seriove) resen vce T lze zajistit jejich implementac jako kriticke sekce toto muze byt mnohdy prlis restriktivn, tudz neefektivn 2 Efektivnejs provaden transakc se dosahne zajistenm serializovatelnosti soubehu transakc pomoc sluzeb TPM rzenych algoritmy (schematy) rzen soubeznosti transakc Jan Staudek, FI MU Brno | PA150 { Transakce 33 Soubezne transakce, serializovatelnost, seriovy plan 2 Schemata rzen soubeznosti transakc implementuj jisty plan 2 Plan vymezuje mozna porad provaden instrukc transakc { konkretne vymezuje, ktere (nekon iktn) operace v soubezne resenych T lze provadet v case prekryvane Kdy jsou operace v soubeznych transakcch nekon iktn ? Pokud operuj se stejnou promennou pouze operacemi read, nebo pokud operuj s ruznymi promennymi 2 Plan je seriovy plan, pokud se instrukce, nalezejc jedne transakci, v nem objevuj jako kontinualn bloky, tj. jsou provedeny neprerusovane pro N transakc existuje N! seriovych planu vsechny seriove plany jsou validn, protoze predpokladame, ze vsechny podle nich realizovane transakce jsou validn a jsou provadene bez prerusen Jan Staudek, FI MU Brno | PA150 { Transakce 34 Soubezne transakce, serializovatelnost, seriovy plan 2 Plan je neseriovy plan pokud reprezentuje provaden transakc, ktera se v case se prekryvaj (multiprocesing) prp. se po castech prokladaj (multitasking) Pocet ruznych seriovych planu pro n (sekvencne provadenych) transakc je n!. Pocty soubezne resenych transakc mohou byt stovky, tisce, ... pro ilustraci { 100! = 9.332621544 × 10157 , doba existence vesmru se odhaduje na cca 13 × 109 let Vzhledem ke vsem moznym zpusobum prokladan operac soubezne resenych transakc, pocet vsech moznych neseriovych planu je MNOHEM vets nez n! Jan Staudek, FI MU Brno | PA150 { Transakce 35 Soubezne transakce, serializovatelnost, seriovy plan 2 Vysledek proveden neserioveho planu { nemus nutne byt nespravny { je spravny, pokud se jedna o tzv. serializovatelny plan 2 Plan jiste skupiny T je serializovatelny, pokud je ekvivalentn nekteremu seriovemu planu proveden teto skupiny T 2 Na bazi hledan serializovatelnosti (Serializability) transakc hledame serializovatelny plan (tj. plan, ktery nen nutne seriovy), ktery speci kuje jiste casove porad provaden instrukc soubeznych T tm, ze urcuje porad provaden vsech instrukc vsech T resenych soubezne, zachovava porad provaden instrukc, ve kterem se instrukce vyskytuj v jednotlivych T a zajist'uje, aby vysledek prokladanych proveden transakc byl ekvivalentn jejich nekteremu seriovemu proveden Jan Staudek, FI MU Brno | PA150 { Transakce 36 Kon iktn operace, kon iktove serializovatelny plan 2 Z hlediska dosazen serializovatelnosti hraj roli tzv. kon iktn operace Mejme plan S resc transakce Ti a Tj a operace Oi a Oj v transakcch Ti a Tj Operace Oi a Oj jsou kon iktn, pokud pristupuj ke stejne datove polozce a alespon jednou operac je operace write 2 Nejsou-li operace Oi a Oj kon iktn, pak plany S a S, ktere se lis pouze casovym poradm proveden Oi a Oj, jsou ekvivalentn 2 idea zajisten ekvivalentnosti planu { kon iktova serializace Kon iktn operace na vsech zprstupnovanych objektech v soubezne resenych transakcch podle serializovatelneho planu se mus provadet v porad shodnem s poradm techto operac v nekterem ze seriovych planu proveden techto transakc Jan Staudek, FI MU Brno | PA150 { Transakce 37 Kon iktn operace, kon iktove serializovatelny plan 2 mezi operacemi read a write mohou transakce provadet nad lokalnmi promennymi transakce (kopiemi DB hodnot) libovolne operace v dale uvadenych zjednodusenych planech vesmes ignorujeme vsechny instrukce jine nez read a write hodnot pamatovanych v bazi dat (datovych polozek), uvadme pouze instrukce read a write 2 Pokud lze z neserioveho planu S vytvorit ekvivalentn seriovy plan S pouhou zmenou porad proveden nekon iktnch operac, pak neseriovy plan S je kon iktove serializovatelny 2 Transakcn monitor mus pripustit soubezne provaden transakc pouze podle kon iktove serializovatelnych planu Jan Staudek, FI MU Brno | PA150 { Transakce 38 Pravidla urcujc kon iktnost operac Jan Staudek, FI MU Brno | PA150 { Transakce 39 Prklady seriovych planu P1: < T1 ; T2 > a P2: < T2 ; T1 > T1 prenas 50 Kc z uctu A na ucet B T2 prenas 10% hodnoty z uctu A na ucet B pozadavek konzistence: A+B=konst Jan Staudek, FI MU Brno | PA150 { Transakce 40 Prklad planu, ktere nejsou seriove plan P3 nen seriovy, je serializovatelny (ekvivalentn planu P1) plan P4 nen seriovy a nezajist'uje platnost omezen A+B=konst spravce soubeznosti nesm realizaci takoveho planu povolit Jan Staudek, FI MU Brno | PA150 { Transakce 41 Prklad planu, ktere nejsou seriove 2 plan P5 je neseriovy a nen kon iktove serializovatelny, spravce soubeznosti nesm realizaci takoveho planu povolit transakce T3 a T4 mus byt reseny seriove, < T 3, T 4 > nebo < T 4, T 3 >. Jan Staudek, FI MU Brno | PA150 { Transakce 42 Problemy soubeznosti transakc 2 Seriove proveden transakc T a U, plan 1 Inicialn stavy uctu a, b a c necht' jsou 100, 200, 300 $ integritn omezen a+b+c=const Jan Staudek, FI MU Brno | PA150 { Transakce 43 Problemy soubeznosti transakc 2 Seriove proveden transakc T a U, plan 2 Inicialn stavy uctu a, b a c necht' jsou 100, 200, 300 $ integritn omezen a+b+c=const Jan Staudek, FI MU Brno | PA150 { Transakce 44 Problemy soubeznosti transakc 2 Problem ztracene korekce (korekce v T prepisuje korekci v U) Inicialn stavy uctu a, b a c necht' jsou 100, 200, 300 $ a+b+c=80+220+280=580, nekonzistence Jan Staudek, FI MU Brno | PA150 { Transakce 45 Problemy soubeznosti transakc 2 Jine (validn) soubezne proveden transakc T a U, ekvivalentn jejich seriovemu proveden T, U Jan Staudek, FI MU Brno | PA150 { Transakce 46 Problemy soubeznosti transakc 2 Problem zskan nekonzistentnho stavu (v transakci W) Inicialn stavy uctu A, B necht' jsou kazdy 200 $ soucet vysek uctu A a B je ale 400 $, nikoli 300 $ Jan Staudek, FI MU Brno | PA150 { Transakce 47 Problemy soubeznosti transakc 2 Seriove proveden proveden transakc V a W je validn Jan Staudek, FI MU Brno | PA150 { Transakce 48 Testovan serializovatelnosti 2 mejme plan mnoziny transakc T1, T2, T3,...Tn 2 tento plan je serializovatelny pokud urcuje seriove ekvivalentn prokladan operac transakc, ve kterem je jejich kombinovany ucinek shodny s kombinovanym ucinkem nektereho jejich serioveho proveden 2 Shodny ucinek ≡ ctec operace vrac shodne hodnoty a nalne jsou vysledne hodnoty modi kovanych objektu shodne 2 Nutnou a postacujc podmnkou seriove ekvivalentnho prokladan proveden transakc je, aby se vsechny pary kon iktnch operac v techto transakcch provedly na vsech zprstupnovanych objektech ve stejnem porad Jan Staudek, FI MU Brno | PA150 { Transakce 49 Testovan serializovatelnosti 2 vypracujme precendencn graf uzly { transakce hrana vede z Ti do Tj, jestlize jsou tyto dve transakce v kon iktu a Ti zprstupnila datovou polozku (kvuli nz vznika kon ikt) drve hranu pojmenujeme jmenem relevantn datove polozky 2 plan je kon iktove serializovatelny pokud je jeho precendencn graf acyklicky klasicky algoritmus detekce cyklu v grafu ma slozitost n2 , kde n je pocet uzlu 2 je-li precedencn graf acyklicky, serializovatelnost lze ilustrovat topologickym trdenm grafu urcen linearnho usporadan, ktere je konzistentn s castecnym usporadanm precendencnho grafu Jan Staudek, FI MU Brno | PA150 { Transakce 50 Topologicke trden 2 acyklicky graf a jeho dve mozna linearn usporadan Jan Staudek, FI MU Brno | PA150 { Transakce 51 Precendecn grafy planu P1, P2 a P4 Jan Staudek, FI MU Brno | PA150 { Transakce 52 Prklad serializovatelneho planu mozna serializace: T5 → T1 → T3 → T2 → T4 jina mozna serializace: T1 → T2 → T3 → T4 → T5 Jan Staudek, FI MU Brno | PA150 { Transakce 53 Vizualn vs. kon iktova ekvivalence dva plany mohou poskytovat stejny vysledek, ale nemus byt kon iktove ekvivalentn vizualn ekvivalence planu se res obtzne, jde o NP-uplny problem, v praxi se vesmes aplikuje kon iktova ekvivalence Jan Staudek, FI MU Brno | PA150 { Transakce 54 Obnova po poruse (vypadku), obnovitelny plan 2 Studujeme nyn vliv poruch (vypadku) na soubezne provaden transakc 2 Hledame omezen vymezujc ze serializovatelnych planu tzv. obnovitelne plany 2 Obnovitelny plan respektuje omezen zajist'ujc pri soubezne resenych transakcch zachovan obnovitelnosti (Recoverability) baze dat po poruse (vypadku) jestlize Ti z jakehokoliv duvodu zkrachuje, je nutne pro zachovan vlastnosti atomicity pri jejm zrusen eliminovat (undo) efekty zpusobene jejm provadenm do doby nez zkrachovala to stejne plat pro kazdou Tj, ktera je zavisla na Ti, tj. ktera cte data modi kovana v prubehu Ti do doby jejich cten v Tj Jan Staudek, FI MU Brno | PA150 { Transakce 55 Problem obnovitelnosti planu, neferove cten, dirty read 2 mejme soubezne resene transakce T1: read(Q), write(Q), read(P); a T2: read(Q) 2 necht' TPM umozn hotovou transakci T2 prohlasit za provedenou drve nez je prohlasena za provedenou T1 Jan Staudek, FI MU Brno | PA150 { Transakce 56 Problem obnovitelnosti planu, neferove cten, dirty read 2 Neferove cten zpusobuje interakce mezi ctenm v jedne transakci a drvejsm zapisem do stejneho objektu v jine transakci 2 nasledujc plan v tom prpade nen obnovitelny z duvodu T1: T2: tzv. neferoveho cten (dirty read) read(Q) write(Q) read(Q) read(P) t commit t abort nezpusob zkrachovan i T2 tj. T1 krachuje po prohlasen T2 za provedenou a rus se (t abort) pro zachovan atomicity se mus rovnez zrusit T2, ponevadz cetla data vytvorena T1, coz uz ale nelze provest, T2 je jiz provedena a provedenou transakci eliminovat (undo) nelze Jan Staudek, FI MU Brno | PA150 { Transakce 57 Problem obnovitelnosti planu, predcasny zapis Mnohe DBS implementuj rusen transakce obnovou na hodnoty objektu pred vsemi jejmi zapisy (before image) Jestlize se provede T a pote se zrus U, bude hodnota a = 105, OK jestlize se zrus T po proveden U, bude hodnota a = 100 a ne 110 jestlize se zrus T po te i U, bude hodnota a = 105 a ne 100 Aby vysledky obnovy byly spravne, mus byt zapisy v transakcch zpozdene do doby proveden nebo zrusen drvejsch transakc, ktere modi kovaly stejny objekt Jan Staudek, FI MU Brno | PA150 { Transakce 58 Obnovitelny plan 2 v systemu se soubezne resenymi transakcemi se obvykle (prirozene) pozaduje, aby kazdy plan byl serializovatelny A obnovitelny 2 plan je obnovitelny, pokud plat: pro kazdy par transakc Ti a Tj, ve kterem Tj cte datovou polozku drve zapsanou Ti, stav t commit ukoncujc Ti nastane pred t commit ukoncujcm Tj Tj lze prohlasit za provedenou po prohlasen Ti za provedenou 2 nasledujc plan uz obnovitelny je Ti: Tj: read(Q) write(Q) read(Q) read(P) t abort zpusob zkrachovan i Tj, ta nen dosud provedena Jan Staudek, FI MU Brno | PA150 { Transakce 59 Kaskadn vracen 2 Cascading Rollbacks 2 zkrachovan jedne T muze zpusobit navrat vce transakc 2 v nasledujcm planu zkrachovan T1 vyvola i navraty T2 a T3 necht' zadna T dosud neprovedla t commit, plan je tudz obnovitelny 2 T1: T2: T3: read(A) read(B) write(A) read(A) write(A) read(A) t abort 2 kasdadn vracen muze predstavovat vysokou zatez Jan Staudek, FI MU Brno | PA150 { Transakce 60 Plany bez kaskadnch vracen 2 ke kaskadnmu vracen nemuze dojt, pokud plat: pro kazdy par transakc Ti a Tj, ve kterem Tj cte datovou polozku drve zapsanou Ti, se t commit ukoncujc Ti se provede pred relevantn operac read v Tj 2 kazdy plan bez kaskadnho vracen je rovnez obnovitelny 2 je vysoce zadouc se omezovat pouze na plany bez kaskadnho vracen 2 negativn dusledek prosazovan planu bez kaskadnch vracen { omezen soubeznosti Jan Staudek, FI MU Brno | PA150 { Transakce 61 Obnovitelny plan { striktn (prsne) provaden transakc 2 transakce zpozd'uj cten a zapisy tak, aby zabranily neferovym ctenm a predcasnym zapisum 2 pri striktnm (prsnym) provadenm transakc se cten a zapisy jisteho objektu v transakci zpozd'uj do doby proveden ci zrusen drvejsch transakc, ktere dany objekt modi kovaly 2 striktn (prsne) provaden transakc podporuje dosazen pozadovane vlastnosti obnovitelnosti, omezuje vsak stupen soubeznosti Jan Staudek, FI MU Brno | PA150 { Transakce 62 Rzen soubeznosti 2 TPM mus poskytnout mechanismus, ktery zajist, aby se pri soubehu transakc realizovaly plany kon iktove serializovatelne a obnovitelne, lepe vsak obnovitelne bez kaskadnch vracen 2 omezen na seriove plany jsou zbytecne restriktivn 2 clem protokolu pro rzen soubeznosti je zajisten, aby plany byly kon iktove serializovatelne a obnovitelne bez kaskadnho vracen protokoly obvykle nevychazej z analyzy precendencnch grafu protokoly obvykle prosazuj pravidla, ktera zajist vyhyban se neserializovatelnym planum protokoly se vzajemne lis svoj narocnost na vykon procesoru a mnozstvm soubeznosti, ktere dosahuj Jan Staudek, FI MU Brno | PA150 { Transakce 63 Rzen soubeznosti 2 Nutnou i postacujc podmnkou seriove ekvivalentnho prokladan proveden transakc je, aby se vsechny pary kon iktnch operac v techto transakcch provedly na vsech zprstupnovanych objektech ve stejnem porad 2 plan je obnovitelny, pokud plat: pro kazdy par transakc Ti a Tj, ve kterem Tj cte datovou polozku drve zapsanou Ti, stav t commit ukoncujc Ti nastane pred t commit ukoncujcm Tj Tj lze prohlasit za provedenou po prohlasen Ti za provedenou pri striktnm (prsnym) provadenm transakc se cten a zapisy jisteho objektu v transakci zpozd'uj do doby proveden ci zrusen drvejsch transakc, ktere dany objekt modi kovaly striktn (prsne) provaden transakc podporuje dosazen pozadovane vlastnosti obnovitelnosti, omezuje vsak stupen soubeznosti Jan Staudek, FI MU Brno | PA150 { Transakce 64 Metody zajist'ovan izolovanosti soubeznych transakc 2 Zamky { zajist'uj pridelen sdlene polozky transakci po dobu nutnou pro zajisten serializovatelnosti zamky jsou dvojho typu { sdlene, pripoustej nasobnost operac read s vyloucenm operac write do sdlene polozky { exkluzivn { zajist'uj vylucny prstup transakce k polozce 2 Casova raztka kazda transakce ma jedinecne casove raztko dane dobou jejho vzniku pri vzniku kon iktu transakce pristupuj ke sdlenym promennym v porad casovych raztek pokud toto porad nelze zajistit (doslo by napr. ke v case zpetnemu zapisu hodnoty polozky) transakce zpusobujc kon ikt krachuje a restartuje se v pozdejsm case, s novym casovym raztkem Jan Staudek, FI MU Brno | PA150 { Transakce 65 Zamky, transakcn protokol na bazi zamykan nejcastejs forma implementace planovace transakc 2 zamek, lock zamek { blokovac prvek udrzovany ke kazde datove polozce zamky spravuje spravce zamku { proces/sluzba TPM zamek lze zamknout a odemknout (sluzby TPM) k datove polozce ma povolen prstup ta transakce, ktera zamkne jej zamek zamky jsou dvojho typu { sdleny pro read, exkluzitivn pro write a existuj pravidla, kdy lze ten ktery typ zamku zamknout transakce jsou pomoc zamykan a odemykan zamku synchronizovane tak, aby jejich ucinky na sdlena data byly ekvivalentn nekteremu jejich seriovemu zpracovan 2 casto pouzvana synonyma zamknut zamku, zskan zamku, vlastnen zamku, ... odemknut zamku, vracen zamku, uvolnen zamku, ... Jan Staudek, FI MU Brno | PA150 { Transakce 66 Zamky, transakcn protokol na bazi zamykan 2 transakcn protokol na bazi zamykan mnozina pravidel vymezujc chovan transakc pri zamykan a odemykan zamku omezuje mnozinu moznych planu na kon iktove serializovatelne plany zarucuje kon iktovou serializovatelnost, pokud vsechny plany, ktere determinuje, jsou kon iktove serializovatelne 2 Typy zamku, rezimy prstupu k datum Sdleny zamek { (rezim shared, lock − S) pokud Ti vlastn lock-S polozky Q, muze obsah polozky Q cst, ale nesm do polozky Q zapisovat Exkluzivitn zamek { (rezim exclusive, lock − X) pokud Ti vlastn lock-X polozky Q, je jedinou transakc, ktera muze obsah polozky Q cst a / nebo do polozky Q zapisovat Jan Staudek, FI MU Brno | PA150 { Transakce 67 Zamky, transakcn protokol na bazi zamykan 2 De facto se jedna o ulohu ctenari-psari zada-li Ti zajistit pomoc zskan zamku lock-X exkluzivn prstup k Q a jina transakce uz zskala jakykoliv zamek polozky Q, Ti mus cekat na uvolnen tohoto zamku zada-li Ti provest pomoc zskan zamku lock-S sdleny prstup ke Q a jina transakce uz zskala zamek lock-X polozky Q, Ti mus cekat na uvolnen tohoto zamku lock-X zada-li Ti provest pomoc zskan zamku lock-S sdleny prstup ke Q a zamek lock-S polozky Q uz zskala jina transakce, Ti zska zamek lock-S tez 2 Kdyz se transakce stane provedena ci zkrachovala, server (TPM) odemkne transakc explicitne neodemcene zamky Jan Staudek, FI MU Brno | PA150 { Transakce 68 Transakcn zamykac protokol 2 Zamykan polozek pouze na dobu individualnch prstupu k polozkam dat nezajist serializovatelnost soubehu transakc 2 Potrebujeme protokol rzen soubeznosti transakc povolujc kdy transakce muze datovou polozku zamknout a odemknout tak, aby se dosahlo serializovatelnosti soubehu transakc Jan Staudek, FI MU Brno | PA150 { Transakce 69 Transakcn zamykac protokol 2 Transakcn zamykac protokol omez pocet moznych planu na serializovatelne plany 2 Mnozina techto planu je podmnozinou vsech moznych planu 2 Nas zajmaj pouze ty transakcn zamykac protokoly, ktere povoluj pouze kon iktove serializovatelne plany, ktere jsou ekvivalentn nekteremu z jejich seriovych planu vzajemne se se lis pouze poradm proveden nekon iktnch operac plat, ze operace jsou kon iktn, pokud operuj se stejnou polozkou a alespon jedna z nich je write Jan Staudek, FI MU Brno | PA150 { Transakce 70 Dvoufazovy transakcn protokol na bazi zamykan 2 Two-Phase Locking Protocol, 2PLP 2 Jeden z protokolu, ktery zajist'uje kon iktovou serializovatelnost Pokud nen znama zadna dals informace o zpusobu zpracovan dat je 2PLP nutny a postacujc protokol pro zajisten kon iktove serializovatelnosti 2 Princip 2PLP { jakmile transakce odemkne nektery zamek, nesm uz zamknout zadny dals zamek 2 Transakce proto vydava zamykac a odemykac pozadavky ve dvou fazch, v zamykac (rustove) fazi a v odemykac (couvac) fazi Jan Staudek, FI MU Brno | PA150 { Transakce 71 Dvoufazovy transakcn protokol na bazi zamykan 2 rustova faze zskavan zamku, serializovan transakc podle pravidel: a) pokud objekt nen zamknuty, zamkne se a transakce pokracuje b) pokud je objekt uzamknuty kon iktnm zamkem jinou transakc, transakce ceka na jeho odemknut c) pokud je objekt uzamknuty nekon iktnm zamkem jinou transakc, objekt se sdl, transakce zska zamek a pokracuje d) pokud je objekt jiz zamknuty stejnou transakc, zamknut se uplatn a transakce pokracuje. (Pokud uplatnen bran kon iktn zamek, pouzije se pravidlo b) 2 couvac faze uvolnovan zamku { lze provadet POUZE PO poslednm zskan zamku 2 Uvaznut 2PLP neres { zamezen uvaznut lze dosahnout napr. vnucenm pevneho razen zprstupnovanych dat Jan Staudek, FI MU Brno | PA150 { Transakce 72 Protokol rzen soubehu transakc s casovymi raztky 2 Rzen soubeznosti transakc zalozene na jejich casovem razen TPM zaznamenava pro kazdy sdleny objekt dobu poslednho cten a zapisu pri kazde operaci s objektem na bazi casovych raztek transakc danych okamzikem jejich vzniku rozhoduje, zda { lze operaci provest bezprostredne, { lze operaci provest pozdeji (transakce bude cekat) nebo { se mus operace odmtnout (transakce krachuje, klient ji muze restartovat) pozadavek transakce na zapis je validn pouze kdyz objekt byl naposledy cteny nebo zapisovany drvejs transakc nebo nebyl dosud zprstupneny pozadavek transakce na cten je validn pouze kdyz objekt byl naposledy zapisovany drvejs transakc nebo nebyl dosud zprstupneny Jan Staudek, FI MU Brno | PA150 { Transakce 73 Protokol rzen soubehu transakc s casovymi raztky 2 Pri startu transakce Ti se Ti prideluje casove raztko, T Si T Si je jedinecne, v jednom okamziku dochaz k jedine udalosti T Si de nuje pozici transakce Ti na casove ose 2 T Si < T Sj { transakce Ti predchaz transakci Tj, je stars 2 T Si > T Sj { transakce Ti nasleduje po transakci Tj, je mlads 2 Pozadavky transakc se totalne rad podle prslusnych casovych raztek transakc pozadavek transakce na write objektu je validn pouze kdyz objekt byl naposled cteny / zapisovany drvejs (stars) transakc a nebo nebyl dosud zprstupneny vubec pozadavek transakce na read objektu je validn pouze kdyz objekt byl naposled zapisovany drvejs (stars) transakc a nebo nebyl dosud modi kovany Jan Staudek, FI MU Brno | PA150 { Transakce 74 Protokol rzen soubehu transakc s casovymi raztky Jan Staudek, FI MU Brno | PA150 { Transakce 75 Protokol rzen soubehu transakc s casovymi raztky Jan Staudek, FI MU Brno | PA150 { Transakce 76 Distribuovana transakce, koncept 2 Distribuovana transakce zahrnuje operace provadene ve vce serverech (uzlech DS ) formou dlcch subtransakc 2 Uzly DS mohou vzajemne komunikovat, obecne { kazdy s kazdym 2 Mus byt zachovan bazovy princip transakce { atomicita, A Bud'to se provedou vsechny operace urcene programovou jednotkou rdic transakci nebo se neprovede zadna z nich 2 Mus byt zachovany pochopitelne i ostatn vlastnosti transakc { CID 2 Subtransakce realizovane v ruznych uzlech DS proto na ukoncovan sve transakce kooperuj pomoc koordinacnch procesu realizovanych na urovni middleware (TPM) Jan Staudek, FI MU Brno | PA150 { Transakce 77 Distribuovana transakce, koncept 2 Pouzita technologie { model klient-server 2 Klient { aplikacn proces bezc v nekterem uzlu DS aktivuje realizaci transakce T zadost zaslanou na koordinatora teto transakce T (server bezc v nekterem uzlu DS), res program de nujc transakci spocvajc ve volan posloupnost operac rescch transakci (subtransakc) vesmes rozmstenych v ruznych uzlech DS napr. podle jimi spravovanych objektu apod. aktivuje krach nebo prohlasen hotove transakce T za provedenou zadost zaslanou na koordinatora jm spustene transakce T 2 Server { systemovy proces bezc v nekterem uzlu DS koordinator transakce T, je soucast TPM, middleware zajist'uje start a ukoncen distribuovane transakce s clem zajistit atomicitu transakce aktivovane klientem Jan Staudek, FI MU Brno | PA150 { Transakce 78 Distribuovana transakce, koncept 2 Prubehy operac subtransakc v jednotlivych uzlech DS rd spravci , funkcnosti na urovni TPM Subtransakce nalezejc transakci T jsou spoustene klientem, v uzlech DS jsou aktivovane dynamicky volanm metod z klienta spravci transakc { jsou procesy bezc v uzlech DS, jsou soucast TPM, middleware { rd validnost soubeznosti (sub)transakc { udrzuj denk pro ucel obnovy po vypadku { spolupracuj s koordinatorem transakce na rozhodnut zda se transakce prohlas za provedenou nebo zda krachuje algoritmy obnovy i rzen soubeznosti se mus respektovat distribuovane prostred Jan Staudek, FI MU Brno | PA150 { Transakce 79 Distribuovana transakce, koncept 2 Klient zahajujc transakci zasla pozadavek openTransaction (n.b. t begin) koordinatorovi transakc rdcmu chod zahajovane transakce, Ci (sluzba v TPM v urcenem uzlu i) 2 Koordinator transakc Ci klientovi vrac id transakce, T { jednoznacny identi kator transakce v DS (napr. IP adresa i + poradove cslo transakce v i) a prebra roli koordinatora transakce T, ktery openTransaction pro transakci T provede 2 Proces klienta a procesy, resc pozadavky klienta jako casti distribuovane transakce, mus byt schopn s koordinatorem transakce komunikovat, obv. via RPC, aby mohly koordinovat svoje akce pri prechodu transakce do stavu provedena (commit) nebo zrusena (abort), Jan Staudek, FI MU Brno | PA150 { Transakce 80 Distribuovana transakce, koncept 2 Koordinator transakce T registruje existenci transakce T a posleze i koordinuje jej ukoncen (commit / abort) 2 Uzly zucastnene na resen transakce T tvor tzv. ,,kohortu T", nazyvame je participujc uzly na transakci T 2 casti transakce realizovane v participujcch uzlech, subtransakce, se obvykle aktivuj volanm metod klientem 2 v participujcm uzlu transakce T se zrizuje objekt participant, ktery je odpovedny za sledovan stavu obnovitelnych objektu v danem serveru zprstupnovanych transakc T a kooperuje s koordinatorem pri ukoncovan transakce T 2 participanti se registruj u koordinatoru svych transakc operac join Jan Staudek, FI MU Brno | PA150 { Transakce 81 Distribuovana transakce, koncept 2 koordinator T si udrzuje seznam participantu transakce T 2 participanti (subtransakce) si relevantn sluzbou svych TPM udrzuj referenci na sveho koordinatora a komunikuj s nm pri ukoncovan transakce, commit / abort 2 ucast participanta na transakci: { registrace u koordinatora + { sprava objektu zprstupnovanych subtransakc + { kooperace s koordinatorem pri ukoncovan transakce 2 bud'to vsichni participanti sve subtransakce provedou (a potvrd) { transakce se stane provedenou, commit 2 nebo vsichni participanti zrus akce provedene v ramci subtransakc { transakce zkrachuje (abort) Jan Staudek, FI MU Brno | PA150 { Transakce 82 Distribuovana transakce, koncept 2 Koordinator transakce { registruje spusten transakce, { registruje participanty, prp. sam del transakci na subtransakce a { res, koordinuje akce pri ukoncovan transakce 2 Spravce transakce v uzlu kohorty, participant { udrzuje denk pro obnovu transakc { participuje na schematu rzen soubeznosti 2 Kazdy participant muze kdykoliv volat koordinatora pozadavkem abortTransaction, pokud z nejakeho duvodu nen schopny jeho uzel v resen subtransakce pokracovat Jan Staudek, FI MU Brno | PA150 { Transakce 83 Konceptualn schema funkcnch komponent TPM Jan Staudek, FI MU Brno | PA150 { Transakce 84 Prklad, distribuovana bankovn transakce 2 Klientova transakce zahrnuje praci s ucty A,B, C a D ucet A spravuje server v pobocce X ucet B spravuje server v pobocce Y ucty C a D spravuje server v pobocce Z transakce { prenas 4 USD z uctu A do do uctu C a { prenas 3 USD z uctu B do uctu D 2 Koordinator transakce muze byt situovany v kteremkoliv serveru napr. v severu pobocky X, ktera je napr. umstena v centrale banky Jan Staudek, FI MU Brno | PA150 { Transakce 85 Prklad, distribuovana bankovn transakce Jan Staudek, FI MU Brno | PA150 { Transakce 86 Prklad, distribuovana bankovn transakce Jan Staudek, FI MU Brno | PA150 { Transakce 87 Prklad, distribuovana bankovn transakce Jan Staudek, FI MU Brno | PA150 { Transakce 88 Prklad, distribuovana bankovn transakce 2 klient otevre transakci a zska jej identi kator, T 2 Posleze klient vyvolava metody predepsane programem transakce realizovane v ramci otevrene transakce napr. b.withdraw (T,3) v serveru Y 2 Invokovany objekt b v serveru Y informuje objekt participant v tomto serveru o tom, ze nalez transakci T 2 pokud tak objekt participant v serveru Y dosud neucinil, informuje objekt participant koordinatora, ze nalez transakci T 2 po aplikacnm dokoncen transakce, klient nakonec informuje koordinatora transakce o konci transakce pozadavkem closeTransaction Jan Staudek, FI MU Brno | PA150 { Transakce 89 Resen problemu ukoncen transakce { Commit protocols 2 Problem { zajisten atomicity (distribuovane) transakce 2 Klient pozadal koordinatora o otevren transakce 2 Pote klient postupne vyzadal provaden subtransakc na vce serverech 2 Nakonec klient zada koordinatora o closeTransaction, ukoncen transakce formou commit nebo abort abort { napr. se mu nepodarilo se spojit s nekterym uzlem nebo zjistil narusen konzistence DB, ... 2 Atomicke ukoncen distribuovane transakce se mus rdit jistymi pravidly, protokolem 2 Jedna se o preveden hotove transakce na provedenou transakci { commit, proto commit protocol Jan Staudek, FI MU Brno | PA150 { Transakce 90 Jednoduchy, 1-fazovy, commit protokol 2 O typu ukoncen (proveden / krach) transakce rozhoduje klient, ktery transakci vyvolal 2 Koordinator postupne (opakovane) sdeluje participantum podle pozadavku klienta zda maj provest commit nebo abort, a to opakovane dokud mu kazdy participant nesdel, ze u sebe provedl commit nebo abort jm resene subtransakce 2 Pro resen ukoncen distribuovane transakce je jednoduchy, 1-fazovy, commit protokol nedostatecny Duvody { viz dale Jan Staudek, FI MU Brno | PA150 { Transakce 91 Jednoduchy, 1-fazovy, commit protokol 2 Pro resen ukoncen distribuovane transakce je jednoduchy, 1-fazovy, commit protokol nedostatecny Kdyz klient rozhodne ukoncit transakci radne, commit, nedava tm moznost zadnemu participantu ci koordinatorovi aby on jednostranne rozhodl o zkrachovan transakce Napr. dky zamykan muze mezi servery vzniknout uvaznut, ktere vede ke zkrachovan transakce, ale o tom se klient nedozv, dokud nevyda dals pozadavek na server, dokud mu neuplyne time-out, ... Napr. koordinator nemus vedet, ze jisty server mel behem resen transakce vypadek a obnovoval svoji cinnost v prubehu distribuovane transakce a koordinator by mel tudz transakci abortovat Jan Staudek, FI MU Brno | PA150 { Transakce 92 2-fazovy commit protokol 2 Jedna se o zvlastn prpad problemu Byzantskych generalu distribuovana dohoda subtransakc zda transakci koncit radne ci krachovat v prostred s vypadky uzlu Lokaln atomicita subtransakce nestac, clem je globaln atomicita, ta nemuze byt zarucena implicitne. Globaln synchronizace distribuovane transakce muze skoncit v nekterych uzlech provedenm subtransakce a v jinych krachem To ohrozuje globaln atomicitu a tudz konzistenci DBS Dosazen atomicity na globaln urovni vyzaduje pouzt synchronizacn protokol, ktery zajist jednoznacny konecny vysledek pro kazdou distribuovanou transakci bez ohledu na vypadky uzlu. Jan Staudek, FI MU Brno | PA150 { Transakce 93 2-fazovy commit protokol 2 Two-Phase Commit Protocol, (2PCP nebo take 2PCP) synchronizacn protokol, ktery res problem atomickeho ukoncen umoznuje kazdemu participantu jednostranne abortovat svoji cast transakce jestli jedna subtransakce krachuje, krachuje cela transakce jestlize se radne ukonc vsechny subtransakce, radne se ukoncuje cela transakce 2 Ukoncen transakce pomoc 2PCP koordinuje koordinator, vysledkem rozhodnut koordinatora muze byt commit { potvrzen proveden subtransakc ve vsech uzlech Si a preveden transakce do stavu provedna abort { zrusen ucinku subtransakc ve vsech uzlech Si, pokud alespon jedna subtransakce zkrachovala, a zrusen transakce Jan Staudek, FI MU Brno | PA150 { Transakce 94 2-fazovy commit protokol 2 2PCP zajist'uje, ze distribuovana transakce se bud' radne ukonc a vsechny jej ucinky se stanou trvale ve vsech participujcch uzlech nebo distribuovana transakce zkrachuje a vsechny jej ucinky ve vsech uzlech se zrus, jako by se transakce nikdy nevykonala. 2 Spusten 2PCP Kazda transakce ma v nekterem uzlu DS koordinatora. Pote, co transakce z hlediska klienta dokonc vsechny aplikacn operace, klient pozada koordinatora o ukoncen transakce koordinator spoust 2PCP. detaily behu 2PCP viz dale Jan Staudek, FI MU Brno | PA150 { Transakce 95 Resen ukoncen transakce, Two-Phase Commit Protocol 2 2PCP se sklada ze dvou faz, jmenovite z hlasovac faze a z faze vydan rozhodnut. 2 Hlasovac faze Koordinator zada vsechny participanty transakce o zavazek, ze subtransakci radne ukonc, kdyz ve fazi vydan rozhodnut k tomu dostanou pokyn { hlasuj ano / ne pro ukoncen transakce Jakmile participant obdrz vyzvu k hlasovan, over na nej navazanou subtransakci z pohledu konzistence dat. Pokud lze subtransakci radne ukoncit (tj. prosla validace), hlasuje ano. V opacnem prpade hlasuje ne, subtransakci nasledne bez dalsho cekan krachuje, rus subtransakc zpusobene ucinky a uvoln se vsechny subtransakc drzene zdroje (zamky, ...). Jan Staudek, FI MU Brno | PA150 { Transakce 96 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Ve faz vydan rozhodnut koordinator transakce rozhoduje zda radne ukoncit transakci, pokud jsou vsichni participanti pripraveni radne ukoncit transakci (hlasovali ano) nebo zda zkrachovat, pokud se kterykoliv participant rozhodl transakci zkrachovat (hlasoval ne). 2 V prpade vydan rozhodnut radne ukoncit transakci, koordinator vysla vsem participantum zpravy commit (radne ukoncit), transakce se stane provedenou 2 V prpade vydan rozhodnut zkrachovat transakci koordinator odesla zpravy abort (zkrachovat), a to pouze tem participantum, kter jsou pripraveni radne ukoncit transakci (hlasovali ano), transakce se stane zkrachovalou Jan Staudek, FI MU Brno | PA150 { Transakce 97 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Jestlize participant hlasoval ano, nemuze subtransakci jednostranne ani radne ukoncit ani zkrachovat, mus cekat, dokud od koordinatora neobdrz konecne rozhodnut. 2 Participant je tudz po neurcitou dobu blokovany (okno nejistoty), ceka na rozhodnut koordinatora. 2 Jakmile participant obdrz naln rozhodnut koordinatora, rozhodnut respektuje a vykona odpovdajc akce a uvoln vsechny zdroje, ktere subtransakce drz, a obvykle odesle zpet koordinatorovi potvrzen (ACK) 2 Zamky vyzadane transakc si transakce mus drzet az do sveho ukoncen Jan Staudek, FI MU Brno | PA150 { Transakce 98 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Jakmile koordinator obdrz potvrzen od vsech participantu, pak v prpade, ze hlasovali ano, zapomene na transakci, vymaze veskere informace tykajc se transakce z protokolove tabulky udrzovane v hlavn pameti. 2 Odolnost 2PCP vuci vypadkum se dosahuje zaznamenavanm prubehu protokolu do denku udrzovanych jak koordinatorem, tak i participanty. 2 Denky se udrzuj ve stabilnch, energeticky nezavislych pametech, vypadky je neznic. 2 Koordinator zapisuje do denku prmo (bez vyrovnavan toku dat na urovni OS), jeste pred odeslanm sveho rozhodnut participantum. Jan Staudek, FI MU Brno | PA150 { Transakce 99 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Stejne tak kazdy participant zapisuje do sveho denku zaznam prepared pred zaslanm hlasu ano a zaznam decision pred zaslanm potvrzen rozhodnut. 2 Kdyz koordinator protokol ukoncuje, zapisuje uz beznym (vyrovnavanym) zapisem do denku zaznam end 2 Tento zaznam indikuje, ze vsichni participanti obdrzeli rozhodnut, a ze zadny z nich se v budoucnosti nebude dotazovat na stav transakce. 2 Po te koordinator muze na transakci z pohledu 2PCP (trvale) zapomenout Jan Staudek, FI MU Brno | PA150 { Transakce 100 Stavovy diagram 2PCP Jan Staudek, FI MU Brno | PA150 { Transakce 101 Two-Phase Commit Protocol, rekapitulace 2 Prvn faze { hlasovac faze koordinator transakce vyzve participanty ke sdelen zda transakci radne ukoncit nebo krachovat kazdy participant sdeluje zda transakci ukoncit nebo krachovat jakmile participant rekne ukoncit, nesm posleze rci krachovat tj. kdyz participant rekne ukoncit, mus si byt jisty, ze bude schopny dokoncit svoji cast commit protokolu, i kdyz mezi tm vypadne a obnov svoji cinnost, denk mus mt zapsany na disku jakmile participant ma vsechny svoje objekty zmenene v prubehu transakce uchovane v permanentn pameti, je pripraveny kdykoliv posleze potvrdit radne ukoncen transakce v permamentn pameti mus mt poznaceny i stav pripraveny Jan Staudek, FI MU Brno | PA150 { Transakce 102 Two-Phase Commit Protocol, rekapitulace 2 Druha faze { vydan rozhodnut o hlasovan koordinator sdel participantum rozhodnut, vysledek hlasovan kazdy participant realizuje rozhodnut jestlize alespon jeden participant hlasoval abort, krachovat, rozhodnut zn zkrachovat transakci jestlize vsichni participanti hlasovali commit, ukoncit, rozhodnut zn ukoncit transakci { commit 2 Problemy mus se zajistit, aby hlasovali vsichni participanti mus se zajistit, aby vsichni realizovali spolecne naln rozhodnut trivialn resen techto problemu je v prostred bez poruch 2PCP ale mus spravne pracovat i v prpadech vypadku serveru, ztrat zprav nebo docasnych vypadku schopnosti komunikace mezi servery Jan Staudek, FI MU Brno | PA150 { Transakce 103 Model poruch pro Two-Phase Commit Protocol 2 Realny distribuovany system = asynchronn distribuovany system 2 Servery mohou vypadavat, zpravy se mohou ztracet 2 Podpurny komunikacn system odstranuje porusene a duplikovane zpravy 2 Nejedna se o byzantinske chyby Server bud'to vypadne nebo se rd zaslanymi zpravami 2 Pripomenut { byzantinska chyba proces muze nastavit chybny obsah zpravy nebo na zadost vracet chybnou hodnotu, muze duplikovat odpoved', ... byzantinskou chybu nelze detekovat pozorovanm, zda proces odpovedel na invokaci, proces muze odpoved' vynechat Jan Staudek, FI MU Brno | PA150 { Transakce 104 Model poruch pro Two-Phase Commit Protocol 2 Two-Phase Commit Protocol je prklad protokolu pro dosazen dohody Obecne plat { dosazen dohody nen v plne asynchronnch systemech mozne 2 Two-Phase Commit Protocol v asynchronnm prostred dohody dosahuje za omezujc podmnky: vypadky procesu (serveru) jsou maskovane obnovou vypadlych procesu novymi procesy, jejichz stav je nastaveny podle informac uchovavanych v permanentn pameti a informac drzenych jinymi procesy proces mozna po jistou dobu nereaguje, ale kdyz reaguje, reaguje validne Jan Staudek, FI MU Brno | PA150 { Transakce 105 Model poruch pro Two-Phase Commit Protocol 2 v kazdem uzlu/participantu mus spravce transakc mus udrzovat denk, write-ahead log aby bylo mozne pri restartu uzlu po jeho vypadku ucinky subtransakce zrusit (viz prednaska Transakce): { objekt se modi kuje pouze po zaznamenan undo info do logu { pred potvrzenm zmen ze zaznamenaj redo a undo logy do stabiln pameti 2 Prpomnka { protokol 2PCP je navrzeny s clem umoznit participantu zkrachovat, zrusit svoji cast transakce (z duvodu zachovan atomicity krachuje cela transakce) pro praci v asynchronnm (distribuovanem) systemu, ve kterem mohou vypadavat uzly (servery) a ztracet se zpravy { se nejedna o byzantinske (libovolne) chyby, server bud' vypadne nebo se rd vyslanymi zpravami { od podpurneho systemu request-reply se ocekava, ze odstran vsechny porusene, prp. duplikovane zpravy Jan Staudek, FI MU Brno | PA150 { Transakce 106 Komunikace v 2PCP 2 Koordinator v prubehu transakce, az na sdelen participanta o pripojen k transakci (join), s participanty nekomunikuje 2 Pozadavek na commit nebo abort transakce predava koordinatorovi klient 2 Pokud klient zada pri ukoncovan transakce abortTransaction nebo kdyz nektery participant hlas abort, koordinator informuje participanty okamzite 2 Vme jiz, ze 2PCP nastupuje do sve role v okamziku, kdy klient pozaduje commitTransaction (ukoncit transakci) V 1. fazi koordinator zada vsechny participanty, aby rekli, zda jsou pripraveni na commit ve 2. fazi koordinator participantum rka, at' udelaj akce odpovdajc commit nebo abort Jan Staudek, FI MU Brno | PA150 { Transakce 107 Komunikace v 2PCP 2 Slozitost pri N clenech kohorty 3N zprav, ve 3 casovych rundach haveCommited (ACK) se nepocta, 2PCP funguje i bez n zprava slouz k indikaci moznosti odstranit zastarale informace 2 Stav neurcitosti v participantu = cekan na naln rozhodnut Jan Staudek, FI MU Brno | PA150 { Transakce 108 Vypadky pri resen 2PCP 2 Komunikace mezi koordinatorem a participanty muze selhat, duvody { nektery server vypadne { nebo komunikacn system ztrat zpravu 2 Resitelnost dosazen dohody se podporuje sledovan casovych vypadku (time-outs) { system je pseudoasynchronn Po casovem vypadku mus proces cekajc na udalost provest relevantn akci Kazdy krok, ve kterem se ceka na udalost, mus byt osetreny hldanm casoveho limitu V asynchronnm systemu uplynut casoveho limitu nemus implikovat trvalou poruchu serveru Jan Staudek, FI MU Brno | PA150 { Transakce 109 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Zotaven ve 2PCP Vypadky uzlu a komunikac jsou detekovane timeouty, hldanm uplynut casovych limitu. Kdyz cinny uzel detekuje vypadek evokuje Recovery Manager, jehoz ukolem je vypadek zvladnout. V 2PCP muze selhat uzel s koordinatorem nebo uzel participanta. V 2PCP jsou ctyri msta, kde muze dojt k selhan komunikace. Jan Staudek, FI MU Brno | PA150 { Transakce 110 V 2PCP jsou ctyri msta, kde muze dojt k selhan komunikace 2 Participant ceka na zpravu s vyzvou k hlasovan. Participant jeste nehlasoval. V tomto prpade participant muze rozhodnout o zkrachovan subtransakce jednostranne. Jan Staudek, FI MU Brno | PA150 { Transakce 111 V 2PCP jsou ctyri msta, kde muze dojt k selhan komunikace 2 Koordinator ceka na hlasovan participantu. Vzhledem k tomu, ze koordinator dosud neucinil konecne rozhodnut, zadny participant se nemohl radne ukoncit, kordinator muze rozhodnout zkrachovat. Jan Staudek, FI MU Brno | PA150 { Transakce 112 V 2PCP jsou ctyri msta, kde muze dojt k selhan komunikace Participant hlasoval ano, ale neobdrzel rozhodnut ukoncit/zkrachovat. V tomto prpade se participant nemuze rozhodnout jednostranne, protoze nen jasne, jake rozhodnut koordinator vyda. Participant je v tomto prpade blokovan, dokud znovu nenavaze komunikaci s koordinatorem a pote, co ji znovu navaze, participant pozada od koordinatora o konecne rozhodnut, prosad pokracovan protokolu a potvrd koordinatorovi rozhodnut. Jan Staudek, FI MU Brno | PA150 { Transakce 113 V 2PCP jsou ctyri msta, kde muze dojt k selhan komunikace 2 Koordinator ceka na potvrzovan od participantu. V tomto prpade koordinator po obnove komunikace znovu posla rozhodnut tem participantum, kter rozhodnut dosud nepotvrdili. Jan Staudek, FI MU Brno | PA150 { Transakce 114 Resen ukoncen transakce, Two-Phase Commit Protocol 2 Pripomenut Koordinator nemuze jen tak jednoduse vymazat informace tykajc se transakce z protokolove tabulky nebo ze sveho stabilnho denku dokud neobdrz potvrzen od vsech participantu. Jan Staudek, FI MU Brno | PA150 { Transakce 115 Obnova koordinatora po vypadku uzlu koordinatora koordinator po restartu cte denk ze stabiln pameti a znovu vytvar protokolarn tabulku tak, aby zachycovala stav 2PCP pro vsechny probhajc transakce pred vypadkem. Transakce, ktere byly aktivn podle koordinatora pred jeho vypadkem a nemaj v denku zaznam decision, koordinator krachuje. Transakcm, ktere zacaly 2PCP a jeste ho nedokoncily pred vypadkem (tj. transakce, ktere maj v jeho denku zaznamy decision bez odpovdajcch zaznamu end ) koordinator dokonc protokol zaslanm rozhodnut a vycka na jejich potvrzen. Jelikoz nekter z participantu jiz mohli obdrzet rozhodnut pred vypadkem a prosadili ho, mohli tito ucastnci jiz zapomenout, ze tato transakce kdy existovala. Takov ucastnci jednoduse odpov slepym potvrzenm, kterym indikuj, ze jiz obdrzeli a prosadili rozhodnut pred vypadkem. Jan Staudek, FI MU Brno | PA150 { Transakce 116 Obnova participanta po vypadku uzlu participanta vyhledava ve svem denku existenci transakc, ktere jsou ve stavu ,,pripravena na ukoncen" (tj. maj v denku zaznam prepared bez zaznamu decision). Pro vyhledanou transakci participant pozada koordinatora o zaslan rozhodnut a pote co rozhodnut obdrz prosad rozhodnut a potvrd. Koordinator bude vzdy schopny reagovat na tyto dotazy, protoze transakci nemuze zapomenout drve, nez obdrz potvrzen vsech participantu. Jan Staudek, FI MU Brno | PA150 { Transakce 117 Vypadky pri resen 2PCP 2 Participant hlasoval v 1. fazi 2PCP Yes a ceka na sdelen vysledku dohody { commit / abort Participant je ve stavu neurcitosti (uncertain) netus jak bude znt rozhodnut, nemuze rozhodnout jednostranne Nemuze uvolnit objekty drzene pro aktualne resenou transakci pro pouzit jinymi soubeznymi transakcemi 2 Vypadek koordinatora v tomto kroku protokolu participant mus cekat na obnovu koordinatora po uplynut casoveho limitu muze pozadat o zopakovan zpravy o rozhodnut po x zopakovan takovych zadost krachuje prpadne se muze dotazovat ostatnch participantu jak znelo rozhodnut pokud ale tito budou rovnez ve stavu neurcitosti, nedozv se ale nic Jan Staudek, FI MU Brno | PA150 { Transakce 118 Vypadky pri resen 2PCP 2 Participant nedostal po ukoncen svych operac dotaz canCommit? Nezbyva nic jineho po uplynut casoveho limitu nez jednostranne udelat abort 2 Koordinator nedostal do uplynut casoveho limitu hlas od nektereho participanta Rozhoduje abort transakce Toto rozhodnut rozesle vsem participantum pokud nektery opozdeny participant bude pote hlasovat commit, zustane ve stavu neurcitosti (resen viz vyse) Jan Staudek, FI MU Brno | PA150 { Transakce 119 Hodnocen 2PCP 2 2PCP je blokujc protokol, { drz si zamcene zdroje behem cekan na zpravu, neuvolnuje je, { ostatn procesy, ktere tyto zdroje pozaduj, cekaj 2 kdyz vypadne uzel s koordinatorem, kohorta sama transakci neukonc, zdroje drzene v uzlech kohorty budou drzene do doby dokud uzel s koordinatorem neobnov svoji cinnost 2 2PCP je konzervativn, pri nejistote dava prednost zrusen (abort) pred dokoncenm (commit) Jan Staudek, FI MU Brno | PA150 { Transakce 120 Prevence uvaznut soubeznych transakc 2 kazda transakce si zamkne vsechna data drve nez se spust eliminace nutne podmnky uvaznut { hold-and-wait velmi neefektivn resen, zvlaste pro distribuovane prostred nepouzitelne 2 nebo se de nuje se porad zamykan dat eliminace postacujc podmnky uvaznut ve wait-for grafu uplne usporadan dat + 2PLP aplikovany na toto porad 2 nebo se aplikuj priority transakc odvozene z behu casu stars transakce ma vyss prioritu, ma pravo cekat 2 nebo se pripust preempce transakce, ktera drz potrebne zdroje eliminace nutne podmnky uvaznut no preemption Jan Staudek, FI MU Brno | PA150 { Transakce 121 Prevence uvaznut na bazi rozhodovacch TS 2 rozhodovac TS se transakci prideluje pri jejm vytvoren a pri prpadnem navratu transakce zpet na zacatek se nemen Wait-Die Scheme, cekej nebo zemri (zemri = delej se znovu) { stars T ceka na mlads T dokud tato neuvoln datovou polozku { mlads T neceka na stars T, vzdy je vracena (zemre) a a spoust se znovu, ale se zachovanm veku (mozna i vcekrat, ale postupne starne a jednou bude nejstars ...) Wound-Wait Scheme, poran (at' se dela nekdo znovu) nebo cekej { stars T neceka na mlads T dokud tato neuvoln datovou polozku, ran ji (tj. prosad jej vracen, ale se zachovanm veku) { mlads T ceka na stars T dokud tato neuvoln datovou polozku 2 v reale schema Wait-Die Scheme casto zpusobuje vce navratu nez schema Wound-Wait Scheme Jan Staudek, FI MU Brno | PA150 { Transakce 122 Prevence uvaznut transakc na bazi TS, Wait-Die Scheme 2 Zalozeno na nepreemptivn technice 2 Kdyz se Ti inicialne startuje, zska rozhodovac T Si 2 Necht' pri uplatnen zadosti Ti s T Si o jisty zamek drz tento zamek Tj s T Sj je-li zadajc Ti stars nez okamzity vlastnk prostredku, { transakce Tj, T Si < T Sj, Ti pocka na uvolnen zamku a zska ho po te, jakmile jej drzitel zamku, tj. transakce Tj, uvoln je-li zadajc Ti mlads nez okamzity drzitel zamku { Tj, T Si > T Sj, Ti je vracena, zadost o pridelen opakuje, ale se stejnym T Si 2 Takze plat { jestlize Ti pozaduje zamek drzeny Tj, sm Ti cekat (wait) jen kdyz T Si < T Sj (Ti je stars nez Tj). Jinak je Ti vracena v historii zpet na vydan zadosti (dies, zemre). Jan Staudek, FI MU Brno | PA150 { Transakce 123 Prevence uvaznut transakc na bazi TS, Wait-Die Scheme 2 Wait-Die Scheme zajist'uje, ze transakce muze zemrt vcekrat, ale ne nekonecne krat, jednou prijde jej cas, kdy si na uvolnen prostredku urcite pocka, protoze bude ze vsech transakc nejstars 2 Prklad: Transakce T1, T2 a T3 maj TS s hodnotami postupne 5, 10, resp. 15. Jestlize T1 (T S1 = 5) pozaduje zamek drzeny T2 (T S2 = 10), T1 bude cekat na uvolnen zamku transakc T2 Jestlize T3 (T S3 = 15) pozaduje zamek drzeny transakc T2 (T S2 = 10), pak T3 zemre, tj. bude vracena na zopakovan zadosti o pridelen zamku, casove raztko se j zachova a tak casem se stava stars a stars a ma stale vets sanci si na uvolnen zamku pockat. Jan Staudek, FI MU Brno | PA150 { Transakce 124 Prevence uvaznut transakc na bazi TS, Wound-Wait Scheme 2 Wound-Wait Scheme zajist'uje, ze stars transakce nikdy neceka na mlads transakci 2 Schema je zalozene na preemptivn technice je-li zadajc Ti stars nez okamzity vlastnk prostredku { Tj , Ti odebere Tj zamek a Tj se v historii vrat, bude zopakovat zadost o jeho pridelen, se stejnym casovym raztkem (roll-back, undo) je-li zadajc Ti mlads nez okamzity vlastnk prostredku { Tj, Ti ceka na uvolnen zamku a zska ho po te jakmile jej dosavadn drzitel zamku Tj uvoln 2 navratu byva mene, cekan vce 2 obe schemata wait-die i wound-wait restartuj transakce s puvodnm rozhodovacm TS, coz zabranuje starnut Jan Staudek, FI MU Brno | PA150 { Transakce 125 Prevence uvaznut transakc na bazi TS, Wound-Wait Scheme Prklad: 2 Transakce T1, T2 a T3 maj TS s hodnotami 5, 10, resp. 15 2 Jestlize T1 (T S1 = 5) pozaduje zamek drzeny transakc T2 (T S2 = 10), prebere T1 zamek od T2, T2 je ,,zranena"transakc T1, je vracena, ... 2 Jestlize T3 (T S3 = 15) pozaduje zamek drzeny transakc T2 (T S2 = 10), transakce T3 bude cekat na jeho uvolnen Jan Staudek, FI MU Brno | PA150 { Transakce 126 Klasi kace poruch 2 poruchy transakc logicke chyby v resen T nelze pokracovat v dusledku nejakych vnitrnch chybovych podmnek aplikace/transakce { chybny vstup, nenalezen dat, pretok, ... { Vesmes neobnovitelna cinnost, havarie / krach cele aplikace beh aplikace nema smysl obnovovat systemem detekovatelne chyby chybu detekuje podpurny system (TPM, OS, DBS, ...), aktivn T krachuje dusledkem napr. uvaznut, uplynutm casoveho limitu, ...). { Zkrachovana transakce muze byt nasledne spustena znovu napr. protokolem TPM rescm uvaznut, nebo klientem z duvodu uplynut casoveho limitu neobnovuje se beh aplikace, opakovane se spoust zkrachovala T Jan Staudek, FI MU Brno | PA150 { Transakce 127 Klasi kace poruch 2 Porucha disku padnut hlav disku na povrch, chyba pamet'oveho media, porucha vyrazujc diskovy mechanismus, ... predpoklad { porucha je detekovatelna (kontroln soucty, ...) Vyss spolehlivost lze dosahnout aplikac nektere z metod RAID Po obnove z periodicky provadenych zaloznch kopi dat a kontrolnch bodu aplikace lze aplikaci od kontrolnho bodu spustit znovu. 2 (Docasny) vypadek systemu vypadek energie, hw porucha, sw porucha systemu, ... predpoklady { obsah energeticky nezavislych pamet se vypadkem systemu neposkozuje, beh vlastnho systemu lze posleze obnovit neporusenost dat lze overovat provadenm integritnch kontrol Transakce nedokoncena pri vypadku systemu krachuje a pri obnove cinnosti systemu ji Recovery Manager (TPM) spust znovu. Jan Staudek, FI MU Brno | PA150 { Transakce 128 Algoritmy obnovy 2 Jedna se o techniky zajist'ujc v prostred s vypadky konzistenci baze dat, atomicitu transakc vc. trvalosti vysledku provedenych transakc 2 Algoritmy obnovy maj 2 casti Akce probhajc behem normalnho resen transakc cl { zajistit dostatek informac nutnych pro obnovu po vypadku cena { snzen vykonu pro aplikace, zvysen naroku na pamet' obnovovac akce probhajc po vypadku, cl { obnova obsahu baze dat do stavu, ktery zarucuje (viz vyse): { konzistenci baze dat, { atomicitu transakc a { trvalost vysledku transakc Jan Staudek, FI MU Brno | PA150 { Transakce 129 Obnovitelnost transakcnho zpracovan, spravce obnovy 2 Obnovitelnost po vypadku / poruse res soucast TPM { spravce obnovy, recovery manager 2 spravce obnovy ma ukoly uchovavat informace o modi kacch hodnot objektu provadenych transakcemi v permanentn pameti (vytvar obnovovac soubor, recovery file) po opetovnem spusten po vypadku obnovovat puvodn hodnoty objektu v serveru (puvodn = vysledek provedenych transakc) prubezne reorganizovat obnovovac soubor s clem dosahnout co nejvyss vykon obnovy udrzovat dostatecny pamet'ovy prostor na disku pro obnovovac soubor 2 Pokud se pozaduje obnovitelnost i pri poruse permanentn pameti, je potreba pouzt zrcadlen disku (RAID) apod. Jan Staudek, FI MU Brno | PA150 { Transakce 130 Metody udrzby obnovovacho souboru 2 Veden denku, log 2 Obnovovac proces mus byt idempotentn operac lze jej opakovat vcekrat se stejnym vysledkem Jan Staudek, FI MU Brno | PA150 { Transakce 131 Veden denku 2 Zmeny v databazi spravovane serverem se behem provaden vsech transakc zaznamenavaj do denku (log) 2 Denkove zaznamy se vytvar apriornm zaznamenavanm { zaznamenavanm predem, write-ahead logging, TPM je vytvar pred vlastnm provedenm operac nad daty zapisuj se na disk prmo, bez vyrovnavan toku na urovni OS (TPM vyvola bezprostredn proveden sluzby OS output) Denk mus TPM periodicky cistit, dale jiz nepotrebne denkove zaznamy vymazava. 2 Porad zaznamu v denku odraz historii behu transakcnho zpracovan 2 Denk obsahuje aktualn, posledn obraz hodnot objektu + historii transakc, ktere tento obraz vyprodukovaly Jan Staudek, FI MU Brno | PA150 { Transakce 132 Typy zaznamu v obnovovacm souboru typu denk 2 Zaznam o startu transakce, < Ti start > 2 Zaznam o korekci polozky/objektu, < Ti, Xj, V1, V2 > Ti identi kator transakce, ktera provedla write Xj identi kator polozky/objektu V1 puvodn hodnota polozky/objektu V2 nova hodnota polozky/objektu zaznam umoznuje provest undo zmen ucinenych zkrachovalou T zaznam umoznuje provest redo zmen ucinenych provedenou T, jejz vysledky se pred vypadkem nezapsaly trvale na disk { T modi kuje DB ≡ provad write do bu eru v RAM, ktery OS nasledne, nekdy, sluzbou output vypisuje na disk 2 Zaznam o proveden transakce, < Ti commit > 2 Zaznam o zkrachovan transakce, < Ti abort > Jan Staudek, FI MU Brno | PA150 { Transakce 133 Veden denku 2 Spravce obnovy je aktivovan kdykoliv transakce je spoustena { spravce zaznamenava v obnovovacm souboru existenci transakce, < Ti start > zapisuje do DB { spravce aktualizuje obnovovac soubor zaznamem o korekci objektu, < Ti, Xj, V1, V2 > je provedena / zkrachuje { spravce aktualizuje v obnovovacm souboru stav transakce zaznamem o proveden ci krachovan, < Ti commit >, < Ti abort > 2 Denk nen aplikacn soucast baze dat, denk (obnovovac soubor) si uchovava v permanentn pameti TPM 2 Pri obnove po vypadku se rus ucinky kazde transakce, ktera nema v denku zaznam o proveden { < Ti commit >, vsechny podle denku neprovedene transakce krachuj Jan Staudek, FI MU Brno | PA150 { Transakce 134 Veden denku 2 TPM v urcitych intervalech vytvar v denku kopie stavu cele DB, tzv. kontroln body, checkpoints 2 Historii transakc provedenych do kontrolnho bodu lze z denku vymazat 2 Pri obnove baze dat po vypadku TPM pak zrekonstruuje stav DB pred vypadkem podle informac uvedenych v poslednm kontrolnm bodu v denku 2 Zapis do obnovovacho souboru se res atomicky, zapisy do obnovovacho souboru jsou prme, nevyrovnavane zapisy, pokud server vypadne, je vadny pouze posledn zapis 2 Obnovovac soubor je udrzovany jako sekvencn soubor, sekvencn zapisy na disk lze resit pomerne rychle Jan Staudek, FI MU Brno | PA150 { Transakce 135 Algoritmus obnovy { bazove vlastnosti 2 Protoze denk obsahuje jak stare tak i nove hodnoty objektu, lze tudz resit jak undo, tak i redo transakce 2 Algoritmy obnovy obvykle vyzaduj, aby objekt modi kovany jednou transakc nemohla modi kovat jina transakce, dokud se prva transakce neprovede nebo nezkrachuje { mus se pouzt alespon striktn 2-fazove zamykan apod. { exkluzivn zamky se uvolnuj az pri commit/abort transakce 2 Moznost obnovitelnosti se dosahuje za cenu omezen soubeznosti, :{( Jan Staudek, FI MU Brno | PA150 { Transakce 136 Obnova podle denku, Log-based Recovery 2 Zaznam o korekci se do denku na disku zapisuje pred modi kac objektu v DB a dky tomu lze v DB udelat modi kaci objektu kdykoliv pozdeji, kdy to je optimaln undo modi kac udelanych zkrachovanymi / nedokoncenymi transakcemi redo modi kac udelanych provedenymi transakcemi, ktere se do vypadku nestacily vypsat do DB na disku Jan Staudek, FI MU Brno | PA150 { Transakce 137 Obnova podle denku, Log-based Recovery 2 Jakmile se transakce se stane hotova do denku na disku se zapse zaznam o proveden transakce < Ti commit > v tomto okamziku jsou v denku uz vsechny dosavadn denkove zaznamy dane transakce provedenou transakci lze tudz kdykoli (po vypadku) zopakovat (redo) z hlediska nalnch hodnot objektu 2 jestlize dojde k vypadku a v denku zaznam < Ti commit > nen, ucinky transakce se pri obnove cinnosti rus, vrac se zpet na puvodn hodnoty modi kovanych objektu Transakce se povazuje za zkrachovalou, provad se undo podle denku Jan Staudek, FI MU Brno | PA150 { Transakce 138 Obnova podle denku, Log-based Recovery, zapory 2 celkove dochaz ke snizovan vykonu zapis dat se provad 2× (1× do denku a 1×do DB), do denku se zapisuj zaznamy o startech, proveden a krachovan transakc 2 zvysuje se pamet'ova slozitost denk (log) vyzaduje pro sve ulozen dals pamet' na disku Jan Staudek, FI MU Brno | PA150 { Transakce 139 Pouzite obnovovac procedury 2 pouzvaj denk k nalezen objektu modi kovanych Ti a starych a novych hodnot techto objektu 2 redo(Ti) nastavuje objekty modi kovane Ti na nove hodnoty porad nastavovan mus byt shodne s poradm modi kac denk se obvykle prohledava systematicky od zacatku a nastavuje se nova hodnota pro kazdy modi kovany objekt Jan Staudek, FI MU Brno | PA150 { Transakce 140 Pouzite obnovovac procedury 2 undo(Ti) nastavuje objekty modi kovane Ti na stare, inicialn hodnoty operace undo(Ti) se provad prave jedenkrat v prpadech, ze se v denku nenalezne ani commit ani abort Ti a res se navrat behem normalnho zpracovan nebo pri obnove po vypadku. porad provaden undo(Ti) { zpetne od poslednho zaznamu v denku pro Ti Jan Staudek, FI MU Brno | PA150 { Transakce 141 Kontroln body, Checkpoints 2 denky transakc mohou byt dlouhe, obnova pak trva dlouho 2 mohou se zbytecne delat redo transakc, ktere jiz maj udelane vystupy (outputs) do baze dat 2 periodicky vytvarene kontroln body dobu obnovy zkrat 2 behem vytvaren kontrolnho bodu nesmej transakce delat korekce dat, nesm zapisovat zaznamy do denku apod. 2 pri periodickem vytvaren kontrolnch bodu se provad: vystup vsech denkovych zaznamu umstenych v danem okamziku v RAM z RAM (energeticky zavisle pameti) do permanentn pameti vystup vsech modi kovanych bloku vyr. pam. na disk (perm. pamet') vystup zaznamu < checkpoint L > do denku (log) udrzovaneho v energeticky nezavisle pameti L je seznam aktivnch transakc v dobe tvorby kontrolnho bodu Jan Staudek, FI MU Brno | PA150 { Transakce 142 Kontroln body, Checkpoints 2 Ti provedene pred zapisem < checkpoint L > se neobnovuj pomoc redo, jejich vysledek je soucast dat kontrolnho bodu 2 Obnova po vypadku se tyka pouze transakc { aktivnch v okamziku vytvaren kontrolnho bodu a { vsech transakc nasledujcch po techto transakcch Pro transakce nemajc v denku < commit > se provede undo Pro transakce majc v denku < commit > se provede redo Jan Staudek, FI MU Brno | PA150 { Transakce 143 Prklad obnovy z kontrolnho bodu vysledek T1 je obsazeny v kontrolnm bodu, nespoust se zadna akce T2 a T4 jsou v dobe vypadku jiz provedene, T3 a T5 nejsou v dobe vypadku provedene, priprav se seznam undo a provede se redo T4 a pak redo T2 provede se undo T5 a pak undo T3 Jan Staudek, FI MU Brno | PA150 { Transakce 144