You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by zh...@apache.org on 2021/11/09 13:28:38 UTC
[hbase] branch branch-2 updated: HBASE-26337 Optimization for
weighted random generators (#3828)
This is an automated email from the ASF dual-hosted git repository.
zhangduo pushed a commit to branch branch-2
in repository https://gitbox.apache.org/repos/asf/hbase.git
The following commit(s) were added to refs/heads/branch-2 by this push:
new cc2e4ae HBASE-26337 Optimization for weighted random generators (#3828)
cc2e4ae is described below
commit cc2e4aec87d449f995ff32176f4242e541ccf01e
Author: clarax <cl...@gmail.com>
AuthorDate: Tue Nov 9 05:27:44 2021 -0800
HBASE-26337 Optimization for weighted random generators (#3828)
Signed-off-by: Duo Zhang <zh...@apache.org>
---
.../hadoop/hbase/master/balancer/CostFunction.java | 10 ++++
.../master/balancer/FavoredStochasticBalancer.java | 8 +++
.../master/balancer/LocalityBasedCostFunction.java | 6 ++-
.../balancer/RegionCountSkewCostFunction.java | 5 ++
.../RegionReplicaGroupingCostFunction.java | 5 ++
.../master/balancer/StochasticLoadBalancer.java | 59 ++++++++++++++++++----
.../hbase/master/balancer/BalancerTestBase.java | 9 ++++
.../balancer/TestStochasticLoadBalancer.java | 4 +-
.../TestStochasticLoadBalancerBalanceCluster.java | 2 +-
...estStochasticLoadBalancerHeterogeneousCost.java | 12 ++++-
.../TestStochasticLoadBalancerLargeCluster.java | 3 +-
11 files changed, 107 insertions(+), 16 deletions(-)
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/CostFunction.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/CostFunction.java
index 2735b69..2164350 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/CostFunction.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/CostFunction.java
@@ -101,4 +101,14 @@ abstract class CostFunction {
return Math.max(0d, Math.min(1d, (value - min) / (max - min)));
}
+
+ /**
+ * Add the cost of this cost function to the weight of the candidate generator that is optimized
+ * for this cost function. By default it is the RandomCandiateGenerator for a cost function.
+ * Called once per init or after postAction.
+ * @param weights the weights for every generator.
+ */
+ public void updateWeight(double[] weights) {
+ weights[StochasticLoadBalancer.GeneratorType.RANDOM.ordinal()] += cost();
+ }
}
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/FavoredStochasticBalancer.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/FavoredStochasticBalancer.java
index fd457ee..2951b7e 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/FavoredStochasticBalancer.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/FavoredStochasticBalancer.java
@@ -86,6 +86,14 @@ public class FavoredStochasticBalancer extends StochasticLoadBalancer implements
return fnPickers;
}
+ /**
+ * @return any candidate generator in random
+ */
+ @Override
+ protected CandidateGenerator getRandomGenerator() {
+ return candidateGenerators.get(ThreadLocalRandom.current().nextInt(candidateGenerators.size()));
+ }
+
@Override
public synchronized void setMasterServices(MasterServices masterServices) {
super.setMasterServices(masterServices);
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/LocalityBasedCostFunction.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/LocalityBasedCostFunction.java
index f7650b3..678c9a3 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/LocalityBasedCostFunction.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/LocalityBasedCostFunction.java
@@ -88,4 +88,8 @@ abstract class LocalityBasedCostFunction extends CostFunction {
return cluster.getOrComputeWeightedLocality(region, entity, type);
}
-}
\ No newline at end of file
+ @Override
+ public final void updateWeight(double[] weights) {
+ weights[StochasticLoadBalancer.GeneratorType.LOCALITY.ordinal()] += cost();
+ }
+}
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionCountSkewCostFunction.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionCountSkewCostFunction.java
index 4e735bc..9f54264 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionCountSkewCostFunction.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionCountSkewCostFunction.java
@@ -60,4 +60,9 @@ class RegionCountSkewCostFunction extends CostFunction {
costs[newServer] = cluster.regionsPerServer[newServer].length;
});
}
+
+ @Override
+ public final void updateWeight(double[] weights) {
+ weights[StochasticLoadBalancer.GeneratorType.LOAD.ordinal()] += cost();
+ }
}
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionReplicaGroupingCostFunction.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionReplicaGroupingCostFunction.java
index 520eb6c..1e72326 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionReplicaGroupingCostFunction.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/RegionReplicaGroupingCostFunction.java
@@ -93,4 +93,9 @@ abstract class RegionReplicaGroupingCostFunction extends CostFunction {
});
return cost.longValue();
}
+
+ @Override
+ public final void updateWeight(double[] weights) {
+ weights[StochasticLoadBalancer.GeneratorType.RACK.ordinal()] += cost();
+ }
}
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/StochasticLoadBalancer.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/StochasticLoadBalancer.java
index cb82673..a69931e 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/StochasticLoadBalancer.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/StochasticLoadBalancer.java
@@ -133,7 +133,12 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
private boolean isBalancerDecisionRecording = false;
private boolean isBalancerRejectionRecording = false;
- private List<CandidateGenerator> candidateGenerators;
+ protected List<CandidateGenerator> candidateGenerators;
+
+ public enum GeneratorType {
+ RANDOM, LOAD, LOCALITY, RACK
+ }
+ private double[] weightsOfGenerators;
private List<CostFunction> costFunctions; // FindBugs: Wants this protected; IS2_INCONSISTENT_SYNC
// To save currently configed sum of multiplier. Defaulted at 1 for cases that carry high cost
private float sumMultiplier;
@@ -213,10 +218,11 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
protected List<CandidateGenerator> createCandidateGenerators() {
List<CandidateGenerator> candidateGenerators = new ArrayList<CandidateGenerator>(4);
- candidateGenerators.add(new RandomCandidateGenerator());
- candidateGenerators.add(new LoadCandidateGenerator());
- candidateGenerators.add(localityCandidateGenerator);
- candidateGenerators.add(new RegionReplicaRackCandidateGenerator());
+ candidateGenerators.add(GeneratorType.RANDOM.ordinal(), new RandomCandidateGenerator());
+ candidateGenerators.add(GeneratorType.LOAD.ordinal(), new LoadCandidateGenerator());
+ candidateGenerators.add(GeneratorType.LOCALITY.ordinal(), localityCandidateGenerator);
+ candidateGenerators.add(GeneratorType.RACK.ordinal(),
+ new RegionReplicaRackCandidateGenerator());
return candidateGenerators;
}
@@ -405,8 +411,33 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
@RestrictedApi(explanation = "Should only be called in tests", link = "",
allowedOnPath = ".*(/src/test/.*|StochasticLoadBalancer).java")
BalanceAction nextAction(BalancerClusterState cluster) {
- return candidateGenerators.get(ThreadLocalRandom.current().nextInt(candidateGenerators.size()))
- .generate(cluster);
+ return getRandomGenerator().generate(cluster);
+ }
+
+ /**
+ * Select the candidate generator to use based on the cost of cost functions. The chance of
+ * selecting a candidate generator is propotional to the share of cost of all cost functions among
+ * all cost functions that benefit from it.
+ */
+ protected CandidateGenerator getRandomGenerator() {
+ double sum = 0;
+ for (int i = 0; i < weightsOfGenerators.length; i++) {
+ sum += weightsOfGenerators[i];
+ weightsOfGenerators[i] = sum;
+ }
+ if (sum == 0) {
+ return candidateGenerators.get(0);
+ }
+ for (int i = 0; i < weightsOfGenerators.length; i++) {
+ weightsOfGenerators[i] /= sum;
+ }
+ double rand = ThreadLocalRandom.current().nextDouble();
+ for (int i = 0; i < weightsOfGenerators.length; i++) {
+ if (rand <= weightsOfGenerators[i]) {
+ return candidateGenerators.get(i);
+ }
+ }
+ return candidateGenerators.get(candidateGenerators.size() - 1);
}
@RestrictedApi(explanation = "Should only be called in tests", link = "",
@@ -511,7 +542,7 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
}
cluster.doAction(action);
- updateCostsWithAction(cluster, action);
+ updateCostsAndWeightsWithAction(cluster, action);
newCost = computeCost(cluster, currentCost);
@@ -527,7 +558,7 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
// TODO: undo by remembering old values
BalanceAction undoAction = action.undoAction();
cluster.doAction(undoAction);
- updateCostsWithAction(cluster, undoAction);
+ updateCostsAndWeightsWithAction(cluster, undoAction);
}
if (EnvironmentEdgeManager.currentTime() - startTime >
@@ -728,17 +759,25 @@ public class StochasticLoadBalancer extends BaseLoadBalancer {
@RestrictedApi(explanation = "Should only be called in tests", link = "",
allowedOnPath = ".*(/src/test/.*|StochasticLoadBalancer).java")
void initCosts(BalancerClusterState cluster) {
+ // Initialize the weights of generator every time
+ weightsOfGenerators = new double[this.candidateGenerators.size()];
for (CostFunction c : costFunctions) {
c.prepare(cluster);
+ c.updateWeight(weightsOfGenerators);
}
}
@RestrictedApi(explanation = "Should only be called in tests", link = "",
allowedOnPath = ".*(/src/test/.*|StochasticLoadBalancer).java")
- void updateCostsWithAction(BalancerClusterState cluster, BalanceAction action) {
+ void updateCostsAndWeightsWithAction(BalancerClusterState cluster, BalanceAction action) {
+ // Reset all the weights to 0
+ for (int i = 0; i < weightsOfGenerators.length; i++) {
+ weightsOfGenerators[i] = 0;
+ }
for (CostFunction c : costFunctions) {
if (c.isNeeded()) {
c.postAction(action);
+ c.updateWeight(weightsOfGenerators);
}
}
}
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
index 0727d98..80df642 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
@@ -561,6 +561,15 @@ public class BalancerTestBase {
testWithCluster(serverMap, null, assertFullyBalanced, assertFullyBalancedForReplicas);
}
+ protected void testWithClusterWithIteration(int numNodes, int numRegions, int numRegionsPerServer,
+ int replication, int numTables, boolean assertFullyBalanced,
+ boolean assertFullyBalancedForReplicas) {
+ Map<ServerName, List<RegionInfo>> serverMap =
+ createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
+ testWithClusterWithIteration(serverMap, null, assertFullyBalanced,
+ assertFullyBalancedForReplicas);
+ }
+
protected void testWithCluster(Map<ServerName, List<RegionInfo>> serverMap,
RackManager rackManager, boolean assertFullyBalanced, boolean assertFullyBalancedForReplicas) {
List<ServerAndLoad> list = convertToList(serverMap);
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
index 639313b..9f9ac84 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
@@ -401,10 +401,10 @@ public class TestStochasticLoadBalancer extends BalancerTestBase {
final double expectedCost = loadBalancer.computeCost(cluster, Double.MAX_VALUE);
BalanceAction action = loadBalancer.nextAction(cluster);
cluster.doAction(action);
- loadBalancer.updateCostsWithAction(cluster, action);
+ loadBalancer.updateCostsAndWeightsWithAction(cluster, action);
BalanceAction undoAction = action.undoAction();
cluster.doAction(undoAction);
- loadBalancer.updateCostsWithAction(cluster, undoAction);
+ loadBalancer.updateCostsAndWeightsWithAction(cluster, undoAction);
final double actualCost = loadBalancer.computeCost(cluster, Double.MAX_VALUE);
assertEquals(expectedCost, actualCost, 0);
}
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerBalanceCluster.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerBalanceCluster.java
index 43c22c1..30a6729 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerBalanceCluster.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerBalanceCluster.java
@@ -51,7 +51,7 @@ public class TestStochasticLoadBalancerBalanceCluster extends BalancerTestBase {
*/
@Test
public void testBalanceCluster() throws Exception {
- conf.setLong("hbase.master.balancer.stochastic.maxRunningTime", 3 * 60 * 1000); // 3 min
+ conf.setLong("hbase.master.balancer.stochastic.maxRunningTime", 2 * 60 * 1000); // 2 min
conf.setLong(StochasticLoadBalancer.MAX_STEPS_KEY, 20000000L);
loadBalancer.onConfigurationChange(conf);
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerHeterogeneousCost.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerHeterogeneousCost.java
index cd6de3f..4696897 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerHeterogeneousCost.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerHeterogeneousCost.java
@@ -76,7 +76,7 @@ public class TestStochasticLoadBalancerHeterogeneousCost extends BalancerTestBas
BalancerTestBase.conf.set(
HeterogeneousRegionCountCostFunction.HBASE_MASTER_BALANCER_HETEROGENEOUS_RULES_FILE,
RULES_FILE);
- loadBalancer = new StochasticLoadBalancer();
+ loadBalancer = new StochasticLoadTestBalancer();
MasterServices services = mock(MasterServices.class);
when(services.getConfiguration()).thenReturn(conf);
BalancerTestBase.loadBalancer.setMasterServices(services);
@@ -307,4 +307,14 @@ public class TestStochasticLoadBalancerHeterogeneousCost extends BalancerTestBas
return super.generate(cluster);
}
}
+
+ static class StochasticLoadTestBalancer extends StochasticLoadBalancer {
+ private FairRandomCandidateGenerator fairRandomCandidateGenerator =
+ new FairRandomCandidateGenerator();
+
+ @Override
+ protected CandidateGenerator getRandomGenerator() {
+ return fairRandomCandidateGenerator;
+ }
+ }
}
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerLargeCluster.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerLargeCluster.java
index 7732c78..9ab1d9b 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerLargeCluster.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancerLargeCluster.java
@@ -41,6 +41,7 @@ public class TestStochasticLoadBalancerLargeCluster extends BalancerTestBase {
conf.setLong("hbase.master.balancer.stochastic.maxRunningTime", 6 * 60 * 1000);
conf.setLong(StochasticLoadBalancer.MAX_STEPS_KEY, 20000000L);
loadBalancer.onConfigurationChange(conf);
- testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
+ testWithClusterWithIteration(numNodes, numRegions, numRegionsPerServer, replication, numTables,
+ true, true);
}
}