PROCESSING SERIALIZED TRANSACTIONS IN PARALLEL WHILE PRESERVING TRANSACTION INTEGRITY

• US 20100287554A1
• Filed: 05/11/2009
• Published: 11/11/2010
• Est. Priority Date: 05/11/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Amundsen, Lance C., Hall, Harold H.
• Granted Patent: US 10,002,019 B2
• Time in Patent Office: Days
• US Class Current: 718/101
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A method, system, and apparatus are disclosed for processing serialized transactions in parallel while preserving transaction integrity. The method includes receiving a transaction comprising at least two keys and accessing a serialization-independent key (“SI-Key”) and a serialization-dependent key (“SD-Key”) from the transaction. A value for the SI-Key identifies the transaction as independent of transactions having a different value for the SI-Key. Furthermore, a value for the SD-Key governs a transaction execution order for each transaction having a SI-Key value that matches the SI-Key value associated with the SD-Key value. The method also includes assigning the transaction to an execution group based on a value for the SI-Key. The method also includes scheduling the one or more transactions in the execution group in an order defined by the SD-Key. The execution group may execute in parallel with one or more additional execution groups.

Claims

1. A method for processing serialized transactions in parallel while preserving:

transaction integrity, the method comprising;

receiving a transaction from a set of serialized transactions, the transaction comprising at least two keys;

accessing a serialization-independent key (“

SI-Key”

) and a serialization-dependent key (“

SD-Key”

) from the transaction;

assigning the transaction to an execution group based on the value for the SI-Key, the execution group configured to hold one or more transactions; and

scheduling the one or more transactions in the execution group for execution in an order defined by each SD-Key value, the execution group configured to execute in parallel with one or more additional execution groups.

2. The method of claim 1, further comprising creating a new execution group in response to identifying a new value for the SI-Key, the new value comprising a value unassociated with a value for a SI-Key of existing execution groups, the new execution group associated with the new value for the SI-Key.

3. The method of claim 1, wherein assigning the transaction further comprises assigning the transaction to an execution group based on a compound attribute, the compound attribute based on a value for the SI-Key and a value for an additional data field.

4. The method of claim 1, further comprising executing the one or more transactions in the execution group.

5. The method of claim 1, wherein the execution group comprises a hash map.

6. The method of claim 1, further comprising sorting the one or more transactions in each execution group based on each SD-Key value.

7. The method of claim 1, wherein the SD-Key comprises a timestamp.

8. The method of claim 1, wherein the SI-Key comprises a unique entity identifier.

9. An apparatus for processing serialized transactions in parallel while preserving transaction integrity, the apparatus comprising:

a receiving module configured to receive a plurality of serialized transactions, each transaction comprising at least two keys;

an accessing module configured to access a serialization-independent key (“

SI-Key”

) and a serialization-dependent key (“

SD-Key”

) from the plurality of transactions;

an assignment module configured to assign each transaction to one of one or more execution groups based on the value for the SI-Key in each transaction, each execution group configured to hold one or more transactions; and

a scheduling module configured to schedule the one or more transactions in each execution group for execution in an order defined by each SD-Key value, each execution group configured to execute in parallel with one or more additional execution groups.

10. The apparatus of claim 9, further comprising a creation module configured to create a new execution group in response to identifying a new value for the SI-Key, the new value comprising a value unassociated with a value for a SI-Key of existing execution groups, the new execution group associated with the new value for the SI-Key.

11. The apparatus of claim 9, wherein the assignment module is further configured to assign the transaction to an execution group based on a compound attribute, the compound attribute based on a value for the SI-Key and a value for an additional data field.

12. The apparatus of claim 9, further comprising a sorting module configured to sort a plurality of transactions in each execution group based on each SD-Key value.

13. The apparatus of claim 9, wherein the plurality of transactions comprises a transaction stream.

14. The apparatus of claim 9, wherein the SD-Key comprises one of a timestamp and a “

nextID”

auto-increment identifier.

15. The apparatus of claim 9, wherein the SI-Key comprises a unique entity identifier.

16. A system for processing serialized transactions in parallel while preserving transaction integrity, the system comprising:

an input device;

a memory comprising;

a receiving module configured to receive a plurality of serialized transactions, each transaction comprising at least two keys;

an accessing module configured to access a serialization-independent key (“

SI-Key”

) and a serialization-dependent key (“

SD-Key”

) from the plurality of transactions;

an assignment module configured to assign each transaction to one of one or more execution groups based on the value for the SI-Key in each transaction, each execution group configured to hold one or more transactions, the one or more execution groups assigned to a plurality of processors for processing;

a sorting module configured to sort a plurality of transactions in each execution group based on the SD-Key;

a scheduling module configured to schedule the one or more transactions for execution in one or more execution groups in an order defined by each SD-Key value, each execution group configured to execute in parallel with one or more additional execution groups;

a plurality of processors configured to process in parallel; and

a bus coupling the input device, the memory, and the plurality of processors.

17. The system of claim 16, further comprising a creation module configured to create a new execution group in response to identifying a new value for the SI-Key, the new value comprising a value unassociated with a value for a SI-Key of existing execution groups, the new execution group associated with the new value for the SI-Key.

18. The system of claim 16, wherein the assignment module is further configured to assign the transaction to an execution group based on a compound attribute, the compound attribute based on a value for the SI-Key and a value for an additional data field.

19. The system of claim 16, wherein the SD-Key comprises one of a timestamp and a “

nextID”

auto-increment identifier.

20. The system of claim 16, wherein the SI-Key comprises a unique entity identifier.