Timestamp-based Protocols

The most commonly used concurrency protocol is the timestamp based protocol. This protocol

uses either system time or logical counter as a timestamp.

Lock-based protocols manage the order between the conflicting pairs among transactions at the

time of execution, whereas timestamp-based protocols start working as soon as a transaction

is created.

Every transaction has a timestamp associated with it, and the ordering is determined by the age
of

the transaction. A transaction created at 0002 clock time would be older than all other
transactions

that come after it. For example, any transaction 'y' entering the system at 0004 is two seconds

younger and the priority would be given to the older one.

In addition, every data item is given the latest read and write-timestamp. This lets the system

know when the last ‘read and write’ operation was performed on the data item.

Timestamp Ordering Protocol

The timestamp-ordering protocol ensures serializability among transactions in their conflicting

read

and write operations. This is the responsibility of the protocol system that the conflicting pair of

tasks should be executed according to the timestamp values of the transactions.

 The timestamp of transaction Ti is denoted as TS(Ti).

 Read time-stamp of data-item X is denoted by R-timestamp(X).
 Write time-stamp of data-item X is denoted by W-timestamp(X).
Timestamp ordering protocol works as follows −

If a transaction Ti issues a read(X) operation −

  If TS(Ti) < W-timestamp(X) then Operation rejected.
 If TS(Ti) >= W-timestamp(X) then Operation executed.
 All data-item timestamps updated.

If a transaction Ti issues a write(X) operation −

 If TS(Ti) < R-timestamp(X) then Operation rejected.

 If TS(Ti) < W-timestamp(X) then Operation rejected and Ti rolled back.Otherwise,
operation executed.

Recovery Techniques Based on Deferred Update

- These techniques defer or postpone any actual updates to the database until the

transaction reaches it commit point.

- During transaction execution, the updates are written to the log file.

- After the transaction reaches it commit point, the log file is force-written to disk, then the

updates are recorded in the database.

- If the transaction fails before reaching its commit point, there is no need to undo any

operations because the transaction has not affected the database on disk in any way.

- A typical deferred update protocol uses the following procedure:

1. A transaction cannot change the database on disk until it reaches its commit point.
2. A transaction does not reach its commit point until all its update operations are recorded
in
the log file and the log file is force-written to disk.
- Recovery techniques based on deferred update are therefore known as

NO UNDO/REDO techniques. REDO is needed in case the system fails after a transaction

commits but before all its changes are recorded on disk. In this case, the transaction operations

are redone from the log file.

Recovery Using Deferred Update in a Single-User Environment

 - RDU_S (Recovery using Deferred Update in a Single-User environment) uses

A REDO procedure as follows:

PROCEDURE RDU_S:

- Use two lists of transactions: the committed transactions since the last

checkpoint, and the active transactions (at most one because the system

is single-user).

- Apply the following REDO operation to all the WRITE_ITEM

operations of the committed transactions and restart the active

transactions:

REDO(WRITE_OP):

Redoing a write_item operation WRITE_OP consists of examining its log

entry [write_item,T,X,old_value,new_value] and setting the value of item X in the database to

its new_value, which is the after image (AFIM).

Deferred Update with Concurrent Execution in a Multiuser Environment

- RDU_M(Recovery Using Deferred Update in a Multiuser environment)

algorithm is as follows where the REDO procedure is as defined above:

PROCEDURE RDU_M:

- Use two lists of truncations:

 - T: committed transactions since the last checkpoint (commit list).

- T : active transactions (active list).

- REDO all the WRITE operations of the committed transactions from

the log file, in the order in which they were written in the log.

- The transactions that are active and did not commit are cancelled and

must be resubmitted.

ARIES recovery algorithm

The ARIES Recovery Algorithm is based on:

- WAL (Write Ahead Logging)

- Repeating history during redo:

- ARIES will retrace all actions of the database system prior to the crash to reconstruct

the database state when the crash occurred.

- Logging changes during undo:

- It will prevent ARIES from repeating the completed undo operations if a failure occurs

during recovery, which causes a restart of the recovery process.

The ARIES recovery algorithm consists of three steps:

1. Analysis: step identifies the dirty (updated) pages in the buffer and the set of
transactions active at the time of crash. The appropriate point in the log where redo
is to start is also determined.
2. Redo: necessary redo operations are applied.
3. Undo: log is scanned backwards and the operations of transactions active at the time of
crash are undone in reverse order.

- The Log and Log Sequence Number (LSN)

 - A log record is written for:

(a) data update

(b) transaction commit

(c) transaction abort

(d) undo

(e) transaction end

- A unique LSN is associated with every log record.

- A log record stores

(a) the previous LSN of that transaction

(b) the transaction ID

(c) the type of log record.

For efficient recovery following tables are also stored in the log during checkpointing:

-Transaction table: Contains an entry for each active transaction, with information such as

transaction ID, transaction status and the LSN of the most recent log record for the transaction.

-Dirty Page table: Contains an entry for each dirty page in the buffer, which includes the page
ID

and the LSN corresponding to the earliest update to that page.

The following steps are performed for recovery

- Analysis phase: Start at the begin_checkpoint record and proceed to the

end_checkpoint record. Access transaction table and dirty page table are appended to
the
end of the log. Note that during this phase some other log records may be written to the
log and transaction table may be modified. The analysis phase compiles the set of redo
and undo to be performed and ends.
- Redo phase: Starts from the point in the log up to where all dirty pages have been
flushed,
and move forward to the end of the log. Any change that appears in the dirty page table
is redone.
- Undo phase: Starts from the end of the log and proceeds backward while
performing appropriate undo. For each undo it writes a compensating record in the log.
The recovery completes at the end of undo phase