Back to results
US 8,572,236 B2Granted
Distributing services in graph-based computations
AssigneeAb Initio Technology LLC
InventorsIgor Sherb, Joseph Skeffington Wholey, III, Larry W. Allen
Life of this patent
Estimating the term…
Abstract
A service request is processed according to a computation graph associated with the service by receiving inputs for the computation graph from a service client, providing the inputs to the computation graph as records of a data flow, receiving output from the computation graph, and providing the output to the service client. Data flows are processed concurrently in a graph-based computation by potentially concurrent execution of different types of requests, potentially concurrent execution of similar request types, and/or potentially concurrent execution of work elements within a request.
Claims71
A method including:
- processing a service request according to a computation graph associated with the service, the computation graph including multiple components interconnected by links representing data flows, by
- receiving inputs for the computation graph from a service client,
- providing the inputs to the computation graph as elements of a data flow,
- partitioning the elements into multiple sets, based on a type of action to be performed on elements in a given set,
- assigning each set to a different subgraph of the computation graph, each subgraph including at least some of the components and the links of the computation graph,
- partitioning each of one or more of the sets into subsets of elements,
- selecting, for each subset of a partitioned set, an instance of processes associated with the components of the subgraph assigned to the set, from a pool of instances identified as available, the instance including the components and the links of the subgraph,
- assigning each subset to its respective selected instance, and tracking that the instance is in use,
- receiving output from the subgraphs of the computation graph, and
- providing the output to the service client.
7 more elements
A system for processing a service request according to a computation graph associated with the service, the computation graph including multiple components interconnected by links representing data flows, the system including:
- means for receiving inputs for the computation graph from a service client,
- a processor configured to provide the inputs to the computation graph as elements of a data flow,
- means for partitioning the elements into multiple sets, based on a type of action to be performed on elements in a given set,
- means for assigning each set to a different subgraph of the computation graph, each subgraph including at least some of the components and the links of the computation graph,
- means for partitioning each of one or more of the sets into subsets of elements,
- means for selecting, for each subset of a partitioned set, an instance of processes associated with the components of the subgraph assigned to the set, from a pool of instances identified as available, the instance including the components and the links of the subgraph,
- means for assigning each subset to its respective selected instance, and tracking that the instance is in use,
- means for receiving output from the subgraphs of the computation graph, and
- means for providing the output to the service client.
6 more elements
A system for processing a data flow in a graph-based computation, the system including
- means for identifying a first computation graph applicable to a first record in the data flow, the computation graph including multiple components interconnected by links representing data flows,
- means for selecting a first instance of processes associated with components of a subgraph from a pool of instances identified as available, the subgraph including at least some of the components and the links of the first computation graph, and the instance including the components and the links of the subgraph,
- means for selecting a second instance from the pool of instances of the subgraph identified as available,
- first processors configured to process a first work element in the first record by the first instance of the subgraph and process a second work element in the first record by the second instance of the subgraph,
- means for identifying the second work element in the first record as capable of being processed independently from the first work element,
- means for receiving a first output work element from the first instance,
- means for receiving a second output work element from the second instance, and
- second processors configured to associate the first output work element with the first
- record and associate the second output work element with the first record,
- in which the first processors are configured to execute the first instance of the subgraph and the second instance of the subgraph at least partially simultaneously.
7 more elements
A method of processing a data flow in a graph-based computation including
- identifying a first computation graph applicable to a first record in the data flow, the computation graph including multiple components interconnected by links representing data flows,
- selecting a first instance of processes associated with components of a subgraph from a pool of instances identified as available, the subgraph including at least some of the components and the links of the first computation graph, and the instance including the components and the links of the subgraph,
- processing a first work element in the first record by the first instance of the subgraph,
- selecting a second instance from the pool of instances of the subgraph identified as available,
- identifying a second work element in the first record as capable of being processed independently from the first work element,
- processing the second work element in the first record by the second instance of the subgraph,
- receiving a first output work element from the first instance,
- receiving a second output work element from the second instance,
- associating the first output work element with the first record, and
- associating the second output work element with the first record,
- in which the first instance of the subgraph and the second instance of the subgraph are executed at least partially simultaneously.
8 more elements
A computer program, stored on a non-transitory computer-readable medium, for processing a service request according to a computation graph associated with the service, the computation graph including multiple components interconnected by links representing data flows, the computer program including instructions for causing a computer to:
- receive inputs for the computation graph from a service client,
- provide the inputs to the computation graph as elements of a data flow,
- partition the elements into multiple sets, based on a type of action to be performed on elements in a given set,
- assign each set to a different subgraph of the computation graph, each subgraph including at least some of the components and the links of the computation graph,
- partition each of one or more of the sets into subsets of elements,
- select, for each subset of a partitioned set, an instance of processes associated with the components of the subgraph assigned to the set, from a pool of instances identified as available, the instance including the components and the links of the subgraph,
- assign each subset to its respective selected instance, and track that the instance is in use,
- receive output from the subgraphs of the computation graph, and
- provide the output to the service client.
6 more elements
A computer program, stored on a non-transitory computer-readable medium, for processing a data flow in a graph-based computation, the computer program including instructions for causing a computer to:
- identify a first computation graph applicable to a first record in the data flow, the computation graph including multiple components interconnected by links representing data flows,
- select a first instance of processes associated with components of a subgraph from a pool of instances identified as available, the subgraph including at least some of the components and the links of the first computation graph, and the instance including the components and the links of the subgraph,
- process a first work element in the first record by the first instance of the subgraph,
- select a second instance from the pool of instances of the subgraph identified as available,
- identify a second work element in the first record as capable of being processed independently from the first work element,
- process the second work element in the first record by the second instance of the subgraph,
- receive a first output work element from the first instance,
- receive a second output work element from the second instance,
- associate the first output work element with the first record, and
- associate the second output work element with the first record,
- in which the instructions cause the computer to execute the first instance of the subgraph and the second instance of the subgraph at least partially simultaneously.
8 more elements
Dependencies are inferred from the claim text.