DBI016 Odpovědi na zkouškové otázky: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Questions)
(Questions)
Řádka 56: Řádka 56:
 
#* data se deleguji nove vzniklym transakcim
 
#* data se deleguji nove vzniklym transakcim
 
#* u joinu: nova transakce zdedi vsechna data
 
#* u joinu: nova transakce zdedi vsechna data
#* u splitu dve moznosti: bud obe transakce dostanou vsechna data, nebo si je rozdeli (zalezi na implementaci - asi...)
+
#* u splitu dve moznosti:  
 +
#*# '''seriovy (serial) split''', kde t<sub>a</sub> musi provest commit drive nez t<sub>b</sub> - obe transakce dostanou vsechna data
 +
#*# '''nezavisly (independent) split''', kde mohou t<sub>a</sub> a t<sub>b</sub> provest commit nezavisle na sobe, data si rozdeli
  
 
= Serializovatelnost =
 
= Serializovatelnost =

Verze z 21. 6. 2006, 10:35

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--Jirja 16:04, 15 Jun 2006 (CEST)

Modely

Questions

  1. Vysvětlete vlastnost atomicity ACID transakcí.
    • Transakce proběhne celá, nebo vůbec.
  2. Vysvětlete vlastnost consistency ACID transakcí.
    • Převádí DB 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.
    • Zavislosti mohou byt velmi slozite
    • neni dobre formalizovano
    • tezke na implementaci
  7. Popište funkci transakčního modelu transactions with savepoints.
    • savepointy jsou body, ke kterym se da rollbackovat (nerika se tomu rollback ale undo)-> nemusi se zrusit cela transakce, kdyz se nepovede 100. operace
    • první SP obvykle po begin
  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 kontext vytvoření SP. A ten po rollbacku též obnovit. Při rollbacku z vnořených procedur vlastně simulujeme longjmp
  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í)(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?
    • 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.
    • "Atomické" {commit,begin} (rika se tomu chain), zachovává se kontext, rollbackuje se jen poslední transakce (porusuje to atomicitu !).
  12. Popište funkci transakčního modelu nested transactions. 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).
  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 potransakce
    • 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í.
    • 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.
    • 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 ta musi provest commit drive nez tb - obe transakce dostanou vsechna data
      2. nezavisly (independent) split, kde mohou ta a tb provest commit nezavisle na sobe, data si rozdeli

Serializovatelnost

