Method for transaction recovery in three-tier applications

[0002] The present invention relates generally to transaction processing systems and more particularly to an efficient method for transaction recovery in three-tier applications.

[0003] Commonly, human end-users are exposed to many different failures and error situations in systems which are called transaction processing systems (TPS). TPSs are three-tier (client-server-database) systems which allow client applications to perform database transactions. “Client” refers to an end-user mode of operation and level of access where requests are made for server processing or database information. As examples of database transactions, there are various reservations systems, such as for airlines, hotels and car rentals, and financial systems, such as banking, credit card, and automated teller machines. In these systems, a customer or sales representative uses a client application at the client level that allows a user to query and update a database. A client interface allows the client application to specify which database to add information to or to update. However, if a failure occurs in either the second tier application server or the third tier database, for example during an update, it is difficult for the client to know whether the update was actually performed or not.

[0004] As an example, for an Automated Teller Machine (ATM) failure, it is likely that the ATM customer would need to call the bank to find out whether the transaction was completed properly. This would generate more work for bank employees and create unsatisfied customers and would be very costly in terms of the lost business, reduced productivity, and unsatisfied customers.

[0005] Essentially, the client needs to query the database and see if the update has been performed and if it has not, to reissue the update. Even this solution is, however, not failure proof.

[0006] First, the system might not know what the values were before the update, and if the update is relative to the old value, the client might not be able to determine whether the initial update was performed or not. For example, if the ATM transaction involved a deposit to an account, the bank employee would have to have information regarding the previous balance and any other deposits and withdrawals that may have occurred to the account around the time of its failure.

[0007] Second, another client might have done an update after the first client's query and failed update. Therefore, the first client will not be able to determine with confidence whether the update was performed or not, requiring the first client would have to guess what to do.

[0008] Thus, involving the client in the recovery of a failed request should be avoided to the largest possible extent. Unfortunately, complex commercial database systems and transaction processing systems generally fail to provide client transparency, or the ability to detect and correct problems without human intervention. Rather, it is expected that the failure recovery either be handled by the client or be coded into applications.

[0009] Embedding the failure recovery into the application code complicates the application considerably and is error prone.

[0010] Implementing error recovery logic is difficult and complex. Client applications as well as application servers currently need to implement error recovery as part of the application specific code. Further, the error recovery logic is not necessarily reusable for any application adhering to the described architecture.

[0011] Traditional solutions have centered around devices called “transaction coordinators”, which are responsible for coordinating and terminating transactions against one or more databases. The potential for failure in both the coordinator and the databases requires that some recovery information be maintained so that a consistent state can be maintained when recovering after failures. This is necessary so that transactions that were in the process of being terminated when a failure occurred can be completely terminated upon recovery. There are problems with these systems however.

[0012] First, traditional systems keep the recovery information in their local disk file on the same machine that runs the transaction coordinator. Maintaining this disk file has a performance cost due to the continual writing of entries to the disk file.

[0013] A second problem with maintaining recovery information in local disk files is in emerging three-tier applications. It is desirable for the transaction coordinators to recover as stateless in the middle tier, which means that entries should replicate freely and that it should be possible that a crash can occur on one node and recovery can occur on a different node. Having recovery information in local disk files so hampers that flexibility that the benefits of three-tier applications are lost.

[0014] Third, current transaction coordinators do not perform “outcome determination”. “Outcome determination” is when the result of a transaction is needed to make a decision. The coordinators keep recovery information around long enough for consistent recovery by the application server, but the moment that a transaction has completely terminated, whether it's abort or commit, the information is deleted. In some cases this is too early because the client machines need to know the outcome in order to determine if they are retrying aborted transactions. Using the recovery information can save a system from duplicating its efforts.

[0015] The latter two problems have been major long-term obstacles to the wide spread adoption of three-tiered systems.

[0016] An answer has long been sought to solve the above problems, but it has also long eluded those skilled in the art.

[0017] The present invention provides a three-tiered transaction processing system in which state information maintained in the database tier is used to facilitate recovery of transaction coordinators without the transaction coordinators having to maintain their own recovery information and a method of accessing such state information.

[0018] The present invention further provides for a three-tiered transaction processing system in which state information maintained in the database tier is used to facilitate recovery of transaction coordinators without the transaction coordinators having to maintain their own recovery information and a method of accessing such state information while controlling the lifetime of this recovery information; i.e., keeping it around long enough so that client tier will have a consistent view of the world before the information is forgotten. This solves the problem of outcome determination.

[0019] The present invention further provides an extension of the XA interface, a standard used by database management systems to control transactions, to also include two additional methods that give access to the set of committed transactions in the database transaction log and the set of prepared transactions in the transaction log of the database management system. The present invention exploits the fact that the transaction log contains entries about committed and prepared transactions already. This solves the problem that the database management system forgets about those entries once transactions are committed.

