Systems, methods and computer program products for improving placement performance of message transforms by exploiting guided replication
View Patent ↗Systems, methods and computer program products for optimizing an objective function (e.g. the overall end-to-end runtime latency) of a flow graph of message transformations which are placed onto an overlay network of broker machines by replicating stateless transformations in a guided manner. Exemplary embodiments include a guided replication method, including given an initial transformation graph and a network topology, running a placement algorithm to obtain top N best task-to-broker assignments, identifying the R-task which forms the performance bottleneck, checking if the objective function improvement drops below a designated threshold, if yes, then selecting the optimal task-to-broker assignment and the program terminates; otherwise, replicating the R-task, optimally distributing the data load among R-task's replicas, deriving a set of starting points from the above obtained top N task-to-broker assignments, and re-executing the placement algorithm with these starting points in an iterative fashion.
1. In a computer system having a processor, a method for placing a message transformation graph onto an overlay network of broker machines, to optimize a given objective function, the method consisting of:
receiving in the processor an initial message transformation graph, a network topology, and expected performance properties of the initial message transformation graph and of network nodes and links, and a designation of particular stateless transformations in the transformation graph as being replicable;
running in the processor a placement algorithm without replicating any transformations to determine a set of task-to-broker assignments with respect to the given objective function, including end-to-end latency;
setting a hash map value to empty;
until the objective function improvement drops below a designated threshold, repeat an improvement step in the processor consisting of the following sub-steps:
identifying a replicable transformation which forms the performance bottleneck, and designating the replicable transformation as a sensitive transformation for this step;
augmenting the transformation graph by replicating the sensitive transformation;
finding a best load distribution among the sensitive transformation's replicas such that the load distributions from the previous run of the placement algorithm are feasible solutions for a next run;
deriving a set of starting points from the task-to-broker assignments achieved from a previous run of the placement algorithm;
re-executing the placement algorithm on the augmented graph, starting the search from the above derived starting points to determine a new set of task-to-broker assignments; and
determining a final optimal task-to-broker assignment from the task-to-broker assignments
storing a number of replicas and load distribution information for the replica transformation in the hash map.
2. The method as claimed in claim 1 wherein the best load distribution among the sensitive transformation's replicas is determined based on a calculated normalized coverage capability of each possible data distribution.
3. The method as claimed in claim 1 wherein each of the set of starting points derived from the task-to-broker assignments achieved from a previous run of the placement algorithm is further perturbed by R times, so as to further expand a potential solution space of a next round of placement.
4. The method as claimed in claim 1 wherein the replication of the sensitive transformation involves the replication of children nodes of the sensitive transformation in the transformation graph.
5. The method as claimed in claim 1 wherein the sensitive transformation is replicated in a constrained path replication manner when the sensitive transformation has multiple parent nodes in the transformation graph.