Questions

  1. 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.
    • w2[x], r1[x], w2[x]
  2. 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]
  3. 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]
  4. Vysvětlete, kdy je vlastnost transakční historie prefix commit closed.
    • Vlastnost je prefix commit closed, jestliže jakmile je splněna v historii H, je také splněna v historii C(H') (tj. commitovaná projekce) pro libovolný prefix H' historie H.

Exercises

  1. 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í
    • one version pohledova ekvivalence historií:
      • pokud T1 cetla data zapsana T2, pak to dela i v druhem rozvrhu (čtení stejné verze dat)
      • hmají stejné poslední zápisy (tj. pokud v jedné je poslední wi[x] pro i=k, je v druhé též polední)
    • multi-version pohledova ekvivalence historií:
      • Každý zápis je vlastně poslední
      • Čtení stejné verze dat není problém, read specifikuj verzi, jakou chce
      • Takže multi-version historie jsou ekvivalentní, pokud obsahují sejné operace

Rozdíl je tedy ten, že u one version máme jednu verzi, kterou si vzájemně mění konfliktní opeace. 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

Účel serializovatelné historie

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 isolovanost, ale zvýšíme paralelismus. To lze zlepšit multi-version 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.

??

?.....?

One version

Questions

  1. 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 $ T_i $ částečně uspořádaná relací $ <_i $, kde
      • $ T_i \subseteq \{r_i[x], w_i[x]; $ x je datová položka$ \} \cup \{a_i, c_i\} $
      • $ a_i \in T_i \oplus c_i \in T_i $, kde $ \oplus $ je xor -- buď commituje nebo abortuje
      • $ q \in \{c_i, a_i\}, q \in T_i \Rightarrow \forall p \in T_i: p <_i q $ -- commit nebo abort je na konci
      • $ 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] $ -- operace na stejných datech jsou uspořádané
    • Kompletní historie -- množina H s částečným uspořádáním $ <_H $, kde H je $ T_i $, $ <_H $ je nadmnožinou sjednocení $ <_i $ a pro každé konfliktní $ p,q \in H $platí$ p <_H q \lor q <_H p $. Historie je prefix kompletní historie.
  2. Definujte, nejlépe formálně, pojem sériové one version transakční historie.
    • Pro každé T_i, T_j platí, že všechny operace z T_i jsou před operacemi z T_j nebo naopak.
  3. Definujte, nejlépe formálně, pojem zotavitelné (jinak také RC) one version transakční historie.
    • H je zotavitelná , jestliže platí: kdykoli T_i čte z T_j (i != j) a c_i je v H, potom c_j < c_i.
    • T_i musí počkat, jestli se přečtená hodnota nezruší abortem a_j.
  4. 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 T_i čte x z T_j, potom c_j < r_i[x].
    • T_i čte až potvrzený výsledek.
  5. Definujte, nejlépe formálně, pojem striktní (jinak také ST) one version transakční historie.
    • H je striktní, jestliže platí: kdykoli w_j[x] < o_i[x] (i!=j), pak a_j < o_i[x] nebo c_j < o_i[x].
    • čte nebo přepisuje se až transakce, která tam psala předtím, skončí.
  6. Definujte formálně relaci conflict equivalence na one version transakčních historiích.
    • H a H' jsou konfliktově ekvivalentní, pokud mají stejné transakce a operace a pořadí konfliktních operací, která neabortují, je stejné.
  7. 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é T_i, T_j takové, že a_i, a_j nejsou v H a pro každé x platí: jestliže T_i čte x z T_j v H, potom T_i čte x z T_j 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'
  8. 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.
  9. 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.
  10. 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 T = {T_1, ..., T_n} je orientovaný graf, jehož vrcholy jsou transakce z C(H) a z T_i vede hrana do T_j, právě když nějaká operace z T_i je v konfliktu s nějakouoperací v T_j a předchází ji.
    • Historie je serializovatelná, právě když tento graf neobsahuje cyklus.
    • Transitivita není podstatná.
  11. Napište příklad sériové one version transakční historie. Použijte zápis, kde R1(X) označuje přečtení položky X transakcí T1, W2(Y) označuje zápis položky Y transakcí T2 atd.
    • r1[x], w1[x], r2[x], w2[y], w2[x]
  12. 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). Použijte zápis, kde R1(X) označuje přečtení položky X transakcí T1, W2(Y) označuje zápis položky Y transakcí T2 atd.
    • 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)
  13. 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). Použijte zápis, kde R1(X) označuje přečtení položky X transakcí T1, W2(Y) označuje zápis položky Y transakcí T2 atd.
    • 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], r1[x], w2[x], c1, c2 - není ACA (r2[x]<c1)
  14. 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á. Použijte zápis, kde R1(X) označuje přečtení položky X transakcí T1, W2(Y) označuje zápis položky Y transakcí T2 atd.
    • 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
  15. 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). Použijte zápis, kde R1(X) označuje přečtení položky X transakcí T1, W2(Y) označuje zápis položky Y transakcí T2 atd.
      • 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

  1. 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í r_i[x_j], w_i[x_i], (x_i je datová položka verze i) a právě jedné z a_i nebo c_i (maximální prvky). Zápis vždy vytváří novou verzi w_i[x_i]. Čtení vždy určuje, kterou verzi chce číst r_i[x_j].
    • MV Kompletní historie
      • každé r_i[x_j] předchází w_j[x_j] (čtu existující verze)
      • každé r_i[x] po w_i[x_i] je r_i[x_i] (preferuje svoje zápisy).
      • každé c_i po r_i[x_j] předchází c_j (zotavitelnost -- nutná pro zajištění, že i C(H) je MV Kompletní historie).
  2. 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)
  3. 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 T_i čte x z T_j, potom je buď i=j, nebo T_j je poslední transakce před T_i, která zapsala verzi x.
    • One copy sériová historie je pohledově ekvivalentní nějaké sériové one version historii.
  4. Definujte formálně relaci view equivalence na multiversion transakčních historiích.
    • Multi version historie jsou pohledově ekvivalentní, pokud mají stejné operace.
  5. 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 C(H) je pohledově ekvivalentní nějaké one copy sériové historii.
  6. 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í (w_i[x_i] < r_j[x_i])
    • Rozšíření: pro každou dvojici w_i[x_i], r_k[x_j] přidej
      • T_i -> T_j, pokud i < j (čtu verzi zapsanou po wi[i])
      • T_k -> T_i, pokud j < i (čtu verzi zapsanou před wi[i])
    • Multi version historie je one-serializovatelná, právě když rozšířený multi version serializační graf je acyklický
  7. 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á. Použijte zápis, kde R1(X1) označuje přečtení položky X1 transakcí T1, W2(Y2) označuje zápis položky Y2 transakcí T2 atd.
    • w1[x1], r2[x1], w2[x2]
    • w1[x1], r2[x1], w2[x2], r3[x1]
  8. 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á. Použijte zápis, kde R1(X1) označuje přečtení položky X1 transakcí T1, W2(Y2) označuje zápis položky Y2 transakcí T2 atd.
    • 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.
    • 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
  7. 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(pi[x])
      • if(pli[x] conflits with qlj[x])
    delay pi[x] /*Ti spí dokud nelze získat zámek*/
      • set lock pli[x]
      • send to DM pi[x]
  8. 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.
