HK1194175B - Distributing services in graph-based computations - Google Patents

Description

Distributing services in graph-based computing

The present application is a divisional application of an invention patent application having an application number of 200780029791.9, an application date of 2007, 8/9, and an invention name of "assigning services in graph-based computing".

Priority

This application claims priority from U.S. provisional patent application No. 60/836,745 filed on 8/10/2006, the entire contents of which are incorporated herein by reference.

Technical Field

The present invention relates to distributing services (distributing services) in graph-based computing.

Background

Typically, complex business systems process data in multiple stages, feeding the data produced by one stage into the next. The overall flow of information through the above system can be described by a directed data flow graph, in which vertices represent components (which may be data files or processes) and links or "edges" represent the flow of data between components.

The graph may also be used for direct-call (invoke) computations. "CO > OPERATING with Graphic Development Environment (GDE) from the company Ab Initio software corporation, Lexington, MASuch a system is "embodied" (embody). A graph made according to such a system provides a method for obtaining information into and out of the processes represented by the components of the graph, a method for moving information between the processes, and a method for defining a running order (running order) for the processes. Such a system includes algorithms for selecting a method of communication between processes and algorithms for scheduling (schedule) process execution and also provides monitoring of the execution of the graph.

The assigned service mechanism (architecture) allows computer programs to access through a network interface such as the world wide web to obtain the functionality of other programs without having to introduce the functional properties (functionality) of these other programs into their own run code (operating code).

Disclosure of Invention

In general, in one aspect, a service request is processed according to a computation graph associated with a service by performing steps comprising: receiving input for the computation graph from a service client, providing the input to the computation graph as a record of a data flow, receiving output from the computation graph, and providing the output to the service client.

The implementations may include one or more of the following features.

The step of receiving the input comprises: identifying the input from the service client in a service request, and providing the input to the computational graph comprises: associating a request identifier with the service request, providing a work element including the input to the computational graph, associating the request identifier with the work element, and transmitting an association (association) of the request identifier with the work element to an output node. The step of identifying the input comprises extracting the input from an encapsulated request. The encapsulated request comprises a SOAP request. The step of receiving the output comprises: receiving a work element including output from the computational graph, and identifying a request identifier associated with the work element, and providing the output to the service client comprises: generating a service response corresponding to the service request identified by the request identifier, the service response including the output included in the work element. The step of generating the service response comprises: embedding the output in the encapsulated response. The encapsulated response comprises a SOAP response.

Processing a second service request according to the computation graph by: receiving a second input for the computational graph from a second service client, providing the second input to the computational graph as a record of a second data flow, receiving a second output from the computational graph, and providing the second output to the second service client; and processing the first input and the second input in parallel in the computational graph. The step of processing the first input and the second input in parallel comprises: identifying a first subgraph applicable to the first input, processing the first input in the first subgraph, identifying a second subgraph applicable to the second input, processing the second input in the second subgraph, receiving a first output from the first subgraph, and receiving a second output from the second subgraph, wherein the first subgraph and the second subgraph are executed simultaneously. The step of processing the first input and the second input in parallel comprises: identifying a first instance of a subgraph as available, processing the first input in the first instance of the subgraph, identifying a second instance of the subgraph as available, processing the second input in the second instance of the subgraph, receiving a first output from the first instance, and receiving a second output from the second instance, wherein the first instance of the subgraph and the second instance of the subgraph are executed simultaneously.

In general, in one aspect, a data stream is processed in a graph-based computation by performing steps comprising: identifying a first graph applicable to a first record in the data stream, identifying a first sub-graph applicable to a first work element in the first record, processing the first work element in the first sub-graph, identifying a second sub-graph applicable to a second work element in the first record, processing the second work element in the second sub-graph, receiving a first output work element from the first sub-graph, receiving a second output work element from the second sub-graph, associating the first output work element with the first record, and associating the second output work element with the first record, wherein the first sub-graph and the second sub-graph are executed at least partially concurrently.

