Intelligent merging of transactions based on a variety of criteria
An apparatus and methods are disclosed for intelligently determining when to merge transactions to backup storage. In particular, in accordance with the illustrative embodiment, queued transactions may be merged based on a variety of criteria, including, but not limited to, one or more of the following: the number of queued transactions; the rate of growth of the number of queued transactions; the calendrical time; estimates of the time required to execute the individual transactions; a measure of importance of the individual transactions; the transaction types of the individual transactions; a measure of importance of one or more data updated by the individual transactions; a measure of availability of one or more resources; a current estimate of the time penalty associated with shadowing a page of memory; and the probability of rollback for the individual transactions, and for the merged transaction.
1. An apparatus comprising:
a queue configured to store a plurality of atomic transactions, wherein said plurality of atomic transactions comprises a first transaction and a second transaction, and wherein said first transaction is before said second transaction in said queue;
a memory; and
a processor coupled to the memory, the processor configured to perform the steps of:
(a) determining whether to merge said first transaction and said second transaction based on whether the number of transactions in said queue exceeds a first predetermined threshold and whether a rate of growth of the number of transactions in a transaction queue exceeds a second predetermined threshold; and
(b) when the determination is affirmative,
(i) merging the first and second transactions,
(ii) processing the merged transaction, wherein the processing comprises transmitting a signal that is based on said merged transaction, and
(iii) storing in the memory a system state produced by the processing, and otherwise,
(i) processing said first transaction, wherein the processing comprises transmitting a signal that is based on said first transaction,
(ii) processing said second transaction, wherein the processing comprises transmitting a signal that is based on said second transaction, and
(iii) storing in the memory a system state produced by the processing of the first transaction and the processing of the second transaction.
2. The apparatus of claim 1 wherein the time required to process said merged transaction is less than the sum of the times required to process said first transaction and said second transaction.
3. The apparatus of claim 1 further comprising a first memory, wherein a first non-empty set of pages of said first memory is updated by said first transaction, and wherein a second non-empty set of pages of said first memory is updated by said second transaction.
4. The apparatus of claim 3 further comprising a second memory, wherein the processing of said first transaction comprises copying to said second memory the updated contents of said first set of pages, and wherein the processing of said second transaction comprises copying to said second memory the updated contents of said second set of pages, and wherein the processing of said merged transaction comprises copying to said second memory the updated contents of the union of said first set of pages and said second set of pages.
5. The apparatus of claim 3 wherein when:
(i) the first transaction stores a first value in a location of said first memory, and
(ii) the second transaction is after the first transaction and stores a second value in said location, and
(iii) the second transaction does not read the contents of said location prior to storing said second value in said location, and
(iv) the first and second transactions are merged, the merged transaction eschews storing said first value in said location.
6. The apparatus of claim 1 wherein the determination whether to merge the first and second transactions is also based on an estimate of the time required to execute the first transaction.
7. The apparatus of claim 6 wherein the determination whether to merge the first and second transactions is also based on an estimate of the time required to execute the second transaction.
8. An apparatus comprising:
a queue configured to store a plurality of atomic transactions, wherein said plurality of transactions comprises a first transaction and a second transaction, and wherein said first transaction is before said second transaction in said queue; and
a memory;
a processor coupled to the memory, the processor configured to perform the steps of:
(a) determining whether to merge said first transaction and said second transaction based on whether the calendrical time is within a predetermined interval of time and whether a rate of growth of the number of transactions in a transaction queue exceeds a predetermined threshold rate of growth; and
(b) when the determination is affirmative,
(i) merging the first and second transactions,
(ii) processing the merged transaction, wherein the processing comprises transmitting a signal that is based on said merged transaction, and
(iii) storing in the memory a system state produced by the processing, and otherwise,
(i) processing said first transaction, wherein the processing comprises transmitting a signal that is based on said first transaction,
(ii) processing said second transaction, wherein the processing comprises transmitting a signal that is based on said second transaction, and
(iii) storing in the memory a system state produced by the processing of the first transaction and the processing of the second transaction.
9. The apparatus of claim 8 wherein the time required to process said merged transaction is less than the sum of the times required to process said first transaction and said second transaction.
10. The apparatus of claim 8 further comprising a first memory, wherein a first non-empty set of pages of said first memory is updated by said first transaction, and wherein a second non-empty set of pages of said first memory is updated by said second transaction.
11. The apparatus of claim 10 further comprising a second memory, wherein the processing of said first transaction comprises copying to said second memory the updated contents of said first set of pages, and wherein the processing of said second transaction comprises copying to said second memory the updated contents of said second set of pages, and wherein the processing of said merged transaction comprises copying to said second memory the updated contents of the union of said first set of pages and said second set of pages.
12. The apparatus of claim 8 wherein the determination whether to merge the first and second transactions is also based on a measure of importance of said first transaction.
13. The apparatus of claim 8 wherein said first transaction is of a first transaction type, and wherein said second transaction is of a second transaction type, and wherein the determination whether to merge the first and second transactions is also based on one or both of said first transaction type and said second transaction type.
14. The apparatus of claim 8 wherein the determination whether to merge the first and second transactions is also based on a measure of availability of a resource of said apparatus.
15. An apparatus comprising:
a queue for storing configured to store a plurality of atomic transactions;
a memory; and
a processor coupled to the memory, the processor configured to perform the steps of:
(a) determining whether to merge a first of said plurality of atomic transactions and a second of said plurality of atomic transactions based on a measure of whether response time for previously-executed transactions exceeds a first predetermined threshold and whether a rate of growth of the number of transactions in a transaction queue exceeds a second predetermined threshold; and
(b) when the determination is affirmative: merging the first and second transactions; executing the merged transaction; and storing in the memory a system state produced by the merged transaction, and
otherwise, executing the first and second transactions separately; and storing in the memory a system state produced by the execution of the first transaction and the execution of the second transaction.
16. The apparatus of claim 15 further comprising:
a first memory whose contents is updated by one or more of said plurality of transactions; and
a second memory for storing a shadowed copy of the contents of said first memory.
17. The apparatus of claim 16 wherein the determination whether to merge the first and second transactions is also based on a current estimate of the time penalty associated with shadowing a page of said first memory.
18. The apparatus of claim 15 wherein the determination whether to merge the first and second transactions is also based on an estimate of the probability of rollback for at least one of: (i) said first transaction, (ii) said second transaction, and (iii) the merged transaction.
19. The apparatus of claim 15 wherein the determination whether to merge the first and second transactions is also based on a measure of importance of a datum written by said first transaction.
20. The apparatus of claim 15 wherein the determination whether to merge the first and second transactions is also based on the rate of growth of the number of transactions in said queue.