{{zpět|Transakce}}

Proč tento materiál?

• vhodný jako opakování před zkouškou

• přehledně ukazuje odpovědi, není nutné je hledat "někde ve slidech"

• je tak česky, jak to jen jde

• více zdrojů není na škodu

Slabiny tohoto materiálu

• vzniká uprostřed noci => obsahuje chyby

• je stručnější a nevysvětluje některé pojmy, které používá

• doporučuji jej jako "shrnutí" -- něco, co čtete nakonec

• neumím vložit tabulku do odstavce-- 16:04, 15 Jun 2006 (CEST)

Spolehlivost

Questions

1. Vysvetlete rozdíl mezi soft error a hard error.

   • soft zotavitelna po retry X hard nezotavitelna po retry

2. Definujte termín mean time to failure.

   • MTTF - prumerne mnozstvi casu nez nastane dalsi chyba

3. Definujte termín mean time to repair.

   • MTTR - prumerne mnozstvi casu nutne na zotaveni

4. Uvedte, jak lze vycíslit dostupnost systému na základe mean time to failure a mean time to repair.

   • MTTF/(MTTF+MTTR)

Modely

Questions

1. Vysvětlete vlastnost atomicity ACID transakcí.

   • Transakce proběhne celá, nebo vůbec.

2. Vysvětlete vlastnost consistency ACID transakcí.

   • Při provádění transakcí se DB převádí z jednoho konzistentního stavu do jiného.

3. Vysvětlete vlastnost isolation ACID transakcí.

   • Transakce o sobe navzájem nevědí, jako by běžela jen jedna.

4. Vysvětlete vlastnost durability ACID transakcí.

   • Změny commitnuté transakce jsou trvalé.

5. Vysvětlete omezení transakčního modelu flat transactions, která mohou bránit jeho praktickému využití v některých transakčních systémech.

   • Mají příliš velký rozsah. Abortu po stotisící operaci se nedá nijak zabránit. To se dá přičíst tomu, že nemají žádnou vnitřní strukturu.

   • Žádný dílčí neúspěch není tolerován. Pokud je špatně jediné číslo konta u deseti tisíc zaměstnanců nějakého podniku, pak transakce odeslání mezd všem zaměstnancům kvůli této chybě abortuje.

   • Flat transakce nemohou spolupracovat s jinými transakcemi. Nemohou s nimi sdílet data (pro sdílení dat neexistují žádná primitiva nebo pravidla), nemohou být vzájemně propojeny přes signifikantní události.

   • Neřeší přirozený problém vnoření do sebe. Běžné programovací jazyky umožňují vnořovat volání procedur, take se může stát, že zavoláme v transakci proceduru, která zahájí novou vnořenou transakci.

6. Vysvětlete omezení transakčního modelu spheres of control, která mohou bránit jeho praktickému využití v některých transakčních systémech. (otázka vyřazena z požadavků)

   • Zavislosti mohou byt velmi slozite

   • neni dobre formalizovano

   • tezke na implementaci

7. Popište funkci transakčního modelu transactions with savepoints vcetne semantiky significant events.

   • savepointy jsou body, ke kterym se da rollbackovat (nerika se tomu rollback ale undo)-> nemusi se zrusit cela transakce, kdyz se nepovede 100. operace (jestli jde o rollback nebo undo, na tom v podstatě nezáleží, třeba v Oracle se tomu říká rollback - viz dokumentace)

   • první SP obvykle po begin

   • significant events - defaultni {begin, commit, abort} + rozsirene {Savepoint(bod), Rollback(bod)}