In general, in one aspect, a data stream is processed in a graph-based computation by performing steps comprising: identifying a first graph applicable to a first record in the data stream, identifying a first instance of a sub-graph as available, processing a first work element in the first record in the first instance of the sub-graph, identifying a second instance of the sub-graph as available, processing a second work element in the first record in the second instance of the sub-graph, 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, wherein the first instance of the sub-graph and the second instance of the sub-graph are executed at least partially concurrently.

Other features and advantages of the invention will be apparent from the description and from the claims.

Drawings

Fig. 1A and 2 show schematic diagrams of a system for distributing services.

FIG. 1B shows a flow diagram of a process for invoking a service.

Figures 3-5b illustrate diagrams for providing distribution services.

Detailed Description

In some instances, there are two ways to interact graph-based computing with the distribution service. In some examples, a graph is used to invoke a service and is associated with the service (relationships to) such that the service appears to be treated as a node in the graph. In other examples, an application (application) is associated with a graph such that the graph provides a service. Both of these cases can be achieved simultaneously. For example, a graph that is providing a service to an application may itself invoke other services to perform some of its computations. For example, a service called by a graph may be provided by other graphs, such that a first graph calls a second graph, rather than including it as a subgraph.

In some instances, as shown in fig. 1A, the service node 102 of the graph-based computation 100 operates by invoking a service in a distributed service-oriented architecture (distributed service-oriented architecture). That is, when the service node 102 is executed, the service 108 outside the graph 100 is invoked as a client of the service. For example, the service node 102 may communicate with a web services plug-in 104 hosted (hosted) on an application server 106 using a combination of one or more of SOAP, HTTP, XML, WSDL, and the like, to reach an external service 108, thereby enabling the service node 102 to access the web service. The external service 108 itself may be a graph-based computation, as described below. The services may be performed in an assignment using any of a variety of methods for assigning computing tasks.

The service node 102 receives input 110 from nodes of other graphs (e.g., node 112) in native format (native format) of the graph-based computation 100, such as records described in a data description language similar to DML of Ab Initio. Node 102 then formats its input 110 into a format appropriate for the type of web service it uses (e.g., SOAP or other type of encapsulated based request) and transmits service request 114 to application server 106. The URL in the request 114 indicates to which of the application server 106, the plug-in 104, and the service 108 the request is sent. The request 114 can be sent in a variety of ways, including by HTTP and RPC (remote procedure Call). The plug-in 104 on the server 106 reformats the incoming request 114 into the appropriate format and passes the appropriate call 116 to the external service 108.

After the service 108 performs any runs it invokes, the service 108 returns an output 118 to the plug-in 104. The plug-in 104 reformats the output 118 of the service 108 into an appropriate service response 120 for return to the service node 102. Service node 102 reformats service response 120 into the appropriate output format and passes output 121 to a node of the downstream graph (e.g., node 122). From the perspective of the nodes 112, 122, 124, and 126 of the other graphs, the assigned service node 102 may participate in the computation 100 of the graph (partition in) as any other node. The mechanism and arrangement of the server 106, such as the nature of the plug-in 104 and how it communicates with the service 108 (or, e.g., whether or not the plug-in 104 is used), is independent of the graph node, as long as the service node 102 receives the type of response 120 it expects. As described below, the servers 106, plug-ins 104, and services 108 may themselves be graph-based computing servers, plug-ins, and graphs, respectively.

In some examples, graph 100 is pipelined, meaning that each node processes a single record or collection of records of a large flow of input records in a pipelined sequential phase manner. In a given phase, each successor (subsequent) node works on the record or set of records it receives from the predecessor (previous) node, while each predecessor node works on the next record or set of records in the input stream. The service node 102 may coordinate the above operations by: that is, service node 102 receives additional records and assigns work requested by each of the additional records to service 108 before a response corresponding to a prior service request is received. For example, if service 108 is capable of handling multiple parallel requests (multiple concurrent requests), the above-described approach can be implemented here. A record may consist of discrete or dispersible working elements that may be processed in such pipelined stages as described for records.

