Timestamp-Based

Concurrency Control

Data Science 310

Boston University

Optimistic Concurrency Control

• Locking is pessimistic.
  • assumes serializability will be violated
  • prevents transactions from performing actions that might violate serializability

• example:

• There are other approaches that are optimistic.
  • assume serializability will be maintained
  • only interfere with a transaction if it actually does something that violates serializability

• deadlock detection+recovery is one such example

• We’ll look at one such approach – one that uses timestamps.

Timestamp-Based Concurrency Control

• In this approach, the DBMS assigns timestamps to txns.
  • TS(T) = the timestamp of transaction T
  • the timestamps must be unique

• TS(T1) < TS(T2) if and only if T1 started before T2

• The system ensures that all operations are consistent with a serial ordering based on the timestamps.

• if TS(T1) < TS(T2), the DBMS only allows actions that are consistent with the serial schedule T1; T2

Timestamp-Based Concurrency Control (cont.)

• Examples of actions that are not allowed:
  • example 1:

Timestamp-Based Concurrency Control (cont.)

• Examples of actions that are not allowed:
  • example 2:

Timestamp-Based Concurrency Control (cont.)

• When a txn attempts to perform an action that is inconsistent with a timestamp ordering:
  • the offending txn is rolled back
  • it is restarted with a new, larger timestamp

• With a larger timestamp, the txn comes later in the equivalent serial ordering.
  • allows it to perform the offending operation

• Rolling back the txn ensures that all of its actions correspond to the new timestamp.

Timestamps on Data Elements

• To determine if an action should be allowed, the DBMS associates two timestamps with each data element:
  • a read timestamp: RTS(A) = the largest timestamp of any txn that has read A

• the timestamp of the reader that comes latest in the equivalent serial ordering

• a write timestamp: WTS(A) = the largest timestamp of any txn that has written A

• the timestamp of the writer that comes latest in the equivalent serial ordering

• the timestamp of the txn that wrote A’s current value

Timestamp Rules for Reads

• When T tries to read A:
  • if TS(T) < WTS(A), roll back T and restart it

• T comes before the txn that wrote A, so T shouldn’t be able to see A’s current value

• T’s read is too late (see our earlier example 1)

• else allow the read
  • T comes after the txn that wrote A, so the read is OK

• the system also updates RTS(A):

        RTS(A) = max(TS(T), RTS(A))

• why can’t we just set RTS(A) to T’s timestamp?

      there may be a previous reader of A that comes after T in the timestamp ordering

Timestamp Rules for Reads (cont.)

• Example: assume that T1 wants to read A, and we have the following timestamps:

• T1 started before T2 (30 < 50)
  • thus T1 comes before T2 in the equivalent serial ordering

• T2 has already read A. How do we know? RTS(A) = TS(T2)

• Despite that, it’s okay for T1 to read A.
  • reads don’t conflict, so we don’t care about the equivalent serial ordering of two readers of an item

• what matters is that T1 comes after the writer of A’s current value (30 > 10)

Timestamp Rules for Writes

• When T tries to write A:
  • if TS(T) < RTS(A), roll back T and restart it

• T comes before the txn that read A, so that other txn should have read the value T wants to write

• T’s write is too late (see our earlier example 2)

• else if TS(T) < WTS(A), ignore the write and let T continue

• T comes before the txn that wrote A’s current value

• thus, in the equivalent serial schedule, T’s write would have been overwritten by A’s current value

• else allow the write
  • how should the system update WTS(A)?

      WTS(A) = TS(T)

Thomas Write Rule

• The policy of ignoring out-of-date writes is known as the Thomas Write Rule:
  • …else if TS(T) < WTS(A), ignore the write and let T continue

• What if there is a txn that should have read A between the two writes? It’s still okay to ignore T’s write of A.

• example:
  • TS(T) = 80, WTS(A) = 100 → we ignore T’s write of A
    what if txn U with TS(U) = 90 is supposed to read A?

• if U had already read A, Thomas write rule wouldn’t apply:
  • RTS(A) = 90
  • T would be rolled back because TS(T) < RTS(A)

• if U tries to read A after we ignore T’s write:
  • U will be rolled back because TS(U) < WTS(A)

Example of Using Timestamps

• They prevent our problematic balance-transfer example.

T2 performed a dirty read. It would also need to be rolled back. (a cascading rollback!)

Multiversion Timestamp Protocol

• To reduce the number of rollbacks, the DBMS can keep old versions of data elements, along with the associated timestamps.

• When a txn T tries to read A, it’s given the version of A that it should read, based on the timestamps.

• the DBMS never needs to roll back a read-only transaction!

Multiversion Timestamp Protocol (cont.)

• Because each write creates a new version, the WTS of a given version never changes.
• The DBMS maintains RTSs and commit bits for each version, and it updates them using the same rules as before.

• If txn T attempts to write A:
  • find the version of A that T should be overwriting (the one with the largest WTS < TS(T))
  • compare TS(T) with the RTS of that version

• example: txn T (TS = 50) wants to write A

• it should be overwriting A(0)

• should we allow its write and create A(50)?

      no. 50 < 75, so T’s write is too late

Multiversion Timestamp Protocol (cont.)

• If T’s write of A is not too late:
  • create a new version of A with WTS = TS(T)

• Writes are never ignored.
  • there may be active txns that should read that version

• Versions can be discarded as soon as there are no active transactions that could read them.

• can discard A(t1) if:
  • there is another, later version, A(t2), with t2 > t1

        and

• there is no active transaction with a TS < t2

• example: we can discard A(0) as soon as there are no remaining txns with TS < 105

Locking vs. Timestamps

• Advantages of timestamps:
  • txns spend less time waiting
  • no deadlocks

• Disadvantages of timestamps:
  • can get more rollbacks, which are expensive
  • may use somewhat more space to keep track of timestamps

• Advantages of locks:
  • only deadlocked txns are rolled back

• Disadvantages of locks:
  • unnecessary waits may occur

The Best of Both Worlds

• Combine 2PL and multiversion timestamping!

• Transactions that perform writes use 2PL.
  • their actions are governed by locks, not timestamps

• thus, only deadlocked txns are rolled back

• Multiple versions of data elements are maintained.
  • each write creates a new version

• the WTS of a version is based on when the writer commits, not when it started

• Read-only transactions do not use 2PL.
  • they are assigned timestamps when they start

• when T reads A, it gets the version from right before T started
  • will only get a version whose writer has committed

• read-only txns never need to wait or be rolled back!