11.5 Timestamping

An alternate concurrency control mechanism that eliminates the deadlock problem is timestamping. In this scheme, no locks are used, so no deadlocks can occur. A timestamp for a transaction is a unique identifier that indicates the relative starting time of the transaction. It could be the reading on the system clock at the time the transaction started, or it could be the value of a logical counter that is incremented every time a new transaction starts. In either case, the timestamp value of each transaction T, which we will indicate by TS(T), is unique and indicates how old the transaction is. The effect of timestamping is to assign a serial order to the transactions. The protocol then ensures that the order is met, by not permitting any reads or writes that would violate the order. In addition to transaction timestamps, there are timestamps for data items. Each data item, x, has two timestamps:

  • Read-Timestamp(x), giving the timestamp of the last transaction that read the item. It is updated when a read(x) operation is done by a transaction.

  • Write-Timestamp(x), giving the timestamp of the last transaction to write (update) the item. It is updated when a write(x) is done.

11.5.1 Basic Timestamping Protocol

In traditional databases, two problems can arise with timestamping:

  1. Late read. A transaction, T, asks to read an item that has already been updated by a younger transaction, which is a transaction that started execution after T began executing.

  2. Late write. T asks to write an item whose current value has already been read or written by a younger transaction.

With a late read, the value that T needs to read is no longer available because it has already been overwritten, so T must roll back and restart with a later timestamp. With a late write, a younger transaction has already read the old value or written a new one. Again, the solution is to roll back T and restart it using a later timestamp. The following rules summarize this basic timestamping protocol. We always test the timestamp of the transaction, TS(T), against the Write-Timestamp(x) and/or Read-Timestamp(x) that identify the transaction(s) that last wrote or read the data item, x.

  1. If T asks to read a data item x, compare the transaction’s timestamp, TS(T) with WriteTimestamp(x).

    1. If Write-Timestamp(x) <= TS(T), then proceed using the current data value and replace Read-Timestamp(x) with TS(T). However, if Read-Timestamp(x) is already larger than TS(T), just do the read and do not change Read-Timestamp(x).

    2. If Write-Timestamp(x) > TS(T), then T is late doing its read, and the value of x that it needs is already overwritten, so roll back T.

  2. If T asks to write a data item x, compare TS(T) with both Write-Timestamp(x) and Read-Timestamp(x).

    1. If Write-Timestamp(x) <= TS(T) and Read-Timestamp(x) <= TS(T), then do the write and replace Write-Timestamp(x) with TS(T).

    2. Else roll back T.

In the case of a late write, 2(b), the reason that we have to roll back if Read-Timestamp(x) is later than TS(T) is that a younger transaction has already read the current value and replacing that value now would create a data inconsistency. If Write-Timestamp(x) is later than TS(T), the value T is trying to write is an obsolete value.

This scheme guarantees that transactions will be serializable and the results will be equivalent to a serial execution schedule in which the transactions are executed in chronological order by the timestamps. FIGURE 11.15 illustrates what happens when the standard timestamping protocol is applied to the schedule showing the inconsistent analysis problem in Figure 11.5. At time t1, the values in BAL_A, BAL_B, and BAL_C are all 5000, and their read and write timestamps, which we call R and W, respectively, are some earlier time, which we will call t0. Transaction SUMBAL is assigned a timestamp of t1, its starting time. Note that this remains its timestamp throughout its duration, regardless of the clock reading. Any reading or writing that SUMBAL does will have the timestamp t1 associated with it, even though the clock reading may have advanced. TRANSFER begins at time t2 and is given transaction timestamp t2. When SUMBAL tries to do a read BAL_A at time t3, its timestamp, t1, is compared with the W value of BAL_A, which is t0. Because this is less than its own timestamp, t1, it reads the value 5000 and, because the R value of BAL_A is less than t1, it replaces the t0 with t1. Similarly, when TRANSFER requests a read of BAL_A, it is permitted to do the read and replaces the R value with its timestamp, t2. At t6, when TRANSFER writes a new value for BAL_A, the write timestamp is changed to t2, which is the timestamp for the TRANSFER transaction. Processing continues normally until time t11, when SUMBAL tries to do a late read. Because the W value of BAL_C is t2, we can see that this value has been written by a later transaction, so SUMBAL cannot read the appropriate value, which has already been overwritten, and it must roll back. It then restarts with a later timestamp, such as t13.