If different requests 114 take different amounts of time to process, then the service node 102 may receive responses in a different order (order) than the order in which its inputs 110 were received. This allows multiple services with different processing times to be accessed by a single node 102. A service node, such as service node 102, may be selectively configured to provide its outputs 121 in an order different from the order in which its inputs 110 are received. To allow such parallel processing without using multiple threaded processes for the service node 102 and without including data in each request 114 describing the entire state of the graph 100 (so that each request 114 can be used based on its return), the service node 102 tracks (keep track of) pending (outstand) requests 114 and matches them with incoming responses 120. In some instances, the graph is pipelined such that individual records or work elements are processed one node at a time and the decentralized nodes process decentralized records or work elements, but multiple (multiple) records or work elements can be assigned to a single service node 102 at any given point in time.

In the pipelined graph, the service node 102 treats each record (e.g., each record of a data stream) as a single transaction (transaction). The corresponding request is generated based on the fields (fields) in the single input record. Some domains may define attributes of the request (e.g., a URL), while other domains are passed as embedded data.

In some examples, as shown in process 150 in FIG. 1B, the relationship between the request 114 and the response 120 is tracked in a memory accessible by the service node 102. The memory may be a vector, table, file, or other such data structure. When an input record 110 is received, as in step 152, a copy of the record 110 is stored to memory 151, as in step 154. The service node 102 then generates the request 114, step 156, sends the request to the service, step 158, and writes the requested ID to memory, step 160, and associates it with the stored copy of the record 110. When the response 120 is received, it includes an ID corresponding to one of the requests to be completed, step 162. The service node 102 matches the ID with an ID in memory, step 164, and retrieves (retrieve) a copy of the corresponding output record 110, step 166. The record is updated in response to response 120, step 168, and output 121 is generated. If the service node 102 is configured to generate outputs in the order in which they become available (not necessarily in the same order as the receipt of the inputs), the outputs 121 are provided to the next node 122, step 170. If the service node 102 is configured to produce results in the same order as its input, the outputs are retained in memory until all outputs corresponding to the previous record have been written as output 121, at which point the output 121 may not be written, as in step 172.

In some instances, graph-based computing is provided as a web service. We refer to a graph providing a network service as a provider graph (provider graph). As shown in FIG. 2, a process 200 running on a client-side system 202, which process 200 may be a computation of a graph, but may be any type of application, sends a request 204 (for a computation that requests use of a provider graph 206) to an application server 208. The request 204 is sent in a format suitable for web-based or other web services (e.g., SOAP, HTTP, or RPC requests). The request 204 is received in a service interface (interface) of the application server 208 according to instructions of a web services plug-in 210 (for SOAP or HTTP requests) running on the application server 208.

The web service plug-in 210 is an application that can handle requests and responses between a web service client and a graph providing a service. The plug-in 210 is installed and executed on the application server 208. The web service plug-in may communicate with a collection of multiple web service provider graphs. Each graph is contained in a list of services accessed by the plug-in. For example, the plug-in uses the URL in the client-side HTTP request message to direct the request to a specific graph.

The plug-in 210 formats the service request into a request 212 (e.g., RPC request) suitable for processing of the graph, and forwards this request 212 to a graph server 214 hosting the graph 206. In some instances, the RPC calls are enabled to go from the client 200 directly to the supplier graph 206. At the graph server 214, the input 216 contained in the request 212 is provided to the graph 206, and the graph 206 is processed to produce an output 218. The graph server 214 sends the output 218 to the application server 208 and its web service plug-in 210 in the appropriate format for the output 220 of the graph (e.g., an RPC response). The plug-in 210 reformats the output 220 of the graph into a web service response 222 having a complementary (complementary) format to the original request 204. The output is returned to the client or to other entities that invoked the service in a conventional manner appropriate for the network service. Processing on client system 202 then treats the response as any other web-based response or web service response.

