3
$\begingroup$

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following, it reads

Each transaction is assigned a unique timestamp by its TM (transaction manager). The TM attaches the timestamp to all dm-reads and dm-writes issued on behalf of the transaction, and DMs (data manager) are required to process conflicting operations in timestamp order.

However, this paper did not explain

Question: How to generate the globally unique timestamps for transactions in distributed database systems (assuming no centralized coordination)? What are the commonly used techniques (with references) in this area?

Specifically, is the <local clock, site-id> pair sufficient and appropriate as a timestamp mechanism? If not, why?


[1] Concurrency Control in Distributed Database Systems by Philip A. Bernstein and Nathan Goodman. Computing Surveys, Vol.13, No., 2, June 1981.

$\endgroup$
2
  • $\begingroup$ My gut feeling tells me that in order for (local clock, site id) to be useful, the clocks would have to be precisely synchronized, otherwise an event timestamped $(C_1, N_1)$ could be observed by site $N_2$ at a local time $C_2 < C_1$, so causation would not imply precession. But databases aren't my field. $\endgroup$ May 17, 2015 at 13:53
  • $\begingroup$ @Gilles It seems that although (local clock, site id) provides globally unique timestamps, it needs other mechanisms (what I want to know) to make sure that all the sites commit all the transactions in the same total order defined by the timestamps. Thanks for your opinion. $\endgroup$
    – hengxin
    May 17, 2015 at 14:03

1 Answer 1

1
$\begingroup$

If the only property you need is global uniqueness - serverId+timestamp is good enough. Since every server has one Transaction Manager, that will guarantee uniqueness within one server and ordering; combine with unique server id and that gives global uniqueness.

This types of ids are globally unique, but are not globally ordered. Which is alright in case of transactions itself not being distributed - one transaction is executed by one server.

Edit below is about ordering

In the proposed method (nodeId+timestamp) all transactions do have total order - this comes from the definition - since every transaction id is unique, then we can take any two transactions and compare which one goes first.

But it is important to remember, that that order is not really related to real time - there is no (reliable) way to say which transaction happened first in practice.

Also, this order won't give causality. For example, let's say we executed transaction Ta on node A and based on result of Ta we executed transaction Tb on B.

In total order it is possible that Tb will come before Ta.

And to close the ordering note: if you do need total order with respect of causality, Lamport Timestamp is the way to go.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.