Timestamp protocols

DBMS PRESENTATION
ON TIMESTAMP
PROTOCOLS
BY:
PRASHANT PRIYADARSHI (110103135)
PRASHANT SAINI (110103134)
RONIT RAJ (110103160)
PRIYANKA KUMARI(110103139)

INTRODUCTION
•A timestamp is a unique identifier used in DBMS to identify a transaction.
•Typically, timestamp values are assigned in the order in which the transactions
are submitted to the system, so a timestamp can be thought of as the transaction
start time.
•We will refer to the timestamp of transaction T as TS(T).
•Concurrency control techniques based on timestamp ordering do not use locks;
hence, deadlocks cannot occur.

GENERATION OF TIMESTAMPS
•Timestamps can be generated in several ways.
•One possibility is to use a counter that is incremented each time its value is
assigned to a transaction. The transaction timestamps are numbered 1, 2, 3, . . .
in this scheme.
•A computer counter has a finite maximum value, so the system must periodically
reset the counter to zero when no transactions are executing for some short
period of time.
•Another way to implement timestamps is to use the current date/time value of
the system clock and ensure that no two timestamp values are generated during
the same tick of the clock.

TIMESTAMP ORDERING
•A schedule in which the transactions participate is then serializable, and the
equivalent serial schedule has the transactions in order of their timestamp
values. This is called timestamp ordering (TO).
•Notice how this differs from 2PL, where a schedule is serializable by being
equivalent to some serial schedule allowed by the locking protocols.
•In timestamp ordering, however, the schedule is equivalent to the particular
serial order corresponding to the order of the transaction timestamps.
•The algorithm must ensure that, for each item accessed by conflicting
operations in the schedule, the order in which the item is accessed does not
violate the serializability order.
•To do this, the algorithm associates with each database item X two timestamp
(TS) values:-

1. Read_TS(X): The read timestamp of item X; this is the largest timestamp
among all the timestamps of transactions that have successfully read item X—
that is, read _TS(X) = TS(T), where T is the youngest transaction that has
read X successfully.
2. Write_TS(X): The write timestamp of item X; this is the largest of all the
timestamps of transactions that have successfully written item X—that is,
write_ TS(X) = TS(T), where T is the youngest transaction that has
written X successfully.

BASIC TIMESTAMP ORDERING
•Whenever some transaction T tries to issue a read_item(X) or a write_item(X)
operation, the basic TO algorithm compares the timestamp of T with read_TS(X)
and write_TS(X) to ensure that the timestamp order of transaction execution is
not violated.
•The concurrency control algorithm must check whether conflicting operations
violate the timestamp ordering in the following two cases:
1. Transaction T issues a write_item(X) operation:
a. If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then abort and roll back T and
reject the operation. This should be done because some younger transaction
with a timestamp greater than TS(T)—and henceafter T in the timestamp
ordering—has already read or written the value of item X before T had a chance
to write X, thus violating the timestamp ordering.
b. If the condition in part (a) does not occur, then execute the write_item(X)
operation of T and set write_TS(X) to TS(T).

2. Transaction T issues a read_item(X) operation:
a. If write_TS(X) > TS(T), then abort and roll back T and reject the operation. This
should be done because some younger transaction with timestamp greater than
TS(T)—and hence after T in the timestamp ordering—has already written the value of
item X before T had a chance to read X.
b. If write_TS(X) <= TS(T), then execute the read_item(X) operation of T and set
read_TS(X) to the larger of TS(T) and the current read_TS(X).

STRICT TIMESTAMP ORDERING
•A variation of basic TO called strict TO ensures that the schedules are
both strict (for easy recoverability) and (conflict) serializable.
•In this variation, a transaction T that issues a read_item(X) or write_item(X) such
that TS(T) > write_TS(X) has its read or write operation delayed until the
transaction T that wrote the value of X (hence TS(T) = write_TS(X)) has committed
or aborted.
•To implement this algorithm, it is necessary to simulate the locking of an
item X that has been written by transaction T until T is either committed or
aborted. This algorithm does not cause deadlock, since T waits for T only if TS(T) >
TS(T).