The graph may process the input using any or all of pipeline parallelism, component parallelism, and data parallelism. That is, multiple sets of inputs may be received, may be interleaved (interleaved) in a pipelined stage, or may be processed in parallel by a collection of different components, perhaps after partitioning.

In some instances, the public or external interfaces to the vendor diagram are defined by a WSDL (web services description language) file. The WSDL file contains an XML-based description of all messages and runs that need to interact with the provider graph. A WSDL file may be defined by an organization, industry, or any other entity for accessing web services related to the entity. WSDL files may also be customized (customization) for performing specific operations (augmentation). In some examples, the WSDL file is generated according to the record format and type definition of the components in the subgraph associated with the supplier graph. In some instances, a single provider graph includes multiple subgraphs that perform respective services. The WSDL file generated from such subgraphs allows the client to access each of the services provided by the provider graph's subgraphs.

In the provider graph, the incoming service request input is converted into the internal language of the service-providing subgraph. For example, as shown in FIG. 3, an incoming request 306 (e.g., a SOAP request) includes a data payload 308(payload), where the payload 308 requests processing through actions (actions) specified by the message. For example, the payload 308 may be a record (described in DML) to be processed by the graph in the action processors 300a and 300 b. Regardless of the format of the incoming messages, the interface layer 301 parses (parse) them and provides the appropriate messages to the nodes of the graph in whatever format they request. At the output, the interface layer 301 works in the opposite way.

Once the message 306 is translated, the action partitioning (partition) type node 302 interprets the action specified in the message 306 and sends a record 308 in the data payload to the appropriate action processor 300a or 300 b. In some examples, partitioning node 302 does not receive a subsequently incoming message 307 until after the gather node 304 notifies partitioning node 302 that the work of the previous record 308 has been output from action processor 300a or 300 b.

In some instances, to enable parallel processing of messages, such as service requests, the partitioning node 302 is configured to partition the action records corresponding to the service requests. The above approach enables multiple requests to be processed simultaneously if they are not requesting the same action handler. For example, if a first record 308 requests an action processor 300a and a second record 310 requests an action processor 300b, the partitioning node 302 sends the second record 310 to the action processor 300b without waiting for the aggregation node 304 to report that the first record 308 has completed its processing.

The sink node 304 receives the processed records 308 and 310 from the action processors 300a and 300b and packages them into a response message 312 and a response message 313, wherein the response message 312 and the response message 313 contain the processed records 308 'and 310' as data payloads. If the partitioner 302 is partitioning transactions (transactions) so that multiple records are processed at once, the sink node 304, upon receiving the processed records 308 'and 310', is able to proceed in a different order than the request messages 306 and 307. An interface 315 between the partition node 302 and the sink node 304 allows the sink node to associate the output records 308 'and 310' with the corresponding inputs 308 and 310, thereby sending reply messages 312 and 313 back to the correct client.

The motion processors 300a and 300b may take any form. As described above, records 308 and 310 may have any format, such as the format described in DML. In this case, the interface layer 301 converts the incoming language (e.g., SOAP) into the DML format used by the action handler. In some examples, the input between the interface layer 301 and the partition node 302 and the sink node 304 may be expressed using an intermediate language.

In some instances, when the sink node 304 is configured to receive the records 308 'and 310' in their order of arrival, the processing of the actions may be further divided within the action processor, as shown in FIG. 3b for action processor 300 b. The action type partitioning node 302 receives the request messages 306 and 307 and sends (route) their records 308 and 310 to the appropriate action processor 300a or 300 b. In the action processor 300b, the record is received by another partitioning node 352, which partitioning node 352 partitions the record in shares (pool). Multiple instances 350a, 350b, and 350c, which are shared to be attributed to sub graph 350, where sub graph 350 implements the processing of action processor 300 b. Each instance may process a different record in parallel with other instances. By partitioning different records 308 and 320 to different instances, the action processor 300b can process multiple records in parallel, allowing the partitioning node 302 to send the next record 320 to the action processor before the previous record 308 processing is complete. The sink node 354 is paired with the partition node 352 so that the node can keep track of which of the instances 350a, 350b and 350c are in use and use the free instances when possible in order to improve parallelism (concurency) and performance. The sink node 304 will also receive the outputs 308 'and 310' of the action processors 300a and 300b and return appropriate output messages 312 and 313 to the client side through the interface layer 301.

