Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-04-07
2001-03-13
Alam, Hosain T. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S208000, C709S209000, C712S031000, C713S001000, C714S013000
Reexamination Certificate
active
06202067
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for completing transactions in a fault tolerant distributed database system.
2. Description of the Prior Art
A distributed database system refers typically to a system with two or more separate intercommunicating databases. At least part of the stored data is identical in two or more database copies. Therefore, when common data is changed in one of the database copies, the same change must be made in all the other database copies in order to keep the databases uniform throughout the database system. Under normal circumstances, database changes are made by a master database controller. The database master controller makes changes to its own copy of the database and has responsibility for controlling updates to other copies of the database that comprise the network. Problems arise, however, when faults occurring either in the database copies or the links coupling the copies to the database master controller prevent the transmission or change to all or part of the databases.
Within a distributed database network, information is entered to the individual databases by a transaction. A database “transaction” is a sequence of user controlled (or master database controlled) database actions which is marked by both a “begin step” and an “end step.” The database actions between a begin step and an end step comprise steps or actions by which a database is updated. The end step can be either a commit or an abort. A commit is an instruction to carry out the previous updating transactions, effectively changing the database. An abort is an instruction to void the previous updating transactions. There are two types of transactions that may occur at each processor: cold transactions and hot transactions. A cold transaction is a transaction that has already been completed and is used only during the recovery period of a failed database processor. A hot transaction is an ongoing transaction that has not completed or aborted.
Distributed databases in the telecommunications industry need to be reliable with a high degree of availability. Additionally, these systems need to be fault tolerant as well: the failure of one database copy should not bring down the entire system. The telecommunications industry is very demanding in this regard, as seen in the example of access to information such as 800 numbers. When a call is placed, the response time between the query to the database and the return of the corresponding number associated with the query needs to be immediate and reliable. Any responsive delay creates a delay in completing the call resulting in customer unsatisfaction.
In a distributed database system, data base synchronization is usually provided with an algorithm called “two-phase commit”. A two-phase commit is executed with one copy of the database designated as the “coordinator”, a “master” or a controller and all the other copies in the distributed database system designated as the “participants”, the “slave” nodes or copies. The two-phase commit algorithm operates as follows:
Phase 1
The coordinator sends a message through the network to all participants requesting them to commit a transaction such as updating one or more database records. If a database participant has failed or is otherwise out of service or unavailable, then it should reply to the coordinator with the message indicating it is not ready to commit the transaction. If a participant is unable to respond due to the failure, the “not ready” response is assumed by the coordinator. The coordinator waits to receive responses from all participants before entering Phase 2.
Phase 2
If all database participants respond positively, then the coordinator broadcasts a “commit” message or command to all database participants so that the participants will commit the transaction. If any participant responds with a message indicating a failure or fails to respond, then the coordinator broadcasts an abort message to all participants.
For the master to know the status of active and available participants for the two-phase commit, the master keeps a dynamic list of active and available database processors known as a “quorum”. This dynamic list is used by the master to determine which database processors are active and available, and as such are available to receive update transactions. If a database processor is on the list, it is assumed to be available to successfully commit a transaction.
The object of the present invention is to provide a distributed database system that provides for an appropriate completion to a transaction that did not complete normally because of a failure of the master database processor. It is desirable if the completion of the transaction occurs without the guidance of a new master and without undoing or redoing the transaction.
It is a further object of the present invention to provide a distributed database system that allows all non-failing participants to automatically perform any fault recovery without external coordination eliminating the resulting delay associated with failed transaction cleanup. Further, failing participants are allowed to resynchronize with the non-failed community and participate in new transactions without interrupting any transactions that may be underway during the resynchronization period.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, the foregoing is achieved by providing a method and apparatus for completing database transactions in a distributed database system that may have failed because one or more of the database participants may have failed. If the master database processor fails, all of the non-failing participants either commit the transaction or abort the transaction pending the return to service or replacement of the master database processor. If one of the slave processors fails, either while a transaction is under way or no transaction is under way, the failing slave processor can be resynchronized with the community without affecting the other slave processors that did not fail. When a failed processor returns to service, it can be updated to identically match slave processors that were updated during the time the failed processor was out of contact with the master database processor.
In one embodiment, the invention provides for a pair of timers associated with each of the slave processors. The first timer starts when the begin step of an update transaction is received by the slave processor. The second timer starts when the slave processor is in position to commit the transaction. The first timer resets after receiving each step of an update transaction. If the first timer “times-out” or expires before receiving the next step of the update transaction, the slave processor aborts the current transaction. Upon the conclusion of an update transaction, the master database processor issues a request to commit message to the slave processors querying whether the slave processors can commit the database update transaction. The vote to commit response by each slave processor to the request to commit message triggers the second timer associated with each slave processor. Once the request to commit message is sent from the master processor to the slave processor, the first timer is disabled until a new transaction is received. If the second timer “times-out”, the slave processor commits the transaction.
If the first timer of a slave processor “times-out” it aborts the current transaction, and sends a global abort message to all slave processors. In response to receiving the global abort message, slave processors receiving the global abort will thereafter also abort the current transaction and will transmit its own global abort message to all the slave processors. The result is that all slave processors will abort the current transaction and the network of processors will come to the identical state.
In the preferred embodiment, a record of each update transaction performed by the master database processor is maintained by the master database pro
Blood Mark Lawrence
Coomer Stephen Dexter
Nason David Dayton
Yamini Mohamad-Reza
Alam Hosain T.
Corrielus Jean M.
Lucent Technologies - Inc.
LandOfFree
Method and apparatus for correct and complete transactions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for correct and complete transactions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for correct and complete transactions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521472