Cyclic Dependency in the Activity cluster

[abhishek gupta]

Hi

I have two queries regarding the replicate Operator.

In order to achieve some optimization the we added the Replicate Operator to DAG, because of which the following structure have came up in the DAG. :

The shape contains the replicate operator at the bottom. So the output of the replicate operator is passed to two output branches and the again given as the input of the join operation.  After debug found the cyclic dependency in the Activity cluster. ( Please find the CC log and Activitycluster  and physical plan file in Attachment)

1. We have very less information about how internally the activity graph is generated. Can any one please confirm that is such kind of DAG may lead to a cyclic dependency in the activity cluster Or there is some problem at our end.

                          InnerJoin
                           ^        ^

                           /         |
                          /          |
                         /           |
                        /            |
                       /             |

                Group By      |
                    ^               |
                      \              |
                        \            |
                          \          |
                            \        |
                              \      |

                                \    |

                                 Replicate

        

2. As use of replicate operator in pipelined manner might lead to deadlock.
           Is the replicate designed such that it will not lead to dead lock. ?

Thanks and Regards

[abhishek gupta]

Hello All,

After a bit of debugging I found following subgraph in Job Activity Graph. (Please see the attached pdf for diagram)
.
1 .One output of the Replicate activity is passed to the probe activity of hash join and another is passed to  PreClusteredGroupBy.
2. The output of the PreClusteredGroupBy is then passed to the build activity of the hash join.
3. There is one blocking edge between the probe and build activity.

When the Hyracks start grouping activities into activity clusters ( inferActivityCluster method in ActivityClusterGraphBuilder.java) . It puts all these activity in the same Activity cluster. Which further generate the cyclic dependency.

Please  suggest how can I resolve this problem.

Apart from that I have few more questions.

1. Does a pipeline connector start spilling in case of overflow?
2. How can I figure out how much buffer is allocated to for each connector ?
3. If I choose the connector policy "pipelining". It might lead to a deadlock in case of M:N partitioning connector with limited buffer size. ( Pipelining in Multi query optimization, Nilesh et al.)  How does hyracks ensure that deadlock does not occur ?
4. How does data is propagated in blocking edge?


Thanks & Ragards
Abhishek

[abhishek gupta]

Hi

   In order to fix this issue we made some modification so that the  probe activity was pushed in different activity cluster.  In the resulting graph a one activity cluster had Split, PreClusteredGroupBy, Build activities and another activity cluster had probe activity.  There was one blocking dependency between the build and probe activity and one inter activity cluster edge from split to probe activity.

java.lang.

IllegalStateException: Connected Activities belong to different Activity Clusters: ANID:ODID:10:0 and ANID:ODID:12:1

    at edu.uci.ics.hyracks.api.job.ActivityCluster.connect(ActivityCluster.java:101)
    at edu.uci.ics.hyracks.api.client.impl.ActivityClusterGraphBuilder.inferActivityClusters(ActivityClusterGraphBuilder.java:243)
    at edu.uci.ics.hyracks.api.client.impl.JobSpecificationActivityClusterGraphGeneratorFactory.createActivityClusterGraphGenerator(JobSpecificationActivityClusterGraphGeneratorFactory.java:65)
    at edu.uci.ics.hyracks.control.cc.work.JobStartWork.doRun(JobStartWork.java:57)
    at edu.uci.ics.hyracks.control.common.work.SynchronizableWork.run(SynchronizableWork.java:32)
    at edu.uci.ics.hyracks.control.common.work.WorkQueue$WorkerThread.run(WorkQueue.java:115)

 I realized that Hyracks does not allow the connecting edges between the two ActivityClusters. So how can I transfer the data between two Activity Clusters ?.

Thanks
Abhishek

[Vinayak Borkar]

Hi Abhishek,


It is illegal to build a Hyracks job where an activity cluster contains
two activities that are connected by a blocking edge. An activity
cluster is constructed by performing a transitive closure of activities
connected by dataflow edges. As you have seen in your case, this leads
to a deadlock.

Going back to your original example, let's see what it means for the
replicate operator to feed the groupby on one side and the probe of the
join on the other. Physically it means that the replicate operator will
need to produce data for the groupby so that the join can do the build.
But while the build is in progress, the probe cannot start and so the
other side of the replicate operator is not willing to accept any data.
So clearly the replicate operator (that uses finite buffers to send data
to its two receivers) will block and not make any progress.

The correct way out of your dilemma is to implement a new replicate
operator that is made up of three activities.

-----> activity0 - - - > activity1 ----->
|
|_ _ _ _ _ _> activity2 ----->

activty0 would read in all the data and materialize it to a file.
activities 1 and 2 would then read the materialized data and provide it
to the upstream consumers.

Another slightly optimized way to build a similar replicate operator is
with two activities:

-------> activity0 ------->
|
| _ _ _ _ > activity1 -------->

Here activity0 reads in data from the producer, materializes it to a
file and forwards it to the first consumer. Then activity1 that has a
blocking edge from activity0 reads the materialized data and forwards it
to the second consumer. This is slightly more optimal because the first
consumer does not have to wait for all the data to be first materialized
like it would have to in the previous way of building the replicated
operator.

Please let me know if you have any other questions.

> * InnerJoin
> ^ ^*
> *

> / |
> / |
> / |
> / |
> / |

> *
> * Group By |
> ^ |
> \ |
> \ |
> \ |
> \ |
> \ |
> *
> * \ |
> *
> * Replicate*

>
>
>
>
> 2. As use of replicate operator in pipelined manner might lead
> to deadlock.
> Is the replicate designed such that it will not lead
> to dead lock. ?
>
>
> Thanks and Regards

> Abhishek Gupta
>
> --
> You received this message because you are subscribed to the Google
> Groups "hyracks-users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to hyracks-user...@googlegroups.com
> <mailto:hyracks-user...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

[abhishek gupta]

Hi Vinayak,

Thanks for Reply !

We had figured out that the blocking edge can not be inside a Activity Cluster. In order to fix that we modified the  algorithm which groups the activities in the activity clusters. Our new algorithm forces the split, and build activity in one activity cluster and the probe in other activity cluster. But because this generates a dataflow edge between two activity clusters which is illegal in the Hyracks, this approach was failed.

(AC1)         (AC1)                 (AC2)

split---------> build - - - - - - - -probe
   |                                        |
   |----------------------------------------|

     (dataflow between two AC)

AC1 - activity cluster 1

AC2 - activity cluster 2

So my question " Is there any way by which I can tell hyracks ( to avoid the implementation of new operator )  that materialize on the dataflow edge to a file and which can be read by activity at other side. Or can I replace it by blocking edge and hyracks will handle all the other internals ?

Does hyracks only allows blocking edges between the two activity clusters.?"

If it is not possible then we will implement the new operator.

Apart from that I got few more questions

1. Does a pipeline connector start spilling in case of overflow ?

2. How can I figure out how much buffer is allocated for each connector ?
3. If I choose the connector policy "pipelining" (as hivesterix does in default case). The pipelining policy might lead to a deadlock in case of M:N partitioning connector with limited buffer size. ( Pipelining in Multi query optimization, Nilesh et al.).  How does hyracks ensure that deadlock does not occur in such cases?

Thanks
Abhishek Gupta

an email to hyracks-users+unsubscribe@googlegroups.com

<mailto:hyracks-users+unsub...@googlegroups.com>.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "hyracks-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to hyracks-users+unsubscribe@googlegroups.com.