Timestamp Based Schedules
This methods detects and fixes deadlocks in strict 2PL systems.
This implements the idea that each transaction should be executed instantly when it is started.
This makes it equivalent to a serial schedule that has a transactions in the order of their start time.
Timestamps
Each transaction $T$ is assigned a unique integer $\text{TS}(T)$ when it starts. This is the timestamp of $T$.
If $T_1$ arrived earlier than $T_1$, we require $\text{TS}(T_1)<\text{TS}(T_2)$.
This is different to last time as we assign a new timestamp even after a restart.
Additionally, for each database item $X$, we need to maintain:
-
Read Time of $X$ - $\text{RT}(X)$
The timestamp of the youngest transaction that read $X$.
-
Write Time of $X$ - $\text{WT}(X)$
The timestamp of the youngest transaction that wrote $X$.
| Action | Timestamp | Read Time | Write Time |
|---|---|---|---|
| $\text{RT}(X)=0$ | $\text{WT}(X)=0$ | ||
| $r_2(X)$ | $\text{TS}(T_2)=2$ | $\text{RT}(X)=2$ | $\text{WT}(X)=0$ |
| $r_1(X)$ | $\text{TS}(T_1)=1$ | $\text{RT}(X)=2$ | $\text{WT}(X)=0$ |
| $r_3(X)$ | $\text{TS}(T_3)=3$ | $\text{RT}(X)=3$ | $\text{WT}(X)=0$ |
| $w_2(X)$ | $\text{RT}(X)=3$ | $\text{WT}(X)=2$ | |
| $w_4(X)$ | $\text{TS}(T_4)=4$ | $\text{RT}(X)=3$ | $\text{WT}(X)=4$ |
Read Requests
If $T_1$ requests to read $X$:
- Abort and restart $T_1$ if $\text{WT}(X)>\text{TS}(T_1)$.
- Else, grant request.
Write Requests
If $T_1$ requests to write $X$:
- Abort and restart $T_1$ if $\text{RT}(X)>\text{TS}(T_1)$ or $\text{WT}(X)>\text{TS}(T_1)$.
- Else, grant request.
A full example of a timestamp based schedules is given in the lecture.
Properties of Timestamp Based Scheduling
Good properties:
- Enforces conflict-serialisable schedules.
- Deadlocks don’t occur.
Bad properties:
- Cascading rollbacks.
- Starvation can occur.
- Through cyclic aborts and restarts of transactions.
This can be prevented using methods not covered.
Ensuring Strictness
Schedules enforced by timestamp based schedulers are not strict.
An additional condition can be added to enforce a strict schedule:
Delay read or write requests until the youngest transaction who wrote $X$ before has committed or aborted.
Multiversion Concurrency Control (MVCC)
This is a variant of timestamp scheduling used by many DBMSs. It is the same idea as timestamp based approaches by you have multiple versions of the database:
- This means that write operations do not overwrite each other, but instead $w_i(X)$ creates a new version of $X$ with it’s own timestamp $\text{TS}(T_i)$.
- Whenever you read, you read the latest version before your timestamp.
This means that a transaction only needs to restart if it tries to write and the read timestamp is later than your timestamp.
The rules are:
- For Writes - Abort and restart $T_1$ if $\text{RT}(X)>\text{TS}(T_1)$ and otherwise, grant request.
- For Reads - Always granted.
There is also a strict variant, where you delay reads until the transaction you read from commits.
There is a full example with MVCC in the lecture.