DBS:transakční zpracování

Jaroslav Pokorný

MFF UK, Praha

pokorny@ksi.ms.mff.cuni.cz

Obsah

• Úvod - proč transakce?

• Pojem transakce
  • vlastnosti ACID
  • transakční modely

• Paralelní zpracování transakcí
  • problémy + jak v SQL
  • uspořádatelnost rozvrhu
  • uzamykací protokoly

• Zotavení z chyb

1. Úvod

Požadavky na SŘBD:

• chránit data organizovaná pod SŘBD,

• poskytnout korektní a rychlý asynchronní přístup většímu množství uživatelů.

Řešení:

• komponenta řízení souběžného (paralelního) zpracování (concurrency control),

• komponenta zotavení z chyb (recovery)

1. Úvod

• Řízení souběžného zpracování zajišťuje uživatelům, že každý vidí konzistentní stav db bez ohledu na to, že více uživatelů přistupuje asynchronně ke stejným údajům.

• Zotavení z chyb zajišťuje, že stav db není narušen v případě chyby software, systému, nebo fyzického média v průběhu zpracování úlohy měnící data v db.

2. Pojem transakce

transakce: programová jednotka spolu s mechanismy, které zabezpečí, že po ukončení programu (korektním i nekorektním) zůstane db konzistentní (splňuje všechna IO definovaná ve schématu db).

snímek PPT

Vlastnosti transakce:

• transparence paralelního zpracování

• atomicita vzhledem k chybám

Architektura software:

2. Pojem transakce

snímek PPT

2. Pojem transakce

Jiná definice: transakce je jistá posloupnost nebo specifikace operací, jako jsou čtení, zápis, výpočet, se kterou se zachází jako s jedním celkem (logická jednotka práce).

Př.: převod peněz z jednoho konta na druhé,

přihlášení na zkoušku, zápis na cvičení,

odhlášení ze zkoušky, odepsání ze cvičení,

přehlášení na jiný termín, přehození na jiné cvičení.

2. Pojem transakce

• výpadek systému ? SŘBD obnoví stav db na stav před započetím provádění transakce.

• konec transakce - příkaz COMMIT (potvrzení) - příkaz ROLLBACK (zrušení)

• začátek transakce - nejčastěji první JMD operace po konci předchozí transakce

• nutné: existence žurnálu (angl. log file); obsahuje historii změn dat v jisté časové periodě. Po incidentu se žurnál prochází s využitím operací REDO a UNDO.

2. Pojem transakce

• pohled programátora:
  • uzávorkovaná kolekce akcí

• jednoduchý model chyb:
  • pouze dvě možnosti:

snímek PPT

2.1 Stavy transakce

• aktivní (A) - jde o stav od počátku provádění transakce,
• částečně potvrzený (PC) - jde o stav po provedení poslední operace transakce,
• chybný (F) - objeví-li se, že v normálním průběhu transakce nelze pokračovat;
• zrušený (AB) - nastane po skončení operace ROLLBACK, tj. uvedení db do stavu před transakcí;
• potvrzený (C) - nastane po úspěšném zakončení, tj. po potvrzení operací COMMIT.

2.1 Stavy transakce

stavový diagram pro transakci

2.2 Vlastnosti ACID

• atomicita - transakce buď proběhne celá nebo vůbec ne,

• konzistence - transakce transformuje db z konzistentního stavu do jiného konzistentního stavu,

• nezávislost - dílčí efekty jedné transakce nejsou viditelné jiným transakcím,

• trvanlivost - efekty úspěšně ukončené (potvrzené) transakce jsou trvale uloženy

2.2 Vlastnosti ACID - atomicita

• Begin-Commit závorkují množinu akcí.

• konzistence může být uvnitř závorek narušena
  modifikace čísla čtenáře v ČTENÁŘ;
  
  modifikace čísla čtenáře ve VÝPŮJČKA;
  modifikace čísla čtenáře v REZERVACE;

• Begin a Commit jsou body konzistence
  • údržba atomicity transakce se nazývá zotavení z chyb. Jedná se např. o vydání příkazu ROLLBACK po chybě dat, po uváznutí apod., nebo provedení automatických akcí REDO a UNDO po chybě systému.

2.2 Vlastnosti ACID - nezávislost (izolace)

• dílčí efekty jedné transakce nejsou viditelné jiným transakcím

? transakce vždy vidí konzistentní db.

Běžící transakce nemůže zjevit své výsledky ostatním transakcím, dokud je nepotvrdí.

• anomálie: např. ztráta aktualizace