[0020] The present invention further provides for a three-tiered transaction processing system that eliminates the performance cost associated with the writing of recovery information to the server.

[0021] The present invention further provides for a three-tiered transaction processing system with stateless recovery in the middle tier. If one server crashes, the recovery information is stored in the database and recovery can take place on a different server node.

[0022] FIG. 1 shows the structure of a generic three-tier application;

[0023] FIG. 2 is a timeline illustrating the operation of the invention in the case of a single failure-free database;

[0024] FIG. 3 is a timeline illustrating how the invention handles a server failure in the case of a single database system;

[0025] FIG. 4 is a timeline illustrating how the invention handles a database failure in the case of a single database system;

[0026] FIG. 5 is a timeline illustrating a failure-free execution of the invention in the case of a multiple database system;

[0027] FIG. 6 is a timeline illustrating how the invention handles a server failure in the case of a multiple database system; and

[0028] FIG. 7 is a timeline illustrating how the invention handles a database failure in the case of a multiple database system.

[0029] Referring now to FIG. 1, therein is shown the structure of a generic three-tier application. It consists of a first tier 10, a second tier 12, and a third tier 14. The first tier 10 is composed of one or more client machines C₁16 through C_n18. The first tier client machines C₁, 16 through C_n18 submit requests to the second tier applications servers 12. The second tier 12 can be made up of any number of applications servers S₁20 and S₂22. The server S₁20 has two parts, an S₁22 request processor 24 and an S₁transaction coordinator 26. The server S₂22 also has two parts, an S₂request processor 28 and an S₂transaction coordinator 30. The second tier application servers S₁20 and S₂22 perform transactions against one or more databases in the third tier 14. The third tier 14 is composed of one or more database machines DB₁32 through DB_n34.

[0030] Referring now to FIG. 2, therein is shown a timeline illustrating the operation of the invention in the case of a single database system. The three tiers are represented by a single client machine 100, a single application server 102, and a single database 104. The application server 102 is composed of two parts, a request processor 106 and a transaction coordinator 108. The starting point of the transaction is the client 100 sending a process request message 110 to the application server 102. In response, the request processor 106 inside the application server 102 first issues a start operation 112 to the database 104, then performs some transient manipulation 114 to the database 104 and finally ends the transaction 116. At this point in time, the manipulation of information inside the database is complete but the changes have yet to take effect and are undoable.

[0031] In order commit or terminate the transaction, the request processor 106 sends a terminate message 118 to the transaction coordinator 108. In response, the transaction coordinator 108 inside of the application server 102 issues a commit message 120 to the database 104. The database 104 sends an acknowledgement 122 back to the transaction coordinator 108 upon completion of the commit 120. The transaction coordinator 108 then returns the status of the commit by sending an affirmative reply signal 124 to the request processor 106. In turn, the request processor 106 then returns the status of the commit by sending an affirmative reply signal 126 to the client 100.

[0032] Upon receipt of an affirmative reply signal 126, the client 100 is in a consistent state as the outcome of the transaction is now known. The client 100 then instructs the system to forget about the transaction by sending a forget signal 128 to the request processor 106. The request processor 106 sends out its own forget signal 130 to the transaction coordinator 108 which in turn sends a forget signal 132 to the database 104.

[0033] Referring now to FIG. 3, therein is shown a timeline illustrating how the invention handles server failures in the case of a single database system. The three tiers are represented by a single client machine 200, a single application server 202, and a single database 204. The application server 202 is composed of two parts, a request processor 206 and a transaction coordinator 208. The starting point of the transaction is the client 200 sending a process request message 210 to the application server 202. In response, the request processor 206 inside the application server 202 first issues a start operation 212 to the database 204 and hen performs some transient manipulation 214 to the database 204. However, before the can be committed as in FIG. 1, the application server 202 experiences a failure 216. The application server 202 goes through a recovery process 216 wherein the process is restarted. During the recovery period, the client 200 detects the server failure 220 through a time-out or similar mechanism. As the application server 202 restarts, the recover protocol begins as the request processor 206 sends the recover message 222 to the transaction coordinator 208. Because the transaction coordinator 208 has no state of its own, it needs to find out what the database 204 what was doing before the server failure 216. It therefore queries the database 204 by sending it a committed message 224 to obtain information about transactions that the client 200 may not know about, may not know the outcome of, or may be interested in retrying. A reply 226 sent back from the database 204 is made up of a list of transaction IDs that had been committed but not yet forgotten. In response to the reply 226, the transaction coordinator 208 creates a local data structure that contains information about the committed transactions and then sends a reply 228 to the request processor 206.

