Query Deployment Plan For A Distributed Shared Stream Processing System

• US 20090192981A1
• Filed: 10/03/2008
• Published: 07/30/2009
• Est. Priority Date: 01/29/2008
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Papaemmanouil, Olga, Banerjee, Sujata, Basu, Sujoy
• Application Number:
  US12/244,878
• Publication Number:
  US 20090192981A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A method of providing a deployment plan for a query in a distributed shared stream processing system includes storing a set of feasible deployment plans for a query that is currently deployed in the stream processing system. A query includes a plurality of operators hosted on nodes in the stream processing system providing a data stream responsive to a client request for information. The method also includes determining whether a QoS metric constraint for the query is violated, and selecting a deployment plan from the set of feasible deployment plans to be used for providing the query in response to determining the QoS metric constraint is violated.

Claims

1. A method of providing a deployment plan for a query in a distributed shared stream processing system, the method comprising:

storing a set of pre-computed feasible deployment plans for a query that is currently deployed in the stream processing system, wherein a query includes a plurality of operators hosted on nodes in the stream processing system providing a data stream responsive to a client request for information;

determining whether a QoS metric constraint for the query is violated; and

selecting a deployment plan from the set of feasible deployment plans to be used for providing the query in response to determining the QoS metric constraint is violated.

2. The method of claim 1, wherein storing a set of feasible deployment plans comprises:

identifying a plurality of partial deployment plans;

identifying feasible partial deployment plans from the plurality of partial deployment plans based on the QoS metric;

identifying a subset of the feasible partial deployment plans based on availability of computer resources of nodes to run operators for each of the plans;

selecting one or more of the subset of feasible partial deployment plans to optimize a service provider metric; and

storing the selected plans.

3. The method of claim 2, wherein identifying a plurality of partial deployment plans comprises identifying a plurality of partial deployment plans at a leaf node for the query;

and

forwarding the partial deployment plans determined to be feasible downstream to nodes to host operators in the partial deployment plans along with metadata used by the downstream nodes to expand the partial deployment plans with placements of its locally executed operators and to quantify an impact of the placements on the QoS metric.

4. The method of claim 3, wherein identifying a plurality of partial deployment plans at a leaf node for the query comprises performing a k-ahead search to determine an impact on the QoS metric to provide a best placement of k downstream operators.

5. The method of claim 4, wherein the k-ahead search comprises:

for each partial deployment plan, identifying candidate nodes to host an operator in the partial deployment plan;

sending a request to a node hosting a downstream operator asking for a second set of candidate hosts for the downstream operator and an estimate of the QoS metric for the candidates;

evaluating whether the QoS metric constraint is violated for each of the candidate nodes; and

repeating the steps of sending a request and evaluating the QoS metric for subsequent downstream operators to determine partial plans that do not violate the QoS metric constraint.

6. The method of claim 3, wherein identifying a subset of the feasible partial deployment plans comprises:

at each of the downstream nodes, determining whether the node has sufficient available computer resources to host the operator;

estimating the impact of the partial plan based on the QoS metric; and

only propagating partial plans downstream that satisfy the QoS metric constraint.

7. The method of claim 6, wherein selecting one or more of the subset of feasible partial deployment plans to optimize a service provider metric comprises:

maintaining statistics on the service provider metric for all the upstream operators of every local operator; and

selecting one or more of the subset of feasible partial deployment plans to store based on the statistics.

8. The method of claim 1, wherein determining whether a QoS metric constraint for the query is violated comprises:

each node in the query monitoring the QoS metric for its operator to the location of its publisher;

each node determining whether the QoS metric constraint is violated based on the monitoring of the QoS metric.

9. The method of claim 8, wherein each node determining whether the QoS metric constraint is violated comprises:

for each node, determining the QoS metric for all queries sharing the operator hosted on the node;

determining whether a tolerance for the QoS metric is violated for any of the queries.

10. The method of claim 1, wherein selecting a deployment plan from the set of feasible deployment plans to be used for providing the service in response to determining the QoS metric constraint is violated comprises:

selecting one or more deployment plans from the set of deployment plans that at least improves the QoS metric such that the QoS metric constraint is not violated;

from the one or more deployment plans, removing any deployment plans that do not migrate at least one operator in a bottleneck link; and

selecting one of the one or more deployments plans not removed based on a service provider metric.

11. The method of claim 10, wherein selecting one or more deployment plans comprises selecting one or more deployment plans from a set of feasible deployment plans stored on a node hosting an operator in the query that detects the QoS metric constraint violation, and if the node cannot identify one or more of deployment plans from the set of feasible deployment plans that improves the QoS metric such that the QoS metric constraint is not violated, the node sends a request to downstream nodes to identify a deployment plan that improves the QoS metric such that the QoS metric constraint is not violated.

12. A method of resolving conflicts to deploy a deployment plan for a query in a distributed stream processing system, the method comprising:

determining a new deployment plan for an existing query should be applied;

for each operator in the new deployment plan, locking the operator unless the operator is already locked;

if the operator is already locked, determining whether a conflict exists;

if a conflict exists, identifying an alternative deployment plan;

if a conflict does not exist, replicating the operator and deploying the new deployment plan.

13. The method of claim 12, wherein locking an operator comprises:

a node determining to apply the new deployment plan sending a request to lock to its publishers and subscribers for the query; and

each node receiving the request sends the request to subscribers of its operator for the query.

14. The method of claim 13, wherein nodes receiving the request, lock a local operator for the query if the operator is not already locked, wherein locking the operator prevents the node from allowing another migration of the locked operator until the lock is released.

15. The method of claim 12, wherein a conflict is operable to exist if the query has direct or indirect dependencies with another query, wherein the direct dependency is based on whether the query and the another query share an operator and the indirect dependency is when no operator is shared by the query and the another query, but there exists a third query with which both the query and the another query share an operator.

16. A computer readable storage medium storing software including instructions that when executed perform a method comprising:

creating partial deployment plans for a query currently deployed in an overlay network providing end-to-end overlay paths for data streams in a distributed stream processing system;

storing statistics on bandwidth consumed by an upstream operator of a local operator for the query;

storing statistics on query latency up to the local operator;

for each partial deployment plan, evaluating differences between the bandwidth consumed and latency for the partial deployment plan versus the currently deployed query; and

for each partial deployment plan, storing the partial deployment plan and metadata for subsequent evaluation of the partial deployment plan if the evaluated differences indicate that the partial deployment plan is better than the deployed query and the partial deployment plan satisfies a QoS metric constraint.

17. The computer readable medium of claim 16, wherein the query comprises a plurality of operators hosted by nodes in the overlay network and each of the nodes creates, evaluates and stores partial deployment plans that together form a plurality of pre-computed deployment plans for the query.

18. The computer readable medium of claim 17, wherein the method comprises:

determining whether the query latency is greater than a threshold; and

selecting one of the pre-computed deployment plans to deploy in the overlay network.

19. The computer readable medium of claim 18, wherein the selected pre-computed deployment plan includes migration of an operator for the query to a new node in the overlay network.

20. The computer readable medium of claim 19, wherein the method comprises:

prior to migrating the operator to a new node, determining whether the new node has sufficient available computer resource capacity to support a load of the operator based on estimated load of the operator and current load of the new node hosting operators for other queries.