System and method for assigning a transaction to a serialized execution group based on an execution group limit for parallel processing with other execution groups

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.

BACKGROUND OF THE INVENTION

Field of the Invention

This invention relates to processing serialized transactions and more particularly relates to processing serialized transactions in parallel while preserving transaction integrity.

Description of the Related Art

The use of computing systems such as cloud, grid, cluster, and other related computing systems that provide large amounts of processing capacity are becoming increasingly more available to quickly process large amounts of data. The ideal data for processing by these parallel systems is often data that is divided and processed simultaneously in chunks. A large portion of business applications are “transaction processing” based and often, atomic transactions are “batched” together into larger units. However, a key characteristic of these batches of transactions is the need for serialization of the workload.

Serialized workloads do not trivially lend themselves to parallel processing algorithms because one transaction may depend on another transaction being executed in order. Thus, by default, serialized workloads often cannot take immediate advantage of the large quantity of non-scarce parallel computing resources available within a parallel processing computing system such as the cloud computing paradigm. Cloud computing makes large amounts of parallel computer resources available, and thus processing time can be reduced by several orders of magnitude. Nevertheless, if a large stream of transactions is serialized, the entire stream must be processed by a single processor stream, and thus fail to take advantage of other available processing resources.

SUMMARY OF THE INVENTION

The present invention has been developed for processing serialized transactions in parallel while preserving transaction integrity.

A method is presented for receiving a transaction, accessing a serialization-independent key (“SI-Key”) and a serialization-dependent key (“SD-Key”), assigning the transaction to an execution group, and executing the one or more transactions in the execution group.

In one embodiment, the method includes receiving a transaction comprising at least two keys. The method may also include accessing an SI-Key and an SD-Key from the transaction. An SI-Key value identifies the transaction as independent of transactions having a different value for the SI-Key. Furthermore, an SD-Key value governs a transaction execution order for each transaction having an SI-Key value that matches the SI-Key value associated with the SD-Key value.

In another embodiment, the method may include assigning the transaction to an execution group based on a value for the SI-Key. In this embodiment, the execution group holds one or more transactions. The method may also include scheduling the one or more transactions in the execution group for execution in an order defined by the SD-Key. The execution group may execute in parallel with one or more additional execution groups.

In one embodiment, the method may include creating a new execution group in response to identifying a new value for the SI-Key. The new value includes a value unassociated with a value for an SI-Key of existing execution groups and the new execution group is associated with the new value for the SI-Key.

In one embodiment, the execution group is a hash map. Furthermore, in another embodiment, assigning the transaction further includes assigning the transaction to an execution group based on a compound attribute. The compound attribute may be based on a value for the SI-Key and a value for the SD-Key.

In some embodiments, the method further includes sorting the one or more transactions in each execution group based on each SD-Key value. In addition, receiving a transaction may include receiving the transaction as part of a transaction stream. The dependent key may be a timestamp and the SI-Key may be a unique entity identifier.

An apparatus is provided for processing serialized transactions in parallel while preserving transaction integrity. The apparatus includes modules that may functionally perform the necessary steps as described above in relation to the method. These modules in the described embodiments include a receiving module, an accessing module, an assignment module, and a scheduling module. In certain embodiments, the apparatus may also include a creation module and a sorting module. Furthermore, in one embodiment, the SD-Key includes a “nextID” auto-increment identifier.

A system of the present invention is also presented for processing serialized transactions in parallel while preserving transaction integrity. The system also includes modules that may functionally perform the necessary steps as described above in relation to the method and apparatus. The system may be embodied as an input device, a memory, a plurality of processors configured to process in parallel, and a bus coupling the input device, memory, and plurality of processors.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1illustrates one embodiment of a system100for processing serialized transactions in parallel while preserving transaction integrity. The system100includes an input device102, a memory104comprising a transaction processing module106, a plurality of processors110a-dconfigured to process in parallel, and a system bus108coupling the input device102, the memory104, and the plurality of processors110a-d. Those of skill in the art recognize that the system100may be simpler or more complex than illustrated, so long as the system100includes modules or sub-systems that correspond to those described herein.

The input device102may include a human input device such as a keyboard, pointing device, or touch screen. Furthermore, the input device may also include a network input, an electronic bus, or any other input device for receiving inputs from another device. The memory104may include a non-volatile storage device such as a hard disk drive or CD ROM drive, a read-only memory (ROM), and a random access volatile memory (RAM). Furthermore, the memory104stores a transaction processing module106.

Given a stream of serialized transactions, certain subsets of the transactions are not serially dependent in relation to each other. Other subsets are serially dependent and a processor110amust execute them in the proper order to maintain transactional integrity. Transactional integrity involves executing serialized transactions in a proper order so as to obtain an accurate result. For example, in certain banking transactions that involve a common client who deposited a sum of money and then withdrew a sum of money, the two transactions must be executed in the order of occurrence, the deposit and then the withdrawal. If the client lacked sufficient funds for the withdrawal before the deposit was made, reversing the order of the transactions would result in a inaccurate negative balance in the account. The serially dependent subsets are often interleaved with other non-related subsets and are not necessarily contiguous.

Therefore, even though a stream of serialized transactions may include subsets of transactions that are not serially dependent on other subsets, the entire stream is typically executed serially.

However, the transaction processing module106divides the serialized transactions into execution groups, with the transactions that are serially dependent on each other in a common group. Each processor110a-dexecutes each execution group independently from the other execution groups. Consequently, the transaction processing module106executes a serialized batch of transactions in an execution group in parallel with another serialized batch of transactions in a different execution group, thus shortening the overall time to process the transactions. The magnitude of the time reduction can be quite large, depending on available parallel computing resources. Cloud computing or distributed computing makes large amounts of parallel computing resources available, thus reducing execution time by several orders of magnitude. Therefore, the transaction processing module106is able to divide an otherwise undividable serialized transaction stream for more efficient processing.

The system bus108may operably interconnect the input device102, memory104, and the plurality of processors110a-d. The plurality of processors110a-dmay reside in the same device as the memory104or may reside in one or more additional devices connected by a communication media such as a network, bus, or direct cable connection.

FIG. 2illustrates one embodiment of an apparatus200for processing serialized transactions in parallel while preserving transaction integrity. The apparatus200depicts one embodiment of the transaction processing module106and includes a receiving module202, an accessing module204, an assignment module206, and a scheduling module208.

The receiving module202receives a plurality of serialized transactions. The receiving module202may receive the plurality of serialized transactions from the input device102in the form of a transaction stream. The serialized transaction stream may include bank transactions, database transactions, or other serialized transactions that require some form of processing. In one embodiment, each serialized transaction includes at least two data fields. For example, in a serialized transaction stream from a bank, each bank transaction may include a CustomerID field to identify the customer, an Action field to identify the purpose of the transaction such as a withdrawal or deposit, an Amount field with a dollar amount, and a TimeStamp field with the time of the transaction. In one embodiment, each transaction includes two or more keys. A key is a data field that the transaction processing module106may use to group and sort the transactions.

The accessing module204accesses a serialization-independent key (“SI-Key”) and a serialization-dependent key (“SD-Key”) from the plurality of serialized transactions. In one embodiment, each value for the SI-Key identifies the transaction as independent of transactions having a different value for the SI-Key. For example, a customer identification, or CustomerID in the bank transaction may be an SI-Key because a transaction with a CustomerID having a first value is independent of transactions having a CustomerID with a second value. The CustomerID field does not relate to execution order. A processor110adoes not need to execute a transaction with a CustomerID of 1 before a transaction with a CustomerID of 2 based on the value of the CustomerID alone. Furthermore, a withdrawal from Customer1will not affect a transaction for Customer2.

The independent key may be a unique entity identifier such as CustomerID or a customer identification number. A unique entity identifier is an identifier that has a unique value for each distinct entity the identifier represents, and a common value for entries from the same entity. Therefore, a CustomerID may be a unique entity identifier because the CustomerID has the same value for transactions originating from a common customer, and a different value for transactions originating from another customer.

Each value for the SD-Key governs a transaction execution order for each transaction having an SI-Key value that matches the SI-Key value associated with the SD-Key value. One of ordinary skill in the art realizes that an SD-Key may be any data field holding values that require execution in a certain order such as a transaction number or a timestamp. Another example of an SD-Key is a “nextID” auto-increment identifier generated by many database applications that is incremented and assigned to each transaction or database entry.

For example, transaction A has a timestamp indicating that the transaction occurred earlier in time than Transaction B. A processor110amust often execute Transaction A before Transaction B because the result of Transaction A may influence the outcome of Transaction B if Transaction A and Transaction B belong to the same serializable group. Therefore, a processor110amust execute transactions with the same SI-Key in an order defined by the SD-Key to maintain transactional integrity as described above. For example, a withdrawal from Customer1will not affect a subsequent transaction by Customer2. Therefore, a processor110amay execute the transactions of Customer1in any order in relation to the transactions of Customer2. However, a withdrawal by Customer1will affect a subsequent transaction by Customer1.

