11.2. Timestamp method

An alternative transaction serialization method that works well in rare transaction conflict situations and does not require a transaction waiting graph. based on the use of timestamps.

The basic idea of ​​the method (for which there are many varieties) is as follows: if transaction T1 started before transaction T2, then the system provides such an execution mode as if T1 had been completely completed before the start of T2.

To do this, each transaction T is assigned a timestamp t corresponding to the start time T. When performing an operation on an object r, transaction T marks it with its timestamp and type of operation (read or change).

Before performing an operation on an r object, transaction T1 performs the following actions:

• Checks if transaction T that marked this object has not expired. If T is over, T1 marks the object r and performs its operation.
• If transaction T is not completed, then T1 checks for conflicting operations. If the operations are non-conflicting, with the object r, a timestamp with a lower value remains or is stamped, and transaction T1 performs its operation.
• If operations T1 and T conflict, then if t (T)> t (T1) (that is, transaction T is more “young” than T), T is rolled back and T1 continues to work.
• If t (T) <t (T1) (T is "older" T1), then T1 receives a new timestamp and starts anew.

The disadvantages of the timestamp method are potentially more frequent transaction rollbacks than in the case of synchronization captures. This is due to the fact that transaction conflict is determined more roughly. In addition, in distributed systems it is not very easy to generate global time stamps with a total order ratio (this is a separate big science).

But in distributed systems, these drawbacks pay off because they do not need to recognize dead ends, and as we have already noted, building a waiting graph in distributed systems is very expensive.