You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@helix.apache.org by ji...@apache.org on 2019/10/07 21:12:12 UTC
[helix] 09/37: Redefine the hard/soft constraints (#422)
This is an automated email from the ASF dual-hosted git repository.
jiajunwang pushed a commit to branch wagedRebalancer2
in repository https://gitbox.apache.org/repos/asf/helix.git
commit ae282a88b90274c414bff95c55eeb1232c7b484e
Author: Yi Wang <i3...@gmail.com>
AuthorDate: Mon Aug 26 12:27:42 2019 -0700
Redefine the hard/soft constraints (#422)
* Refactor the interfaces of hard/soft constraints and a central place to keep the softConstraint weights
---
.../rebalancer/waged/RebalanceAlgorithm.java | 45 ------------------
.../constraints/ConstraintsRebalanceAlgorithm.java | 49 --------------------
.../waged/constraints/HardConstraint.java | 23 ++++-----
.../constraints/LeastPartitionCountConstraint.java | 53 +++++++++++++++++++++
.../waged/constraints/SoftConstraint.java | 54 +++++++++++++++++-----
.../constraints/SoftConstraintWeightModel.java | 54 ++++++++++++++++++++++
6 files changed, 159 insertions(+), 119 deletions(-)
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/RebalanceAlgorithm.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/RebalanceAlgorithm.java
deleted file mode 100644
index d4221a1..0000000
--- a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/RebalanceAlgorithm.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package org.apache.helix.controller.rebalancer.waged;
-
-/*
- * 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 org.apache.helix.controller.rebalancer.waged.constraints.HardConstraint;
-import org.apache.helix.controller.rebalancer.waged.model.ClusterModel;
-import org.apache.helix.model.ResourceAssignment;
-
-import java.util.Map;
-
-/**
- * A generic rebalance algorithm interface for the WAGED rebalancer.
- *
- * @see <a href="Rebalance Algorithm">https://github.com/apache/helix/wiki/Design-Proposal---Weight-Aware-Globally-Even-Distribute-Rebalancer#rebalance-algorithm-adapter</a>
- */
-public interface RebalanceAlgorithm {
-
- /**
- * Rebalance the Helix resource partitions based on the input cluster model.
- *
- * @param clusterModel
- * @param failureReasons Return the failures <ResourceName, <FailureReason, Count>> that happen during the rebalance calculation.
- * If the map is null, no failure will be returned.
- * @return A map of <ResourceName, ResourceAssignment>.
- */
- Map<String, ResourceAssignment> rebalance(ClusterModel clusterModel,
- Map<String, Map<HardConstraint.FailureReason, Integer>> failureReasons);
-}
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintsRebalanceAlgorithm.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintsRebalanceAlgorithm.java
deleted file mode 100644
index 286fd07..0000000
--- a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintsRebalanceAlgorithm.java
+++ /dev/null
@@ -1,49 +0,0 @@
-package org.apache.helix.controller.rebalancer.waged.constraints;
-
-/*
- * 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 org.apache.helix.controller.rebalancer.waged.RebalanceAlgorithm;
-import org.apache.helix.controller.rebalancer.waged.model.ClusterModel;
-import org.apache.helix.model.ResourceAssignment;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.HashMap;
-import java.util.Map;
-
-/**
- * A placeholder before we have the implementation.
- * The constraint-based rebalance algorithm that is used in the WAGED rebalancer.
- */
-public class ConstraintsRebalanceAlgorithm implements RebalanceAlgorithm {
- private static final Logger LOG = LoggerFactory.getLogger(ConstraintsRebalanceAlgorithm.class);
-
- private Map<HardConstraint.FailureReason, Integer> _failureReasonCounterMap = new HashMap<>();
-
- public ConstraintsRebalanceAlgorithm() {
- // TODO Constraints initialization
- }
-
- @Override
- public Map<String, ResourceAssignment> rebalance(ClusterModel clusterModel,
- Map<String, Map<HardConstraint.FailureReason, Integer>> failureReasons) {
- return new HashMap<>();
- }
-}
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/HardConstraint.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/HardConstraint.java
index 3ee57ea..f544d4b 100644
--- a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/HardConstraint.java
+++ b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/HardConstraint.java
@@ -27,24 +27,21 @@ import org.apache.helix.controller.rebalancer.waged.model.ClusterContext;
* Evaluate a partition allocation proposal and return YES or NO based on the cluster context.
* Any proposal fails one or more hard constraints will be rejected.
*/
-public interface HardConstraint {
- enum FailureReason {
- FAULT_ZONES_CONTAIN_SAME_PARTITION,
- NODES_DEACTIVATED,
- NODES_NO_TAG,
- NODES_EXCEED_MAX_PARTITION,
- NODES_INSUFFICIENT_RESOURCE,
- NODES_CONTAIN_SAME_PARTITION,
- }
+abstract class HardConstraint {
/**
- * @return True if the proposed assignment is valid.
+ * Check if the replica could be assigned to the node
+ * @return True if the proposed assignment is valid; False otherwise
*/
- boolean isAssignmentValid(AssignableNode node, AssignableReplica rep,
+ abstract boolean isAssignmentValid(AssignableNode node, AssignableReplica replica,
ClusterContext clusterContext);
/**
- * @return Detail of the reason that the proposed assignment was rejected.
+ * Return class name by default as description if it's explanatory enough, child class could override
+ * the method and add more detailed descriptions
+ * @return The detailed description of hard constraint
*/
- FailureReason getFailureReason();
+ String getDescription() {
+ return getClass().getName();
+ }
}
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/LeastPartitionCountConstraint.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/LeastPartitionCountConstraint.java
new file mode 100644
index 0000000..a8d36db
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/LeastPartitionCountConstraint.java
@@ -0,0 +1,53 @@
+package org.apache.helix.controller.rebalancer.waged.constraints;
+
+/*
+ * 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 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;
+
+/**
+ * Evaluate the proposed assignment according to the instance's partition count.
+ */
+class LeastPartitionCountConstraint extends SoftConstraint {
+ static LeastPartitionCountConstraint INSTANCE = new LeastPartitionCountConstraint();
+
+ private LeastPartitionCountConstraint() {
+ }
+
+ /**
+ * Returns a score depending on the number of assignments on this node. The score is scaled evenly
+ * between the minScore and maxScore.
+ * When the node is idle, return with the maxScore.
+ * When the node usage reaches the estimated max partition, return with (minScore + maxScore ) /
+ * 2.
+ * When the node usage reaches 2 * estimated_max or more, return with the minScore.
+ * If the estimated max partition count is not set, it defaults to Integer.MAX_VALUE in
+ * clusterContext.
+ */
+ @Override
+ float getAssignmentOriginScore(AssignableNode node, AssignableReplica replica,
+ ClusterContext clusterContext) {
+ throw new UnsupportedOperationException("The POC implementation has a bug, will fix it as TODO");
+// float doubleMaxPartitionCount = 2.0f * clusterContext.getEstimatedMaxPartitionCount();
+// int curPartitionCount = node.getCurrentAssignmentCount();
+// return Math.max((doubleMaxPartitionCount - curPartitionCount) / doubleMaxPartitionCount, 0);
+ }
+}
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraint.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraint.java
index bce4a5a..db145fe 100644
--- a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraint.java
+++ b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraint.java
@@ -27,23 +27,53 @@ import org.apache.helix.controller.rebalancer.waged.model.ClusterContext;
* Evaluate a partition allocation proposal and return a score within the normalized range.
* A higher score means the proposal is more preferred.
*/
-public interface SoftConstraint {
- float MIN_SCORE = -1000.0f;
- float MAX_SCORE = 1000.0f;
+abstract class SoftConstraint {
+ private float _maxScore = 1000f;
+ private float _minScore = -1000f;
+
+ interface ScalerFunction {
+ /**
+ * Scale the origin score to a normalized range (0, 1).
+ * The purpose is to compare scores between different soft constraints.
+ * @param originScore The origin score
+ * @return The normalized value between (0, 1)
+ */
+ float scale(float originScore);
+ }
/**
- * The scoring function returns a score between MINIMAL_SCORE and MAXIMUM_SCORE, which is then weighted by the
- * individual normalized constraint weights.
- * Each individual constraint will define the meaning of MINIMAL_SCORE to MAXIMUM_SCORE differently.
+ * Default constructor, uses default min/max scores
+ */
+ SoftConstraint() {
+ }
+
+ /**
+ * Child class customize the min/max score on its own
+ * @param maxScore The max score
+ * @param minScore The min score
*/
- float assignmentScore(AssignableNode node, AssignableReplica rep, ClusterContext clusterContext);
+ SoftConstraint(float maxScore, float minScore) {
+ _maxScore = maxScore;
+ _minScore = minScore;
+ }
/**
- * Set the importance factor of the soft constraint.
- * The more important it is, the more contribution it will make to the final evaluation.
- * @param importance
+ * The scoring function returns a score between MINIMAL_SCORE and MAXIMUM_SCORE, which is then
+ * weighted by the
+ * individual normalized constraint weights.
+ * Each individual constraint will define the meaning of MINIMAL_SCORE to MAXIMUM_SCORE
+ * differently.
+ * @return float value representing the score
*/
- void setConstraintImportance(float importance);
+ abstract float getAssignmentOriginScore(AssignableNode node, AssignableReplica replica,
+ ClusterContext clusterContext);
- float getConstraintImportance();
+ /**
+ * The default scaler function that squashes any score within (min_score, max_score) to (0, 1);
+ * Child class could override the method and customize the method on its own
+ * @return The MinMaxScaler instance by default
+ */
+ ScalerFunction getScalerFunction() {
+ return (score) -> (score - _minScore) / (_maxScore - _minScore);
+ }
}
diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraintWeightModel.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraintWeightModel.java
new file mode 100644
index 0000000..10201ce
--- /dev/null
+++ b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/SoftConstraintWeightModel.java
@@ -0,0 +1,54 @@
+package org.apache.helix.controller.rebalancer.waged.constraints;
+
+/*
+ * 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.Map;
+
+import com.google.common.collect.ImmutableMap;
+
+/**
+ * The class retrieves the offline model that defines the relative importance of soft constraints.
+ */
+class SoftConstraintWeightModel {
+ private static Map<? extends SoftConstraint, Float> MODEL;
+
+ static {
+ // TODO either define the weights in property files or zookeeper node or static human input
+ MODEL = ImmutableMap.<SoftConstraint, Float> builder()
+ .put(LeastPartitionCountConstraint.INSTANCE, 1.0f).build();
+ }
+
+ /**
+ * Get the sum of normalized scores, given calculated scores map of soft constraints
+ * @param originScoresMap The origin scores by soft constraints
+ * @return The sum of soft constraints scores
+ */
+ float getSumOfScores(Map<SoftConstraint, Float> originScoresMap) {
+ float sum = 0;
+ for (Map.Entry<SoftConstraint, Float> softConstraintScoreEntry : originScoresMap.entrySet()) {
+ SoftConstraint softConstraint = softConstraintScoreEntry.getKey();
+ float score = softConstraint.getScalerFunction().scale(softConstraintScoreEntry.getValue());
+ float weight = MODEL.get(softConstraint);
+ sum += score * weight;
+ }
+
+ return sum;
+ }
+}