Bankovní institut vysoká škola Praha Katedra matematiky, statistiky a informačních technologií
Řízení souběžného přístupu k datům v systémech řízení báze dat Bakalářská práce
Autor:
Petr Havlas Informační technologie, správce informačních systémů
Vedoucí práce:
Praha
Ing. Michal Valenta, Ph.D.
Červen, 2012
Prohlášení: Prohlašuji, ţe jsem bakalářskou práci zpracoval samostatně a v seznamu uvedl veškerou pouţitou literaturu. Svým podpisem stvrzuji, ţe odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámen se skutečností, ţe se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze
elektronických
vysokoškolských prací.
V Praze, dne 25.6.2012
……………….………….. Podpis autora
Poděkování: Děkuji Ing. Michalu Valentovi Ph.D. za podporu a odborné vedení během mé práce.
Anotace Bakalářská práce “Řízení souběţného přístupu k datům v systémech řízení báze dat“ je zaměřena na představení základních mechanismů pouţívaných pro řízení paralelního přístupu k datům v systémech řízení báze dat a provádí porovnání implementace v databázovém systému Oracle a PostgreSQL. Klíčová slova Řízení souběţného přístupu, dvoufázové zamykání, multiversion concurrency control, transakce, uváznutí, uspořádatelnost rozvrhu, ekvivalence rozvrhu
Annotation Bachelor’s thesis “Concurrency control in database management systems” is dealing with basic technics used in database management systems and compare implementation of these technics in Oracle and PostgreSQL databases. Key words Concurrency control, two-phase locking, multiversion concurrency control, transaction, deadlock, schedule serializability, schedule equivalence
Obsah 1
ÚVOD .................................................................................................................................................................... 6 1.1 TRANSAKCE .................................................................................................................................................... 6 1.2 USPOŘÁDATELNOST ........................................................................................................................................ 7 1.2.1 Rozvrhovač a rozvrh transakcí ............................................................................................................... 7 1.2.2 Uspořádatelný versus sériový rozvrh ..................................................................................................... 9 1.3 IZOLACE TRANSAKCÍ ..................................................................................................................................... 12 1.3.1 Anomálie ............................................................................................................................................... 13 1.3.2 Úroveň izolace podle SQL standardu ................................................................................................... 14 1.4 ŘÍZENÍ SOUBĚŢNÉHO PŘÍSTUPU ..................................................................................................................... 15 1.4.1 Optimistické a pesimistické metody řízení souběžného přístupu .......................................................... 15 1.5 UVÁZNUTÍ ..................................................................................................................................................... 16 1.5.1 Prevence ............................................................................................................................................... 16 1.5.2 Timeout ................................................................................................................................................. 19 1.5.3 Detekce a zotavení ................................................................................................................................ 19
2
METODY POUŽÍVANÉ PRO ŘÍZENÍ SOUBĚŽNÉHO PŘÍSTUPU ......................................................... 22 2.1 ZÁMKY .......................................................................................................................................................... 22 2.1.1 Dvoufázové zamykání (2PL) ................................................................................................................. 23 2.1.2 Strukturované zamykání ....................................................................................................................... 25 2.2 TIMESTAMP ORDERING ................................................................................................................................. 26 2.2.1 Thomas’ Write Rule .............................................................................................................................. 28 2.3 MULTIVERSION CONCURRENCY CONTROL ..................................................................................................... 28 2.3.1 Multiversion timestamp ordering ......................................................................................................... 31 2.3.2 Multiversion 2PL .................................................................................................................................. 31 2.4 VALIDATION-BASED CONCURRENCY CONTROL ............................................................................................. 32
3
ORACLE RDBMS.............................................................................................................................................. 34 3.1 IMPLEMENTACE CONCURRENCY CONTROL V RDBMS ORACLE ................................................................... 34 3.1.1 Zámky ................................................................................................................................................... 34 3.1.2 MVCC a Undo segment ........................................................................................................................ 38 3.2 ÚROVNĚ IZOLACE V ORACLE DATABÁZI ....................................................................................................... 40 3.3 CHYBY SPOJENÉ SE SOUBĚŢNÝM PŘÍSTUPEM ................................................................................................. 45
4
POSTGRESQL ................................................................................................................................................... 48 4.1 IMPLEMENTACE CONCURRENCY CONTROL V POSTGRESQL ......................................................................... 48 4.1.1 Zámky ................................................................................................................................................... 48 4.1.2 Implementace MVCC ............................................................................................................................ 51 4.2 ÚROVNĚ IZOLACE V POSTGRESQL ................................................................................................................ 53
5
ZÁVĚR ................................................................................................................................................................ 59
5
1 Úvod Tato práce se zabývá problematikou řízení souběţného přístupu (concurrency control) v databázovém stroji, jejím cílem je přinést přehled základních technik, postupů a protokolů - první část obsahuje úvod do problematiky, přehled základních termínů z oblasti transakčního zpracování a řízení souběţného přístupu, druhá část je jiţ zaměřena na konkrétní protokoly vyuţívané pro řízení souběţného přístupu a poslední část práce se věnuje implementaci ve vybraných relačních databázích – pro porovnání jsem vybral RDBMS Oracle, jako jednoho z hlavních představitelů komerčního databázového software a PostgreSQL, jako zástupce pokročilých Open source řešení.
1.1 Transakce Transakce je obvykle definována jako logická jednotka databázového zpracování, obsahuje jednu nebo více operací přístupu k databázi (vloţení, smazání, modifikace, a nebo čtení dat). Pro zajištění integrity dat musí transakce splňovat tzv. ACID vlastnosti, kde ACID jsou první písmena vlastností – Atomicity (atomičnost), Consistency (konzistence), Isolation (izolovanost) a Durability (trvalost). Atomicita určuje, ţe transakce je vţdy vykonána jako jedna operace, jako celek. Znamená to tedy, ţe všechny operace v transakci jsou buď úspěšně provedeny, nebo se neprovede ţádná - účelem je zajistit konzistentní data v případě poruchy databázového stroje. Konzistence zajišťuje, ţe pokud je databáze konzistentní před započetím transakce, úspěšné provedení transakce uvede databázi opět do konzistentního stavu. Toto je zodpovědností vývojáře nebo uţivatele, který transakci sestavuje. Izolovanost umoţňuje paralelní provádění transakcí, musí zajistit, ţe výsledek paralelně prováděných transakcí bude stejný jako při sekvenčním zpracování, nesmí tedy docházet k ovlivňování mezi současně běţícími transakcemi. Trvalost znamená, ţe změny provedené úspěšně dokončenou transakcí jsou persistentní, nesmí dojít k jejich ztrátě při poruše databázového systému.
6
1.2 Uspořádatelnost Pro databázové zpracování je typické, ţe probíhají stovky nebo tisíce transakcí za vteřinu a je tedy velmi pravděpodobné, ţe dvě nebo více operací budou pracovat se stejnými daty. Jedním z důleţitých úkolů databázového stroje tedy je zajištění konzistence dat při souběţném zpracování, aby výsledek zpracování souběţných transakcí byl shodný jako při jejich sekvenčním průběhu. Vlastnost provést paralelní transakce tak, ţe výsledek odpovídá sériovému zpracování, se nazývá uspořádatelnost (serializability). Obecně lze uvést, ţe rozvrh transakcí je uspořádatelný, pokud je efekt změn v databázi stejný, jako v případě sériového rozvrhu.
1.2.1 Rozvrhovač a rozvrh transakcí Rozvrh (schedule) je časově uspořádaná sekvence akcí prováděná jednou nebo vice transakcemi, pro zápis rozvrhu se pouţívají pouze operace READ a WRITE. Nyní předpokládejme rozvrh S, který obsahuje transakce Ti a Tj, kde i≠j. Transakce Ti obsahuje pouze jednu operaci Ij, Tj pouze operaci Ij a všechny operace pracují se stejný datovým objektem O - existují tedy čtyři moţné kombinace, které musíme brát v úvahu: Ii=READ(O), Ij=READ(O) - v tomto případě nezáleţí na pořadí, protoţe v obou případech je čtený stejný objekt. Ii=READ(O), Ij=WRITE(O) – kdyţ Ii proběhne před Ij, tak transakce Ti přečte obsah O ještě před jeho změnou transakcí Tj. Pokud se pořadí prohodí, Ti přečte hodnotu O změněnou transakcí Tj - výsledek tedy záleţí na pořadí instrukcí. Ii=WRITE(O), Ij=READ(O) – jedná se o obdobný případ jako v předchozím bodu, na pořadí záleţí. Ii=WRITE(O), Ij=WRITE(O) – pořadí operací přímo ovlivňuje hodnotu O uloţenou v databázi, protoţe se projeví pouze poslední provedená instrukce WRITE. O operacích, jejichţ pořadí nelze vyměnit, říkáme, ţe jsou konfliktní - instrukce Ii a Ij jsou konfliktní, pokud patří k různým transakcím, pracují se stejným objektem a alespoň jedna z nich je instrukcí WRITE. Tabulka 1 obsahuje přehledně uspořádané všechny kombinace.
7
READ(X)
WRITE(X)
READ(X)
Kompatibilita
Konflikt
WRITE(X)
Konflikt
Konflikt
Tabulka 1: Kompatibilita operací READ a WRITE Zdroj: (9)
Pokud po sobě jdoucí operace Ii a Ij nejsou konfliktní, můţeme jejich pořadí vyměnit a vytvořit tak rozvrh S' – říkáme, ţe rozvrh S' je ekvivalentní rozvrhu S, pokud pořadí všech operací je stejné, s výjimkou těch, na jejichţ pořadí nezáleţí. Pokorný (9) potom definuje ekvivalenci (vzhledem ke konfliktům) rozvrhů S a S' pomocí dvojice podmínek: 1) Pokud se v rozvrhu S vyskytuje READ(O) v transakci Ti a tato hodnota vznikla z WRITE (O) v transakci Tj, potom toto musí být zachováno i v rozvrhu S'. 2) Jestliţe se v rozvrhu S vyvolává poslední operace WRITE(O) v transakci Ti, pak totéţ je nutné zachovat i v rozvrhu S'. Zotavitelnost rozvrhu – rozvrh nazýváme zotavitelným (recoverable) pokud v případě transakci Ti a Tj platí, ţe operace WRITE(X) v Ti předchází operaci READ(X) transakce Tj, ale potvrzení (COMMIT) transakce Tj nastane dříve neţ ukončení transakce Ti, pokud by potom došlo ke zrušení (ABORT) transakce Ti , transakce Tj uţ by byla potvrzena a nebylo by moţné obnovit konzistenci dat. Na obrázku 1 je jednoduchá ukázka nezotavitelného rozvrhu transakcí T1 a T2, obrázek 2 potom obsahuje tentýţ rozvrh, upravený tak, aby splňoval podmínky zotavitelnosti. T1 WRITE(X)
T2
T1 WRITE(X)
READ(X) WRITE(X) COMMIT
READ(X) WRITE( ABORT
ABORT Obrázek 1: Nezotavitelný rozvrh Zdroj: autor
T2
COMMIT Obrázek 2: Zotavitelný rozvrh Zdroj: autor
V některých případech můţe zrušení jedné transakce vést k nutnosti zrušit také další transakce, toto chování se nazývá kaskádové rušení (cascading aborts). Zabránit tomuto chování se dá tím, ţe transakce čte pouze potvrzené změny. Pokud je rozvrh odolný proti kaskádovému rušení, znamená to, ţe je také zotavitelný, ale pro zotavitelný rozvrh jiţ nemusí 8
platit, ţe je zároveň odolný proti kaskádovému rušení. Na obrázku 3a je zotavitelný rozvrh, ale pokud provedeme zrušení transakce T1, musíme také provést zrušení transakce T2, protoţe pracovala s neplatnou hodnotou X. Upravený rozvrh 3b jiţ tento problém řeší. T1 WRITE( )
ABOR
T2
T1
READ(X) WRITE(X)
WRITE(X)
T2 READ(X) WRITE(X)
T
ABORT ABORT a)
COMMIT b)
Obrázek 3: Kaskádové rušení Zdroj: autor
1.2.2 Uspořádatelný versus sériový rozvrh O sériovém rozvrhu mluvíme v případě, ţe všechny operace transakce Tx jsou dokončeny před první operací transakce Ty atd. T1
X (X=100)
T2
READ(X); X=X+10 WRITE(X) READ(Y); Y=Y-5 WRITE(Y)
Y (Y=100)
110 95 READ(X); X=X*2 WRITE(X) READ(Y); Y=Y+45 WRITE(Y)
220
220
140 140
Obrázek 4: Sériový rozvrh 1 Zdroj: autor T1
X (X=100)
T2 READ(X); X=X*2 WRITE(X) READ(Y); Y=Y+45 WRITE(Y)
READ(X); X=X+10 WRITE(X) READ(Y); Y=Y-5 WRITE(Y)
Y (Y=100)
200 145 210 210
140 140
Obrázek 5: Sériový rozvrh 2 Zdroj: autor
Korektním rozvrhem označujeme rozvrh, po jehoţ dokončení je databáze ve stejném stavu, jako po dokončení některého sériového rozvrhu. Korektnost rozvrhu zajišťuje jeho 9
uspořádatelnost. Uspořádatelností rozvrhu rozumíme fakt, ţe rozvrh je nějakým způsobem ekvivalentní se sériovým rozvrhem (dále si představíme pohledovou a konfliktovou ekvivalenci). Platí, ţe kaţdý sériový rozvrh je uspořádatelný, ale jiţ neplatí, ţe kaţdý uspořádatelný rozvrh je sériový. O dvojici rozvrhů S a S' můţeme prohlásit, ţe jsou pohledově ekvivalentní, pokud splňují následující trojici podmínek (10): 1. Pokud transakce Ti čte úvodní hodnotu objektu O v rozvrhu S, musí ji číst také v rozvrhu S'. 2. Pokud transakce Ti čte v rozvrhu S objekt O zapsaný transakcí Tj, tak v rozvrhu S' musí Ti také číst O zapsaný transakcí Tj. 3. Pro kaţdý objekt O platí, ţe transakce, která tento objekt zapsala poslední v S, musí ho poslední zapsat také v S'. Pokud je rozvrh pohledově ekvivalentní se sériovým rozvrhem, říkáme o něm, ţe je pohledově uspořádatelný. Dvojice rozvrhů je konfliktově ekvivalentní, pokud relativní pořadí konfliktních operací (viz Tabulka 1) je stejné v obou rozvrzích (12), rozvrh označujeme jako konfliktově uspořádatelný, pokud je konfliktově ekvivalentní s nějakým sériovým rozvrhem. Můţe platit, ţe korektní rozvrh není podle uvedené definice ekvivalentní s ţádným sériovým rozvrhem. Test na konfliktovou uspořádatelnost se skládá ze dvou kroků: Krok 1: zjištění konfliktních párů – víme, ţe konflikt vzniká, pokud různé transakce provedou operace nad stejným objektem a alespoň jedna z těchto operací je WRITE, sledujeme tedy situace, kdy transakce Ti čte objekt, který předtím transakce Tj zapsala, transakce Ti zapisuje objekt, který předtím přečetla transakce Tj, a nebo transakce Ti zapisuje objekt, který jiţ předtím zapsala transakce Tj.
10
Mějme rozvrh S trojice transakcí T1,T2 a T3 T1
T2
T3
READ(X) WRITE(X) WRITE(X) WRITE(Y) READ(Y) WRITE(Y) WRITE(X)
V rozvrhu S můţeme nalézt celkem pět konfliktních párů: 1. Transakce T2 zapisuje objekt X poté co transakce T1 tento objekt přečetla. 2. Transakce T1 zapsala X po zápisu X transakcí T2. 3. Transakce T1 čte Y, který jiţ předtím zapsala transakce T3. 4. Transakce T1 zapisuje Y poté, co Y zapsala transakce T3. 5. Transakce T3 zapisuje X po transakci T1. Krok 2: vytvoření a vyhodnocení precedenčního grafu - začneme zakreslením uzlů pro transakce T1, T2 a T3, poté jednotlivé konfliktní operace zakreslíme jako hrany orientovaného grafu.
RW(X)
T1
WW(X)
WW(Y)
T2
WW(X)
WR(Y)
T3 Obrázek 6: Precedenční graf rozvrhu transakcí Zdroj: autor
Pokud je vytvořený graf acyklický, znamená to, ţe daný rozvrh je konfliktově ekvivalentní se sériovým rozvrhem (je konfliktově uspořádatelný). V našem případě je vytvořený precedenční graf cyklický, daný rozvrh tedy není konfliktově uspořádatelný.
11
Pokud bych měl shrnout vztah mezi vlastnostmi transakčních rozvrhů uvedenými v předchozím textu, lze to přehledně provést pomocí Vennova diagramu:
uspořádatelné rozvrhy všechny rozvrhy
pohledově uspořádatelné rozvrhy konfliktově uspořádatelné rozvrhy
zotavitelné rozvrhy
rozvrhy odolné proti kaskádovému rušení
sériové rozvrhy
Obrázek 7: Vztah mezi různými druhy rozvrhů Zdroj: upraveno podle (1) a (5)
Jak je z diagramu zřejmé, platí, ţe kaţdý sériový rozvrh splňuje všechny dříve uvedené vlastnosti – je uspořádatelný (i pohledově a konfliktově), je odolný proti kaskádovému rušení a je zotavitelný. Na druhou stranu jiţ neplatí, ţe kaţdý uspořádatelný rozvrh je zotavitelný a odolný proti kaskádovému rušení, nebo ţe zotavitelný rozvrh je nutně také uspořádatelný.
1.3 Izolace transakcí Jedním z nejdůleţitějších úkolů databázového stroje je zajistit izolaci transakcí, v této kapitole na tuto vlastnost nahlédneme z pohledu SQL standardu (19). V SQL standardu se izolace a úroveň izolace definuje za pomocí anomálií (phenomena), které databázový systém umoţňuje.
12
1.3.1 Anomálie Rozlišujeme čtyři základní druhy anomálií – ztráta aktualizace (lost update), dočasná aktualizace (dirty read), neopakovatelné čtení (non-repeatable read) a fantóm (phantom read). 1.3.1.1 Ztráta aktualizace Ztráta aktualizace nastane v případě, ţe jedna transakce přepíše výsledek druhé. T1 READ(A); A=A+20
T2 READ(A); A=A+10 WRITE(A) COMMIT
WRITE(A) COMMIT Obrázek 8: Ztráta aktualizace Zdroj: autor
Jak je vidět z rozvrhu transakcí T1 a T2, změny transakce T2 jsou přepsány transakcí T1 a ztraceny. 1.3.1.2 Dočasná aktualizace Zdrojem této anomálie je čtení nepotvrzených dat - na jednoduchém příkladu si můţeme předvést, jak k tomuto problému dojde – uvaţujme dvě transakce T1 a T2: T1 sníţí obsah A o 5, následně transakce T2 přečte obsah A dříve, neţ dojde k potvrzení transakce T1 a navýší B o hodnotu A. T1 READ(A); A=A-5 WRITE(A)
T2
READ(A) READ(B);B=B+A WRITE(B) COMMIT ROLLBACK Obrázek 9: Rozvrh s výskytem dirty read Zdroj: autor
Pokud v dalším kroku dojde ke zrušení transakce T1, nastane problém - transakce T2 obsahuje nyní jiţ neplatná data, protoţe hodnota A se kterou pracovala, vlastně nikdy neexistovala.
13
1.3.1.3 Neopakovatelné čtení Podstatou této anomálie je čtení dat před změnou a po potvrzení této změny transakce T1 přečte řádek, transakce T2 tento řádek změní a je potvrzena. Kdyţ nyní transakce T1 přečte opět stejný řádek, dostane jinou hodnotu, neţ při prvním čtení. T1 READ(A)
T2 READ(A); A=A+10 WRITE(A) COMMIT
READ(A) COMMIT Obrázek 10: Rozvrh s neopakovatelným čtením Zdroj: autor
1.3.1.4 Fantóm Jedná se o podobný problém, jako v případu neopakovatelného čtení, jenom s tím rozdílem, ţe se změní počet vrácených řádků – transakce T1 přečte mnoţinu řádků, která odpovídá nějaké podmínce, potom transakce T2 smaţe nebo vloţí řádek, který také odpovídá podmínce z transakce T1 a je potvrzena. Pokud nyní T1 zopakuje původní dotaz, vrátí se jí rozdílný počet řádků, neţ v prvním případu.
1.3.2 Úroveň izolace podle SQL standardu SQL standard rozlišuje čtyři úrovně izolace transakcí – READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ a SERIALIZABLE. Úroveň izolace SQL transakce určuje úroveň, po jakou jsou data v této transakci ovlivňována paralelně běţícími transakcemi, a po jakou úroveň můţe tato transakce ovlivňovat data ostatních transakcí. Podle SQL standardu je ve všech čtyřech úrovních zaručeno, ţe transakce proběhne buď celá, nebo vůbec a ţe nemůţe dojít k fenoménu ztracené aktualizace. Implicitní úrovní izolace transakce je podle standardu SERIALIZABLE.
READ UNCOMMITTED READ COMMITTED REPEATABLE READ SERIALIZABLE
Dirty reads
Non-repeatable read
Phantom
možné nemožné nemožné nemožné
možné možné nemožné nemožné
možné možné možné nemožné
Tabulka 2: Úrovně izolace a fenomény podle standardu SQL Zdroj: (19) 14
1.4 Řízení souběžného přístupu Databázi lze zjednodušeně definovat také jako konečnou mnoţinu zdrojů, ke kterým paralelně přistupují uţivatelé (8). Uţivatelé interagují s databázovým systémem pomocí transakcí, coţ jak jsme si ukázali dříve, jsou sekvence operací čtení a zápisu. Transakci je v případě paralelního zpracování nutné brát nejen jako jednotku zpracování nebo práce, ale také jako jednotku konzistence, ve smyslu, ţe databázi dostává z jednoho konzistentního stavu do druhého. Řízení souběţného přístupu (Concurrency Control) má potom za úkol zajistit, ţe je konzistence zachována také při paralelním zpracování a přístupu ke zdrojům databáze.
1.4.1 Optimistické a pesimistické metody řízení souběžného přístupu Jedním z mechanismů poţívaným pro řízení souběţného přístupu jsou zámky. Transakce musí před přístupem k objektu získat zámek nad tímto objektem, příkladem těchto protokolů můţe být např. dvoufázové zamykání (podrobněji se budu těmito protokoly zabývat v kapitole 2.1). Protoţe tyto protokoly implicitně předpokládají, ţe můţe dojít ke konfliktu transakcí a předcházejí tomu tím, ţe objekt uzamknou, i kdyţ ke konfliktu nemusí dojít (a objekt uvolní, aţ kdyţ tato moţnost vyprší), označujeme je jako metody pesimistické (Pessimistic concurrency control).
Tento přístup je vhodnější pro prostředí s vyšším
výskytem konfliktů. Druhá skupina protokolů je postavena na předpokladu, ţe konflikt je málo častá situace a akce nutné k zajištění integrity databáze se tedy spouští pouze v případu, ţe k tomuto konfliktu dojde. Tento přístup se označuje jako optimistický (Optimistic concurrency control). Protokoly postavené na tomto přístupu neblokují ţádné operace a odsouvají test korektnosti transakce aţ na její závěr, pokud při závěrečném testu zjistí problém, transakci zruší, aby nedošlo k porušení integrity databáze. Protokoly s tímto přístupem jsou vhodné pro nasazení v systémech s malým mnoţstvím konfliktů a s vysokým podílem read-only transakcí. Příkladem tohoto přístupu jsou Validation-based protokoly (viz kapitola 2.3).
15
1.5 Uváznutí Korth a Silberschatz (11) definuje uváznutí (deadlock) jako stav systému, kde existuje taková mnoţina transakcí, ţe kaţdá transakce z této mnoţiny čeká na jinou transakci z této mnoţiny. Dále to upřesňuje - existuje mnoţina čekajících transakcí {T0, T1, ...,Tn} taková, ţe T0 čeká na datový objekt, který drţí T1, T1 čeká na objekt drţený transakcí T2, ..., Tn-1 čeká na objekt, který drţí Tn, která čeká na objekt drţený T0. V této situaci nemůţe pokračovat ţádná z transakcí. V okamţiku, kdy jiţ k uváznutí dojde, má databáze jedinou moţnost a to je zrušení některé z uváznutých transakcí. Existují dvě základní metody, jak se s problémem uváznutí vypořádat – prvním z nich je prevence (deadlock prevention), kde se snaţíme předejít samotnému vzniku uváznutí a druhá moţnost je dopustit vznik uváznutí, následně ho detekovat a zotavit se z tohoto stavu (deadlock detection and deadlock recovery). T1 SHARE_LOCK(X) READ(X)
T2
SHARE_LOCK(Y) READ(Y) LOCK(Y) LOCK(X) Obrázek 11: Jednoduchá ukázka uváznutí (deadlock) Zdroj: autor
1.5.1 Prevence Existují dva základní přístupy k prevenci uváznutí – jedním z nich je zabránění vzájemnému čekání pomocí řazení poţadavků na zámky nebo vyţadováním, aby všechny zámky byly získány najednou. Druhý přístup je částečně podobný detekci uváznutí a v případě, ţe by mohlo dojít k uváznutí, provede zrušení transakce.
16
Nejjednodušší realizací prvního přístupu je poţadavek na uzamčení všech datových objektů, které transakce bude vyuţívat, ještě před začátkem jejího běhu – budou tedy zamčeny všechny poţadované datové objekty, nebo ţádný. Nevýhodou této metody je například, ţe před začátkem transakce je velmi náročné predikovat objekty k uzamčení, nebo nízké vyuţití datových objektů, protoţe je mnoho z nich často zamčeno a to i po velmi dlouhou dobu. Tato metoda je pouţívána například v konzervativním dvoufázovém zamykání (Conservative 2PL, C2PL). Druhý protokol zaloţený na tomto přístupu vyţaduje setřídění všech datových objektů (např. pokud dochází k zamykání po datových blocích, můţeme pouţít třídění podle jejich fyzické adresy) a zajištění, ţe transakce zamyká objekty podle tohoto pořadí. Pokud transakce uzamkne objekt On, jiţ nemůţe dojít k poţadavku na uzamčení objektu On-1, který podle setřídění tomuto objektu předchází. Předpokládejme transakci T1, která čeká na zámek objektu O0, drţený T0; T2 čeká na zámek O1, drţený T1;...;Tn čeká na zámek na objektu On-1, drţený transakcí Tn-1 a T1 čeká na zámek objektu On, drţený transakcí Tn. Pokud T1 drţí zámek objektu O1 a čeká na zámek O0, musí platit, ţe O1
17
1.5.1.1 Wait-die Jedná se o nepreemtivní techniku – kdyţ transakce Ti datový objekt drţený transakcí Tj, transakci Ti bude umoţněno čekání pouze v případě, ţe její časová značka je niţší neţ časová značka transakce Tj, tedy transakce Ti musí být starší neţ transakce Tj. Pokud toto neplatí, transakce Ti je zrušena a provede se rollback. T1
T2
T3
T4
LOCK(A); READ(A) LOCK(A); Dies LOCK(B);READ(B) LOCK(A); Dies LOCK(C);WRITE(C) UNLOCK(B);UNLOCK(C) LOCK(B);WRITE(B) UNLOCK(A); UNLOCK(B) LOCK(A);LOCK(D) LOCK(A); Waits READ(D);WRITE(A) UNLOCK(A);UNLOCK(D) LOCK(A);WRITE(A)
Obrázek 12: Prevence uváznutí s algoritmem wait-die Zdroj: upraveno podle (6)
Typické pro wait-die algoritmus je, ţe starší transakce čeká, aţ mladší uvolní poţadovaný datový objekt, takţe čím je transakce starší, tím je více náchylná k čekání. Pokud je ve wait-die algoritmu transakce Ti zrušena a je proveden rollback, protoţe poţadovala data drţená transakcí Tj, můţe Ti, pokud je restartována, opět spustit stejnou sekvenci operací a pokud jsou data stále uzamčena transakcí Tj, dojde opět ke zrušení transakce Ti a tato situace se můţe stále opakovat, dokud nedojde k uvolnění poţadovaných dat. 1.5.1.2 Wound-wait Je preemptivní technika, jedná se o opak algoritmu wait-die - pokud transakce Ti poţaduje data drţená transakcí Tj, Ti bude čekat pouze v případě, ţe její časové razítko je vyšší neţ časové razítko Tj (tedy Ti je mladší neţ Tj), jinak je Tj zrušena (v algoritmu se pouţívá termín wounded) a je proveden její rollback. Na rozdíl od algoritmu wait-die, v algoritmu wound-wait starší transakce nikdy nečeká na mladší.
18
T1
T2
T3
T4
LOCK(A); READ(A) LOCK(A); Waits LOCK(B);READ(B) LOCK(A); Waits Wounded LOCK(B);WRITE(B) UNLOCK(A); UNLOCK(B) LOCK(A);LOCK(D) LOCK(A); Waits READ(D);WRITE(A) UNLOCK(A);UNLOCK(D) LOCK(A);WRITE(A)
Obrázek 13: Prevence uváznutí s algoritmem wound-wait Zdroj: upraveno podle (6)
Pokud transakce Tj poţaduje data drţená starší transakcí Ti, je transakce Ti zrušena a je proveden rollback. Pokud dojde k restartu transakce Ti, ta nyní čeká na uvolnění dat transakcí Tj, oproti algoritmu wait-die tedy můţe docházet k niţšímu výskytu operace rollback.
1.5.2 Timeout Řešení uváznutí pomocí časového limitu (timeout) je metodou na rozmezí mezi prevencí, kde k uváznutí nemůţe dojít, a detekcí. Funguje na jednoduchém principu, kdy je stanoven časový limit pro získání zámku a pokud se to transakci nepodaří, dojde ke zrušení transakce a je proveden rollback. Pokud tedy de facto jiţ došlo k uváznutí, po zrušení jedné z transakcí dojde k uvolnění a ostatní transakce mohou pokračovat. Tento algoritmus je poměrně jednoduchý na implementaci, ale je vhodný spíše pro systémy s kratšími transakcemi a je také citlivý na správné nastavení hodnoty čekání na získání zámku.
1.5.3 Detekce a zotavení Uváznutí se většinou týká pouze malého počtu transakcí, takţe můţe být výhodné, místo prevence, řešit tento problém aţ v případě, ţe k němu dojde. Aby to bylo moţné, musí databázový stroj periodicky monitorovat informace o zámcích, musí existovat algoritmus pro identifikaci uváznutí a systém musí provést zotavení z tohoto uváznutí. Pro popis a detekci uváznutí se pouţívá orientovaný graf, který se nazývá graf čekání (wait-for graph).
19
1.5.3.1 Wait-for graph Mnoţina uzlů tohoto grafu odpovídá mnoţině všech aktivních transakcí v systému, hranou je potom orientovaná dvojice Ti
Tj, kde transakce Ti čeká na uvolnění zámku
drţeného transakcí Tj. Manaţer zámků periodicky upravuje graf podle aktivních transakcí i jejich zámků (drţených i poţadovaných) a pokud v grafu vznikne cyklus, znamená to, ţe v systému došlo k uváznutí. Nejlépe si pouţití grafu čekání předvedeme na konkrétním příkladu - máme rozvrh čtveřice transakcí T1, T2, T3 a T4 (obrázek 9). T1 1 LOCK(A) 2 3 4 5 LOCK(B) 6 7 8
T2
T3
T4
LOCK(B) LOCK(C) LOCK(D) LOCK(C) LOCK(D) LOCK(A)
Obrázek 14: Rozvrh ilustrující vznik uváznutí Zdroj: autor
Nejprve vytvoříme graf čekání po provedení kroku 7, tedy přesně před vznikem uváznutí (obrázek 15).
T1
T2
T4
T3
Obrázek 15: Graf čekání před vznikem uváznutí Zdroj: autor
Pokud vytvoříme graf po provedení kroku 8 (obrázek 16), vidíme, ţe přibyla hrana T4 T1 a došlo ke vzniku cyklu – systém se tedy nyní nachází ve stavu uváznutí.
20
T1
T2
T4
T3
Obrázek 16: Graf čekání po vzniku uváznutí Zdroj: autor
1.5.3.2 Zotavení z uváznutí Pokud systém zjistí, ţe se nachází v uváznutí, musí se z této situace nějakým způsobem zotavit – nejčastějším řešením potom bývá zrušení některé z transakcí zapojených v uváznutí. Prvním krokem je obvykle výběr vhodné „oběti“ (victim selection) – měla by se vybrat transakce, jejíţ zrušení bude mít nejniţší nároky na zdroje. Zde se můţe projevit mnoho faktorů, např. jak dlouho jiţ transakce běţí, s kolika datovými objekty pracuje, kolik jich bude potřebovat pro své dokončení, kolik transakcí ovlivní případný rollback apod. Příkladem můţe být např. patent US7185339 společnosti Oracle – Victim selection for deadlock detection. Druhým krokem je samotné zrušení, rollback transakce. Nejjednodušším řešení je úplný rollback, tedy zrušení transakce a její restart. Efektivnější je zrušení pouze některých kroků transakce (partial rollback), ale to samozřejmě klade další nároky na systém - je nutné udrţovat dodatečné informace o stavu běţících transakcí (např. sekvence poţadavků a přidělení zámků) a samozřejmě musí být transakce po tomto částečném rollbacku schopna opět pokračovat. Problémem, který je nutné během zotavení řešit, je moţné stárnutí transakcí (starvation). K tomu můţe dojít, pokud je ke zrušení opakovaně vybrána stejná transakce, je tedy nutné zajistit, aby transakce mohla být vybrána pouze v konečném (a malém) počtu případů.
21
2 Metody používané pro řízení souběžného přístupu 2.1 Zámky Jedním ze způsobů, jak zajistit uspořádatelnost, je vyţadovat, aby přístup k datovým objektům (v případě databázového stroje jsou to většinou datové bloky nebo řádky v tabulce) byl exkluzivní, tedy pokud jedna transakce přistupuje k objektu, ţádná další ho nemůţe modifikovat. Nejobvyklejším způsobem, jak toto vynutit, je umoţnit transakci přistup k objektu pouze, pokud má v drţení zámek k tomuto objektu. Rozlišujeme dva základní módy uzamčení objektu – sdílený, který pokud transakce obdrţí, můţe objekt číst, ale nemůţe ho modifikovat. Exkluzivní zámek potom umoţňuje operace čtení i zápisu. Tabulka 3 zobrazuje moţnou kompatibilitu zámků poţadovaných různými transakcemi nad jedním objektem - pokud si tuto informaci spojíme s informací, jaká operace vyţaduje jaký zámek, asi nás nepřekvapí, ţe kompatibilita operací odpovídá kompatibilitě z tabulky 1 v kapitole o uspořádatelnosti, zvláště pokud si uvědomíme, ţe cílem zámků je zajistit uspořádatelnost transakčního rozvrhu. sdílený
exkluzivní
sdílený
ANO
NE
exkluzivní
NE
NE
Tabulka 3: Matice kompatibility zámků Zdroj: (11)
Pokud transakce Ti chce přistupovat k objektu O, musí nejprve získat zámek nad objektem O, pokud objekt O je jiţ uzamčen v nekompatibilním módu jinou transakcí, musí transakce Ti čekat, dokud nejsou všechny nekompatibilní zámky uvolněny. Vezměme dvě transakce T1={READ(A), WRITE(A)}a T2={READ(A)}, jejich rozvrh by s vyuţitím zámků mohl vypadat například jako na obrázku 17.
22
T1 LOCK-S(A) READ(A)
T2
LOCK-S(A) READ(A) UNLOCK(A) LOCK-X(A) WRITE(A) UNLOCK(A) Obrázek 17: Rozvrh transakcí s využitím zamykání Zdroj: autor
Je vidět, ţe transakce T2 mohla získat sdílený zámek na objektu A, protoţe sdílené zámky jsou vzájemně kompatibilní, ale transakce T1 jiţ musela čekat na získání exkluzivního zámku, dokud transakce T2 svůj sdílený zámek neuvolnila.
2.1.1 Dvoufázové zamykání (2PL) Jedním z reálných protokolů zaloţených na zámcích a zajišťujících uspořádatelnost je tzn. dvoufázové zamykání (two-phase locking – 2PL). Jedná se protokol široce rozšířený v komerčních databázových systémech, například v databázích Oracle, kde je vyuţíván ve spojení s multiverzováním (viz kapitoly 2.4 a 3). Základem 2PL protokolu jsou tři pravidla (1): 1. Pokud rozvrhovač obdrţí poţadavek na operaci, nejprve otestuje, jestli zámek potřebný pro tuto operaci není v konfliktu s jiţ existujícím zámkem. Pokud ano, rozvrhovač přinutí transakci čekat, dokud se nepodaří zámek přidělit. 2. Kdyţ transakce získá zámek, zámek nemůţe být uvolněn přinejmenším do doby, neţ byla dokončena operace vyţadující zámek. 3. Pokud byl jednou zámek uvolněn, nemůţe transakce jiţ transakce ţádný další zámek získat. Pravidlo tři je příčinou, proč se tento protokol nazývá dvoufázovým. Dělí totiţ transakci na dvě fáze – fázi zamykání (growing phase) a fázi odemykání (shrinking phase). V první fázi, fázi zamykání, můţe transakce získávat zámky, ale ţádný zámek nemůţe uvolnit. Ve druhé fázi můţe transakce zámky jiţ pouze uvolňovat (5). Tato základní varianta
23
dvoufázového zamykání není odolná proti uváznutí, ani proti kaskádovému abortu a také nezajišťuje zotavitelnost rozvrhu, ale jak si ukáţeme dále, zajišťuje jeho uspořádatelnost. Předpokládejme, ţe existuje mnoţina transakcí T0,T1,…,Tn, které splňují pravidla 2PL a mají neuspořádatelný rozvrh. Neuspořádatelný rozvrh znamená, ţe musí existovat cyklický precedenční graf, předpokládejme tady, ţe existuje precedenční graf obsahující cyklus T0 T1 … Tn-1 Tn T0. Ať ti je čas, kdy transakce Ti získala svůj poslední zámek (tento okamţik se nazývá lock point). Pro všechny transakce kde Ti Tj tedy platí ti
24
2.1.2 Strukturované zamykání Zatím jsme uvaţovali zamykání pouze na úrovni určitého objektu, v některých případech pro nás ovšem můţe být výhodnější seskupit objekty do větších celků a umoţnit zamčení těchto celků, tím minimalizovat počet zámků a sníţit reţii spojenou s jejich správou. Pro tyto účely se pouţívá tzv. strukturované zamykání (Multiple granularity locking), pro ilustraci uvaţujme například strukturu jako na obrázku 18. DB
A1
A2
Fb
Fa
ra1
ra2
…
Fc
ran
Obrázek 18: Strukturované zamykání Zdroj: upraveno podle (11)
Máme databázi, která se dělí na oblasti, kaţdá oblast obsahuje několik souborů, kaţdý soubor obsahuje záznamy. Kaţdý z uzlů je moţné zamknout individuálně, stejně jako v případě 2PL, budeme pouţívat sdílený a exkluzivní zámek. Pokud nyní transakce získá explicitně zámek na některém uzlu, všichni jeho potomci jsou implicitně také zamčeni a to ve stejném módu, jako tento uzel. Předpokládejme transakci Ti, která uzamkla celý soubor Fa, implicitně jsou také zamčeny všechny záznamy v tomto souboru. Následně chce transakce Tj zamknout záznam ra2, ale tento záznam není explicitně uzamčen! Systém tedy, aby zjistil, jestli je moţné záznam zamknout, musí projít hierarchický strom od jeho kořene aţ po záznam ra2 a pokud je některý z uzlů uzamčen v nekompatibilním módu, Tj musí čekat. Dále předpokládejme transakci Tk, která chce uzamknout celou databázi – jak ale systém pozná, ţe někde v celé struktuře není nekompatibilní zámek? Jednou z moţností je prohledat celý strom, tím se ale připravíme o výhodu tohoto konceptu. Lepší je zavést novou kategorii zámků – intenční zámky (intention lock) (1). Pokud je uzel uzamčen v intenčním módu, znamená to, ţe některý z potomků tohoto uzlu je explicitně uzamčen – intenční zámek je umístěn na všechny předchůdce uzlu dříve, 25
neţ je uzel explicitně uzamčen. Rozlišujeme tři nové druhy zámků: intenční sdílený (intention- shared) - explicitní zámky na niţší úrovni jsou pouze sdílené; intenční exkluzivní (intention-exclusive) – některý z explicitních zámků na niţší úrovni je exkluzivní; sdílený a intenčně exkluzivní zámek (shared and intention-exclusive) - podstrom tohoto uzlu je explicitně uzamčen sdíleným zámkem a některý z objektů na niţší úrovni je zamčen exkluzivním zámkem.
IS IX S SIX X
IS Ano Ano Ano Ano Ne
IX Ano Ano Ne Ne Ne
S Ano Ne Ano Ne Ne
SIX Ano Ne Ne Ne Ne
X Ne Ne Ne Ne Ne
Tabulka 4: kompatibilita zámků při strukturovaném zamykání Zdroj: (11)
2.2 Timestamp Ordering Tyto protokoly vyuţívají pro zajištění uspořádatelnosti techniku časových razítek (timestamp). Kaţdá transakce v okamţik svého vzniku obdrţí unikátní značku TS(Ti). Pokud transakce Ti obdrţí timestamp TS(Ti) a transakce Tj, která začne po transakci Ti, obdrţí timestamp TS(Tj), potom platí, ţe TS(Ti) < TS(Tj). Pro získání časového razítka se obvykle vyuţívají systémové hodiny nebo čítač, který se s kaţdou transakcí navýší, respektive kombinace obou těchto metod. Základním pravidlem Timestamp Ordering protokolu je: pokud operace Ii a Ij jsou konfliktní, potom je operace Ii provedena před Ij pokud platí, ţe TS(Ti) < TS(Tj). Představme si precedenční graf rozvrhu S, pokud existuje hrana precedenčního grafu Ti Tj, tak musí existovat dvojice konfliktních operací Ii a Ij, kde Ii < Ij. Jinak řečeno, podle pravidla Timestamp Ordering protokolu platí TS(Ti) < TS(Tj). Pokud v grafu existuje cyklus T0 T1 … Tn-1 Tn T0, potom musí také platit TS(T0) < TS(T0) a to není moţné, takţe není moţný ani vznik cyklu v precedenčním grafu a je zřejmé, ţe tento protokol zaručuje uspořádatelnost.
26
Časové razítko není přiřazováno pouze transakcím, ale také pro kaţdý objekt je definována dvojice časových razítek:
W-TS(O) – obsahuje časovou značku poslední transakce, která provedla úspěšný zápis do objektu O.
R-TS(O) – obsahuje časovou značku poslední transakce, která provedla úspěšné čtení objektu O. Předpokládejme transakci Ti, která chce provést operaci čtení na objektu O, vzhledem
k moţným konfliktním operacím mohou nastat dvě situace: TS(Ti) < W-TS(O), to znamená, ţe transakce Ti poţaduje hodnotu O, která jiţ byla přepsána, transakce bude tedy zrušena. TS(Ti) ≥ W-TS(O), transakce je novější neţ poslední modifikace objektu O, objekt O bude přečten a do R-TS(O) je přiřazena vyšší hodnota z R-TS(O) a TS(Ti). Předpokládejme, ţe transakce Ti chce modifikovat (zapsat) objekt O, tedy vyvolat operaci WRITE(O): TS(Ti) < R-TS(O), novější transakce přečetla objekt O, nemůţeme tedy provést modifikaci, protoţe tím by se data přečtená novější transakcí stala neplatná. Transakce bude zrušena. TS(Ti) < W-TS(O), transakce Ti se pokouší zapsat zastaralou hodnotu objektu O, dojde tedy ke zrušení transakce. V ostatních případech systém provede zápis a do W-TS(Ti) je vloţena hodnota TS(Ti). Jak jsme si jiţ dříve dokázali,
Timestamp Ordering
protokoly zajišťují
uspořádatelnost, kromě toho také zajišťují odolnost proti uváznutí, protoţe v tomto protokolu nedochází k čekání. Na druhou stranu můţe docházet ke stárnutí transakcí (starvation), pokud sekvence krátkých konfliktních transakcí opakovaně způsobí restart dlouhé transakce. Protokol také můţe vygenerovat nezotavitelený rozvrh, ale dá se rozšířit tak, aby tomuto problému bránil – to lze udělat například provedením všech operací WRITE najednou, aţ na konci transakce.
27
2.2.1 Thomas’ Write Rule Představme si, ţe rozvrhovač obdrţel operaci zápisu Wi(O) transakce Ti poté, co jiţ odeslal ke zpracování operaci zápisu Wj(O) pocházející od transakce Tj, ale zároveň platí TS(Ti)TS(Tj), provede se operace Wi(O) a změní se časové razítko W-TS(O), jinak se operace Wi(O) neprovede a dojde pouze ke změně časového razítka W-TS(O).
2.3 Multiversion concurrency control Cílem těchto protokolů je zajistit, aby transakce nikdy nečekala na operaci čtení (nebo dokonce nebyla zrušena). Princip je poměrně jednoduchý – během operace zápisu vyniká vţdy nová verze objektu, kaţdý zápis Wi(O) vytvoří vlastní verzi objektu Oi, starší verze objektů nejsou mazány, ale jsou k dispozici pro operace čtení. Jak se tyto nové vlastnosti projeví na konfliktních operacích? Víme, ţe dvě operace jsou konfliktní, pokud kaţdá náleţí k jiné transakci, obě pracují se stejným objektem a alespoň jedna z nich je WRITE. Pro potřeby mutliverzovacího protokolu je nutné tuto definici pouze lehce upravit s tím, ţe aby došlo ke konfliktu, musí obě operace přistupovat ke stejné verzi datového objektu (1)(2). Jaké konflikty jsou tedy moţné podle této upravené definice? Vezměme první typ konfliktu, kdy operace čtení předchází operaci zápisu: Ri(Oj) < Wj(Oj), je zřejmé, ţe k tomuto konfliktu dojít nemůţe, protoţe verze objektu nad kterou by k němu mohlo dojít, v okamţiku čtení ještě ani neexistuje. Konflikt mezi dvěma operacemi WRITE, Wi(Oi) < Wj(Oi) není také moţná, protoţe kaţdý zápis vytváří vlastní verzi objektu. Konflikt je moţný pouze v posledním případu, kdy operace WRITE předchází operaci READ, Wi(Oi) < Rj(Oi). Aby bylo moţné dokázat, ţe rozvrh podle MVCC je uspořádatelný, je třeba rozšířit teorii uspořádatelnosti o další dva typy rozvrhu nebo historie: více-verzový rozvrh (MV) a 28
jedno-verzový rozvrh (1V), který je interpretací uţivatelského pohledu na MV rozvrh jako na jednu verzi. Sériový 1V rozvrh je to, co uţivatel vnímá jako správné, je tedy třeba dokázat, ţe kaţdý z MV rozvrhů, které rozvrhovač můţe vytvořit, je ekvivalentní sériovému 1V rozvrhu (1). Vyjděme z definice konfliktové ekvivalence, která říká, ţe MV rozvrh SMV je ekvivalentní 1V rozvrhu S1V, pokud platí, ţe kaţdý pár konfliktních operací v SMV je ve stejném pořadí také v S1V. Nyní vezměme jednoduchý rozvrh SMV=W0(x0) C0 W1(x1) C1 R2(x0) W2(y2) C2 Vidíme, ţe jediné konfliktní operace jsou W0(x0) a R2(x0), nyní mapováním verzí objektu na korespondující objekt vytvoříme odpovídající 1V rozvrh S1V=W0(x) C0 W1(x) C1 R2(x) W2(y) C2 Je vidět, ţe jediné dvě konfliktní operace jsou ve stejném pořadí jako v MV rozvrhu, takţe podle definice konfliktové ekvivalence by rozvrhy mely být ekvivalentní. Kdyţ ale prozkoumáme, co čte transakce T2 v MV a co v 1V rozvrhu, zjistíme, ţe je zde rozpor – v MV rozvrhu čte T2 po T0, ale v 1V rozvrhu čte po T1. Konfliktovou ekvivalenci tedy nelze pouţít, protoţe operace v MC a 1V jsou z hlediska konfliktů rozdílné. Protoţe tedy konfliktová ekvivalence nejde pouţít, pouţijeme ekvivalenci pohledovou. Ta říká, ţe dva rozvrhy S a S' jsou pohledově ekvivalentní, pokud platí: transakce Ti čte první v S, tak musí číst první také v S', transakce Ti čte z Tj, tak musí stejně číst také v S' a pokud Ti poslední zapisuje v S, musí poslední zapisovat také v S'. Pokud nyní porovnáme oba rozvrhy, vidíme, ţe v SMV čte T2 z T0, ale v S1V čte z T1, tedy rozvrhy nejsou pohledově ekvivalentní. Jako další krok je nutné dokázat, ţe kaţdý MV rozvrh je ekvivalentní sériovému 1V rozvrhu. Bohuţel, jak si ukáţeme na příkladu, nelze jednoduše pouţít precedenční graf, protoţe existují takové MV rozvrhy, pro které neexistuje ekvivalentní 1V rozvrh. Představme si například MV rozvrh S1 S1=W0(x0) C0 R1(x0) W1(x1) C1 R2(x0) C2
29
Pokud kaţdou verzi objektu x budeme brát jako nezávislou, dostaneme precedenční graf na obrázku 18. T2 T1 T3 Obrázek 19: Precedenční graf MV rozvrhu Zdroj: autor
Nyní vytvořme sériový 1V rozvrh S2: S2=W0(x) C0 R1(X) W1(x) C1 R2(x) C2 Přestoţe S1 je sériový rozvrh a graf je acyklický, není rozvrh S1 pohledově ekvivalentní sériovému 1V rozvrhu S2, protoţe T2 čte v S1 z T0, ale v S2 čte z T1. Pouze podmnoţina sériových MV rozvrhů, která se označuje jako monoversion (v některé literatuře také jako 1-serial) rozvrhy, je ekvivalentní sériové 1V rozvrhu. Monoversion rozvrhem označujeme takový MV rozvrh, kde Ti čte x z Tj a Tj je nejnovější transakce před Ti, která zapsala nějakou verzi x. Všechny multiversion rozvrhy jsou ekvivalentní sériovým 1V rozvrhům, takţe abychom prokázali, ţe MVCC je korektní, musíme ukázat, ţe MV rozvrhy jsou ekvivalentní monoversion rozvrhům. Aby to bylo moţné, je třeba vyuţít tzv. multiversion precedenční graf a platí, ţe MV rozvrh je ekvivalentní monoversion rozvrhu, pokud jeho multiversion precedenční graf je acyklický1.
1
Formální důkaz např. (1)(2)(12) 30
2.3.1 Multiversion timestamp ordering Jako v kaţdém protokolu pracujícím na principu řazení časových razítek, je kaţdé transakci Ti před její exekucí přiřazen jedinečný timestamp TS(Ti). Kaţdý zápis datového objektu x vygeneruje novou verzi objektu xi a ke kaţdé verzi je přiřazeno časové razítko transakce, která ji vytvořila. Operace na datovém objektu rozvrhovač překládá do operací nad verzí tohoto objektu: při operaci Ri(x) nalezne verzi xk objektu x, kde Tk má nejvyšší timestamp TS(Tk) niţší neţ TS(Ti) a tuto verzi přečte. Operace čtení nemůţe nikdy čekat nebo být zrušena. Wi(x), pokud existuje operace čtení Rj(xk), kde platí TS(Tk) <=TS(Ti) <=TS(Tj), je operace Wi(x) zrušena a proveden restart transakce Ti. V ostatních případech je proveden zápis nové verze, nebo v případě i=k je přepsána verze xk. Jak je vidět, operace zápisu můţe být zrušena. Verze, které jiţ nejsou potřeba, jsou odstraňovány - verze xk a xj jsou verze objektu x, pokud platí TS(Tk) < TS(Ti) a zároveň TS(Tj) < TS(Ti), kde TS(Ti) je timestamp nejstarší transakce v systému, potom starší z verzí xj a xk je smazána. Tato základní verze protokolu není zotavitelná, ani odolná proti kaskádovému rušení. Rozšíření, které by tomuto bránilo, je moţné podobně jako u Timestamp protokolu.
2.3.2 Multiversion 2PL V klasickém 2PL protokolu můţe exkluzivní (pro zápis) zámek na objektu x zabránit transakci v získání sdíleného (pro čtení) zámku. Multiversion 2PL tento konflikt řeší pouţitím více verzí x – stejně jako pro ostatní MV protokoly platí, ţe operace zápisu vytvoří novou verzi objektu x a neblokuje tedy čtení. Kaţdá transakce dostane přiřazenu unikátní hodnotu transakčního čítače (jedná se vlastně opět o časové razítko), který se navyšuje s kaţdým potvrzením (commit) v databázi (příkladem tohoto čítače můţe být třeba SCN v databázích Oracle). Pokud transakce provádí operaci čtení, transakce získá sdílený zámek nad objektem a přečte verzi vytvořenou transakcí s hodnotou čítače nejvyšší niţší nebo rovnou čítači transakce, která čte. Pokud transakce provádí zápis, musí nejprve získat exkluzivní zámek, poté zapíše novou verzi, jejíţ čítač zatím nastaví na ∞. Po vykonání všech akcí transakce dojde k jejímu potvrzení – čítač se navýší o 1 a hodnota čítače se přiřadí verzi zapsané touto transakcí, dojde k uvolnění všech zámků. 31
Potvrzení můţe v daný okamţik provádět vţdy pouze jedna transakce. Mazání starých verzí probíhá obdobným způsobem jako v případě multiversion timestamp ordering protokolu. Popsaný protokol je zotavitelný a je odolný proti kaskádovému rušení, popsaná implementace je postavena na striktním 2PL, ale stejně jako striktní 2PL není odolná proti uváznutí.
2.4 Validation-based concurrency control V případech, kdy většina transakcí je read-only, můţe být počet konfliktů poměrně nízký a reţie spojená s řízením souběţného přístupu, jak jsme si ho ukázali v předchozích kapitolách zbytečně vysoká. V těchto případech tedy můţe být vhodné pouţít protokol, který je zaloţen na optimistickém přístupu, ţe ke konfliktu mezi transakcemi nedochází a případný konflikt řeší aţ na konci běhu transakce. V tomto protokolu kaţdá transakce proběhne ve třech fázích a v pořadí - čtení, validace a zápis: 1. Ve fáze čtení (read phase) jsou provedeny všechny operace transakce, data jsou přečtena z databáze a případné zápisy proběhnou do privátního pracovního prostoru. 2. V okamţiku potvrzení transakce (commit) nastává validační fáze. V jejím průběhu je otestováno, jestli by transakce mohla být v konfliktu s některou z paralelně běţících transakcí. Pokud je to moţné, transakce je zrušena, pracovní prostor je vyčištěn a transakce je restartována. 3. Pokud ve validační fázi není zjištěna moţnost konfliktu, nastává poslední fáze, zápis provedených změn. Data zapsaná do pracovního prostoru transakce jsou zkopírována do databáze.
32
Rozvrhovač pro validaci vyuţívá časová razítka transakcí a také informace o průběhu jednotlivých fází. Pro kaţdý pár transakcí Ti a Tj, kde TS(Ti)
33
3 Oracle RDBMS Relační databáze firmy Oracle je dnes nejrozšířenějším komerčním databázovým systémem a od verze 1 z roku 1978 dospěla aţ k aktuálně pouţívané verzi 11.2.
3.1 Implementace Concurrency Control v RDBMS Oracle Oracle pro zajištění konzistence a paralelního zpracování vyuţívá protokolu na základě dvoufázových zámků a udrţování více verzí (Multiversion 2PL) - Oracle podporuje konzistenci čtení jak na úrovni příkazu, tak na úrovni transakce (záleţí na pouţitém stupni izolace). Jako časové razítko (viz kapitola 2.3 Multiversion Concurrency Control) slouţí tzv. System Change Number (SCN). Zjednodušeně se jedná o číslo, které v čase definuje potvrzenou verzi databáze. Maximální hodnotou tohoto čísla je 248 a v okamţiku, kdy dosáhne maxima, dojde k vynulování. Toto má za následek vznik nové inkarnace databáze a s tím spojené následky jako zneplatnění předchozích záloh apod. V následujících kapitolách si ukáţeme, jaké zámky databáze vyuţívá, jak je implementováno MVCC a která omezení jsou s Oracle implementací spjaté. Začátkem transakce je v Oracle databázi vţdy začátek DML nebo DDL operace s výjimkou příkazu SELECT (pokud se nejedná o distribuovaný dotaz). Ukončení se v případu DML musí provést explicitně příkazem COMMIT nebo ROLLBACK, DML příkazy provedou potvrzení implicitně. Při sestavování transakcí je třeba si uvědomit, ţe dojde k potvrzení i provedením DDL operace a nakládat s nimi tedy opatrně.
3.1.1 Zámky Databáze Oracle pouţívá dvoufázové zamykání, v databázi jsou tedy dva základní módy zámků – sdílené a exkluzivní, kde nad daným objektem můţe existovat více sdílených zámků, ale pouze jediný exkluzivní. Oracle umoţňuje zamykat data jak na úrovni celé tabulky, tak na úrovni řádku. Exkluzivní zámek brání sdílení zdrojů a je nutné ho získat, pokud transakce potřebuje modifikovat data, tedy pouze transakce, která tento zámek získá, můţe tato data měnit. Ostatní transakce musí čekat, dokud není zámek uvolněn. Sdílený zámek umoţňuje sdílení zdrojů, více transakcí můţe získat tento zámek nad jedním objektem. Přístup k datům
34
můţeme rozlišit na čtení a zápis, kde čtení je dotaz na data, zápis je jejich modifikace. Pokud shrneme základní pravidla pro přístup k datům v Oracle databázi, jsou to: Řádek je zamčen pouze v případě modifikace. Pokud transakce má na daném řádku zámek pro zápis, blokuje tento zámek ostatní poţadavky na modifikaci daného řádku. Čtení nikdy neblokuje zápis. Při čtení řádku nedochází ke vzniku zámku nad tímto řádkem, jedinou výjimkou je příkaz SELECT…FOR UPDATE. Zápis nikdy neblokuje čtení. Pokud je řádek modifikován, databáze pouţije záznam řádku v UNDO segmentu (více viz kapitola 3.1.2 MVCC a Undo segment). Získání a uvolnění zámků probíhá v Oracle databázi automaticky na základě prováděných operací, ale také umoţňuje uţivatelům a vývojářům na úrovni transakce nebo připojení (session) vytvářet a řídit zámky manuálně. Databáze provádí automatickou konverzi zámků, pokud je třeba zvýšit restriktivnost jiţ existujícího zámku, ale nikdy neprovádí eskalaci zámků, tedy změnu granularity zámků – například v případě zamčení velkého mnoţství řádků v jedné tabulce nedojde k eskalaci tohoto zámku na zámek tabulky. Oracle, vzhledem k vyuţití zámků, není odolný proti uváznutí. Ochrana proti uváznutí je zaloţena na detekci s vyuţitím wait-for grafu a zrušení příslušného příkazu (statement-level rollback), zrušena je vţdy operace transakce, která uváznutí detekovala (více viz kapitola 3.3 Chyby spojené se souběţným přístupem). Protoţe Oracle nevyuţívá eskalaci zámků a zámky pro čtení, je četnost uváznutí poměrně nízká. Základními druhy zámků v Oracle databázi jsou DML zámky, DDL zámky a systémové zámky. Nejprve si představíme DDL a systémové zámky a poté se hlouběji zaměřím na DML zámky, které primárně souvisí s transakcemi a paralelním přístupem k datům. DDL zámky (data dictionary locks) jsou zámky datového slovníku - chrání definici objektů v době, kdy nad daným objektem nebo nad objektem, na který se daný objekt odkazuje, probíhá DDL příkaz a vţdy je zamčen pouze objekt, který je modifikován nebo na který je odkazováno. DDL zámek brání změně nebo smazání objektu a jeho získání či
35
uvolnění je vţdy zcela automatické, uţivatel nemůţe ţádným způsobem tento zámek explicitně vyţádat. Exkluzivní DDL zámek znemoţní ostatním získat jiný DDL nebo DML zámek. Většina DDL operací vyţaduje tento zámek a zámek je drţen po dobu trvání dané DDL operace a je ukončen automatickým potvrzením (commit). Sdílený DDL zámek umoţňuje konkurenci pro podobné DDL operace. Například při vytvoření pohledu, transakce získá sdílený DDL zámek na všechny tabulky pouţité v tomto pohledu. Ostatní transakce mohou také získat sdílený DDL zámek, ale nemohou získat exkluzivní. Stejně jako exkluzivní zámek i sdílený trvá po dobu běhu DDL příkazu a je automaticky ukončen potvrzením transakce. Systémové zámky chrání interní databázové a paměťové struktury. Uţivatel nemá ţádnou kontrolu nad jejich výskytem či dobou trvání. Jedná se o latche, mutexy a systémové zámky. 3.1.1.1 DML zámky Zámky řádků (row locks, TX locks) vznikají při operacích INSERT, UPDATE, DELETE, MERGE a SELECT…FOR UPDATE a jsou to zámky nad jednotlivými řádky tabulky a trvají, dokud není transakce ukončena příkazem COMMIT nebo ROLLBACK. Pokud transakce získá zámek na řádek tabulky, musí také získat příslušný zámek na celou tabulku. Informace o zámku je udrţována v hlavičce datového bloku, kde je udrţována identifikace transakce (transaction ID), která mění řádek v daném bloku, modifikovaný řádek potom obsahuje odkaz na tento záznam. Záznam zůstává v hlavičce bloku i po konci transakce. Kdyţ chce další transakce modifikovat řádek, pomocí transaction ID zjistí, jestli je zámek stále aktivní. Pokud ano, transakce čeká na notifikaci, ţe byl uvolněn, pokud ne, transakce získá zámek. Zámky tabulek (TM lock) jsou transakcí poţadovány v případě operací INSERT, UPDATE, DELETE, MERGE, SELECT…FOR UPDATE nebo LOCK TABLE a tento zámek je třeba k ochraně před konfliktními DML nebo DDL operacemi. ROW SHARE (RS) zámky indikují, ţe transakce, která drţí tento zámek na tabulce, má také zamčené řádky v této tabulce a zamýšlí je modifikovat. Jedná se o nejméně restriktivní tabulkový zámek.
36
ROW EXCLUSIVE TABLE (RX) zámek indikuje, ţe transakce modifikovala některé řádky. Ostatním transakcím umoţňuje se dotazovat na data v tabulce, vkládat nové řádky, měnit je, mazat nebo zamykat. SHARE TABLE (S) zámek umoţňuje ostatním transakcím spouštět dotazy nad tabulkou (s výjimkou SELECT…FOR UPDATE), ale modifikace je moţná pouze v případě, ţe transakce je jediná, která Share Table zámek drţí. Více transakcí můţe tento zámek drţet nad stejnou tabulkou souběţně, takţe tento zámek nezaručuje, ţe transakce bude moci modifikovat data v tabulce. SHARE ROW EXCLUSIVE TABLE (SRX) zámek je vice restriktivní neţ Share Table zámek, můţe ho vţdy drţet pouze jedna transakce. Zámek umoţňuje ostatním transakcím spouštět dotazy nad tabulkou (s výjimkou SELECT…FOR UPDATE), ale ţádná transakce nemůţe tabulku modifikovat. EXCLUSIVE TABLE (X) zámek je nejrestriktivnější, ostatním transakcím brání ve všech typech DML operací. DML operace SELECT INSERT UPDATE DELETE SELECT…FOR UPDATE
LOCK TABLE table IN
ROW SHARE MODE ROW EXCLUSIVE MODE SHARE MODE SHARE EXCLUSIVE MODE EXCLUSIVE MODE
Tabulka 5: DML zámky v Oracle databázi Zdroj: Oracle Database Concepts 10g Release 2 (10.2) (14)
37
zámek řádku
zámek tabulky
X X X X
RX RX RX RS RS RX S SRX X
DML operace SELECT INSERT UPDATE DELETE SELECT…FOR UPDATE
LOCK TABLE table IN
RX RX RX RS RS
kompatibilní zámky RS RX S SRX Y Y Y Y Y Y N N Y Y N N Y Y N N Y Y Y Y Y Y Y Y
X Y N N N N N
RX S
Y Y
Y N
N Y
N N
N N
SRX X
Y N
N N
N N
N N
N N
zámek tabulky
ROW SHARE MODE ROW EXCLUSIVE MODE SHARE MODE SHARE EXCLUSIVE MODE EXCLUSIVE MODE
Tabulka 6: kompatibilita tabulkových DML zámků v Oracle databázi Zdroj: Oracle Database Concepts 10g Release 2 (10.2) (14)
Jak je uvedeno jiţ dříve, Oracle databáze řídí zámky a zamykání zcela automaticky bez nutnosti intervence ze strany uţivatele nebo tvůrce aplikace, ale v některých případech můţe být výhodné tento implicitní způsob zamykání potlačit a převzít alespoň částečně kontrolu. Tato situace můţe nastat například při situaci, kdy je vyţadována konzistence čtení na úrovni transakce, nebo je aplikací poţadován exkluzivní přístup k nějakému zdroji, aby transakce nemusela čekat, aţ skončí ostatní transakce. Příkazy přepisující implicitní management zámků jsou SET TRANSACTION ISOLATION LEVEL, ALTER SESSION SET ISOLATION LEVEL, LOCK TABLE a SELECT…FOR UPDATE. Oracle také umoţňuje uţivateli definovat vlastní zámky pomocí package dbms_lock. Tyto uţivatelské zámky jsou zpravovány stejným způsobem jako ostatní zámky v databázi, včetně detekce uváznutí, ale ţádným způsobem s nimi nekolidují.
3.1.2 MVCC a Undo segment Databáze Oracle s vyuţitím MVCC zajišťuje dvě základní věci: Konzistenci čtení pro databázové dotazy, tedy všechny data vrácená jedním dotazem jsou potvrzená a odpovídají stejnému okamţiku v čase2. Čtení a zápisy se nikdy vzájemně neblokují.
2
Oracle nikdy neumoţňuje „Dirty Reads“, tedy čtení nepotvrzených dat 38
Okamţik v čase, ke kterému jsou data čtena, závisí na zvolené úrovni izolace – v případě úrovně „Read Committed“ tento okamţik odpovídá startu dotazu (Statement-level consistency). Pokud je zvolena úroveň „Serializable“ nebo „Read Only“, je tímto okamţikem čas vzniku transakce (Transaction-level consistency).
Obrázek 20: Undo segment Zdroj: Oracle Database Concepts 11g Release 2 (13)
Aby bylo moţné udrţovat tuto konzistenci čtení, je třeba zajistit mechanismus zajišťující vytváření a udrţování verze dat - Oracle pro tuto činnost vyuţívá datové struktury nazvané undo segmenty. Vţdy při startu transakce je tato transakce přiřazena k některému z undo segmentů, záznam o této transakci je zapsán do jeho transakční tabulky. Pokud v průběhu transakce dojde k modifikaci dat, je vytvořen tzv. undo záznam, který obsahuje původní obsah datového bloku a je zapsán do příslušného undo segmentu. Undo segment tedy obsahuje původní verze dat změněných nepotvrzenými nebo nedávno potvrzenými transakcemi. Databáze můţe tyto verze pouţít pro čtení konzistentního obrazu databáze nebo pro rollback zrušených transakcí a návrat zpět do konzistentního stavu. Samotný undo segment je tvořen extenty, do kterých transakce cyklicky zapisují měněné datové bloky. Obrázek 19 ukazuje dvojici transakcí T1 a T2, která začala psát do třetího extentu E3 - transakce v daný okamţik vţdy píše pouze do jediného extentu (current extent) a v okamţiku kdy zjistí, ţe daný extent je jiţ zaplněný, ověří dostupnost dalšího extentu. Pokud tento neobsahuje data ţádné aktivní transakce, začnou aktivní transakce zapisovat do tohoto extentu a případná uloţená data jsou přepsána. V případě, ţe následující extent jiţ obsahuje aktivní data, musí databáze vytvořit nový extent. Kdyţ se nyní vrátíme k obrázku 19 – pokud dojde k zaplnění extentu E3, databáze zjistí, jestli extent E4 obsahuje aktivní data. V případě, ţe ne, extent E4 je označen jako current extent a transakce pokračuje
39
se zápisem do tohoto extentu. Jinak databáze musí alokovat nový extent a pokračovat zápisem do tohoto extentu.
Obrázek 21: Konzistence čtení a undo segment Zdroj: Oracle Database Concepts 11g Release 2 (13)
Nyní si ukáţeme, jak je undo segment vyuţit pro zajištění konzistence. Zaměřme se na situaci znázorněnou na obrázku 20, je zřejmé, ţe příkaz SELECT započal v čase odpovídajícímu SCN=10023, dotaz tedy můţe vrátit pouze potvrzené řádky, které odpovídají tomuto SCN (SCN nejvyšší niţší nebo rovné 10023). Pokud transakce při čtení narazí na blok, jehoţ SCN je vyšší neţ tato hodnota (dva bloky s hodnotou SCN=10024), databáze pozná, ţe se jedná o změněný blok a pokusí se konzistentní obraz zrekonstruovat pomocí bloků uloţených v undo segmentu (v našem případě pomocí bloků konzistentních k SCN 10006 a 10021).
3.2 Úrovně izolace v Oracle databázi Z kapitoly 1.3 jiţ víme, ţe ANSI standard rozlišuje čtyři základní úrovně izolace transakce, jsou to read uncommitted, read committed, repeatable read a serializable. Ve
40
srovnání se standardem Oracle poskytuje tři úrovně izolace – READ COMMITTED, SERIALIZABLE a READ-ONLY. READ COMMITTED je implicitní úroveň izolace v Oracle databázi. V tomto nastavení kaţdý dotaz spuštěný transakcí vidí pouze data potvrzená před začátkem dotazu (nikoliv transakce) a je moţný výskyt neopakovatelného čtení (nonrepeatable read) a fantómů (phantom read). V případě read committed transakce dojde ke konfliktu zápisu, pokud se transakce pokusí modifikovat řádek tabulky jiţ změněný stále nepotvrzenou transakcí. Read committed transakce musí počkat, neţ je blokující transakce dokončena (příkaz commit nebo rollback). Session 1 SQL> select * from tab1; 1
2
Session 2
JMENO ADRESA ---------- ---------NOVAK PRAHA ZEMAN PRCICE SQL> update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; 1 row updated. SQL> select * from tab1; JMENO ADRESA ---------- ---------NOVAK PRAHA ZEMAN PRCICE SQL> update tab1 set adresa='PRAHA' where jmeno='ZEMAN';
3
4
dotaz vrací stejný výsledek jako v kroku 1, protože změna z kroku 2 nebyla potvrzena
1 row updated. SQL> select * from tab1; 5
JMENO ADRESA ---------- ---------NOVAK BOLESLAV ZEMAN PRCICE SQL> select * from tab1; JMENO ADRESA ---------- ---------NOVAK PRAHA ZEMAN PRAHA SQL> update tab1 set adresa='CHOMUTOV' where jmeno='NOVAK';
6
7 8 9
commit; 1 row updated.
41
protože změny stále nebyly potvrzeny, vidí každá transakce pouze své změny
příkaz musí čekat, protože se pokouší modifikovat řádek již zamčený druhou transakcí
Session 1 SQL> select * from tab1; 10
Session 2
JMENO ADRESA ---------- ---------NOVAK BOLESLAV ZEMAN PRCICE
11
commit; SQL> select * from tab1;
12
13
úroveň izolace read committed umožňuje vznik neopakovatelného čtení. Session 2 modifikovala tabulku tab1 a session1 vrátila při opakování dotazu jiné hodnoty než v kroku 10
JMENO ADRESA ---------- ---------NOVAK CHOMUTOV ZEMAN PRAHA SQL> select count(*) from tab1 where adresa='PRAHA'; COUNT(*) ---------1
14
SQL> update tab1 set ADRESA='PRCICE' where adresa='PRAHA';
15
1 row updated. commit; SQL> select count(*) from tab1 where adresa='PRAHA';
16
stejný dotaz jako v kroku 13 vrací jiný počet řádků, jeden řádek zmizel
COUNT(*) ---------0
Tabulka 7: Oracle - ukázky chování při izolaci read committed Zdroj: autor
V úrovni izolace SERIALIZABLE transakce vidí pouze změny potvrzené ještě před startem transakce (nikoli dotazu) a změny provedené transakcí samou. Pro serializable transakci se databáze jeví, ţe v daný čas běţí pouze ona, jakoby ţádný další uţivatel nemodifikoval data v databázi. Pokud je transakce spuštěna s úrovní izolace serializable, nemůţe dojít k ţádné ze tří anomálií definovaných v ANSI standardu, je garantováno, ţe dotaz vrátí stejný výsledek po celou dobu trvání transakce. Serializable transakce můţe modifikovat řádek tabulky pouze tehdy, kdy všechny změny tohoto řádku, provedené ostatními transakcemi, byly potvrzeny ještě před započetím této transakce. Pokud se transakce pokusí modifikovat data změněná nebo smazaná transakcí potvrzenou aţ po začátku serializable transakce, operace je zrušena s chybou ORA-08177: Cannot serializable access for this transaction. Ačkoliv z pohledu výskytu anomálií odpovídá tato úroveň izolace úrovni izolace serializable, dá se najít případ, kdy chování neodpovídá uspořádatelnému rozvrhu:
42
1 2 3
Session 1 create table tab1 (a number); create table tab2 (a number); alter session set isolation_level=serializable;
alter session set isolation_level=serializable;
4 5 6 7 8
Session 2
insert into tab1 select count(*) from tab2; insert into tab2 select count(*) from tab1; commit; commit; select count(*) from tab1;
9
COUNT(*) ---------0
select count(*) from tab2; 10
COUNT(*) ---------0
Tabulka 8: Oracle - chyba v úrovni izolace serializable Zdroj: autor
Oba závěrečné dotazy vrátí hodnotu 0, ale pokud spustíme transakce sériově, jeden z dotazů musí vrátit hodnotu 1, tedy se nejedná o uspořádatelný rozvrh, protoţe výsledek není ekvivalentní sériovému rozvrhu. Tato anomálie je způsobena tím, ţe ve skutečnosti Oracle databáze neposkytuje uspořádatelnost, ale snapshot isolation3. Jako poslední úroveň izolace se pro Oracle databází uvádí Read Only. Tato úroveň je obdobou serializable, ale jak je zřejmé jiţ podle názvu, read-only izolace nepovoluje modifikaci dat. Tato úroveň izolace neodpovídá ţádné úrovni podle ANSI standardu, tak se jí nebudeme hlouběji věnovat. Jak je uvedeno jiţ dříve, implicitní úrovní je read committed, pokud je třeba tuto úroveň změnit, je to moţné jak na
úrovni
uţivatelského
připojení
(příkaz
ALTER
SESSION
SET
ISOLATION_LEVEL=READ COMMITED|SERIALIZABLE), tak na úrovni transakce (příkaz SET TRANSACTION ISOLATION LEVEL READ COMMITED|SERIALIZABLE).
3
Existuje také rozšíření serializable snapshot isolation, které garantuje plnou uspořádatelnost. Tato modifikace je pouţita například v PostgreSQL 9.1. 43
Session 1 1
Session 2 alter session set isolation_level=serializable; SQL> select * from tab1; JMENO ADRESA ---------- ---------NOVAK CHOMUTOV ZEMAN PRCICE
2
3
SQL> update tab1 set adresa='PRAHA'; 2 rows updated.
4
commit; SQL> select * from tab1;
5
JMENO ADRESA ---------- ---------NOVAK CHOMUTOV ZEMAN PRCICE
6
commit;
v případě izolace serializable transakce nevidí žádné změny potvrzené po začátku serializable transakce
SQL> select * from tab1; JMENO ADRESA ---------- ---------NOVAK PRAHA ZEMAN PRAHA
7
8
SQL> update tab1 set adresa='CHOMUTOV'; 2 rows updated.
9
10
commit; SQL> update tab1 set adresa='PRCICE' where jmeno='NOVAK'; update tab1 set adresa='PRCICE' where jmeno='NOVAK' * ERROR at line 1: ORA-08177: can't serialize access for this transaction
Tabulka 9: Oracle - chování transakce při izolaci serializable Zdroj: autor
44
pokud se serializable transakce pokusí modifikovat řádky, již změněné jinou transakcí, potvrzenou po začátku serializable transakce, dojde k chybě ORA-08177
3.3 Chyby spojené se souběžným přístupem ORA-60 Deadlock detected je chyba, kterou databáze dává najevo, ţe detekovala uváznutí a provedla zrušení jedné z uvázlých operací. Nyní si na reálném příkladu ukáţeme vznik uváznutí, a jak se s ním databáze vypořádá. Session 1
0
1
Session 2
select * from t1; AB ---------- ----1 ORIG 2 ORIG 3 ORIG 4 ORIG 5 ORIG 6 ORIG 7 ORIG 8 ORIG 9 ORIG 10 ORIG update t1 set b='S1' where a<5; 4 rows updated. update t1 set b='S2' where a>5; 5 rows updated.
2 3
update t1 set b='S1' where a=6; WAIT update t1 set b='S2' where a=1; WAIT
4 5 6 7
8
ERROR at line 1: ORA-00060: deadlock detected while waiting for resource commit; commit; select * from t1; AB ---------- ----1 S2 2 S1 3 S1 4 S1 5 ORIG 6 S2 7 S2 8 S2 9 S2 10 S2
Tabulka 10: Uváznutí v Oracle databázi Zdroj: autor
45
Jak je vidět v Tabulce 10, v případě uváznutí dojde ke zrušení pouze poslední operace v transakci, ostatní změny zůstanou platné. Zároveň s vyhlášením chyby, databáze také vygeneruje soubor, obsahující informace o uváznutí, které mohou být uţitečné pro další
DEADLOCK DETECTED ( ORA-00060 ) [Transaction Deadlock] The following deadlock is not an ORACLE error. It is a deadlock due to user error in the design of an application or from issuing incorrect ad-hoc SQL. The following information may aid in determining the deadlock: Deadlock graph: Resource Name TX-00030007-006a9a5b TX-00040006-00766535
---------Blocker(s)-------process session holds waits 37 114 X 47 317 X
session 114: DID 0001-0025-0007F6EE session 317: DID 0001-002F-0007A6FD Rows waited on: Session 114: obj (dictionary objn Session 317: obj (dictionary objn
-
---------Waiter(s)--------process session holds waits 47 317 X 37 114 X
session 317: DID 0001-002F-0007A6FD session 114: DID 0001-0025-0007F6EE
rowid = 00792F9E - AAeS+eADBAAAjthAAF 7942046, file - 193, block - 146273, slot - 5) rowid = 00792F9E - AAeS+eADBAAAjthAAA 7942046, file - 193, block - 146273, slot - 0)
----- Information for the OTHER waiting sessions ----Session 317: sid: 317 ser: 62523 audsid: 687939519 user: 18/OPS$ORACLE flags: (0x45) USR/- flags_idl: (0x1) BSY/-/-/-/-/flags2: (0x40008) -/pid: 47 O/S info: user: oracle, term: UNKNOWN, ospid: 19296 image: oracle@sd01bo03 (TNS V1-V3) client details: O/S info: user: oracle, term: pts/3, ospid: 19295 machine: sd01bo03 program: sqlplus@sd01bo03 (TNS V1-V3) application name: SQL*Plus, hash value=3669949024 current SQL: update t1 set b='S2' where a=1 ----- End of information for the OTHER waiting sessions -----
analýzu.
46
ORA-1555 Snapshot too old je chyba konzistence čtení. Existují dvě hlavní příčiny této chyby – přepsání dat v rollback segmentu a přepsání transakčního slotu v rollback segmentu. Jak víme, Oracle pro dodrţení konzistence čte starší verze dat z rollback segmentů, ale zároveň je ţivotnost těchto dat garantována pouze po dobu trvání transakce. Scénář vzniku této chyby je tedy následující: 1. Dotaz nastartoval v čase T1 při SCN=40, kaţdý přečtený blok tedy musí odpovídat stavu databáze při SCN 40. 2. Pokud transakce při SCN=41 modifikuje řádek, je přepsán obsah datového bloku a původní obsah je uloţen do rollback segmentu. 3. Transakce je potvrzena příkazem commit. 4.
Pokud stále trvá dotaz z kroku 1 a potřebuje nyní přečíst blok změněný transakcí v bodě 2, musí přečíst verzi bloku, která odpovídá SCN=40. Kdyţ tuto verzi bloku nenajde v rollback segmentu, protoţe jiţ byla přepsána daty jiné transakce, je oznámena chyba ORA-1555.
Pokud transakce zapíše blok do rollback segmentu, je informace o této transakci zapsána do slotu v transakční tabulce rollback segmentu (tabulka je součástí hlavičky rollback segmentu) a pokud je transakce ukončena, je moţné příslušný slot opět pouţít. Scénář vzniku chyby je tedy obdobný jako v předchozím případě, pouze dojde k přepsání informace v transakčním slotu místo dat v rollback segmentu.
47
4 PostgreSQL PostgreSQL je pokročilý open-sorce databázový systém a spolu s MySQL je jedním z nejrozšířenějších open-source relačních databázových systémů. První prototyp, ještě jako Postgres, byl představen v roce 1988 a v roce 1989 se objevila verze 1. V roce 1994 byl přidán interpretr jazyka SQL a v roce 1996 došle ke změně názvu na PostgreSQL.
4.1 Implementace Concurrency Control v PostgreSQL Implementace řízení souběţného přístupu se v mnohém podobá implementaci v Oracle databázi – oba systémy pouţívají kombinaci MVCC a 2PL a zámky na úrovni řádek i tabulek. Oba systémy také pouţívají snapshot isolation, i kdyţ PostgreSQL od verze 9.1 vyuţívá také serializable snapshot isolation, coţ mu na rozdíl od Oracle umoţňuje plnou implementaci uspořádatelnosti. Transakci můţe v PostgreSQL tvořit jeden příkaz nebo skupina příkazů implicitní chování odpovídá nastavení autocommit=on a pokud chceme, aby transakci tvořilo více operací, je nutné příkazem BEGIN nebo START TRANSACTION začít transakční blok, ten je ukončen příkazem COMNMIT, ROLLBACK nebo ABORT. K DDL operacím se v rámci transakčního bloku přistupuje stejně jako k DML operacím, pokud se provede ROLLBACK nebo ABORT, je operace zrušena. V případu, kdyţ dojde v transakčním bloku k chybě, jsou výsledky všech operací zrušeny, nelze potvrdit ani operace, které proběhly bez chyby.
4.1.1 Zámky Stejně jako v databázi firmy Oracle i v PostgreSQL rozlišujeme zámky na úrovni tabulky a na úrovni řádku. Všechny tyto zámky jsou řízeny automaticky, ale je také moţné je vyvolat explicitně příkazem LOCK. Pokud je zámek transakcí jednou získán, je drţen aţ do konce transakce. ACCESS SHARE zámek. Tento zámek vzniká při příkazu SELECT nad čtenými tabulkami a je v konfliktu pouze s ACCESS EXCLUSIVE zámkem. ROW SHARE zámek vzniká při příkazu SELECT FOR UPDATE a SELECT FOR SHARE. Tento zámek brání získání zámků EXCLUSIVE a ACCESS EXLUSIVE.
48
ROW EXCLUSIVE zámek je v konfliktu se zámky SHARE, SHARE ROW EXCLUSIVE, EXCLUSIVE a ACCESS EXCLUSIVE. Tento mód tabulkového zámku je nutné nad cílovou tabulkou získat pro provedení operací modifikujících data tabulky, tedy příkazů UPDATE, DELETE a INSERT. SHARE UPDATE EXCLUSIVE, tento zámek chrání tabulku před paralelními změnami schématu a před operací VACUUM (k této operaci se vrátím v kapitole 4.1.2 Implementace MVCC). K jeho vzniku dochází při příkazech VACUUM (bez FULL), ANALYZE, CREATE INDEX CONCURRENTLY a některé příkazy ALTER TABLE. S tímto zámkem nelze zároveň získat zámky v módu SHARE UPDATE EXCLUSIVE, SHARE, SHARE ROW EXCLUSIVE, EXCLUSIVE a ACCESS EXCLUSIVE. SHARE zámek vzniká při příkazu CREATE INDEX (bez CONCURRENTLY) a brání souběţným změnám v datech. Tento mód je v konfliktu se zámky ROW EXCLUSIVE, SHARE UPDATE EXCLUSIVE, SHARE ROW EXCLUSIVE, EXCLUSIVE a ACCESS EXCLUSIVE. SHARE ROW EXCLUSIVE, tento zámek není implicitně vyvolán ţádným příkazem v PostgreSQL. Současně s tímto zámkem nelze získat ţádný z těchto zámků: ROW EXCLUSIVE, SHARE UPDATE EXCLUSIVE, SHARE, SHARE ROW EXCLUSIVE, EXCLUSIVE a ACCESS EXCLUSIVE. EXCLUSIVE zámek je kompatibilní pouze se zámkem ACCESS SHARE, paralelně s tímto zámkem je moţné pouze čtení. Tento mód tabulkového zámku není automaticky poţadován v případě ţádného PostgreSQL příkazu. ACCESS EXCLUSIVE je nekompatibilní se všemi ostatními tabulkovými zámky. Garantuje tedy svému drţiteli, ţe je jedinou transakcí přistupující k objektu. Je také jediným zámkem, který blokuje příkaz SELECT. Zámek v tomto módu je třeba pro operace ALTER TABLE, DROP TABLE, TRUNCATE, REINDEX, CLUSTER a VACUUM FULL. Také se jedná o implicitní mód zámku v případě příkazu LOCK TABLE.
49
Držený zámek Požadovaný zámek ACCESS SHARE
ROW SHARE
ROW EXCLUSIVE
SHARE UPDATE EXCLUSIVE
SHARE
SHARE ROW EXCLUSIVE
EXCLUSIVE
ACCESS SHARE
ACCESS EXCLUSIV E
X
ROW SHARE ROW EXCLUSIVE SHARE UPDATE EXCLUSIVE
X
X
X
X
X
X
X
X
X
X
X
X
X
X
SHARE
X
X
SHARE ROW EXCLUSIVE
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
EXCLUSIVE ACCESS EXCLUSIVE
X
Tabulka 11: Konflikty mezi tabulkovými zámky v PostgreSQL Zdroj: (15)
Ačkoliv tomu někdy název nenasvědčuje, všechny dosud uvedené zámky, jsou zámky na úrovni celé tabulky (table-level locks). Zámky řádků mají, obdobně jako v Oracle databázi, jediný účel – brání paralelnímu zápisu do stejného řádku a opět stejně jako v případě Oracle, blokují pouze zápis, nikdy čtení. Sdílený zámek řádku je vyvolán příkazem SELECT FOR SHARE. Exkluzivní zámek vzniká při DML operacích modifikujících data nebo příkazem SELECT FOR UPDATE (zde je rozdíl proti Oracle, kde v případě tohoto příkazu je získán sdílený zámek). Uváznutí je v PostgreSQL řešeno obdobně jako v Oracle databázi, také zde neexistuje ţádná prevence, ale dochází k uváznutí, jeho následné detekci a ke zrušení jedné z transakcí. Na rozdíl od Oracle zde dochází ke zrušení celé transakce, nikoliv pouze uváznuté operace. Session 1 1
postgres=# select * from tab3; col1 -----(0 rows)
2
postgres=# begin; BEGIN postgres=# begin; BEGIN
3 4
Session 2
postgres=# insert into tab3 values(1); INSERT 0 1 50
5
postgres=# update tab1 set col1=10; UPDATE 1
6
postgres=# update tab2 set col1=11; UPDATE 1
7
postgres=# update tab1 set col1=12;
8
postgres=# update tab2 set col1=22; ERROR: deadlock detected DETAIL: Process 6430 waits for ShareLock on transaction 1894; blocked by process 2974. Process 2974 waits for ShareLock on transaction 1893; blocked by process 6430. HINT: See server log for query details.
9
UPDATE 1 postgres=*# commit; COMMIT
10 11
databáze detekovala vznik uváznutí, došlo ke zrušení jedné z operací
je proveden rollback celé transakce
postgres=# commit; ROLLBACK
protože došlo ke zrušení celé transakce, není v tabulce tab3 žádný řádek
postgres=# select * from tab3; col1 12 -----(0 rows) Tabulka 12: Uváznutí v databázi PostgreSQL Zdroj: autor
4.1.2 Implementace MVCC Jak víme jiţ z předchozích kapitol, MVCC je zaloţeno na principu vytváření více verzí dat a řízení jejich viditelnosti podle průběhu transakcí. PostgreSQL tedy vytváří při zápisu nové verze řádků (PostgreSQL pro tyto verze řádků pouţívá termín tuple) a zároveň řídí viditelnost těchto dat pro transakce. Protoţe se stejně jako v Oracle jedná o MVCC, platí také obdobná pravidla - kaţdý dotaz vidí pouze změny potvrzené před jeho startem nebo změny v rámci vlastní transakce. PostgreSQL tedy při kaţdé modifikaci vytvoří v tabulce nový tuple, doplněný o dvojicí údajů xmin a xmax, kde xmin odpovídá identifikátoru transakce, která tuple vytvořila a xmax zase transakci, která ukončila jeho platnost. Insert provedený transakcí s ID=20 tedy vytvoří tuple s hodnotou xmin=20, xmax zůstane prázdný. Pokud později transakce s ID=25 daný tuple smaţe, xmin zůstane beze změny, ale do xmax se naplní hodnota 25. Operace update je potom kombinací předchozích dvou, pokud by předchozí transakce s ID=25 provedla update, původní tuple bude doplněn o hodnotu xmax=25 a zároveň vznikne nový tuple s xmin=25. 51
Session 1 postgres=# begin; BEGIN postgres=*# insert into mvcc_test values(1); INSERT 0 1 postgres=*# commit; COMMIT
Session 2
postgres=# select xmin,xmax,a from mvcc_test; xmin | xmax | a ------+------+--1963 | 0 | 1 (1 row)
V tabulce je nový řádek vytvořený transakcí 1963
postgres=# select xmin,xmax,a from mvcc_test; xmin | xmax | a ------+------+--1963 | 1964 | 1 (1 row)
Je stále vidět původní řádek vytvořený transakcí 1963 a zároveň je vidět, že jeho platnost ukončila transakce 1964
postgres=# select xmin,xmax,a from mvcc_test; xmin | xmax | a ------+------+--1964 | 0 | 11 (1 row)
Update je potvrzený, už je vidět pouze nový řádek transakce 1964
postgres=# select xmin,xmax,a from mvcc_test; xmin | xmax | a ------+------+--1964 | 1965 | 11 (1 row)
Platnost řádku byla ukončena transakcí 1965
postgres=# begin; BEGIN postgres=*# update mvcc_test set a=11; UPDATE 1
postgres=# commit; COMMIT
postgres=# begin; BEGIN postgres=*# delete from mvcc_test; DELETE 1
postgres=# commit; COMMIT Tabulka 13: PostgreSQL - implementace MVCC Zdroj: autor
Během startu dotazu systém zjistí aktuální transakční čítač a identifikátory všech běţících transakcí, tuple je potom pro dotaz viditelný pokud xmin: 52
Patří potvrzené transakci. Je niţší neţ transakční čítač získaný na začátku dotazu. Neodpovídá ţádné transakci, která byla v běhu při startu dotazu. a zároveň xmax: Je prázdný nebo patří zrušené transakci nebo Je vyšší neţ hodnota transakčního čítače na počátku dotazu nebo Odpovídá transakci, která byla při startu dotazu v běhu. Jak je vidět, kaţdá modifikace znamená buď vznik nového řádku nebo modifikaci některé z hodnot xmin/xmax, popřípadě kombinaci obojího, ţádná data se tedy z tabulky fyzicky nemaţou. Aby se zabránilo přílišnému růstu velikosti dat a dopadům na výkonnost, existuje v PostgreSQL procedura VACUUM, která v případě standardního běhu uvolní expirované řádky, takţe je moţné je přepsat, nebo v případě VACUUM FULL tabulku fyzicky přeskládá a uvolní místo na souborovém systému.
4.2 Úrovně izolace v PostgreSQL PostgreSQL umoţňuje nastavit všechny čtyři úrovně izolace podle ANSI standardu, ale ve skutečnosti se interně pouţívají pouze tři z nich, READ COMMITTED, REPEATABLE READ a SERIALIZABLE. Při volbě READ UNCOMMITTED se de facto systém chová jako při READ COMMITTED a při REPEATABLE READ není moţný výskyt fantomů. Defaultní nastavení odpovídá READ COMMITED a nastavení lze změnit na úrovni transakce příkazem SET TRANSACTION ISOLATION LEVEL, na úrovni uţivatelského připojení pomocí příkazu SET
SESSION CHARACTERISTICS AS
TRANSACTION ISOLATION LEVEL, nebo lze změnit defaultní nastavení pro pomocí parametru default_transaction_isolation. READ COMMITTED je implicitním nastavením izolace transakcí, dotaz v této izolaci vidí pouze změny potvrzené před jeho startem (statement-level read consistency) a nepotvrzené změny provedené v rámci téţe transakce, ve které je spuštěn. Dva stejné dotazy spuštěné v rámci jedné transakce tedy mohou vrátit různá data.
53
Session 1 postgres=# begin; BEGIN
1
Session 2
postgres=# begin; BEGIN
2
3
4
postgres=# select * from tab1; jmeno | adresa -------+-------NOVAK | PRAHA ZEMAN | PRCICE (2 rows) postgres=# update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; UPDATE 1 postgres=# select * from tab1; jmeno | adresa -------+-------NOVAK | PRAHA ZEMAN | PRCICE (2 rows) postgres=# update tab1 set adresa='PRAHA' where jmeno='ZEMAN'; UPDATE 1
5
6
7
postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | PRCICE NOVAK | BOLESLAV (2 rows)
transakce vidí nepotvrzené změny, které sama provedla
8
postgres=# select * from tab1; jmeno | adresa -------+-------NOVAK | PRAHA ZEMAN | PRAHA (2 rows)
9
postgres=# update tab1 set adresa='CHOMUTOV' where jmeno='NOVAK';
10 11 12
13 14 15
dotaz vrací stejný výsledek jako v kroku 3, protože změna z kroku 4 nebyla potvrzena
postgres=# commit; COMMIT UPDATE 1 postgres=# begin; BEGIN postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | PRCICE NOVAK | BOLESLAV (2 rows) postgres=# commit; COMMIT postgres=# begin; BEGIN 54
protože změny stále nebyly potvrzeny, vidí každá transakce pouze své změny
příkaz musí čekat, protože se pokouší modifikovat řádek již zamčený druhou transakcí
16
17
postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | PRAHA NOVAK | CHOMUTOV (2 rows) postgres=# select count(*) from tab1 where adresa='PRAHA'; count ------1 (1 row) postgres=# update tab1 set ADRESA='PRCICE' where adresa='PRAHA'; UPDATE 1 postgres=# commit; COMMIT
18 19
20
úroveň izolace read committed umožňuje vznik neopakovatelného čtení. Session 2 modifikovala tabulku tab1 a session1 vrátila při opakování dotazu jiné hodnoty než v kroku 10
postgres=# select count(*) from tab1 where adresa='PRAHA'; count ------0 (1 row)
stejný dotaz jako v kroku 17 vrací jiný počet řádků, jeden řádek zmizel (fantom)
Tabulka 14: PostgreSQL - Read Committed izolace Zdroj: autor
55
Úroveň izolace REPEATABLE READ odpovídá úrovni SERIALIZABLE v databázi Oracle, transakce vidí pouze změny potvrzené před jejím startem nebo změny provedené jí samou. Tato úroveň vylučuje všechny tři anomálie podle ANSI standardu, ale nezaručuje uspořádatelnost rozvrhu. Stejně jako v Oracle je nutné počítat s moţnou chybou v uspořádatelnosti, pokud se transakce pokusí modifikovat řádky, jiţ paralelně modifikované jinou potvrzenou transakcí. Session 1 1
create table t1 (a int);
2
create table t2 (a int); postgres=# SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL REPEATABLE READ; SET postgres=# begin; BEGIN
3
postgres=# SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL REPEATABLE READ; SET postgres=# begin; BEGIN
4
5
postgres=# insert into t1 select count(*) from t2; INSERT 0 1 postgres=# insert into t2 select count(*) from t1; INSERT 0 1
6 7
Session 2
postgres=# commit; COMMIT postgres=# commit; COMMIT
8 postgres=# select * from t1; a --0 (1 row)
Transakce vidí snímek databáze, jak vypadala v okamžiku startu transakce, tedy jako by v databázi byla sama
9
10 11
postgres=# select * from t2; b --0 (1 row) postgres=# begin; BEGIN postgres=# begin; BEGIN
56
postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | CHOMUTOV NOVAK | CHOMUTOV (2 rows)
12
13
postgres=# update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; UPDATE 1 postgres=# commit; COMMIT postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | CHOMUTOV NOVAK | CHOMUTOV (2 rows) postgres=# commit; COMMIT postgres=# select * from tab1; jmeno | adresa -------+---------ZEMAN | CHOMUTOV NOVAK | BOLESLAV (2 rows)
14
15
16
17
postgres=# begin; BEGIN postgres=# begin; BEGIN
18
19
20
v případě izolace repeatable read transakce nevidí žádné změny potvrzené po začátku transakce
postgres=# update tab1 set adresa='BOLESLAV'; UPDATE 2 postgres=# commit; COMMIT postgres=*# update tab1 set adresa='PRCICE' where jmeno='NOVAK'; ERROR: could not serialize access due to concurrent update
pokud se transakce v izolaci repeatable read pokusí modifikovat řádky, již změněné jinou transakcí, potvrzenou po začátku serializable transakce, dojde k chybě
Tabulka 15: PostgreSQL - Repeatable Read izolace Zdroj: autor
Izolace SERIALIZABLE poskytuje nejstriktnější izolaci transakce a emuluje sériové provedení transakcí, jakoby transakce byly provedeny postupně, nikoliv paralelně.
57
Samozřejmě stejně jako v případě REPEATABLE READ je nutné počítat s výskytem moţných chyb uspořádatelnosti, pokud nelze rozvrh provést jako sériový. Tato úroveň izolace pracuje obdobně jako REPEATABLE READ, pouze navíc sleduje podmínky, které mohou způsobit, ţe transakční rozvrh nebude ekvivalentní s ţádným sériovým rozvrhem. Při tomto monitoringu nedochází k ţádnému blokování transakcí, ale je sním spojena jistá reţie a v případě detekce podmínek, které by mohly způsobit nemoţnost uspořádatelnosti rozvrhu, dojde k vyvolání chyby. Session 1 1
Session 2
postgres=# SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE; SET postgres=# SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE; SET
2
3
4
postgres=# select * from tab; class | val -------+----1 | 10 1 | 20 2 | 100 2 | 200 (4 rows) postgres=# begin; BEGIN postgres=# begin; BEGIN
5
6
postgres=# select sum(val) from tab where class=1; sum ----30 (1 row) postgres=# insert into tab values(2,30); INSERT 0 1 postgres=# select sum(val) from tab where class=2; sum ----300 (1 row)
7
postgres=# insert into tab values(1,300); INSERT 0 1 8
postgres=# commit; COMMIT
58
postgres=# commit; ERROR: could not serialize access due to read/write dependencies among transactions DETAIL: Reason code: Canceled on identification as a pivot, during commit attempt. HINT: The transaction might succeed if retried.
9
Tabulka 16: PostgreSQL - serializable izolace Zdroj: autor
Technika zajišťující tuto úroveň izolace se nazývá Serializable Snapshot Isolation (SSI) a poprvé byla představena v roce 2008 (3). V PostgreSQL je nově od verze 9.1, do této verze SERIALIZABLE odpovídalo úrovni izolace REPEATABLE READ. Zjednodušeně se jedná o techniku snapshot isolation (a také přebírá mnohé z výhod této techniky – čtení neblokuje nic, zápis neblokuje čtení) doplněnou o monitoring konfliktů zápisu a čtení mezi transakcemi a hledání moţných nebezpečných struktur v precedenčním grafu, které by mohly vést k anomáliím ve zpracování rozvrhu. V případě, ţe je toto nebezpečí objeveno, dojde ke zrušení transakce, aby nemohlo dojít k porušení uspořádatelnosti. Můţe dojít k falešně pozitivnímu nálezu (tedy je zrušena transakce, i kdyţ by reálně k porušení uspořádatelnosti nedošlo), ale nikdy nemůţe dojít ke vzniku anomálie ve zpracování.
5 Závěr Pokud porovnáváme implementaci řízení paralelního přístupu k datům ve dvou diskutovaných databázích, zjistíme, ţe na první pohled se jedná o velmi podobné implementace, ale pokud se se zaměříme na detail, nalezneme některé rozdíly, které mají poměrně velký dopad. Obě databáze pouţívají MVCC a snapshot isolation, a obě také pouţívají dvoufázového zamykání ve spojení se strukturovanými zámky na úrovni tabulek a řádků. Ani jeden ze systémů neprovádí eskalaci zámků. V čem především se oba systémy liší, je způsob implementace MVCC – Oracle vyuţívá rollback segmenty, takţe zápis různých verzí dat nemá přímý dopad na tabulky a jejich velikost, také případné operace nad tabulkami jsou rychlejší, protoţe nemusí fyzicky číst všechny verze řádků. Na druhou stranu je tato implementace náchylná k výskytu chyby ORA-1555, kdy dotaz v rollback segmentu jiţ nenalezl potřebné datové bloky pro zajištění konzistence čtení. Výskyt této chyby se dá omezit nastavením dostatečné velikosti prostoru pro rollback segmenty (undo tablespace) ve spojení s parametrem
UNDO_RETENTION, popřípadě ještě ve spojení s RETENTION
GUARANTEE klauzulí (s tímto nastavením je však nutné být opatrný). PostgreSQL pouţívá 59
implementaci, která umoţnuje rychlý rollback (pouze změna příznaku v řádku) a je odolná proti chybě obdobné ORA-1555. Na druhou stranu vyţaduje pravidelné spouštění příkazu VACUUM nebo VACUUM FULL (ten ale výrazně zatěţuje systém a na poměrně dlouhou dobu můţe uzamknout tabulky). Také v případě tabulek, kde se provádí mnoho změn, můţe tato implementace vést ke značnému nárůstu velikosti tabulek a s tím spojenému dopadu na výkonnost databázového stroje. PostgreSQL má ve verzi 9.1 oproti Oracle databázi také implementovanou podporu skutečné uspořádatelnosti, Oracle umoţnuje pouze snapshot isolation a ačkoliv tato izolace brání výskytu anomálií, jak to vyţaduje standard ANSI, je nutné se specifiky této techniky počítat (na druhou stranu, velké mnoţství databází funguje v implicitně nastavené úrovni izolace read committed). Obě databáze vyuţívají pokročilé techniky pro řízení souběţného přístupu (i kdyţ základy těchto technik jsou staré téměř jako samy relační databáze, jejich implementace je v některých databázových systémech poměrně čerstvá) a určitě patří k jedněm z nejvyspělejších databázových systémů. Zajímavé je porovnat chování těchto dvou databází zaloţených na MVCC s databází, která MVCC neposkytuje, např. databázovým systémem Teradata. Řízení souběţného přístupu v Teradata databázi je zaloţeno na striktním dvoufázovém zamykání (S2PL) a to přináší poměrně významné rozdíly v chování databáze. První rozdíl je v nabízených úrovních izolace, Teradata nabízí dvě – pro S2PL přirozenou úroveň SERIALIZABLE (implicitní úroveň izolace pro Teradata databázi) a potom také, při vyuţití tzv. access zámků, úroveň READ UNCOMMITTED (tuto úroveň databáze zaloţené na MVCC poskytnout nemohou). Nevyuţití MVCC sebou při izolaci SERIALIZABLE přináší nevýhody typické pro 2PL protokoly – čtení je blokováno zápisem a čtení blokuje zápis.
ACCESS/CHECKSUM ACCESS/CHECKSUM Y READ Y WRITE Y EXCLUSIVE N
READ Y Y N N
WRITE Y N N N
EXCLUSIVE N N N N
Tabulka 17: Kompatibilita zámků v Teradata RDBMS Zdroj: upraveno podle (16)
Při nastavení úrovně izolace READ UNCOMMITTED dojde ke změně přísnosti (severity) zámku pouţitého pro dotaz, z READ na ACCESS, se všemi důsledky z toho plynoucími: čtení jiţ neblokuje zápis a je moţné číst právě měněná data. Jediným nekompatibilním zámkem s ACCESS je EXCLUSIVE, který vzniká na tabulce nebo databázi v případě 60
strukturálních změn. Jak je zřejmé z předchozího popisu 2PL protokolu, přináší implementace uspořádatelnosti s vyuţitím této techniky poměrně závaţné nedostatky, jako je blokování čtení zápisem, blokování zápisu čtení a s tím spojená vyšší pravděpodobnost uváznutí. Ačkoliv se zdá implementace pouţitá v Teradata databázi méně vhodná, neţ MVCC v Oracle nebo PostgreSQL, je třeba si uvědomit k jakému typu zpracování je tato databáze určena. Teradata je systém určený pro OLAP úlohy a pro tyto úlohy je typické dávkové zpracování a velké objemy zpracovávaných dat. Dávkové zpracování sniţuje riziko blokování zápisu čtením a naopak velké objemy ukládaných dat nejsou příliš vhodné pro MVCC, protoţe to znamená velkou náročnost na diskový systém. Případné moţné konflikty dávek nahrávajících data a dotazů uţivatelů se potom v praxi řeší například vybudováním vrstvy pohledů s nastaveným modifikátorem zámku na ACCESS, takţe případný dotaz spuštěný v nevhodný čas nemůţe blokovat dávky zapisující nová data. Domnívám se, ţe tato práce, zamýšlená především jako rešeršní, splnila svůj cíl a přinesla základní přehled technik pouţívaných pro zajištění paralelního přístupu k datům v databázových systémech (jedná se především o relační SQL databáze). Dalším výsledkem jsou také praktické ukázky chování obou databázových systémů ve vybraných scénářích, které potvrzují vlastnosti dané implementace.
61
Seznam použité literatury 1. BERNSTEIN, Philip A, Vassos HADZILACOS a Nathan GOODMAN. Concurrency control and recovery in database systems. Reading, Mass.: Addison-Wesley Pub. Co., c1987, 370 s. ISBN 02-011-0715-5. 2. BERNSTEIN, Philip A. a Nathan GOODMAN. Multiversion concurrency control-theory and algorithms. In: ACM Transactions on Database Systems, Vol.8, No.4., New York: ACM, 1983, s. 465-483. ISSN 03625915. DOI: 10.1145/319996.319998. Dostupné z: dl.acm.org 3. CAHILL, Michael J., Uwe RÖHM a Alan D. FEKETE. Serializable isolation for snapshot databases. In: SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data. New York: ACM, 2008, s. 729-738. ISBN 978-160558-102-6. DOI: 10.1145/1376616.1376690. 4. CAREY, Michael J. a WALEED A. MUHANNA. The Performance of Multiversion Concurrency Control Algorithms. In: ACM Transactions on Database Systems, Vol. 4, No. 4., New York: ACM, 1986, s. 338-378. DOI: 10.1145/6513.6517. Dostupné z: dl.acm.org 5. ELMASRI, Ramez a Shamkant B. NAVATHE. Fundamentals of Database Systems. 4th ed. Boston: Pearson/Addison-Wesley, 2003, 1030 s. ISBN 03-211-2226-7. 6. GARCIA-MOLINA, Hector, Jeffrey D. ULLMAN a Jennifer WIDOM. Database Systems: The Complete Book. New Jersey: Prentice Hall, 2002, 1119 s. ISBN 01-3031995-3. 7. KUNG, H.T. a John T. ROBINSON. On Optimistic Methods for Concurrency Control. In: ACM Transactions on Database Systems (TODS) Volume 6 Issue 2. New York: ACM, 1981. DOI: 10.1145/319566.319567. 8. MENASCÉ, Daniel A. a Tatuo NAKANISHI. Optimistic versus pessimistic concurrency control mechanisms in database management systems. In: Information Systems, Volume 7, Issue 1. 1982, s. 13-27. DOI: 10.1016/0306-4379(82)90003-5. 9. POKORNÝ, Jaroslav a Ivan HALAŠKA. Databázové systémy. Vyd. 2. Praha: ČVUT, 2004, 148 s. ISBN 80-010-2789-9. 10. RAMAKRISHNAN, Raghu a Johannes GEHRKE. Database management systems. 2nd ed. Boston: McGraw-Hill, c2000, 906 s. ISBN 00-723-2206-3.
11. SILBERSCHATZ, Abraham, Henry KORTH a S. SUDARSHAN. Database system concepts. Vyd. 5. Boston: McGraw-Hill, 2006, 1142 s. ISBN 00-729-5886-3. 12. WEIKUM, Gerhard a Gottfried VOSSEN. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. San Francisco: Morgan Kaufmann, 2002, 852 s. ISBN 15-586-0508-8.
Internetové zdroje 13. Dokumentace Oracle Database, 11g Release 2 (11.2) [online]. [cit. 2012-06-01]. Dostupné z: http://www.oracle.com/pls/db112/homepage 14. Dokumentace Oracle Database, 10g Release 2 (10.2) [online]. [cit. 2012-06-01]. Dostupné z: http://www.oracle.com/pls/db102/homepage 15. Dokumentace PosgreSQL a wiki [online]. [cit. 2012-06-01]. Dostupné z: http://www.postgresql.org 16. Dokumentace Teradata Database 13.10 [online]. [cit. 2012-06-01]. Dostupne z: http://www.info.teradata.com/templates/eSrchResults.cfm?prodline=&txtpid=&txtrelno= &txtttlkywrd=TDBS13.10&rdsort=Title&srtord=Asc&nm=Teradata+Database+13.10 17. Bruce Momjian: MVCC Unmasked [online]. [cit. 2012-06-01]. Dostupné z: http://momjian.us/main/writings/pgsql/mvcc.pdf 18. Bruce Momjian: PostgreSQL Internals Through Pictures [online]. [cit. 2012-06-01]. Dostupné z: http://momjian.us/main/writings/pgsql/internalpics.pdf 19. My Oracle Support [online]. [cit. 2012-06-01]. Dostupné z: http://support.oracle.com 20. SQL92 standard, ISO/IEC 9075:1992, Database Language SQL [online]. [cit. 2012-06-01]. Dostupné z: http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt
Seznam zkratek a termínů v anglickém jazyce 2PL
2-phase locking
C2PL
Conservative 2-phase locking
MVCC
Multiversion Concurrencz Control
MV
Multiversion
S2PL
Strict 2-phase locking
Abort
zrušení transakce
Cascading abort
kaskádové rušení
Commit
potvrzení transakce
Concurrency Control
řízení souběţného (paralelního) zpracování
Conservative two-phase
konzervativní dvoufázové zamykání
locking Deadlock
uváznutí
Multiple granularity
strukturované zamykání
locking Multiversion Concurrency
řízení souběţného zpracování zaloţené na udrţování více verzí
Control
měněných objektů
Rollback
vrácení změn provedených zrušenou transakcí
Schedule
rozvrh
Scheduler
rozvrhovač
Serializability
uspořádatelnost
Serializable snapshot
rozšíření snapshot isolation, které umoţňuje uspořádatelnost
isolation Snapshot isolation
technika v MVCC, kdy transakce vidí izolovaný snímek databáze, který odpovídá okamţiku vzniku této transakce
Starvation
stárnutí transakce (opakovaný restart transakce)
Strict two-phase locking
striktní dvoufázové zamykání
Timestamp Ordering
uspořádání podle časových razítek
Two-phase locking
dvoufázové zamykání
Seznam obrázků
Obrázek 1: Nezotavitelný rozvrh ...................................................................................................................8 Obrázek 2: Zotavitelný rozvrh .......................................................................................................................8 Obrázek 3: Kaskádové rušení .........................................................................................................................9 Obrázek 4: Sériový rozvrh 1 ..........................................................................................................................9 Obrázek 5: Sériový rozvrh 2 ..........................................................................................................................9 Obrázek 6: Precedenční graf rozvrhu transakcí ...........................................................................................11 Obrázek 7: Vztah mezi různými druhy rozvrhů ...........................................................................................12 Obrázek 8: Ztráta aktualizace .......................................................................................................................13 Obrázek 9: Rozvrh s výskytem dirty read ....................................................................................................13 Obrázek 10: Rozvrh s neopakovatelným čtením ..........................................................................................14 Obrázek 11: Jednoduchá ukázka uváznutí (deadlock) .................................................................................16 Obrázek 12: Prevence uváznutí s algoritmem wait-die ................................................................................18 Obrázek 13: Prevence uváznutí s algoritmem wound-wait ..........................................................................19 Obrázek 14: Rozvrh ilustrující vznik uváznutí.............................................................................................20 Obrázek 15: Graf čekání před vznikem uváznutí .........................................................................................20 Obrázek 16: Graf čekání po vzniku uváznutí ...............................................................................................21 Obrázek 17: Rozvrh transakcí s vyuţitím zamykání ....................................................................................23 Obrázek 18: Strukturované zamykání ..........................................................................................................25 Obrázek 19: Precedenční graf MV rozvrhu .................................................................................................30 Obrázek 20: Undo segment ..........................................................................................................................39 Obrázek 21: Konzistence čtení a undo segment ...........................................................................................40 Obrázek 22: Ukázka trace soboru pro chybu ORA-60.................................................................................46
Seznam tabulek Tabulka 1: Kompatibilita operací READ a WRITE ......................................................................................8 Tabulka 2: Úrovně izolace a fenomény podle standardu SQL .....................................................................14 Tabulka 3: Matice kompatibility zámků ......................................................................................................22 Tabulka 4: kompatibilita zámků při strukturovaném zamykání ...................................................................26 Tabulka 5: DML zámky v Oracle databázi ..................................................................................................37 Tabulka 6: kompatibilita tabulkových DML zámků v Oracle databázi .......................................................38 Tabulka 7: Oracle - ukázky chování při izolaci read committed..................................................................42 Tabulka 8: Oracle - chyba v úrovni izolace serializable ..............................................................................43 Tabulka 9: Oracle - chování transakce při izolaci serializable .....................................................................44 Tabulka 10: Uváznutí v Oracle databázi ......................................................................................................45 Tabulka 11: Konflikty mezi tabulkovými zámky v PostgreSQL .................................................................50 Tabulka 12: Uváznutí v databázi PostgreSQL .............................................................................................51 Tabulka 13: PostgreSQL - implementace MVCC ........................................................................................52 Tabulka 14: PostgreSQL - Read Committed izolace ...................................................................................55 Tabulka 15: PostgreSQL - Repeatable Read izolace....................................................................................57 Tabulka 16: PostgreSQL - serializable izolace ............................................................................................59 Tabulka 17: Kompatibilita zámků v Teradata RDBMS ...............................................................................60
Seznam příloh Příloha č. 1 – Pouţité SQL skripty pro ukázky v databázi Oracle Příloha č. 2 – Pouţité SQL skripty pro ukázky v databázi PostgreSQL
Příloha č. 1 Použité SQL skripty pro ukázky v databázi Oracle ------------------ READ COMMITTED ----------------create table tab1 (jmeno varchar2(10),adresa varchar2(10); insert into tab1 values ('NOVAK','PRAHA'); insert into tab1 values ('ZEMAN','PRCICE'); commit; -- SQL pro session 1: select * from tab1; update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; select * from tab1; commit; select * from tab1; select * from tab1; select count(*) from tab1 where adresa='PRAHA'; select count(*) from tab1 where adresa='PRAHA';
--1 --2 --5 --8 --9 --11 --12 --15
-- SQL pro session 2 select * from tab1; update tab1 set adresa='PRAHA' where jmeno='ZEMAN'; select * from tab1; update tab1 set adresa='CHOMUTOV' where jmeno='NOVAK'; commit; update tab1 set ADRESA='PRCICE' where adresa='PRAHA'; commit;
--3 --4 --6 --7 --10 --13 --14
------------------------- SERIALIZABILITY error -----------------------create table tab1 (a number); create table tab2 (a number); -- SQL pro session 1 alter session set isolation_level=serializable; insert into tab1 select count(*) from tab2; commit; select count(*) from tab1; select count(*) from tab2;
--1 --3 --5 --7 --8
-- SQL pro session 2 alter session set isolation_level=serializable; insert into tab2 select count(*) from tab1; commit;
--2 --4 --6
---------------------------------------------1
-- SERIALIZABILITY -- stejna sada tabulek jako pro read committed ----------------------------------------------- SQL pro session 1 update tab1 set adresa='PRAHA'; commit; update tab1 set adresa='CHOMUTOV'; commit;
--3 --4 --8 --9
-- SQL pro session 2 alter session set isolation_level=serializable; select * from tab1; select * from tab1; commit; select * from tab1; update tab1 set adresa='PRCICE' where jmeno='NOVAK';
--1 --2 --5 --6 --7 --10
-------------- ORA-00060 ------------create table t1 (a number, b varchar2(10)); begin for i in 1..10 loop; insert into t1(i,'ORIG'); end lookp; commit; end; / -- SQL pro session 1 update t1 set b='S1' where a<5; update t1 set b='S1' where a=6; commit; select * from t1;
--1 --3 --6 --7
-- SQL pro session 2 update t1 set b='S2' where a>5; update t1 set b='S2' where a=1; commit;
--2 --4 --5
2
Příloha č. 2 Použité SQL skripty pro ukázky v databázi PostgreSQL ------------ Deadlock ----------create table tab1 (col1 int); create table tab2 (col1 int); create table tab3 (col1 int); insert into tab1 values(1); insert into tab2 values(1); -- SQL pro session 1 select * from tab3; begin insert into tab3 values(1); update tab1 set col1=10; update tab2 set col1=22; commit; select * from tab3;
--1 --2 --4 --5 --8 --10 --11
-- SQL pro session 2 begin update tab2 set col1=11; update tab1 set col1=12; commit;
--3 --6 --7 --9
---------- MVCC --------create table mvcc_test (a number); -- SQL pro session 1 begin insert into mvcc_test values(1); commit; begin; update mvcc_test set a=11; commit; begin; delete from mvcc_test; commit;
--1 --2 --3 --5 --6 --8 --10 --11 --13
-- SQL select select select select
--4 --7 --9 --12
pro session xmin,xmax,a xmin,xmax,a xmin,xmax,a xmin,xmax,a
2 from from from from
mvcc_test; mvcc_test; mvcc_test; mvcc_test;
------------------ READ COMMITTED ----------------create table tab1 (jmeno varchar(10),adresa varchar(10)); insert into tab1 values('NOVAK','PRAHA'); 1
insert into tab1 values('ZEMAN','PRCICE'); -- SQL pro session 1 begin select * from tab1; update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; select * from tab1; commit; begin; select * from tab1; select * from tab1; select count(*) from tab1 where adresa='PRAHA'; select count(*) from tab1 where adresa='PRAHA';
--1 --3 --4 --7 --10 --11 --12 --15 --16 --19
-- SQL pro session 2 begin; select * from tab1; update tab1 set adresa='PRAHA' where jmeno='ZEMAN'; select * from tab1; update tab1 set adresa='CHOMUTOV' where jmeno='NOVAK'; commit; begin; update tab1 set ADRESA='PRCICE' where adresa='PRAHA'; commit;
--2 --5 --6 --8 --9 --13 --14 --17 --18
------------------- REPEATABLE READ -----------------create table t1 (a number); create table t2 (a number); -- SQL pro session 1 SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION READ;--1 begin; insert into t1 select count(*) from t2; commit; select * from t1; select * from t2; begin; update tab1 set adresa='BOLESLAV' where jmeno='NOVAK'; commit; begin; update tab1 set adresa='BOLESLAV'; commit;
-- SQL pro session 2 SET SESSION CHARACTERISTICS AS TRANSACTION READ;--3 begin; insert into t2 select count(*) from t1; commit; begin; select * from tab1; select * from tab1; 2
ISOLATION
LEVEL
REPEATABLE --2 --5 --7 --9 --10 --11 --14 --15 --19 --21 --22
LEVEL
REPEATABLE --4 --6 --8 --12 --13 --16
commit; select * from tab1; begin; update tab1 set adresa='PRCICE' where jmeno='NOVAK';
--17 --18 --20 --23
---------------- SERIALIZABLE --------------create table tab (class int, val int); insert into tab values (1,10); insert into tab values (1,20); insert into tab values (2,100); insert into tab values (2,200); -- SQL pro session 1 SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE;--1 select * from tab; --3 begin; --4 select sum(val) from tab where class=1; --6 insert into tab values(2,30); --7 commit; --10 -- SQL pro session 2 SET SESSION CHARACTERISTICS AS TRANSACTION ISOLATION LEVEL SERIALIZABLE;--2 begin; --5 select sum(val) from tab where class=2; --8 insert into tab values(1,300); --9 commit; --11
3