Př.: čítač rezervací letenek: správně 79 a ne 84

další: dočasná aktualizace, nekorektní použití agregační funkce

2.2 Vlastnosti ACID - trvanlivost

• efekty úspěšně ukončené (potvrzené) transakce jsou trvale uloženy (perzistence).

tj. jakmile transakce vydá potvrzení výsledků, pak výsledky jsou trvalé a nemohou být ztraceny z db (další rys atomicity).

2.3 Modelování transakcí

transakční model:
• struktura transakce
• struktura objektů (jednoduchý objekt, ADT, složitý objekt, aktivní objekt)

Struktura transakce:

• ploché transakce

• hnízděné transakce: obsahují dílčí transakce
  • uzavřené hnízdění (sémantika: zdola nahoru)
  • otevřené hnízdění (kořenová transakce není atomická - sága)

• workflow: dlouhotrvající transakce

snímek PPT

3. Paralelní zpracování transakcí

Předpoklady: ploché transakce, jednoduché objekty, operace FETCH, resp. OUTPUT pro komunikaci vyrovnávací paměť (VP) ? disk

READ(X,x) - přiřazuje hodnotu atributu X lokální proměnné x. Není-li stránka s danou hodnotou ve VP, provede se FETCH(X) + přiřazení hodnoty X z VP proměnné x.

WRITE(X,x) - přiřazuje hodnotu lokální proměnné x atributu X ve VP. Není-li žádaná stránka ve VP, provede se FETCH(X), následuje přiřazení proměnné x atributu X ve VP.

snímek PPT

3.1 Pojem rozvrhu

Předpoklad: transakce T1 a T2 dané posloupnostmi akcí {T11,...,T1n}, resp. {T21,...,T2m}.

rozvrh - pořadí provádění dílčích akcí více transakcí v čase. Zodpovídá: rozvrhovač

snímek PPT

3.2 Problémy

ztráta aktualizace (při “prokládání” transakcí)

Přestože by hodnota X v db měla být 79, je 84.

snímek PPT

3.2 Problémy

dočasná aktualizace (při chybě systému)

Po provedení ROLLBACK u T1 bude aktualizace provedená v T2 založena na původních změnách;

? chybný výsledek.

snímek PPT

3.2 Problémy

nekorektní použití agregační funkce

snímek PPT

3.2 Problémy

neopakovatelné čteníT1 používající kurzor (viz SQL) se snaží znovu přečíst řádek, který již četla dříve, ten však již obsahuje jiné hodnoty (nebo neexistuje) díky aktualizaci v T2, která probíhá paralelně.

fantómT1 přečte množinu řádků (jeden příkaz SELECT) a zpracovává je. Mezitím některé z těchto řádků změní T2 (DELETE nebo INSERT). Použije-li T1 týž příkaz (pro jiné kalkulace), obdrží již jinou množinu řádků.

snímek PPT

3.2 Problémy

Povolené anomálie v SQL92:

ANSI SQL nastavuje implicitně úroveň 3.

snímek PPT

3.3 Uspořádatelnost rozvrhu

Sériové rozvrhy zachovávají operace každé transakce pohromadě.

Pz.: pro N transakcí lze naplánovat N! různých sériových rozvrhů.

Paralelní rozvrh … operace transakcí jsou navzájem prokládány

Požadavek na korektnost rozvrhu: efekt paralelního zpracování transakcí je týž, jako podle nějakého sériového rozvrhu. Transakční zpracování, které zaručuje tuto vlastnost, zaručuje uspořádatelnost.

snímek PPT

3.3 Uspořádatelnost rozvrhu

Definice ekvivalence rozvrhů je založena na komutativitě operací READ a WRITE:

Df.: Dvě operace jsou konfliktní, jestliže výsledky jejich různého sériového volání nejsou ekvivalentní.

Operace, které nejsou konfliktní nazýváme kompatibilní.

snímek PPT

3.3 Uspořádatelnost rozvrhu

Df.: Rozvrhy S1 a S2 pro množinu transakcí T = {T1,...,TN}. Pak S1 s S2 jsou ekvivalentní (vzhledem ke konfliktům), jsou-li splněny dvě podmínky:

1. Jestliže se v jednom rozvrhu vyskytuje READ(A) v Ti a tato hodnota vznikla z WRITE(A) v transakci Tj, potom totéž musí být zachováno v druhém rozvrhu.

2. Jestliže se v jednom rozvrhu vyvolá poslední operace WRITE(A) v Ti, pak totéž musí být i v druhém rozvrhu.

Relativní pořadí konfliktních operací je stejné v S1 i S2.

