21 - timestamp

Il timestamp identifica una transazione. È assegnato alla transazione al suo inizio dallo scheduler. Può essere:

• il valore di un contatore
• l’ora di inizio di una transazione

Il timestamp è crescente: se il timestamp di T1 è minore di quello di T2, la transazione T1 è iniziata prima di T2 (quindi, se fossero eseguite in modo seriale, T1 verrebbe eseguita prima).

serializzabilità

Uno schedule è serializzabile se è equivalente allo schedule seriale in cui le transazioni compaiono in base al loro timestamp. Quindi, se per ciascun item acceduto da più di una transazione, l’ordine con cui le transazioni accedono all’item è quello imposto dai timestamp.

esempio 1

consideriamo le due transazioni T1 e T2 con i loro timestamp $TS(T_1)=110$ e $TS(T_2)=100$.

quindi, uno schedule è serializzabile se è equivalente allo schedule seriale $T_2{T}_1$.

Per esempio, questo schedule non è serializzabile, perché $T_1$ legge $X$ prima che $T_2$ l’abbia scritto:

esempio 2

Consideriamo invece queste due transazioni con timestamp $TS(T_1)=110$ e $TS(T_2)=100$:

Uno schedule serializzabile deve essere equivalente allo schedule seriale $T_2{T}_1$ $T_2{T}_1$

quindi, questo schedule è serializzabile solo se non viene eseguita la scrittura di $X$ da parte di $T_2$:

read e write timestamp

A ciascun item $X$ vengono assegnati due timestamp:

• read timestamp read_TS(X) ⇒ il più grande tra tutti i timestamp di transazioni che hanno letto con successo $X$
• write timestamp write_TS(X) ⇒ il più grande tra tutti i timestamp di transazioni che hanno scritto con successo $X$

il "più grande"

il “più grande timestamp” NON è il timestamp dell’ultima transazione che l’ha letto/scritto - è il timestamp della transazione più “giovane” tra quelle che l’hanno letto/scritto

tornando all'esempio 2

controllo della serializzabilità

Ogni volta che una transazione $T$ cerca di eseguire un read(X) o un write(X), occorre confrontare il timestamp $TS(T)$ con il read timestamp e il write timestamp di $X$ per assicurarsi che sia rispettato l’ordine.

algoritmo

scrittura:

T cerca di eseguire una write(X).

1. se $read\_TS(X)>TS(T)$ (ovvero se una transazione più giovane l’ha già letta) $X$ viene rolled back
2. se $write\_TS(X)>TS(T)$, invece di fare un rollback, semplicemente non si effettua l’operazione di scrittura (ignorando l’atomicità)
   • (vuol dire che una transazione più giovane ha già scritto)
3. se nessuna delle condizioni precedenti è soddisfatta, allora:
   • si esegue write(X) e si sovrascrive il write timestamp di $X$: $write\_TS(X):=TS(T)$

lettura:

T cerca di eseguire una read(X).

1. se $write\_TS(X)>TS(T)$, $T$ viene rolled back
2. se $write\_TS(X)\le TS(T)$, allora
   • si esegue read(X) e, se $read\_TS(X)<TS(T)$, si sovrascrive: $read\_TS(X):=TS(T)$

esempio 1

Analizziamo questo schedule:

Le transazioni hanno i seguenti timestamp: $TS(T1)=110,TS(T2)=100,TS(T3)=105$. Assumiamo che all’inizio tutti i read e write timestamp siano azzerati.

Al passo 9 la transazione $T2$ verrà abortita - cercherà di scrivere $X$, ma il suo timestamp sarà minore del read timestamp di $X$ (dato da $T1$ al passo 4): questo significa che $T1$ ha letto il valore errato di $X$: quello non ancora modificato da $T2$. Per questo bisogna eseguire il rollback.

osservazioni

Notiamo che lo schedule delle transazioni superstiti è equivalente allo schedule seriale delle transazioni eseguite in ordine di arrivo.

cosa provoca il rollback di una transazione?

• se la transazione voleva leggere ⇒ trovare un’altra transazione più giovane che ha già scritto i dati

• se la transazione voleva scrivere ⇒ trovare un’altra transazione più giovane che ha già letto i dati

ricorda scritto i dati, non è necessario il rollback (basta non eseguire la scrittura).

Se invece una transazione vuole scrivere e trova una transazione più giovane che ha già

ignorare l'atomicità

Perché possiamo ignorare l’atomicità saltando l’operazione di scrittura di una transazione $T$? L’atomicità serve a garantire la coerenza in una base di dati. Le transazioni che potrebbero trovare una situazione incoerente (a causa della non-scrittura) sono quelle che avrebbero dovuto leggere i dati scritti da $T$ (e si sarebbero ritrovate invece i dati di una transazione più giovane $T^{\prime }$)

• ma non esiste una transazione $T^{\prime \prime }$ arrivata dopo $T$ ma prima di $T^{\prime }$ (con $TS(T^{\prime })>TS(T^{\prime \prime })>TS(T)$) che ha letto il dato: altrimenti, $T$ sarebbe stata rolled-back (avrebbe cercato di scrivere quando una transazione più giovane aveva già letto).
• se poi dovesse arrivare $T^{\prime \prime }$ che vuole leggere il valore di $X$, questa sarebbe rolled back per il primo passo dell’algoritmo di controllo della lettura (troverebbe $write\_TS(X)$ maggiore del proprio perché scritto da $T^{\prime }$)

perché non il timestamp dell'ultima transazione?

Prendiamo come esempio questo caso, con i timestamp $T1<T2<T3$. Se il write timestamp e il read timestamp fossero quelli dell’ultima transazione anziché della più giovane, $T2$ scriverebbe il valore di un item ($X$) già letto da $T3$, quando $T3$ avrebbe dovuto leggere il valore di $T2$.

domande orale

possibili domande orale

• come funziona il timestamp?
• quando una transazione è serializzabile nel caso dei timestamp?
• algoritmo di controllo della serializzabilità
• perché si può ignorare l’atomicità nel caso del write?