COMPUTERWORLD
pod kapotou
Stromové protokoly

Síla dvoufázového uzamykacího protokolu spočívala v tom, že protokol zajišťoval uspořádatelnost pro každý legální rozvrh. Víme již také, že v modelu plochých transakcí s jednoduchými objekty jde o podmínku nutnou, tj. uspořádatelnost implikuje dvoufázovost. V jiných modelech transakcí lze použít i jiné protokoly, obecně nedvoufázové protokoly, vedoucí také ke korektním rozvrhům. Ukážeme zde speciální případ tzv. stromového protokolu vhodného např. pro hierarchické databáze, ale i pro jiné stromové struktury dat, jako jsou např. B-stromy.

Budeme předpokládat pouze výlučné zámky W_LOCK, tj. po provedení W_LOCK(X) může být objekt X jak čten, tak zapisován. V stromovém protokolu může každá transakce T používat zámky s následujícími pravidly:

  1. První W_LOCK(X) transakce T lze použít na jakémkoli objektu X.
  2. Další objekt může být uzamčen transakcí T pouze když předchůdce byl v T uzamčen.
  3. Objekty mohou být odemknuty kdykoliv.
  4. Prvek, který byl transakcí T zamknut a odemknut nemůže být následně znovu zamknut v T.

Lze ukázat, že všechny rozvrhy, které jsou legální pod stromovým uzamykacím protokolem jsou uspořádatelné a na rozdíl od dvoufázových protokolů zde nedochází k uváznutí.

Uvažujme strom na obrázku 1 a transakce

T1: W_LOCK(B); W_LOCK(E); UNLOCK(E); W_LOCK(D); UNLOCK(B); W_LOCK(G); UNLOCK(D); UNLOCK(G).

T2: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H).

T3: W_LOCK(B); W_LOCK(E); UNLOCK(E); UNLOCK(B).

T4: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H).

 

 

 

Obr. 1 Hierarchická databáze

Jeden z možných uspořádatelných rozvrhů transakcí T1,...,T4 je v tabulce 1.

T1

T2

T3

T4

W_LOCK(B)

     

W_LOCK(D)

   

W_LOCK(H)

   

UNLOCK(D)

   

W_LOCK(E)

     

UNLOCK(E)

     

W_LOCK(D)

     

UNLOCK(B)

     

 

W_LOCK(B)

 

 

W_LOCK(E)

 

UNLOCK(H)

   

W_LOCK(G)

     

UNLOCK(D)

     

   

W_LOCK(D)

   

W_LOCK(H)

   

UNLOCK(D)

   

UNLOCK(H)

 

UNLOCK(E)

 

 

UNLOCK(B)

 

UNLOCK(G)

     

Tab. 1 Uspořádatelný rozvrh transakcí T1,...,T4

Další příklad speciálního případu stromového protokolu se týká B-stromů. Ukážeme zároveň, jak se realizují fyzické zámky, tj. jak se řeší případ vícenásobného vstupu do fyzické struktury. Pro práci s B-stromy budeme uvažovat operace READ(X) a operaci UPDATE(X). První z nich znamená nalezení a přečtení listového uzlu s objektem X z B-stromu, druhá představuje buď INSERT(X) nebo DELETE(X), tj. aktualizaci B-stromu prostřednictvím objektu X.

Pro operaci UPDATE lze u B-stromů objevit jednu přirozenou vlastnost, která nám určuje, jak velký kus B-stromu musí být uzamčen, aby operace UPDATE mohla být provedena.

Uzel B-stromu nazveme bezpečný, jestliže má

(i) méně než m-1 klíčů (pro operaci INSERT)

(ii) více než é m/2ù - 1 klíčů (pro operaci DELETE)

Není-li uzel bezpečný, bude UPDATE ovlivňovat předchůdce tohoto uzlu (důsledek štěpení nebo slévání uzlů). Pro každý uzel v B-stromu bude existovat fronta, do které se budou ukládat požadavky na zamykání. Tyto požadavky budou uděleny v souladu s pravidly výlučných a sdílených zámků, tj. jeden uzel může být uzamčen současně nejvýše jedním výlučným zámkem nebo několika sdílenými zámky. Nesmí však být uzamčen současně sdíleným (R_LOCK) a výlučným (W_LOCK) zámkem. Připomeňme, že sdílené zámky umožňují pouze čtení.

Pro B-stromy ukážeme dva protokoly, zvlášť pro čtení B-stromu a zvlášť pro aktualizaci. V obou algoritmech uzamykání předpokládáme hloubku stromu větší než 1.

  • protokol pro READ

1. Umísti R_LOCK do kořene B-stromu

2. Přečti kořen B-stromu do vyrovnávací paměti (běžný uzel)

3. while běžný uzel není list do

begin umísti R_LOCK na následníka uzlu běžného uzlu; uvolni zámek uzlu běžného uzlu; přečti následníka běžného uzlu

end

  • protokol pro UPDATE

1. Umísti W_LOCK do kořene B-stromu

2. Přečti kořen B-stromu do vyrovnávací paměti (běžný uzel)

3. while běžný uzel není list do

begin umísti W_LOCK na následníka uzlu běžného uzlu;

přečti následníka do běžného uzlu;

if běžný uzel je bezpečný then uvolni zámky všech uzamčených předchůdců

end

Všimněme si, že protokol pro READ udržuje vždy jen jeden uzamknutý uzel v transakci, u protokolu pro UPDATE jich může být více.

Uvažujme část B-stromu s m=3 (obrázek 2). B-strom obsahuje klíče z domény atributu např. JMÉNO_F (jméno filmu) a do stromu se bude pouze zapisovat (tj. pro bezpečnost stačí splnění vlastnosti (i)). Chceme-li např. vložit do B-stromu klíč Filosofská historie, vyplývá z algoritmu vkládání do B-stromu, že na cestě z kořene stromu 6 do listu 0 je bezpečný uzel 6 a 2. Tedy W_LOCK bude aplikován třikrát - sice na uzly 6, 2, 0, ovšem s tím, že uzel 6 bude uvolněn ještě před vstupem do uzlu 0. Zarámovaná část obrázku 2 ukazuje zamknutou větev stromu těsně před operacemi štěpení uzlu 0 (bude se opravovat i uzel 2). Odemknutí uzlů 2 a 0 bude následovat až po těchto operacích.

 

 

 

 

 

6

Karla - -

2 5 -

 

2 5

F.L .Věk - - Poklad - -

0 4 - 3 1 -

 

0 4

Babička F.L.Věk - Karla - -

Z3 Z5 - Z1 - -

Obr. 2 Zamykání B-stromu

Závěrem poznamenejme, že protokol pro aktualizaci B-stromu je speciálním případem stromového protokolu. Je tedy garantována uspořádatelnost pro jakýkoli legální rozvrh, zajištěna je absence uváznutí. Stromové protokoly mají proti dvoufázovým uzamykacím protokolů dvě výhody. Umožňují dříve odmykat objekty a zabraňují uváznutí. Obojí přispívá k zvýšení průchodnosti transakčního provozu.



<seznam dílů seriálu>   <COMPUTERWORLD>