?

snímek PPT

3.3 Uspořádatelnost rozvrhu

Př.:

T4: {READ(A),akce1(A),WRITE(A),READ(B),akce2(B),WRITE(B)}

T5: {READ(A),akce3(A),WRITE(A),READ(B),akce4(B),WRITE(B)}

S3 S4

S1:{T4,T5}, S2:{T5,T4}. jsou sériové rozvrhy.

S3 a S4 nejsou sériové.

Zřejmě S3 ? S1, S3 ? S2.

Rozvrh je uspořádatelný, jestliže existuje sériový rozvrh s ním ekvivalentní.

3.3 Uspořádatelnost rozvrhu

Pz.:

• Existují rozvrhy, které nejsou ekvivalentní se žádným sériovým rozvrhem podle df. a přesto produkují stejný výsledek jako nějaký sériový rozvrh. Pojem konfliktu je zde založen na znalosti sémantiky operací.

• Existují možnosti definovat smysluplná kritéria korektnosti, která nejsou založena na pojmu uspořádatelnost.

snímek PPT

3.4 Testování uspořádatelnosti

Precedenční graf rozvrhu S. Jde o orientovaný graf {U,H}U = {Ti | i = 1, 2, ..., n}, H={hik(A)} hik(A)... vzhledem k manipulacím s objektem A vede hrana od uzlu Ti k uzlu Tk (viz konstrukce)

Důsledek: rozvrh S může být ekvivalentní pouze s takovým sériovým rozvrhem, kde Ti předchází Tk.

Př.: S3 S4

4

5

3.4 Testování uspořádatelnosti

Konstrukce hrany hik v precedenčním grafu: existuje-li alespoň jeden objekt A tak, že

• s ohledem na podmínku 2 pro ekvivalenci:(i) poslední WRITE(A) v Tj je před posledním voláním WRITE(A) v Tk

• s ohledem na podmínku 1 pro ekvivalenci:(ii) Tj volá WRITE(A) před tím, než Tk volá READ(A)

(v Tk se čte z db hodnota A, vzniklá v Tj)(iii) Tj volá READ(A) před tím, než Tk volá WRITE(A)(v Tj se čte z db hodnota A, dříve, než se v Tk změní)

snímek PPT

3.4 Testování uspořádatelnosti

Př.:

snímek PPT

3.4 Testování uspořádatelnosti

Př.:

3.4 Testování uspořádatelnosti

Tv.: Rozvrh je uspořádatelný, (tedy ekvivalentní některému sériovému rozvrhu), jestliže v jeho precedenčním grafu neexistuje cyklus.

Př: podle tohoto tvrzení:rozvrh S4 není uspořádatelný, rozvrh S3 je uspořádatelný.

Tv.: Dva rozvrhy jsou ekvivalentní, jestliže mají stejný precedenční graf.

3.4 Testování uspořádatelnosti

• Testování uspořádatelnosti jakéhokoliv rozvrhu není pro praxi vhodné. Časové nároky takového přístupu by zřejmě přesahovaly rozumnou míru.

• Přístup z druhé strany:

Konstruovat transakce podle předem daných pravidel tak, že za určitých předpokladů bude každý jejich rozvrh uspořádatelný. Soustavě takových pravidel se obecně říká protokol.

3.5 Uzamykací protokoly

Nejznámější protokoly jsou založeny na dynamickém zamykání a odmykání objektů v db.

Jednoduchý model:
• objekt A může být v daném čase uzamčen nejvýše jednou transakcí (operace LOCK(A), UNLOCK(A))
• transakce, která uzamkla objekt, má právo na něm provádět operace READ a WRITE (a další operace).

3.5 Uzamykací protokoly

Legální rozvrh:

• objekt je v transakci uzamknutý, kdykolivk němu chce tato transakce přistupovat,

• transakce se nebudou pokoušet uzamknout objekt již uzamknutý jinou transakcí (jinak musí čekat na uvolnění zámku).

Pz: Samotná legálnost rozvrhu nezaručuje uspořádatelnost.

snímek PPT

S7 a S8 nemají stejné výsledky.V S7 se akce7 provádí s jinou hodnotou A, než v S8. Podobně i S7 a rozvrh {T10,T9}.

Pz.: Zamykání a odmykání samo ještě nevede k uspořádatelnému rozvrhu.

3.5 Uzamykací protokoly

snímek PPT

V případech některých rozvrhů může nastat uváznutí (deadlock).

Uváznutí lze řešit tak, že provedeme ROLLBACK jedné transakce. Co tato uzamkla, bude odemknuto, čímž se druhá transakce odblokuje.