Output records 308 'and 310' and output messages 312 and 313 may be returned in a different order than the order in which input requests 306 and 307 were received. For example, if input record 310 contains fewer work elements (described below) than record 308, output response 313 may be returned first, even if output response 313 corresponds to subsequently received request 307. If the action processors 300a and 300b operate in such a way that records may be processed out of order or at different rates depending on their complexity or other factors, the output order may also change based on the complexity of the input data.

In some examples, as shown in fig. 4, the record 406 of a single service request includes data that is processed as a data stream by a provider graph, i.e., as a plurality of work elements 408a-408e, where the work elements 408a-408e pass through the graph one by one. The action processor 300a (if the record is not to be further partitioned) or the sub-graph 350 (if the record is to be further partitioned) includes a unpack node 402, wherein the unpack node 402 unpacks (decomplexes) the input record 406 into its various work elements 408a-408e and sends the work elements appropriately into the serving sub-graph 400. The corresponding packing (wrap) node 404 reassembles the streams of output work elements 408a '-408 e' into a single response 412 for return to the client that sent the request 406.

In some examples, as shown in fig. 5a, once actions are divided and broken down into work elements, the work elements are also processed in parallel. As with the record in FIG. 3a, the partition node 502 partitions the work elements 408a-408e according to the type of work element that it requests which of the work element processors 500a or 500b to process each work element. If the order in which the work elements are processed is important, then after the to-be-assembled node 504 notifies it that each output work element 408' was received, the partition node 502 sends only one work element 408 to the processors 500a and 500b at a time (likely each work element is partitioned to use two processors). In some examples, if the order of processing is not important, the partitioning node sends one work element to each processor 500a and 500b, assuming that the work elements require different processors.

As the work elements 408a '-408 e' leave the processors 500a and 500b, they are accumulated (accumulated) by the collection node 504. Once all the work elements from one record 406 have been collected, they are merged back into the output record 412. The communication 515 between the partitioning node 502 and the aggregation node 504 allows the partitioning node 502 to track which work element processors may be used for additional work elements.

Techniques for processing multiple parallel data streams are also described in U.S. patent 6,584,581, published 24/6/2003 and U.S. patent 6,654,907, published 25/11/2003, the contents of which are incorporated herein by reference.

Fig. 5b shows in detail how the work element processor 500b operates and how the sub-graph of fig. 5a is tied to certain higher level nodes of fig. 3a, 3b and 4 to form the provider graph 501. In some examples, as shown in fig. 5b, work element processor 500b further divides the work elements to be run in multiple instances 550a, 550b, and 550c of subgraph 550. The instance 550a is selected from a share of available instances of processes associated with nodes of graphs within the sub-graph 550. Initially, work element 408i is received by partitioning node 552. The node 552 has accessed multiple instances 550a, 550b, and 550c of the subgraph 550. The output of each instance is received through a sink node 554. For external processes (e.g., services or other subgraphs) that would slow down work handling by these nodes, subgraph 550 may take turns calling these external processes.

In the foregoing system, a partition component similar to node 552 could have divided a single work element 514 into separate components and sent one component to each of instances 550i (where i is a, b, or c). To eliminate possible parallelism, the sink node 554 would wait until each instance returns an output before merging the multiple outputs into a single output for the work element. To maintain pipelining, the partitioning node may have sent delimiters (delimiters) via each instance behind the work elements so that when the delimiters are received from each instance, the aggregate component can know that the work elements have been completed. In some examples, in a given stage of pipelining, a delimiter is sent after a set of multiple work elements is processed by a given node.

