View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.hadoop.hbase.master.balancer;
19  
20  import java.util.ArrayList;
21  import java.util.Arrays;
22  import java.util.Collection;
23  import java.util.Collections;
24  import java.util.Comparator;
25  import java.util.Deque;
26  import java.util.HashMap;
27  import java.util.HashSet;
28  import java.util.Iterator;
29  import java.util.List;
30  import java.util.Map;
31  import java.util.Map.Entry;
32  import java.util.NavigableMap;
33  import java.util.Random;
34  import java.util.Set;
35  import java.util.TreeMap;
36  
37  import org.apache.commons.lang.NotImplementedException;
38  import org.apache.commons.logging.Log;
39  import org.apache.commons.logging.LogFactory;
40  import org.apache.hadoop.conf.Configuration;
41  import org.apache.hadoop.hbase.ClusterStatus;
42  import org.apache.hadoop.hbase.HBaseIOException;
43  import org.apache.hadoop.hbase.HRegionInfo;
44  import org.apache.hadoop.hbase.RegionLoad;
45  import org.apache.hadoop.hbase.ServerName;
46  import org.apache.hadoop.hbase.TableName;
47  import org.apache.hadoop.hbase.client.RegionReplicaUtil;
48  import org.apache.hadoop.hbase.conf.ConfigurationObserver;
49  import org.apache.hadoop.hbase.master.LoadBalancer;
50  import org.apache.hadoop.hbase.master.MasterServices;
51  import org.apache.hadoop.hbase.master.RackManager;
52  import org.apache.hadoop.hbase.master.RegionPlan;
53  import org.apache.hadoop.hbase.master.balancer.BaseLoadBalancer.Cluster.Action.Type;
54  import org.apache.hadoop.hbase.security.access.AccessControlLists;
55  import org.apache.hadoop.util.StringUtils;
56  
57  import com.google.common.base.Joiner;
58  import com.google.common.collect.ArrayListMultimap;
59  import com.google.common.collect.Lists;
60  import com.google.common.collect.Sets;
61  
62  /**
63   * The base class for load balancers. It provides the the functions used to by
64   * {@link org.apache.hadoop.hbase.master.AssignmentManager} to assign regions 
65   * in the edge cases. It doesn't provide an implementation of the 
66   * actual balancing algorithm.
67   *
68   */
69  public abstract class BaseLoadBalancer implements LoadBalancer {
70    private static final int MIN_SERVER_BALANCE = 2;
71    private volatile boolean stopped = false;
72  
73    private static final List<HRegionInfo> EMPTY_REGION_LIST = new ArrayList<HRegionInfo>(0);
74  
75    protected final RegionLocationFinder regionFinder = new RegionLocationFinder();
76  
77    private static class DefaultRackManager extends RackManager {
78      @Override
79      public String getRack(ServerName server) {
80        return UNKNOWN_RACK;
81      }
82    }
83  
84    /**
85     * An efficient array based implementation similar to ClusterState for keeping
86     * the status of the cluster in terms of region assignment and distribution.
87     * LoadBalancers, such as StochasticLoadBalancer uses this Cluster object because of
88     * hundreds of thousands of hashmap manipulations are very costly, which is why this
89     * class uses mostly indexes and arrays.
90     *
91     * Cluster tracks a list of unassigned regions, region assignments, and the server
92     * topology in terms of server names, hostnames and racks.
93     */
94    protected static class Cluster {
95      ServerName[] servers;
96      String[] hosts; // ServerName uniquely identifies a region server. multiple RS can run on the same host
97      String[] racks;
98      boolean multiServersPerHost = false; // whether or not any host has more than one server
99  
100     ArrayList<String> tables;
101     HRegionInfo[] regions;
102     Deque<RegionLoad>[] regionLoads;
103 
104     int[][] regionLocations; //regionIndex -> list of serverIndex sorted by locality
105 
106     int[]   serverIndexToHostIndex;      //serverIndex -> host index
107     int[]   serverIndexToRackIndex;      //serverIndex -> rack index
108 
109     int[][] regionsPerServer;            //serverIndex -> region list
110     int[][] regionsPerHost;              //hostIndex -> list of regions
111     int[][] regionsPerRack;              //rackIndex -> region list
112     int[][] primariesOfRegionsPerServer; //serverIndex -> sorted list of regions by primary region index
113     int[][] primariesOfRegionsPerHost;   //hostIndex -> sorted list of regions by primary region index
114     int[][] primariesOfRegionsPerRack;   //rackIndex -> sorted list of regions by primary region index
115 
116     int[][] serversPerHost;              //hostIndex -> list of server indexes
117     int[][] serversPerRack;              //rackIndex -> list of server indexes
118     int[]   regionIndexToServerIndex;    //regionIndex -> serverIndex
119     int[]   initialRegionIndexToServerIndex;    //regionIndex -> serverIndex (initial cluster state)
120     int[]   regionIndexToTableIndex;     //regionIndex -> tableIndex
121     int[][] numRegionsPerServerPerTable; //serverIndex -> tableIndex -> # regions
122     int[]   numMaxRegionsPerTable;       //tableIndex -> max number of regions in a single RS
123     int[]   regionIndexToPrimaryIndex;   //regionIndex -> regionIndex of the primary
124     boolean hasRegionReplicas = false;   //whether there is regions with replicas
125 
126     Integer[] serverIndicesSortedByRegionCount;
127 
128     Map<String, Integer> serversToIndex;
129     Map<String, Integer> hostsToIndex;
130     Map<String, Integer> racksToIndex;
131     Map<String, Integer> tablesToIndex;
132     Map<HRegionInfo, Integer> regionsToIndex;
133 
134     int numServers;
135     int numHosts;
136     int numRacks;
137     int numTables;
138     int numRegions;
139 
140     int numMovedRegions = 0; //num moved regions from the initial configuration
141     // num of moved regions away from master that should be on the master
142     int numMovedMetaRegions = 0;       //num of moved regions that are META
143     Map<ServerName, List<HRegionInfo>> clusterState;
144 
145     protected final RackManager rackManager;
146 
147     protected Cluster(
148         Map<ServerName, List<HRegionInfo>> clusterState,
149         Map<String, Deque<RegionLoad>> loads,
150         RegionLocationFinder regionFinder,
151         RackManager rackManager) {
152       this(null, clusterState, loads, regionFinder,
153         rackManager);
154     }
155 
156     @SuppressWarnings("unchecked")
157     protected Cluster(
158         Collection<HRegionInfo> unassignedRegions,
159         Map<ServerName, List<HRegionInfo>> clusterState,
160         Map<String, Deque<RegionLoad>> loads,
161         RegionLocationFinder regionFinder,
162         RackManager rackManager) {
163 
164       if (unassignedRegions == null) {
165         unassignedRegions = EMPTY_REGION_LIST;
166       }
167 
168       serversToIndex = new HashMap<String, Integer>();
169       hostsToIndex = new HashMap<String, Integer>();
170       racksToIndex = new HashMap<String, Integer>();
171       tablesToIndex = new HashMap<String, Integer>();
172 
173       //TODO: We should get the list of tables from master
174       tables = new ArrayList<String>();
175       this.rackManager = rackManager != null ? rackManager : new DefaultRackManager();
176 
177       numRegions = 0;
178 
179       List<List<Integer>> serversPerHostList = new ArrayList<List<Integer>>();
180       List<List<Integer>> serversPerRackList = new ArrayList<List<Integer>>();
181       this.clusterState = clusterState;
182 
183       // Use servername and port as there can be dead servers in this list. We want everything with
184       // a matching hostname and port to have the same index.
185       for (ServerName sn : clusterState.keySet()) {
186         if (serversToIndex.get(sn.getHostAndPort()) == null) {
187           serversToIndex.put(sn.getHostAndPort(), numServers++);
188         }
189         if (!hostsToIndex.containsKey(sn.getHostname())) {
190           hostsToIndex.put(sn.getHostname(), numHosts++);
191           serversPerHostList.add(new ArrayList<Integer>(1));
192         }
193 
194         int serverIndex = serversToIndex.get(sn.getHostAndPort());
195         int hostIndex = hostsToIndex.get(sn.getHostname());
196         serversPerHostList.get(hostIndex).add(serverIndex);
197 
198         String rack = this.rackManager.getRack(sn);
199         if (!racksToIndex.containsKey(rack)) {
200           racksToIndex.put(rack, numRacks++);
201           serversPerRackList.add(new ArrayList<Integer>());
202         }
203         int rackIndex = racksToIndex.get(rack);
204         serversPerRackList.get(rackIndex).add(serverIndex);
205       }
206 
207       // Count how many regions there are.
208       for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
209         numRegions += entry.getValue().size();
210       }
211       numRegions += unassignedRegions.size();
212 
213       regionsToIndex = new HashMap<HRegionInfo, Integer>(numRegions);
214       servers = new ServerName[numServers];
215       serversPerHost = new int[numHosts][];
216       serversPerRack = new int[numRacks][];
217       regions = new HRegionInfo[numRegions];
218       regionIndexToServerIndex = new int[numRegions];
219       initialRegionIndexToServerIndex = new int[numRegions];
220       regionIndexToTableIndex = new int[numRegions];
221       regionIndexToPrimaryIndex = new int[numRegions];
222       regionLoads = new Deque[numRegions];
223       regionLocations = new int[numRegions][];
224       serverIndicesSortedByRegionCount = new Integer[numServers];
225 
226       serverIndexToHostIndex = new int[numServers];
227       serverIndexToRackIndex = new int[numServers];
228       regionsPerServer = new int[numServers][];
229       regionsPerHost = new int[numHosts][];
230       regionsPerRack = new int[numRacks][];
231       primariesOfRegionsPerServer = new int[numServers][];
232       primariesOfRegionsPerHost = new int[numHosts][];
233       primariesOfRegionsPerRack = new int[numRacks][];
234 
235       int tableIndex = 0, regionIndex = 0, regionPerServerIndex = 0;
236 
237       for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
238         int serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
239 
240         // keep the servername if this is the first server name for this hostname
241         // or this servername has the newest startcode.
242         if (servers[serverIndex] == null ||
243             servers[serverIndex].getStartcode() < entry.getKey().getStartcode()) {
244           servers[serverIndex] = entry.getKey();
245         }
246 
247         if (regionsPerServer[serverIndex] != null) {
248           // there is another server with the same hostAndPort in ClusterState.
249           // allocate the array for the total size
250           regionsPerServer[serverIndex] = new int[entry.getValue().size() + regionsPerServer[serverIndex].length];
251         } else {
252           regionsPerServer[serverIndex] = new int[entry.getValue().size()];
253         }
254         primariesOfRegionsPerServer[serverIndex] = new int[regionsPerServer[serverIndex].length];
255         serverIndicesSortedByRegionCount[serverIndex] = serverIndex;
256       }
257 
258       hosts = new String[numHosts];
259       for (Entry<String, Integer> entry : hostsToIndex.entrySet()) {
260         hosts[entry.getValue()] = entry.getKey();
261       }
262       racks = new String[numRacks];
263       for (Entry<String, Integer> entry : racksToIndex.entrySet()) {
264         racks[entry.getValue()] = entry.getKey();
265       }
266 
267       for (Entry<ServerName, List<HRegionInfo>> entry : clusterState.entrySet()) {
268         int serverIndex = serversToIndex.get(entry.getKey().getHostAndPort());
269         regionPerServerIndex = 0;
270 
271         int hostIndex = hostsToIndex.get(entry.getKey().getHostname());
272         serverIndexToHostIndex[serverIndex] = hostIndex;
273 
274         int rackIndex = racksToIndex.get(this.rackManager.getRack(entry.getKey()));
275         serverIndexToRackIndex[serverIndex] = rackIndex;
276 
277         for (HRegionInfo region : entry.getValue()) {
278           registerRegion(region, regionIndex, serverIndex, loads, regionFinder);
279 
280           regionsPerServer[serverIndex][regionPerServerIndex++] = regionIndex;
281           regionIndex++;
282         }
283       }
284       for (HRegionInfo region : unassignedRegions) {
285         registerRegion(region, regionIndex, -1, loads, regionFinder);
286         regionIndex++;
287       }
288 
289       for (int i = 0; i < serversPerHostList.size(); i++) {
290         serversPerHost[i] = new int[serversPerHostList.get(i).size()];
291         for (int j = 0; j < serversPerHost[i].length; j++) {
292           serversPerHost[i][j] = serversPerHostList.get(i).get(j);
293         }
294         if (serversPerHost[i].length > 1) {
295           multiServersPerHost = true;
296         }
297       }
298 
299       for (int i = 0; i < serversPerRackList.size(); i++) {
300         serversPerRack[i] = new int[serversPerRackList.get(i).size()];
301         for (int j = 0; j < serversPerRack[i].length; j++) {
302           serversPerRack[i][j] = serversPerRackList.get(i).get(j);
303         }
304       }
305 
306       numTables = tables.size();
307       numRegionsPerServerPerTable = new int[numServers][numTables];
308 
309       for (int i = 0; i < numServers; i++) {
310         for (int j = 0; j < numTables; j++) {
311           numRegionsPerServerPerTable[i][j] = 0;
312         }
313       }
314 
315       for (int i=0; i < regionIndexToServerIndex.length; i++) {
316         if (regionIndexToServerIndex[i] >= 0) {
317           numRegionsPerServerPerTable[regionIndexToServerIndex[i]][regionIndexToTableIndex[i]]++;
318         }
319       }
320 
321       numMaxRegionsPerTable = new int[numTables];
322       for (int serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
323         for (tableIndex = 0 ; tableIndex < numRegionsPerServerPerTable[serverIndex].length; tableIndex++) {
324           if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
325             numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
326           }
327         }
328       }
329 
330       for (int i = 0; i < regions.length; i ++) {
331         HRegionInfo info = regions[i];
332         if (RegionReplicaUtil.isDefaultReplica(info)) {
333           regionIndexToPrimaryIndex[i] = i;
334         } else {
335           hasRegionReplicas = true;
336           HRegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
337           regionIndexToPrimaryIndex[i] =
338               regionsToIndex.containsKey(primaryInfo) ?
339               regionsToIndex.get(primaryInfo):
340               -1;
341         }
342       }
343 
344       for (int i = 0; i < regionsPerServer.length; i++) {
345         primariesOfRegionsPerServer[i] = new int[regionsPerServer[i].length];
346         for (int j = 0; j < regionsPerServer[i].length; j++) {
347           int primaryIndex = regionIndexToPrimaryIndex[regionsPerServer[i][j]];
348           primariesOfRegionsPerServer[i][j] = primaryIndex;
349         }
350         // sort the regions by primaries.
351         Arrays.sort(primariesOfRegionsPerServer[i]);
352       }
353 
354       // compute regionsPerHost
355       if (multiServersPerHost) {
356         for (int i = 0 ; i < serversPerHost.length; i++) {
357           int numRegionsPerHost = 0;
358           for (int j = 0; j < serversPerHost[i].length; j++) {
359             numRegionsPerHost += regionsPerServer[serversPerHost[i][j]].length;
360           }
361           regionsPerHost[i] = new int[numRegionsPerHost];
362           primariesOfRegionsPerHost[i] = new int[numRegionsPerHost];
363         }
364         for (int i = 0 ; i < serversPerHost.length; i++) {
365           int numRegionPerHostIndex = 0;
366           for (int j = 0; j < serversPerHost[i].length; j++) {
367             for (int k = 0; k < regionsPerServer[serversPerHost[i][j]].length; k++) {
368               int region = regionsPerServer[serversPerHost[i][j]][k];
369               regionsPerHost[i][numRegionPerHostIndex] = region;
370               int primaryIndex = regionIndexToPrimaryIndex[region];
371               primariesOfRegionsPerHost[i][numRegionPerHostIndex] = primaryIndex;
372               numRegionPerHostIndex++;
373             }
374           }
375           // sort the regions by primaries.
376           Arrays.sort(primariesOfRegionsPerHost[i]);
377         }
378       }
379 
380       // compute regionsPerRack
381       if (numRacks > 1) {
382         for (int i = 0 ; i < serversPerRack.length; i++) {
383           int numRegionsPerRack = 0;
384           for (int j = 0; j < serversPerRack[i].length; j++) {
385             numRegionsPerRack += regionsPerServer[serversPerRack[i][j]].length;
386           }
387           regionsPerRack[i] = new int[numRegionsPerRack];
388           primariesOfRegionsPerRack[i] = new int[numRegionsPerRack];
389         }
390 
391         for (int i = 0 ; i < serversPerRack.length; i++) {
392           int numRegionPerRackIndex = 0;
393           for (int j = 0; j < serversPerRack[i].length; j++) {
394             for (int k = 0; k < regionsPerServer[serversPerRack[i][j]].length; k++) {
395               int region = regionsPerServer[serversPerRack[i][j]][k];
396               regionsPerRack[i][numRegionPerRackIndex] = region;
397               int primaryIndex = regionIndexToPrimaryIndex[region];
398               primariesOfRegionsPerRack[i][numRegionPerRackIndex] = primaryIndex;
399               numRegionPerRackIndex++;
400             }
401           }
402           // sort the regions by primaries.
403           Arrays.sort(primariesOfRegionsPerRack[i]);
404         }
405       }
406     }
407 
408     /** Helper for Cluster constructor to handle a region */
409     private void registerRegion(HRegionInfo region, int regionIndex, int serverIndex,
410         Map<String, Deque<RegionLoad>> loads, RegionLocationFinder regionFinder) {
411       String tableName = region.getTable().getNameAsString();
412       if (!tablesToIndex.containsKey(tableName)) {
413         tables.add(tableName);
414         tablesToIndex.put(tableName, tablesToIndex.size());
415       }
416       int tableIndex = tablesToIndex.get(tableName);
417 
418       regionsToIndex.put(region, regionIndex);
419       regions[regionIndex] = region;
420       regionIndexToServerIndex[regionIndex] = serverIndex;
421       initialRegionIndexToServerIndex[regionIndex] = serverIndex;
422       regionIndexToTableIndex[regionIndex] = tableIndex;
423 
424       // region load
425       if (loads != null) {
426         Deque<RegionLoad> rl = loads.get(region.getRegionNameAsString());
427         // That could have failed if the RegionLoad is using the other regionName
428         if (rl == null) {
429           // Try getting the region load using encoded name.
430           rl = loads.get(region.getEncodedName());
431         }
432         regionLoads[regionIndex] = rl;
433       }
434 
435       if (regionFinder != null) {
436         //region location
437         List<ServerName> loc = regionFinder.getTopBlockLocations(region);
438         regionLocations[regionIndex] = new int[loc.size()];
439         for (int i=0; i < loc.size(); i++) {
440           regionLocations[regionIndex][i] =
441               loc.get(i) == null ? -1 :
442                 (serversToIndex.get(loc.get(i).getHostAndPort()) == null ? -1
443                     : serversToIndex.get(loc.get(i).getHostAndPort()));
444         }
445       }
446     }
447 
448     /** An action to move or swap a region */
449     public static class Action {
450       public static enum Type {
451         ASSIGN_REGION,
452         MOVE_REGION,
453         SWAP_REGIONS,
454         NULL,
455       }
456 
457       public Type type;
458       public Action (Type type) {this.type = type;}
459       /** Returns an Action which would undo this action */
460       public Action undoAction() { return this; }
461       @Override
462       public String toString() { return type + ":";}
463     }
464 
465     public static class AssignRegionAction extends Action {
466       public int region;
467       public int server;
468       public AssignRegionAction(int region, int server) {
469         super(Type.ASSIGN_REGION);
470         this.region = region;
471         this.server = server;
472       }
473       @Override
474       public Action undoAction() {
475         // TODO implement this. This action is not being used by the StochasticLB for now
476         // in case it uses it, we should implement this function.
477         throw new NotImplementedException();
478       }
479       @Override
480       public String toString() {
481         return type + ": " + region + ":" + server;
482       }
483     }
484 
485     public static class MoveRegionAction extends Action {
486       public int region;
487       public int fromServer;
488       public int toServer;
489 
490       public MoveRegionAction(int region, int fromServer, int toServer) {
491         super(Type.MOVE_REGION);
492         this.fromServer = fromServer;
493         this.region = region;
494         this.toServer = toServer;
495       }
496       @Override
497       public Action undoAction() {
498         return new MoveRegionAction (region, toServer, fromServer);
499       }
500       @Override
501       public String toString() {
502         return type + ": " + region + ":" + fromServer + " -> " + toServer;
503       }
504     }
505 
506     public static class SwapRegionsAction extends Action {
507       public int fromServer;
508       public int fromRegion;
509       public int toServer;
510       public int toRegion;
511       public SwapRegionsAction(int fromServer, int fromRegion, int toServer, int toRegion) {
512         super(Type.SWAP_REGIONS);
513         this.fromServer = fromServer;
514         this.fromRegion = fromRegion;
515         this.toServer = toServer;
516         this.toRegion = toRegion;
517       }
518       @Override
519       public Action undoAction() {
520         return new SwapRegionsAction (fromServer, toRegion, toServer, fromRegion);
521       }
522       @Override
523       public String toString() {
524         return type + ": " + fromRegion + ":" + fromServer + " <-> " + toRegion + ":" + toServer;
525       }
526     }
527 
528     @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="NM_FIELD_NAMING_CONVENTION",
529         justification="Mistake. Too disruptive to change now")
530     public static final Action NullAction = new Action(Type.NULL);
531 
532     public void doAction(Action action) {
533       switch (action.type) {
534       case NULL: break;
535       case ASSIGN_REGION:
536         AssignRegionAction ar = (AssignRegionAction) action;
537         regionsPerServer[ar.server] = addRegion(regionsPerServer[ar.server], ar.region);
538         regionMoved(ar.region, -1, ar.server);
539         break;
540       case MOVE_REGION:
541         MoveRegionAction mra = (MoveRegionAction) action;
542         regionsPerServer[mra.fromServer] = removeRegion(regionsPerServer[mra.fromServer], mra.region);
543         regionsPerServer[mra.toServer] = addRegion(regionsPerServer[mra.toServer], mra.region);
544         regionMoved(mra.region, mra.fromServer, mra.toServer);
545         break;
546       case SWAP_REGIONS:
547         SwapRegionsAction a = (SwapRegionsAction) action;
548         regionsPerServer[a.fromServer] = replaceRegion(regionsPerServer[a.fromServer], a.fromRegion, a.toRegion);
549         regionsPerServer[a.toServer] = replaceRegion(regionsPerServer[a.toServer], a.toRegion, a.fromRegion);
550         regionMoved(a.fromRegion, a.fromServer, a.toServer);
551         regionMoved(a.toRegion, a.toServer, a.fromServer);
552         break;
553       default:
554         throw new RuntimeException("Uknown action:" + action.type);
555       }
556     }
557 
558     /**
559      * Return true if the placement of region on server would lower the availability
560      * of the region in question
561      * @param server
562      * @param region
563      * @return true or false
564      */
565     boolean wouldLowerAvailability(HRegionInfo regionInfo, ServerName serverName) {
566       if (!serversToIndex.containsKey(serverName.getHostAndPort())) {
567         return false; // safeguard against race between cluster.servers and servers from LB method args
568       }
569       int server = serversToIndex.get(serverName.getHostAndPort());
570       int region = regionsToIndex.get(regionInfo);
571 
572       int primary = regionIndexToPrimaryIndex[region];
573 
574       // there is a subset relation for server < host < rack
575       // check server first
576 
577       if (contains(primariesOfRegionsPerServer[server], primary)) {
578         // check for whether there are other servers that we can place this region
579         for (int i = 0; i < primariesOfRegionsPerServer.length; i++) {
580           if (i != server && !contains(primariesOfRegionsPerServer[i], primary)) {
581             return true; // meaning there is a better server
582           }
583         }
584         return false; // there is not a better server to place this
585       }
586 
587       // check host
588       if (multiServersPerHost) { // these arrays would only be allocated if we have more than one server per host
589         int host = serverIndexToHostIndex[server];
590         if (contains(primariesOfRegionsPerHost[host], primary)) {
591           // check for whether there are other hosts that we can place this region
592           for (int i = 0; i < primariesOfRegionsPerHost.length; i++) {
593             if (i != host && !contains(primariesOfRegionsPerHost[i], primary)) {
594               return true; // meaning there is a better host
595             }
596           }
597           return false; // there is not a better host to place this
598         }
599       }
600 
601       // check rack
602       if (numRacks > 1) {
603         int rack = serverIndexToRackIndex[server];
604         if (contains(primariesOfRegionsPerRack[rack], primary)) {
605           // check for whether there are other racks that we can place this region
606           for (int i = 0; i < primariesOfRegionsPerRack.length; i++) {
607             if (i != rack && !contains(primariesOfRegionsPerRack[i], primary)) {
608               return true; // meaning there is a better rack
609             }
610           }
611           return false; // there is not a better rack to place this
612         }
613       }
614       return false;
615     }
616 
617     void doAssignRegion(HRegionInfo regionInfo, ServerName serverName) {
618       if (!serversToIndex.containsKey(serverName.getHostAndPort())) {
619         return;
620       }
621       int server = serversToIndex.get(serverName.getHostAndPort());
622       int region = regionsToIndex.get(regionInfo);
623       doAction(new AssignRegionAction(region, server));
624     }
625 
626     void regionMoved(int region, int oldServer, int newServer) {
627       regionIndexToServerIndex[region] = newServer;
628       if (initialRegionIndexToServerIndex[region] == newServer) {
629         numMovedRegions--; //region moved back to original location
630       } else if (oldServer >= 0 && initialRegionIndexToServerIndex[region] == oldServer) {
631         numMovedRegions++; //region moved from original location
632       }
633       int tableIndex = regionIndexToTableIndex[region];
634       if (oldServer >= 0) {
635         numRegionsPerServerPerTable[oldServer][tableIndex]--;
636       }
637       numRegionsPerServerPerTable[newServer][tableIndex]++;
638 
639       //check whether this caused maxRegionsPerTable in the new Server to be updated
640       if (numRegionsPerServerPerTable[newServer][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
641         numRegionsPerServerPerTable[newServer][tableIndex] = numMaxRegionsPerTable[tableIndex];
642       } else if (oldServer >= 0 && (numRegionsPerServerPerTable[oldServer][tableIndex] + 1)
643           == numMaxRegionsPerTable[tableIndex]) {
644         //recompute maxRegionsPerTable since the previous value was coming from the old server
645         for (int serverIndex = 0 ; serverIndex < numRegionsPerServerPerTable.length; serverIndex++) {
646           if (numRegionsPerServerPerTable[serverIndex][tableIndex] > numMaxRegionsPerTable[tableIndex]) {
647             numMaxRegionsPerTable[tableIndex] = numRegionsPerServerPerTable[serverIndex][tableIndex];
648           }
649         }
650       }
651 
652       // update for servers
653       int primary = regionIndexToPrimaryIndex[region];
654       if (oldServer >= 0) {
655         primariesOfRegionsPerServer[oldServer] = removeRegion(
656           primariesOfRegionsPerServer[oldServer], primary);
657       }
658       primariesOfRegionsPerServer[newServer] = addRegionSorted(
659         primariesOfRegionsPerServer[newServer], primary);
660 
661       // update for hosts
662       if (multiServersPerHost) {
663         int oldHost = oldServer >= 0 ? serverIndexToHostIndex[oldServer] : -1;
664         int newHost = serverIndexToHostIndex[newServer];
665         if (newHost != oldHost) {
666           regionsPerHost[newHost] = addRegion(regionsPerHost[newHost], region);
667           primariesOfRegionsPerHost[newHost] = addRegionSorted(primariesOfRegionsPerHost[newHost], primary);
668           if (oldHost >= 0) {
669             regionsPerHost[oldHost] = removeRegion(regionsPerHost[oldHost], region);
670             primariesOfRegionsPerHost[oldHost] = removeRegion(
671               primariesOfRegionsPerHost[oldHost], primary); // will still be sorted
672           }
673         }
674       }
675 
676       // update for racks
677       if (numRacks > 1) {
678         int oldRack = oldServer >= 0 ? serverIndexToRackIndex[oldServer] : -1;
679         int newRack = serverIndexToRackIndex[newServer];
680         if (newRack != oldRack) {
681           regionsPerRack[newRack] = addRegion(regionsPerRack[newRack], region);
682           primariesOfRegionsPerRack[newRack] = addRegionSorted(primariesOfRegionsPerRack[newRack], primary);
683           if (oldRack >= 0) {
684             regionsPerRack[oldRack] = removeRegion(regionsPerRack[oldRack], region);
685             primariesOfRegionsPerRack[oldRack] = removeRegion(
686               primariesOfRegionsPerRack[oldRack], primary); // will still be sorted
687           }
688         }
689       }
690     }
691 
692     int[] removeRegion(int[] regions, int regionIndex) {
693       //TODO: this maybe costly. Consider using linked lists
694       int[] newRegions = new int[regions.length - 1];
695       int i = 0;
696       for (i = 0; i < regions.length; i++) {
697         if (regions[i] == regionIndex) {
698           break;
699         }
700         newRegions[i] = regions[i];
701       }
702       System.arraycopy(regions, i+1, newRegions, i, newRegions.length - i);
703       return newRegions;
704     }
705 
706     int[] addRegion(int[] regions, int regionIndex) {
707       int[] newRegions = new int[regions.length + 1];
708       System.arraycopy(regions, 0, newRegions, 0, regions.length);
709       newRegions[newRegions.length - 1] = regionIndex;
710       return newRegions;
711     }
712 
713     int[] addRegionSorted(int[] regions, int regionIndex) {
714       int[] newRegions = new int[regions.length + 1];
715       int i = 0;
716       for (i = 0; i < regions.length; i++) { // find the index to insert
717         if (regions[i] > regionIndex) {
718           break;
719         }
720       }
721       System.arraycopy(regions, 0, newRegions, 0, i); // copy first half
722       System.arraycopy(regions, i, newRegions, i+1, regions.length - i); // copy second half
723       newRegions[i] = regionIndex;
724 
725       return newRegions;
726     }
727 
728     int[] replaceRegion(int[] regions, int regionIndex, int newRegionIndex) {
729       int i = 0;
730       for (i = 0; i < regions.length; i++) {
731         if (regions[i] == regionIndex) {
732           regions[i] = newRegionIndex;
733           break;
734         }
735       }
736       return regions;
737     }
738 
739     void sortServersByRegionCount() {
740       Arrays.sort(serverIndicesSortedByRegionCount, numRegionsComparator);
741     }
742 
743     int getNumRegions(int server) {
744       return regionsPerServer[server].length;
745     }
746 
747     boolean contains(int[] arr, int val) {
748       return Arrays.binarySearch(arr, val) >= 0;
749     }
750 
751     private Comparator<Integer> numRegionsComparator = new Comparator<Integer>() {
752       @Override
753       public int compare(Integer integer, Integer integer2) {
754         return Integer.valueOf(getNumRegions(integer)).compareTo(getNumRegions(integer2));
755       }
756     };
757 
758     @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="SBSC_USE_STRINGBUFFER_CONCATENATION",
759         justification="Not important but should be fixed")
760     @Override
761     public String toString() {
762       String desc = "Cluster{" +
763           "servers=[";
764           for(ServerName sn:servers) {
765              desc += sn.getHostAndPort() + ", ";
766           }
767           desc +=
768           ", serverIndicesSortedByRegionCount="+
769           Arrays.toString(serverIndicesSortedByRegionCount) +
770           ", regionsPerServer=[";
771 
772           for (int[]r:regionsPerServer) {
773             desc += Arrays.toString(r);
774           }
775           desc += "]" +
776           ", numMaxRegionsPerTable=" +
777           Arrays.toString(numMaxRegionsPerTable) +
778           ", numRegions=" +
779           numRegions +
780           ", numServers=" +
781           numServers +
782           ", numTables=" +
783           numTables +
784           ", numMovedRegions=" +
785           numMovedRegions +
786           '}';
787       return desc;
788     }
789   }
790 
791   // slop for regions
792   protected float slop;
793   protected Configuration config;
794   protected RackManager rackManager;
795   private static final Random RANDOM = new Random(System.currentTimeMillis());
796   private static final Log LOG = LogFactory.getLog(BaseLoadBalancer.class);
797 
798   // Regions of these tables are put on the master by default.
799   private static final String[] DEFAULT_TABLES_ON_MASTER =
800     new String[] {AccessControlLists.ACL_TABLE_NAME.getNameAsString(),
801       TableName.NAMESPACE_TABLE_NAME.getNameAsString(),
802       TableName.META_TABLE_NAME.getNameAsString()};
803 
804   public static final String TABLES_ON_MASTER =
805     "hbase.balancer.tablesOnMaster";
806 
807   protected final Set<String> tablesOnMaster = new HashSet<String>();
808   protected final MetricsBalancer metricsBalancer = new MetricsBalancer();
809   protected ClusterStatus clusterStatus = null;
810   protected ServerName masterServerName;
811   protected MasterServices services;
812 
813   /**
814    * By default, regions of some small system tables such as meta,
815    * namespace, and acl are assigned to the active master. If you don't
816    * want to assign any region to the active master, you need to
817    * configure "hbase.balancer.tablesOnMaster" to "none".
818    */
819   protected static String[] getTablesOnMaster(Configuration conf) {
820     String valueString = conf.get(TABLES_ON_MASTER);
821     if (valueString == null) {
822       return DEFAULT_TABLES_ON_MASTER;
823     }
824     valueString = valueString.trim();
825     if (valueString.equalsIgnoreCase("none")) {
826       return null;
827     }
828     return StringUtils.getStrings(valueString);
829   }
830 
831   /**
832    * Check if configured to put any tables on the active master
833    */
834   public static boolean tablesOnMaster(Configuration conf) {
835     String[] tables = getTablesOnMaster(conf);
836     return tables != null && tables.length > 0;
837   }
838 
839   @Override
840   public void setConf(Configuration conf) {
841     setSlop(conf);
842     if (slop < 0) slop = 0;
843     else if (slop > 1) slop = 1;
844 
845     this.config = conf;
846     String[] tables = getTablesOnMaster(conf);
847     if (tables != null && tables.length > 0) {
848       Collections.addAll(tablesOnMaster, tables);
849     }
850     this.rackManager = new RackManager(getConf());
851     regionFinder.setConf(conf);
852   }
853 
854   protected void setSlop(Configuration conf) {
855     this.slop = conf.getFloat("hbase.regions.slop", (float) 0.2);
856   }
857 
858   /**
859    * Check if a region belongs to some small system table.
860    * If so, it may be expected to be put on the master regionserver.
861    */
862   public boolean shouldBeOnMaster(HRegionInfo region) {
863     return tablesOnMaster.contains(region.getTable().getNameAsString());
864   }
865 
866   /**
867    * Balance the regions that should be on master regionserver.
868    */
869   protected List<RegionPlan> balanceMasterRegions(
870       Map<ServerName, List<HRegionInfo>> clusterMap) {
871     if (masterServerName == null
872         || clusterMap == null || clusterMap.size() <= 1) return null;
873     List<RegionPlan> plans = null;
874     List<HRegionInfo> regions = clusterMap.get(masterServerName);
875     if (regions != null) {
876       Iterator<ServerName> keyIt = null;
877       for (HRegionInfo region: regions) {
878         if (shouldBeOnMaster(region)) continue;
879 
880         // Find a non-master regionserver to host the region
881         if (keyIt == null || !keyIt.hasNext()) {
882           keyIt = clusterMap.keySet().iterator();
883         }
884         ServerName dest = keyIt.next();
885         if (masterServerName.equals(dest)) {
886           if (!keyIt.hasNext()) {
887             keyIt = clusterMap.keySet().iterator();
888           }
889           dest = keyIt.next();
890         }
891 
892         // Move this region away from the master regionserver
893         RegionPlan plan = new RegionPlan(region, masterServerName, dest);
894         if (plans == null) {
895           plans = new ArrayList<RegionPlan>();
896         }
897         plans.add(plan);
898       }
899     }
900     for (Map.Entry<ServerName, List<HRegionInfo>> server: clusterMap.entrySet()) {
901       if (masterServerName.equals(server.getKey())) continue;
902       for (HRegionInfo region: server.getValue()) {
903         if (!shouldBeOnMaster(region)) continue;
904 
905         // Move this region to the master regionserver
906         RegionPlan plan = new RegionPlan(region, server.getKey(), masterServerName);
907         if (plans == null) {
908           plans = new ArrayList<RegionPlan>();
909         }
910         plans.add(plan);
911       }
912     }
913     return plans;
914   }
915 
916   /**
917    * Assign the regions that should be on master regionserver.
918    */
919   protected Map<ServerName, List<HRegionInfo>> assignMasterRegions(
920       Collection<HRegionInfo> regions, List<ServerName> servers) {
921     if (servers == null || regions == null || regions.isEmpty()) {
922       return null;
923     }
924     Map<ServerName, List<HRegionInfo>> assignments
925       = new TreeMap<ServerName, List<HRegionInfo>>();
926     if (masterServerName != null && servers.contains(masterServerName)) {
927       assignments.put(masterServerName, new ArrayList<HRegionInfo>());
928       for (HRegionInfo region: regions) {
929         if (shouldBeOnMaster(region)) {
930           assignments.get(masterServerName).add(region);
931         }
932       }
933     }
934     return assignments;
935   }
936 
937   @Override
938   public Configuration getConf() {
939     return this.config;
940   }
941 
942   @Override
943   public void setClusterStatus(ClusterStatus st) {
944     this.clusterStatus = st;
945     regionFinder.setClusterStatus(st);
946   }
947 
948   @Override
949   public void setMasterServices(MasterServices masterServices) {
950     masterServerName = masterServices.getServerName();
951     this.services = masterServices;
952     this.regionFinder.setServices(masterServices);
953   }
954 
955   public void setRackManager(RackManager rackManager) {
956     this.rackManager = rackManager;
957   }
958 
959   protected boolean needsBalance(Cluster c) {
960     ClusterLoadState cs = new ClusterLoadState(c.clusterState);
961     if (cs.getNumServers() < MIN_SERVER_BALANCE) {
962       if (LOG.isDebugEnabled()) {
963         LOG.debug("Not running balancer because only " + cs.getNumServers()
964             + " active regionserver(s)");
965       }
966       return false;
967     }
968     if(areSomeRegionReplicasColocated(c)) return true;
969     // Check if we even need to do any load balancing
970     // HBASE-3681 check sloppiness first
971     float average = cs.getLoadAverage(); // for logging
972     int floor = (int) Math.floor(average * (1 - slop));
973     int ceiling = (int) Math.ceil(average * (1 + slop));
974     if (!(cs.getMaxLoad() > ceiling || cs.getMinLoad() < floor)) {
975       NavigableMap<ServerAndLoad, List<HRegionInfo>> serversByLoad = cs.getServersByLoad();
976       if (LOG.isTraceEnabled()) {
977         // If nothing to balance, then don't say anything unless trace-level logging.
978         LOG.trace("Skipping load balancing because balanced cluster; " +
979           "servers=" + cs.getNumServers() +
980           " regions=" + cs.getNumRegions() + " average=" + average +
981           " mostloaded=" + serversByLoad.lastKey().getLoad() +
982           " leastloaded=" + serversByLoad.firstKey().getLoad());
983       }
984       return false;
985     }
986     return true;
987   }
988 
989   /**
990    * Subclasses should implement this to return true if the cluster has nodes that hosts
991    * multiple replicas for the same region, or, if there are multiple racks and the same
992    * rack hosts replicas of the same region
993    * @param c Cluster information
994    * @return whether region replicas are currently co-located
995    */
996   protected boolean areSomeRegionReplicasColocated(Cluster c) {
997     return false;
998   }
999 
1000   /**
1001    * Generates a bulk assignment plan to be used on cluster startup using a
1002    * simple round-robin assignment.
1003    * <p>
1004    * Takes a list of all the regions and all the servers in the cluster and
1005    * returns a map of each server to the regions that it should be assigned.
1006    * <p>
1007    * Currently implemented as a round-robin assignment. Same invariant as load
1008    * balancing, all servers holding floor(avg) or ceiling(avg).
1009    *
1010    * TODO: Use block locations from HDFS to place regions with their blocks
1011    *
1012    * @param regions all regions
1013    * @param servers all servers
1014    * @return map of server to the regions it should take, or null if no
1015    *         assignment is possible (ie. no regions or no servers)
1016    */
1017   @Override
1018   public Map<ServerName, List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions,
1019       List<ServerName> servers) {
1020     metricsBalancer.incrMiscInvocations();
1021     Map<ServerName, List<HRegionInfo>> assignments = assignMasterRegions(regions, servers);
1022     if (assignments != null && !assignments.isEmpty()) {
1023       servers = new ArrayList<ServerName>(servers);
1024       // Guarantee not to put other regions on master
1025       servers.remove(masterServerName);
1026       List<HRegionInfo> masterRegions = assignments.get(masterServerName);
1027       if (!masterRegions.isEmpty()) {
1028         regions = new ArrayList<HRegionInfo>(regions);
1029         for (HRegionInfo region: masterRegions) {
1030           regions.remove(region);
1031         }
1032       }
1033     }
1034     if (regions == null || regions.isEmpty()) {
1035       return assignments;
1036     }
1037 
1038     int numServers = servers == null ? 0 : servers.size();
1039     if (numServers == 0) {
1040       LOG.warn("Wanted to do round robin assignment but no servers to assign to");
1041       return null;
1042     }
1043 
1044     // TODO: instead of retainAssignment() and roundRobinAssignment(), we should just run the
1045     // normal LB.balancerCluster() with unassignedRegions. We only need to have a candidate
1046     // generator for AssignRegionAction. The LB will ensure the regions are mostly local
1047     // and balanced. This should also run fast with fewer number of iterations.
1048 
1049     if (numServers == 1) { // Only one server, nothing fancy we can do here
1050       ServerName server = servers.get(0);
1051       assignments.put(server, new ArrayList<HRegionInfo>(regions));
1052       return assignments;
1053     }
1054 
1055     Cluster cluster = createCluster(servers, regions);
1056     List<HRegionInfo> unassignedRegions = new ArrayList<HRegionInfo>();
1057 
1058     roundRobinAssignment(cluster, regions, unassignedRegions,
1059       servers, assignments);
1060 
1061     List<HRegionInfo> lastFewRegions = new ArrayList<HRegionInfo>();
1062     // assign the remaining by going through the list and try to assign to servers one-by-one
1063     int serverIdx = RANDOM.nextInt(numServers);
1064     for (HRegionInfo region : unassignedRegions) {
1065       boolean assigned = false;
1066       for (int j = 0; j < numServers; j++) { // try all servers one by one
1067         ServerName serverName = servers.get((j + serverIdx) % numServers);
1068         if (!cluster.wouldLowerAvailability(region, serverName)) {
1069           List<HRegionInfo> serverRegions = assignments.get(serverName);
1070           if (serverRegions == null) {
1071             serverRegions = new ArrayList<HRegionInfo>();
1072             assignments.put(serverName, serverRegions);
1073           }
1074           serverRegions.add(region);
1075           cluster.doAssignRegion(region, serverName);
1076           serverIdx = (j + serverIdx + 1) % numServers; //remain from next server
1077           assigned = true;
1078           break;
1079         }
1080       }
1081       if (!assigned) {
1082         lastFewRegions.add(region);
1083       }
1084     }
1085     // just sprinkle the rest of the regions on random regionservers. The balanceCluster will
1086     // make it optimal later. we can end up with this if numReplicas > numServers.
1087     for (HRegionInfo region : lastFewRegions) {
1088       int i = RANDOM.nextInt(numServers);
1089       ServerName server = servers.get(i);
1090       List<HRegionInfo> serverRegions = assignments.get(server);
1091       if (serverRegions == null) {
1092         serverRegions = new ArrayList<HRegionInfo>();
1093         assignments.put(server, serverRegions);
1094       }
1095       serverRegions.add(region);
1096       cluster.doAssignRegion(region, server);
1097     }
1098     return assignments;
1099   }
1100 
1101   protected Cluster createCluster(List<ServerName> servers,
1102       Collection<HRegionInfo> regions) {
1103     // Get the snapshot of the current assignments for the regions in question, and then create
1104     // a cluster out of it. Note that we might have replicas already assigned to some servers
1105     // earlier. So we want to get the snapshot to see those assignments, but this will only contain
1106     // replicas of the regions that are passed (for performance).
1107     Map<ServerName, List<HRegionInfo>> clusterState = getRegionAssignmentsByServer(regions);
1108 
1109     for (ServerName server : servers) {
1110       if (!clusterState.containsKey(server)) {
1111         clusterState.put(server, EMPTY_REGION_LIST);
1112       }
1113     }
1114     return new Cluster(regions, clusterState, null, this.regionFinder,
1115       rackManager);
1116   }
1117 
1118   /**
1119    * Generates an immediate assignment plan to be used by a new master for
1120    * regions in transition that do not have an already known destination.
1121    *
1122    * Takes a list of regions that need immediate assignment and a list of all
1123    * available servers. Returns a map of regions to the server they should be
1124    * assigned to.
1125    *
1126    * This method will return quickly and does not do any intelligent balancing.
1127    * The goal is to make a fast decision not the best decision possible.
1128    *
1129    * Currently this is random.
1130    *
1131    * @param regions
1132    * @param servers
1133    * @return map of regions to the server it should be assigned to
1134    */
1135   @Override
1136   public Map<HRegionInfo, ServerName> immediateAssignment(List<HRegionInfo> regions,
1137       List<ServerName> servers) {
1138     metricsBalancer.incrMiscInvocations();
1139     if (servers == null || servers.isEmpty()) {
1140       LOG.warn("Wanted to do random assignment but no servers to assign to");
1141       return null;
1142     }
1143 
1144     Map<HRegionInfo, ServerName> assignments = new TreeMap<HRegionInfo, ServerName>();
1145     for (HRegionInfo region : regions) {
1146       assignments.put(region, randomAssignment(region, servers));
1147     }
1148     return assignments;
1149   }
1150 
1151   /**
1152    * Used to assign a single region to a random server.
1153    */
1154   @Override
1155   public ServerName randomAssignment(HRegionInfo regionInfo, List<ServerName> servers) {
1156     metricsBalancer.incrMiscInvocations();
1157     if (servers != null && servers.contains(masterServerName)) {
1158       if (shouldBeOnMaster(regionInfo)) {
1159         return masterServerName;
1160       }
1161       servers = new ArrayList<ServerName>(servers);
1162       // Guarantee not to put other regions on master
1163       servers.remove(masterServerName);
1164     }
1165 
1166     int numServers = servers == null ? 0 : servers.size();
1167     if (numServers == 0) {
1168       LOG.warn("Wanted to do retain assignment but no servers to assign to");
1169       return null;
1170     }
1171     if (numServers == 1) { // Only one server, nothing fancy we can do here
1172       return servers.get(0);
1173     }
1174 
1175     List<HRegionInfo> regions = Lists.newArrayList(regionInfo);
1176     Cluster cluster = createCluster(servers, regions);
1177     return randomAssignment(cluster, regionInfo, servers);
1178   }
1179 
1180   /**
1181    * Generates a bulk assignment startup plan, attempting to reuse the existing
1182    * assignment information from META, but adjusting for the specified list of
1183    * available/online servers available for assignment.
1184    * <p>
1185    * Takes a map of all regions to their existing assignment from META. Also
1186    * takes a list of online servers for regions to be assigned to. Attempts to
1187    * retain all assignment, so in some instances initial assignment will not be
1188    * completely balanced.
1189    * <p>
1190    * Any leftover regions without an existing server to be assigned to will be
1191    * assigned randomly to available servers.
1192    *
1193    * @param regions regions and existing assignment from meta
1194    * @param servers available servers
1195    * @return map of servers and regions to be assigned to them
1196    */
1197   @Override
1198   public Map<ServerName, List<HRegionInfo>> retainAssignment(Map<HRegionInfo, ServerName> regions,
1199       List<ServerName> servers) {
1200     // Update metrics
1201     metricsBalancer.incrMiscInvocations();
1202     Map<ServerName, List<HRegionInfo>> assignments
1203       = assignMasterRegions(regions.keySet(), servers);
1204     if (assignments != null && !assignments.isEmpty()) {
1205       servers = new ArrayList<ServerName>(servers);
1206       // Guarantee not to put other regions on master
1207       servers.remove(masterServerName);
1208       List<HRegionInfo> masterRegions = assignments.get(masterServerName);
1209       if (!masterRegions.isEmpty()) {
1210         regions = new HashMap<HRegionInfo, ServerName>(regions);
1211         for (HRegionInfo region: masterRegions) {
1212           regions.remove(region);
1213         }
1214       }
1215     }
1216     if (regions == null || regions.isEmpty()) {
1217       return assignments;
1218     }
1219 
1220     int numServers = servers == null ? 0 : servers.size();
1221     if (numServers == 0) {
1222       LOG.warn("Wanted to do retain assignment but no servers to assign to");
1223       return null;
1224     }
1225     if (numServers == 1) { // Only one server, nothing fancy we can do here
1226       ServerName server = servers.get(0);
1227       assignments.put(server, new ArrayList<HRegionInfo>(regions.keySet()));
1228       return assignments;
1229     }
1230 
1231     // Group all of the old assignments by their hostname.
1232     // We can't group directly by ServerName since the servers all have
1233     // new start-codes.
1234 
1235     // Group the servers by their hostname. It's possible we have multiple
1236     // servers on the same host on different ports.
1237     ArrayListMultimap<String, ServerName> serversByHostname = ArrayListMultimap.create();
1238     for (ServerName server : servers) {
1239       assignments.put(server, new ArrayList<HRegionInfo>());
1240       serversByHostname.put(server.getHostname(), server);
1241     }
1242 
1243     // Collection of the hostnames that used to have regions
1244     // assigned, but for which we no longer have any RS running
1245     // after the cluster restart.
1246     Set<String> oldHostsNoLongerPresent = Sets.newTreeSet();
1247 
1248     int numRandomAssignments = 0;
1249     int numRetainedAssigments = 0;
1250 
1251     Cluster cluster = createCluster(servers, regions.keySet());
1252 
1253     for (Map.Entry<HRegionInfo, ServerName> entry : regions.entrySet()) {
1254       HRegionInfo region = entry.getKey();
1255       ServerName oldServerName = entry.getValue();
1256       List<ServerName> localServers = new ArrayList<ServerName>();
1257       if (oldServerName != null) {
1258         localServers = serversByHostname.get(oldServerName.getHostname());
1259       }
1260       if (localServers.isEmpty()) {
1261         // No servers on the new cluster match up with this hostname,
1262         // assign randomly.
1263         ServerName randomServer = randomAssignment(cluster, region, servers);
1264         assignments.get(randomServer).add(region);
1265         numRandomAssignments++;
1266         if (oldServerName != null) oldHostsNoLongerPresent.add(oldServerName.getHostname());
1267       } else if (localServers.size() == 1) {
1268         // the usual case - one new server on same host
1269         ServerName target = localServers.get(0);
1270         assignments.get(target).add(region);
1271         cluster.doAssignRegion(region, target);
1272         numRetainedAssigments++;
1273       } else {
1274         // multiple new servers in the cluster on this same host
1275         if (localServers.contains(oldServerName)) {
1276           assignments.get(oldServerName).add(region);
1277           cluster.doAssignRegion(region, oldServerName);
1278         } else {
1279           ServerName target = null;
1280           for (ServerName tmp: localServers) {
1281             if (tmp.getPort() == oldServerName.getPort()) {
1282               target = tmp;
1283               break;
1284             }
1285           }
1286           if (target == null) {
1287             target = randomAssignment(cluster, region, localServers);
1288           }
1289           assignments.get(target).add(region);
1290         }
1291         numRetainedAssigments++;
1292       }
1293     }
1294 
1295     String randomAssignMsg = "";
1296     if (numRandomAssignments > 0) {
1297       randomAssignMsg =
1298           numRandomAssignments + " regions were assigned "
1299               + "to random hosts, since the old hosts for these regions are no "
1300               + "longer present in the cluster. These hosts were:\n  "
1301               + Joiner.on("\n  ").join(oldHostsNoLongerPresent);
1302     }
1303 
1304     LOG.info("Reassigned " + regions.size() + " regions. " + numRetainedAssigments
1305         + " retained the pre-restart assignment. " + randomAssignMsg);
1306     return assignments;
1307   }
1308 
1309   @Override
1310   public void initialize() throws HBaseIOException{
1311   }
1312 
1313   @Override
1314   public void regionOnline(HRegionInfo regionInfo, ServerName sn) {
1315   }
1316 
1317   @Override
1318   public void regionOffline(HRegionInfo regionInfo) {
1319   }
1320 
1321   @Override
1322   public boolean isStopped() {
1323     return stopped;
1324   }
1325 
1326   @Override
1327   public void stop(String why) {
1328     LOG.info("Load Balancer stop requested: "+why);
1329     stopped = true;
1330   }
1331 
1332   /**
1333    * Used to assign a single region to a random server.
1334    */
1335   private ServerName randomAssignment(Cluster cluster, HRegionInfo regionInfo,
1336       List<ServerName> servers) {
1337     int numServers = servers.size(); // servers is not null, numServers > 1
1338     ServerName sn = null;
1339     final int maxIterations = numServers * 4;
1340     int iterations = 0;
1341 
1342     do {
1343       int i = RANDOM.nextInt(numServers);
1344       sn = servers.get(i);
1345     } while (cluster.wouldLowerAvailability(regionInfo, sn)
1346         && iterations++ < maxIterations);
1347     cluster.doAssignRegion(regionInfo, sn);
1348     return sn;
1349   }
1350 
1351   /**
1352    * Round robin a list of regions to a list of servers
1353    */
1354   private void roundRobinAssignment(Cluster cluster, List<HRegionInfo> regions,
1355       List<HRegionInfo> unassignedRegions, List<ServerName> servers,
1356       Map<ServerName, List<HRegionInfo>> assignments) {
1357 
1358     int numServers = servers.size();
1359     int numRegions = regions.size();
1360     int max = (int) Math.ceil((float) numRegions / numServers);
1361     int serverIdx = 0;
1362     if (numServers > 1) {
1363       serverIdx = RANDOM.nextInt(numServers);
1364     }
1365     int regionIdx = 0;
1366 
1367     for (int j = 0; j < numServers; j++) {
1368       ServerName server = servers.get((j + serverIdx) % numServers);
1369       List<HRegionInfo> serverRegions = new ArrayList<HRegionInfo>(max);
1370       for (int i = regionIdx; i < numRegions; i += numServers) {
1371         HRegionInfo region = regions.get(i % numRegions);
1372         if (cluster.wouldLowerAvailability(region, server)) {
1373           unassignedRegions.add(region);
1374         } else {
1375           serverRegions.add(region);
1376           cluster.doAssignRegion(region, server);
1377         }
1378       }
1379       assignments.put(server, serverRegions);
1380       regionIdx++;
1381     }
1382   }
1383 
1384   protected Map<ServerName, List<HRegionInfo>> getRegionAssignmentsByServer(
1385     Collection<HRegionInfo> regions) {
1386     if (this.services != null && this.services.getAssignmentManager() != null) {
1387       return this.services.getAssignmentManager().getSnapShotOfAssignment(regions);
1388     } else {
1389       return new HashMap<ServerName, List<HRegionInfo>>();
1390     }
1391   }
1392 
1393   @Override
1394   public void onConfigurationChange(Configuration conf) {
1395   }
1396 }