Highly ordered transaction processing

Patent metadata

Field	Value
Publication number	US-9965731-B2
Application number	US-76693207-A
Country	US
Kind code	B2
Filing date	Jun 22, 2007
Priority date	Jun 22, 2007
Publication date	May 8, 2018
Grant date	May 8, 2018

Abstract

Improved techniques are disclosed for processing transactions or requests in a data processing system. For example, a method for processing requests in a system including a plurality of nodes includes the following steps. At least two nodes of the plurality of nodes receive a plurality of requests. The two nodes exchange information to determine an order for processing requests. The two nodes process the requests in accordance with the order. The order may include a total order or a partial order.

First claim

What is claimed is:

1. A method comprising:
receiving a first subset of a first plurality of requests and a first subset of a second plurality of requests in a first execution venue from two or more gateway nodes over at least one network;
receiving a second subset of the first plurality of requests in a second execution venue from the two or more gateway nodes over the at least one network;
determining, in the first execution venue, a first local threading of the first subset of the first plurality of requests;
determining, in the second execution venue, a second local threading of the second subset of the first plurality of requests;
transmitting the first local threading of the first subset of the first plurality of requests from the first execution venue to a coupling facility over said at least one network;
transmitting the second local threading of the first subset of the first plurality of requests from the second execution venue to the coupling facility over said at least one network;
determining, by the coupling facility, a total ordering for processing the first plurality of requests based at least in part on the first local threading of the first subset of the first plurality of requests and at least the second local threading of the second subset of the first plurality of requests;
receiving the total ordering for processing the first plurality of requests in the first execution venue from the coupling facility over said at least one network;
processing, in the first execution venue, the first plurality of requests in accordance with the total ordering received from the coupling facility;
wherein the first local threading of the first subset of the first plurality of requests is different than the second local threading of the second subset of the first plurality of requests;
wherein the first subset of the first plurality of requests and the second subset of the first plurality of requests have at least one request in common;
wherein the first execution venue and the second execution venue are implemented as respective first and second virtual machines on at least one processing device comprising a processor coupled to a main memory;
wherein the coupling facility comprises a shared memory accessible by the first execution venue and the second execution venue;
wherein the first plurality of requests is associated with a first order book of a plurality of order books, the first order book being managed by a first group of two or more execution venues comprising the first execution venue and at least the second execution venue;
wherein the second plurality of requests is associated with a second order book of the plurality of order books, the second order book being managed by a second group of two or more execution venues comprising the first execution venue;
wherein the first execution venue is part of a first multicast group comprising the first group of execution venues and a second multicast group comprising the second group of execution venues;
wherein the first subset of the first plurality of requests are received at the first execution venue from the two or more gateway nodes via one or more multicast messages specifying a first multicast address of the first multicast group;
wherein the first subset of the second plurality of requests are received at the first execution venue via one or more multicast messages specifying a second multicast address of the second multicast group; and
wherein central processing unit resources allocated to the first virtual machine and the second virtual machine are dynamically adjusted responsive to determining a status of respective ones of the plurality of order books.

2. The method of claim 1 , wherein the first local threading of the first subset of the first plurality of requests comprises a total ordering of the first subset of the first plurality of requests.

3. The method of claim 1 , wherein the first local threading of the first subset of the first plurality of requests comprises a partial ordering of the first subset of the first plurality of requests.

4. The method of claim 1 , wherein receiving the first subset of the first plurality of requests comprises:
receiving a first local ordering of at least a portion of the first subset of the first plurality of requests from a first one of the two or more gateway nodes; and
receiving at least a second local ordering of at least a portion of the first subset of the first plurality of requests from a second one of the two or more gateway nodes.

5. The method of claim 4 , wherein determining the first local threading of the first subset of the first plurality of requests is based on the first local ordering and the second local ordering.

6. The method of claim 1 , wherein the first subset of the first plurality of requests comprises at least one request not in the second subset of the first plurality of requests.

7. The method of claim 1 , further comprising the first execution venue recording results of processing respective ones of the first plurality of requests in persistent storage of a history recorder coupled to the first execution venue over said at least one network.

8. The method of claim 7 , wherein processing the first plurality of requests in accordance with the total ordering comprises utilizing a sliding window, the sliding window comprising:
a first request at a first edge of the sliding window, the first request being a newest unhandled request, the first request advancing each time another request in the first plurality of requests is assigned a total ordering number;
a second request at a second edge of the sliding window, the second request being an oldest request that has been processed and persisted in the history recorder but for which a request completion acknowledgement has not been received from the two or more gateway nodes, the second request advancing on receiving the request completion acknowledgment;
a third request between the first edge and the second edge, the third request corresponding to a request that is expected to be processed next according to the total ordering; and
a fourth request between the first edge and the third request, the fourth request corresponding to a request that has been processed but for which a history recording completion acknowledgement has not been received from the history recorder, the fourth request advancing on receiving the history recording completion acknowledgment.

9. The method of claim 1 , wherein the total ordering is determined by performing an ordering aggregation procedure, and wherein the performing the ordering aggregation procedure comprises collating requests received from the two or more gateways and using the coupling facility to determine the total ordering.

10. A method comprising:
receiving a first local threading of a first subset of a first plurality of requests at a coupling facility from a first execution venue over at least one network;
receiving a second local threading of a second subset of the first plurality of requests at the coupling facility from a second execution venue over said at least one network;
determining, in the coupling facility, a total ordering for processing the first plurality of requests based at least in part on the first local threading of the first subset of the first plurality of requests and the second local threading of the second subset of the first plurality of requests; and
transmitting the total ordering for processing the first plurality of requests from the coupling facility to the first execution venue and the second execution venue over said at least one network;
wherein the first execution venue and the second execution venue receive the respective first and

Assignees

• Dantzig Paul M
• Dillenberger Donna N
• Iyengar Arun Kwangil
• Parr Francis Nicholas
• Su Gong
• IBM

Inventors

• Dantzig Paul M
• Dillenberger Donna N
• Iyengar Arun Kwangil
• Parr Francis Nicholas
• Su Gong

Classifications

• G06Q10/06 Primary

  Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling · CPC title

• G06F9/5038 Primary

  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) · CPC title

• G06F2209/5021

  Priority · CPC title