THOMAS WRITE RULE
•A modification of the basic TO algorithm, known as Thomas’s write rule,does not
enforce conflict serializability; but it rejects fewer write operations, by modifying
the checks for the write_item(X) operation as follows:
1. If read_TS(X) > TS(T), then abort and roll back T and reject the operation.
2. If write_TS(X) > TS(T), then do not execute the write operation but continue
processing. This is because some transaction with timestamp greater than TS(T)—
and hence after T in the timestamp ordering—has already written the value of X.
Hence, we must ignore the write_item(X) operation of T because it is already
outdated and obsolete. Notice that any conflict arising from this situation would
be detected by case (1).
3. If neither the condition in part (1) nor the condition in part (2) occurs, then
execute the write_item(X) operation of T and set write_TS(X) to TS(T).

Correctness of Timestamp-Ordering
• The timestamp-ordering protocol guarantees serializability
since all the arcs in the precedence graph are of the form:
Thus, there will be no cycles in the precedence graph
• Timestamp protocol ensures freedom from deadlock as no
transaction ever waits.
• But the schedule may not be cascade-free, and may not even
be recoverable.
transaction
with smaller
timestamp
transaction
with larger
timestamp

Recoverability and Cascade Freedom
Problem with timestamp-ordering protocol:
• Suppose Ti aborts, but Tj has read a data item written by Ti
• Then Tj must abort; if Tj had been allowed to commit earlier, the
schedule is not recoverable.
• Further, any transaction that has read a data item written by Tj
must abort
• This can lead to cascading rollback --- that is, a chain of rollbacks
Solution:
• A transaction is structured such that its writes are all performed at
the end of its processing
• All writes of a transaction form an atomic action; no transaction
may execute while a transaction is being written
• A transaction that aborts is restarted with a new timestamp

Multiversion Timestamp Ordering
•Each data item Q has a sequence of versions Q1 < Q2,...., < Qm. Each
version Qk contains three data fields:
–Content -- the value of version Qk.
–W-timestamp(Qk) -- timestamp of the transaction that created
(wrote) version Qk
–R-timestamp(Qk) -- largest timestamp of a transaction that
successfully read version Qk
•when a transaction Ti creates a new version Qk of Q, Qk's W-timestamp
and R-timestamp are initialized to TS(Ti).
•R-timestamp of Qk is updated whenever a transaction Tj reads Qk, and
TS(Tj) > R-timestamp(Qk).

Multiversion Timestamp Ordering (Cont)
The multiversion timestamp scheme presented next ensures
serializability.
Suppose that transaction Ti issues a read(Q) or write(Q) operation.
Let Qk denote the version of Q whose write timestamp is the largest
write timestamp less than or equal to TS(Ti).
• If transaction Ti does a read(Q), then the value returned is the
content of version Qk.
• If transaction Ti does a write(Q), and if TS(Ti) < R-timestamp(Qk),
then transaction Ti is aborted and rolled back. Otherwise, if TS(Ti)
= W-timestamp(Qk), the contents of Qk are overwritten, otherwise
a new version of Q is created.
• Reads always succeed; a write by Ti is rejected if some other
transaction Tj that (in the serialization order defined by the
timestamp values) should read Ti's write, has already read a
version created by a transaction older than Ti.

T1
t1 T2
t2 T3
t3 T4
t4 T5
t5
read2(Y)->Y0
read1(X)->X0
read3(Y)->Y0
write4(Y)
write5(Z)
read6(Z)->Z1
read7(Y)->Y0
abort
read8(X)->X0
write9(Z)
abort
write(Y)
write(Z)
Example Use of the Protocol
A partial schedule for several data items for transactions T1, T2, T3, T4,
T5, with timestamps t1 < t2 < t3 < t4 < t5
Version 0 Version 1
C R W C R W
X X0 1:t5
Y Y0 2:t2 Y1 4:t3
Z Z0 Z1 6:t5 5:t3
Still have
cascading
rollback

Timestamp protocols

Recommended

More Related Content

What's hot (20)

Similar to Timestamp protocols (20)

Recently uploaded (20)

Timestamp protocols