Checkpoints

Question 1

Checkpoints

Answer 1

Used to declare a point before which the DBMS was in a consistent state, and all transactions were committed.

Question 2

Advantages of Checkpoints

Answer 2

• faster recovery
• less space used for log-file

Question 3

Simple checkpointing

Answer 3

Checkpoint the log periodically.
No need to undo transactions before a checkpoint.

Question 4

Simple Checkpointing process

Answer 4

• Stop accepting new transactions
• Wait until all active transactions finish and have written commit/abort record on log
• Flush the log to disk
• Write log record checkpoint
• Flush again
• Resume accepting transactions

Question 5

Transactions interrupting checkpoints

Answer 5

Other transactions cannot interrupt a checkpoint, and the transactions within a checkpoint have to finish before we can start anything else.

Question 6

ARIES Checkpoints

Answer 6

Two things are required for ARIES checkpoints:
- Undo and redo logging
- Transactions do not write to buffer before they are sure they want to commit

Question 7

Writing ARIES Checkpoints

Answer 7

We write:
<CHECKPOINT(T1, T2, …)>
in the log and flush it, with these transactions not being committed or aborted as they are in progress.

We then write the content of the buffer to disk.

Then we write

<END>
in the log and flush it.
</END>

Question 8

How writing ARIES checkpoints work

Answer 8

• we have a checkpoint with a set amount of transactions.
• when using undo/redo, we look for the first checkpoint with a corresponding end checkpoint.
• we check that checkpoint’s transactions to see which ones have committed.
• we then undo to the earliest transaction that has not committed.

Question 9

Writing checkpoints example

Answer 9

If T1 begins before T2, and neither has committed, we start at T1 and undo both.
However, lets say you have T1 and T2 again, and T2 has committed but T1 has not. We then redo the committed transactionsafter the cehckpoint and undo the uncommitted transactions before the checkpoint.

Question 10

Conflict serialisability v Recovery

Answer 10

CS:
- equivalent to serial schedules
- ensures consistency and correctness
- can be enforced using two-phase locking

Logging and Recovery:
- ensures we can restore desired database states
- undo incomplete transactions, redo complete transactions
- robust; works even after system failure

Question 11

Dirty reads

Answer 11

The isolation property is not fully enforced for efficiency reasons, which leads to us reading uncommitted transactions.
Can slow the system when an abort occurs, since you have to rollback multiple transactions (since one transaction reads from another uncommitted one, both may have to be rollbacked).

Question 12

Cascading Rollbacks

Answer 12

Lets say we have two transactions which happen in a serial manner (T1 -> T2). Both commits happen after T2.
If we have to rollback T1, then if T2 has used something from T1, then we also rollback T2.

The issue is that if we do not rollback everything, it leads to isolation problems.
If we do abort them, we are rolling back a committed transaction, leading to durability breaks.

Question 13

Recoverable Schedules

Answer 13

A schedule s is recoverable if the following is true:
If a transactions T1 commits and has read item X that was written before by a different transaction T2, then T2 must commit before T1.

Question 14

Recoverable Schedules Example

Answer 14

Lets say we have:

T2 ; Write X
T1; Read X
T2 ; Commit
SYSTEM ERROR
T1; Commit

If we were to perform cascading rollbacks, since they should only effect active transactions, only T1 will be rolled back. This is not an issue since it is performing the read again with the same data since we committed beforehand.

Question 15

Cascade-less Schedules

Answer 15

Only reads values that were written by committed transactions.

Question 16

Cascade-less Schedule Properties

Answer 16

• Recoverable
• (In general) not serialisable
• Can lead to deadlocks

Question 17

Strict Schedules

Answer 17

Each transaction reads and writes values that have already been committed.

Question 18

Strict Two-Phase Locking

Answer 18

Enforces both:
- Conflict-serialisability
- Strict schedules
A transaction must not release any simple or exclusive lock until it has committed or aborted, and that the commit or abort log has been wrote to disk (does not apply to shared locks).

