Basi di Dati - Complementi - Lezione del 18 marcio 2008

 :: Basi di Dati - Complementi - Lezione del 18 marzo 2008 ::

Torna alla pagina di BDC

Timestamp multiversione

C'è un altro tipo di timestamp, quello multiversione. La differenza con il timestamp monoversione è che questo mantiene 1 sola copia (versione) di un oggetto. Il multiversione invece ne mantiene di più, e questo rende possibile l'accettazione di più operazioni di lettura rispetto al monoversione.

Infatti, ogni volta che c'è una scrittura su di un oggetto, salvo la nuova versione, contrassegnata con WTM e RTM della trans che ha eseguito l'operazione. Quindi, se scrivo 10 volte su x, avrò 10 versioni diverse di x.

Le letture quindi se arrivano in ritardo rispetto al timestamp dell'ultima versione di un oggetto, non le mando a casa: invece, vado a cercare nelle versioni precedenti il timestamp più grande tra quelli minori della lettura che sto analizzando adesso.

Per intenderci, se ho 10 versioni di x, ognuna con timestamp crescente (1, 2 ... 10), e dopo la 10^a scrittura arriva un read con timestamp 4, allora il mio sistema multiversione va a recuperare il più grande valore tra quelli minori di 4, in questo caso 3, e darà questo come risposta alla lettura.

 read(x, ts)

Sempre accettata. Restituisce la versione con WTM massimo tra quelli minori di ts. Poi aggiorno l'RTM di quella versione, mettendoci ts.

 write(x, ts)

Trovo la versione con WTM massimo tra quelli <= ts. Sarebbe in pratica la copia su cui la mia trans attuale avrebbe dovuto scrivere.

• RTM > ts: NO, perché quella versione è già stata letta da qualcuno più giovane di me;
• altrimenti, creo una nuova versione con i miei RTM e WTM.

Dal punto di vista dell'accettazione di schedule diversi, il timestamp è un po' più ristretto rispetto a 2PL.

Vediamo una bella tabellina che mi dice come stanno i rapporti tra 2PL e TS.

Comparazione scheduler
	2PL	TS
Trans. rifiutate	messe in attesa	uccise
Ordine di serializzazione:	imposto dai conflitti	imposto dal ts
Attesa per commit:	Sì	bufferizzazione del write
Deadlock:	Sì	No

2PL non uccide sempre, mette in coda in attesa di condizioni migliori. Invece TS accoppa le trans che sgarrano. 2PL ha i deadlock, TS no perché non usa proprio i lock. Per evitare i lock, 2PL deve essere attivato nella sua versione conservativa (vedi la lezione precedente). Il problema del TS è che uccidere le trans e farle ripartire è più costoso che nemmeno metterle in attesa: ecco perché i DBMS commerciali generalmente usano 2PL.

Gestione dei lock

Se uso i lock, devo anche gestirli, e chi lo fa è un'entità fantasiosamente chimata gestore dei lock. Le richieste che possono arrivare da parte di una trans possono essere:

• r_lock (T, x, errcode, timeout)
• w_lock (T, x, errcode, timeout)
• unlock (T, x)

Il timeout serve per non attendere indefinitamente: se dopo un certo tempo la trans non è ancora stata servita completamente, la accoppo perché è scaduta, faccio il rollback e la riprendo.

Il lock a 3 stati necessita di 3 bit per risorsa, e c'è una tabella che memorizza i lock per ogni risorsa. Siccome vi si accede di frequente, questa tabella è tenuta in memoria centrale.

Lock gerarchico

Per rendere le cose più razionali, si è deciso di rendere possibile un lock a diversi livelli. Dal livello più alto a quello più basso, troviamo il DB, la tabella, il frammento di tabella e la singola tupla. Il motivo dietro a ciò è che se devo modificare una tupla, non dovrei lockare totalmente l'intero DB.

I tipi di lock gerarchico sono i seguenti:

• X = esclusivo
• S = shared
• I = intenzionale

