US5335343A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Distributed transaction processing using two-phase commit protocol with presumed-commit without log force
Assignee: Hewlett Packard Development Co LP
•
Filing: 1992-07-06
•
Granted: 1994-08-02
•
Expires: 2012-07-06
Abstract
Abstract A two-phase commit protocol for a distributed transaction processing system employs the presumed-commit configuration, with the exception that the new presumed-commit protocol coordinator needs to force-write only a "commit" log record for committed transactions, not the previous force writing of two log records. In order to provide information needed to allow the coordinator to answer inquiries from subordinate processes following a crash or loss of communications, a technique for circumscribing the set of indeterminate transactions is employed. The transactions are numbered in increasing order, identified by a transaction ID (T -- ID). The commit protocol is not allowed to begin unless the transaction ID of the committing transaction is within some preselected range of numbers starting from the highest-numbered stably-recorded transaction ID. That is, if the transaction number is too far removed from the highest TID of a stably stored log record (written to disk storage and able to survive a crash), then log records are written to disk until this condition hold. This may require writing to a disk log record for the committing transaction. Most commit transactions can, however, proceed without waiting for a disk write (forced log), and so performance is improved. A technique is disclosed for circumscribing the set of indeterminate transactions (not shown whether they committed, aborted or never started) so that information is small. It must be "permanently" retained, but the coordinator can store some of it in a cache (volatile memory) to answer inquiries.
Inventors
- 👤 Butler Lampson
- 👤 David B. Lomet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 18:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/466; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; G06F16/2315; G06F16/2322; G06F16/2329; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
154 words
A method of operating a transaction processing system using a presumed-commit two-phase commit protocol, comprising the steps of: assigning transaction identifiers (TIDs) to transactions in increasing order; when a transaction is ready to commit, sending a commit command to a coordinator process, said coordinator process executing at a site having permanent storage and volatile memory; determining whether the TID of said transaction ready to commit is within a selected range of TIDs; if said TID of said transaction ready to commit is within said selected range of TIDs, sending a prepare message to subordinate processes; if said TID of said transaction ready to commit is not within said selected range of TIDs, writing any volatile log records, including a log record for said transaction which is ready to commit, to said permanent storage so as to ensure that said TID is within the selected range before sending said prepare message to said subordinate processes.
Claim 2
Independent Claim
154 words
A method of operating a transaction processing system using a presumed-commit two-phase commit protocol, comprising the steps of: assigning transaction identifiers (TIDs) to transactions in increasing order; when a transaction is ready to commit, sending a commit command to a coordinator process, said coordinator process executing at a site having permanent storage and volatile memory; determining whether the TID of said transaction ready to commit is within a selected range of TIDs; if said TID of said transaction ready to commit is within said selected range of TIDs, sending a prepare message to subordinate processes; if said TID of said transaction ready to commit is not within said selected range of TIDs, writing any volatile log records, including a log record for said transaction which is ready to commit, to said permanent storage so as to ensure that said TID is within the selected range before sending said prepare message to said subordinate processes.
Claim 3
Dependent Claim
40 words
A method according to claim 1 wherein said range begins at the highest TID of an earlier log record which has previously been written to said permanent storage and extends for a selected number of TIDs beyond said highest TID.
Claim 4
Dependent Claim
48 words
A method according to claim 1 including the step of maintaining a list of all TIDs the outcome of which is indeterminate, said list having TID numbers of magnitude less than the highest number of said range, and said list excluding all TIDs which have committed or aborted.
Claim 5
Dependent Claim
26 words
A method according to claim 1 including the steps of executing said coordinator and each of said subordinates at separate sites interconnected by a communications network.
Claim 6
Dependent Claim
51 words
A method according to claim 1 including the step of maintaining a stable record of the oldest TID (O -- TID), which is the TID of the transaction that has the lowest TID number that has not been committed or aborted but for which all lower TIDs have committed or aborted.
Claim 7
Dependent Claim
41 words
A method according to claim 1 including the step of maintaining in said permanent storage a record of TIDs active near the time of a system crash, in which is recorded which ones may have been active and which ones committed.
Claim 8
Dependent Claim
161 words
A transaction processing system using a presumed-commit two-phase commit protocol, said system including a commit coordinator and a plurality of subordinates, comprising: means for assigning transaction identifiers (TIDs) to transactions executing on said system, in increasing order; means for sending a commit command to said coordinator when a transaction executing on said system is ready to commit, said coordinator executing at a site having permanent storage and volatile memory; means for determining whether the TID of said transaction ready to commit is within a selected range of TIDs; means for sending a prepare message to said subordinate if said TID of said transaction ready to commit is within said selected range of TIDs; means for writing any volatile log records to said permanent storage before sending said prepare message to said subordinates, if said TID of said transaction ready to commit is not within said selected range of TIDs, so as to ensure that said TID is within the selected range.
Claim 9
Dependent Claim
161 words
A transaction processing system using a presumed-commit two-phase commit protocol, said system including a commit coordinator and a plurality of subordinates, comprising: means for assigning transaction identifiers (TIDs) to transactions executing on said system, in increasing order; means for sending a commit command to said coordinator when a transaction executing on said system is ready to commit, said coordinator executing at a site having permanent storage and volatile memory; means for determining whether the TID of said transaction ready to commit is within a selected range of TIDs; means for sending a prepare message to said subordinate if said TID of said transaction ready to commit is within said selected range of TIDs; means for writing any volatile log records to said permanent storage before sending said prepare message to said subordinates, if said TID of said transaction ready to commit is not within said selected range of TIDs, so as to ensure that said TID is within the selected range.
Claim 10
Dependent Claim
40 words
A system according to claim 7 wherein said range begins at the highest TID of an earlier commit record which has previously been written to said permanent storage and extends for a selected number of TIDs beyond said highest TID.
Claim 11
Dependent Claim
47 words
A system according to claim 7 including means for maintaining a list of all TIDs the outcome of which is indeterminate, said list having TID numbers of magnitude less than the highest number of said range, and said list excluding all TIDs which have committed or aborted.
Claim 12
Dependent Claim
24 words
A system according to claim 7 wherein said coordinator and each of said subordinates are executed at separate sites interconnected by a communications network.
Claim 13
Dependent Claim
50 words
A system according to claim 7 including means for maintaining a stable record of the oldest TID (O -- TID), which is the TID of the transaction that has the lowest TID number that has not been committed or aborted but for which all lower TIDs have committed or aborted.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-01 | 1998-01-31 | 1998-08-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-01 | 2002-01-31 | 2002-08-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-01 | 2006-01-31 | 2006-08-02 | $7700.00 | Window Closed / Lapsed |