Query Placement Phase

Query Placement Phase is responsible for the placement of query plan on the physical NES topology. We have several placement strategies for the placement of query plan on the NES topology. Each placement strategy is split into two different phases, a Path-Selection Phase and an Operator-Assignment Phase.

  • Path-Selection Phase: is responsible for preparing a topology sub-graph where operators from the query plan are to be placed.
  • Operator-Assignment Phase: is responsible for assigning operators to the physical nodes on the topology sub-graph obtained from the previous phase. The operators are assigned to the physical node only if the resource available on the node is more than the resource required for placing the operator.

Once, both of the phases get completed successfully, the system generated Network Sink/Source operators are added in the intermediate physical nodes to enable the transfer of tuple streams from one physical node to another. We will explain various placement strategies using the following example:

Bottom-Up Strategy

In the Bottom-Up Strategy, we try to place the operators closer to the location where its upstream operator is placed.

We first present how the Path-Selection phase is executed.

  • For each logical source in the query plan, we first find the sub-graph for each physical source connecting the physical source node and the sink node. (See below)

  • We then compute the occurrence matrix for all the nodes from the respective sub-graphs identified for the physical source node for each logical source. (See below)

  • We then prune the sub-graphs for the nodes with multiple parents using following rules:
    • Whenever we encounter more than one parent for a logical node then (a.) We list all the nodes starting from the parent till the sink node and then (b.) We then compute the weight for the parent using the formula W = Sum(occurrence count for the nodes found in (a.))/number of nodes.
    • We select the parent with max(W) and remove the other nodes from the sub-garph.

  • We then merge the pruned sub-graphs of each logical source together.

  • Then we merge together the sub-graphs for different logical sources together.

After the Path-Selection phase the sub-graphs for the placement looks as follow:

The input query graph is already processed using Logical Source Expansion Rule before we run the operator-assignment phase.

The next phase is Operator-Assignment phase which performs assignment of the expanded query graph to the suitable nodes in the topology sub-graph found in the Path-Selection phase.

Following are the steps:

  1. We start from any source operator in the query plan and find the physical node in the topology sub-graph for the assignment (as shown below).
    (Note: all the source and sink operators are also called pinned operators because they have a predefined location for assignment. If the node doesn't have the resources available for the pinned operator assignment then the placement is marked as failed.)
  2. Once the operator is assigned, the following steps are performed for all the parent operators:
    1. If the Operator is not an N-ary or not a Sink operator then:
      1. The operator is assigned to the same node where its child operator is placed if there are enough resources available on the node.
      2. If this is not the case then:
        1. The next physical parent node of the node without resources is located which has enough resources for the placement and the operator is assigned to the node (as shown below) and Step 2 is repeated.
        2. If no physical node is found then the placement is marked for failure.
    2. If the operator is an N-ary operator then:
      1. It is checked if all its child operators are already assigned to a node or not.
      2. If not all children are placed then the Source operator of one of the unassigned children operator is picked and Step 1 is repeated (as shown below).
      3. If all the children are placed then a candidate physical node is selected from which all the assigned child operator's physical nodes can be reached and Step 2.1.1 is repeated (as shown below).
    3. If the operator is a Sink operator then
      1. From the pinned operator location catalog its physical location is identified and the assignment is performed.
      2. If the physical node has no resources then the placement is marked for failure.
  3. Once, all operators are assigned, then the Network source and sink operators are placed appropriately to allow stream data to reach to the query's sink operator. (As shown below, the circles in diferent colors are Network source and Sink operators trnasmitting data from different physical source locations).

Top-Down Strategy

IFCOP Strategy

Infrastructure-aware Fog-Cloud Operator Placement Strategy (IFCOP) is a cost-based operator placement strategy for NebulaStream. IFCOP aims to minimize the processing-time latency of query execution. To achieve that, IFCOP optimizes the operator placement by iteratively generating candidates and evaluating them with a cost function. At the end of the iteration, IFCOP returns the candidate having the lowest cost.

Candidate Representation

IFCOP uses a 2D binary matrix to represent an operator placement candidate. The matrix has a size of number of nodes number of operators. Following is an example of a candidate:

Each row in the matrix represents a placement decision in a topology node. By having 1 in a cell (i,j) we decide to place the operator j to the node i. For example, in cell (5,6) we set the decision to 1 to indicate that we place the filter operator in Node 6.

Candidate Generation

To generate a candidate, IFCOP iterates through source operators in the query plan and performs placement for one source at a time. Following are the steps to place the operators:

  1. The placement starts by selecting a source node in the topology to place the current source operator. IFCOP chooses the last source node which does not have the source operator for the current operator.
  2. After that, IFCOP draw a random binary decision whether to place the next operator in the query plan in the current topology node. If that is the case, IFCOP places the parent of the current operator in the current topology node. Otherwise, IFCOP moves the topology iterator to the parent of the current topology node.
  3. In the next topology node, IFCOP repeats the random drawing of the decision on whether to place an operator in the current topology node, and succeeding steps (step 2-3).
  4. Once the topology iterator reaches the sink node, IFCOP checks if the operator iterator is a sink node. If that is not the case, IFCOP places all remaining operators in the sink node. Otherwise, IFCOP places the sink operator in the sink node.

IFCOP repeats these steps for all source operators in the query to place the all operators in the query plan.

Cost Function

IFCOP uses a cost function to select the best candidate that can minimize processing-time latency. The cost function of IFCOP consists of network cost and node over-utilization cost.

  1. Network Cost

The network cost defines the relative amount of data transferred over the topology as a result of applying an operator placement. To compute the overall cost, we need to compute a local cost of a node and take into account the child cost of that node.

  1. Node Over-utilization cost

The node overutilization defines the excess number of operators placed in a topology node with regards to its capacity. We compute the node over-utilization cost as follows:

overutilization cost = (min(0, node.capacity - node.load))

  1. Total Cost

The total cost is computed as a weight sum of network cost and node over-utilization cost.

Costtotal = w1 * network cost + w2 * overutilization cost

Optimization

To select the best operator placement candidate, IFCOP performs a fixed number of iterations. In each iteration, IFCOP generates an operator placement candidate and then checks its cost. If the cost is less then the current best candidate, IFCOP update the best candidate with the current candidate. At the end of the iteration, IFCOP returns the latest value of the best operator placement candidate.

 
query_placement.txt · Last modified: 2021/07/29 10:32 by 134.96.191.189
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki