Timestamp-Based Scheduler

This is a Scheduler that gives Conflict-Serializable Schedule

This scheduler is optimistic:

  • it allows any sequence of action
  • periodically it checks if everything is okay. yes - continue, no - abort the transaction and restart


Assume we execute 3 transactions $T_1, T_2, T_3$

  • timestamp-scheduler.png
  • we allow arbitrary reordering of actions from these transactions
  • but we also consistently check if the reordering is equivalent to the serial schedule $(T_1, T_2, T_3)$
  • if not - some transactions are aborted and restarted


Rules

Additional information:

  • every transaction $T_i$ receives a timestamp $TS(T_i)$
    • $TS(T_i)$ can be either a datetime or just a value that gets incremented on each operation
    • the higher the $TS(T_i)$, the later $T_i$ started
  • for each DB item $X$ we associate two timestamps and a boolean flag $C(X)$
    • $RT(X)$ - read time of $X$: the $TS(T)$ of the last transaction $T$ that read $X$
    • $WT(X)$ - write time of $X$: the $TS(T)$ of the last transaction $T$ that wrote $X$

Basic Rule:

  • $RT(X)$: every time $X$ is read by $T$ check if
    • $TS(T) > RT(X)$
    • yes - update the $RT(X) \leftarrow TS(T)$
  • $WT(X)$ (initially 0): on every write to $X$ by $T$ check if
    • $TS(T) > WT(X)$
    • yes - update $WT(X) \leftarrow TS(T)$
  • $C(X)$
    • true if the latest transaction that wrote to $X$ has committed
    this is the transaction $T$ that wrote its $TS(T)$ to $WT(X)$
    • false otherwise


Problematic Situations

Problematic Situation 1

suppose we have the following sequence of actions:

  1. $T_\text{start},$
  2. $U_\text{start},$
  3. ${\color{blue}{U \text{ writes } X}},$ - allow this because we're optimistic
  4. ${\color{red}{T \text{ reads } X}},$ - not consistent with the serial schedule $(T, U)$ $\Rightarrow$ abort $T$
  5. $...$

So the problem is

  • $T$ starts before $U$, but $U$ writes before $T$ reads
  • should be $T$ reads then $U$ writes

To avoid it we want to check if

  • $TS(T) \geqslant WT(X)$ then we grant a read request $r_T(X)$ to transaction $T$
    • i.e. we should not allow reading of things that were modified by transactions that started later than $T$
  • otherwise we abort $T$


Problematic Situation 2

The sequence of actions:

  1. $U_\text{start},$
  2. $U \text{ writes } X,$
  3. $T_\text{start},$
  4. $T \text{ reads } X,$
  5. ${\color{red}{U_\text{abort}}}, $
  6. $...$

Problem:

  • Actions 1-4 are consistent with the serial schedule $(U, T)$
  • However $U$ aborts
  • that means that read of $X$ by $T$ was inconsistent - it will be rolled back to the old value on $U_\text{abort}$

To avoid that:

  • reads to $X$ should be delayed until
  • the transaction that last modified $X$ has committed
    • i.e. the transaction with timestamp $WT(X)$
    • and we wait until $C(X)$ is set to true
  • so we do not abort, just pause


Problematic Situation 3

Sequence of Actions:

  1. $T_\text{start},$
  2. $U_\text{start},$
  3. ${\color{blue}{U \text{ reads } X}},$ - we're optimistic, so the read is successful
  4. ${\color{red}{T \text{ writes } X}},$ - not consistent with the serial schedule $(T, U)$
  5. $...$

The problem:

  • $T$ starts before $U$, but $U$ reads before $T$ writes
  • should be $T$ first writes, then $U$ reads the value written by $T$

Solution:

  • a write request $w_T(X)$ should be granted if $TS(T) \geqslant RT(X)$
  • i.e. if the transaction $U$ that last read $X$ was created before the current transaction $T$


Problematic Situation 4

  1. $S_\text{start},$
  2. ${\color{blue}{S \text{ read } X}},$
  3. $T_\text{start},$
  4. $U_\text{start},$
  5. ${\color{blue}{U \text{ writes } X}},$
  6. ${\color{blue}{T \text{ writes } X}},$ - note that in this case we allow $w_T(X)$ (but ignore it) since it "will" be overwritten if executed $(T, U)$
  7. $T_\text{commit},$
  8. ${\color{red}{U_\text{abort}}}, $
  9. $...$

The problem

  • we allow, but ignore write of $T$ to $X$:
    • we know that the value stored in $X$ should be the value written by $U$
    • because in the serial schedule $(T, U)$, $U$ would execute after $T$ and overwrite the value of $X$
  • but $U$ aborts afterwards
    • it means we shouldn't have ignored the write by $T$
    • and $X$ should store the value written by $T$

Solution:

  • $w_T(X)$ is realizable by $T$ if $TS(T) \geqslant RT(X)$ and $TS(T) < WT(X)$
    • the transaction $T$ started later that the transaction $S$ that did the last read of $X$
    $S_\text{start}, T_\text{start}, S \text{ reads } X, T \text{ writes } X$
    • and $T$ started earlier than some transaction $R$ that did the write to $X$
    $T_\text{start}, R_\text{start}, R \text{ writes } X, T \text{ writes } X$
  • if $C(X)$ is false then $T$ must be delayed till $C(X)$ becomes true
    • i.e. the transaction $R$ that last wrote $X$ has committed
  • if $C(X)$ we can ignore the write

Timestamp-Based Schedule Rules

The rules are:

  • every transactin $T$ receives a timestamp $TS(T)$
  • to each DB item $X$ we associate values $RT(X), WT(X), C(X)$

Suppose we have a transaction $T$ with $TS(T) = t$

$T$ is allowed to read $X$ if

  • $t \geqslant WT(X)$
  • if $C(X)$ is false, then $T$ is paused until $C(X)$ becomes true or transaction that last wrote $X$ aborts
  • if $t < WT(X)$ we abort $T$ and restart it with the next available $TS(T)$

$T$ is allowed to write to $X$ if

  • $RT(X) \leqslant t$ and $WT(X) \leqslant t$
  • if $t < RT(X)$ then $T$ is aborted and restarted
  • if $RT(X) \leqslant t < WT(X)$
    • if $C(X)$ is true we do nothing (keep the current state of $X$)
    • otherwise we pause $T$ until $C(X)$ becomes true or transaction that last wrote $X$ aborts

These rules prevent all bad cases


Cons and Pros

  • Not very effective when we have many transactions that both read and write - in this case we have to abort and restart many transactions
  • When you have few transactions that write it's very efficient - they can proceed immediately


Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion