Determining operator partitioning constraint feasibility

摘要

Techniques for determining feasibility of a set of one or more operator partitioning constraints are provided. The techniques include receiving one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function, processing each set of one or more operator partitioning constraints to determine feasibility of each set of one or more operator partitioning constraints, creating and outputting one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints, and creating and outputting a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility.

主权项

1. A method for determining feasibility of a set of one or more operator partitioning constraints, wherein the method comprises:
receiving one or more sets of operator partitioning constraints, wherein each set of one or more constraints define one or more desired conditions for grouping together of operators into partitions and placing partitions on hosts, wherein each operator is embodied as software that performs a particular function, and wherein said receiving is carried out on a distinct software module executing on a hardware processor; processing each set of one or more operator partitioning constraints to determine (i) a feasible partitioning of operators into a fusion of operators and (ii) an assignment of the fusion of operators to a host, such that all operator partitioning constraints are satisfied, wherein said processing is carried out on a distinct software module executing on a hardware processor; creating and outputting one or more candidate partitions and one or more host placements for each set of feasible partitioning constraints, wherein said creating and outputting one or more candidate partitions is carried out on a distinct software module executing on a hardware processor; and creating and outputting a certificate of infeasibility for each set of infeasible partitioning constraints, wherein the certificate of infeasibility outlines one or more reasons for infeasibility, wherein said creating and outputting a certificate is carried out on a distinct software module executing on a hardware processor, and wherein said outlining comprises:
identifying each operator and constraint causing infeasibility arising from at least one of partition co-location, partition ex-location, partition isolation and host ex-location constraint;identifying each operator and constraint causing infeasibility arising from at least one of host co-location, resource matching, host ex-location and host isolation; andidentifying a Hall set arising from infeasibility of a bipartite matching problem arising from at least one of host isolation, host ex-location and resource matching constraint.