8. Vysvětlete, s jakými problémy by byla spojena možnost uložit a obnovit savepoint v různých úrovních vnoření procedur volaných v rámci téže transakce.

   • muze nastat dopredny rollback (??) tzn. rollback k již rollbackovaným stavům. Musely by se pamatovat všechny částečné rollbacky (byly by součástí historie. To je ale i problém bez vnořování.

   • Musíme si pamatovat i <b>kontext</b> vytvoření SP. A ten po rollbacku též obnovit. Při rollbacku z vnořených procedur vlastně simulujeme <i>longjmp</i>

9. Vysvětlete, s jakými problémy by byla spojena možnost obnovit savepoint po restartu systému.

   • ztrata atomicity - napriklad uroky na vsech uctech by nebyly provedeny "najednou" (a to by záznamy SP musely být persistentní)<i>(neni to nahodou naopak? Podle me je problem v tom, ze pri persistentnim savepointu nezmizi uroky prictene pred padem systemu -> jsou prictene treba o nekolik hodin drive nez tem, kterym se prictou az pri dokonceni transakce po opetnem nahozeni systemu.) - to je ale jinými slovy totéž (problém je s tím "najednou"), ne?</i>

   • schopnost obnovení konextu výpočtu (proměnné, struktury, ...) "uprostřed" (osobně si to představuji jako probuzení systému z hybernace)

10. Vysvětlete, s jakými problémy by byla spojena možnost obnovit později uložený savepoint po obnovení dříve uloženého savepointu.

    • bylo by treba ukladat celou historii vsech rollbacku, aby se mohl provadet dopredny rollback, ktery anuluje nejaky jiz probehly rollback (ten uz pak v historii neni)

11. Popište funkci transakčního modelu chained transactions vcetne semantiky significant events.

    • "Atomické" {commit,begin} (rika se tomu chain), zachovává se kontext, rollbackuje se jen poslední transakce (porusuje to atomicitu !).

    • new significant events - chain = {commit, begin}

12. Popište funkci transakčního modelu nested transactions vcetne semantiky significant events. Vysvětlete, jak a proč jsou v tomto modelu závislé transakce a jak a proč se v tomto modelu nakládá s prostředky přidělenými transakcím při jejich ukončení.

    • Rodič je commit-dependent na synovi - nemůže commitovat dřív než on.

    • Potomek je abort-dependent na rodiči - pokud abortuje ten, abortuje se i potomek (I commitnutý! Tj. porušení durability.).

    • Zámky potomka se při jeho commitu předávají rodiči, při abortu se nově vytvořené zruší. Potomek dědí zámky rodiče a vidí na jeho rozpracovaná data (tj. porušení izolace).

    • siginificant events - ve slidech zadny navic nejsou, tak bych to videl na klasiku {begin, commit, abort} (events jsou stejne, otazka byla na semantiku - coz je imho to vyse popsane ze rodic pri commitu musi pockat na commit vsech synu...)

13. Uveďte, v čem je použití modelu nested transactions lepší než použití modelu transactions with savepoints s uložením savepointu namísto volání begin vnořené transakce a obnovením savepointu namísto volání abort vnořené transakce.

    • paralelni podtransakce

    • rozdil v zamcich: rodic rozhoduje jake zamky da detem, a ty po commitu predaji zamky rodeici

14. Popište funkci kompenzujících transakcí. Vysvětlete, jak a proč se u těchto transakcí omezují možné způsoby jejího ukončení.

    • abort rodicovske transakce zpusobi vyvolani kompenzujici transakce (kdyz nemuzou byt dokonceny vsechny podtransakce nebude dokoncena zadna)

    • kompenzujici transakce musi vzdy provest commit (kdyby provedla abort, znamenalo by to, ze se nepovedl abort puvodni transakce, a to se nesmi stat)

15. Popište funkci transakčního modelu split and join transactions vcetne semantiky significant events.

    • dalsi dve operace split (rozdeleni jedne transakce do dvou) a join (spojeni dvou transakci o jedne)

    • data se deleguji nove vzniklym transakcim

    • u joinu: nova transakce zdedi vsechna data

    • u splitu dve moznosti:

      1. seriovy (serial) split, kde t_a musi provest commit drive nez t_b - obe transakce dostanou vsechna data

      2. nezavisly (independent) split, kde mohou t_a a t_b provest commit nezavisle na sobe, data si rozdeli

    • significant events - {begin, abort, commit} + split + join

Serializovatelnost

Questions

#Vysvětlete jev dirty read a napište příklad transakční historie, kde k němu došlo.

• Transakce čte nějaký mezivýsledek.

• Transakci je povolené číst data z dat, která byla modifikována jinou transakcí, která ještě není commit

• http://en.wikipedia.org/wiki/Isolation_(database_systems)#Dirty_reads

• w2[x], r1[x], w2[x]

#Vysvětlete jev unrepeatable read a napište příklad transakční historie, kde k němu došlo.

• Opakované čtení vrátí jinou hodnotu.

• r1[x], w2[x], r1[x]

#Vysvětlete jev lost update a napište příklad transakční historie, kde k němu došlo. #*Aktualizovaná hodnota je přepsána výpočtem založeným na předchozí (neaktualizované) hodnotě.

#*r1[x], w2[x], w1[x] #Vysvětlete, kdy je vlastnost transakční historie prefix commit closed.

#*Vlastnost je prefix commit closed, jestliže je splněna v historii H, je také splněna v historii C(H') (tj. commitovaná projekce - historie, která obsahuje jen operace commitovaných transakcí. H obsahuje commitované, abortované i běžící transakce.) pro libovolný prefix H' historie H.

Exercises

#Rozeberte účel definice serializovatelných historií pomocí ekvivalence se seriovými historiemi. Ve světle tohoto účelu vysvětlete použití conflict equivalence a view equivalence u one version a multiversion transakcí. Vysvětlení účelu doplňte o zvážení, zda jsou serializovatelné historie jedinou třídou historií, která mu vyhovuje.

• Seriova historie je korektni (transakce se provedou jedna po druhe, nikdo neuvidi zadne castecne vysledky), ale neefektivni

• Seriová historie

  • Úplná (uspořádání transakcí, zachováním uspořádáním operací v transakcích a seřazeni konfliktních operací napříč transkcemi)

  • Operace různých transakcí nejsou promíchány

• Serializovtelná == když její commitovaná projekce je konfliktove ekvivalentni s nejakou seriovou (konfliktova ekvivalence = stejne poradi (neabortujicich) konfliktnich operaci) historií

• <i>one version</i> pohledova ekvivalence historií:

  • pokud T₁ cetla data zapsana T₂, pak to dela i v druhem rozvrhu (čtení stejné verze dat)

  • mají stejné poslední zápisy (tj. pokud v jedné je poslední w_i[x] pro i=k, je v druhé též polední)

• <i>multi-version</i> pohledova ekvivalence historií:

  • Každý zápis je vlastně poslední

  • Čtení stejné verze dat není problém, <i>read</i> specifikuje verzi, jakou chce

  • Takže <i>multi-version</i> historie jsou ekvivalentní, pokud obsahují stejné operace

Rozdíl je tedy ten, že u <i>one version</i> máme jednu verzi, kterou si vzájemně mění konfliktní operace. Proto je ta hodnota jednoznačně určená jejich pořadím. Konfliktová ekvivalence nestačí. r3 čte různé verze x

H1 = w1[x1]c1 w2[x2]c2 r3[x1]w3[y3]c3 H2 = w1[x] c1 w2[x] c2 r3[x] w3[y] c3

<b>Účel serializovatelné historie</b>

Právě proto, že seriová historie je korektní ale neefektívni, hledáme historie, které jsou ekvivalentní nejaké sériové historii, co do výsledku ale ne postupu provádení.

Zachováme izolovanost, ale zvýšíme paralelismus. To lze zlepšit <i>multi-version</i> historií, protože nová verze datové položky vytvoří jen novou verzi, ale nepřepíše starou. Navíc kopie se stejně hodí uchovat kvuli logu.

"Vysvětlení účelu doplňte o zvážení, zda jsou serializovatelné historie jedinou třídou historií, která mu vyhovuje."

Existuji i dalsi historie STRICT, AVOID CASCADING ABORTS, RECOVERABLE, ale ty uz nejsou serializovatelne ani nemaji serializovatelne jako podmnozinu. Viz slide 05-18

One version

Questions

#Definujte formálně pojem transakce a kompletní transakční historie pro potřeby další klasifikace transakčních historií z hlediska izolovanosti jednotlivých transakcí. Předpokládejte existenci jediné verze dat. #*Transakce -- množina <math>T_i</math> částečně uspořádaná relací <math><_i</math>, kde

#**<math>T_i \subseteq \{r_i[x], w_i[x]; </math> x je datová položka<math>\} \cup \{a_i, c_i\}</math> #**<math>a_i \in T_i \oplus c_i \in T_i</math>, kde <math>\oplus</math> je xor -- buď commituje nebo abortuje

#**<math>q \in \{c_i, a_i\}, q \in T_i \Rightarrow \forall p \in T_i: p <_i q</math> -- commit nebo abort je na konci #**<math>r_i[x], w_i[x] \in T_i \Rightarrow r_i[x] <_i w_i[x] \lor w_i[x] <_i r_i[x]</math> -- operace na stejných datech jsou uspořádané

#*Kompletní historie -- množina H s částečným uspořádáním <math><_H</math>, kde <math>H = \bigcup_{i=1}^{n} T_i</math>, <math><_H</math> je nadmnožinou sjednocení <math><_i</math> a pro každé konfliktní <math>p,q \in H</math>platí<math>p <_H q \lor q <_H p</math>. Historie je prefix kompletní historie. #Definujte, nejlépe formálně, pojem sériové one version transakční historie.

• Pro každé <math>T_i, T_j</math> platí, že všechny operace z <math>T_i</math> jsou před operacemi z <math>T_j</math> nebo naopak.

#Definujte, nejlépe formálně, pojem zotavitelné (jinak také RC) one version transakční historie.

• H je zotavitelná , jestliže platí: kdykoli <math>T_i</math> čte z <math>T_j, (i \neq j)</math> a <math>c_i \in H</math>, potom <math>c_j <c_i</math>.

• <math>T_i</math> musí počkat, jestli se přečtená hodnota nezruší abortem <math>a_j</math>.

#Definujte, nejlépe formálně, pojem one version transakční historie, která předchází kaskádovým abortům (jinak také ACA).

• H předchází kaskádovým abortům, jestliže platí: kdykoli <math>T_i</math> čte <math>x \in T_j</math>, potom <math>c_j <r_i[x]</math>.

• <math>T_i</math> čte až potvrzený výsledek.

#Definujte, nejlépe formálně, pojem striktní (jinak také ST) one version transakční historie.

• H je striktní, jestliže platí: kdykoli <math>w_j[x] <o_i[x] (i \neq j)</math>, pak <math>a_j <o_i[x]</math> nebo <math>c_j <o_i[x]</math>.

• čte nebo přepisuje se až transakce, která tam psala předtím, skončí.

#Definujte formálně relaci conflict equivalence na one version transakčních historiích.

• H a H' jsou konfliktově ekvivalentní, pokud mají stejné:

#**transakce, #**operace

#**pořadí konfliktních operací, která neabortují #Definujte formálně relaci view equivalence na one version transakčních historiích.

• H a H' jsou pohledově ekvivalentní, jestliže jsou nad stejnou množinou transakcí, mají stejné operace a platí:

  • pro každé <math>T_i, T_j</math> takové, že <math>a_i, a_j</math> nejsou v H a pro každé x platí: jestliže <math>T_i</math> čte <math>x \in T_j</math> v H, potom <math>T_i</math> čte <math>x \in T_j</math> v H'

  • pro každé x platí: jestliže w[x] je finální zápis x v H, potom je to finální zápis x i v H'

#Definujte, nejlépe formálně, pojem serializovatelné (jinak také izolované či SR) one version transakční historie za pomoci relace conflict equivalence.

• Historie H je (konfliktově) serializovatelná, jestliže C(H) je konfliktově ekvivalentní nějaké sériové historii.

#Definujte, nejlépe formálně, pojem serializovatelné (jinak také izolované či SR) one version transakční historie za pomoci relace view equivalence.

• Historie H je (pohledově) serializovatelná, jestliže pro její libovolný prefix H' je C(H') pohledově ekvivalentní nějaké sériové historii.