Il lock esclusivo è quello che esclude tutti dall'accesso all'oggetto. È il tipo del w_lock. Il lock shared invece è il tipo del r_lock. Il lock intenzionale invece dice che ho l'intenzione di lockare una risorsa che gerarchicamente è più in basso rispetto al mio nodo.

Ecco le vario "combo":

• XL = esclusivo (il w_lock)
• SL = shared (r_lock)
• ISL = Intentional Shared Lock
• IXL = Intentional eXclusive Lock
• SIXL = Shared Intentional-Exclusiove Lock: voglio un lock shared sul nodo corrente, e manifesto anche l'intenzione di lockare più in basso nella gerarchia.

Se voglio un nodo basso in gerarchia, devo cominciare a cercare lock intenzionali partendo dall'alto. Quando poi li rilascio, li rilascio partendo dal basso.

Posso chiedere SL o ISL su di un nodo solo se ho ISL o IXL sul nodo genitore, e non è una cosa strana perché concorda con quanto detto qui sopra. Allo stesso modo, posso chiedere IXL, XL o SIXL solo se ho SIXL o IXL sul genitore. I lock di tipo X infatti "inglobano" i lock di tipo S, ecco perché se voglio una S su di un nodo posso avere S o X sul genitore, ma se voglio X devo per forza avere una X nel genitore.

La granularità è la dimensione della scala gerarchica. Posso farla fine (tanti livelli) o spessa (pochi livelli). Si cerca di raggiungere un compromesso, perché se è troppo fine diventa costosa, se è troppo grossa anche se costa meno produce più attese inutili.

In SQL 99, le transazioni sono state classificate in 2 tipi:

• Read Only, che non modificando niente non chiedono i lock di tipo X;
• Read Write, che è il tipo di default.

Se riandiamo coi ricordi alle proprietà ACID, vediamo che la proprietà I di isolamento si riferisce proprio alla possibilità di isolare le azioni in un ambiente di esecuzione parallela. SQL ci permette di dare ad una transazione uno tra 4 possibili livelli di isolamento, dal più lasco al più stretto:

• read uncommitted: leggo solamente senza chiedere lock, e non mi preoccupo di leggere solo da trans che hanno committato. Mi espongo quindi volontariamente al rischio di letture inconsistenti, ma so che sarò molto veloce.
• read committed: chiede lock per leggere. Non garantisce però la serializzabilità.
• repeatable read: fa lock a livello di tupla, eliminando tutte le anomalie tranne l'inserimento fantasma.
• serializable: evita tutte le anomalie, ed è la scelta di default.

Per poter funzionare a dovere, questi livelli presuppongono che il DBMS utilizzi il 2PL. Ma c'è una cosa in più: per evitare anomalie, servono anche i cosiddetti lock di predicati, che sono aggiuntivi rispetto ai lock sulle risorse. Infatti, se i lock delle risorse permetterebbero delle operazioni da parte di altre trans, ci sono però certi costrutti SQL come gli operatori aggregati che funzionerebbero male in certi casi, con i soli lock. Quindi, occorre che il DBMS imposti anche un lock di predicato, per evitare del tutto anomalie di questo tipo.

Deadlock

Si tratta di una mutua attesa:

 T1 vuole x, ma x ce l'ha T2;
 T2 vuole y, ma y ce l'ha T1.

L'uno aspetta l'altro, e siccome nessuna può mollare il lock perché, secondo le regole, una volta che mollo un qualsiasi lock non posso più richiederne nessun altro, non se ne esce più.

Per scoprire se le nostre trans vanno in deadlock, si costruisce un grafo di attesa, con le risorse per ogni trans, e gli archi che vanno da una trans che vuole una risorsa alla trans da cui la riceverà. Se ci sono cicli, ci saraanno anche deadlock.

Risolvere i deadlock

Posso usare il timeout: se dopo un po' di tempo non ottengo la risorsa, muoio, e mollo quindi tutte le mie risorse lockate.

