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 org.apache.yetus.audience.InterfaceAudience;
022
023/**
024 * Generates candidates which moves the replicas out of the region server for
025 * co-hosted region replicas
026 */
027@InterfaceAudience.Private
028class RegionReplicaCandidateGenerator extends CandidateGenerator {
029
030  StochasticLoadBalancer.RandomCandidateGenerator randomGenerator =
031    new StochasticLoadBalancer.RandomCandidateGenerator();
032
033  /**
034   * Randomly select one regionIndex out of all region replicas co-hosted in the same group
035   * (a group is a server, host or rack)
036   *
037   * @param primariesOfRegionsPerGroup either Cluster.primariesOfRegionsPerServer,
038   *   primariesOfRegionsPerHost or primariesOfRegionsPerRack
039   * @param regionsPerGroup either Cluster.regionsPerServer, regionsPerHost or regionsPerRack
040   * @param regionIndexToPrimaryIndex Cluster.regionsIndexToPrimaryIndex
041   * @return a regionIndex for the selected primary or -1 if there is no co-locating
042   */
043  int selectCoHostedRegionPerGroup(int[] primariesOfRegionsPerGroup, int[] regionsPerGroup,
044      int[] regionIndexToPrimaryIndex) {
045    int currentPrimary = -1;
046    int currentPrimaryIndex = -1;
047    int selectedPrimaryIndex = -1;
048    double currentLargestRandom = -1;
049    // primariesOfRegionsPerGroup is a sorted array. Since it contains the primary region
050    // ids for the regions hosted in server, a consecutive repetition means that replicas
051    // are co-hosted
052    for (int j = 0; j <= primariesOfRegionsPerGroup.length; j++) {
053      int primary = j < primariesOfRegionsPerGroup.length
054        ? primariesOfRegionsPerGroup[j] : -1;
055      if (primary != currentPrimary) { // check for whether we see a new primary
056        int numReplicas = j - currentPrimaryIndex;
057        if (numReplicas > 1) { // means consecutive primaries, indicating co-location
058          // decide to select this primary region id or not
059          double currentRandom = StochasticLoadBalancer.RANDOM.nextDouble();
060          // we don't know how many region replicas are co-hosted, we will randomly select one
061          // using reservoir sampling (http://gregable.com/2007/10/reservoir-sampling.html)
062          if (currentRandom > currentLargestRandom) {
063            selectedPrimaryIndex = currentPrimary;
064            currentLargestRandom = currentRandom;
065          }
066        }
067        currentPrimary = primary;
068        currentPrimaryIndex = j;
069      }
070    }
071
072    // we have found the primary id for the region to move. Now find the actual regionIndex
073    // with the given primary, prefer to move the secondary region.
074    for (int regionIndex : regionsPerGroup) {
075      if (selectedPrimaryIndex == regionIndexToPrimaryIndex[regionIndex]) {
076        // always move the secondary, not the primary
077        if (selectedPrimaryIndex != regionIndex) {
078          return regionIndex;
079        }
080      }
081    }
082    return -1;
083  }
084
085  @Override
086  BaseLoadBalancer.Cluster.Action generate(BaseLoadBalancer.Cluster cluster) {
087    int serverIndex = pickRandomServer(cluster);
088    if (cluster.numServers <= 1 || serverIndex == -1) {
089      return BaseLoadBalancer.Cluster.NullAction;
090    }
091
092    int regionIndex = selectCoHostedRegionPerGroup(
093      cluster.primariesOfRegionsPerServer[serverIndex],
094      cluster.regionsPerServer[serverIndex],
095      cluster.regionIndexToPrimaryIndex);
096
097    // if there are no pairs of region replicas co-hosted, default to random generator
098    if (regionIndex == -1) {
099      // default to randompicker
100      return randomGenerator.generate(cluster);
101    }
102
103    int toServerIndex = pickOtherRandomServer(cluster, serverIndex);
104    int toRegionIndex = pickRandomRegion(cluster, toServerIndex, 0.9f);
105    return getAction(serverIndex, regionIndex, toServerIndex, toRegionIndex);
106  }
107
108}