3.5 Uzamykací protokoly

snímek PPT

Omezíme se dále na tzv. dobře formované transakce, které podporují přirozené požadavky na transakce:

a) transakce zamyká objekt, chce-li k němu přistupovat,

b) transakce nezamyká objekt, když ho již zamkla,

c) transakce neodmyká objekt, který nezamkla,

d) na konci transakce nezůstane žádný objekt zamčený.

Cíl: hledáme postačující podmínku pro to, aby všechny legální rozvrhy pro dobře formované transakce byly uspořádatelné.

Pz.: Nestačí, že objekt odemkneme bezprostředně po manipulaci s ním.

3.5 Uzamykací protokoly

snímek PPT

3.5 Uzamykací protokoly

Řešení: udělat transakce dvoufázové.T2 je, T1 není dovufázová (pomůže prohození UNLOCK(A) s LOCK(B) v T1).

Precendenční graf pro tento rozvrh:

Rozvrh není uspořádatelný.

snímek PPT

3.5 Uzamykací protokoly

Dvoufázová transakce:1. fáze - uzamyká se, nic se neodemyká 2. fáze - od prvního odemknutí do koncetransakce se už nic nezamyká

Uzamykací protokol je množina pravidel, které udávají, kdy transakce bude uzamykat a odmykat objekty db.

Tv.: Jestliže všechny transakce v dané množině transakcí T jsou dobře formované a dvoufázové, pak každý jejich legální rozvrh je uspořádatelný.

snímek PPT

Precendenční graf pro tento rozvrh:

Je uspořádatelný, ač T13’ není dvoufázová.Nevylučuje se existence uspořádatelného legálního rozvrhu (ne)dobře formovaných nedvoufázových transakcí.

3.5 Uzamykací protokoly

snímek PPT

3.5 Uzamykací protokoly

Jeden z uspořádatelných rozvrhů dvoufázových T16 a T17. Transakce T17 jednou čeká na uvolnění zámku pro A, jednou na uvolnění zámku pro C. 

Kdyby LOCK(A), resp. LOCK(C) byly v rozvrhu před UNLOCK(A), resp. UNLOCK(C) v transakci T16, rozvrh by se stal nelegálním.

snímek PPT

3.5 Uzamykací protokoly

snímek PPT

Rozvrh, plánující naznačené provádění kroků transakcí, vede k uváznutí. Nelze pokračovat ani s LOCK(B), ani s LOCK(A).

Řešení: metody detekce či prevence uváznutí

3.5 Uzamykací protokoly

4. Zotavení z chyb

• globální chyby (mají vliv na více transakcí)
  • spadnutí systému serveru (např. výpadek proudu) ? obecně ztráta obsahu VP.
  • systémové chyby (např. uváznutí, odumřeníkomunikace klienta se serverem) ? ovlivňují transakce, avšak nikoli celou db
  • chyby médií (např. incident na disku) ? ohrožení db, nebo její části,

• lokální chyby (v jedné transakci).
  • logické chyby: měly by být “odchyceny” a ošetřeny na úrovni transakce explicitním vyvoláním ROLLBACK (pokus o porušení IO při zápisu do db, dělení nulou při výpočtu).

4. Zotavení z chyb

• Optimistická strategie:předpokládá se, že častější konec transakce bude COMMIT, nové hodnoty se přímo píší do db, průběh transakce se dokumentuje v žurnálu. Při ROLLBACK se použije žurnál pro obnovení původního stavu dat v db.

• Pesimistická strategie:předpokládá se, že častější konec transakce bude ROLLBACK, nové hodnoty se přímo nepíší do db, průběh transakce se dokumentuje v žurnálu. Do db se změny promítnou až při operaci COMMIT.

4. Zotavení z chyb

Při optimistické strategii, po restartu systému:
• Na transakce, jejichž stav bude v důsledku incidentu nedefinovaný, je nutné použít ROLLBACK (pomocí UNDO).
• Transakce, které byly úplné před započetím chyby systému, avšak které nebyly dokončeny fyzicky (např. odeslání VP na disk), je nutné zopakovat (REDO).

synchronizační body - vyznačují v žurnálu hranice mezi dvěma po sobě následujícími transakcemi.

kontrolní body - vyznačují v žurnálu hranice automaticky v jistých intervalech

snímek PPT

• natáhnutí celé db ze záložní kopie (BACKUP)

• použití žurnálu k REDO všech ukončených transakcí až do té chvíle, kdy ještě žurnál poskytuje potřebné informace.

4. Zotavení z chyb