Question 19

Conflict Serialisable Schedule Relations

Answer 19

• always serialisable
• can be recoverable
• can be cascade-less
• can be serial
• can be strict

Question 20

Serialisable Schedule Relations

Answer 20

• can be conflict-serialisable
• can be recoverable
• can be cascade-less
• can be serial
• can be strict

Question 21

Recoverable Schedule Relations

Answer 21

• can be serialisable
• can be cascade-less
• can be conflict-serialisable
• can be strict
• can be serial

Question 22

Strict Schedules Relations

Answer 22

• always cascade-less
• always serialisable
• always conflict-serialisable
• always recoverable
• can be serial

Question 23

Serial Schedules Relations

Answer 23

• always cascade-less
• always serialisable
• always conflict-serialisable
• always recoverable
• always strict

Question 24

Strict 2PL Deadlock

Answer 24

Strict two-phase locking is still susceptible to deadlock.

Question 25

Dealing with deadlocks

Answer 25

- Assume a transaction is in a deadlock if it exceeds a time limit. - Wait-for graphs (restart certain transactions) - Using timestamps There are more general ways: 1) Detect deadlock and fix it 2) Prevent deadlock with deadlock free schedules

Question 26

Timestamps

Answer 26

Each transaction is assigned a unique integer TS(T) upon arrival. For example, if T1 arrives earlier than T2, we require TS(T1) < TS(T2) (we say that T1 is older than T2). Does not allow resets.

Question 27

Wait-Die Scheme

Answer 27

Old transactions will wait for unlocks: - If t1 is older than t2, then t1 is allowed to wait further for t2 to unlock - If t1 is younger than t2, then t1 is rollbacked and dies

Question 28

Wound-Wait Scheme

Answer 28

Old transactions never wait for unlocks: - If t1 is older than t2, then t2 is rollbacked unless it has finished - If t1 is younger than t2, then t1 is allowed to wait further for t2 to unlock

Question 29

Timestamp-based Schedulers

Answer 29

For these schedulers, there are three possible actions per transaction: - grant request - abort transaction - delay transaction Allows resets.

Question 30

Maintaining timestamps of transactions for item X

Answer 30

For each database item X, maintain: - Read time of X: RT(X) -> timestamp of youngest transactions which read X - Write time of X: WT(X) -> timestamp of youngest transactions that wrote X

Question 31

Examples of maintaining timestamps

Answer 31

If T1 requests to read X, either: - abort and restart T1 if WT(X) > TS(T1) - grant request otherwise If T1 requests to write X, either: - abort and restart T1 if WT(X) > TS(T1) or if RT(X) > TS(T1) - grant request otherwise

Question 32

Starvation

Answer 32

Can happen if cascading rollbacks occur in timestamp-based schedulers. If we have: T1 -> r(X), w(x), r(y) T2 -> r(y), w(y), r(x) with TS(T1) = 1, and TS(T2 = 2), we can have starvation occur, with the order being. Line1(T1) Line2(T1) Line3(T1) Line1(T2) Line2(T2) Line3(T2) Line4(T1) RESTART Line1(T1) Line2(T1) Line3(T1) Line1(T2) RESTART

Question 33

Timestamp-based Scheduling overall

Answer 33

- Enforces conflict-serialisable schedules - Prevents deadlocks - Allows cascading rollbacks - Allows starvation

Question 34

Multi-version Concurrency Control

Answer 34

The idea is the same as time-stamp based approaches to scheduling, but you have multiple versions of the database. So instead of overwriting things, we create a new version of the item at time TS(T_i). Also, whenever you read something, you read the latest version if the timestamp if bigger.

Question 35

Rules

Answer 35

- Writes ; abort and restart T1 if RT(X > TS(T1) and otherwise, grant request - Reads ; always grant. There is also a strict variant, where you delay reads until the transaction you read from commits.