In contrast, shared partitioning node 552 sends the entire work element 408a to a single instance 550a for processing. The sink node 554 is configured to wait (expect) for output 408 a' associated with work elements from only one instance 550 a. Upon receiving the waiting output 408 a' (which, in some examples, is followed by a separator), the sink node 554 provides the output to the next node 504. The sink node 554 does not wait for work element components or delimiters from the other instances 550b and 550 c. This allows the work element processor 500b to use only the instances 550i that are actually needed for a given work element. Like the shared partitioning of transaction records (transactional records) in FIG. 3b, the shared partitioning of work elements also allows multiple work elements to be processed in parallel. Instead of waiting for the first work element 408a to finish processing and emerge from its instance 550a, the partition node 552 receives another work element input 408c from the upstream node 502 and sends it to the next available instance 500 b. In this way, multiple work elements 408a and 408b may be processed simultaneously without having to multithread (multithreaded) the partition node 552. In some instances, the partitioning node 552 notifies the sink node 554 which work elements are in each instance via the communication link 560 so that the sink node 554 knows what is waiting and can associate the output elements 408a ', 408 c' with the input work elements 408a, 408 c.

Dividing the work elements among the shares also allows the outputs 408a ', 408b ', and 408c ' to be returned out of order with respect to the inputs 408a, 408b, and 408 c. For example, if the data in work element 408a causes instance 550a to process the work element longer than instance 550b does work element 408c, then sink node 554 will receive output 408c 'before it receives output 408 a'. Since the two work elements 408a and 408c are independent of each other, the sink node 554 is able to send the output 408c 'to the next node 504 without having to wait for the output 408 a'. It is assumed here that the other stages (e.g., divide/assemble pair 502/504 and pack/unpack pair 402/404) are configured to accommodate (accmod ate) changes in the order of work elements within work element processor 500 b. In some instances, it may be necessary or desirable to maintain the order, then the sink node 554 will retain the outputs 408c 'until the outputs 408 a' are received and release them in order to the next node 504. In such calculations, it is also an advantage that instances 550a, 550b, and 550c can process multiple work elements simultaneously. For example, if the processing time of the subgraph 550 is longer than the processing time of other nodes or subgraphs, then such a calculation would be useful.

Both the action type partitioning and sharing partitioning for transactions and the type partitioning and sharing partitioning for work elements allow the graph to run with inherent parallelism, i.e., related or unrelated work elements are processed simultaneously by different processing elements.

Sharing partitions, type partitions, and other methods of parallel processing of requests and their work elements may all be implemented in the provider graph, such that the services provided by the graph are themselves capable of processing parallel input. For example, the graph 501 in FIG. 5b operates as a provider graph, where the first node 570 is a subscribing node (subscribe node) and the final node 572 is a publishing node (publish node) paired with the subscribing node 570. The subscribing node 570 receives the request including the input 406 and sends the input 406 to the dividing node 402. The subscribing node 570 cooperates with the publishing node 572 to match the outputs 412 with the inputs 406 and package them (packages) into appropriate responses (i.e., to ensure that each response reaches the calling client). Because the graph 501 handles parallel records and parallel work elements, the subscribing node 570 can continuously receive incoming requests without waiting for the publishing node 572 to receive the output 412. Using a sub-graph that performs action type partitioning on requests allows a single provider graph 501 to provide multiple services.

In some instances, the subscribing node 570 and the publishing node 572 assume that the individual requests are independent and that the order in which the requests are returned is irrelevant, and thus the partitioning node 402 and the aggregating node 404 in the graph 501 are configured to execute out of order. If the order is important, either or both of the subscribing 570 and publishing 572 nodes can ensure that the order in which the responses are returned is the same as the order in which the corresponding outputs were received.

Other embodiments are within the scope of the following claims and other claims to the applicant.

Claims (21)

