Pre-Grant Publication Number: 20070198518
Please help the USPTO examine the application by evaluating the relevance of the publicly submitted prior art to the patent application.
Peer-to-Patent forwards the Top 10 most relevant prior art submissions and their annotations to the United States Patent and Trademark Office.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Review this prior art and click on the thumbs up (or down) to indicate whether this submission should be forwarded to the USPTO.
If you login then you can add an annotation by typing in the box at the bottom of the screen to comment on the relevance of the prior art to the claims of the patent application.
Prior Art Detail
Summary / Description
| Summary / Description | Sagas are groups of transactions such that if any one of them fails, the entire group fails. Kudos to Jon Walpole for bringing this to my attention! |
Basic Information
| Type of Prior Art | Print Publication |
| Publication Title * | SAGAS |
| Author | Hector Garcia-Molina and Kenneth Salem |
| ISBN | ISSN:0163-5808 |
| Page Range | 249-259 |
| Medium | Journal article |
| Publication Date * | December 1, 1987 |
| URL | http://portal.acm.org/citation.... |
Notes / To Do
| Notes | There are also in-memory databases, which do not have disk involved. Even databases that are designed to use disk storage can be configured to have their tables placed in simulated disk volumes in memory. (This is well known, but if someone has a refere |
Excerpt
Excerpt Long lived transactions (LLTs) hold on to database resources for relatively long periods of time, significantly delaying the termination of shorter and more common transactions. To alleviate these problems we propose the notion of a saga. A LLT is a saga if it can be written as a sequence of transactions that can be interleaved with other transactions. The database management system guarantees that either all the transactions in a saga are successfully completed or compensating transactions are run to amend a partial execution. Both the concept of saga and its implementation are relatively simple, but they have the potential to improve performance significantly. We analyze the various implementation issues related to sagas, including how they can be run on an existing system that does not directly support them. We also discuss techniques for database and LLT design that make it feasible to break up LLTs into sagas. |
Relevance
Claims
1
A system, comprising:
one or more processors; and
a memory coupled to the one or more processors, wherein the memory stores program instructions executable by the one or more processors to implement a memory manager configured to:
coordinate memory access requests specifying data locations within the memory, wherein said coordinating comprises:
recording, within a collaborator record of a first shared data object in the memory, identifications of a set of two or more transactions that have each requested synchronization on the first shared data object;
in response to a commit request from a given transaction of the set, determining whether to commit or abort the given transaction based at least in part on transactional states of one or more other transactions of the set, wherein said determining comprises examining the collaborator record to identify the one or more other transactions of the set; and
committing or aborting the given transaction according to said determining.
Relevance
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Claim Chart
All
2
The system as recited in Claim 1, wherein the coordination further comprises:
recording, within a respective shared data object record for each transaction of the set of transactions, an identification of one or more additional shared data objects on which the corresponding transaction has requested synchronization;
in response to the commit request, examining the shared data object record of the given transaction to identify one or more additional shared data objects on which the given transaction has requested synchronization;
wherein said determining whether to commit or abort the given transaction is based at least in part on a transactional state of an additional transaction identified in a collaborator record of an additional shared data object of the one or more additional shared data objects.
Relevance
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
Claim Chart
All
3
The system as recited in Claim 1, wherein the coordinating further comprises:
in response to determining to commit the given transaction, determining to commit each other transaction of the set and committing each other transaction of the set; and
in response to determining to abort the given transaction, determining to abort each other transaction of the set and aborting each other transaction of the set.
Relevance
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
Claim Chart
All
5
The system as recited in Claim 1, wherein said determining whether to commit or abort the given transaction comprises:
determining to commit the given transaction if each of the other transactions in the set is in a committing state indicating that the other transaction has issued a commit request and has not yet been committed, and if none of the other transactions in the set is in an aborted state.
Relevance
The latter clause (none of the other transactions in the set is in an aborted state) is anticipated by this reference (where "set" is "saga" in the reference). The earlier clauses are anticipated given that the saga itself is analogous to a transaction -- the saga is committed only if all transactions commit.
The latter clause (none of the other transactions in the set is in an aborted state) is anticipated by this reference (where "set" is "saga" in the reference). The earlier clauses are anticipated given that the saga itself is analogous to a transaction -- the saga is committed only if all transactions commit.
Claim Chart
Some
6
The system as recited in Claim 1, wherein said determining whether to commit or abort the given transaction comprises:
determining to abort the given transaction if any one of the other transactions in the set is in an aborted state.
Relevance
See commentary for claim 5.
See commentary for claim 5.
Claim Chart
All
7
The system as recited in Claim 1, wherein said determining whether to commit or abort the given transaction comprises:
if a particular other transaction of the set is in an active state indicating that the particular other transaction has not yet issued a commit request, waiting until the particular other transaction changes transactional state;
if the particular other transaction changes state to a committing state indicating that the particular other transaction has issued a request to commit, determining to commit the given transaction if each other transaction of the set is also in a committing state; and
if the particular other transaction changes state to an aborted state, determining to abort the given transaction.
Relevance
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
Claim Chart
All
9
The system as recited in Claim 1, wherein said recording is responsive to respective registration requests for the first shared data object from each transaction of the set, wherein said coordinating further comprises:
in response to a registration request for the first shared data object from an additional transaction,
if the registration request is received before a commit request from any transaction of the set, recording an identification of the additional transaction in the collaborator list of the first data object; and
if the registration request is received after the commit request, waiting until the given transaction is committed or aborted before recording an identification of the additional transaction in the collaborator record.
Relevance
Parallel sagas can add additional transactions to the group as they are encountered, but sagas cannot be partitioned. Such partitioning would be required to anticipate the final clause of this claim.
Parallel sagas can add additional transactions to the group as they are encountered, but sagas cannot be partitioned. Such partitioning would be required to anticipate the final clause of this claim.
Claim Chart
Some
11
A computer-implemented method of coordinating memory access requests specifying data locations within a memory, comprising:
receiving respective registration requests from a set of two or more transactions, wherein each registration request indicates that a corresponding transaction of the set has requested synchronization on a first shared data object within the memory;
recording, within a collaborator record of the first shared data object in the memory, identifications of the two or more transactions of the set;
in response to a commit request from a given transaction of the set, determining whether to commit or abort the given transaction based at least in part on transactional states of one or more other transactions of the set, wherein said determining comprises examining the collaborator record to identify the one or more other transactions of the set; and
committing or aborting the given transaction according to said determining.
Relevance
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Claim Chart
All
12
The method as recited in Claim 11, further comprising:
recording, within a respective shared data object record for each transaction of the set of transactions, an identification of one or more additional shared data objects on which the corresponding transaction has requested synchronization;
in response to the commit request, examining the shared data object record of the given transaction to identify one or more additional shared data objects on which the given transaction has requested synchronization;
wherein said determining whether to commit or abort the given transaction is based at least in part on a transactional state of an additional transaction identified in a collaborator record of an additional shared data object of the one or more additional shared data objects.
Relevance
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
Claim Chart
All
13
The method as recited in Claim 11, further comprising:
in response to determining to commit the given transaction, determining to commit each other transaction of the set and committing each other transaction of the set; and
in response to determining to abort the given transaction, determining to abort each other transaction of the set and aborting each other transaction of the set.
Relevance
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
Claim Chart
All
14
The method as recited in Claim 11, wherein said determining whether to commit or abort the given transaction comprises:
determining to commit the given transaction if (a) any one of the other transactions in the set is in a committed state, or (b) each of the other transactions in the set is in a committing state indicating that the other transaction has issued a commit request and has not yet been committed, and if none of the other transactions in the set is in an aborted state; and
determining to abort the given transaction if any one of the other transactions in the set is in an aborted state.
Relevance
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
Claim Chart
All
15
The method as recited in Claim 11, wherein said determining whether to commit or abort the given transaction comprises:
if a particular other transaction of the set is in an active state indicating that the particular other transaction has not yet issued a commit request, waiting until the particular other transaction changes transactional state;
if the particular other transaction changes state to a committing state indicating that the particular other transaction has issued a request to commit, determining to commit the given transaction if each other transaction of the set is also in a committing state; and
if the particular other transaction changes state to an aborted state, determining to abort the given transaction.
Relevance
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
Claim Chart
All
16
A computer readable medium comprising program instructions, wherein the instructions are computer-executable to implement a memory manager configured to coordinate memory access requests specifying data locations within the memory, wherein said coordinating comprises:
receiving respective registration requests from a set of two or more transactions, wherein each registration request indicates that a corresponding transaction of the set has requested synchronization on a first shared data object within the memory;
recording, within a collaborator record of the first shared data object in the memory, identifications of the two or more transactions of the set;
in response to a commit request from a given transaction of the set, determining whether to commit or abort the given transaction based at least in part on transactional states of one or more other transactions of the set, wherein said determining comprises examining the collaborator record to identify the one or more other transactions of the set; and
committing or aborting the given transaction according to said determining.
Relevance
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Configure a database so that its tables and logs are in memory using operating system features that simulate disks using main memory. The database is then a memory manager. The saga identifier (p 252 col 1 1st full para) identifies the collaborator record. Page 256 describes concurrent execution of transactions within a saga, including aborting ("backward recovery") other transactions in response to a given transaction failing (col 2 1st full para). Transactions are allowed to commit otherwise.
Claim Chart
All
17
The computer readable medium as recited in Claim 16, wherein said coordinating further comprises:
recording, within a respective shared data object record for each transaction of the set of transactions, an identification of one or more additional shared data objects on which the corresponding transaction has requested synchronization;
in response to the commit request, examining the shared data object record of the given transaction to identify one or more additional shared data objects on which the given transaction has requested synchronization;
wherein said determining whether to commit or abort the given transaction is based at least in part on a transactional state of an additional transaction identified in a collaborator record of an additional shared data object of the one or more additional shared data objects.
Relevance
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
This reference covers database-management systems, which of necessity identify shared objects among transactions. In addition, the saga identifier described on page 252 col 1 1st full para constitutes a shared data object among the constituent transactions.
Claim Chart
All
18
The computer readable medium as recited in Claim 16, wherein said coordinating further comprises:
in response to determining to commit the given transaction, determining to commit each other transaction of the set and committing each other transaction of the set; and
in response to determining to abort the given transaction, determining to abort each other transaction of the set and aborting each other transaction of the set.
Relevance
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
Claim Chart
All
19
The computer readable medium as recited in Claim 16, wherein said determining whether to commit or abort the given transaction comprises:
determining to commit the given transaction if (a) any one of the other transactions in the set is in a committed state, or (b) each of the other transactions in the set is in a committing state indicating that the other transaction has issued a commit request and has not yet been committed, and if none of the other transactions in the set is in an aborted state; and
determining to abort the given transaction if any one of the other transactions in the set is in an aborted state.
Relevance
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
This reference "determines to commit" by refraining from executing the supplied compensation code. In the abort case, other transactions might be aborted directly (in the parallel case on page 256) or by executing the supplied compensation code.
Claim Chart
All
20
The computer readable medium as recited in Claim 16, wherein said determining whether to commit or abort the given transaction comprises:
if a particular other transaction of the set is in an active state indicating that the particular other transaction has not yet issued a commit request, waiting until the particular other transaction changes transactional state;
if the particular other transaction changes state to a committing state indicating that the particular other transaction has issued a request to commit, determining to commit the given transaction if each other transaction of the set is also in a committing state; and
if the particular other transaction changes state to an aborted state, determining to abort the given transaction.
Relevance
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
This is anticipated given that the reference's enclosing saga is analogous to a transaction. The saga cannot commit before all the enclosed transactions at least reach a committing state. The saga will abort if any of the enclosed transactions are aborted.
Claim Chart
All