In one embodiment, the accessing module204accesses the SI-Key and SD-Key based on keys predefined by the user. A user may define the data fields for the SI-Key and SD-Key based on the nature of the transactions. Furthermore, the user may define the data field for the SI-Key and the data field for the SD-Key in a set of predefined key requirements for reference by the accessing module204. In one embodiment, the predefined key requirements list several possible data fields for the accessing module to use as keys. In addition, one of ordinary skill in the art realizes that other methods, such as automatic methods, may be used by the accessing module204to identify or access keys in a transaction stream.

The assignment module206creates one or more execution groups and assigns each transaction to one of the one or more execution groups based on the value for the SI-Key in each transaction. Each execution group may hold one or more transactions. Furthermore, the assignment module206may assign transactions to execution groups based on user preference or on system performance and processor availability.

For example, in one embodiment, the assignment module206assigns transactions with a first value for the SI-Key to a first execution group and transactions with a second value for the SI-Key to a second execution group. In this embodiment, a distinct execution group exists for each SI-Key value. If a user has limited the number of execution groups for use by the assignment module206or if the number of processors110a-dis limited, the assignment module206may assign transactions with different values for the SI-Key to the same execution group. Therefore, in another embodiment, the assignment module206assigns transactions with a first value for the SI-Key and transactions with a second value for the SI-Key to a first execution group and assigns transactions with a third value for the SI-Key and a fourth value for the SI-Key to a second execution group. Therefore, a single execution group may hold transactions with different SI-Key values.

In one embodiment, the execution group is a hash map using the SI-Key values as keys for the hash map. The assignment module206groups each transaction into one of a number of parallel hash maps depending on the value of the SI-Key for the transaction.

In another embodiment, the assignment module206assigns the transaction to an execution group based on a compound attribute. The compound attribute is based on a value for the SI-Key and a value for an additional data field. For example, an execution group may comprise transactions with a common SI-Key combined with a zip code data field in the transactions. This may be useful to subdivide the execution groups based on geographic location for entities with offices in many locations. One of ordinary skill in the art realizes that the assignment module206may use many different data fields for the compound attribute to form various divisions of execution groups. By using a compound attribute, the assignment module206may further subdivide the transactions and is not limited to grouping the transactions based on the SI-Keys alone.

The scheduling module208schedules the one or more transactions in each execution group for execution in an order defined by the SD-Key. Each execution group executes on a processor110ain parallel with one or more additional execution groups on one or more additional processors110b-d. As mentioned above, a processor110amay execute transactions with a particular SI-Key value without regard to order in relation to transactions with a different SI-Key value. Therefore, the scheduling module208may schedule an execution group for a processor110ato execute in parallel with execution groups executing on other processors110b-dwithout affecting the results of the transactions in each execution group and maintaining transactional integrity. However, within each execution group, the scheduling module208schedules the transactions to be executed by a processor110ain order based on each value for the SD-Key. For example, if the SD-Key is a timestamp, the scheduling module208schedules the transactions in each execution group to be executed by a processor110ain order from the earliest timestamp to the latest.

Scheduling the execution groups to execute in parallel results in a decrease of overall execution time for the transaction workload. Furthermore, the scheduling module208may utilize computing environments with large amounts of available parallel computing resources such as a cloud computing system or a distributed computing system.

FIG. 3illustrates another embodiment of an apparatus300for processing serialized transactions in parallel while preserving transaction integrity. The apparatus300includes the receiving module202, the accessing module204, the assignment module206, and the scheduling module208, wherein these modules include substantially the same features as described above in relation toFIG. 2. Additionally, in one embodiment, the apparatus300includes a creation module302and a sorting module304.

The creation module302creates a new execution group in response to identifying a new value for the SI-Key. The new value is a value unassociated with the values for SI-Keys in existing execution groups. The new execution group is associated with the new value for the SI-Key. For example, if the creation module302determines that an execution group does not exist for the independent key value of CustomerID equal to 1, the creation module302creates a new execution group for transactions that have a value for the CustomerID equal to 1.

In one embodiment, the creation module302creates execution groups for every distinct SI-Key value. In another embodiment, the creation module302creates new execution groups until reaching an execution group limit. A user/operator may predefine the execution group limit. In addition, the execution group limit may be automatically determined by the creation module302based on the number of available processors110a-d, system resources of the executing system, and the like. In some embodiments, the creation module302determines an optimal number of execution groups to maximize performance and minimize execution time.