1. A system for distributing services in graph-based computing, a service request being processed according to a computational graph associated with a service, the computational graph comprising nodes connected by links representing recorded data flows passing between the nodes, by:

means for receiving a first input for the computation graph from a service client,

means for providing the first input arranged as a record of a data flow to the computational graph, wherein the record of the data flow includes a plurality of work elements,

means for dividing the plurality of work elements into a plurality of groups based on a type of action performed on the work elements in a given group,

means for providing each group to a different subgraph of the computational graph, each subgraph comprising at least some components of the computational graph and the links,

means for dividing each of one or more of the plurality of groups into a plurality of subgroups of the plurality of working elements,

means for assigning each subgroup of a given group to a different instance of the subgraph assigned to the given group, each instance comprising the components and the links of the subgraph,

means for receiving an output from said subgraph of said computational graph, an

Means for providing a service response including the output from the subgraph,

wherein said means for receiving said first input comprises means for identifying said first input in a service request from said service client, and

the means for providing the first input to the computational graph comprises:

means for associating a request identifier with the service request,

means for providing a work element including the first input to the computational graph,

means for associating said request identifier with said work element, an

Means for transmitting an association of the request identifier and the work element to an output node.

2. The system of claim 1, wherein the means for identifying the first input comprises means for extracting the first input from a packaged request.

3. The system of claim 2, wherein the encapsulated request comprises a SOAP request.

4. The system of claim 1, wherein

The means for receiving the output comprises:

means for receiving work elements including outputs from said computation graph, and

means for identifying a request identifier associated with said work element, an

The means for providing the service response including the output from the subgraph comprises:

means for generating a service response corresponding to the service request identified by the request identifier, wherein the service response comprises the output included in the work element.

5. The system of claim 4, wherein generating the service response comprises: embedding the output in the encapsulated response.

6. The system of claim 5, wherein the encapsulated response comprises a SOAP response.

7. The system of claim 1, further comprising:

means for receiving a second input for the computation graph from a second service client,

providing the second input to the means for computing a graph as a record of a second data flow, wherein the record of the second data flow includes a plurality of work elements,

means for receiving a second output from said sub-graph of said computation graph, an

Means for providing said second output to said second service client; and

means for processing the first input and the second input in parallel in the computational graph.

8. The system of claim 7, wherein the means for processing the first input and the second input in parallel comprises:

means for identifying a first sub-graph applicable to the first input,

means for processing the first input in the first sub-graph,

means for identifying a second sub-graph applicable to the second input,

means for processing the second input in the second sub-graph,

means for receiving a first output from said first sub-graph, an

Means for receiving a second output from the second sub-graph,

wherein the first sub-graph and the second sub-graph are executed simultaneously.

9. The system of claim 7, wherein the means for processing the first input and the second input in parallel comprises:

the first instance of the sub-graph is identified as a usable device,

means for processing the first input in a first instance of the subgraph,

identifying a second instance of the subgraph as a usable device,

means for processing the second input in a second instance of the subgraph,

means for receiving a first output from said first instance, an

Means for receiving a second output from the second instance,

wherein the first instance of the subgraph and the second instance of the subgraph are executed concurrently.

10. A system for processing a service request according to a computational graph associated with a service, the computational graph comprising nodes connected by links representing recorded data flows passing between the nodes, the system comprising:

a computer system configured to process a service request according to a computational graph associated with the service, the computational graph comprising nodes connected by links representing recorded data flows passing between the nodes, by:

receiving a first input for the computation graph from a service client,

providing the first input arranged as a record of a data flow to the computational graph, wherein the record of the data flow includes a plurality of work elements,

dividing the plurality of work elements into a plurality of groups based on a type of action performed on the work elements in a given group,

providing each group to a different subgraph of the computational graph, each subgraph comprising at least some components of the computational graph and the links,

dividing each of one or more of the plurality of groups into a plurality of subgroups of the plurality of working elements,

assigning each subgroup of a given group to a different instance of the subgraph assigned to the given group, each instance comprising the components and the links of the subgraph,