#Definujte formálně serializační graf one version transakční historie a vysvětlete vztah mezi vlastnostmi tohoto grafu a serializovatelností (jinak také izolovaností či SR) transakční historie.

• Serializační graf SG(H) historie H nad <math>T = {T_1, ..., T_n}</math> je orientovaný graf, jehož vrcholy jsou transakce z C(H) a z <math>T_i</math> vede hrana do <math>T_j</math>, právě když nějaká operace z <math>T_i</math> je v konfliktu s nějakou operací v <math>T_j</math> a předchází ji.

• Historie je serializovatelná, právě když tento graf neobsahuje cyklus.

• Transitivita není podstatná.

#Napište příklad sériové one version transakční historie.

• r1[x], w1[x], r2[x], w2[y], w2[x]

#Napište příklad zotavitelné (jinak také RC) one version transakční historie, která nepředchází kaskádovým abortům (jinak také ACA). Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude zotavitelná, ale zůstane serializovatelná (jinak také izolovaná či SR).

• r1[x], w1[x], r2[x], w2[x], r3[x], w3[z], c1, c2, c3

• nejaka transakce commituje driv, nez ta jejiz data cetla -> stacilo by prehodit c1<->c2 ?

• Nebo možná:

  • r1[x], w2[x], r3[x], c2, c3, c1 - je RC (c2<c3), není ACA (c2>r3[x])

  • r1[x], w1[x], w2[x], r3[x], c2, c3, c1 - není RC (c1>c2)

#Napište příklad one version transakční historie, která předchází kaskádovým abortům (jinak také ACA) a není striktní (jinak také ST). Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude předcházet kaskádovým abortům, ale zůstane zotavitelná (jinak také RC).

• r1[x], w1[x], c1, r2[x], w2[x], c2, r3[x], w3[z], c3

