US5940839A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fault-tolerant system and method of managing transaction failures in hierarchies
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1997-04-04
•
Granted: 1999-08-17
•
Expires: 2017-04-04
Abstract
Abstract A fault-tolerant technique for managing cross-hierarchy failure of a process of transactions is disclosed. The process has blocks of transactions and one or more of the transactions may be subtransaction of others. The technique includes enabling a block having one or more transactions in the process to notice, e.g., the failure in a transaction not in the process, wherein the noticed failure will cause a failure of a transaction (FFT) in the process. The technique also includes, upon the failure of the transaction FFT in the process, determining an in-progress closest recoverable ancestor (ICRA) in a block in the process. The ICRA is the nearest transaction to the failed transaction FFT, in the block on an ancestor tree of the FFT, that is in-block-recoverable and in-progress. The technique further includes recovering from the first process failed transaction by undoing from the ICRA to that failed transaction. The undoing step includes aborting or compensating one or more transactions, or both. In the case that the closest recoverable ancestor (CRA), i.e., the nearest transaction to the FFT is not in-progress, the closest in-progress ancestor (CIP) of the CRA and the closest recoverable in-progress ancestor (ERA) of the CIP are identified. The CIP is the nearest transaction to the CRA, on the ancestor tree of the FFT, that is neither committed nor aborted as viewed from outside the first process. The ERA is the nearest in-block recoverable transaction to the CIP on the ancestor tree of the FFT and in progress in a block containing the CIP.
Inventors
- 👤 Qiming Chen
- 👤 Umeshwar Dayal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 09:32
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
138 words
A method for managing a plurality of transactions of a set of processes including one or more processes in a computer database system, each process including a nested plurality of transactions having more than two levels of hierarchies, comprising: (a) upon the failure of a transaction (FFT) in one of the processes, identifying an ancestor tree including nested blocks of transactions in the process and on the ancestor tree an in-progress closest recoverable ancestor (ICRA) without regard to the level of hierarchies of the ICRA in the process in which the failed transaction occurs, the ICRA being the in-block recoverable transaction nearest to the FFT and in progress in a ICRA-containing block; and (b) undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 2
Independent Claim
138 words
A method for managing a plurality of transactions of a set of processes including one or more processes in a computer database system, each process including a nested plurality of transactions having more than two levels of hierarchies, comprising: (a) upon the failure of a transaction (FFT) in one of the processes, identifying an ancestor tree including nested blocks of transactions in the process and on the ancestor tree an in-progress closest recoverable ancestor (ICRA) without regard to the level of hierarchies of the ICRA in the process in which the failed transaction occurs, the ICRA being the in-block recoverable transaction nearest to the FFT and in progress in a ICRA-containing block; and (b) undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 3
Dependent Claim
42 words
The method according to claim 1 further comprising noticing the success or failure in a failure-causing transaction not in the process, wherein the noticed success or failure of the failure-causing transaction will cause a failure of the transaction (FFT) in the process.
Claim 4
Dependent Claim
45 words
The method according to claim 1 further comprising identifying the ICRA in the ancestor tree of the FFT wherein the ICRA is one of the group of retriable, non-critical to the block, and having in the block an alternative transaction path not including the FFT.
Claim 5
Dependent Claim
28 words
The method according to claim 1 wherein the ICRA is either non-critical to the block or has in the block an alternative transaction path not including the FFT.
Claim 6
Dependent Claim
37 words
The method according to claim 1 further comprising processing the process through an alternative transaction path proceeding from the ICRA, the alternative transaction path including transactions that are different from ancestors of the FFT below the ICRA.
Claim 7
Dependent Claim
64 words
The method according to claim 1 further comprising: eliminating the effect of the FFT and of any transactions that are ancestors of the FFT below the ICRA in the ancestor tree and further processing the ICRA-containing block through an alternative path of transactions proceeding downward from the ICRA, the alternative path including transactions that are different from ancestors of the FFT below the ICRA.
Claim 8
Dependent Claim
34 words
The method according to claim 1 further comprising: adding a dummy transaction note to the ancestor tree as a parent to a transaction in a nonhierarchical transaction structure to render the transaction structure hierarchical.
Claim 9
Dependent Claim
41 words
The method according to claim 7 further comprising arranging concurrent transactions into blocks of transactions, some of the blocks being subblocks of others, by adding a dummy transaction note as a parent to concurrent transactions to render the transaction structure hierarchical.
Claim 10
Dependent Claim
51 words
The method according to claim 7 further comprising arranging sequential transactions into blocks of transactions, some of the blocks being subblocks of others, by adding a dummy transaction note as a parent to each of the sequential transactions that are not terminal to link all sequential transactions to other transactions hierarchically.
Claim 11
Dependent Claim
68 words
The method according to claim 2 further comprising identifying on the ancestor tree of FFT a closest recoverable ancestor (CRA) which is the in-block recoverable transaction nearest to the FFT in a CRA-containing block, and identifying a closest in-progress ancestor (CIP) of the CRA, the CIP being the nearest transaction to the CRA on the ancestor tree of FFT wherein said nearest transaction is neither committed nor aborted.
Claim 12
Dependent Claim
62 words
The method according to claim 10 further comprising: identifying a closest recoverable ancestor (ERA) of the CIP as the ICRA, the ERA being the nearest transaction to the CIP, on the ancestor tree of the FFT, that is non-critical to an in-progress block including the CIP or has in said in-progress block an alternative transaction path that does not include the CIP.
Claim 13
Dependent Claim
17 words
The method according to claim 10 further comprising identifying the CRA wherein the CRA is not in-progress.
Claim 14
Dependent Claim
16 words
The method according to claim 10 further comprising identifying the CRA wherein the CRA is in-progress.
Claim 15
Dependent Claim
19 words
The method according to claim 1 further comprising arranging the transactions in a block into a hierarchy of transactions.
Claim 16
Dependent Claim
79 words
The method according to claim 14 further comprising arranging sequential transactions into blocks of transactions, some of the blocks being subblocks of others, by adding a different dummy transaction note to as a parent to each of the sequential transactions that are nonterminal to link the sequential transaction to another transaction hierarchically, and further comprising adding a dummy transaction note as a parent to all of the concurrent transactions to link the concurrent transactions hierarchically to the dummy transaction.
Claim 17
Independent Claim
218 words
A method for managing a first process including transactions wherein one or more of the transactions may be subtransaction of others, comprising: (a) providing a hierarchy of blocks of transactions of the first process in which all nonterminal transactions are linked hierarchically, some of the blocks being subblocks of others; (b) noticing failure in a transaction in a second process whose transactions are not transactions of the first process, wherein a failure of the second-process transaction will cause a failure of a transaction (FFT) in the first process; (c) identifying an ancestor tree of the FFT and on the ancestor tree a closest recoverable ancestor (CRA) in a block containing the CRA, the CRA being the nearest in-block recoverable transaction to the FFT; (d) identifying a closest in-progress ancestor (CIP) of the CRA, the CIP being the nearest transaction to the CRA, on the ancestor tree of the FFT, that is neither committed nor aborted. (e) identifying a closest recoverable in-progress ancestor (ERA) of the CIP, the ERA being the nearest transaction to the CIP, on the ancestor tree of the FFT, that is in-block recoverable in a block containing the CIP; and (f) undoing all transactions from the ERA downward by at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 18
Independent Claim
218 words
A method for managing a first process including transactions wherein one or more of the transactions may be subtransaction of others, comprising: (a) providing a hierarchy of blocks of transactions of the first process in which all nonterminal transactions are linked hierarchically, some of the blocks being subblocks of others; (b) noticing failure in a transaction in a second process whose transactions are not transactions of the first process, wherein a failure of the second-process transaction will cause a failure of a transaction (FFT) in the first process; (c) identifying an ancestor tree of the FFT and on the ancestor tree a closest recoverable ancestor (CRA) in a block containing the CRA, the CRA being the nearest in-block recoverable transaction to the FFT; (d) identifying a closest in-progress ancestor (CIP) of the CRA, the CIP being the nearest transaction to the CRA, on the ancestor tree of the FFT, that is neither committed nor aborted. (e) identifying a closest recoverable in-progress ancestor (ERA) of the CIP, the ERA being the nearest transaction to the CIP, on the ancestor tree of the FFT, that is in-block recoverable in a block containing the CIP; and (f) undoing all transactions from the ERA downward by at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 19
Dependent Claim
131 words
A transaction management system for managing a process having a plurality of transactions in nested form with multiple levels of hierarchies, comprising: (a) computer means for identifying an ancestor tree in the process with multiple levels of hierarchies of a failed transaction (FFT) in the process and determining an in-progress closest recoverable ancestor (ICRA) in a nested block of transactions including the ICRA in the ancestor tree without regard to the level of hierarchies of the ICRA in the process in which the failed transaction occours, the ICRA being the nearest transaction to the FFT, on the ancestor tree of the FFT, that is in-block recoverable and in-progress; and (b) computer means for undoing from the ICRA downward, including one of the group of aborting and compensating one or more transactions.
Claim 20
Dependent Claim
131 words
A transaction management system for managing a process having a plurality of transactions in nested form with multiple levels of hierarchies, comprising: (a) computer means for identifying an ancestor tree in the process with multiple levels of hierarchies of a failed transaction (FFT) in the process and determining an in-progress closest recoverable ancestor (ICRA) in a nested block of transactions including the ICRA in the ancestor tree without regard to the level of hierarchies of the ICRA in the process in which the failed transaction occours, the ICRA being the nearest transaction to the FFT, on the ancestor tree of the FFT, that is in-block recoverable and in-progress; and (b) computer means for undoing from the ICRA downward, including one of the group of aborting and compensating one or more transactions.
Claim 21
Dependent Claim
46 words
The system according to claim 17 further comprising means for allowing a transaction in the process to notice success or failure in a failure-causing transaction not in said process, wherein the success or failure of the failure-causing transaction will cause a failure of the transaction FFT.
Claim 22
Dependent Claim
72 words
The system according to claim 18 further comprising computer means for identifying a closest recoverable ancestor (CRA) of FFT which is the in-block recoverable transaction nearest to the FFT in a CRA-containing block, and identifying a closest in-progress ancestor (CIP) of the CRA, the CIP being the nearest transaction to the CRA, on the ancestor tree of the FFT, that is neither committed nor aborted as viewed from outside the first process.
Claim 23
Dependent Claim
45 words
The system according to claim 19 further comprising computer means for identifying a closest recoverable in-progress ancestor (ERA) of the CIP, the ERA being the nearest in-block recoverable transaction to the CIP on the ancestor tree of the FFT in a block containing the CIP.
Claim 24
Dependent Claim
28 words
The system according to claim 18 wherein the system further comprises computer means for arranging the transactions in a block in the process into a hierarchy of transactions.
Claim 25
Dependent Claim
214 words
A program storage medium readably by a computer, tangibly embodying a program of instruction including code means executable by the computer to manage transactions in a process in a database system wherein the process has a plurality of transactions in nested form having more than two levels of hierarchies, the program storage medium comprising: a memory device having code means, said code means including, (a) code means for noticing the success or failure in a failure-causing transaction not in the process, wherein the noticed success or failure of the failure-causing transaction will cause a failure of a transaction (FFT) in the process; (b) code means for identifying an ancestor tree of the failed transaction FFT in the process, the ancestor tree including nested blocks of transaction in the process, the code means further for identifying on the ancestor tree an in-progress recoverable ancestor (ICRA) closest to the failed transaction FFT without regard to the level of hierarchy of the ICRA in the process the failed transaction occurs, the ICRA being the nearest in-block recoverable transaction to the FFT and in progress in a ICRA-containing block; and (c) code means for undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 26
Dependent Claim
214 words
A program storage medium readably by a computer, tangibly embodying a program of instruction including code means executable by the computer to manage transactions in a process in a database system wherein the process has a plurality of transactions in nested form having more than two levels of hierarchies, the program storage medium comprising: a memory device having code means, said code means including, (a) code means for noticing the success or failure in a failure-causing transaction not in the process, wherein the noticed success or failure of the failure-causing transaction will cause a failure of a transaction (FFT) in the process; (b) code means for identifying an ancestor tree of the failed transaction FFT in the process, the ancestor tree including nested blocks of transaction in the process, the code means further for identifying on the ancestor tree an in-progress recoverable ancestor (ICRA) closest to the failed transaction FFT without regard to the level of hierarchy of the ICRA in the process the failed transaction occurs, the ICRA being the nearest in-block recoverable transaction to the FFT and in progress in a ICRA-containing block; and (c) code means for undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 27
Independent Claim
130 words
A method for managing a plurality of transactions of a process in a computer database system, the process including a nested set of transactions, comprising: (a) upon the failure of a transaction (FFT) in the process, identifying an ancestor tree including nested blocks of transactions in the process and on the ancestor tree an in-progress closest recoverable ancestor (ICRA), the ICRA being the in-block recoverable transaction nearest to the FFT and in progress in a ICRA-containing block, wherein the ICRA is one of the group of retriable, non-critical to the block, and having in the block an alternative transaction path not including the FFT; and (b) undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 28
Independent Claim
130 words
A method for managing a plurality of transactions of a process in a computer database system, the process including a nested set of transactions, comprising: (a) upon the failure of a transaction (FFT) in the process, identifying an ancestor tree including nested blocks of transactions in the process and on the ancestor tree an in-progress closest recoverable ancestor (ICRA), the ICRA being the in-block recoverable transaction nearest to the FFT and in progress in a ICRA-containing block, wherein the ICRA is one of the group of retriable, non-critical to the block, and having in the block an alternative transaction path not including the FFT; and (b) undoing all transactions from the ICRA downward, including at least one of the group of aborting and compensating from the ICRA to the FFT.
Claim 29
Dependent Claim
26 words
The method according to claim 1 wherein the step of identifying the ICRA comprises bypassing any FFT's closest recoverable ancestor that is no longer in progress.
Claim 30
Dependent Claim
59 words
The method according to claim 1 wherein the undoing will undo all the transaction from the ICRA downward in the ancestor tree of the FFT regardless of whether the FFT fails due to a failed transaction in the ancestor tree of the FFT or a failed transaction in an ancestor tree of another process in the set of processes.
Claim 31
Dependent Claim
20 words
The system according to claim 17 wherein the ancestor tree of the process includes more than two levels of hierarchies.
References Cited (Backward Citations)
US4819159A
Cited
US5247664A
Cited
US5504899A
Cited
US5241675A
Cited
US5481699A
Cited
US5335343A
Cited
US5404508A
Cited
US5764897A
Cited
US5465328A
Cited
US5758356A
Cited
US5682527A
Cited
US5729733A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-16 | 2003-02-15 | 2003-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-16 | 2007-02-15 | 2007-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-16 | 2011-02-15 | 2011-08-17 | $7700.00 | Window Closed / Lapsed |