Řízení konkurenčního přístupu k datům

řízení konkurenčního přístupu k datům, binární zámky, víceúrovňové zámky, časové známky, multiverze

Úvod

Velkým problémem u transakcí je zajistit jejich sériovost. Transakce se skládají z jednotlivých operací. Tyto operace zabírají různý čas.

V jedu chvíli mohou dvě transakce operovat nad stejnou hodnotou a navzájem si ji měnit pod rukama. Příkladem může být scénář, kdy dvě transakce provádějí operace nad dvěma bankovními účty.

  • jedná hodnotu čte a začne ji upravovat
  • druhá transakce začne dělat to samé, přečte tu samou hodnotu a začne ji upravovat
  • jedna z těchto transakcí nevyhnutelně zapíše upravenou hodnotu zpět jako první
  • ta druhá poté při svém zápisu přepíše výsledek
Špatná posloupnost konfliktních operací
obr. 1: Špatná posloupnost konfliktních operací

Řízení konkurenčního přístupu k datům zajišťuje správnou posloupnost (řazení) konfliktních operací

Máme několik prostředků, jak toho docílit:

  • zamykání dat (zabrání vícenásobnému současnému přístupu k datům) - je řízeno pomocí manažera zámků, který spravuje zámky skrze tabulku zámku, ve které jsou záznamy o tom, jaká transakce zamkla jakou položku.
    • binární zámky
    • víceúrovňové zámky
  • časové známky (zajišťují sériovost transakčních scénářů - nejdříve jedna, pak druhá)
  • multiverze (používání více verzí dat)

Binární zámky

Tento zámek je svázaný s danou položkou a určuje, které operace je na ni možné provádět. Může nabývat dvou hodnot 1 - zamčeno, 0 - odemčeno.

Postup aplikace binárního zámku:

  • transakce se pokusí zamknout hodnotu, se kterou chce pracovat, pokud je tedy hodnota odemčená
  • pokud je hodnota zamčená, transakce čeká, dokud se hodnota neodemkne
    • transakce NESMÍ odemknout zámek hodnoty, kterou sama nezamkla
    • jakmile se odemkne, transakce se opět pokusí zamknout hodnotu
  • po zamčení hodnoty provede potřebné operace a odemkne hodnotu

Sdílené a výhradní zámky (Víceúrovňové zámky)

Tyto zámky se dělí na dva druhy, podle toho, jestli zamykají čtení hodnoty, nebo zápis hodnoty:

  • read_lock(X): Více transakcí najednou může použít read_lock
    • transakce NEMŮŽE použít read_lock(X), pokud jiná transakce použila write_lock(X)
  • write_lock(X): Pouze jediná transakce může použít write_lock
    • transakce NEMŮŽE použít write_lock(X), pokud je hodnota X jakkoliv zamčená

Platí, že unlock(X) odemyká jak read_lock, tak write_lock nad touto hodnotou.

Postup aplikace víceúrovňových zámků:

  • Pro čtení:
    • transakce se pokusí zamknout hodnotu, kterou chce číst, pokud jiná hodnota nepoužila write_lock
    • pokud je hodnota write_locknutá, tak transakce čeká, než bude hodnota odemčena
    • pokud hodnota není write_locknutá, transakce zvýší počítadlo, které určuje, kolik jiných transakcí read_locknulo hodnotu a provede čtení
  • Pro zápis:
    • transakce se pokusí zamknout hodnotu, kterou chce zapsat, pokud jiná transakce nepoužila read NEBO write lock
    • v opačném případě čeká na odemknutí hodnoty, poté manažer zámků aktivuje tuto čekající transakci
    • transakce se pokusí opět o zamknutí hodnoty
  • Pro odemknutí:
    • pokud transakce zamkla pomocí write_locku hodnotu, tak ji odemkne (stále platí, že transakce nemůže odemknout hodnotu, kterou nezamknula)
    • čekající transakce ve frontě se aktivují
    • pokud transakce odemyká svůj read_lock nad hodnotou, tak dekrementuje hodnotu počítadla
    • pakliže je počítadlo na 0, nastaví se hodnota proměnné na unlocked a manažer zámků aktivuje transakci, jež čeká ve frontě

Transakce již nyní nejsou konkurentní, ale zároveň stále nejsou sériové. Jedná transakce si může hodnotu read_locknout, přečíst ji a unlocknout -> má ji přečtenou a je připravena s ní něco dělat. Jenže mezi unlocknutím a tím, než s tou hodnotou transakce něco udělá stihne jiná transakce tuto hodnotu také read_locknout, přečíst, unlocknout, provést operaci, write_locknout a zapsat (čímž zneplatní hodnotu, kterou předtím první transakce přečetla).

Nesériové zpracování
obr. 2: Nesériové zpracování i po aplikaci sdílených a výhradních zámků

Tento problém se řeší dvoufázovým zamykáním.

Dvoufázové zamykání

Jedná se o proces zamykání, kde se všechny operace zamykání provedou před jakoukoliv operací odemykání. Jde tedy o postupy aplikace sdílených a výhradních zámků.

Máme 3 druhy:

  • základní: všechny zamykací operace jsou časově před odemykacími operacemi
  • konzervativní: předem se stanoví hodnoty, které se mají zamknout - množina hodnot pro zápis a množina hodnot pro čtení
    • pokud se nepodaří zamknout jednu položku z množiny, nezamkne se žádná
  • striktní: žádný zámek není uvolněn, pokud není transakce potvrzena (dokončena) - může způsobit deadlock

Řešení deadlocku - časové známky.

Časové známky (TimeStamp - TS)

Časová známka je proměnná, která je přidělena každé transakci. Tato proměnná se mění podle toho, jak transakce probíhá -> čítač.

Princip je uspořádat transakce podle nejvyšší hodnoty TS.

  • hodnota read_TS(X): obsahuje nejvyšší TS ze všech transakcí, které úspěšně četly X.
  • hodnota write_TS(X): obsahuje nejvyšší TS ze všech transakcí, které úspěšně zapsaly X

Kdykoliv transakce chce psát nebo zapisovat, tak algoritmus transakčního uspořádání porovná TS transakce s read_TS(X) nebo s write_TS(X) a kontroluje, zdali není narušené pořadí -> pokud je pořadí narušené, transakce musí počkat a začít znovu, nebo provést rollback.

Multiverze

Techniky multiverzního řízení:

  • pomocí časových značek
  • pomocí dvoufázového zamykání

Časové značky

Systém udržuje více verzí (proto mutliverze) hodnoty. Může to být \(X1, X2, ..., X_n\).

  • každá položka \(X_i\)ma svojí hodnotu read_TS a write_TS
  • pokud se transakce snaží zapisovat nebo číst je vytvořená nová verze \(X_i + 1\), jejíž časová známka je
    • \(read\_TS(X_i + 1)\) pokud chce číst
    • \(write\_TS(X_i + 1)\) pokud chce zapisovat

Postup aplikace:

Pro read:

Najde se verze \(X_i\) s nejvyšší hodnotou write_TS pro tuto hodnotu (X), která odpovídá \(X_i\).

Pro write:

Pokud má X nejvyšší hodnotu pro write_TS(X) takovou, že je menší nebo rovna TS(T) a současně je TS(T) menší než read_TS tohoto X, tak nastane rollback, v opačném případě se vytvoří nová verze X.

  • Timestamp hodnoty musí souhlasit s timestampem transakce, pokud tomu tak není, tak s touto hodnotou již operuje jiná transakce.

Zdroje