The sorting module304sorts a plurality of transactions in each execution group based on the SD-Key. In certain embodiments, the received transactions are not in order based on the SD-Key. Therefore, the sorting module304sorts the transactions to ensure data integrity. In one embodiment, the sorting module304sorts the transactions based on two or more SD-Keys. For example, the sorting module304may sort transactions in one execution group based on a batch number and a timestamp. In another embodiment, if two or more SI-Keys are assigned to a single execution group, the sorting module304first sorts by the SI-Key, then orders by the SD-Key.

FIG. 4illustrates one embodiment of a method400for processing serialized transactions in parallel while preserving transaction integrity. The method400starts402when the receiving module202receives404a plurality of transactions with each transaction including two or more keys. Next, the accessing module204identifies406an SI-Key independent of transaction order in relation to another transaction, and an SD-Key governing transaction execution order in relation to another transaction.

The assignment module206then assigns408each transaction to one of one or more execution groups based on a value for the SI-Key in each transaction. Finally, the scheduling module208schedules410the one or more transactions in each execution group for execution in an order defined by the SD-Key. Furthermore, the scheduling module208executes each execution group in parallel with one or more additional execution groups. Then the method400ends414.

FIG. 5illustrates a detailed embodiment of a method500for processing serialized transactions in parallel while preserving transaction integrity. First, the method500starts502when the receiving module202receives504a transaction stream through the input device. The transaction stream comprises a plurality of transactions, each transaction including two or more keys. Next, the accessing module204identifies506an SI-Key and an SD-Key from the plurality of transactions. The accessing module204may use user-defined data fields as keys or may select the SI-Key and SD-Key from the predefined key requirements.

The assignment module206then evaluates508each transaction. The creation module302determines510that the transaction has a new value for the SI-Key, or an SI-Key value that is not associated with any other execution groups, and the creation module302creates512a new execution group associated with that value. The assignment module206then assigns514the transaction to the new execution group.

Alternatively, the creation module302determines510that the value for the SI-Key in the transaction is already represented in an execution group or that the number of execution groups equals an execution group limit. Therefore, the assignment module206assigns514the transaction to an existing execution group and the creation module302does not create a new execution group.

Next, the receiving module202determines516that the transaction stream includes another transaction and the method repeats the steps beginning with the evaluating508step. Alternatively, the receiving module202determines516that the stream has ended. The sorting module304sorts518the transactions in each execution group based on the SD-Key. The scheduling module208schedules520the transactions in each execution group for execution in parallel on a plurality of processors110a-d. Finally, the plurality of processors110a-dexecutes522the transactions in each execution group. Then, the method500ends524.

FIG. 6is an example table600with transactions from a transaction stream. The table600illustrates data fields and keys of each transaction. The table600lists fourteen sample transactions. The first column602identifies the transaction. The next column604describes the transaction with classifications/descriptions such as “deposit,” “withdrawal,” or “transfer.” The next column606includes the CustomerID field which will serve as the SI-Key. The next column608includes a timestamp of when the transaction occurred and will serve as the SD-Key. The final column610includes the execution group to which the transaction Txis assigned.

T1, T4, T11, and T12are assigned to Execution Group A because each of these transactions share a common SI-Key606, a CustomerID of 1. Therefore, these four transactions originate from the same customer and can be executed in order to ensure that data integrity is preserved. Consequently, the scheduling module208may schedule the transactions T1, T4, T11, and T12to be executed in order based on the SD-Key timestamp608with the earliest transactions executed first. Thus, the two deposits (T1and T4) from the customer will be correctly executed before the withdrawal (T11) and transfer (T12).

Similarly, T2, T8, and T14are assigned to Execution Group B because these transactions have the SI-Key606with a CustomerID of 3. The transactions in Execution Group B may be executed in parallel with the transactions in Execution Group A because the transactions in each group belong to different customers and are not serialization dependent on each other.

Transactions T3, T5, and T7have been assigned to Execution Group C based on their SI-Key606values. The transactions in Execution Group C may also be executed in parallel with transactions from Execution Group A and Execution Group B.

Likewise, T6and T13have been assigned to Execution Group D and T9and T10have been assigned to Execution Group E. In the example table600, the timestamps608for T1and T2are identical. However, T1and T2are assigned to different execution groups610and will be executed independent of one another. Therefore, two transactions may have identical SD-Key608values if the transactions have distinct SI-Key606values.