A table with 7 columns labeled Time, SUMBAL, TRANSFER, BAL underscore A R W, BAL underscore B R W, BAL underscore C R W, SUM. The row entries are as follows. Row 1. Time: t 1. SUMBAL: BEGIN TRANSACTION Assign timestamp t 1. TRANSFER: blank. BAL underscore A R W: 5000, t 0, t 0. BAL underscore B R W: 5000, t 0, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 2. Time: t 2. SUMBAL: SUM equals 0 semicolon. TRANSFER: BEGIN TRANSACTION Assign timestamp t 2. BAL underscore A R W: 5000, t 0, t 0. BAL underscore B R W: 5000, t 0, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 3. Time: t 3. SUMBAL: read BAL underscore A open parentheses 5000 close parentheses. TRANSFER: dot, dot, dot. BAL underscore A R W: 5000, t 1, t 0. BAL underscore B R W: 5000, t 0, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 4. Time: t 4. SUMBAL: SUM equals SUM plus BAL underscore A open parentheses 5000 close parentheses. TRANSFER: read BAL underscore A open parentheses 5000 close parentheses. BAL underscore A R W: 5000, t 2, t 0. BAL underscore B R W: 5000, t 0, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 5. Time: t 5. SUMBAL: read BAL underscore B open parentheses 5000 close parentheses. TRANSFER: BAL underscore A equals BAL underscore A minus 1000 open parentheses 4000 close parentheses. BAL underscore A R W: 5000 t 2, t 0. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 6. Time: t 6. SUMBAL: SUM equals SUM plus BAL underscore B open parentheses 10000 close parentheses. TRANSFER: blank. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 5000, t 0, t 0. SUM: blank. Row 7. Time: t 7. SUMBAL: read BAL underscore C open parentheses 5000 close parentheses. TRANSFER: blank. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 5000, t 1, t 0. SUM: blank. Row 8. Time: t 8. SUMBAL: blank. TRANSFER: Read BAL underscore C open parentheses 5000 close parentheses. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 5000, t 2, t 0. SUM: blank. Row 9. Time: t 9. SUMBAL: blank. TRANSFER: BAL underscore C equals BAL underscore C plus 1000 open parentheses 6000 close parentheses. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 5000, t 2, t 0. SUM: blank. Row 10. Time: t 10. SUMBAL: blank. TRANSFER: write BAL underscore C open parentheses 6000 close parentheses. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 1, t 0. BAL underscore C R W: 6000, t 2, t 2. SUM: hyphen. Row 11. Time: t 11. SUMBAL: Read BAL underscore C late read ROLLBACK. TRANSFER: blank. BAL underscore A R W: 4000, t 2, t 2. BAL underscore B R W: 5000, t 0, t 0. BAL underscore C R W: 6000, t 2, t 2. SUM: hyphen. Row 12. Time: t 12. SUMBAL: blank. TRANSFER: COMMIT. BAL underscore A R W: blank. BAL underscore B R W: blank. BAL underscore C R W: blank. SUM: blank. Row 13. Time: t 13. SUMBAL: restart with timestamp t 13. TRANSFER: blank. BAL underscore A R W: blank. BAL underscore B R W: blank. BAL underscore C R W: blank. SUM: blank. Row 14. Time: dot, dot, dot. SUMBAL: blank. TRANSFER: blank. BAL underscore A R W: blank. BAL underscore B R W: blank. BAL underscore C R W: blank. SUM: blank.

FIGURE 11.15 Timestamping Applied to Figure 11.5

11.5.2 Thomas’s Write Rule

A variation of the basic timestamping protocol that allows greater concurrency is one in which some obsolete writes can safely be ignored without rolling back the transaction. It applies in the case where T is trying to do a write to data item x but a new value has already been written for x by a younger transaction. If a younger transaction has already read x, then it needed the value that T is trying to write, so it is necessary to roll back T and restart it. Otherwise, the transaction can proceed, with or without doing a write according to the following write protocol, called Thomas’s write rule, which applies to transaction T trying to write x.

  1. If Read-Timestamp(x) > TS(T), then a younger transaction needed the new value, so T has to be rolled back.

  2. If Write-Timestamp(x) > TS(T) but Read-Timestamp (x) <= TS(T), the write operation can be ignored because it is obsolete, but T can proceed because its write was not needed.

  3. Else do the write operation and replace Write-Timestamp(x) by TS(T).

11.5.3 Multiversion Timestamping