[0034] In the meantime the client 200 has detected the failure 216. The client 200 does not actually know if the transaction was committed or not, so it sends a retry message 230 to the request processor 206 which in response sends a committed message 232 to the transaction coordinator 208 to find out if the transaction was actually committed. The transaction coordinator 208 then takes the information that it got back from the database 204 in the reply 226 and checks to see if the pertinent transaction ID is part of the committed set. In this case the transaction ID is not part of the committed set because the application server 202 crashed before committing so the reply 234 sent back to the request processor 206 is negative. Because of the negative reply 234, the request processor 206 issues a rollback command 236 to undo the transient database changes and roll back the transaction that was in progress. The request processor 206 then simulates a client process request message by sending itself a process request message 238 and restarts the process with a start message 240 identical to the initial start message 212. The transaction then continues on as in the failure-free case shown in FIG. 2

[0035] Referring now to FIG. 4, therein is shown a timeline illustrating how the invention handles a database failure in the case of a single database system. The three tiers are represented by a single client machine 300, a single application server 302, and a single database 304. The application server 302 is composed of two parts, a request processor 306 and a transaction coordinator 308. The starting point of the transaction is the client 300 sending a process request message 310 to the application server 302. In response, the request processor 306 inside the application server 302 first issues a start operation 312 to the database 304 and then performs some transient manipulation 314 to the database 304. Before the database transient manipulation 314 has been completed however, the database 304 experiences a failure 316 and crashes and the manipulate call returns an error code 318 to the request processor 306. The request processor 306 then sends an exception 320 to the client machine 300 letting it know that a problem of some type has occurred. The application server 302 then detects the database failure 322 and calls a rebuild c-set (committed set) method 324 after the database 304 recovers in order to reestablish its view of which transactions had been committed before the crash occurred. The transaction coordinator 308 then sends a committed query 326 to the database 304 to get the list of committed transactions. In response, the database returns the set of committed transactions in its reply 328. In comparing the lists of committed transactions from the transaction coordinator 308 and the database 304, differences may appear due to the database failure 316. As a result, the database 304 committed list must be updated and expired messages removed so a forget message 330 is sent from the transaction coordinator 308 to the database 304.

[0036] In the meantime the client machine 300 upon receiving the exception 320 retries the original process request 310 by sending a retry signal 332 to the request processor 306 of the application server 302. The request processor 306 then checks with the transaction coordinator 308 to see whether the transaction has already been committed and, not finding it committed due to the database failure 316, is sent back a negative reply 336. In response, the request processor 306 issues a rollback command 338 to undo the transient database changes and roll back the transaction that was previously in progress. The request processor 306 then simulates a client process request message by sending itself a process request message 340 and restarts the process with a start message 342 identical to the initial start message 312. The transaction then continues on as in the failure-free case shown in FIG. 2.

[0037] Referring now to FIG. 5, therein is shown a timeline illustrating a failure-free execution of the invention in the case of multiple databases. The three tiers are represented by a single client machine 400, a single application server 402, and one or more databases DB₁404 through DB_n406. The application server 402 is composed of two parts, a request processor 408 and transaction coordinator 410. The starting point of the transaction is the client 400 sending a process request message 412 to the application server 402. In response, the request processor 408 inside the application server 402 issues multiple start operations 414 to the databases DB₁404 through DB_n406, then manipulates 416 the databases DB₁404 through DB_n406, and finally terminates the transaction with the databases DB₁404 through DB_n406 with an end message 418.

[0038] In order to make the changes permanent in the databases, a two-phase commit protocol is initiated with a terminate message 420 from the request processor 408 to the transaction coordinator 410. A prepare message 422 is then sent to all of the databases DB₁404 through DB_n406 requesting a vote on whether the databases can all commit to the changes occurring in the transaction. In this failure-free case, all votes come back in affirmative vote messages 424 causing the transaction coordinator 410 to send a commit message 426 to all of the databases DB₁404 through DB_n406. When all the databases DB₁404 through DB_n406 have replied with acknowledgement messages 428 representing their reception and processing of the commit messages 426, the transaction coordinator 410 returns an affirmative reply 430 to the request processor 408. The request processor 408 informs the client 400 that the transaction was completed successfully with an affirmative reply 432, and the client 400, as in the single database case in FIG. 2, initiates a forget process with a forget message to the request processor 408. The request processor 408 signals the transaction coordinator 410 with a forget message 436, and transaction coordinator 410 notifies the databases DB₁404 through DB_n406 with forget messages 438.

[0039] Referring now to FIG. 6, therein is shown a timeline illustrating how the invention handles server failures in the case of a multiple database system. The three tiers are represented by a single client machine 500, a single application server 502, and one or more databases DB₁504 through DB_n506. The application server 502 is composed of two parts, a request processor 508 and transaction coordinator 510. The starting point of the transaction is the client 500 sending a process request message 512 to the application server 502. In response, the request processor 510 inside the application server 502 issues multiple start operations 514 to the databases DB₁504 through DB_n506, then manipulates 516 the databases DB₁504 through DB_n506. However, before the transaction can be committed as in FIG. 5, the application server 502 experiences a failure 518.