Quanto deve essere lungo il timeout? Se è troppo lungo, non si va più avanti. Se è troppo corto troppa gente morirebbe presto inutilmente => solito compromesso. Però è semplice da implementare, e quindi molto utilizzato.

Se no, disegno il grafo delle attese di cui sopra, rilevando il deadlock, e decido a posteriori chi eliminare. Problema: ogni quanto creo il grafico e lo controllo?

Posso decidere di prevenire il problema, e fare in modo che le richieste che potrebbero causare deadlock vengano rifiutate in partenza. Un po' drastico perché si fanno processi in base a sospetti, però funziona, anche se è difficile sapere in partenza che cosa una trans vuole.

Un altro sistema è quello di introdurre un ordinamento totale tra i miei oggetti. L'ordinamento non deve rispettare qualche norma, purché sia totale, ovvero tutti gli oggetti siano ordinati. Il comportamento che forzo poi è che i lock vanno richiesti seguendo questo ordine: se chiedo il lock su di una risorsa, non posso chiedere il lock di risorse precedenti ma solo di risorse seguenti. Così evito in partenza le situazioni in cui due vogliono cose mutue: non può accadere semplicemente per via dell'ordinamento, perché se io voglio l'oggetto c, concorrerò solo per gli oggetti da d in poi, ma non potrò contestare quelli prima di c, e quindi si tratta di semplice concorrenza senza deadlock, risolta da uno scheduler qualsiasi. Il problema è che tutto ciò è difficile da realizzare.

Uccisione delle trans

Abbiamo appena visto che prevengo l'insorgere di deadlock quando scopro in partenza che potrebbero esserci. Ma poi, quale delle due (o più) trans coinvolte vado ad uccidere? Bella domanda.

Se scelgo una strategia preemptive, uccido chi HA in quel momento la risorsa. Al contrario, una strategia non preemptive uccide chi fa la richiesta di una risorsa che causerebbe deadlock.

Se uso il timestamp, devo confrontare il timestamp delle due transazioni. Prendiamo il caso in cui

 ti vuole lock su x
 tj ha il lock su x

La strategia wait-die è di tipo non preemptive, e si comporta così:

• se ti < tj, allora ti è più vecchio e ha la precedenza lui.
• se no, uccido ti e lo riavvio ma con lo STESSO timestamp.

Perché tengo lo stesso timestamp? Perché in questo modo quando lo riavvio si troverà ad essere una delle più vecchie tra le trans che concorreranno in futuro, e da vecchia avrà la precedenza sui govani.

Invece la strategia wound-wait agisce così:

• se ti > tj, allora ti è giovane e lo metto in attesa di essere ripescato poi.
• se no, abortisco tj e lo faccio resuscitare con lo stesso timestamp per i motivi spiegati qui sopra.

Dobbiamo però sapere che in generale i sistemi commerciali non usano la prevenzione, perché questa andrebbe ad uccidere trans che solo in potenza avrebbero causato danni, e nella pratica i deadlock non sono moltissimi.

In mancanza di timestamp posso usare altre maniere, di cui una piuttosto grezza è la no waiting: accoppo il richiedente e lo faccio rinascere più tardi.

Il cautious waiting va a vedere se tj, che ha il lock desiderato, è a sua volta in attesa di altri. Se la risposta è sì, vuol dire che ci sono potenziali deadlock (in quanto potrebbe aspettare risorse da qualcuno legato a ti), e quindi uccido il richiedente, ti. Se tj invece non aspetta nessuno, metto ti in dolce attesa.

Problemi coi lock

Sono essenzialmente di due tipi:

Livelock: una trans attende un lock che non le arriva mai per via delle priorità.

Starvation: una trans viene sempre uccisa per qualche motivo, e ciò accade quando i timestam sono gestiti male. È proprio per evitare le starvations che uso i ts vecchi quando resuscito una trans.

Torna alla pagina di BDC