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