chci\mám nic R W C
R yes yes yes no
W yes no no no
C yes no no no
    • schedule(pi[x])
      • case pi[x]
        • wi[x]
          • attempts to set wlii[x]
          • set lock
          • schedule wi[xi]
        • ri[x]
          • attempts to set rlii[x]
          • set lock
          • if(Ti has already wlii[x])
            • schedule ri[xi]
          • else schedule ri[xj], where xj last committed
        • ci
          • all wli[x] converts to cli[x] /* způsobí odložení commitu dokud nejsou uvolněny všechny rl[x] */
  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
  8. 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
  9. Nakreslete kolizní tabulku pro hierarchické zámky v režimech R, W, IR a IW.
chci\mám nic IS IX S SIX X
IS yes yes yes yes yes no
IX yes yes yes no no no
S yes yes no yes no no
SIX yes yes no no no no
X yes no no no no no
  1. Vysvětlete termín phantom.
    • Pokud chci pracovat s nějakou množinou položek vybírám (resp. mažu ji), určenou predikátem, co zamknout? Jedná se o problém dynamicky se měnící databáze. Sice zamknu položky co jsem vybral, ale může s měnit množina odpovídající predikátu. Potřebujeme zamknout celou databázy? Ne, stačilo by "zamknout predikát".
  2. 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ší.
  3. Vysvětlete termín predicate locking.
  4. Vysvětlete termín key range locking.
  5. Vysvětlete termín previous or next key range locking.
  6. 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á rlock)
    • rl1[x], rl2[x], r1[x], r2[x], upg_wl1[x], upg_wl2[x], w1[x], w2[x], ...
chci\mám nic IS IX S SIX U X
IS yes yes yes yes yes no no
IX yes yes yes no no no no
S yes yes no yes no no no
SIX yes yes no no no no no
U yes yes no no no no no
X yes no no no no no no
  1. Popište detekci deadlocku pomocí timeouts a uveďte její přednosti a nedostatky.
  2. Popište detekci deadlocku pomocí wait for grafu a uveďte její přednosti a nedostatky.
  3. Uveďte, proč a jak se vybírá cíl volání abort pro přerušení deadlocku.
  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ět?ovou režii, kterou by mělo přímočaré ukládání zámků spolu s daty, ke kterým se vztahují.

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ů.

Č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 r_i[x], ..., w_j[x] právě když ts(T_i)<ts(T_j))
    • Pokud máme cyklus v serializačním grafu tak potom ts(T)<ts(T')<..<ts(T) SPOR)
  2. 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 [operace,data_item]=max naplánovaná timestamp, odmítáme pi nad data_item, pokud ts(pi)<[operace,data_item]
    • V opačném případě může dojít ke změně hodnoty
  3. 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, ci se pozdrží dokud cj pro všechny Tj, jejichž verze četla Ti
    • schedule(pi[x])
      • if(p==ri[x])
    p=ri[xj] where j is the largest available timestamp for x that is smaller than or equal to i
      • else/*p==wi[x]*/
    if(occurred rj[xk] && (ts(Tk) < ts(Ti) < ts(Tj))
    reject
    else
    p=wi[xi]
    accept
  4. 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ět?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.

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(pi[x])
      • if(node Ti is not in SSG) add node Ti to SSG
      • foreach qj conflits with pi[x] do connect from::Tj to::Ti in SSG
      • if(cycle in SSG)
    abort Ti
    delete and disconect Ti from SSG
    else schedule pi[x] /*(after DM acknowledges all scheduled conflicting operations)*/
  3. 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.
    • Pokud Ti, lze ji zřejmě odstranit z grafu.
    • Dále vidíme, že pro zkončené transakce Ti jižb nepřibývají vstupní hrany do Ti. A pokud už do Ti žádná vstupní hrana nevede, nemúže ležet n kružnici a lze 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í Ti
    • Co třeba toto:
      • T1 = w1[x], w1[x], ..
      • T2 = w2[x], w2[x], ..
      • w1[x], w2[x], w1[x], a1 cyklus abortuje se T1
      • w2[x], w1[x], w2[x], a2 cyklus abortuje se T2
      • a znovu w1[x], w2[x], w1[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.
  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 bez výpadku účastníků.
  3. 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.
  4. 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ů
  5. 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.