receiving an output from the subgraph of the computational graph, an

Providing a service response including the output from the subgraph.

11. The system of claim 10, wherein

The computer system is configured to receive the first input, including the computer system being configured to identify the first input in a service request from the service client, an

The computer system configured to provide the first input to the computational graph includes the computer system configured to:

associating a request identifier with the service request,

providing a work element including the first input to the computational graph,

associating the request identifier with the work element, an

Transmitting an association of the request identifier and the work element to an output node.

12. The system of claim 11, wherein the computer system being configured to identify the first input comprises the computer system being configured to extract the first input from the packaged request.

13. The system of claim 12, wherein the encapsulated request comprises a SOAP request.

14. The system of claim 10, wherein

The computer system configured to receive the output, including the computer system configured to:

receiving a work element including an output from the computation graph, an

Identifying a request identifier associated with the work element, an

The computer system configured to provide a service response including the output from the subgraph, including the computer system configured to:

generating a service response corresponding to the service request identified by the request identifier, the service response including the output included in the work element.

15. The system of claim 14, wherein the computer system being configured to generate the service response comprises the computer system being configured to embed the output in the encapsulated response.

16. The system of claim 15, wherein the encapsulated response comprises a SOAP response.

17. The system of claim 10, further comprising the computer system configured to:

processing a second service request according to the computation graph, wherein the steps comprise:

receiving a second input for the computation graph from a second service client,

providing the second input to the computational graph as a record of a second data flow, wherein the record of the second data flow includes a plurality of work elements,

receiving a second output from said sub-graph of said computational graph, an

Providing the second output to the second service client; and

in the computational graph, the first input and the second input are processed in parallel.

18. The system of claim 17, wherein the computer system being configured to process the first input and the second input in parallel comprises the computer system being configured to:

identifying a first sub-graph applicable to the first input,

processing the first input in the first sub-graph,

identifying a second sub-graph applicable to the second input,

processing the second input in the second sub-graph,

receiving a first output from the first sub-graph, an

Receiving a second output from the second sub-graph,

wherein the first sub-graph and the second sub-graph are executed simultaneously.

19. The system of claim 17, wherein the computer system being configured to process the first input and the second input in parallel comprises the computer system being configured to:

a first instance of the sub-graph is identified as available,

processing the first input in a first instance of the subgraph,

identifying a second instance of the subgraph as available,

processing the second input in a second instance of the subgraph,

receiving a first output from the first instance, an

Receiving a second output from the second instance,

wherein the first instance of the subgraph and the second instance of the subgraph are executed concurrently.

20. The system of claim 10, wherein the computational graph comprises a first graph, a first subgraph of the first graph, and a second subgraph of the first graph, and the step of the computer system being configured to provide the first input to the computational graph as a plurality of work elements of a data stream comprises the computer being configured to:

identifying a first graph applicable to a first record in the data stream,

identifying a first sub-graph applicable to a first working element in the first record,

processing the first working element in the first sub-graph,

identifying a second sub-graph that applies to a second working element in the first record,

processing the second working element in the second sub-graph,

receiving a first output work element from the first sub-graph,

receiving a second output work element from the second sub-graph,

associating the first output work element with the first record, an

Associating the second output work element with the first record,

wherein the first sub-graph and the second sub-graph are executed at least partially simultaneously.

21. The system of claim 10, wherein the computational graph comprises a first graph, a first instance of one subgraph of the first graph, and a second instance of the subgraph of the first graph, and the step of the computer system being configured to provide the first input to the computational graph as a plurality of work elements of a data stream comprises the computer system being configured to:

identifying a first graph applicable to a first record in the data stream,

a first instance of the sub-graph is identified as available,

processing a first work element in the first record in a first instance of the subgraph,

identifying a second instance of the subgraph as available,

processing a second working element in the first record in a 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, an

Associating the second output work element with the first record,

wherein the first instance of the subgraph and the second instance of the subgraph are executed at least partially concurrently.