• pridat za w2[x] r1[y] ? (a vsechny commity dat nakonec v poradi c1, c2, c3 )

• Nebo možná:

  • w1[x], w2[x], c1, c2 - je ACA (nic nečtu), není ST (w2[x]<c1)

  • w1[x], r2[x], w2[x], c1, c2 - není ACA (r2[x]<c1)

#Napište příklad serializovatelné (jinak také izolované či SR) one version transakční historie, která není sériová. Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude serializovatelná.

• r1[x], r2[y], w1[x], w2[y], r2[x], w2[x]

• r1[x], r2[y], r2[x], w1[x], w2[y], r2[x], w2[x] - dík přidání r2[x] T2<T1, ale dík w2[x] nakonci T1<T2

#Napište příklad striktní (jinak také ST) one version transakční historie, která není sériová. Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude striktní, ale bude předcházet kaskádovým abortům (jinak také ACA).

• r2[y], w1[x], c1, w2[x], w2[y], c2 - je ST, není seriová

• w1[x], r2[y], w1[y], c1, w2[x], c2 - je ST, není SR

• r2[y], w1[x], w2[x], c1, w2[x], w2[y], c2 - není ST, je ACA

• w1[x], r2[y], w1[y], w2[y], c1, w2[x], c2 - není ST, je ACA

Multiversion

Questions

#Definujte formálně pojem transakce a kompletní transakční historie pro potřeby další klasifikace transakčních historií z hlediska izolovanosti jednotlivých transakcí. Předpokládejte existenci více verzí dat.

• MV Transakce je částečně uspořádaná množina (multi-množina?) operací <math>r_i[x_j]</math>, <math>w_i[x_i]</math>, (<math>x_i</math> je datová položka verze i) a právě jedné z <math>a_i</math> nebo <math>c_i</math> (maximální prvky). Zápis vždy vytváří novou verzi <math>w_i[x_i]</math>. Čtení vždy určuje, kterou verzi chce číst <math>r_i[x_j]</math>.

• MV Kompletní historie

  • každé <math>r_i[x_j]</math> předchází <math>w_j[x_j]</math> (čtu existující verze)

  • každé <math>r_i[x]</math> po <math>w_i[x_i]</math> je <math>r_i[x_i]</math> (preferuje svoje zápisy).

  • každé <math>c_i</math> po <math>r_i[x_j]</math> předchází <math>c_j</math> (zotavitelnost - nutná pro zajištění, že i <math>C(H)</math> je MV Kompletní historie).

#Definujte, nejlépe formálně, pojem sériové multiversion transakční historie.

• stejně jako one version (historie je úplná a operace různých transakcí nejsou pomíchány)

#Definujte, nejlépe formálně, pojem one copy sériové multiversion transakční historie.

• One copy sériová multiversion transakční histore je taková sériová multiversion historie, pro kterou platí: pro každé i, j, x: pokud <math>T_i</math> čte x z <math>T_j</math>, potom je buď <math>i = j</math>, nebo <math>T_j</math> je poslední transakce před <math>T_i</math>, která zapsala verzi x.

• One copy sériová historie je pohledově ekvivalentní nějaké sériové one version historii.

#Definujte formálně relaci view equivalence na multiversion transakčních historiích.

• Multi version historie jsou pohledově ekvivalentní, pokud mají stejné operace a čtou stejnou verzi dat.

#Definujte, nejlépe formálně, pojem serializovatelné (jinak také izolované či 1SR) multiversion transakční historie za pomoci relace view equivalence.

• Multi version historie je one-serializovatelná, pokud <math>C(H)</math> je pohledově ekvivalentní nějaké one copy sériové historii.

#Definujte formálně rozšířený serializační graf multiversion transakční historie a vysvětlete vztah mezi vlastnostmi tohoto grafu a serializovatelností (jinak také izolovaností či 1SR) transakční historie.

• Multi version serializační graf: vrcholy představují transakce, hrany určují pořadí konfliktních operací (<math>w_i[x_i] <r_j[x_i]</math>)

• Rozšíření: pro každou dvojici <math>w_i[x_i]</math>, <math>r_k[x_j]</math> přidej

  • <math>T_i</math> -> <math>T_j</math>, pokud <math>i <j</math> (čtu verzi zapsanou po <math>w_i[x_i]</math>)

  • <math>T_k</math> -> <math>T_i</math>, pokud <math>j <i</math> (čtu verzi zapsanou před <math>w_i[x_i]</math>)

• Multi version historie je one-serializovatelná, právě když rozšířený multi version serializační graf je acyklický

#Napište příklad one copy sériové multiversion transakční historie. Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude one copy sériová, ale zůstane sériová.

• w1[x1], r2[x1], w2[x2]

• w1[x1], r2[x1], w2[x2], r3[x1]

#Napište příklad serializovatelné (jinak také izolované či 1SR) multiversion transakční historie, která není one copy sériová. Ukažte příklad jedné operace, jejíž doplnění do historie způsobí, že ta již nebude serializovatelná.

• w1[x1], r2[x1], r1[z1], w2[x2]

• w1[x1], r2[x1], r1[z1], w2[x2], w1[x2]

Plánovače

Questions

1. Uveďte možnosti, které má plánovač operací k dispozici pro zajištění izolovanosti transakcí. Vysvětlete, jak se ve využití těchto možností liší agresivní a konzervativní plánovače.

   • možnosti zajištění izolovanosti: provést operaci hned, odmítnout, pozdržet

   • Agresivní plánovač -- snaha vykonat operace co nejrychleji => snaha plánovat okamžite => občas musí odmítat.Zbavuje se možnosti preuspořádat operace. Vhodný na hodně malých transakcí.

   • Konzervativní plánovač -- snaha předcházet odmítání => zpožďuje. Vhodný na méně komplikovaných transakcí.

Zamykání

Questions

1. Definujte, nejlépe formálně, pojem dobře formované transakce.

   • pokud jsou všechny akce pokryté prislušnými zámky, popřípade pokud je dodržané správne párování operací LOCK a UNLOCK

