[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317844476 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/OptimalAssignment.java ## @@ -0,0 +1,83 @@ +package org.apache.helix.controller.rebalancer.waged.model; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.model.ResourceAssignment; + +/** + * The data model represents the optimal assignment of N replicas assigned to M instances; + * It's mostly used as the return parameter of an assignment calculation algorithm; If the algorithm + * failed to find + * optimal assignment given the endeavor, the user could check the failure reasons + */ +public class OptimalAssignment { + private Map> _optimalAssignment = new HashMap<>(); + private Map>> _failedAssignments = + new HashMap<>(); + private final ClusterContext _clusterContext; + + public OptimalAssignment(ClusterContext clusterContext) { +_clusterContext = clusterContext; + } + + public ClusterContext getClusterContext() { +return _clusterContext; + } + + public Map getOptimalResourceAssignment() { +// TODO: convert the optimal assignment to map +return Collections.emptyMap(); + } + + public void trackAssignmentFailure(AssignableReplica replica, + Map> failedAssignments) { +_failedAssignments.put(replica, failedAssignments); + } + + public boolean hasAnyFailure() { +return !_failedAssignments.isEmpty(); + } + + public String getFailures() { +// TODO: format the error string +return _failedAssignments.toString(); + } + + public void addAssignment(AssignableReplica replica, AssignableNode node) { Review comment: @jiajunwang @i3wangyi What was the reason for adding assignment info to ClusterModel in the first place? I feel that we should have just one source of truth for the assignment result. What about ClusterContext? Could we discuss and clearly define the roles of each? (ClusterModel, ClusterContext, and OptimalAssignment). This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317841334 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all + * "hard constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { + private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); + private final List _hardConstraints; Review comment: Curious, do we want to make these constraints immutable? What if the user wishes to add/remove constraints? Do we then instantiate a new `ConstraintBasedAlgorithm` object? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317843445 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/OptimalAssignment.java ## @@ -0,0 +1,77 @@ +package org.apache.helix.controller.rebalancer.waged.model; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import org.apache.helix.HelixException; +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.model.ResourceAssignment; + +/** + * The data model represents the optimal assignment of N replicas assigned to M instances; + * It's mostly used as the return parameter of an assignment calculation algorithm; If the algorithm + * failed to find optimal assignment given the endeavor, the user could check the failure reasons + */ +public class OptimalAssignment { + private Map> _optimalAssignment = new HashMap<>(); + private Map>> _failedAssignments = + new HashMap<>(); + private final ClusterModel _clusterModel; + + public OptimalAssignment(ClusterModel clusterModel) { +_clusterModel = clusterModel; + } + + public ClusterModel getClusterModel() { +return _clusterModel; + } + + public Map getOptimalResourceAssignment() { +if (hasAnyFailure()) { + throw new HelixException("The rebalance algorithm failed to compute the optimal resource assignment"); +} +// TODO: convert the optimal assignment to map +return Collections.emptyMap(); + } + + public void trackAssignmentFailure(AssignableReplica replica, Review comment: Rename to `recordHardConstraintFailures` to better reflect what it's really doing. This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317843157 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all + * "hard constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { + private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); + private final List _hardConstraints; + private final List _softConstraints; + + public ConstraintBasedAlgorithm(List hardConstraints, + List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; + } + + @Override + public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment optimalAssignment = new OptimalAssignment(clusterModel); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); + +for (String resource : replicasByResource.keySet()) { + for (AssignableReplica replica : replicasByResource.get(resource)) { +Optional maybeBestNode = +getNodeWithHighestPoints(replica, nodes, optimalAssignment); +// stop immediately if any replica cannot find best assignable node +if (optimalAssignment.hasAnyFailure()) { + LOG.error( + "Unable to find any available candidate node for partition {}; Fail reasons: {}", + replica.getPartitionName(), optimalAssignment.getFailures()); + return optimalAssignment; +} +maybeBestNode.ifPresent(node -> { + optimalAssignment.addAssignment(replica, node); + clusterModel.assign(replica.getResourceName(), replica.getPartitionName(), + replica.getReplicaState(), node.getInstanceName()); +}); + } +} + +return optimalAssignment; + } + + private Optional getNodeWithHighestPoints(AssignableReplica replica, + List assignableNodes, OptimalAssignment optimalAssignment) { +Map> hardConstraintFailures = new HashMap<>(); +List candidateNodes = assignableNodes.stream().filter(candidateNode -> { + boolean isValid = true; + // evaluate all hard constraints and record all the failure reasons why one assignment fails + for (HardConstraint hardConstraint : _hardConstraints) { +if (!hardConstraint.isAssignmentValid(candidateNode, replica, optimalAssignment.getClusterModel().getContext())) { + hardConstraintFailures.computeIfAbsent(candidateNode, node -> new ArrayList<>()) + .add(hardConstraint); + isValid = false; +} + } + return isValid; +}).collect(Collectors.toList()); +if
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317841689 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all + * "hard constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { + private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); + private final List _hardConstraints; + private final List _softConstraints; + + public ConstraintBasedAlgorithm(List hardConstraints, + List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; + } + + @Override + public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment optimalAssignment = new OptimalAssignment(clusterModel); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); + +for (String resource : replicasByResource.keySet()) { + for (AssignableReplica replica : replicasByResource.get(resource)) { Review comment: What would the ordering be? Alphabetical order? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317842569 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all + * "hard constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { + private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); + private final List _hardConstraints; + private final List _softConstraints; + + public ConstraintBasedAlgorithm(List hardConstraints, + List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; + } + + @Override + public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment optimalAssignment = new OptimalAssignment(clusterModel); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); + +for (String resource : replicasByResource.keySet()) { + for (AssignableReplica replica : replicasByResource.get(resource)) { +Optional maybeBestNode = +getNodeWithHighestPoints(replica, nodes, optimalAssignment); +// stop immediately if any replica cannot find best assignable node +if (optimalAssignment.hasAnyFailure()) { + LOG.error( + "Unable to find any available candidate node for partition {}; Fail reasons: {}", + replica.getPartitionName(), optimalAssignment.getFailures()); + return optimalAssignment; +} +maybeBestNode.ifPresent(node -> { + optimalAssignment.addAssignment(replica, node); + clusterModel.assign(replica.getResourceName(), replica.getPartitionName(), + replica.getReplicaState(), node.getInstanceName()); +}); + } +} + +return optimalAssignment; + } + + private Optional getNodeWithHighestPoints(AssignableReplica replica, + List assignableNodes, OptimalAssignment optimalAssignment) { +Map> hardConstraintFailures = new HashMap<>(); +List candidateNodes = assignableNodes.stream().filter(candidateNode -> { + boolean isValid = true; + // evaluate all hard constraints and record all the failure reasons why one assignment fails + for (HardConstraint hardConstraint : _hardConstraints) { +if (!hardConstraint.isAssignmentValid(candidateNode, replica, optimalAssignment.getClusterModel().getContext())) { + hardConstraintFailures.computeIfAbsent(candidateNode, node -> new ArrayList<>()) + .add(hardConstraint); + isValid = false; Review comment: +1. Shouldn't we stop early? Is it to record all failure reasons?
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317842418 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all + * "hard constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { + private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); + private final List _hardConstraints; + private final List _softConstraints; + + public ConstraintBasedAlgorithm(List hardConstraints, + List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; + } + + @Override + public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment optimalAssignment = new OptimalAssignment(clusterModel); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); + +for (String resource : replicasByResource.keySet()) { + for (AssignableReplica replica : replicasByResource.get(resource)) { +Optional maybeBestNode = +getNodeWithHighestPoints(replica, nodes, optimalAssignment); +// stop immediately if any replica cannot find best assignable node +if (optimalAssignment.hasAnyFailure()) { + LOG.error( + "Unable to find any available candidate node for partition {}; Fail reasons: {}", + replica.getPartitionName(), optimalAssignment.getFailures()); + return optimalAssignment; +} +maybeBestNode.ifPresent(node -> { + optimalAssignment.addAssignment(replica, node); + clusterModel.assign(replica.getResourceName(), replica.getPartitionName(), + replica.getReplicaState(), node.getInstanceName()); +}); + } +} + Review comment: Nit: space This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r317841049 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,117 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot + * bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better + * assignment + * + * The goal is to accumulate the most points(rewards) from "soft constraints" while avoiding all Review comment: +1. You want to _honor_ all hard constraints. This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314180856 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/ClusterContext.java ## @@ -71,6 +71,10 @@ _estimatedMaxTopStateCount = estimateAvgReplicaCount(totalTopStateReplicas, instanceCount); } + ClusterContext(Map> currentMapping) { + Review comment: extra space? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314181444 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/OptimalAssignment.java ## @@ -0,0 +1,83 @@ +package org.apache.helix.controller.rebalancer.waged.model; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.model.ResourceAssignment; + +import javafx.util.Pair; + +/** + * The data model represents the optimal assignment of N replicas assigned to M instances; + * It's mostly used as the return parameter of an assignment calculation algorithm; If the algorithm + * failed to find + * optimal assignment given the endeavor, the user could check the failure reasons + */ +public class OptimalAssignment { + private Map> _optimalAssignment = new HashMap<>(); + private Map, List> _failedAssignments = new HashMap<>(); + private ClusterContext _clusterContext; + + public OptimalAssignment(ClusterContext clusterContext) { +_clusterContext = clusterContext; + } + + public ClusterContext getClusterContext() { +return _clusterContext; + } + + public Map getOptimalResourcesAssignment() { Review comment: getOptimalResourcesAssignment -> getOptimalResourceAssignment This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314180937 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/ClusterModel.java ## @@ -95,22 +95,22 @@ public ClusterContext getContext() { return _bestPossibleAssignment; } - /** - * Assign the given replica to the specified instance and record the assignment in the cluster model. - * The cluster usage information will be updated accordingly. - * - * @param resourceName - * @param partitionName - * @param state - * @param instanceName - */ - public void assign(String resourceName, String partitionName, String state, String instanceName) { -AssignableNode node = locateAssignableNode(instanceName); -AssignableReplica replica = locateAssignableReplica(resourceName, partitionName, state); - -node.assign(replica); -_clusterContext.addPartitionToFaultZone(node.getFaultZone(), resourceName, partitionName); - } +// /** Review comment: Did you mean to remove this? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314180593 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,109 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterContext; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better assignment + * Review comment: @i3wangyi Oh I was referring to the p? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314180887 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/ClusterContext.java ## @@ -115,4 +124,19 @@ private int estimateAvgReplicaCount(int replicaCount, int instanceCount) { return (int) Math .ceil((float) replicaCount / instanceCount * ERROR_MARGIN_FOR_ESTIMATED_MAX_COUNT); } + + Review comment: extra space This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r314181390 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/model/OptimalAssignment.java ## @@ -0,0 +1,83 @@ +package org.apache.helix.controller.rebalancer.waged.model; + +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.model.ResourceAssignment; + +import javafx.util.Pair; Review comment: Umm... I'm not too sure about importing a JavaFX library. Is it possible to create your own private POJO? I feel like we're trying too hard to shoehorn our use case in here... This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r311729802 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,109 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterContext; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better assignment + * + * The goal is to avoid all "hard constraints" while accumulating the most points(rewards) from "soft constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { +private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); +private final List _hardConstraints; +private final List _softConstraints; + +public ConstraintBasedAlgorithm(List hardConstraints, List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; +} + +@Override +public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment currentAssignment = new OptimalAssignment(); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); +ClusterContext clusterContext = clusterModel.getContext(); + + Review comment: Extra space? This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r311731548 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,109 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterContext; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better assignment + * + * The goal is to avoid all "hard constraints" while accumulating the most points(rewards) from "soft constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { +private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); +private final List _hardConstraints; +private final List _softConstraints; + +public ConstraintBasedAlgorithm(List hardConstraints, List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; +} + +@Override +public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment currentAssignment = new OptimalAssignment(); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); +ClusterContext clusterContext = clusterModel.getContext(); + + +for (String resource : replicasByResource.keySet()) { Review comment: Could you use Map.Entry on replicasByResource here? Performance is better with Map.Entry/entrySet() since you're calling Map.get(K). This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org
[GitHub] [helix] narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm
narendly commented on a change in pull request #381: Implement the POC work greedy constraint based algorithm URL: https://github.com/apache/helix/pull/381#discussion_r311737328 ## File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/algorithm/ConstraintBasedAlgorithm.java ## @@ -0,0 +1,109 @@ +package org.apache.helix.controller.rebalancer.waged.algorithm; + +import org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint; +import org.apache.helix.controller.rebalancer.waged.constraints.SoftConstraint; +import org.apache.helix.controller.rebalancer.waged.model.AssignableNode; +import org.apache.helix.controller.rebalancer.waged.model.AssignableReplica; +import org.apache.helix.controller.rebalancer.waged.model.ClusterContext; +import org.apache.helix.controller.rebalancer.waged.model.ClusterModel; +import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Function; +import java.util.stream.Collectors; + + +/** + * The algorithm is based on a given set of constraints + * - HardConstraint: Approve or deny the assignment given its condition, any assignment cannot bypass any "hard constraint" + * - SoftConstraint: Evaluate the assignment by points/rewards/scores, a higher point means a better assignment + * + * The goal is to avoid all "hard constraints" while accumulating the most points(rewards) from "soft constraints" + */ +public class ConstraintBasedAlgorithm implements RebalanceAlgorithm { +private static final Logger LOG = LoggerFactory.getLogger(ConstraintBasedAlgorithm.class); +private final List _hardConstraints; +private final List _softConstraints; + +public ConstraintBasedAlgorithm(List hardConstraints, List softConstraints) { +_hardConstraints = hardConstraints; +_softConstraints = softConstraints; +} + +@Override +public OptimalAssignment calculate(ClusterModel clusterModel) { +OptimalAssignment currentAssignment = new OptimalAssignment(); +Map> replicasByResource = clusterModel.getAssignableReplicaMap(); +List nodes = new ArrayList<>(clusterModel.getAssignableNodes().values()); +ClusterContext clusterContext = clusterModel.getContext(); + + +for (String resource : replicasByResource.keySet()) { +for (AssignableReplica replica : replicasByResource.get(resource)) { +Optional bestNode = getNodeWithHighestPoints(replica, nodes, clusterContext, currentAssignment); Review comment: I don't see a clear advantage here for using an Optional here. You're working on just one instance of AssignableNode. A simple null check would suffice? If getNodeWithHighestPoints() returned multiple AssignableNodes and if you were doing a batch/streamed operation on those AssignableNodes, then I think using Optional here might make sense. See https://stackoverflow.com/questions/42285448/optional-ofnullablei-ifpresent-vs-if-i-null for more explanation on this. This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services - To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org