The timestamping protocols discussed so far assume that there is only one version of each data item in the database. Concurrency can be increased if we allow multiple versions to be stored, so that transactions can access the version that is consistent for them. With multiversioning, each data item x has a sequence of versions <x1, x2,…, xn>, each of which has the following:

  • The content field, a value for xi

  • A Write-Timestamp(xi), which is the timestamp of the transaction that wrote the value

  • A Read-Timestamp(xi), which is the timestamp of the youngest transaction (i.e., the one with the largest timestamp) that has read version xi

Whenever a write(x) is done, a new version of x is created, with the appropriate WriteTimestamp. When a read(x) is done, the system selects the appropriate version of x. The multiversion timestamp protocol is as follows:

  1. When transaction T does a read(x), the value that is returned is the value of the content field associated with the latest Write-Timestamp that is less than or equal to TS(T). The Read-Timestamp is then set to the later of TS(T) or its current value.

  2. When T does a write(x), the version we must use is the one whose Write-Timestamp is the largest one that is less than or equal to TS(T). For that version:

    1. If Read-Timestamp(x) > TS(T), indicating that x has already been read by a younger transaction, roll back T, because it would be a late write.

    2. Else create a new version of x, with Read- and Write-Timestamps equal to TS(T).

For example, assume that the following read-only transaction, T, is to be performed and has been assigned a timestamp of 10:

A listing of a transaction. Line 1. Transaction T colon. Line 2. Read V A L, semicolon. Line 3. Dot, dot, dot.

In FIGURE 11.16(A), Transaction T with timestamp 10 requests a data item VAL that has already been updated by a transaction with timestamp 11, as shown by the Write-Timestamp for the current version, Version 2. However, an old version of the data item, Val, Version 1, exists with a content value of 100 and a Write-Timestamp of 9. Because this is the last Write-Timestamp less than or equal to the transaction’s timestamp (10), we use that version for transaction T. The Read-Timestamp of that version is then changed to 10 as shown in FIGURE 11.16(B). The effect of this process is to ensure that the transactions read data items as if they were executed serially.

A table with 4 columns labeled VERSION, VAL, Read hyphen Timestamp, and Write hyphen Timestamp. The row entries are as follows. Row 1. VERSION: 1. VAL: 100. Read hyphen Timestamp: 9. Write hyphen Timestamp: 9. Row 2. VERSION: 2, current version. VAL: 150. Read hyphen Timestamp: 11. Write hyphen Timestamp: 11. A table with 4 columns labeled VERSION, VAL, Read hyphen Timestamp, and Write hyphen Timestamp. The row entries are as follows. Row 1. VERSION: 1. VAL: 100. Read hyphen Timestamp: 10. Write hyphen Timestamp: 9. Row 2. VERSION: 2, current version. VAL: 150. Read hyphen Timestamp: 11. Write hyphen Timestamp: 11. A table with 4 columns labeled VERSION, VAL, Read hyphen Timestamp, and Write hyphen Timestamp. The row entries are as follows. Row 1. VERSION: 15. BAL: 500. Read hyphen Timestamp: 19. Write hyphen Timestamp: 19. Row 2. VERSION: 16, current version. BAL: 600. Read hyphen Timestamp: 21. Write hyphen Timestamp: 21
A table with 4 columns labeled VERSION, VAL, Read hyphen Timestamp, and Write hyphen Timestamp. The row entries are as follows. Row 1. VERSION: 15. BAL: 500. Read hyphen Timestamp: 19. Write hyphen Timestamp: 19. Row 2. VERSION: 16, current version. BAL: 600. Read hyphen Timestamp: 21. Write hyphen Timestamp: 21. Row 3. VERSION: 151. BAL: 490. Read hyphen Timestamp: 20. Write hyphen Timestamp: 20.

FIGURE 11.16 Multiversion Timestamping Examples

Assume a transaction, S, does both a read and a write operation and is assigned a timestamp of 20. The transaction is

A listing of a transaction. Line 1. Transaction S, colon. Line 2. Read BAL, semicolon. Line 3. BAL equals BAL minus 10, semicolon. Line 4. Write BAL, semicolon.

In FIGURE 11.16(C), transaction S with timestamp 20 is doing a write to an item, BAL, whose current version, version 16, was written by a later transaction with timestamp 21. However, we examine the version whose Write-Timestamp is less than or equal to 20 (version 15 in this case). For that version, because the Read-Timestamp is less than or equal to 20, this is not a late write, so we create a new version with both timestamps of 20, as shown in FIGURE 11.16(D).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.22.41.212