Reliable message propagation in a distributed computer system

Details Reliable message propagation in a distributed computer system Reliable message propagation in a distributed computer system

1999-02-24

2002-05-28

Ray, Gopal C. (Department: 2181)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C709S201000

Reexamination Certificate

active

06397352

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to distributed computer systems, and more specifically, to reliable message propagation in distributed computer systems.
BACKGROUND OF THE INVENTION
One of the long standing challenges in distributed computing has been the propagation of messages from one system to another. In many distributed computing systems, to maintain data consistency it is critical that each message be delivered exactly once to its intended destination site. For example, in a distributed database system, messages that are propagated to a destination site often specify updates that must be made to data that reside at the destination site. The updates are performed as a “transaction” at the destination site. Frequently, such transactions are part of larger distributed transactions that involve many sites. For the purpose of explanation, a message that specifies one or more operations that are to be performed as part of a transaction are referred to herein as “transaction messages”.
If a transaction message is propagated multiple times to a particular destination site, the updates from the transaction may be incorrectly applied multiple times. For example, if a transaction message that debits an account “X” one-hundred dollars is sent twice to a destination site in which the account is maintained, the account “X” may be incorrectly debited two-hundred dollars instead of just one-hundred dollars.
In addition, to maintain data consistency, distributed database systems require that (1) all changes made by a distributed transaction must either be “committed” or, in the event of an error, “rolled back”; and (2) transaction messages are to be processed in the order in which they are received. When a transaction is committed, all of the changes to data specified by the transaction are made permanent. On the other hand, when a transaction is rolled back, all of the changes to data specified by the transaction already made are retracted or undone, as if the changes to the data were never made.
One approach for ensuring data consistency in a distributed computer system is by using a “two-phase commit” sequence to propagate messages between the distributed computer systems. According to the two-phase commit approach, a coordinating system (the source site) is responsible for coordinating the propagation of messages to the participating system (the destination site). For explanation purposes, the dequeue from the propagation queue is the transaction at the source site and the enqueue at the destination queue is the transaction at the destination site. However, in general, the operation at the destination site can be any arbitrary transaction.
The two-phase commit sequence involves two phases, the “prepare phase” and the “commit phase”. In the prepare phase, the transaction is prepared at the destination site. When a transaction is prepared at a destination site, the database is put into such a state that it is guaranteed that modifications specified by the transaction to the database data can be committed. Once the destination site is prepared it is said to be in an “in-doubt” state. In this context, an in-doubt state is a state in which the destination site has obtained the necessary resources to commit the changes for a particular transaction but has not done so because a commit request has not been received from the source site. Thus, the destination site is in-doubt as to whether the changes for the particular transaction will go forward and be committed or instead, be required to be rolled back. After the destination site is prepared, the destination site sends a prepared message to the source site so that the commit phase may begin.
In the commit phase, the source site communicates with the destination site to coordinate either the committing or rollback of the transaction. Specifically, the source site either receives prepared messages from all of the participants in the distributed transaction, or determines that at least one of the participants has failed to prepare. The source site then sends a message to the destination site to indicate whether the modifications made at the destination site as part of the distributed transaction should be committed or rolled back. If the source site sends a commit message to the destination site, the destination site commits the changes specified by the transaction and returns a message to the source site to acknowledge the committing of the transaction. Alternatively, if the source site sends a rollback message to the destination site, the destination site rolls back all of the changes specified by the distributed transaction and returns a message to the source site to acknowledge the rolling back of the transaction. Thus, the two-phase commit sequence can be used to ensure that the messages are propagated exactly once and in order.
For example,
FIG. 1
illustrates a conventional two-phase commit sequence for propagating messages from a source site
102
to a destination site
104
. Source site
102
includes a server process
106
and a database
110
. Server process
106
includes a transmit queue
114
that is used to store messages that need to be transmitted to destination site
104
. In this example, transmit queue
114
currently contains a message (“TX_A”) that needs to be enqueued at destination site
104
. Similarly, destination site
104
includes a server process
108
and a database
112
. Server process
108
includes a receive queue
116
that stores messages that are received from different sites.
In this example, a two-phase commit is performed to propagate TX_A from source site
102
to destination site
104
. To perform the two-phase commit, at state “1”, source site
102
begins a propagation transaction TX_
1
to propagate a message that includes TX_A to destination site
104
. Upon receiving a message, destination site
104
begins a transaction TX_
2
to enqueue a message TX_A. In this example, it shall be assumed that the enqueue of TX_A will require that certain information be updated within data block
114
in database
112
. At state “2”, the source site
102
sends a “prepare” message to the destination site
104
. After preparing the enqueue transaction, destination site
104
must retain the lock on some or all of the data that is contained in data block
114
until it receives a message from source site
102
to commit or abort the enqueue transaction.
Once destination site
104
is prepared, destination site
104
sends a prepared message (state 3) to source site
102
to indicate that it is prepared to commit transaction TX_
2
. The destination site
104
then waits in an in-doubt state for a message from the source site
102
that indicates whether the transaction TX_
2
(enqueue of message TX_A) should be either committed or rolled back. Thus, the destination site
104
cannot release the locks acquired as part of the enqueue transaction until source site
102
responds with a message that indicates whether or not the enqueue of message TX_A is to be committed or rolled back. This may cause other transactions requiring access to data block
114
to be blocked while the enqueue transaction is in an in-doubt state. In certain cases, as when source site
102
fails, destination site
104
may be forced to remain in an in-doubt state for a significant amount of time. Thus, for some systems, such as banking database systems, the delays that can result from failures after a prepared phase in the two-phase commit protocol to propagate messages are unacceptable.
Upon receiving the prepared message, the source site
102
commits transaction TX_
1
(the dequeue of message TX_A from the transaction queue). By committing propagation transaction TX_
1
, a record is stored in nonvolatile memory in database
110
that indicates that transaction TX_
2
in destination site
104
must be committed.
At state “4”, as part of propagation transaction TX_
1
, source site
102
sends a request message to the destination site
104
that indicates whether or not the enqueue of message TX_A should be committed

Affiliated with

Also associated with

Rating

Reliable message propagation in a distributed computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reliable message propagation in a distributed computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reliable message propagation in a distributed computer system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2818928