001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018
019package org.apache.hadoop.hbase.master.balancer;
020
021import java.util.ArrayList;
022import java.util.Collections;
023import java.util.List;
024import java.util.Map;
025
026import org.apache.hadoop.hbase.client.RegionInfo;
027
028import org.apache.yetus.audience.InterfaceAudience;
029
030/**
031 * Generates a candidate action to be applied to the cluster for cost function search
032 */
033@InterfaceAudience.Private
034abstract class CandidateGenerator {
035
036  abstract BaseLoadBalancer.Cluster.Action generate(BaseLoadBalancer.Cluster cluster);
037
038  /**
039   * From a list of regions pick a random one. Null can be returned which
040   * {@link StochasticLoadBalancer#balanceCluster(Map)} recognize as signal to try a region move
041   * rather than swap.
042   *
043   * @param cluster The state of the cluster
044   * @param server index of the server
045   * @param chanceOfNoSwap Chance that this will decide to try a move rather
046   *   than a swap.
047   * @return a random {@link RegionInfo} or null if an asymmetrical move is
048   *   suggested.
049   */
050  int pickRandomRegion(BaseLoadBalancer.Cluster cluster, int server,
051    double chanceOfNoSwap) {
052    // Check to see if this is just a move.
053    if (cluster.regionsPerServer[server].length == 0
054        || StochasticLoadBalancer.RANDOM.nextFloat() < chanceOfNoSwap) {
055      // signal a move only.
056      return -1;
057    }
058    int rand = StochasticLoadBalancer.RANDOM.nextInt(cluster.regionsPerServer[server].length);
059    return cluster.regionsPerServer[server][rand];
060  }
061
062  int pickRandomServer(BaseLoadBalancer.Cluster cluster) {
063    if (cluster.numServers < 1) {
064      return -1;
065    }
066
067    return StochasticLoadBalancer.RANDOM.nextInt(cluster.numServers);
068  }
069
070  int pickRandomRack(BaseLoadBalancer.Cluster cluster) {
071    if (cluster.numRacks < 1) {
072      return -1;
073    }
074
075    return StochasticLoadBalancer.RANDOM.nextInt(cluster.numRacks);
076  }
077
078  int pickOtherRandomServer(BaseLoadBalancer.Cluster cluster, int serverIndex) {
079    if (cluster.numServers < 2) {
080      return -1;
081    }
082    while (true) {
083      int otherServerIndex = pickRandomServer(cluster);
084      if (otherServerIndex != serverIndex) {
085        return otherServerIndex;
086      }
087    }
088  }
089
090  int pickOtherRandomRack(BaseLoadBalancer.Cluster cluster, int rackIndex) {
091    if (cluster.numRacks < 2) {
092      return -1;
093    }
094    while (true) {
095      int otherRackIndex = pickRandomRack(cluster);
096      if (otherRackIndex != rackIndex) {
097        return otherRackIndex;
098      }
099    }
100  }
101
102  BaseLoadBalancer.Cluster.Action pickRandomRegions(BaseLoadBalancer.Cluster cluster,
103    int thisServer, int otherServer) {
104    if (thisServer < 0 || otherServer < 0) {
105      return BaseLoadBalancer.Cluster.NullAction;
106    }
107
108    // Decide who is most likely to need another region
109    int thisRegionCount = cluster.getNumRegions(thisServer);
110    int otherRegionCount = cluster.getNumRegions(otherServer);
111
112    // Assign the chance based upon the above
113    double thisChance = (thisRegionCount > otherRegionCount) ? 0 : 0.5;
114    double otherChance = (thisRegionCount <= otherRegionCount) ? 0 : 0.5;
115
116    int thisRegion = pickRandomRegion(cluster, thisServer, thisChance);
117    int otherRegion = pickRandomRegion(cluster, otherServer, otherChance);
118
119    return getAction(thisServer, thisRegion, otherServer, otherRegion);
120  }
121
122  protected BaseLoadBalancer.Cluster.Action getAction(int fromServer, int fromRegion,
123      int toServer, int toRegion) {
124    if (fromServer < 0 || toServer < 0) {
125      return BaseLoadBalancer.Cluster.NullAction;
126    }
127    if (fromRegion > 0 && toRegion > 0) {
128      return new BaseLoadBalancer.Cluster.SwapRegionsAction(fromServer, fromRegion,
129        toServer, toRegion);
130    } else if (fromRegion > 0) {
131      return new BaseLoadBalancer.Cluster.MoveRegionAction(fromRegion, fromServer, toServer);
132    } else if (toRegion > 0) {
133      return new BaseLoadBalancer.Cluster.MoveRegionAction(toRegion, toServer, fromServer);
134    } else {
135      return BaseLoadBalancer.Cluster.NullAction;
136    }
137  }
138
139  /**
140   * Returns a random iteration order of indexes of an array with size length
141   */
142  List<Integer> getRandomIterationOrder(int length) {
143    ArrayList<Integer> order = new ArrayList<>(length);
144    for (int i = 0; i < length; i++) {
145      order.add(i);
146    }
147    Collections.shuffle(order);
148    return order;
149  }
150
151}