2. Definujte, nejlépe formálně, pojem dvoufázové transakce.

   • všechny operace LOCK předcházejí všem operacím UNLOCK - pote co zacala odemykat uz nic nezamyka

3. Definujte, nejlépe formálně, pojem legální transakční historie.

   • Dobře formovaná

   • Historie popisujicí proveditelný postup zamykání (bez konfliktů vzhledem k tabulce kolizí zámku)

4. Vysvětlete, proč a jak lze dvoufázové zamykání použít k vytváření serializovatelných (jinak také SR) one version transakčních historií. Zaměřte se na zdůvodnění serializovatelnosti vytvářených historií.

   • pokud jsou vsechny transakce dvoufazove, dobre formovane a historie je legalni, potom je historie serializovatelna (locking theorem)

   • myslenka dukazu: oznacime S(T) index prvniho unlocku transakce T. Plati: T' zavisi na T -> S(T)<S(T'). Predpokladejme pro spor, ze veta neplati pro historii H. Tedy je v H cyklus zavislosti. Z toho ale plyne S(T)<S(T')<S(T)...<S(T) =spor

5. Vysvětlete, proč a jak lze dvoufázové zamykání použít k vytváření striktních (jinak také ST) one version transakčních historií. Zaměřte se na zdůvodnění striktnosti vytvářených historií.

   • Striktni historie vzniknou, kdyz uvolnovani zamku se dela po commitu/abortu transakce, ktera je drzela -- nic nectou nebo neprepisuji dokud ne commitovala transakce, ktera tam psala pretim (snad zrejme)

6. Vysvětlete vliv granularity zamykaných položek na funkci plánovače operací, který izoluje transakce pomocí dvoufázového zamykání.

#*Velká - hodně s čeká, až seriový běh #*Malá - vetší pravděpodobnost deadlocku, velký overhead

1. Popište algoritmus plánovače operací, který izoluje one version transakce pomocí dvoufázového zamykání. Popis formulujte jako proceduru, která při každém volání očekává požadavek transakce na vykonání operace jako svůj vstup a vrací rozhodnutí plánovače jako svůj výstup.

#*Zámek nelze uvolnit, dokud DM nepotvrdil zpracování operace kterou chránil. #*Zamykání je navíc dvoufaázové

#*schedule(p_i[x]) #**if(pl_i[x] conflits with ql_j[x])

#***delay p_i[x] /*T_i spí dokud nelze získat zámek*/ #**set lock pl_i[x]

#**send to DM p_i[x]

1. Popište algoritmus plánovače operací, který izoluje multiversion transakce pomocí dvoufázového zamykání. Popis formulujte jako proceduru, která při každém volání očekává požadavek transakce na vykonání operace jako svůj vstup a vrací rozhodnutí plánovače jako svůj výstup.

• Konverze zámku w-lock na c-lock může způsobit deadlock

• schedule(p_i[x])

  • case p_i[x]

::***w_i[x] ::****attempts to set wl_i[x]

::****set lock ::****schedule w_i[x_i]

::***r_i[x] ::****attempts to set rl_i[x]

::****set lock ::****if(T_i has already wl_i[x])

::*****schedule r_i[x_i] ::****else schedule r_i[x_j], where x_j last committed

::***c_i ::****all wl_i[x] converts to cl_i[x] způsobí odložení commitu dokud nejsou uvolněny všechny rl[x] (cl je certify lock) */

Questions 2

1. Definujte pravidla pro zamykání používaná transakcemi na stupni izolace 0 (bez ekvivalentu v SQL) a uveďte, jakým způsobem může taková transakce porušit vlastnost isolation.

   • Dobře formovaná pro zápis.

2. Definujte pravidla pro zamykání používaná transakcemi na stupni izolace 1 (přibližně ekvivalentní read uncommited v SQL) a uveďte, jakým způsobem může taková transakce porušit vlastnost isolation.

   • Dobře formovaná a 2PL pro zápis.

3. Definujte pravidla pro zamykání používaná transakcemi na stupni izolace 2 (přibližně ekvivalentní read committed v SQL) a uveďte, jakým způsobemmůže taková transakce porušit vlastnost isolation.

   • Dobře formovaná a 2PL pro zápis. Dobře formovaná pro čtení

4. Definujte pravidla pro zamykání používaná transakcemi na stupni izolace 3 (přibližně ekvivalentní repeatable read a serializable v SQL).

   • Dobře formovaná a 2PL pro zápis. Dobře formovaná a 2PL pro čtení

5. Napište příklad transakční historie, ve které transakce na stupni izolace 1 (přibližně ekvivalentní read uncommitted v SQL) porušuje vlastnost isolation ve spolupráci s jinou, plně izolovanou transakcí.

6. Napište příklad transakční historie, ve které transakce na stupni izolace 2 (přibližně ekvivalentní read committed v SQL) porušuje vlastnost isolation ve spolupráci s jinou, plně izolovanou transakcí.

7. Popište algoritmus operací uzamknutí a odemknutí vybraného uzlu stromové hierarchie pro hierarchické zamykání s použitím zámků v režimech R,W, IR a IW.

   • Uspořádání zámků IS<{IX,S}<{SIX,U}<X

#*Zamčení #**Cestu od kořene k rodiči zamknout Intention zámkem

#**Uzel pak příslušným Shared/eXclusive zámkem #*Odmčení

#**Od uzlu ke kořeni

1. Popište algoritmus operací uzamknutí a odemknutí vybraného uzlu obecné acyklické hierarchie pro hierarchické zamykání s použitím zámků v režimech R, W, IR a IW.

#*Jako u stromu, ale pro zamčení uzlu Shared potřebuji alespoň jednoho jeho rodiče IS, pro zamčení uzlu eXclusive potřebuji všechny jeho rodiče IX

1. Nakreslete kolizní tabulku pro hierarchické zámky v režimech R, W, IR a IW.

Questions 3

1. Vysvětlete termín phantom.

   • Pokud chci pracovat s nějakou množinou položek určenou predikátem vybírám (resp. mažu ji), co zamknout? Jedná se o problém dynamicky se měnící databáze. Sice zamknu položky co jsem vybral, ale může se změnit množina odpovídající predikátu. Potřebujeme zamknout celou databázi? Ne, stačilo by "zamknout predikát".

   • jinak zo T.Skopalových slajdov:

#**nyní uvažujme dynamickou databázi, tj. do databáze lze vkládat a z databáze mazat (tj. ne pouze číst a aktualizovat stávající data) #**pokud jedna transakce pracuje s množinou entit a druhá tuto množinu LOGICKY mění (přidává nebo odebírá), může to mít za následek nekonzistenci databáze (neuspořádatelný rozvrh)

#***proč: T1 uzamkne všechny entity, které v dané chvíli odpovídají jisté vlastnosti (např. podmínce WHERE příkazu SELECT) #***T2 v průběhu zpracování T1 může tuto množinu LOGICKY rozšířit (tj. v této chvíli by množina zámků definovaná podmínkou WHERE byla větší), což má za následek, že některé nově přidané entity budou uzamknuté (a tudíž i zpracované), kdežto jiné ne

#**platí i pro striktní 2PL

1. Vysvětlete termín read past locking.

   • Přeskočí sepoložky zamčené pro zápis (resp. dirty data ze stupně isolace 0, 1). Pro statistiky nevadí, dirty data mohou být výrazně horší.

2. Vysvětlete termín predicate locking.

   • Uzamknou se záznamy asociované s výběrovým predikátem

   • dva pred. zámky jsou konfliktní, když se navzájem nevylučují

3. Vysvětlete termín key range locking.

   • zamykání, které pro každý prvek databáze X před Y umí udělat zámek na rozsah klíčů [X,Y), který se dynamicky mění v závislosti na prováděných operacích na tomto rozsahu

4. Vysvětlete termín previous or next key range locking.

   • Key Range Locking, které pro posloupnost položek X, Y, Z a zámek na Y implikuje zámek na [Y,Z) (previous locking) nebo (X, Y] (next locking)

5. Na příkladu transakční historie vysvětlete důvod zavedení update zámků a nakreslete kolizní tabulku pro zámky v režimech R, W a U.

#*Pokud transakce čte x, aby jej mohla potom zapsat změněné (update), může chtít rlock a ten později chce povýšit na wlock. Pokud ale totéž udělají dvě transakce, vznikne dead-lock #*Řešením je ulock (ten dostane max. jedna transakce a navíc jen pokud ještě nikdo nemá wlock, po zamknutí ulock už není možné zamknout pro čtení)

#*rl₁[x], rl₂[x], r₁[x], r₂[x], upg_wl₁[x], upg_wl₂[x], w₁[x], w₂[x], ...

Questions 4

1. Popište detekci deadlocku pomocí timeouts a uveďte její přednosti a nedostatky.

   • Časový limit na obržení zámku. time expired->abort

     • - Nebezpečí live lock (protože cyklus čekání nebyl přerušen)

     • - Tricky tuning of the timeout parameter.

     • - Unnecessary aborts cannot be avoided.

     • + Je to jednoduché a stejně pokud se moc blokuje/čeká, tak něco není vpořádku

2. Popište detekci deadlocku pomocí wait for grafu a uveďte její přednosti a nedostatky.

   • + Přeruší cyklus čekání hned jak vznikne

   • + Path pushing

   • - Velká režije

   • - U path pushing nebezpečí phantom locks

3. Uveďte, proč a jak se vybírá cíl volání abort pro přerušení deadlocku.

   • Nejmenší škoda (např. nejkratší log)

   • Wait-die

   • Wound-wait

4. Vysvětlete, jak lze spravovat zámky používané pro izolování transakcí tak, aby jejich existence nepředstavovala nadměrnou časovou a paměťovou režii, kterou by mělo přímočaré ukládání zámků spolu s daty, ke kterým se vztahují.

   • V paměti jen co je zamčeno a hashovat (kolize nevadí)

   • Dynamická granularita zamykání

Exercises

1. Popište funkci plánovače založeného na dvoufázovém zamykání nad one version transakcemi a na vhodně zvoleném příkladu ukažte, jak varianty tohoto plánovače produkují serializovatelné historie a striktní historie. Na příkladu ukažte, jak může vzniknout deadlock a jak plánovač pokračuje po abortu některé z transakcí, které se ho účastní. Příklady uveďte včetně zvolených operací jednotlivých transakcí astavů zámků.

2. Popište funkci plánovače založeného na dvoufázovém zamykání nad multiversion transakcemi a na vhodně zvoleném příkladu ukažte, jak varianty tohoto plánovače produkují serializovatelné (jinak také 1SR)historie. Na příkladu ukažte, jak může vzniknout deadlock a jak plánovač pokračuje po abortu některé z transakcí, které se ho účastní. Příklady uveďte včetně zvolených operací jednotlivých transakcí a stavů zámků.

   • Multiversion planovac zalozeny na 2PL pouziva prave dve verze historie. Jedna je "rozdelana", jedna je commitla - pro cteni.

   • Pouzivaji se 3 typy zamku - R, W a C(ertified), pricemz R a W spolu nekoliduji, ale C koliduje se vsim. Pri commitu se transakce pokusi upgradovat vsechny W na C.

   • Priklad historie: RL1(X), R1(X), RL2(Y), R2(Y), WL1(Y), W1(Y), C1 - ceka, az bude moct upgradovat WL(Y) na CL(Y) (tj. az 2. txce pusti RL(Y)), WL2(X), C2 - pokusi se upgradovat WL(X) na CL(X), takze ceka #* na 1, az ji pustu RL(X). Obe txce na sebe ted cekaji v kruhu ... tj. mame tu deadlock. Reseni je jedine - abortovat jednu z txci.

   • (prevzato z fora)

Časová razítka

Questions

1. Vysvětlete, proč a jak lze časová razítka použít k vytváření serializovatelných (jinak také SR) one version transakčních historií. Zaměřte se na zdůvodnění serializovatelnosti vytvářených historií.

   • DM vykonává konfliktní operace v pořadí určeném timestampy (tj. v historii je <math>r_i[x], ..., w_j[x]</math> právě když <math>ts(T_i) <ts(T_j)</math>)

#*Pokud máme cyklus v serializačním grafu tak potom <math>ts(T) <ts(T') < .. < ts(T)</math> SPOR)

1. Popište algoritmus plánovače operací, který izoluje one version transakce pomocí časových razítek. Popis formulujte jako proceduru, která při každém volání očekává požadavek transakce na vykonání operace jako svůj vstup a vrací rozhodnutí plánovače jako svůj výstup.

   • Pokud si vedeme seznam <math>[operace, dataItem]</math> = max naplánovaná timestamp, odmítáme <math>p_i</math> nad dataItem, pokud <math>ts(p_i) <[operace, dataItem]</math>

   • V opačném případě může dojít ke změně hodnoty

2. Popište algoritmus plánovače operací, který izoluje multiversion transakce pomocí časových razítek. Popis formulujte jako proceduru, která při každém volání očekává požadavek transakce na vykonání operace jako svůj vstup a vrací rozhodnutí plánovače jako svůj výstup.

#*Pro zotavitelnost, c_i se pozdrží dokud c_j pro všechny T_j, jejichž verze četla T_i #*schedule(p_i[x])

#::if (p == r_i[x]) #:::p = r_i[x_j] where j is the largest available timestamp for x that is smaller than or equal to i

#::else /*p == w_i[x]*/ #:::if (occurred r_j[x_k] && (ts(T_k) <ts(T<sub>i<ts(T<sub>j

#::::reject #:::else

#::::p = w_i[x_i] #::::accept

1. Vysvětlete, jak lze spravovat časová razítka používaná pro izolování transakcí tak, aby jejich existence nepředstavovala nadměrnou časovou a paměťovou režii, kterou by mělo přímočaré ukládání časových razítek spolu s daty, ke kterým se vztahují.

#*Stačí si u datových položek pamatovat, kdo je naposledy četl? Viz 3. otázka, write větev, zabraňující přepsání starší verze položky, se kterou pracuje (četla ji) transakce mladší.

Exercises

1. Popište funkci plánovače založeného na časových razítcích nad one version transakcemi a na vhodně zvoleném příkladu ukažte, jak tento plánovač produkuje serializovatelné historie. Na příkladu ukažte, jak při opakovaném abortu některých transakcí může vzniknout livelock . Příklady uveďte včetně zvolených operací jednotlivých transakcí a hodnot časových razítek.

2. Popište funkci plánovače založeného na časových razítcích nad multiversion transakcemi a na vhodně zvoleném příkladu ukažte, jak tento plánovač produkuje serializovatelné (jinak také 1SR) historie. Napříkladu ukažte, jak při opakovaném abortu některých transakcímůže vzniknout livelock . Příklady uveďte včetně zvolených operací jednotlivých transakcí a hodnot časových razítek.

   • Livelock = neustale se abortujici transakce. Ke kolizi dojde, pokud se transakce snazi zapsat data, jejich starsi verzi uz cetla mladsi transakce. Napr. mam X verze 5, ktere cetla transakce 7. Transakce #* 6 tim padem nemuze X zapsat (protoze by psala 6. verzi) a tak je abortovana.

   • Jednoduchy priklad - mam polozku X, kterou skoro vsichni ctou, ale jen transakce T ji zapisuje. Transakce T navic bezi dlouho (aby spocitala X) a X zapisuje az na konci.

   • Takze se T rozebehne a zacne pocitat. Mezitim se objevi spousta mladsich transakci, ktere si prectou X. Na konci se T pokusi zapsat X, coz se ji nepovede (protoze uz ho cetli mladsi transakce), tak se # #* abortuje a zkusi to znova. Pokud se ctenari objevuji dostatecne casto, tak se T nikdy nepodari zapsat X.

   • (prevzato z fora)

Serializační graf

Questions

1. Vysvětlete, proč a jak lze testování serializačního grafu použít k vytváření serializovatelných (jinak také SR) one version transakčních historií. Zaměřte se na zdůvodnění serializovatelnosti vytvářených historií.

2. Popište algoritmus plánovače operací, který izoluje one version transakce pomocí testování serializačního grafu. Popis formulujte jako proceduru, která při každém volání očekává požadavek transakce navykonání operace jako svůj vstup a vrací rozhodnutí plánovače jako svůj výstup.

   • schedule(p_i[x])

     • if(node T_i is not in SSG) add node T_i to SSG

     • foreach q_j conflits with p_i[x] do connect from::T_j to::T_i in SSG

     • if(cycle in SSG)

#:::abort T_i #:::delete and disconect T_i from SSG

#::else schedule p_i[x] /*(after DM acknowledges all scheduled conflicting operations)*/

1. Vysvětlete, kdy lze ze serializačního grafu používaného pro izolování transakcí odebírat uzly a hrany tak, aby jeho existence nepředstavovala nadměrnou paměťovou režii, kterou by mělo přímočaré ukládání všech uzlů a hran.

   • Informace o ukončené T_i může být smazána, když již T_i nemůže být nikdy v budoucnu zapojena do cyklu v SSG.

   • Pro skončené transakce T_i již nepřibývají vstupní hrany do T_i. Pokud už tedy do T_i žádná vstupní hrana nevede, nemůže ležet na kružnici a lze ji odstranit.

Exercises

1. Popište funkci plánovače založeného na testování serializačního grafu nad one version transakcemi a na vhodně zvoleném příkladu ukažte, jak tento plánovač produkuje serializovatelné historie. Na příkladu ukažte, jak při opakovaném abortu některých transakcí může vzniknout livelock. Příklady uveďte včetně zvolených operací jednotlivých transakcí a stavu serializačního grafu zahrnujícího i odebírání uzlů a hran.

#*live-lock opakované zabíjení T_i

• Co třeba toto:

  • T₁ = w₁[x], w₁[x], ..

  • T₂ = w₂[x], w₂[x], ..

  • w₁[x], w₂[x], w₁[x], a₁ cyklus abortuje se T₁

  • w₂[x], w₁[x], w₂[x], a₂ cyklus abortuje se T₂

  • a znovu w₁[x], w₂[x], w₁[x] ...

Commitment

Questions

1. Uveďte, jaké podmínky musí splňovat protokol pro atomické ukončení transakce.

#*Všechny procesy, které dospěly k rozhodnutí, rohodly stejně #*Rozhodnutí procesu je nezvratné

#*Rozhodnutí commit může být učiněno jen pokud s tím ostatní prcesy souhlasí (volily yes) #*Pokud nedošlo k chybě a všichni volily yes rozhodnutí bude commit (jinak vomit ;)

#*Pokud za běhu dojde jen k selháním, které je algoritmus schopen tolerovat, tak pokud se ze všech selhání zotaví a v dostatečně dlouhé době k dalším nedojde, tak by nakonec všechny procesy měly dospět k rozhodnutí. #:Copyright 1987 by Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman.

1. Popište algoritmus dvoufázového commit protokolu na úrovni obsahu a významu zpráv zasílaných účastníkům a záznamů ukládaných do logu. Soustřeďte se pouze na průběh protokolu bez výpadku účastníků.

   1. Přípravná fáze - koordinátor pošle všem zprávu prepare, účastníci závazně odpoví prepared nebo not prepared

   2. Commit - když jsou všichni připraveni, koordinátor přikáže commit, jinak abort

2. Popište algoritmus dvoufázového commit protokolu na úrovni obsahu a významu zpráv zasílaných účastníkům a záznamů ukládaných do logu. Soustřeďte se pouze na průběh protokolu po výpadku účastníka.

   • Po odeslání prvního potvrzení koordinátorem může transakce skončit už jedině commitem

     • Recovery protokol pro koordinátora - koukni se do logu a zjisti, kdy jsi skončil

     • Recovery protokol pro účastníka - mezi ohlášením schopnosti commitovat a commitem sám o sobě neví, jak má transakce dopadnout kvůli výpadku, a při zotavení se na to musí optat koordinátora.

3. Uveďte, jak lze upravit dvoufázový commit protokol, aby se oproti standardní verzi snížil počet zasílaných zpráv potřebných k rozhodnutí.

#*Standardní verze je stromově uspořádána (coordinátor-kořen, účastníci-potomci/listy) #*Lineární (resp. kruh)

#**Někdo začne, pošle prepare/commit #**Další se k tomu může přidat, pošle dál. Když už zpráva má potvrzení všech účastníků, postupně se commituje.

#**Když někdo chce abortovat, rozešle abort (třeba i na obě strany) #**Pomalejší – commit trvá 3N kroků

1. Uveďte, jak lze upravit dvoufázový commit protokol, aby se oproti standardní verzi snížila doba potřebná k rozhodnutí.

#*All-to-all (broadcast) #**Nejdřív se broadcastem pošle prepare.

#**Pak každý broadcastem odpoví stav a všichni vědí všechno. #**Celkem tedy 2 kroky (oproti 3 v původní variantě), pošle se víc zpráv.

Exercises

1. Popište funkci dvoufázového commit protokolu a na vhodně zvoleném příkladu ukažte commit a abort ukončení transakce bez a s výpadkem účastníků. Na příkladu ukažte, jak výpadek koordinátora může způsobit zablokování ostatních účastníků a vysvětlete, jak mohou účastníci tuto situaci vyřešit heuristickým rozhodnutím a jak může heuristické rozhodnutí porušit atomické ukončení transakce. Příklady uveďte včetně obsahu zpráv zasílaných účastníkům a záznamů ukládaných do logu.

   • Při čekání na potvrzení od koordinátora uzel nemůže nic dělat (stav READY), pokud ale abortoval, je to nezajímá ho zbytek.

   • Když by účastník měl čekat, rozhodne se na vlastní pěst. (To může vést k nekonzistenci, ale někdy je to levnější než se zdržovat; a pak se to stejně dá později opravit podle logu.)

     • Je blokován v READY stavu, ať se rozhodne heuristicky, může to být špatně:

       • commit, tak je možnost, že někdo posal vote_no

       • abort, tak je možnost, že všichni ostatní původně všichni vote_yes

Systémy

Exercises

1. Nakreslete strukturu typického transakčního monitoru. Popište funkci a spolupráci jednotlivých prvků této struktury. Vysvětlete důvody vedoucí použití právě takové struktury.

2. Navrhněte rozhraní pro koordinaci účastníků relativně krátkých transakcí vyžadujících atomické ukončení, nebo popište nějaký standard definující takové rozhraní. Popište detailně metody rozhraní a ilustrujte jejich funkci.

3. Navrhněte rozhraní pro koordinaci účastníků relativně dlouhých transakcí nevyžadujících atomické ukončení, nebo popište nějaký standard definující takové rozhraní. Popište detailně metody rozhraní a ilustrujte jejich funkci.

1) Transakcni monitor. Obrazek sem asi nenacpu, ale zhruba. TPM (Transaction Processing Monitor) spojuje predevsim spojuje klienty a servery. Klientum umoznuje zakladat a ridit transakce. Pozadavky dispatchuje na servery. Servery jsou typicky startovany on demand a obsahuji pouze business logiku. Servery predavaji pozadavky Resource managerum. Commit (2PC) ridi opet TPM. TPM se stara jeste o dalsi veci - recovery, logging, load balancing (frontovani pozadavku) apod.

PDF obsahující schéma struktury TP monitoru

2) Doporucuji popsat OTS z CORBA. Viz slajdy 19-SLD-Example-CORBA-OTS.pdf

3) Ja osobne bych tady asi popisoval Activity service. Viz 21-SLD-Example-CORBA-AS.pdf

(prevzato z fora)