[0040] The application server 502 goes through a recovery period wherein the process is restarted. During the recovery period, the client 500 detects the server failure 520 through a time-out or similar mechanism. As the application server 502 restarts, the recover protocol begins as the request processor 508 sends the recover message 522 to the transaction coordinator 510. Because the transaction coordinator 510 has no state of its own, it needs to find out what the database what was doing before the server failure. It therefore queries the databases DB₁504 through DB_n506 by sending them committed queries 524 to obtain information about transactions that the client 500 may not know about, may not know the outcome of, or may be interested in retrying. The replies 526 sent back from the databases DB₁504 through DB_n506 make up a committed set of transaction IDs that have been committed but not yet forgotten. With the information from the replies 526, the transaction coordinator 510 reconstructs the state of the application 502 before the server failure 518 and for each transaction listed, sends a commit message 528 to the databases DB₁504 through DB_n506. The databases DB₁504 through DB_n506 send back affirmative acknowledgements 530 to the transaction coordinator 510 when all the transactions in the committed set are committed.

[0041] In order to fully recover, the transaction coordinator 510 next constructs a set of transactions that were in a prepared but not yet committed state before the server failure 518 occurred by sending a prepared message 532 to all of the databases DB₁504 through DB_n506 and getting a list of prepared transaction ID's back in a reply 534. It aborts those transactions with abort messages 536 to the databases DB₁504 through DB_n506 and waits for affirmative acknowledgements 538 to confirm the abortions. After receiving the acknowledgements 538, the transaction coordinator 510 knows that all the transactions that were in progress before the crash have now been consistently terminated either by committing or terminating them and can send back an okay signal 540 to the request processor 508.

[0042] In the meantime the client 500 has detected the server failure 518. The client 500 does not actually know if the transaction was committed or not, so it sends a retry message 542 to the request processor 508 which in response, sends a committed message 544 to the transaction coordinator 510 to find out if the transaction was actually committed. Because the current transaction was not committed due to the server failure 518, the transaction coordinator 510 returns a negative reply 546 to the request processor 508 causing the request processor 508 to issue a rollback command 548 to undo the transient database changes and roll back the transaction that was in progress. The request processor 508 then simulates a client process request message by sending itself a process request message 550 and restarts the process with a start message 552 identical to the initial start message 514. The transaction then continues on as in the failure-free case shown in FIG. 5.

[0043] Referring now to FIG. 7, therein is shown a timeline illustrating how the invention handles a database failure in the case of a multiple database system. The three tiers are represented by a single client machine 600, a single application server 602, and one or more databases DB₁604 through DB_n606. The application server 602 is composed of two parts, a request processor 608 and transaction coordinator 610. The starting point of the transaction is the client 600 sending a process request message 612 to the application server 602. In response, the request processor 610 inside the application server 602 issues multiple start operations 614 to the databases DB₁604 through DB_n606, then manipulates 616 the databases DB₁604 through DB_n606. However, before the transaction can be committed as in FIG. 5, the database DB_n604 experiences a failure 618.

[0044] As a result, the manipulation 616 by the request processor 608 returns an exception 620 that is passed on to the client 600. The transaction coordinator 610 also detects 622 the database failure 618 and begins the recovery process by sending itself the rebuild c-set command 624. In order to rebuild the c-set, the transaction coordinator 610 sends a committed query 626 to the databases DB₁604 through DB_n606. In return, the databases DB₁604 through DB_n606 reply 628 with information to compile a list of committed transactions. To be safe, the transaction coordinator 610 sends forget messages 630 to the databases DB_l604 through DB_n606 to confirm that all the expired transactions in the committed transaction list are forgotten.

[0045] Meanwhile, the client 600 that earlier received the exception 620 issues a retry command 632 to the request processor 608. The request processor 608 does not know if the transaction was committed or not, so it sends a committed message 634 to the transaction coordinator 610 to find out. Because the current transaction was not committed due to the database failure 618, the transaction coordinator 610 returns a negative reply 636 to the request processor 608 causing the request processor 608 to issue a rollback command 638 to undo the transient database changes and roll back the transaction that was in progress. The request processor 608 then simulates a client process request message by sending itself a process request message 640 and restarts the process with a start message 642 identical to the initial start message 614. The transaction then continues on as in the failure-free case shown in FIG. 5.

[0046] While the invention has been described in conjunction with a specific best mode, it is to be understood that many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended to embrace all such alternatives, modifications, and variations which fall within the spirit and scope of the included claims. All matters set forth herein or shown in the accompanying drawings are to be interpreted in an illustrative and non-limiting sense.